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

一、算法设计题

1． 设要求按

是一个记录构成的数组，

是一个整数数组，其值介于1〜100之间，现

的内容调整A 中记录的次序，比如当B[l]＝ll 时，则要求将A[l]的内容调整到A[ll]

中去。规定可使用的附加空间为O(1)。

【答案】算法如下:

//A是100个记录的数组，B 是整型数组，本算法利用数组B 对A 进行计数排序

//若B[i]＝i 则A[i]正好在自己的位置上，则不需要调整

//B[j]和B[k]交换

//r0是数组A 的元素类型，A[j]和A[k]

交换

//完成了一个小循环，第i 个已经安排好

//算法结束

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

【答案】算法如下:

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

点

结束

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

n0

. 叶结点

输出并计数

结束

:

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

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

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

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

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

输入顶点信息

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

4． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。

(2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。

【答案】(1)满足条件的二叉树如下:

(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。

(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下:

全局变量

从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .

中序遍历右子树

叶结点

中序遍历左子树

5． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；

。其中，data 存放结点的值；lc 、rc 为指向左、

右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。

【答案】算法如下:

先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在

设P 指向二叉树的根结点

结束

在中序线索二叉树T 中,, 求给定值为x 的结点的

后继结点

首先在T 树上査找给定值为x 的结点，由p 指向

' 若P 的右标志为1, 则P 的rc 指针指向其后继

结点P 的右子树中最左边的结点是结点P 的中序后继

结库

.

6． 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空，入桟和出找的操作序列可表示为仅由I 和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

(1)下面所示的序列中哪些是合法的？

A.

B.

C.

D.

(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false(假定被判定的操作序列已存入一维数组中) 。

【答案】(1)A和D 是合法序列，B 和C 是非法序列。 (2)设被判定的操作序列已存入一维数组A 中，算法如下:

//判断字符数组A 中的输入输出序列是否是合法序列。

//i为下标

//j和k 分别为I 和字母O 的个数

//入栈次数增

1