2018年同济大学电子与信息工程学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。
【答案】算法如下:
//设整数序列存于数组a 中，共有n 个，本算法求解其最大值
2． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组
【答案】算法如下:
本句的有无不影响査找结果
3． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
第 2 页，共 38 页
中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not
find ”信息。请编写出算法并简要说明算法思想。
r 最小值
("最大值
) ；
4． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。
【答案】算法如下:
复制二叉树t 的非递归算法
是二叉树的结点指针的队列，容量足够大
结束本题
5． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。
【答案】算法如下:
//本算法将无符号十进制整数m 转换为十六进制整数
本算法的递归描述如下:
//本算法将无符号十进制整数m 转换为十六进制整数
第 3 页，共 38 页
二、应用题
6． 写出下面算法中带标号语句的频度。
TYPE
Ar ＝ARRAY[l...n]OF datatype；
PROCEDURE penn(a:ar ；k ，n :integer) ； V AR x:datatype ；i :integer ； BEGIN (1)IF k＝n THENBEGIN
(2)FOR i:＝l TO nDO (3)write(a[i])；
(4)FOR i:＝k TO n DO (5)A[i]:＝a[i]+i*i； (6)perm(a, k+1, n) ；
设k 的初值等于1。
【答案】(1)这是一个递归调用，因k 初值为1, 由语句(6)知，每次调用k 增1，故第(1)语句执行n 次，所以频度是n 。
(2)这是FOR 循环语句，在满足(1)的条件下执行，该语句进入循环体(3)n次，加上最后一次判断出界，故执行了n ＋1次，所以频度是n ＋1。
(3)这是循环体语句，共执行了n 次，所以频度是n 。
(4)这是循环语句，当k ＝l 时判断n ＋1次(进入循环体(5)n次) ，k ＝2时判断n 次，最后一次k ＝n ﹣l 时判断3次，故执行次数是(n＋1) ＋n ＋... ＋3＝(n＋4)(n﹣1)/2次，所以频度是(n＋4)(n﹣1)/2。
(5)语句(5)是(4)的循环体，每次比(4)少一次判断，故执行次数是n ＋(n﹣1) ＋... ＋2＝(n＋2)(n
第 4 页，共 38 页