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

一、算法设计题

1． 试将下列递归过程改写为非递归过程。

【答案】算法如下:

2． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。

【答案】算法如下:

在二叉树t 中査找结点值等于x 的结

点

结束

统计以t 为根结点的子树的叶结点数

n0

. 叶结点

输出并计数

结束:

3． 在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L ，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。

顺序存储结构的线性表描述为:

线性表可能达到的最大长度}；

【答案】算法如下:

//在顺序表a 中査找值为x 的元素，査找成功返回0值，否则返回查找失败时的较大下标值

//当査找失败时，low ＝high ＋

1

//结束对分査找函数

//本过程生成顺序表

L

//顺序表L 初始化

//设x ＝9999时退出输入

//去查找x 元素

//不同元素才插入

//插入元素x ，线性表长度增

1

//结束过程creat

4． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。

【答案】算法如下:

在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置

否则返回-1表示失败

元素序号

结束

，查找失败的平均查找

期望值分析:在等概率情况下，则查找成功的平均查找长度为

长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为。

5． 给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。

【答案】算法如下:

建立有向图的十字链表存储结构

假定权值为整型

建立顶点向量

当输入i 、j 、v 之一为0时，结

束算法运行

申请结点

弧结点中权值域

算法结束

二、应用题

6． 文件F 由200条记录组成, 记录从1开始编号, 用户打开文件后, 欲将内存中的一条记录插入文件F 中, 作为其第30条记录, 请回答下列问题, 并说明理由。

(1)若文件系统为顺序分配方式, 每个存储块存放一条记录, 文件F 的存储区域前后均有足够空