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

一、算法设计题

1． 设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针) ，data(数据) 和next(后继指针) 域外，还有一个访问频度域freq 。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L，X) 运算时，令元素值为x 的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增(递减) 的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x) 运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

【答案】算法如下:

//L是带头结点的按访问频度递减的双向链表

//本算法先査找数据x ，査找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中

//P为L 表的工作指针，q 为p 的前驱，用于査找插入位置

//查找值为x 的结点

("不存在所査结点\n”) ；exit(0)；

//令元素值为x 的结点的freq 域加

1

//将P 结点从链表上摘下

//以下査找P 结点的插人位置

//将P 结点插人

//返回值为x 的结点的指针

//算法结束

2． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。

【答案】算法如下:

//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为

//p和q 分别是链表A 和B 的工作指针

//pre为A 中p 所指结点的前驱结点的指针

//A

链表中当前结点指针后移

//B链表中当前结点指针后移

//处理A , B 中元素值相同的结点，

应刪除

//删除结点

3． —个有向图G=(V，E) 的平方图

，使得表示。

【答案】算法如下:

4． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

【答案】算法如下:

//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列

//本算法将两链表合并成一个按元素值递减次序排列的单链表

//pa, pb 分别是链表la 和lb 的工作指针

//la作为结果链表的头指针，先将结果链表初始化为空

//当两链表均不为空时

//将pa 的后继结点暂存于r

满足下述性质

:

当且仅当存在某个顶点且22。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表

//将pa 结点链于结果表中，同时逆置

//恢复pa 为当前待比较结点

//将pb 的后继结点暂存于

r

//将pb 结点链于结果表中，同时逆置

//恢复pb 为当前待比较结点

//避免再对pa 写下面的While 语句

//算法Union 结束

5． 写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。

【答案】算法如下:

//本算法将链表L1拆成L1和L2两个链表，L2链接方向与L1相反

//空链表

//奇数序号结点在L1中

//偶数序号

结点逆置插入到L2中

//置L1

表尾

二、应用题

6． 试证明:同一棵二又树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的相对位置出现(即先后顺序相同) ，例如前序，后序，对称序。

【答案】前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相