一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一项符合题目要求的。请在答题卡上将所选项的字母涂黑。)
1. 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是x=2while(xx=2x
A.O(log2n)
B.O(n)
C.O(nlog2n)
D.O(n2)
解答：A。程序中，执行频率最高的语句为“x=2x”。设该语句执行了t次，则2t+1=n/2，故t=log2(n/2)-1=log2n-2= O(log2n)。
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个叶结点有右孩子。
&bdquo&bdquo
共116个叶结点
7. 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是
A.95,22,91,24,94,71
C.21,89,77,29,36,38
B.92,20,91,34,88,35
D.12,25,71,68,33,34
解答：A。选项A中，当查到91后再向24查找，说明这一条路径之后查找的数都要比91小，后面的94就错了。
8. 下列关于图的叙述中，正确的是
Ⅰ. 回路是简单路径
Ⅱ.存储稀疏图，用邻接矩阵比邻接表更省空间
Ⅲ.若有向图中存在拓扑序列，则该图不存在回路
A.仅Ⅱ
B.仅Ⅰ、Ⅱ
C.仅Ⅲ
D.仅Ⅰ、Ⅲ
解答：C。Ⅰ.回路对应于路径，简单回路对应于简单路径Ⅱ.刚好相反Ⅲ.拓扑有序的必要条件。故选C。
9. 为提高散列(Hash)表的查找效率，可以采取的正确措施是
Ⅰ. 增大装填(载)因子
Ⅱ.设计冲突(碰撞)少的散列函数
Ⅲ.处理冲突(碰撞)时避免产生聚集(堆积)现象
A.仅Ⅰ
B.仅Ⅱ
C.仅Ⅰ、Ⅱ
D.仅Ⅱ、Ⅲ
解答：B。III错在“避免”二字。
10.为实现快速排序算法，待排序序列宜采用的存储方式是
A.顺序存储 B.散列存储 C.链式存储
解答：A。内部排序采用顺序存储结构。D.索引存储
11.已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是
A.1
B.2
C.4
D.5
解答：B。首先与10比较，交换位置，再与25比较，不交换位置。比较了二次。
12.下列选项中，描述浮点数操作速度指标的是
A.MIPS
B.CPI
C.IPC
D.MFLOPS
解答：D。送分题。
上海应用技术大学2025考研招生入学考试大纲：740设计基础
京公网安备 11010802020593号
电子营业执照