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

一、算法设计题

1． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。

【答案】算法如下:

//d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面

//设链表有头结点

//q指向待处理结点

//P记数据域值最大的结点

//将P 摘下

//插人P 结点

2． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(

【答案】算法如下:

在后半部分继续进行划分

在前半部分继续进行划分

第 2 页，共 35 页

) 小元素。

3． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。

【答案】算法如下:

按递减次序输出二叉排序树结点的值

是元素为二叉树结点指针的栈，容量足够大

沿右子树向下

结束

4． 已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。

(1)编写用前序遍历树中每个结点的非递归算法；

(2)编写将树中最大序号叶结点的祖先结点全部打印输出的算法。 【答案】(1)算法如下:

全局变量

递妇遍历以顺序方式存储的二叉树bt ，i 是根结点下标(初始调用时为

1)

是桟s 的栈顶指针，栈容量足够大

访问根结点，设虚结点

以0表示

右子女的下标位置入

栈

沿左子女向下

取出栈顶元素

结束

(2)算法如下:

打印最大序号叶结点的全部袓先

找最大序号叶结点，该结点存储时在最后

的双亲结点

f

从结点c 的双亲结点直到根结点，

路径上所有结点均为祖先结点

逆序输出，最老的祖先最后输出

结束

第 3 页，共 35 页

5． 设要求按

是一个记录构成的数组，是一个整数数组，其值介于1〜100之间，现

的内容调整A 中记录的次序，比如当B[l]＝ll 时，则要求将A[l]的内容调整到A[ll]

中去。规定可使用的附加空间为O(1)。

【答案】算法如下:

//A是100个记录的数组，B 是整型数组，本算法利用数组B 对A 进行计数排序

//若B[i]＝i 则A[i]正好在自己的位置上，则不需要调整

//B[j]和B[k]交换

//r0是数组A 的元素类型，A[j]和A[k]

交换

//完成了一个小循环，第i 个已经安排好

//算法结束

二、应用题

6． 为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？

【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。

7． 设散列表为，即表的大小为m=13。现采用双散列法解决冲突。散列函数和再哈希函数分别为:

»

注:

％是求佘数运算

中，函数REV(X)表示颠倒十进制数x 的各位，如码序列为(2，8，31，20，19，18，53，27) 。

(1)试画出插入这8个关键码后的哈希表； (2)计算搜索成功的平均搜索长度ASL 。

【答案】(1)插入这8个关键码后的哈希表如表所示:

表 插入关键字后的哈希表

其

等。若插入的关键

第 4 页，共 35 页