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

一、算法设计题

1． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。

【答案】算法如下:

在增加双亲指针

和标志域

的二叉树中，不用栈后序遍历二叉树

) 区分在遍

历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍

向左

向右

访问根结点

找被访问结点的双亲

结束

2． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。

【答案】算法如下:

L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符

//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表

//建立三个链表的头结点

//置三个循环链表为空表

//分解原链表

//L指向待处理结点的后继

//处理字母字符

//处理数字字符

//处理其他符号

//结束while(L!＝

null) //算法结束

3． 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。

【答案】算法如下:

//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间

//pa、pb 是两链表的工作指针

//监视哨

//pa指针后移

//pb指针后移

//处理交集元素

//删除重复元素

//交集元素并入结果表

//置结果链表尾

4． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素

在C 中的存放位置下标的公式。

【答案】算法如下:

和B 的

//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置

//算法结束

5． 编写算法，求二叉树的宽度。

【答案】算法如下:

求二叉树bt 的最大宽度

空二叉树宽度为

Q 是队列，元素为二叉树结点指针，容量

足够大

front 为队头指针，rear 为队尾指针

last 为同层最右结点在队列中的位置

temp 记当前层宽度，maxw 记最大宽度

根结点入队

同层元素数加

1

左子女入队

右子女入队

一层结束

指向下层最右元素

更新当前最大宽度

二、应用题

6． 在一棵表示有序集S 的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S 分为3部分:在该路径左边结点中的元素组成的集合S1; 在该路径上的结点中的元素组成的集合S2; 在该路径右边结点中的元素组成的集合S3; 有

？为什么？

【答案】该结论不成立。例如，本题中对于任一

。若对于任意的是否总

，可在S2中找到a 的最近祖先f 。a 在