数据结构：期末考第六次测试（总复习）

一、单选题（共50题，100分）

1、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（ D ）.（2.0）
A、（n−1）/2
B、 n
C、 n+1
D、 n/2

2、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列为e2、e4、e3、e6、e5和e1，则栈S的容量至少应该为（ C ）。（2.0）
A、 6
B、 4
C、 3
D、 2

3、设栈的输入序列为1、2、3… n，若输出序列的第一个元素为n，则第i个输出的元素为（ B ）。（2.0）
A、不确定
B、 n−i+1
C、 i
D、 n−i

4、在一个长度为n的顺序表中删除第i个元素（1<=i<=n）时，需向前移动（）个元素。（2.0）
A、 n−i
B、 n−i+1
C、 n−i−1
D、 i

5、若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（）。（2.0）
A、O(n)
B、 O(1)
C、O( $n^2$ )
D、O( $n^3$ )

6、表达式 $a * (b + c) - d$ 的后缀表达式是（）。（2.0）
A、 $ab c d * + -$
B、 $ab c + * d -$
C、 $ab c * + d -$
D、 $- + * ab c d$

7、顺序循环队列中（数组的大小为n），队头指示front指向队列的第1个元素，队尾指示rear指向队列最后元素的后1个位置，则循环队列中存放了n - 1个元素，即循环队列满的条件为（）。（2.0）
A、 (rear+1)%n=front−1
B、 (rear+1)%n=front
C、 (rear)%n=front
D、 rear+1=front

8、两个有序线性表分别具有n个元素与m个元素且n≤m，现将其归并成一个有序表，其最少的比较次数是（）。（2.0）
A、n
B、 m
C、 n−1
D、 m+n

9、在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（）。（2.0）
A、O(1)
B、O(n)
C、O( $n^2$ )
D、O( $nlog_{2^n}$ )

10、若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（）。（2.0）
A、O(n)
B、O( $n^2$ )
C、O( $n^3$ )
D、O( $n×log2^n$ )

11、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）。（2.0）
A、 s->next=p;p->next=s;
B、 s->next=p->next;p->next=s;
C、 s->next=p->next;p=s;
D、 p->next=s;s->next=p;

12、前序遍历和后序遍历结果相同的二叉树为（）。（2.0）
A、一般二叉树
B、只有根结点的二叉树
C、根结点无左孩子的二叉树
D、根结点无右孩子的二叉树
E、所有结点只有左子树的二叉树
F、所有结点只有右子树的二叉树

13、一棵具有5层的满二叉树所包含的结点个数为（）。（2.0）
A．15
B．31
C．63
D．32

14、如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（）。（2.0）
A、有向完全图
B、连通图
C、强连通图
D、有向无环图

15、若邻接表中有奇数个表结点，则一定（）。（2.0）
A、图中有奇数个顶点
B、图中有偶数个顶点
C、图为无向图
D、图为有向图

16、假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（）。（2.0）
A、 O(n)
B、 O(e)
C、 O(n+e)
D、 O( $n * e$ )

17、下列哪一个选项不是图8.34所示有向图的拓扑排序结果（）。（2.0）

A、 AFBCDE
B、 FABCDE
C、 FACBDE
D、 FADBCE

18、判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。（2.0）
A、单源最短路Dijkstra算法
B、所有顶点对最短路Floyd算法
C、广度优先遍历算法
D、深度优先遍历算法

19、在一个带权连通图G中，权值最小的边一定包含在G的（）。（2.0）
A、最小生成树中
B、深度优先生成树中
C、广度优先生成树中
D、深度优先生成森林中

20、适用于折半查找的表的存储方式及元素排列要求为（）。（2.0）
A、链式方式存储，元素无序
B、链式方式存储，元素有序
C、顺序方式存储，元素无序
D、顺序方式存储，元素有序

21、设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（）。（2.0）
A、 21
B、 23
C、 41
D、 62

22、已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（）。（2.0）
A、 1.0
B、 2.9
C、 3.4
D、 5.5

23、以下各选项所示的各棵二叉树中，二叉排序树是（）。（2.0）

