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

目录

2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研仿真模拟题（一） .... 2 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研仿真模拟题（二） .. 12 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研仿真模拟题（三） .. 22 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研仿真模拟题（四） .. 33 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研仿真模拟题（五） .. 43

第 1 页，共 51 页

一、算法设计题

1． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到

【答案】算法如下：

2． 设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。

【答案】（1）递归算法如下：

（2）非递归算法如下：

第 2 页，共 51 页

3． 已知某哈希表序号。

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

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

【答案】（1）算法如下：

（2）算法如下：

的装填因子小于1，哈希函数

为关键字的第一个字母在字母表中的

4． 对给定关键字序号

要求在无序记录

中找到关键字从小到大排在第j 位上的记

录，写一个算法利用快速排序的划分思想实现上述查找（要求用最少的时间和最少的空间）。

例如：给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下：

第 3 页，共 51 页

5． 线性表中元素存放在向量和最小元素。

【答案】算法如下：

6． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。

【答案】算法如下：

//全局变量链表头指针head ,

pre

//将BiTree 树中的所有叶结点链成带头结点的双链表

//若bt 不空

//中序遍历左子树

//叶结点

//第一个叶结点

//生成头结点

//头结点的左链空，右链指向第一个结点

//第一个叶结点左链指向头结点，pre 指向当前叶结点

//当前叶结点链入双链表

//中序遍历右子树

//最后一个叶结点的右链置空（链表结束标记）

//

结束

7． 设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？

【答案】算法如下：

第 4 页，共 51 页

中，元素是整型数。试写出递归算法求出A 中的最大