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

一、应用题

1． 设散列表为数分别为

：

注：％是求余数运算中，函数码序列为

（2）计算搜索成功的平均搜索长度

表示颠倒十进制数x 的各位，如

即表的大小为

其

等。若插入的关键

，现采用双散列法解决冲突。散列函数和再哈希函

（1）试画出插入这8个关键码后的哈希表；

【答案】（1）插入这8个关键码后的哈希表如表所示：

表 插入关键字后的哈希表

（2）

2．

设与记录

对应的关键字分别是

进行交换。

之前全部记录

（其

的关键字一定

如果存在

和

使得

且

成立，试证明经过一趟起泡后，一定有记录与值。由题假设知中包括

在

之前且

则

即说明

和

【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极

是反序；设对于

和

）中关键字最大为

，故经过起泡排序前i-2次比较后，

必定交换，证毕。

为又因故和Rf 为反序，由此可知

3． 写出下面算法中带标号语句的频度。

设k 的初值等于1。

【答案】（1）这是一个递归调用，因k 初值为1，由语句（6）知，每次调用k 增1，故第（1）语句执行n 次，所以频度是n 。

（2）这是FOR 循环语句，在满足（1）的条件下执行，该语句进入循环体（3）n 次，加上最后一次判断出界，故执彳丁了n ＋1次，所以频度是n ＋1。

（3）这是循环体语句，共执行了n 次，所以频度是n 。

，k=2时判断n 次，最后（4）这是循环语句，当k=l时判断n ＋1次（进入循环体（5）n 次）

一次k=n－l 时判断3次，故执行次数是（n ＋1）＋n ＋... ＋3=（n ＋4）（n －1）/2次，所以频度是（n ＋4）（n －1）/2。

（5）语句（5）是（4）的循环体，每次比（4）少一次判断，故执行次数是n ＋（n －1）＋... ＋2=（n ＋2）（n －1）/2次，所以频度是（n ＋2）（n －1）/2。

（6）这是循环体语句，共执行了n －1次，所以频度是n －1。

4． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：造出哈希表，试回答下列问题：

（1）画出哈希表示意图；

（2）若查找关键字63，需要依次与哪些关键字比较？ （3）若查找关键字60，需要依次与哪些关键字比较？

（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 【答案】（1）哈希表示意图如表所示：

表 哈希示意图

（2）查找关键字63时，由于63比较。

（3）查找关键字60时，由于（4）

哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17，

为关键字，用

线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）

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

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

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

6． 设

阶稀疏矩阵A 有t 个非零元素，其三元组表示为

表示A 才有意义？ 的

个存储单元，用二维数组存储时占用

个单元，

只有当试问：非零元

素的个数t 达到什么程度时用，共占用三元组表

元组）

时，用

【答案】稀疏矩阵A 有t 个非零元素，加上行数mu 、列数皿和非零元素个数tu （也算一个三

表示A 才有意义。解不等式得

7． 在各种排序方法中，哪些是稳定的? 哪些是不稳定的? 并为每一种不稳定的排序方法举出一个不稳定的实例。

【答案】各种排序算法稳定性的归纳如图所示：

图

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

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

（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？ （3）若只从平均情况下排序最快考虑，则应选取哪种排序方法？

（4）若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 【答案】（1）应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法。 （2）应选取归并排序方法 （3）应选取快速排序方法 （4）应选取堆排序方法

二、算法设计题