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

一、算法设计题

1． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组

【答案】算法如下:

本句的有无不影响査找结果

2． 设排序二叉树中结点的结构为下述三个域构成:

Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。

【答案】算法如下:

非递归删除以r 为根的二叉排序树

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

沿左分枝向下

出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间

在二叉排序树T 中删除所有小于等于x

的结点

第 2 页，共 40 页

中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not

find ”信息。请编写出算法并简要说明算法思想。

根结点的值小于等于

x

删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止

沿根结点左分支向下，査小干等于x 的结点

q 记P 的双亲

结点的值小于等于

x

再査原P 的右子树中小于等于x 的结点

3． 设线性表存于A[l..size]的前mun 各分量中，且递增有序。请设计一个算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。

【答案】算法如下:

//A是Size 个元素空间但目前仅有num(num＜size}个元素的线性表 //本算法将元素x 插入到线性表中，并保持线性表的有序性

//题目要求下标从1开始

//对分査找元素x 的插入位置

//元素后移

//将元素x 插人

算法结束

设计思想:算法中当查找失败(即线性表中无元素X) 时，变量low 在变量high 的右面(low＝high ＋l) 。移动元素从位置low 开始，直到num 为止。

时间复杂度:查找的复杂度为O (logn)，插入的时间复杂度为O (n)，若用顺序查找，则查找的时间复杂度亦为O(n)。

第 3 页，共 40 页

4． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。

【答案】算法如下:

//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为

//p和q 分别是链表A 和B 的工作指针

//pre为A 中p 所指结点的前驱结点的指针

//A

链表中当前结点指针后移

//B链表中当前结点指针后移

//处理A , B 中元素值相同的结点，

应刪除 //删除结点

5． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。

【答案】算法如下:

在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回

确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情

况

返回第一邻接点，

和

中必有一个等于

i

取第一个边结点

二、应用题

6． 设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素, 各表中元素按升序排列。要求通过5次两两合并, 将6个表最终合并成1个升序表, 并在最坏情况下比较的总次数达到最小。请回答下列问题。

(1)给出完整的合并过程, 并求出最坏情况下比较的总次数。 (2)根据你的合并过程, 描述

个不等长升序表的合并策略, 并说明理由。

【答案】(1)6个表的合并顺序如下图所示。

第 4 页，共 40 页