一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一
项符合题目要求的。请在答题卡上将所选项的字母涂黑。)
1． 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是
x=2；
while（x<n/2）
x=2*x；
A．O(log
2
n) B．O(n) C．O(nlog
2
n) D．O(n
2
)
解答：A。程序中，执行频率最高的语句为“x=2*x”。设该语句执行了t次，则2
t+1
=n/2，
故t=log
2
(n/2)-1=log
2
n-2= O(log
2
n)。
2． 元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所
有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是
A．3 B．4 C．5 D．6
解答：B。出栈顺序必为d_c_b_a_，e的顺序不定，在任意一个“_”上都有可能。
3． 已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front和rear分别指向队头
元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则
初始时front和rear的值分别是
A．0,0 B．0，n-1 C．n-1,0 D．n-1，n-1
解答：B。插入元素时，front不变，rear+1.而插入第一个元素之后，队尾要指向尾元
素，显然，rear初始应该为n-1,front为0。
4． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是
A．257 B．258 C．384 D．385
解答：C。叶结点数为n，则度为2的结点数为n-1,度为1的结点数为0或1，本题中为1（总
结点数为偶数），故而即2n=768。
5． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的
中序遍历序列不会是
A．1,2,3,4 B．2,3,4,1 C．3,2,4,1 D．4,3,2,1
解答：C。由前序和后序遍历序列可知3为根结点，故（1,2）为左子树，（4）为右子树，
C不可能。或画图即可得出结果。
6． 已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结
点个数是
A．115 B．116 C．1895 D．1896
解答：D。本题可采用特殊情况法解。设题意中的树是如下图所示的结构，则对应的二
叉树中仅有前115个叶结点有右孩子。
7． 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是
A．95,22,91,24,94,71 B．92,20,91,34,88,35
C．21,89,77,29,36,38 D．12,25,71,68,33,34
评论0
最新资源