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. 已知一棵树的边集表示为{, ,
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