2022年中国民用航空飞行学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdfVIP

2022年中国民用航空飞行学院计算机科学与技术专业《数据结构与算

法》科目期末试卷A（有答案）

一、选择题

1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放

在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并

2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-1

3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续

4、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

5、已知串S=aaab，其next数组值为（）。

A.0123B.1123C.1231D.1211

6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1

A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ

7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序

方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序

A．仅Ⅰ、Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、ⅣD．仅Ⅲ、Ⅳ、Ⅴ

8、有关二叉树下列说法正确的是（）。

A.二叉树的度为2

B.一棵二叉树的度可以小于2

C.二叉树中至少有一个结点的度为2

D.二叉树中任何一个结点的度都为2

9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

D.其中度为2的结点最多为一个

10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，

4，8，20，9，7}则该次采用的增量是（）。

A.1B.4C.3D.2

二、填空题

11、若用n表示图中顶点数目，则有______条边的无向图成为完全图。

12、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m，n）为这种表

示方式的数目。例f（5，3）=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，

1+1+1+1+1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整。

②执行程序，f（6，4）=______。

13、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则

删除一个元素平均需要移动元素的个数是______。

14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、

______、______、______。

15、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，

请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag，left，data，

right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，

right指向其右孩子，rflag=1，right指向其后继。

16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为

______。

17、已知U=‘xyxyxyxxyxy’；t=‘xxy’；A