中山大学 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;
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 题表
下标 0 1 2 3 4 5 6 7 8 9 10

   5. 给定图 $G$ 如下

图
图 1:第二 5 题图

   (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 &)).


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利