2017年陕西科技大学902数据结构(同等学力加试)复试仿真模拟三套题
● 摘要
一、应用题
1． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？
【答案】（1）最高位优先（MSD ）法 先对最高位关键字进行排序，将序列分成若干子序列，
每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字
列。
（2）最低位优先
先对最低位关键字
位关键字
序列参加排序，
但对法 进行排序，然后对高一级关键字进行排序，依次重复，直至对最高进行排序，按值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。
2． 设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。
（1）给出完整的合并过程，并求出最坏情况下比较的总次数。
（2）根据你的合并过程，描述
n
【答案】
（1）6个表的合并顺序如下图所示。
个不等长升序表的合并策略，并说明理由。
对应于合并过程的哈夫曼树
根据上图中的哈夫曼树，6个序列的合并过程为：
第1次合并：表A 与表B 合并，生成含45个元素的表AB ;
第2次合并：表AB 与表C 合并，生成含85个元素的表ABC ;
第3次合并：表D 与表E 合并，生成含110个元素的表DE ;
第4次合并：表ABC 与表DE 合并，生成含195个元素的表ABCDE ;
第5次合并：表ABCDE 与表F 合并，生成含395个元素的最终表。
由于合并两个长度分别为m 和n 的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比较的总次数计算如下：
第1次合并：最多比较次数= 10+35-1=44;
第2次合并：最多比较次数=45+40-1 = 84;
第3次合并：最多比较次数=50+60-1 = 109;
第4次合并：最多比较次数=85+110-1 = 194;
第5次合并：最多比较次数= 195+200-1 = 394; 比较的总次数最多为：44+84+109+194+394 = 825。
（2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。
3． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？
【答案】（1）首次适配法
从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。
（2）最佳适配法
链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。
（3）最差适配法
链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。
4． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。
图1
【答案】因为
小为
因为所以768和所以首址大小为互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址
将其插入可利用空间表中。回其伙伴地址为512、；大小为的空闲块。因为收后该伙伴系统的状态图如图2所示：
图2 回收后该伙伴系统的状态图
5． 在二叉树的Llink-Rlink 存储表示中，引入“线索”的好处是什么？
【答案】在二叉链表表示的二叉树中，引入线索的目的主要是便于査找结点的前驱和后继，因为若知道各结点的后继，二叉树的遍历就非常简单。利用二叉链表结构查结点的左右子女非常方便. 但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时作为前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定：当ltag=0时，lchild 指向左子树，当ltag=1时，lchild 指向前驱：当rtag=0时，rchild 指向右子树，当rtag=l时，rctiild 指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈（利用后序线索二叉树査后扔继续要栈）。