中山大学 2012 年913专业基础(数据结构)考研真题

                     

贡献者: xzllxls

1. 一、单项选择题(每题 2 分,共 40 分)

   1.算法复杂度通常是表达算法在最坏情况下所需要的计算量,0(1)的含义是( )
(A).算法执行 1 步就完成
(B).算法执行 1 秒钟就完成
(C).解决执行常数步就完成
(D).算法执行可变步数就完成

   2.在数据结构中,按逻辑结构可把数据结构分为( )
(A).静态结构和动态结构
(B).线性结构和非线性结构
(C).顺序结构和链式结构
(D).内部结构和外部结构

   3.在数据结构中,可用存储顺序代表逻辑顺序的数据结构为( )
(A). Hash 表
(B).二叉搜索树
(C).链式结构
(D).顺序结构

   4.对链式存储的正确描述是( )
(A).结点之间是连续存储的
(B).各结点的地址由小到大
(C).各结点类型可以不一-致
(D).结点内单元是连续存储的

   5.在下列关于 “串” 的陈述中,正确的说明是( )
(A).串是一种特殊的线性表
(B).串中元素只能是字母
(C).串的长度必须大于零
(D).空串就是空白串

   6.关于堆栈的正确描述是( )
(A). FILO
(B). FIFO
(C).只能用数组来实现
(D).可以修改栈中元素的数据

   7. 假设循环队列的长度为 QSize。当队列非空时,从其队列头取出数据后,其队头下标 Front 的变化为()
(A). Front = Front+1
(B). Front= (Front+ 1)% 100
(C). Front= (Front + 1) % QSize
(D). Front = Front % Qsize + 1

   8.假设 Head 是带头结点单向循环链的头结点指针,判断其为空的条件是( )
(A). Head.next = NULL
(B). Head->next == Head
(C). Head->next == NULL
(D). Head == NULL

   9.设 A[n][n]为一个对称矩阵,数组下标从[0][0]开始。为了节省存储,将其下三角部分按行存放在一维数组 B[0..m-1],m=n(n+1)/2, 对下三角部分中任一元素 $A_{ij}(i\geqslant j)$ 它在一-维数组 B 的下标 k 值是( )
(A). (-1)/2+j
(B). (-1)2+)-1
(C). (+1)2+j-1
(D). i(i+1)/2+j

   10.假设二又树的根结点为第 0 层,那么,其第 i 层(20)的结点数最多为( )
(A). $2i$
(B). $2^i$
(C). $2^{i+1}-1$
(D). $2^{i+1}$

   11.若一棵二叉树的后序和中序序列分别是 dbefca 和 dbacef,则其先序序列是( )
(A). adbefc
(B). abdcfe
(C). adbcef
(D). abdcef

   12.用一维数组来存储满二叉树,若数组下标从 0 开始,则元素下标为 k 的右子结点下标是( )(不考虑数组下标的越界问题)
(A). 2k+1
(B). 2k+2
(C). $\lfloor k/2 \rfloor$
(D). $\lceil k/2 \rceil$

   13. 假设 LTree 和 RTree 是二叉搜索树 Tree 的左右子树,H(T)表示树 T 的高度。若树 Tree 是 AVL 树,则( )
(A). H(LTree)-H(RTree)=0 (B). H(LTree)- H(RTree)<1 (C). H(LTree) - H(RTree)<= 1 (D). |H(LTree)- HRTree)| <= 1

   14. 对 n 个结点和 e 条边的无向图(无环),其邻接矩阵中零元素的个数为( )
(A).$e$
(B).$2e$
(C).$n^2-e$
(D).$n^2-2e$

   IS.用邻接矩阵存储有 n 个顶点和 e 条边的有向閔,则删除与某个顶点相邻的所有边的时间复杂度是()
(A). $O(m)$
(B). $O(e)$
(C). $O(n+e)$
(D). $O(ne)$

   16. 下列播序算法中,时间复杂度最差的是( )
(A).选择排序
(B).桶(基數)排序
(C).快速排序
(D).堆排序

   17. 基于比较的排序算法对 n 个数进行排序的比较次数下界为( )
(A). $O(logn)$
(B). $O(m)$
(C). $O(nlogn)$
(D). $O(n^2)$

   18. 在下列存储条件下,( )是最适合使用折半查找算法来进行查找操作。
