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

一、单选题（共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、 abcd+−
B、 abc+d−
C、 abc+d−
D、 −+abcd

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);
}

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;
}

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、 198
B、 195
C、 197
D、 196

39、按照二叉树的定义，具有三个结点的二叉树有（）棵。（2.0）
A、 5
B、 4
C、 3
D、 6

40、二叉树中第5层上的结点个数最多为( )（2.0）
A、 8
B、 15
C、 16
D、 20

41、一棵完全二叉树上有768个结点，则该二叉树中叶子结点的个数是（）。（2.0）
A、 257
B、 258
C、 384
D、 385

42、若G是一个非连通无向图，共有28条边，则该图至少有多少个顶点（）。（2.0）
A、 7
B、 8
C、 9
D、 27

43、【2014统考真题】下列选项中，不可能是快速排序第2趟排序结果是（）。（2.0）
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）
A、递归次数与初始数据的排列次序无关
B、每次划分后，先处理较长的分区可以减少递归次数
C、每次划分后，先处理较短的分区可以减少递归次数
D、递归次数与每次划分后得到的分区的处理顺序无关

45、【2019统考真题】排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是（）。（2.0）
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、顺序存储
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）
A、冒泡排序
B、希尔排序
C、归并排序
D、基数排序

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

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

49、【2015统考真题】下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是（）。（2.0）
A、直接插入排序
B、冒泡排序
C、基数排序
D、快速排序

50、【2017统考真题】下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是（）。
Ⅰ．插入排序 Ⅱ．选择排序 Ⅲ．冒泡排序 Ⅳ．希尔排序 Ⅴ．堆排序（2.0）
A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ
C、仅Ⅲ、Ⅳ
D、仅Ⅳ、Ⅴ