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

一、算法设计题

1． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。

【答案】算法如下:

在二叉树t 中査找结点值等于x 的结

点

结束

统计以t 为根结点的子树的叶结点数

n0

. 叶结点

输出并计数

结束

:

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

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

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

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

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

输入顶点信息

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

3． 试编写一算法对二叉树按前序线索化。

【答案】算法如下:

设置前驱

对以线索链表为存储结构的二叉树BT 进行前序线索化

设置左线索

设置前驱的右线索

为建立右链做准备

前驱后移

左子树前序线索化

右子树前序线索化

结束

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

【答案】算法如下:

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

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

//监视哨

//pa指针后移

//pb指针后移

//处理交集元素

//删除重复元素

//交集元素并入结果表

//置结果链表尾

5． 设排序二叉树中结点的结构为下述三个域构成:

Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。

【答案】算法如下:

非递归删除以r 为根的二叉排序树

栈，容量足够大，栈中元素是二叉排序树结点的指针

沿左分枝向下

出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间

在二叉排序树T 中删除所有小于等于x

的结点

根结点的值小于等于

x

删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止

沿根结点左分支向下，査小干等于x 的结点

q 记P 的双亲

结点的值小于等于

x

再査原P 的右子树中小于等于x 的结点

二、应用题

6． 给出一组关键字:29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程:

归并排序，每归并一次书写一个次序。 快速排序，每划分一次书写一个次序。

堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 【答案】(1)2—路归并第一趟:18，29，25，47，12，58，10，51; 第二趟:18，25，29，47，10，12，51，58;