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

一、算法设计题

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

【答案】算法如下:

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

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

false

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

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

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

2

//结点值间的关

系符合题目要求

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

//未查到表尾就结束了

//成功返回

//算法结束

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

//初始p ﹣＞next 指向第二项

//失败

//成功

2． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。

【答案】算法如下:

//本算法将无符号十进制整数m 转换为十六进制整数

本算法的递归描述如下:

//本算法将无符号十进制整数m 转换为十六进制整数

3． 已知两个链表A 和B 分别表示两个集合，其元素递增排列。编一函数，求A 与B 的交集，并存放于A 链表中。

【答案】算法如下:

//设工作指针pa 和pb ；

//结果表中当前合并结点的前驱的指针

//交集并入结果表中

//释放结点空

间

//释放结点空间

//释放结点空间

//置链表尾标记

//注:本算法中也可对B 表不作释放空间的处理

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

【答案】算法如下:

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

j)

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

释放空间

沿链表继续査找

删顶点j 的边结点(j,

i)

释放空间

沿链表继续査找

5． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i

【答案】算法如下:

对以邻接表存储的DAG 图g 重新编号, 使若有

记录结点的逆序序号

，则编号

求各顶点的入度