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

一、算法设计题

1． 已知深度为h 的二叉树，以一维数组应的算法。

【答案】算法如下:

计算深度为h 、以一维数组BT 作为其存储结构的二叉树的叶结点数，n 为数组长度

记叶结点数

若结点无孩子，则

是叶子

存储在数组后一半的元素是叶结点

2． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素

在C 中的存放位置下标的公式。

//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置

//算法结束

第 2 页，共 19 页

作为其存储结构，试编写一算法，求该二叉

树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相

和B 的

【答案】算法如下:

3． 设有一个数组中存放了一个无序的关键序列

【答案】算法如下:

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

【答案】算法如下:

。现要求将K n 放在将元素排序后

的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。

求二叉树bt 的最大宽度

空二叉树宽度为

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

足够大

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

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

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

根结点入队

同层元素数加

1

左子女入队

右子女入队

一层结束

指向下层最右元素

更新当前最大宽度

5． 设键盘输入n 个英语单词，输入格式为词个数，试编一程序，建立一个单向链表，实现:

(1)如果单词重复出现，则只在链表上保留一个。

(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出

第 3 页，共 19 页

其中n 表示随后输入英语单

出现次数最多的前k(k＜＝n) 个单词。

【答案】定义结点数据类型如下:

//频度域，记单词出现的次数

//maxsize是单词中可能含有的最多字母个数

(1)算法如下:

（ ）

//建立有n(n＞0) 个单词的单向链表，若单词重复出现，则只在链表中保留一个

//申请头结点

//链表初始化

//建立n 个结点的链表

//a是与链表中结点数据域同等长度的字符数组

//p是工作指针，pre 是前驱指针

//单词重复出现，频度增

1

//指针后移

//该单词没出现过，应插入

//将新结点插入到链表最后

//结束for 循环

//结束creat 算法 (2)算法如下:

（ ）

//建立有n 个单词的单向链表，重复单词只在链表中保留一个，最后输出频度最高的k 个单词

//申请头结点

//链表初始化

//建立n 个结点的链表

//a是与链表中结点数据域同等长度的字符数组

//P是工作指针，pre 是前驱指针

//单词重复出现，频度增1

第 4 页，共 19 页