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

一、算法设计题

1． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。

【答案】算法如下:

复制二叉树t 的非递归算法

是二叉树的结点指针的队列，容量足够大

结束本题

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

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

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

【答案】算法如下:

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

设P 指向二叉树的根结点

结束

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

后继结点

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

第 2 页，共 37 页

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

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

结库

.

3． 设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中(注:按层从上到下，由左到右) 。

【答案】算法如下:

是结点在一维数组中的编

号

队列，容量足够大

本算法将二叉树的二叉链表存储结构转换为顺序存储结构

seq

初始化，#代表虚结点

根结点入队

存入顺

序存储结构

左

子女入队

右

子女人队

4． 结点类型和存储结构如下:

试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。

【答案】算法如下:

对存储在数组R 中的记录进行排序

初始化

设R[0]作监视哨，Max 是该类型最大元

素

初始假定第一个元素有序

第 3 页，共 37 页

前驱

第一个元素

査找第i 个元素的序号

将笫i 个元素链入静态链表

5． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。

【答案】算法如下:

//设整数序列存于数组a 中，共有n 个，本算法求解其最大值

二、应用题

6． 已知有5个顶点的图如下图所示

图

请回答下列问题

(1)写出上图的邻接矩阵A(行、列下标从0开始) 。 (2)求A2, 矩阵(3)

若已知具有么？

【答案】(1)邻接矩阵为

中位于0行3列元素值的含义是什么？

个顶点的邻接矩阵为B ,

则

非零元素的含义是什

第 4 页，共 37 页