（1）插入10
10
(2) 插入6
10 (3) 插入3
10 (4)
6 调整 6 6 3 10 （5）插入2 2 3 6 （6）插入5
6 （7）插入4 （8）
5 3 6 4 10 6 10 2 5 2 5 3 10 3 10
调整 2 3、答：当关键字为3时，比较次数为4； 当关键字为8时，比较次数为1； 当关键字为19时，查找不成功；
4、答：（2）略
（3）深度优先遍历序列：ABCDE广度优先遍历序列：ABCED（4）关键路径A--B（长100）
作业题三参考答案： 一、单项选择题
1、D 2、B 3、A 4、C 5、D 6、A 7、B 8、C 9、B 10、D 二、填空题 1、2，3 2、4 3、n-1 4、e
5、相同类型数据，地址连续 6.三元组顺序表，三元组 7. 矩阵转置
三、应用题 1、 答： 2、答：
B
C
①
二叉链表
② ∧ ③ ∧ ④ ∧ ⑤ ∧ ⑥ ∧ ∧ ⑦ ⑧ ∧(2 ∧ ∧ ⑨ ∧ A
D
E
3. 答：Prim算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）
即：
4. 答：由完全二叉树的定义可知，除最后一层外，其他各层的结点是满的。设该完全二叉树有d层，则除最后一层外各层的结点个数分别为：1，2，4，8，16，32，…，即第i层的结点个数为2i-1。这里第8层有8个结点，显然第8/层是最后的一层，那么第7层的结点个数为27-1=64个，其中的4个结点有8个叶子结点，余下的为叶子结点，个数为64-4=60，所以该完全二叉树的叶子结点个数为60+8=68个。 5. 答：对应的二叉树形式如图所示：
作业题四参考答案： 一、单项选择题
1. A 2. B 3. D 4. B 5. D 6、C 7、C 8、C 9、B 10、D 二、填空题 1. 答：前一个位置
2. 答：数组元素，数组元素，维数 3. 答：邻阵矩阵，邻接表 4. 答：9，4
5. 答：[48 44] 52 [64 80 91] 6、1，2 三．判断 1. 答：√ 2. 答：× 3. 答：× 4. 答：√ 5. 答：√ 四、应用题
1. 答：模式p的next函数值如下：
2. 答：A共120个字节。
a4,5的起始地址为：1116。
按行优先存储时，a2,5的起始地址为：1068。 按列优先存储时，a2,5的起始地址为：1108。
3. 答：（1）哈希函数H（key）=（关键字各字符编码之和）MOD 7 （2）
4. 答：一趟快速排序：22,19,13,6,24,38,43,32
初始大堆：43,38,32,22,24,6,13,19
二路并归：第一趟：19,24,32,43,6,38,13,22 第二趟：19,24,32,43,6,13,22,38
第三趟：6,13,19,22,24,32,38,43
堆排序辅助空间最少，最坏情况下快速排序时间复杂度最差。
作业题五参考答案： 一、单项选择题
1. 答：C 2、D 3、D 4. 答：C 5. 答：B 6. 答：A 7. 答：D 8. 答：B 9. 答：C 10. 答：A 二、填空题 1、1，n-1 2、60 3、2 4、快速排序 5、简单选择排序
6．数据，指针，数据，指针 三 判断 1. 答：√ 2. 答：× 3. 答：× 4. 答：√ 5. 答：× 四、应用题
1. 答：该十字链表有一个十字链表表头结点，max(m,n)个行列表头结点。另外，每个非零元素对应一个结点，即k个元素结点，所以共有max(m,n)+k+1个结点。
2. 答：（1）最小生成树的定义略。（2）最小生成树有两棵。（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W）形式），其中W代表权值。V（G）={1，2，3，4，5} E1(G)={(4，5，2)，（2，5，4），（2，3，5），（1，2，7）}；E2(G)={(4，5，2），（2，4，4），（2，3，5），（1，2，7）} 3. 答：采用顺序查找法：文件中记录可以以任意持续存放。 采用折半查找法：文件中的记录必须按照关键字从小到大有序存放。
采用分块查找法：将文件分成若干个块，每一个快中的记录可以任意的存放，但块之间的必须按照关键字从小到大的次序存放，即前一块中的所有记录的关键字的值必须小于后一块的所有记录的关键字的字值。 4. 答：排序过程如下： (1)[]88,33,22,55,99,11,66 (2)[11],33,22,55,99,88,66 (3)[11,22],33,55,99,88,66 (4)[11,22,33],55,99,88,66 (5)[11,22,33,55],99,88,66
数据结构专升本模拟试题及参考答案
