C、486，314，123，145，508，298 D、298，123，508，486，145，314 34. 任何一个无向连通图的最小生成树( )。

A、一定有多棵 B、可能不存在 C、一棵或多棵 D、只有一棵 35. 无向图的邻接矩阵是一个( )

A、对角矩阵 B、上三角矩阵 C、对称矩阵 D、零矩阵

36. 设无向图G-=(V,E)和G’=(V’,E’),如G’为G的生成树，则下列说法中不正确的是( )。

A、G’为G的无环子图 B、G’为G 连通分量 C、G’为G极小连通子图且V’=V D、G’为G的子图 37. 以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ ）

A、 v1，v2，v3，v4，v5，v6，v7 B、 v1，v2，v5，v4，v3，v7，v6 C、 v1，v2，v3，v4，v7，v5，v6 D、 v1，v2，v5，v6，v7，v3，v4

38. 下面几个符号串编码集合中，不是前缀编码的是（ ）

A、{0,10,110,1111} B、{0,1,00,11}

C、{00,010,0110,1000} D、{b,c,aa,ac,aba,abb,abc} 39. 希尔排序的增量序列必须是（ ）。

A、 递增的 B、递减的 C、随机的 D、非递减的

40. 采用起泡排序法对n个关键字进行升序排序，若要使排序过程中比较关键字的次数最

多，则初始时的序列应满足条件（ ）

A、关键字完全无序 B、关键字基本有序 C、关键字从小到大排列 D、关键字从大到小排列 41. 在下列内部排序中( )是不稳定的。

A、希尔排序 B、起泡排序 C、直接插入排序 D、归并排序

42. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。

A、（100，80， 90， 60， 120，110，130） B、（100，120，110，130，80， 60， 90） C、（100，60， 80， 90， 120，110，130） D、(100，80， 60， 90， 120，130，110) 43. 在查找过程中，冲突指的是（ ）。

A、两个元素具有相同序号 B、两个元素的键值不同 C、不同键值对应相同的存储地址 D、两个元素的键值相同

5

44. 对有14个元素的有序表A[1..14]作二分查找，查找元素A[4]时的被比较元素依次为

（ ）。

A、A[1]，A[2]，A[3]，A[4] B、A[1]，A[14]，A[7]，A[4] C、A[7]，A[5]，A[3]，A[4] D、A[7]，A[3]，A[5]，A[4] 45. 以v1为起始结点对下图进行广度度优先遍历，正确的遍历序列是（ ）

A、 v1，v2，v3，v4，v5，v6，v7 B、v1，v2，v5，v6，v7，v3，v4 C、 v1，v2，v5，v6，v7，v3，v4 D、 v1，v4，v5，v7，v6，v2，v3

二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 1. 数据的物理结构包括 的存储和 的存储。

2. 若一个算法中的语句频度之和为T(n)=1921n+4nlogn,则算法的时间复杂度

为 。

3. 下面程序段的时间复杂度是 。

i=1；

while (i<=n) i=i*3；

4. 循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前

队列的元素个数是 。 5. 在单链表中设置头结点的作用是 ____。

6. 线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个

元素平均需要移动元素的个数是_ 。

7. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一

种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是 遍历方法。

8. 如果排序过程不改变 之间的相对次序，则称该排序方法是稳定的。

9. 从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需 一个位置。 10. 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的 。 11. 若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi

6

的 。

12. 一棵含999个结点的完全二叉树的深度为 。

13. 假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的

操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为 。 14. .如图所示的有向无环图可以排出 种不同的拓扑序列。

15. 从空树起，依次插入关键字1l，27，35，48，52，66和73构造所得的二叉排序树，在

等概率查找的假设下，查找成功时的平均查找长度为 。 16. 带头结点的双循环链表L中只有一个元素结点的条件是 。

17. 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中 的数目正相关。 18. 已知一棵完全二叉树中共有768结点，则该树中共有 个叶子结点。

19. 实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需要 存

放被访问的结点以实现遍历。

20. Prim（普里姆）算法适用于求 的网的最小生成树；kruskal（克鲁斯卡尔）算

法适用于求 的网的最小生成树。

21. 对长度为20的有序表进行二分查找的判定树的高度为 。

22. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为 ，有_ 个

叶子结点。

23. 高度为h的完全二叉树中最少有 个结点，最多有 个结点。 24. 设连通图G中有n个顶点e条边，则对应的最小生成树上有 条边。 25. 构造n个结点的强连通图，至少有 条弧。

26. 表达式求值是 应用的一个典型例子。

27. 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出

栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是 。

28. 快速排序算法在最差的情况下其时间复杂度是 。

7

29. 对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果

是 。

三、应用题（本大题共5小题，每小题6分，共30分） 1. 2.

已知二叉树的先序遍历序列ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。 如图请给出邻接表、邻接矩阵及逆邻接表。

V1 V3

V2 V4

3.

由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。

4.

请画出下图所示的树所对应的二叉树，并写出对应二叉树的先序遍历和中序遍历。

1 2 3 4 6 8 5 7

5. 设散列表为HT[13], 散列函数为 H (key) = key 。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。

6. 已知带权图G如图所示，画出图G的一棵最小生成树。

8