A、

B、

C、

D、

24、有数据{53，30，37，12，45，24，96}，从空二叉树开始逐步插入数据形成二叉排序树，若希望高度最小，则应该选择下列（）的序列输入。（2.0）
A、 37,24,12,30,53,45,96
B、 45,24,53,12,37,96,30
C、 12,24,30,37,45,53,96
D、 30,24,12,37,45,96,53

25、对于哈希函数H(key)=key%13，被称为同义词的关键字是（）。（2.0）
A、 35和41
B、 23和39
C、 15和44
D、 25和51

26、下列序列中，（）是执行第一趟快速排序后得到的序列。（2.0）
A、 [da,ax,eb,de,bb]ff[ha,gc]
B、 [cd,eb,ax,da]ff[ha,gc,bb]
C、 [gc,ax,eb,cd,bb]ff[da,ha]
D、 [ax,bb,cd,da]ff[eb,gc,ha]

27、下面的序列中初始序列构成最小堆（小根堆）的是（）。（2.0）
A、 10、60、20、50、30、26、35、40
B、 70、40、36、30、20、16、28、10
C、 20、60、50、40、30、10、8、72
D、 10、30、20、50、40、26、35、60

28、在下列算法中，（）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。（2.0）
A、堆排序
B、插入排序
C、冒泡排序
D、快速排序

29、若需在O（nlogn）的时间内完成对数组的排序，且要求排序算法是稳定的，则可选择的排序方法是（）。（2.0）
A、归并排序
B、堆排序
C、快速排序
D、直接插入排序

30、以下排序方法中，不稳定的排序方法是（）。（2.0）
A、直接选择排序
B、二分法插入排序
C、归并排序
D、基数排序

31、一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（）方法。（2.0）
A、快速排序
B、堆排序
C、插入排序
D、二路归并排序

32、若要求尽可能快地对实数数组进行稳定的排序，则应选（）。（2.0）
A、快速排序
B、堆排序
C、归并排序
D、基数排序

33、排序的趟数与待排序元素的原始状态有关的排序方法是（）。（2.0）
A、冒泡排序
B、快速排序
C、插入排序
D、选择排序

34、直接插入排序在最好情况下的时间复杂度为（）。（2.0）
A、 O（n）
B、 O（log n）
C、 O（nlog n）
D、 O（n2）

35、下面程序运行后的输出结果是（）。（2.0）

#include <stdio.h>
void f(int *p);
int main(){  int a[5]={1,2,3,4,5},*r=a;f(r);printf("%d\n",*r);
}
void f(int *p){  p=p+3;printf("%d,",*p);
}

1、在main函数中，我们定义了一个整数数组a并初始化为{1,2,3,4,5}，然后定义了一个指向a的指针r。
2、调用函数f并将r的地址作为参数传递给它。
3、在函数f中，指针p被初始化为传递给它的地址（即a数组的地址）。然后，p被增加3个整数单位（即指向了a[3]），并打印出*p的值，即a[3]的值，也就是4。
4、但是，需要注意的是，在f函数中，p是一个局部指针变量，对p的修改（即p=p+3;）不会影响到main函数中的r。这是因为p和r是两个不同的指针变量，它们各自在内存中保存了不同的地址值。
5、回到main函数，由于r没有被修改，它仍然指向a数组的开始，即a[0]。因此，printf(“%d\n”,*r);将打印出a[0]的值，也就是1。
6、所以，最终的输出结果是4,（来自f函数）和1（来自main函数），中间用换行符分隔。但由于题目只要求输出结果（没有要求换行符），我们通常只写出4,1作为答案。

A、 1,3
B、 3,3
C、 3,1
D、 4,1

36、下面程序的输出结果是什么（）。（2.0）

\#include <stdio.h>
int main( ){int x=20,y=40,*p;p=&x;printf("%d,",*p);*p=x+10;p=&y;printf("%d,",*p);*p=y+20;printf("%d,%d\n",x,y);return 0;
}

