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

一、算法设计题

1． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。

【答案】算法如下:

求以双亲表示法作为存储结构的树的深度

深度加1, 并取新的双亲

最大深度更新

返回树的深度

’结束Depth

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

【答案】算法如下:

全局变量链表头指针

将

若bt 不空

中序遍历左子树

叶结点

第一个叶结点

生成头结点

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

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

中序遍历右子树

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

)

结束

第 2 页，共 35 页

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

当前叶结点链入双链表

；

3． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为

【答案】算法如下:

从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素

，其中，2为排序树中所含结点数，m 为输出的关键字个数。

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

【答案】算法如下:

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

否则返回-1表示失败

元素序号

结束

，查找失败的平均查找

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

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

5． 设是一个记录构成的数组，是一个整数数组，其值介于1〜100之间，现要求按

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

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

【答案】算法如下:

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

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

第 3 页，共 35 页

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

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

交换

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

//算法结束

二、应用题

6． 调用下列C 函数f(n)，回答下列问题:

(1)试指出f(n)值的大小，并写出，f(n)值的推导过程；

(2)假定n ＝5, 试指出，f(5)值的大小和执行，f(5)时的输出结果。 C 函数:

【答案】(1)第一层FOR 循环判断n ＋1次，往下执行n 次，第二层FOR 执行次数为(n＋(n﹣1) ＋(n﹣2) ＋... ＋1) ，第三层循环体受第一层循环和第二层循环的控制，其执行次数如表所示。

执行次数

表

执行次数为f(n)＝(1＋2＋... ＋，n) ＋(2＋3＋... ＋，n) ＋... ＋n ＝n*n(n＋1)/2﹣n(n2﹣l)/6。(2)在n ＝5对，f(5)＝55，执行过程中，输出结果为:sum ＝15 sum＝29 sum＝41 sum＝50 sum＝55

第 4 页，共 35 页