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

一、算法设计题

1． 编写算法，求二叉树的宽度。

【答案】算法如下:

求二叉树bt 的最大宽度

空二叉树宽度为

Q 是队列，元素为二叉树结点指针，容量

足够大

front 为队头指针，rear 为队尾指针

last 为同层最右结点在队列中的位置

temp 记当前层宽度，maxw 记最大宽度

根结点入队

同层元素数加

1

左子女入队

右子女入队

一层结束

指向下层最右元素

更新当前最大宽度

2． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。

串被确认的最大长度

【答案】算法如下:

//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回0

//在类C 中，一维数组下标从零开始

//两串相等

//算法结束

3． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，

试写出判断表达式中括号

是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:

//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配

//s是一维数组，容量足够大，是用于存放括号的栈

//top用作栈顶指针

//'#先入栈，用于和表达式结束符号'#'匹配

//字符数组E 的工作指针

//逐字符处理字符表达式的数组

//读人其他字符，不进行处理

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

【答案】算法如下:

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

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

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

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

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

行号

" 修改第i 行最小元素的

列号

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

是马鞍点，

元素值是

是马鞍点

5． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。

【答案】算法如下:

//head是带头结点的单链表的头指针

//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间

//循环到仅剩头结点

//pre为元素最小值结点的前驱结点的指针

//P为工作指针

//记住当前最小值结点的前驱

//输出元素最小值结点的数据

//删除元素值最小的结点，释放结点

空间

//释放头结点

//

二、应用题

6． 设度为m 的树采用多重链表存储。每个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。则空指针的数目是多少? 说明这种存储方式的利弊。

【答案】(1)空指针数目:n(n>0)个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有

+1个。

(2)利弊:这种存储结构统一，便于处理但空链域造成存储效率低。