数据结构（本科）期末综合练习一（单选题）

数据结构（本科）期末综合练习一（单选题）

单选题

1. 一个数组元素a[i] 与( )的表示等价。

A. *(a+i) B. a+i C. *a+i D. &a+i

2. 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。 A. 指针 B. 引用 C. 传值 D. 常值

3. 下面程序段的时间复杂度为( )。 for(int i=0; i

for(int j=0; j

22

A. O(m) B. O(n) C. O(m*n) D. O(m+n)

4. 执行下面程序段时，执行S语句的次数为( )。 for(int i=1; i<=n; i++)

for(int j=1; j<=i; j++) S;

22

A. n B. n/2 C. n(n+1) D. n(n+1)/2

5. 下面算法的时间复杂度为( )。 int f(unsigned int n) {

if(n==0 || n==1) return 1; else return n*f (n-1); }

2

A. O(1) B. O(n) C. O(n) D. O(n!)

6. 一种抽象数据类型包括数据和( )两个部分。

A. 数据类型 B. 操作 C. 数据抽象 D. 类型说明

7. 当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为( )，以节省参数值的传输时间和存储参数的空间。

A. 基本类型 B. 引用型 C. 指针型 D. 常值引用型

8. 当需要进行标准I/O操作时，则应在程序文件中包含iostream.h头文件，当需要进行文件I/O操作时，则应在程序文件中包含( )头文件。

A.fstream.h B.stdlib.h C.iomanip.h D.string.h

9. 一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空

1

间的大小即记录长度为( )。

A. 所有域长度之和 B. 最大域所占字节长度 C. 任意一个域长度 D. sizeof(r)的值

10. 输出一个二维数组b[m][n]中所有元素值的时间复杂度为( )。

2

A. O(n) B. O(m+n) C. O(n) D. O(m*n)

2

11. 一个算法的时间复杂度为(3n+2nlog2n+4n-7)/(5n)，其数量级形式的复杂度表示为( )。

2

A. O(n) B. O(nlog2n) C. O(n) D. O(log2n)

2

12. 某算法的时间代价为T(n)=100n+10nlog2n+n+10，其时间复杂度为（ ）。

2

A. O(n) B. O(nlog2n) C. O(n) D. O(1)

23

13. 某算法仅含程序段1和程序段2，程序段1的执行次数3n，程序段2的执行次数为0.01n，则该算法的时间复杂度为（ ）。

23

A. O(n) B. O(n) C. O(n) D. O(1)

14. 以下说法错误的是（ ）。 A. 抽象数据类型具有封装性。 B. 抽象数据类型具有信息隐蔽性。

C. 使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。 D. 抽象数据类型的一个特点是使用与实现分离。

15. 在二维数组中，每个数组元素同时处于（ ）个向量中。 A. 0个 B. 1个 C. 2个 D. n个

16. 多维数组实际上是由嵌套的（ ）实现的。

A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量

17. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为（ ）。

A. n B. n/2 C.(n+1)/2 D.(n-1)/2

18. 在一个长度为n的顺序表中向第i个元素（0≤i≤n-1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。

A. n-i B. n-i+1 C. n-i-1 D. i

19. 在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需要从前向后依次前移（ ）个元素。

A. n-i B. n-i+1 C. n-i-1 D. i

2

20. 在一个长度为n的顺序表中删除一个值为x的元素时，需要比较元素和移动元素的总次数为（ ）。

A. (n+1)/2 B. n/2 C. n D. n+1

21. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ ）。

2

A. O(n) B. O(1) C. O(n) D. O(log2n)

22. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。

2

A. O(n) B. O(n/2) C. O(1) D. O(n)

23. 在一个长度为n的有序顺序表中搜索值为x元素的时间效率最高的算法的渐进时间复杂度为（ ）。 A. O(1) B. O(n) C. O(log2n) D. O(n)

24. 在二维数组A[8][10]中，每一个数组元素A[i][j] 占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（ ）。 A. 80 B. 100 C. 240 D. 270

25. 设有一个n?n的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ ）处。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2

26. 设有一个n?n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ ）处。

A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2

27. 设有两个串t和p，求p在t中首次出现的位置的运算叫做（ ）。 A. 求子串 B. 模式匹配 C. 串替换 D. 串连接

28. 不带头结点的单链表first为空的判定条件是（ ）。 A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL;

29. 带头结点的单链表first为空的判定条件是（ ）。 A. first==NULL; B. first->link==NULL; C. first->link==first; D. first!=NULL;

30. 设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行的操作是（ ）。

A. s->link=p->link; p->link=s; B. q->link=s; s->link=p;

3

C. p->link=s->link; s->link=p; D. p->link=s; s->link=q;

31. 设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是（ ）。

A.s->link=p; p->link=s; B. p->link=s; s->link=p;

C.s->link=p->link; p=s; D. s->link=p->link; p->link=s;

32. 设单链表中结点的结构为（data, link）。若想摘除p->link所指向的结点，则应执行的操作是（ ）。

A. p->link=p->link->link; B. p=p->link; p->link=p->link->link; C. p->link=p; D. p=p->link->link;

33. 非空的循环单链表first的尾结点（由p所指向）满足的条件是（ ）。 A. p->link==NULL; B. p==NULL; C. p->link==first; D. p==first;

34. 设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是（ ）。 A.s = rear; rear = rear->link; delete s; B.rear = rear->link; delete rear;

C.rear = rear->link->link; delete rear;

D.s = rear->link->link; rear->link->link = s->link; delete s;

35. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较的结点数是（ ）。

A. n B. n/2 C. (n-1)/2 D. (n+1)/2

36. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）。

2

A. O(1) B. O(n) C. O(n) D. O(nlog2n)

37. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ ）。 A. O(1) B. O(n)

2

C. O(n) D. O(nlog2n)

38.单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。 A. O(1) B. O(m) C. O(n) D. O(m+n)

39. 利用双向链表作线性表的存储结构的优点是（ ）。

A. 便于单向进行插入和删除的操作 B. 便于双向进行插入和删除的操作

4

C. 节省空间 D. 便于销毁结构释放空间

40. 带表头的双向循环链表的空表满足（ ）。

A. first＝NULL; B. first->rLink==first C. first->lLink==NULL D. first->rLink==NULL

41. 已知L是一个不带表头的单链表, 在表首插入结点*p的操作是（ ）。 A. p = L; p->link = L; B. p->link = L; p = L; C. p->link = L; L = p; D. L = p; p->link = L;

42. 已知L是带表头的单链表, 删除首元结点的语句是（ ）。

A. L = L->link; B. L->link = L->link->link; C. L = L; D. L->link = L;

43. 栈的插入和删除操作在( )进行。

A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置

44. 当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行( )语句修改top指针。

A. top++; B. top--; C. top = 0; D. top;

45. 若让元素1,2,3依次进栈，则出栈次序不可能出现( )种情况。 A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,2

46. 在一个顺序存储的循环队列中，队头指针指向队头元素的( )位置。 A. 前一个 B. 后一个 C. 当前 D. 后面

47. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为( )。 A. n-2 B. n-1 C. n D. n+1

48. 从一个顺序存储的循环队列中删除一个元素时，首先需要( )。 A. 队头指针加一 B. 队头指针减一

C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素

49. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。

A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear

50. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL

5

51. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行( )操作。

A. top->link=s; B. s->link=top->link; top->link=s; C. s->link=top; top=s; D. s->link=top; top=top->link;

52. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行( )操作。

A. x=top->data; top=top->link; B. top=top->link; x=top->data; C. x=top; top=top->link; D. x=top->data;

53. 设循环队列的结构是 typedef struct {

DataType data[MaxSize]; int front, rear; } Queue;

若有一个Queue类型的队列Q，试问判断队列满的条件应为( ) 。 A. Q.front==Q.rear; B. Q.front-Q.rear==MaxSize;

C. Q.front+Q.rear==MaxSize; D. Q.front==(Q.rear+1) % MaxSize;

54. 设循环队列的结构是

const int MaxSize = 100; typedef int DataType; typedef struct {

DataType data[MaxSize]; int front, rear; } Queue;

若有一个Queue类型的队列Q，则应用( )表达式计算队列元素的个数。 A. (Q.rear-Q.front+MaxSize) % MaxSize; B.Q.rear-Q.front+1; C. Q.rear-Q.front-1; D. Q.rear-Qfront;

55. 为增加内存空间的利用率和减少溢出的可能性, 由两个栈共享一块连续的内存空间时, 应将两栈的( )分别设在这块内存空间的两端。

A. 长度 B. 深度 C. 栈顶 D. 栈底

56. 递归是将一个较复杂的（规模较大的）问题转化为一个稍为简单的（规模较小的）与原问题（ ）的问题来解决，使之比原问题更靠近可直接求解的条件。 A. 相关 B. 子类型相关 C. 同类型 D. 不相关

57. 递归调用时系统需要利用一个（ ）来实现数据的传递和控制的转移。 A. 队列 B. 优先级队列 C. 双端队列 D. 栈

6

58. 在系统实现递归调用时需利用递归工作记录保存（ ），当递归调用程序执行结束时通过它将控制转到上层调用程序。

A. 调用地址 B. 递归入口 C. 返回地址 D. 递归出口

59. 在递归执行过程中，当前执行的递归函数过程的递归工作记录一定是递归工作栈中的栈顶记录，称之为（ ）记录。

A. 活动 B. 当前 C. 日志 D. 标记

60. 将递归求解过程改变为非递归求解过程的目的是（ ）。

A. 提高速度 B. 改善可读性 C. 增强健壮性 D. 提高可维护性

61. 如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后语句，则这种递归属于（ ），它很容易被改写为非递归过程。

A. 单向递归 B. 回溯递归 C. 间接递归 D. 尾递归

62. 设有一个递归算法如下

int fact ( int n ) { //n大于等于0 if ( n <= 0 ) return 1; else return n * fact (n-1); }

则计算fact (n) 需要函数调用的次数为（ ）次。 A．n B．n+1 C．n+2 D．n-1

63. 设有一个递归算法如下 int X ( int n ) {

if ( n <= 3 ) return 1;

else return X (n-2) + X (n-4) + 1; }

试问计算X (X (5) ) 时需要调用（ ）次X函数。

A．2次 B．3次 C．4次 D．5次

64. 设有一个广义表A (a)，其表尾为（ ）。 A．a B．( ( ) ) C．（） D．(a)

65. 设有一个广义表A ( (x, (a, b) ), (x, (a, b), y) )，运算Head (Head (Tail (A) ) ) 的执行结果为（ ）。

A．x B．(a, b) C．(x,(a,b)) D．y

66. 下列广义表中的线性表是（ ）。

A．E(a,(b,c)) B．E(a,E) C．E(a,b) D．E(a,L( ))

67. 对于一组广义表A( ), B(a,b), C(c,(e,f,g)), D(B,A,C), E (B, D)，其中的E是（ ）。

7

A. 线性表 B. 纯表 C. 递归表 D. 再入表

68. 已知广义表A ( (a, b, c), (d, e, f ) )，从A中取出原子e的运算是（ ）。 A．Tail (Head (A) ) B．Head (Tail (A) )

C．Head (Tail(Head(Tail(A)))) D．Head(Head(Tail(Tail (A))))

69. 树中所有结点的度之和等于所有结点数加( )。 A. 0 B. 1 C. –1 D. 2

70. 在一棵树中，( )没有前驱结点。

A. 树枝结点 B. 叶子结点 C. 树根结点 D. 空结点

71. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加( )。 A. 2 B. 1 C. 0 D. –1

72. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于( )。 A. n B. n-1 C. n+1 D. 2*n

73. 在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层，i大于等于0而小于等于树的高度)，最多具有( )个结点。

ii+1i-1n

A. 2 B. 2 C. 2 D. 2

74. 在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于( )。

h-1h+1hh

A. 2 B. 2 C. 2-1 D. 2

75. 一棵具有35个结点的完全二叉树的高度为( )。假定空树的高度为 -1。 A. 5 B. 6 C. 7 D. 8

76. 在一棵具有n个结点的完全二叉树中，树枝结点的最大编号为( )。假定树根结点的编号为0。

A. ?(n-1)/2? B. ?n/2? C. ?n/2? D. ?n/2?-1

77. 在一棵完全二叉树中，若编号为i的结点存在左子女，则左子女结点的编号为( )。假定树根结点的编号为0。

A 2i B 2i-1 C 2i+1 D 2i+2

78. 在一棵完全二叉树中，假定树根结点的编号为0，对于编号为i(i>0)的结点，其双亲结点的编号为( )。

A. ?(i+1)/2? B. ?(i-1)/2? C. ?i/2? D. ?i/2?-1

79. 在一棵树的左子女-右兄弟表示法中，一个结点的右子女是该结点的( )结点。

8

A. 兄弟 B. 父子 C. 祖先 D. 子孙

80. 在一棵树的静态双亲表示中，每个存储结点包含( )个域。 A 1 B 2 C 3 D 4

81. 已知一棵二叉树的广义表表示为a(b(c),d(e(,g(h)),f))，则该二叉树的高度为( )。假定树根结点的高度为0。

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

82. 已知一棵树的边集表示为{, , , , , , , }，则该树的深度为( )。假定树根结点的高度为0。 A. 2 B. 3 C. 4 D. 5

83. 利用n个值作为叶结点的权生成的霍夫曼树中共包含有( )个结点。 A. n B. n+1 C. 2*n D. 2*n-1

84. 利用3,6,8,12这四个值作为叶子结点的权，生成一棵霍夫曼树，该树的带权路径长度为( )。

A 55 B 29 C 58 D 38

85. 一棵树的广义表表示为a(b,c(e,f(g)),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为( )。

A 1 B 2 C 3 D 4

86. 向具有n个结点的堆中插入一个新元素的时间复杂度为( )。 A. O(1) B. O(n) C. O(log2n) D. O(nlog2n)

87. 若搜索每个元素的概率相等，则在长度为n的顺序表上搜索任一元素的平均搜索长度为( )。

A. n B. n+1 C. (n-1)/2 D. (n+1)/2

88. 对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索任一元素的平均搜索长度为( )。 A. 5.5 B. 5 C. 39/8 D. 19/4

89. 对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索第三个元素的概率为1/6，则搜索任一元素的平均搜索长度为( )。 A. 5/3 B. 2 C. 7/3 D. 4/3

90. 对长度为n的单链有序表，若搜索每个元素的概率相等，则搜索任一元素的搜索成功的平均搜索长度为( )。

A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4

9

91. 对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值向上取整。

A. log2(n+1) B. log2n C. n/2 D. (n+1)/2

92. 对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值的向下取整加1。

A. log2(n+1) B. log2n C. n/2 D. (n+1)/2

93. 对于长度为9的顺序存储的有序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( )除以9。

A. 20 B. 18 C. 25 D. 22

94. 对于长度为18的顺序存储的有序表，若采用折半搜索，则搜索第15个元素的搜索长度为( )。

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

95. 对具有n个元素的有序表进行折半搜索，则搜索任一元素的时间复杂度为( )。

2

A. O(n) B. O(n) C. O(1) D. O(log2n)

96. 在一棵高度为h的具有n个元素的二叉搜索树中，搜索一个元素的最大搜索长度为( )。

A. n B. log2n C. (h+1)/2 D. h+1

97. 从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为( )。

2

A. O(n) B. O(1) C. O(log2n) D. O(n)

98. 向具有n个结点的二叉搜索树中插入一个元素的时间复杂度大致为( )。 A. O(1) B. O(log2n ) C. O(n) D. O(nlog2n)

99. 在一棵AVL树中，每个结点的平衡因子的取值范围是( )。 A. -1?1 B. -2?2 C. 1?2 D. 0?1

100. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为( )种旋转类型。

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

101. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的左单或右单旋转的调整过程，此时需要修改相关( )个指针域的值。

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

10

102. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关( )个指针域的值。

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

103. 设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1?V2，E1?E2，则称 ( )。 A．G1是G2的子图 B．G2是G1的子图 C．G1是G2的连通分量 D．G2是G1的连通分量

104. 有向图的一个顶点的度数等于该顶点的 ( )。 A．入度 B．出度 C．入度与出度之和 D．（入度+出度）／２

105. 一个连通图的生成树是包含图中所有顶点的一个 ( )。

A．极小子图 B．连通子图 C．极小连通子图 D．无环子图

106. n个顶点的连通图中至少含有 ( )。

A．n-1条边 B．n条边 C．n(n-1)/2条边 D．n(n-1)条边

107. n个顶点的强连通图中至少含有 ( )。

A．n-1条有向边 B．n条有向边 C．n(n-1)/2条有向边 D．n(n-1)条有向边

108. 在一个带权连通图G中，权值最小的边一定包含在G的( ) 中。 A．最小生成树 B．生成树 C．广度优先生成树 D．深度优先生成树

109. 对于具有e条边的无向图，它的邻接表中有 ( ) 个边结点。 A．e-1 B．e C．2(e-1) D．2e

110. 具有n个顶点的有向无环图最多可包含 ( ) 条有向边。 A．n-1 B．n C．n(n-1)/2 D．n(n-1)

111. 一个有n个顶点和n条边的无向图一定是 ( )。

A．连通的 B．不连通的 C．无环的 D．有环的

112. 在n个顶点的有向无环图的邻接矩阵中至少有 ( ) 个零元素。 A．n B．n(n-1)/2 C．n(n+1)/2 D．n(n-1)

113. 对于有向图，其邻接矩阵表示比邻接表表示更易于 ( )。 A．查找一条边 B．求一个顶点的邻接点 C．进行图的深度优先遍历 D．进行图的广度优先遍历

114. 在一个有向图的邻接矩阵表示中，删除一条边需要耗费的时间是 ( )。 A．O(1) B．O(i) C．O(j) D．O(i+j)

11

115. 与邻接矩阵相比，邻接表更适合于存储 ( )。 A．无向图 B．连通图 C．稀疏图 D．稠密图

116. 设一个有n个顶点和e条边的有向图采用邻矩阵表示，要计算某个顶点的出度 所耗费的时间是 ( )。

2

A．O(n) B．O(e) C．O(n+e) D．O(n)

117. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是 ( )。 A．栈 B．队列 C．二叉树 D．树

118. 设无向图的顶点个数为n，则该图最多有（ ）条边。

A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)

119. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。

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

120. 若采用邻接矩阵存储具有n个顶点的无向图，则该邻接矩阵是一个 ( )。

A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵

121. 图的深度优先搜索类似于树的（ ）次序遍历。

A. 先根 B. 中根 C. 后根 D. 层次

122. 图的广度优先搜索类似于树的（ ）次序遍历。

A. 先根 B. 中根 C. 后根 D. 层次

123. 在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（ ）辅助结构，判断一条边的两个端点是否在同一个连通分量上。

A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合

124. 采用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（ ）数。

A. 非零 B. 非整 C. 非负 D. 非正

125. 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。

e2

A. O(nlog2e) B. O(n+e) C. O(n) D. O(n)

126. 若待排序对象序列在排序前已基本按排序码递增顺序排列，则采用( )方法比较次数最少。

A. 直接插入排序 B. 快速排序 C. 归并排序 D. 直接选择排序

12

127. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。

A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序

128. 对5个不同的数据元素进行直接插入排序，最多需要进行( )次比较。 A. 8 B. 10 C. 15 D. 25

129. 下列排序算法中，( )算法是不稳定的。

A. 起泡排序 B. 直接插入排序 C. 基数排序 D. 快速排序

130. 假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，则应取的归并路数至少是( )。

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

131. 在基于排序码比较的排序算法中，( )算法在最坏情况下的时间复杂度不高于O(nlog2n)。

A. 起泡排序 B. 希尔排序 C. 堆排序 D. 快速排序

132. 在下列排序算法中，( )算法使用的附加空间与输入序列的长度及初始排列无关。 A. 锦标赛排序 B. 快速排序 C. 基数排序 D. 归并排序

133. 一个对象序列的排序码为{46, 79, 56, 38, 40, 84}，采用快速排序（以位于最左位置的对象为基准）所得到的第一次划分结果为( )。

A. {38, 46, 79, 56, 40, 84} B. {38, 79, 56, 46, 40, 84} C. {40, 38, 46, 79, 56, 84} D. {38, 46, 56, 79, 40, 84}

134. 如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中( )算法最快。

A. 归并排序 B. 希尔排序 C. 快速排序 D. 基数排序

135. 设有一个含有200个元素的表待散列存储，用线性探查法解决冲突，按关键码查询时找到一个元素的平均探查次数不能超过1.5，则散列表的长度应至少为（ ）。 （注：平均探查次数的计算公式为Snl={1+1/(1-α)}/2, 其中α为装填因子） A. 400 B. 526 C. 624 D. 676

136. 5阶B树中, 每个结点最多允许有（ ）个关键码。

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

137. 在10阶B树中根结点所包含的关键码个数最少为（ ）。

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

138. 在一棵高度为h的B树中，叶结点处于第（ ）层。（注：树根结点为第0层，B树高

13

度为失败结点所处层数）。

A. h-1 B. h C. h+1 D. h+2

139. 在一棵高度为h的B树中，插入一个新关键码时，为搜索插入位置需读取（ ）个结点。

A. h-1 B. h C. h+1 D. h+2

140. 当对一个线性表R[60] 进行索引顺序搜索（分块搜索）时，若共分成了10个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序搜索，则搜索每一个表项的平均搜索长度为（ ）。

A. 7 B. 8 C. 9 D. 10

141. 当对一个线性表R[60] 进行索引顺序搜索（分块搜索）时，若共分成了8个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序搜索，则搜索每一个表项的平均搜索长度为（ ）。

A. 7 B. 8 C. 9 D. 10

142. 既希望较快的搜索又便于线性表动态变化的搜索方法是（ ）。

A. 顺序搜索 B. 折半搜索 C. 散列搜索 D. 索引顺序搜索

143. 散列函数应该有这样的性质，即函数值应当以（ ）概率取其值域范围内的每一个值。 A. 最大 B. 最小 C. 平均 D. 同等

144. 设散列地址空间为0?m-1，k为表项的关键码，散列函数采用除留余数法，即Hash(k)=k%p。为了减少发生冲突的频率，一般取p为（ ）。

A. m B. 小于m的最大质数 C. 大于m的最小质数 D. 小于m的最大合数

145. 在采用开散列法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的（ ）值相同。

A. 关键码 B. 非关键码 C. 散列函数 D. 某个域

146. 解决散列法中出现的冲突问题常采用的方法是（ ）。 A. 数字分析法、除留余数法、平方取中法 B. 数字分析法、除留余数法、线性探查法 C. 数字分析法、线性探查法、双散列法 D. 线性探查法、双散列法、开散列法

147. 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（ ）引起的。 A. 同义词之间发生冲突 B. 非同义词之间发生冲突 C. 同义词之间或非同义词之间发生冲突 D. 散列表“溢出”

14

148. 采用线性探查法解决冲突时所产生的一系列后继散列地址（ ）。 A. 必须大于原散列地址 B. 必须小于原散列地址

C. 可以大于或小于原散列地址 D. 不能超过散列表长度的一半

149. 对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度（ ）。 A. 为O(log2n) B. 为O(n) C. 与n/m值有关 D. 与n/m值无关

单选题参考解答

1. A 2. B 3. C 4. D 5. B 6. B 7. B 8. A 9. D 10. D 11. A 12. C 13. C 14. C 15. C 16. A 17. C 18. A 19. C 20. C 21. B 22. A 23. C 24. C 25. A 26. C 27. B 28. A 29. B 30. B 31. D 32. A 33. C 34. D 35. D 36. B 37. C 38. C 39. B 40. B 41. C 42. B 43. A 44. B 45. C 46. A 47. B 48. A 49. D 50. D 51. C 52. A 53. D 54. A 55. D 56. C 57. D 58. C 59. A 60. A 61. D 62. B 63. C 64. C 65. A 66. C 67. D 68. C 69. C 70. C 71. A 72. C 73. A 74. D 75. A 76. D 77. C 78. B 79. A 80. B 81. B 82. B 83. D 84. A 85. C 86. C 87. D 88. C 89. A 90. B 91. A 92. B 93. C 94. B 95. D 96. D 97. C 98. B 99. A 100. C 101. B 102. D 103. A 104. C 105. C 106. A 107. B 108. A 109. D 110. C 111. D 112. C 113. A 114. A 115. C 116. A 117. B 118. B 119. B 120. D 121. A 122. D 123. C 124. C 125. B 126. A 127. C 128. B 129. D 130. C 131. C 132. C 133. C 134. D 135. A 136. C 137. B 138. A 139. B 140.C 141. B 142. D 143. D 144. B 145. C 146. D 147. C 148. C 149. C

数据结构（本科）期末综合练习二（填空与判断题）

填空题

1. 数据是________的载体，它能够被计算机程序识别、存储和加工处理。

2. 数据结构包括逻辑结构、________和数据的运算三个方面。

3. 数据结构的逻辑结构包括线性结构和________结构两大类。

4. 数据结构的存储结构包括顺序、________、索引和散列等四种。

5. 基本数据类型是计算机已经实现了的________。

6. 抽象数据类型的特点是________、信息隐蔽、使用与实现分离。

15

7. 算法的一个特性是________，即算法必须执行有限步就结束。

8. 面向对象的特征应包括对象、类、________、消息通信。

9. 属性与服务相同的对象构成类，类中的每个对象称为该类的________。

10. 对象的私有状态只能通过该对象的________才能改变。

11. 模板类是一种数据抽象，它把________当作参数，可以实现类的复用。

12. 在类的继承结构中，位于上层的类叫做基类，其下层的类则叫做________类。

13. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的_________存取的。

14. 在程序运行过程中不能扩充的数组是__________分配的数组。这种数组在声明它时必须指定它的大小。

15. 在程序运行过程中可以扩充的数组是__________分配的数组。这种数组在声明它时需要使用数组指针。

16. 二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或直接后继）。

17. 若设一个n?n的矩阵A的开始存储地址LOC(0, 0) 及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素a[i][j]的存储地址为_________。

18. 对称矩阵的行数与列数_________且以主对角线为对称轴，aij = aji，因此只存储它的上三角部分或下三角部分即可。

19. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储_________个矩阵元素。

20. 将一个n阶对称矩阵A的上三角部分按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中，则A[I][J]在I≤J时将存放于数组B的_________位置。

21. 利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和_________。

22. 线性表是由n（n≥0）个_________组成的有限序列。

16

23. 若设串S = “documentHash.doc\\0”，则该字符串S的长度为_________。

24. 链表是一种采用 存储结构存储的线性表。

25. 链表只适用于 查找。

26. 在链表中进行插入和 操作的效率比在顺序存储结构中进行相同操作的效率高。

27. 链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的__________的值。

28. 链接存储表示的结点存储空间一般在程序的运行过程中进行动态地_______和释放。

29. 单链表中逻辑上相邻的结点而在物理位置上_______相邻。

30. 在单链表中, 除了表头结点外, 任意结点的存储位置由其直接_____结点的指针域的值所指示。

31. 在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对________进行特殊处理。

32. 若设L是指向带表头的单链表, 语句 L->link=L->link->link的作用是________单链表中的第一个结点。

33. 在双向链表中, 每个结点除了数据域外, 还有两个指针域, 它们分别指向_________________。

34. 线性表的链接存储只能通过________顺序访问。

35. 链表与顺序表、索引表、散列表等都是数据逻辑结构的__________表示。

36. 设双向循环链表每个结点结构为(data,llink,rlink),则结点*p的前驱结点的地址为__________。

37. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为___________表。

38. 队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为________表。

39. 向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给________。

40. 队列的删除操作在________进行。

41. 向一个顺序栈插入一个元素时，首先使________后移一个位置，然后把待插入元素写入到这个

17

位置上。

42. 若设顺序栈的最大容量为MaxSize，top==-1表示栈空，则判断栈满的条件是________________。

43. 当用长度为MaxSize的数组顺序存储一个栈时，若用top == MaxSize表示栈空，则表示栈满的条件为________。

44. 向一个循环队列中插入元素时，需要首先移动________指针，然后再向所指位置写入新元素。

45. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行________和top=p操作。

46. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有________个结点。

47. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有________个结点。

48. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_________的对象。

49. 如果一个过程直接或间接地调用自己，则称这个过程是一个________的过程。

50. 递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和_________。

51. 函数内部的局部变量是在进入函数过程后才分配存储空间，在函数过程执行结束后就________局部变量所占用的存储空间。

52. 迷宫问题是一个回溯控制的问题，最好使用__________的方法来解决。

53. 非空广义表的除第一个元素外其他元素组成的表称为广义表的________。

54. 广义表A ( (a, b, c), (d, e, f ) ) 的表尾为________。

55. 广义表是一种递归的数据结构，子表结点则指示下一层广义表的________。

56. 广义表的深度定义为广义表括号的________。

57. 对于一棵具有n个结点的树，该树中所有结点的度数之和为______。

58. 一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点k的所有祖先的结点数为________个。

59. 一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为_________。假定树根结点的层数为0。

18

60. 假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为________。假定树根结点的深度为0。

61. 在一棵高度为3的四叉树中，最多含有________个结点，假定树根结点的高度为0。

62. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有________个。

63. 一棵高度为5的完全二叉树中，最多包含有________个结点。假定树根结点的高度为0。

64. 假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则该树的高度为________。假定树根结点的高度为0。

65. 在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为________个。

66. 假定一棵二叉树的结点数为18，则它的最小高度为________。假定树根结点的高度为0。

67. 在一棵高度为h的理想平衡二叉树中，最少含有________个结点。假定树根结点的高度为0。

68. 在一棵高度为h的理想平衡二叉树中，最多含有________个结点。假定树根结点的高度为0。

69. 若将一棵树A(B(C,D,E),F(G(H),I))按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点的个数为________个。

70. 将一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有________子女。

71. 在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的左子女元素的下标为______。

72. 在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的右子女元素的下标为________。

73. 在一个最小堆中，堆顶结点的值是所有结点中的________。

74. 在一个最大堆中，堆顶结点的值是所有结点中的________。

75. 以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素的渐进时间复杂度为

19

________。

76. 对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为pi,搜索长度（即在搜索过程中依次同有关元素比较的总次数）为ci，则在搜索成功情况下的平均搜索长度的计算公式为________。

77. 假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为________。

78. 从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为________。

79. 假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为______个。

80. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向________继续搜索。

81. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的________上。

82. 根据n个元素建立一棵二叉搜索树的渐进时间复杂度大致为_____________。

83. 在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。

84. 根据一组记录(56,42,50,64,48)依次插入结点生成一棵AVL树时，当插入到值为_______的结点时需要进行旋转调整。

85. 根据一组记录(56,74,63,64,48)依次插入结点生成一棵AVL树时，当插入到值为63的结点时需要进行________________调整。

86. 根据一组记录(56,42,38,64,48)依次插入结点生成一棵AVL树时，当插入到值为38的结点时需要进行____________调整。

87. 根据一组记录(56,42,73,50,64,48,22)依次插入结点生成一棵AVL树时，当插入到值为_______的结点时才出现不平衡，需要进行旋转调整。

88. 在一棵具有n个结点的AVL树上进行插入或删除元素的渐进时间复杂度大致为_________。

?010?若3个顶点的图G的邻接矩阵为?100?，则图G一定是________向图。有

????010?? 20

89. n (n﹥0) 个顶点的连通无向图各顶点的度之和最少为________。

90. 用邻接矩阵存储图，占用的存储空间与图中的________数有关。

91. 设图G = (V, E)，V = {V0, V1, V2, V3}, E = {(V0, V1), (V0, V2), (V0, V3), (V1, V3)}，则从顶点V0开始的图G的不同深度优先序列有________种。

92. 设图G = (V, E)，V = {1, 2, 3, 4}, E = {<1, 2>, <1, 3>, <2, 4>, <3, 4>}，从顶点1出发，对图G进行广度优先搜索的序列有________种。

93. n (n﹥0) 个顶点的无向图中顶点的度的最大值为________。

94. 在重连通图中每个顶点的度至少为________。

95. n个顶点的连通无向图的生成树含有________条边。

96. 11个顶点的连通网络N有10条边，其中权值为1, 2, 3, 4, 5的边各2条，则网络N的最小生成树各边的权值之和为_________。

97. 在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个________上，才会被加入到生成树中。

98. 一般来说,深度优先生成树的高度比广度优先生成树的高度要________。

99. 求解带权连通图最小生成树的Prim算法使用图的________作为存储结构。

100. 设图的顶点数为n，则求解最短路径的Dijkstra算法的时间复杂度为________。

101. 第i (i = 1, 2, …, n-1) 趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做__________排序。

102. 第i (i=0,1,...,n-2) 趟从参加排序的序列中第i个至第n-1个元素中挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做_________排序。

103. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做__________排序。

104. 每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做_________排序。

105. 在直接选择排序中，记录比较次数的时间复杂度为________。

21

106. 在直接选择排序中，记录移动次数的时间复杂度为__________。

107. 在堆排序中，对n个记录建立初始堆需要调用__________次调整算法。

108. 在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用_________次调整算法。

109. 在堆排序中，对任意一个分支结点进行调整运算的时间复杂度为____________。

110. 对n个数据对象进行堆排序，总的时间复杂度为______________。

111. 给定一组数据对象的关键码为{46,79,56,38,40,84}，则利用堆排序方法建立的初始堆（最大堆）为_______________。

112. 快速排序在平均情况下的时间复杂度为___________。

113. 快速排序在最坏情况下的时间复杂度为____________。

114. 快速排序在平均情况下的空间复杂度为____________。

115. 快速排序在最坏情况下的空间复杂度为____________。

116. 给定一组数据对象的关键码为{46，79，56，38，40，84}，对其进行一趟快速排序处理，得到的右子表中有________个对象。

117. 在对n个数据对象的二路归并排序中，每趟归并的时间复杂度为____________。

118. 在对n个数据对象进行的二路归并排序中，整个归并过程的时间复杂度为___________。

119. 在索引表中，每个索引项至少包含有__________域和地址域这两项。

120. 假定一个线性表为 {12, 23, 74, 55, 63, 40, 82, 36}，若按key%3条件进行划分，使得同一余数的元素成为一个子表，则包含74的子表长度为________。

121.假定一个线性表为 (”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的以a为第一个字母的子表长度为________。

122. 在索引表中，若一个索引项对应数据对象表中的一个表项，则称此索引为稠密索引，若对应数据对象表中的若干表项，则称此索引为________索引。

123. 假定对长度n = 100的线性表进行索引顺序搜索，并假定每个子表的长度均为n，则进

22

行索引顺序搜索的时间复杂度为________。

124. 假定对长度n=100的线性表进行索引顺序搜索，并假定每个子表的长度均为n，则进行索引顺序搜索的平均搜索长度为________。

125. 若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为________。

126. 若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则二级索引表的长度为________。

127. 假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m = 20的散列表，每个散列地址的同义词子表（单链表）的长度平均为________。

128. 在线性表的散列存储中，装载因子 ? 又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则 ? 等于________。

129. 对于包含n个关键码的m阶B树，其最小高度为____________。

130. 已知一棵3阶B树中含有50个关键码，则该树的最小高度为________。

131. 已知一棵3阶B树中含有50个关键码，则该树的最大高度为________。

132. 在一棵m阶B树上，每个非根结点的关键码数最少为__________个。

133. 在一棵m阶B树上，每个非根结点的子树最少为________棵。

134. 在一棵m阶B树上，每个非根结点的关键码数最多为________个。

135. 在对m阶B树插入元素的过程中，每向一个结点插入一个关键码后，若该结点的关键码个数等于________个，则必须把它分裂为2个结点。

136. 在从m阶B树删除关键码的过程中，当从一个结点中删除掉一个关键码后，所含关键码个数等于?m/2?-2个，并且它的左、右兄弟结点中的关键码个数均等于________，则必须进行结点合并。

23

判断题

1. 数据元素是数据的最小单位。

2. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。

3. 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。

4. 数据的逻辑结构与数据元素本身的内容和形式无关。

5. 算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。

6. 只有用面向对象的计算机语言才能描述数据结构算法。

7. 如果采用如下方式定义一维字符数组： const int maxSize = 30; char a[maxSize];

则这种数组在程序执行过程中不能扩充。

8. 如果采用如下方法定义一维字符数组： int maxSize = 30;

char * a = new char[maxSize];

则这种数组在程序执行过程中不能扩充。

9. 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。

10. 多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

11. 在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。

12. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。

13. 插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。

14. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

15. 用字符数组存储长度为n的字符串，数组长度至少为n+1。

16. 线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。

17. 线性表若采用链式存储表示, 在删除时不需要移动元素。

24

18. 在线性链表中删除中间的结点时，只需将被删结点释放。

19. 在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。

20. 每次从队列中取出的是具有最高优先权的元素, 这种队列就是优先级队列。

21. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。

22. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。

23. 栈和队列都是顺序存取的线性表, 但它们对存取位置的限制不同。

24. 在使用后缀表示实现计算器类时用到一个栈的实例, 它的作用是暂存运算器对象。

25. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

26. 若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。

27. 在用单链表表示的链式队列Q中，队头指针为Q->front，队尾指针为Q->rear，则队空条件为Q->front == Q->rear。

28. 递归定义的数据结构通常用递归算法来实现对它的操作。

29. 递归的算法简单、易懂、容易编写，而且执行效率也高。

30. 递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。

31. 递归方法和递推方法本质上是一回事，例如求n! 时既可用递推的方法，也可用递归的方法。

32. 用非递归方法实现递归算法时一定要使用递归工作栈。

33. 将f = 1 + 1/2 + 1/3+ ? + 1/n转化为递归函数时，递归部分为f (n) = f (n-1) + 1/n，递归结束条件为f (1) = 1。

34. 一个广义表的表头总是一个广义表。

35. 一个广义表的表尾总是一个表。

36. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的长度为3，深度为4。

25

37. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是 ( (b), c), ( ( (d) ) )。

38. 当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。

39. 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

40. 二叉树是一棵无序树。

41. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。

b42. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。

43. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。

44. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的结果。

45. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。

46. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。

47. 对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。

48. 对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。

49. 在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。

50. 线索二叉树中的每个结点通常包含有5个数据成员。

51. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。

52. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。

26

53. 进行折半搜索的表必须是顺序存储的有序表。

54. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。

55. 假定有两个用单链有序表表示的集合，则这两个集合的交运算可得到一个新的集合单链表，其长度小于等于参加运算的任意一个集合单链表的长度。

56. 假定有两个用单链有序表表示的集合，则这两个集合的差运算可得到一个新的集合单链表，其长度小于参加运算的任意一个集合单链表的长度。

57. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。

58. 对于同一组关键码互不相同的记录，若生成二叉搜索树时插入记录的次序不同则得到不同形态的二叉搜索树。

59. 对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。

60. 对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。

61. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优二叉搜索树。

62. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。

63.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。

64. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

65. 邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。

66. 存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。

67. 强连通分量是有向图中的极大强连通子图。

68. 对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。

69. 有回路的有向图不能完成拓扑排序。

27

70. 在AOE网络中一定只有一条关键路径。

71. 用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。

72. 对于AOE网络，加速任一关键活动就能使整个工程提前完成。

73. 对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。

74. 在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。

75. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。

76. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。

77. 如果无向图中每个顶点的度都大于等于2，则该图中必有回路。

78. 如果有向图中各个顶点的度都大于2，则该图中必有回路。

79. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。

80. 图的广度优先搜索算法通常采用非递归算法求解。

81. 对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。

82. 直接选择排序是一种稳定的排序方法。

83. 若将一批杂乱无章的数据按堆结构组织起来, 则堆中数据必然按从小到大的顺序线性排列。

84. 当输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。

85. 在任何情况下，快速排序需要进行关键码比较的次数都是O(nlog2n)。

86. 若用m 个初始归并段参加 k 路平衡归并排序，则归并趟数应为?log2m?。

87. 堆排序是一种稳定的排序算法。

88. 任何基于排序码比较的算法，对n个数据对象进行排序时，最坏情况下的时间复杂度都不会大于O(nlog2n)。

28

89. 装载因子是散列表的一个重要参数，它反映了散列表的装满程度。

90. 在用散列表存储关键码集合时，可以用双散列法寻找下一个空位置。在设计再散列函数时，要求计算出的值与表的大小m 互质。

91. 一棵3 阶B树是平衡的3 路搜索树，反之，一棵平衡的3 路搜索树是3 阶B树。

92. 闭散列法通常比开散列法时间效率更高。

93. 一棵 m 阶 B 树中每个结点最多有 m-1 个关键码，最少有 ?m/2?-1个关键码。

94. 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。

95. 在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采用折半搜索。

96. 在散列法中采取开散列（链地址）法来解决冲突时, 其装载因子的取值一定在(0,1)之间。

97. AVL树（平衡二叉搜索树）的所有叶结点不一定在同一层次上，同样，平衡m路搜索树的叶结点也不一定在同一层次上。

98. 在一棵B树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加1。

99. 向一棵B树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。

100. 从一棵B树删除关键码的过程中，若最终引起树根结点的合并，则新树比原树的高度增加1。

填空题参考解答

1. 信息 2. 存储结构 3. 非线性 4. 链接 5. 数据结构 6. 数据封装 7. 有穷性 8. 继承

9. 实例 10. 操作（或服务）11. 数据类型 12. 派生（或子） 13. 下标（或顺序号）14. 静态 15. 动态 16. 两个

17. LOC(0,0)+(i*n+j)*d 18. 相等19. n(n+1)/2 20. (2n-I-1)*I/2+J 21. 值 22. 数据元素 23. 16 24. 链式（或链接） 25. 顺序 26. 删除 27. 指针域 28. 分配 29. 不一定 30. 前驱 31. 表头指针 32. 删除

33. 前趋结点和后继结点34. 链接指针 35. 存储 36. p->llink

37. 后出先进 38. 先进先出 39. 栈顶指针 40. 队头（或队首）

29

41. 栈顶指针 42. top==MaxSize-1

43. top == 0 44. 队尾45. p->link=top 46. 1 47. 一 48. 递归 49. 递归 50.局部变量

51. 释放 52. 递归 53. 表尾 54. ( (d, e, f ) ) 55. 表头结点 56. 重数 57. n-1 58. 2 59. 3 60. 4

61. 85 62. 6 63. 63 64. 3

65. 6 66. 4 67. 2h 68. 2h+1

-1 69. 2 70. 右 71. 2i+1 72. 2i+2 n73. 最小值 74. 最大值 75. O(n) 76.

?pici

i?177. 20.5 78. 3 79. 19

80. 右子树 81. 左子树 82. O(nlog2n) 83. 1 84. 50 85. 先右后左双旋转86. 右单旋转 87. 64 88. O(log2n) 89. 2(n-1) 90. 顶点 91. 4 92. 2 93. n-1 94. 2 95. n-1 96. 30

97. 连通分量 98. 高 99. 邻接矩阵 100. O(n2

) 101. 直接插入 102. 直接选择 103. 交换 104. 二路归并

105. O(n2

)106. O(n) 107. n/2 108. n-1 109. O(log2n) 110. O(nlog2n)

111. 84，79，56，38，40，46 112. O(nlog2n)

113. O(n2

) 114. O(log2n) 115. O(n) 116. 3 117. O(n) 118. O(nlog2n) 119. 关键码

120. 2 121. 3 122. 稀疏 123. O(n)124. 11 125. 500 126. 25 127. 5 128. n/m 129. ?logm(n+1)? 130. 4 131. 5 132. ?m/2?-1 133. ?m/2? 134. m-1 135. m 136. ?m/2?-1

判断题参考解答

1. 错2. 对3. 错4. 对5. 错6. 错7. 对8. 错9. 错10. 对 11. 错12. 对13. 错14. 对15. 对16. 对17. 对18. 错19. 对

20. 对21. 对22. 错23. 对24. 对25. 对26. 错27. 错28. 对29. 错 30. 对31. 错32. 错33. 对34. 错35. 对36. 对37. 错38. 对39. 对 40. 错41. 错42. 对43. 错44. 对45. 对46. 对47. 错48. 错49. 错 50. 对51. 错52. 对53. 对54. 错55. 对56. 错57. 对58. 对59. 错 60. 对61. 对62. 错63. 对64. 错65. 对66. 对67. 对68. 错69. 对 70. 错71. 对72. 错73. 对74. 对75. 对76. 对77. 对78. 错79. 对 80. 对81. 错82. 错83. 错84. 对85. 错86. 错87. 错88. 错89. 对 90. 对91. 错92. 错93. 错94. 对95. 对96. 错97. 对98. 对99. 错 100. 错

30

31

本文来源：https://www.bwwdw.com/article/wn27.html