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

一、算法设计题

1． 请用流程图或高级语言表示算法。已知有向图有n 个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的

(以其中之一为0标志结束) ，对于每条这样的

边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。

提示:先产生邻接表的n 个头结点(其结点数值域从1到n) 。 【答案】算法如下:

建立有向图的邻接表存储结构

输入顶点信息

题目要求两顶点之一为0表示结束

2． 写出按后序序列遍历中序线索树的算法。

【答案】算法如下:

求结点t 最左子孙的左线索

沿左分支向下

求结点t 最右子孙的右线索

沿右分支向下

第 2 页，共 36 页

若t 是的右孩子，返回1, 否则返回

后序遍历中序线索二叉树

bt

沿左分支向下

左孩子为线索，右孩子为链，相当从左返回

P 为叶子, 相当从右返回

访问结点

修改P 指向双亲

是左子女，用最右子孙的右线索找双亲

.

转向当前结点右分支

结束

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

【答案】算法如下:

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

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

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

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

//分解原链表

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

//处理字母字符

//处理数字字符

//处理其他符号

//结束while(L!＝

null) //算法结束

第 3 页，共 36 页

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

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

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

//算法结束

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

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

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

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

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

哈希地址

1~26

设哈希表初始值为

null

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

(2)算法如下:

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

记査找不成功的总的次数

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

第 4 页，共 36 页

和B 的

【答案】算法如下:

-