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

一、应用题

1． 设有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）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。

2． 写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。

【答案】此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。

第一趟：12，23，35，16，25，36， 19，21，16， 47 第二趟：12，16，23，35，16，25，36， 19，21，47 第三趟：12，16，23，16，25，35， 19，21，36， 47 第四趟：12， 16， 16，23， 19， 25， 35， 21， 36，47 第五趟：12，16，16，19，23，25，21，35， 36， 47 第六趟：12，16，16，19，21， 23，25，35， 36， 47 第七趟：12，16，16，19，21，23，25，35， 36， 47

3． 对下面的关键字集

若查找表的装填因子为0.8，采用线性探

测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。

【答案】（1）由于装填因子为0.8，关键字有8个，所以表长为哈希函数，哈希函数为

（2）哈希表如表所示：

表 哈希表

（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，

当其哈希地址为

时的查找次数。本例中

（4）算法如下：

用除留余数法设计

故查找失败和查找成功时的平均查找长度分别为：

4． 证明：置换选择排序法产生的初始归并段的长度至少为m （m 是所用缓冲区的长度）。

【答案】证明：由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，，缓以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时（即初始归并段）冲区中m 个元素中除最小元素之外，其他m-1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的m 个元素。证毕。

5． 设度为m 的树采用多重链表存储，毎个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。 则空指针的数目是多少？说明这种存储方式的利弊。

【答案】（1）空指针数目：n （n>0）个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nm-（n-1）=n（m-l ）+1个。

（2）利弊：这种存储结构统一，便于处理但空链域造成存储效率低。

6． 若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。