华中科技大学 2016 年数据结构与算法分析 887 真题
一．术语解释
1. 队列
2. 森林
3. 线性表的链式存储结构
4. 图的遍历
5. 哈希函数的同义词
二．单项
1. 2^167 的个位数是（）
A.2 B.4 C.6 D.8
2. 算法
Int func(int n)
{
if(n==0)
{
return(n);
A. 1、2、3、4、5 B. 3、4、2、1、5
A. 3、4、5、2、1 B. 4、2、5、3、1
5．对一组关键字{ 10、20、30、40、50}，使用哈希函数 n(key)=key%7,在一个装填因子为
0.6 的哈希表中，采用线性探测法方式处理冲突，岁任意关键字，当查找不成功时，平均查
找次数是（）
A.16/7 B. 16/9 C. 17/9 D. 18/9
三．简答题
1.一个整型数组是{ 1、8、2、3、4、5、6、7}，利用数组建成一个最小堆，并使用堆排序，
将其排序为一个降序数组，要求用图形表示中间过程结果。
2.如何通过一次遍历找到单链表倒数第三个节点，画图说明计算过程。
3.一个有向图如下所示，给出该图的邻接矩阵，并得到所有拓扑排序的结果。
}
return(n%7+func(n/7);
}
时间复杂度（）
A. O(logn) B. O(n) C. O(nlogn) D. O(n^2)
3. 一个算法的时间复杂度与哪一因素无关（）
A.输入参数的值 B.问题的规模
C.计算机主频 D.循环执行的次数
4. 1、2、3、4、5 依次入栈，不可能的出栈顺序（）
V0
V1
V2
V3ห้องสมุดไป่ตู้
V4
V5
V6
V7
V8
4.证明对于长度为 N 的整型数组，快速排序的平均时间复杂度为 O(nlogn) 5.如果找到两个长度分别为 m 和 n 的按升序排列的整型数组的中位值，即两个数组所有元素 中第(m+n)/2 小的元素，并分析时间复杂度，如何设计算法用对数复杂度得到结果。 四，算法题 注意：如果编写代码困难，可以使用伪代码代替，但会扣一定的分 1．设计并实现 C 语言程序 int findMaxlength(NODE* root)，计算给定根节点为 root 的一棵 二叉树中任意两节点距离的最大值，其中双亲与子女节点为单位距离。 2. 编写一个 C 语言函数 void print_intersection(int a[],int b[],int n),打印两个长度为 n 的按升序 排列数组的交集。
以上资料为手抄版，用于考生交流，严禁用于商业用途！ Produced by sylen