中山大学 2015 年918专业基础（数据结构）考研真题

贡献者： 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;

　　 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 分)

　　 5. 给定图 $G$ 如下

　　 (1)请找出并画出图 $G$ 的一棵最小代价生成树. (5 分)
(2)请画出图 $G$ 对应的邻接矩阵. (6 分)

3. 三、编程题(共 50 分)

　　 1. (10 分)以下是一个(不完整的)直接插入排序算法的代码，请根据注释的提示把缺少的代码补充完整。

void insertion_sort(int entrylI, int count)
{
    int first. unsorted;  // position of first unsorted entry
    int position;         // searches sorted part of list
    int current;          // holds the entry temporarily removed from list
    for(first_unsorted = 1; first_unsorted < count; first_unsorted++)
    {
        if(entry[first_unsorted] < entry[first_unsorted-1])
        {
            // please complete the code here
        }
    }
}

　　 2. (15 分)逆转链表:写一算法逆置带头结点的单链表 L,要求逆置后的单链表利用 L 中的原结点，不可以重新申请结点空间。链表结点的声明如下:

template <class Entry>
struct Node{
    Entry data;
    Node<Entry> * next;
};

void reverse(Node<Entry>* L)

　　 3. (25 分)写一个算法，逐层遍历一棵二叉树(从上到下，从左到右)。以下是二叉树及二叉树中的节点的声明:

template <class Entry>
class Binary_tree {
public:
    Binary_tree();
    void Layer_order(vold(*visit)(Binary_node<Entry> &));
protected:
    Binary_node<Entry> * root;
};
template <class Entry>
struct Binary_node{
    Entry data;
    Binary_node<Entry> * left;
    Binary_node<Entry> * right;
    Binary_node();
    Binary_node(const Entry &x);
};

void Layer.order(void(*visit)(Entry &)).