05哈工程数据结构真题

B．偶数 C．素数 D．合数

13．对动态查找有高效率的查找表组织结构是—— A．有序表 B．分块有序表 C．循环链表 D B-树

14．当初始数据有序时，不应采用—— A．堆排序 B．快速排序 C．基数排序 D．希尔排序

15．在n个元素中找出两个最小的元素，当n很大时，采用——方法比较次数较少。

A．树型选择排序 B．简单选择排序 C．归并排序 D．快速排序

四．综合题（每小题10分，共40分）

1．一棵二叉树的先序，中序，后序序列分别如下：（其中有部分结点未显示出来）

先序序列：_B_F_ICEH_G 中序序列：D_KFIA_EJC_

后序序列：_K_FBHJ_G_A

（1）。将先序，中序，后序序列完整写出来。 （2）。画出该二叉树。

2．对关键字序列{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec} (1).构造一棵平衡二叉（排序）树

（2）。求其查找成功的平均查找长度ASL。 3对无向加权图：

① 3 ⑤ 6 ⑥ 1 ⑨ 5 8 17 ③ 12 11 14 19 23 16 25 ② 4 ④ 8 ⑦ 2 ⑧ （1）用普里姆算法从顶点①出发求其最小生成树，并写出选点顺序。 （2）用克鲁斯卡尔算法求其最小生成树，并写出选边顺序 4． 给出的3阶B-树： 44

（1）。写出对给出的B-树依次插入关键字29，25，84，6后的B-树。 （2）。写出对给出的B-树依次删除关键字11，49，52，36后的B-树。 五．算法题（第1，2，3题各12分，第4题14分，共50分）

1．对用二叉链表表示的二叉树，设计一个算法，求其后序序列的第一个结

2 11 36 49 60 69 99 23 52 89 点。

2．完全二叉树顺序存储在数组A[1…n]中，请写一算法：求下标为i和j的

两个结点的所有公共祖先结点，并按下标从大到小的顺序将它们的值打印出来。

3．长度为n的字符串存储在结点大小为1的单链表中。试写一算法，判断

字符串是否中心对称（例如：‘abccba’是中心对称）。

4．已知一棵满二叉树顺序存储在数组B[1…n]中，设计一个算法，产生二叉

树的二叉链表。