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

一、算法设计题

1． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:

{二叉树根结点的指针}

【答案】算法如下:

生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写

)

是二叉树结点指针的一维数组，容量足够大

一维数组最后元素的下标

元素或虚结点

根结点

双亲结点和子女结点用指针链上

结束

2． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。

【答案】算法如下:

以后序遍历算法求以二叉树表示的算术表达式的

值

.

求左子树表示的子表达式的值

求右子树表示的子表达式的值

3． 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C , 其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点(链表A 的元素类型为整型，要求B 、C 表利用A 表的结点) 。

【答案】算法如下:

//本算法将带头结点的单链表A 分解成数据域值小于零和大于零的两个单链表B 和

C

//为C 申请结点空间

//C初始化为空表

//P为工作指针

//B表初始化

//暂存P 的后继

//小于0的放入B 表

//将小于0的结点链人B 表

//P指向新的待处理结点

//算法结束

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

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

【答案】算法如下:

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

初始化

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

素

初始假定第一个元素有序

前驱

第一个元素

査找第i 个元素的序号

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

5． 请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。

【答案】算法如下:

//A是的矩阵，本算法求矩阵A 中的马鞍点

//max数组存放各列最大值元素的行号，初始化为行号

//min数组存放各行最小值元素的列号，初始化为列号

0 //选各行最小值元素和各列最大值元素

//修改第j 列最大元素的

行号

" 修改第i 行最小元素的

列号

//第i 行最小元素的列号

是马鞍点，

元素值是

是马鞍点

//

二、应用题

6． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问:

当n=7时，在最好情况下需进行多少次比较? 请说明理由。 当n=7时，给出一个最好情况的初始排序的实例。