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

一、算法设计题

1． 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？

【答案】算法如下:

关键字

链指针

用链地址法解决冲突，构造哈希表，哈希函数用

初始化

输入n(本例中n=9)

个关键字按题意x 互不相同

4等插入结点链入同义词表

构造的哈希表如图所示:

图构造的哈希表

查找成功时的平均查找长度

。

2． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。

【答案】算法如下:

复制二叉树t 的非递归算法

是二叉树的结点指针的队列，容量足够大

结束本题

3． 设稀疏矩阵中有t 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M 的转置矩阵N ，要求转置算法的时间复杂度为0(n＋t) 。

【答案】算法如下:

//采用三元组表方式存储，按列序实现矩阵的转置

//行数、列数和非零元素个数

//设置N 中第一个非零元素从下标1开始存储

//按列，共

//在//转置

//三元组表上实现矩阵的快速转置的算法

列

个元素中查找

//矩阵M 每一列非零元初始化为零

//求矩阵M 每一列的非

零元个数

//第1列第一个非零元在转置后的三元组中下标是

1

//求

第j 列第一个非零元在

中的序号

//求转置矩阵N 的三元组表

//同列下一非零元

素位置

4． 设有一个数组中存放了一个无序的关键序列

【答案】算法如下:

5． 设排序二叉树中结点的结构为下述三个域构成:

Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。

【答案】算法如下:

非递归删除以r 为根的二叉排序树

栈，容量足够大，栈中元素是二叉排序树结点的指针

沿左分枝向下

。现要求将K n 放在将元素排序后

的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。