(A).顺序存储
(B).链式存储
(C).散列存储
(D),数据有序且顺序存储

   I9. 在下列算法中,求图最小生成树的算法是( )
(A). DFS 算法
(B). KMP 算法
(C). Prim 算法
(D). Dijkstra 算法

   20. 若结点的存储地址与其关键字之间存在某种映射关系,则称这种存储结构为( )
(A).顺序存储结构
(B).链式存储结构
(C).散列存储结构
(D).索引存储结构

2. 二、解答题(每题 10 分,共 50 分)

   1.假设有如图 1 所示的图

图
图 1:第二 1 题图

   (1)写出图 1 的邻接矩阵;
(2)根据邻接矩阵从顶点 a 出发进行宽度(或广度)优先遍历,面出相应的宽度优先遍历树(同一个结点的邻接结点按结点序号大小为序)。

   2.简单描述求图最小生成树的 Kruskal 算法(克鲁斯卡尔算法)的基本思想,并按步骤列出图 2 的最小生成树的求解过程。

图
图 2:第二 2 题图

   3.简单叙述快速排序的思想,在 “第一个元素为支点” 前提下按步骤列出下列序列的排序过程。
待排序的数值序列: 45 12 56 87 34 78

   4.已知有下列 13 个元索的散列表:

图
图 3:第二 4 题图

   其散列函数为 K(key) = key % m (m= 13)。处理冲突的方法为双重散列法,探查序列为:
$h_i=(h(key)+i*h(key))\%m$ $\qquad$ $i=0,1,...,m-1$ 其中: $h(key)=key\%11+1$
问:对表中关键字 35 进行查找时,所需进行的比较次数为多少?依次写出每次的计算公式和值。

   5.假设设在通信中,字符 a, b,c,d, e,,g 出现的频率如下:
a: 20% b: 7% c:16% d: 27% e:7% f 10% g: 13%
(1)根据 Huffinan 算法(赫夫曼算法)画出其赫夫曼树:
(2)给出每个字母所对应的赫夫曼编码,规定:结点左分支边上标 0,右分支边上标 1;
(3)计算其加权路径的长度 WPL.

3. 三、阅读理解题,按空白编号填写相应的 C 语言语句,以实现函数功能。(每空 2 分,每题 10 分,共 30 分)

   1.排队是日常生活中常见的一种现象,比如:在商店排队付款。当第- -位顾客完成付款离开后,其他顾客依次前移。下面用数据结构中的队列来模拟这种排队现象。

# define QUEUE
struct Queue {
    int queue[QUEUE];
    int Rear;    // Rear记录队列尾
};
(1)初始化队列 Q
void InitQueue(Queue *Q)
{
    Q->Rear=-1;
}

   (2)入队操作 EnQueue(Q, dat):若队列 Q 已满,返回 0, 否则,把数据 data 加入队列 Q,并返回 1

int EnQueue(Queue *Q, int *data)
{
    if(___(1)___) return 0;
    ____(2)____;
    Q->queue[Rear] = data;
    return 1;
}

   (3)出队操作 DeQueue(Q, dat);若队列 Q 为空,则返回 0,否则,把队头元素存入地址参数 data,然后从队列 Q 中去除该队头元素,并返回 1

int DeQueue(Queue *Q, int *data)
{
    if(Q->Rear==-1) return0;
    *data=____(3)____;
    for(i=0;i<Q->Rear;i++)  ____(4)____ ;
    ____(5)____;
    return 1;
}
这二个堆栈在某个时刻的状态如下图所示。

图
图 4:第三 1 题图

   (1)初始化堆栈

void InitStacks(Stacks *stack)
{
    stack->Top1 =___(1)___;
    stack->Top2 =___(2)___;
}
(2)堆栈 l(左堆栈)压栈操作
int push1(Stacks *stack, int data)
{
    if( __(3)__ )return 0;
    stack->Top1++;
    Elements[stack->Top1]= data;
    return 1;
}
(3)堆栈 2(右堆栈)出栈操作,并把栈顶元素的值赋给指针变量 data 所指向的存储单元
BOOL pop2(Stacks *stack, int *data)
{
    if(___(4)___)return 0;
    *data = Elements[stack-> Top2];
    ____(5)____;
    return 1;


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

                     

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