数据结构专升本模拟题及参考答案

第二趟：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 (6)[11,22,33,55,66],99,88 (7)[11,22,33,55,66,88],99 (8)[11,22,33,55,66,88,99]