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

一、算法设计题

1． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。

【答案】算法如下:

在用邻接表方式存储的无向图g 中，删除边(i,

j)

删顶点i 的边结点(i, j) , pre 是前驱指针

释放空间

沿链表继续査找

删顶点j 的边结点(j,

i)

释放空间

沿链表继续査找

2． 二路插入排序是将待排关键字序列二路插入。编写实现2-路插入排序算法。

【答案】算法如下:

二路插入排序的算法

辅助存储

插人后部

折半査找插入位置

移动元素

第 2 页，共 37 页

中关键字分二路分别按序插入到辅助向量

前半部和后半部(注.. 向量d 可视为循环表) ，其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分

插入有序位置

插入前部

移动元素

将序列复制回去

3． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)

【答案】算法如下:

//L是带头结点的单链表，本算法删除其最小值结点

//P为工作指针。指向恃处理的结点。假定链表非空

//pre指向最小值结点的前驱

//q指向最小值结点，初始假定第一元素结点是最小值结点

//查最小值结点

//指针后移

//从链表上刪除最小值结点

//释放最小值结点空间

//结束算法Delete

4． 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。

(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。

(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。

【答案】(1)算法如下:

按关键字第一个字母在字母表中的顺序输出各关键字

第 3 页，共 37 页

哈希地址

1~26

设哈希表初始值为

null

取关键字第一字母在字母表中的序号

(2)算法如下:

求链地址解决冲突的哈希表査找不成功时平均査找长度

记査找不成功的总的次数

按我们约定，査找不成功指到空指针为止

5． 已知一个单链表中每个结点存放一个整数，并且结点数不少于2, 请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture ，否则返回false 。

【答案】算法如下:

//la是结点的元素为整数的单链表。本算法判断从第二结点开始

//毎个元素值是否等干其序号的平方减去其前驱的值，如是返回true ；否则，返回

false

//P是工作指针，初始指向链表的第二项

//pre是p 所指结点的前驱指针

//i是la 链表中结点的序号，初始值为

2

//结点值间的关

系符合题目要求

//当前结点的值不等于其序号的平方减去前驱的值

//未查到表尾就结束了

//成功返回

//算法结束

//假设无头结点，初始P 指向第一元素结点

第 4 页，共 37 页

-