1 设一个堆栈的入栈顺序是 1、2、3、4、5。若第一个出栈的元素是 4，则最后一个出栈
的元素是：
A. 1 或 5 B. 1 或者 3 C. 1 D. 5
2.将两个结点数都为 且都从小到大有序的单向链表合并成一个从小到大有序的单向链
表，那么可能的最少比较次数是：
A. 1 B. C. D. 3.在用数组表示的循环队列中 front 值一定小于等于 rear 值
A. 正确 B. 错误
4.由若干个二叉树组成的集合（称之为森林）F 中，叶结点总个数为 n，度为 2 的结点总个
数为 m，则该集合中二叉树的个数为：
A. m-n B. n-m-1 C. 无法确定 D. n-m
5.如果一二叉树的后序遍历结果是 FDEBGCA，中序遍历结果是 FDBEACG,那么该二叉树的
前序遍历结果是什么？
A. ABDFEGC B. ABDEFCG C. ABDFECG D. ABCDEFG
6.如果 A 和 B 都是二叉树的叶结点，问下面判断中哪个是对的？
A. 存在一种二叉树结构，其前序遍历结果是…A…B…，而中序遍历结果是…B…A… B. 存在一种二叉树结构，其中序遍历结果是…A…B…，而后序遍历结果是…B…A… C. 存在一种二叉树结构，其前序遍历结果是…A…B…，而后序遍历结果是…B…A… D. 其他三种判断都是错的
7.在一棵由 4、5、6 等若干整数结点构成的搜索树中，如果结点 4 和 6 在树的同一层，那
么可以断定结点 5 一定是 4 和 6 的父亲？
A. 正确 B. 错误
8.将 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7 逐个按顺序插入到初始为空的最小堆
中，然后连续执行两次删除最小元素操作（DeleteMin），此后堆顶的元素是什么？
A. 9 B. 7 C. 6 D. 5
9.散列表大小为 11, 散列函数为 H(K)=K mod 11。采用平方探测法处理冲突
,将关键字序列 6，25，39，61 依次插入到散列表中。那
么，元素 61 存放在散列表中的位置是：
A. 5 B. 6 C. 7 D. 8
10.采用平方探测冲突解决策略（ ，注意：不是 ），
将一批散列值均等于 2 的对象连续插入一个大小为 11 的散列表中，那么第四个对象一定位
于数组下标为 0 的位置。
A. 正确 B. 错误
11.令 P 代表入栈，O 代表出栈。当利用堆栈求解后缀表达式“1 2 3 + * 4 –”时，堆
栈操作序列是：
A. PPPOOPOOPPOO B. PPOOPPOOPPOO
C. PPPOOPOOPPOOPO D. PPPOOPOO
12.有一个四叉树，度 2 的结点数为 4, 度 3 的结点数为 2, 度 4 的结点数为 1.问该树的
叶结点个数是多少？
A. 8 B. 12 C. 18 D. 20
13.将下列数{88, 70, 61, 96, 120, 90}按顺序插入初始为空的 AVL 中，所形成的
AVL 树的前序遍历结果是：
A. 61,70,88,90,96,120
B. 90,70,61,88,96,120
C. 88,70,61,90,96,120
D. 88,70,61,96,90,120
14.下面说法中哪个是错误的
A. 任何最小堆的前序遍历结果也是有序的（从小到大）
B. 任何搜索树中同一层的结点从左到右是有序的（从小到大）
C. 任何最小堆中从根结点到任一叶结点路径上的所有结点也是有序的（从小到大）
D. 任何 AVL 树的中序遍历结果也是有序的（从小到大）
15.设一段文本中包含 4 个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本
的哈夫曼编码比采用等长方式的编码节省了多少位数？
A. 0 B. 2 C. 4 D. 5
16.将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个大小 TableSize
为 11 散列表中。散列函数 H 为： H(key) = key mod TableSize (求余)，采用线
性探测冲突解决策略。问：当第一次发现有冲突时，散列表的装填因子大约是多少？
A. 0.27 B. 0.64 C. 0.73 D. 0.45
17.在一个大小为 11 的空散列表中，散列函数为 H(key)=key MOD 11。按照线性探测
冲突解决策略连续插入散列值相同的 4 个元素。问：此时,该散列表的平均不成功查找次数
是多少？
A. 1 B. 21/11 C. 4/11 D. 不确定
18.算法分析的两个主要方面是时间复杂度和空间复杂度的分析。
A. 正确 B. 错误
19.若要求在找到从 S 到其他顶点最短路的同时，还给出不同的最短路的条数，我们可以将
Dijkstra 算法略作修改，增加一个 count[]数组：count[V]记录 S 到顶点 V 的最短路
径有多少条。则 count[V]应该被初始化为
A. 对所有顶点都有 count[V]=1
B. 对所有顶点都有 count[V]=0
C. count[S]=1; 对于其他顶点 V 则令 count[V]=0
D. count[S]=0; 对于其他顶点 V 则令 count[V]=1
20.在一个图中，若删除顶点 V 以及 V 相关的边后，图的一个连通分量分割为两个或两个
以上的连通分量，则称顶点 V 为该图的一个关节点。则下图的关节点有：（多选）
A. E, F, C B. C, E, F C. C, H, K
D. F, C, E E. F, B F. C. E
21.若要检查有向图中有无回路，除了可以利用拓扑排序算法外，下列哪种算法也可以用？
A. 广度优先搜索 B. Dijkstra 算法
C. 深度优先搜索 D. Prim 算法
22.{ 12, 9, 11, 8, 7, 4, 5, 13, 23 }是下列哪种方法第 2 趟排序后的结果？
A. 堆排序 B. 归并排序 C. 插入排序 D. 基数排序
23.给定初始待排序列{ 15，9，7，8，20，-1，4 }。如果希尔排序第 1 趟结束后得到
序列为{ 15，-1，4，8，20，9，7 }，则该趟增量为
A. 1 B. 2 C. 3 D. 4
24.下列代码的时间复杂度是：
for(i=0; i<n; i++)
for(j=i; j>0; j/=2)
printf(“%d\n”, j);
A. B. C. D. 25.斐波那契数列 的定义为：
, , , 。用递归函数计算 的空间
复杂度是 。
A. 正确 B. 错误
26.在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。
A. 正确 B. 错误
27.用邻接矩阵存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。
A. 正确 B. 错误
28.下图为一个 AOV 网，其可能的拓扑有序序列为：（多选）
A. ACBDEF B. ABCEFD C. ACBEDF
D. ABCDFE E. ABCEDF
29.如果无向图 G 必须进行三次广度优先搜索才能访问其所有顶点，则 G 一定有 3 个连通
分量。
A. 正确 B. 错误
30.给定有权无向图的邻接矩阵如下，其最小生成树的总权重是
A. 15 B. 13 C. 17 D. 10 E. 14
31.给定无向图 G，从 V0 出发进行深度优先遍历访问的边集合为：{(V0,V1), (V0,V4),
(V1,V2), (V1,V3), (V4,V5), (V5,V6)}。则下面哪条边不可能出现在 G 中？
A. (V0,V2) B. (V1,V5) C. (V0,V6) D. (V4,V6)
32.给定一有向图的邻接表如下。若从 v1 开始利用此邻接表做广度优先搜索得到的顶点序
列为：{v1, v3, v2, v4, v5}，则该邻接表中顺序填空的结果应为
A. v2, v3, v4 B. v3, v4, v2 C. v3, v2, v4 D. v4, v3, v2
33.对于给定的有权无向图 G，下列哪个说法是正确的？
A. G 的最小生成树中，任意一对顶点间的路径必是它们在 G 中的最短路径
B. 设顶点 V 到 W 的最短路径为 P。若我们将 G 中每条边的权重都加 1，则 P 一定仍然是 V
到 W 的最短路径
C. 单源最短路问题可以用 的时间解决
D. 其他几个说法全不对
34.我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两
城市间最经济的飞行路线问题？
A. Kruskal 算法
B. Dijkstra 算法
C. 深度优先搜索
D. 拓扑排序算法
35.下列排序算法中，哪种算法可能出现：在最后一趟开始之前，所有的元素都不在其最终
的位置上？(设待排元素个数 N>2)
A. 插入排序 B. 堆排序 C. 冒泡排序 D. 快速排序
36.对于归并排序，归并趟数的数量级是 。
A. 正确 B. 错误
37.有一组记录（46,77,55,38,41,85），用快速排序的方法，以第一个记录为基准得
到的一次划分结果为
A.（41,38,46,85,77,55） B.（46,41,38,55,77,85）
C.（41,38,85,55,77,46） D.（38,41,46,55,77,85）
38.仅基于比较的算法能得到的最好的时间复杂度是 。
A. 正确 B. 错误
39.在堆排序、快速排序、归并排序之间比较它们对额外空间的占用量，下面关系式中正确
的是
A. 堆排序 > 快速排序 > 归并排序 B. 堆排序 < 快速排序 < 归并排序
C. 堆排序 > 归并排序 > 快速排序 D. 堆排序 < 归并排序 < 快速排序
40.对给定序列{ 110, 119, 7, 911, 114, 120, 122 }采用次位优先的基数排序，
则 2 趟收集后的结果为
A. 7, 110, 119, 114, 911, 120, 122
B. 7, 110, 119, 114, 911, 122, 120
C. 7, 110, 911, 114, 119, 120, 122
D. 110, 120, 911, 122, 114, 7, 119
网友评论