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

一、算法设计题

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

【答案】算法如下:

是结点在一维数组中的编

号

队列，容量足够大

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

seq

初始化，#代表虚结点

根结点入队

存入顺

序存储结构

左

子女入队

右

子女人队

2． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，

当

时，将

入栈；当

时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给

出相应的信息。

【答案】算法如下

:

栈空间容量

//s是元素为整数的栈，本算法进行入栈和出栈操作

//top为栈顶指针，定义top ＝0时为栈空

//n个整数序列进行处理

//从键盘读入整数序列

//读入的整数不等于﹣1时人栈

//读入的整数等于﹣1时出栈

//算法结束。

3． 图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算法。

【答案】算法如下:

利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G 的最小生成

树

数组存放生成树

数组存放顶点是否找到最短路径

初始化, 设顶点信息就是编号

从v0开始，求其最小生成树

是尚未到最小生成树的顶点的集合

循环n －1次

顶点u 已找到最短路径下，下面修改相关顶点的最短路径

算法结束

4． 设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 要逆置

和B 的

【答案】算法如下:

//算法结束

5． 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。

(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。

(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。

【答案】(1)算法如下:

按关键字第一个字母在字母表中的顺序输出各关键字

哈希地址

1~26

设哈希表初始值为

null

取关键字第一字母在字母表中的序号

(2)算法如下:

求链地址解决冲突的哈希表査找不成功时平均査找长度

记査找不成功的总的次数

按我们约定，査找不成功指到空指针为止

-

二、应用题

6． 假定对有序表:(3，4，5，7，24，30，42，54，63，72，87，95) 进行折半查找，试回答下列问题:

(1)画出描述折半查找过程的判定树； (2)若查找元素54，需依次与哪些元素比较？