当前位置：问答库＞考研试题

目录

2017年武汉工程大学数据结构(C语言版) 之数据结构(C语言版) 复试实战预测五套卷（一） ... 2 2017年武汉工程大学数据结构(C语言版) 之数据结构(C语言版) 复试实战预测五套卷（二） . 10 2017年武汉工程大学数据结构(C语言版) 之数据结构(C语言版) 复试实战预测五套卷（三） . 19 2017年武汉工程大学数据结构(C语言版) 之数据结构(C语言版) 复试实战预测五套卷（四） . 29 2017年武汉工程大学数据结构(C语言版) 之数据结构(C语言版) 复试实战预测五套卷（五） . 36

一、应用题

1． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？

【答案】（1）最高位优先（MSD ）法 先对最高位关键字进行排序，将序列分成若干子序列，

每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字

列。

（2）最低位优先

先对最低位关键字

位关键字

序列参加排序，

但对法 进行排序，然后对高一级关键字进行排序，依次重复，直至对最高进行排序，按值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。

2． 在一棵表示有序集S 的二叉搜索树（binary search tree ）中，任意一条从根到叶结点的路径将S 分为3部分：在该路径左边结点中的元素组成的集合S1:在该路径上的结点中的元素组成的集合S2:在该路径右边结点中的元素组成的集合S3; S=S1US2US3, 若对于任意的

是否总有a ≤b ≤c? 为什么？

【答案】该结论不成立。例如，本题中对于任一

f 的左子树上。对于从a 到根结点路径上的所有

均有a

3． 某文件系统空间的最大容量为4TB ，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在b 的右子树上，这时a>b，因此a

（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？

（2）假设索引表区采用如下结构：第0〜7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B ，块数占2B ; 剩余504字节采用直接索引结构，一个索引项占6B ，则可支持的单个文件最大长度是多少字节? 为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理 值并说明理由。

【答案】

（1）文件系统存储空间共有块数可存放

（2） 为表示个块号，索引表项占512B 个索引项，每个索引项对应一个磁盘块，故最大文件长度：块号占6字节，块数占2字节的情形下，最大文件长度

：

理由：合理的起始块号和块数所占字节数分别为

块数占4B 或以上，就可表示4TB 大小的文件长度，达到文件系统的空间上限。

4． 已知有6个顶点（顶点编号为0--5）的有向带权图G , 其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。

要求：

（1）写出图G 的邻接矩阵A 。

（2）画出有向带权图G 。

（3）求图G 的关键路径，并计算该关键路径的长度。

【答案】（1）由题可以画出待定上三角矩阵的结构图如下（图中? 为待定元素）：

可以看出，第一行至第五行主对角线上方的元素分别为5, 4, 3, 2, 1个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：

将各元素填入各行即得邻接矩阵：

（2）根据第一步所得矩阵A 容易做出有向带权图G , 如下：

（3）下图中粗线箭头所标识的4个活动组成图G 的关键路径。

由上图容易求得图的关键路径长度为：4+5+4+3 = 16。

5． 对于后序线索二叉树，怎样査找任意结点的直接后继? 对于中序线索二叉树，怎样査找任意结点的直接前驱？

【答案】（1）后序线索树中结点的后继的方法如下：根结点无后继：当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩于且双亲无右孩时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树种最左下的叶结点是其后继。

（2）对中序线索二叉树的某结点，若其左标记等于1，则左孩子为线索，指向直接前驱；否则其前驱是其左子树上按中序遍历的最后一个结点。

6． 在堆排序、快速排序和合并排序中：

（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？

（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？

（3）若只从平均情况下排序最快考虑，则应选取哪种排序方法？

（4）若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？

【答案】（1）应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法。 （2）应选取归并排序方法

（3）应选取快速排序方法

（4）应选取堆排序方法

7． 假设利用边界标识法，并以首次拟合策略分配，己知在某个时刻可利用空间表的状态如图所示（注：存储块头部域的值和申请分配的存储量均包括头部和尾部的存储空间）请画出：

（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；

（2）系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。