1、初始化变量 x 为 20，y 为 40，并声明一个整数指针 p。
2、p 被赋值为 &x，即 p 指向变量 x 的地址。
3、打印 *p 的值，由于 p 指向 x，所以输出 x 的值，即 20。输出为 20,。
4、将 x 的值加上 10 后赋给 *p，即 x 的值被修改为 30（因为 p 指向 x）。
5、p 被重新赋值为 &y，即 p 现在指向变量 y 的地址。
6、打印 *p 的值，由于 p 指向 y，所以输出 y 的值，即 40。输出为 40,。
7、将 y 的值加上 20 后赋给 *p，即 y 的值被修改为 60（因为 p 指向 y）。
8、最后，打印 x 和 y 的值。此时 x 的值是 30（在第4步中被修改过），y 的值是 60（在第7步中被修改过）。输出为 30,60。
所以，整个程序的输出是：
20,40,30,60
注意，在 printf 语句中，逗号 , 也会被打印出来，作为输出的一部分。

A、 20,40,20,40
B、 20,40,30,60
C、 20,40,20,40
D、 30,60,30,60

37、二维数组M[i][j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围是0 ~ 4，列下标j的范围是0 ~ 5，M按行存储时元素M[3][5]的起始地址与M按列存储时地址相同的元素是（）。（2.0）
A、 M[2][4]
B、 M[3][4]
C、 M[3][5]
D、 M[4][4]

38、将三对角矩阵A[1…100][1…100]按行优先存入一维数组B[1…298]中，A中元素A[66][65]在数组B中的位置为（）。（2.0）

[解析] 根据三对角对阵压缩方法
将A[1…n][1…n]压缩至B[0…3n-3]时，aij与bk的对应关系为:k=2i+j-3;
将A[1…n[1…n]压缩至B[1…3n-2]时，aij与bk的对应关系为:k=2i+j-2;
根据题目，A中元素A66,65，在B数组中的位置k为:k=2i+j-2=2x66+65-2=195

A、 198
B、 195
C、 197
D、 196

39、按照二叉树的定义，具有三个结点的二叉树有（）棵。（2.0）

5种。分别是：根-左-左；根-右-右；根-（一左一右）；根-左-右；根-右-左。

A、 5
B、 4
C、 3
D、 6

40、二叉树中第5层上的结点个数最多为( )（2.0）

非空二叉树的第i层上最多有 $2^{i-1}$ 个结点

A、 8
B、 15
C、 16
D、 20

41、一棵完全二叉树上有768个结点，则该二叉树中叶子结点的个数是（）。（2.0）

完全二叉树的叶子节点数 = (总节点数+1)/2，结果向下取整。(768+1)/2 = 384。

A、 257
B、 258
C、 384
D、 385

42、若G是一个非连通无向图，共有28条边，则该图至少有多少个顶点（）。（2.0）

完全图边数=28，解n(n-1)/2=28，得n=8，因此N=8+1=9.

A、 7
B、 8
C、 9
D、 27

43、【2014统考真题】下列选项中，不可能是快速排序第2趟排序结果是（）。（2.0）

快速排序：每趟排序过后，选定的pre的位置确定；即两趟意味选项中至少有两个位置是确定

A、 2，3，5，4，6，7，9
B、 2，7，5，6，4，3，9
C、 3，2，5，4，7，6，9
D、 4，2，3，5，7，6，9

44、【2010统考真题】采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（）。（2.0）

原始快速排序的其中一步是选取第一位数字作为分界线，把当前数组中小于它的放到左边，大于它的放到右边。如果初始数据是降序排列，要通过快排生成升序序列，那么递归次数会大大增加，就是O(n)，如果每次选取的恰好是中位数，递归次数就是O(logn)。所以一般都会对原始的快速排序加上随机选择“分界线”，就避免了初始数据对时间复杂度的影响。
那么递归次序就和分区处理顺序无关。

A、递归次数与初始数据的排列次序无关
B、每次划分后，先处理较长的分区可以减少递归次数
C、每次划分后，先处理较短的分区可以减少递归次数
D、递归次数与每次划分后得到的分区的处理顺序无关

45、【2019统考真题】排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是（）。（2.0）

答案：D，分析如下。
每经过一趟快排，轴点元素都必然就位。也就是说，一趟下来至少有1个元素在其最终位置。所以考察各个选项，看有几个元素就位即可。
最终排序位置是：2, 5, 12, 16, 28, 32, 60, 72，而选项中正确的位置有：
A. 5, 2, 16, 12, 28, 60, 32, 72
B. 2, 16, 5, 28, 12, 60, 32, 72
C. 2, 12, 16, 5, 28, 32, 72, 60
D. 5, 2, 12, 28, 16, 32, 72, 60
第一趟排序，确定一个元素位置
第二趟排序，又确定一个或两个元素位置
当第一趟元素确认的位置为最左或最右时，第二趟排序只能确认一个位置（A，B选项情况）
当第一趟元素确认位置不是最左或最右时，第二趟能确认2个位置（C选项情况）
所以，两趟排序共确认2或3个元素位置。
原文链接：http://t.csdnimg.cn/gJyu1

A、 5，2，16，12，28，60，32，72
B、 2，16，5，28，12，60，32，72
C、 2，12，16，5，28，32，72，60
D、 5，2，12，28，16，32，72，60

46、【2011统考真题】为实现快速排序算法，待排序序列宜采用的存储方式是（）。（2.0）

快速排序中元素进行比较，需要快速查询，而顺序存储适用于频繁快速查询
故答案：A 顺序存储
（摘抄）
1、顺序存储方式：顺序存储方式就是在一块连续的存储区域（物理）一个接着一个的存放数据。一般采用数组或结构数组来描述。
2、链式存储方式：链式存储方式比较灵活，节点逻辑上相邻，但不要求节点在物理位置上（存储区域）相邻，一个节点的引用字段往往指向下一个节点的存放位置，比如链表；
3、索引存储方式：索引存储方式是采用附加的索引表的方式来存储节点信息的一种存储方式。索引表由若干索引项组成。索引存储方式中索引项的一般形式为(关键字、地址)；
4、散列存储方式：散列存储方式是根据节点o的关键字，利用散列函数直接计算出该节点的存储地址的一种存储方式。

A、顺序存储
B、散列存储
C、链式存储
D、索引存储

47、【2010统考真题】对一组数据（2，12，16，88，5，10）进行排序，若前3趟排序结果如下：
第1趟排序结果：2，12，16，5，10，88
第2趟排序结果：2，12，5，10，16，88
第3趟排序结果：2，5，10，12，16，88
则采用的排序的方法可能是（）。（2.0）

冒泡排序过程:从第1个记录开始到第n个记录，对相邻记录的关键字进行比较，若与排序要求相逆，则将交换，这样一趟后，具有最大关键字的记录交换到最后；然后从第1个记录开始到第n-1个记录继续进行第2趟冒泡，使得具有次最大关键字的记录换到倒数第2个位置；进行n-1趟冒泡后，达到n个记录按关键码排序

A、冒泡排序
B、希尔排序
C、归并排序
D、基数排序

48、【2012统考真题】在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每趟排序结束后都至少能够确定一个元素最终位置的方法是（）。
Ⅰ．简单选择排序 Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排序 Ⅴ．2路归并排序（2.0）

每一次排序之后都能确定至少一个元素位置的排序方法包括:
1.选择排序:每次将最大的数放到最后。所以最大的数排一次序后位置就确定了。
2.冒泡排序:同选择排序。每一次排序最大的值位置确定。
3.快排:每一次排序pivot的位置确定。
4.堆排序:每一次排序时，都是将堆顶的元素和最后一个节点互换，然后调整堆，再将堆大小减1。所以每一次排序堆顶元素确定。
不能至少确定一个元素的位置的方法包括:
1.插入排序:不到最后一步求的都是相对位置。
2.shell排序:对简单插入排序的改进。不到最后一步，是无法确定每个元素位置的。
3.归井排序:同部有序，并不能确定任一元素在全局的位置。
4.基数排序，计数排序:利用桶排序的思路，不是基于比较的排序，也无法在一次排序中确定某个元素的位置。因为每一次排序都是整体处理。