中山大学 2015 年918专业基础(数据结构)考研真题 – 小时百科
2024年 7月 4日 
 
 
 
 
 
 
 
 
 
 
贡献者: xzllxls
声明:“该内容来源于网络公开资料，不保证真实性，如有侵权请联系管理员”
1. 一、单项选择题(每小题 3 分，共 45 分)
1. stl 中的优先队列是采用什么数据结构来实现的？
a.堆 $\qquad$ b.队列 $\qquad$ c.栈 $\qquad$ d.图
2.数据结构中，与所使用的计算机无关的是数据的()结构。
a.存储 $\qquad$ b.物理 $\qquad$ c.逻辑 $\qquad$ d.物理和存储
3.计算机算法指的是( )。
a.计算方法 $\qquad$ b. 排序方法
c.调度方法 $\qquad$ d. 解决问题的有限指令序列
4.给定一个有 n 个元素的数组(n 为偶数)。如果要找出数组中的最大元素和最小元素，最少要进行( )次比较？
a.$2n$ $\qquad$ b.$3n/2-2$ $\qquad$ c.$2n-2$ $\qquad$ d.$4n/3$
5.给定一个包含 250 个整数的数组，该数组中的整数已按从小到大的顺序排好序。假设用二分查找从该数组中寻找某个给定的整数 y,最多只需要做( )次比较。
a.8 $\qquad$ b.9 $\qquad$ c.10 $\qquad$ d.7
6. $t(n)$ 表示某个算法的时间复杂度。假设 $t(n)=2t(n/2)+o(m)$,则 $t(n)$ 为( )
a. $o(log3n)$ $\qquad$ b. $o(n)$ $\qquad$ c. $o(nlog_3n)$ $\qquad$ d. $o(n^2)$
7.假设整数 n>0，下面的程序的时间复杂度是( ).
x=2;
while (x<n/3) x=2*x;
a. $o(log_2n)$ $\qquad$ b. $o(m)$ $\qquad$ c. $o(nlog_2n)$ $\qquad$ d.$o(n)$
8.下列排序算法中，哪个是稳定的排序算法？
a.选择排序 $\qquad$ b. 快速排序 $\qquad$ c. 归并排序 $\qquad$ d. 希尔排序
9.假设小明用某-排序算法对整数序列(82, 45, 25, 15, 21)进行排序。以下为排序过程中序列状态的变化过程:
输入:82 45 25 15 21
第一步:45 82 25 15 21
第二步:25 45 82 15 21
第三步:15 25 45 82 21
……
请问小明用的是什么排序算法？
a.选择排序 $\qquad$ b.归并排序 $\qquad$ c.快速排序 $\qquad$ d.插入排序
10.以下的排序算法中，哪个算法在最坏情况下的时间复杂度是 0(n3)？
a.堆排序 $\qquad$ b. 快速排序 $\qquad$ c. 归并排序 $\qquad$ d. 基数排序
11.给定一个算术表达式 $x$。$x$ 的中缀形式是 $a*b+c*d-e$，且 x 的前缀形式是 $+*ab-*cde$.那么，$x$ 的后缀形式是什么？
a. $acd*e-b*+$ $\qquad$ b. $ab*cd*+e-$ $\qquad$ c. $cd*e-ab*+$ $\qquad$ d. $ab*cd*e-+$
12.给定一棵空的 avl 树，依次把 13, 24, 37, 90, 53 逐一插入该树，在此过程中要保持该树为 avl 树(假设左子树的元素要小于右子树) .则最终得到的 avl 树的高度是( ), 树根是( ).
a.3,37 $\qquad$ b.3, 24 $\qquad$ c.4, 37 $\qquad$ d.3, 53
13.下面哪个函数随着 n 增大而增长得最快？( ).
a.$100n^2log_2n$
b.$n(log_2n)^5$
c.$n^{2.1}$
d.$n^2+1000nlog_2n$
14.一个有 $n$ 个顶点的无向图最多有( )条无向边(假设该图无自环)。
a.$n$ $\qquad$ b. $n(n-1)$ $\qquad$ c. $n(n-1)/2$ $\qquad$ d.$2n$
15.一棵高度为 $k$ 的二又树最多有( )个节点
a.$2^{k+1}-1$ $\qquad$ b.$2^k-1$
c.$2^{k+1}-1$ $\qquad$ d.$2^k+1$.
2. 二、简答题(共 55 分)
1. (11 分)给定一个整数数组{4,6,3,2,1,5,7}.假设用选择排序算法对数组中的整数进行从小到大排序。请写出每次迭代后数组中的状态( 即每次迭代后，数组中的 7 个整数是如何排序的)
2. (11 分)从空的二叉树开始，根据字典顺序，严格按照二叉排序树(或称二叉搜索树)的插入算法，依次插入 e，b, d, f, a, g, c。请画出构造二叉排序树的每一步骤。
3. (10 分)假定一个堆为(56,38,42,30,25,40,35,20)，则依次从中删除两个元素后得到的堆是什么？要求画出过程。
4.给定一个空的哈希表，依次把键 12, 34, 55, 54, 13, 21, 19, 70 插入到哈希表中。假没采用的哈希函数是 b(k)=k mod 11,采用线性探查(linear probing)来解决冲突
(1)当上述键值全部插入后，请画出哈希表的状态(6 分)
(2)假如每个键值被查找的概率均等，请计算出平均查找长度(average search length) (6 分)
表1:第二 4 题表