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

一、算法设计题

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． 已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。

【答案】算法如下:

根据二叉树前序序列pre 和中序序列in 建立二叉树。第 2 页，共 36 页 和是两个序列首、尾

元素下标

申请结点

是根

在中序序列中，根结点将树分成左右

子树

无左子树

递归建立左子树

无右子树

递归建立右子树

结束:

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

【答案】算法如下:

//设工作指针pa 和pb ；

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

//交集并入结果表中

//释放结点空

间

//释放结点空间

//释放结点空间

//置链表尾标记

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

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

【答案】算法如下:

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

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

false

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

第 3 页，共 36 页

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

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

2

//结点值间的关

系符合题目要求

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

//未查到表尾就结束了

//成功返回

//算法结束

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

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

//失败

//成功

5． 给定nxm 矩阵并设

设计一算法判定x 的值是否在A 中，要求时间复杂度

为O(m＋n) 。

【答案】算法如下:

//n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中

//flag是成功査到x 的标志

//假定x 为整型

(“矩阵A 中无

算法search 结束。

元素\n"，x) ；

二、应用题

6． 将算术表达式转化为二叉树。

【答案】该算术表达式转化的二叉树如图所示。

第 4 页，共 36 页