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

                     

贡献者: xzllxls

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

   1.算法复杂度通常是表达算法在最坏情况下所需要的计算量,$O(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[)][m]为一个对称矩阵,数组下标从[0[0)开始.为了节省存储,将其下三角部分按行存放在一维数组 B0.m-1], m=n(n+1)2, 对下三角部分中任一元素 4.fi≥D, 它在一-维数组 B 的下标 k 值是( )
(A). i(i-1)/2+j
(B). (-1)2+j-1
(C). (i+1)/2+j-1
(D). i(+1)2+j

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

   11. 若一棵二叉树的后序和中序序列分别是 dbefca 和 dbaef,则其先序序列是( )
(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). HCLTree)- H(RTree) < 1
(C). H(LTree) - H(RTree) <= 1
(D). H(LTree) - H(RTree) <= 1

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

   15. 用邻接矩阵存储有 n 个顶点和 e 条边的有向图,则删除与某个顶点相邻的所有边的时间复杂度是()
(A). $O(n)$
(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).数据有序且顺序存储

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

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

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

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

图
图 1:第二 1 题图

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

图
图 2:第二 2 题图

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

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

图
图 3:第二 4 题图

   其散列函数为 h(key)=key%m (m=13),处理冲突的方法为双重散列法,探查序列为:
$h=(h(key)+i*(key)\%m$ $\qquad$ $i=0.1.... m-1$, 其中:$h'(key)=key\%11+1$
间:对表中关键字 35 进行查找时,所需进行的比较次数为多少?依次写出每次的计算公式和值.s.假设设在通信中,字符 a, b,c,d, e,,g 出现的频率如下:
a:20% b: 7% $\quad$ c:16% $\quad$ d: 27% e: 7% $\quad$ f: 10% $\quad$ g: 13(1)根据 Huffman 算法(赫夫曼算法)画出其赫夫曼树:
(2)给出每个字母所对应的赫夫曼编码,规定:结点左分支边上标 0,右分支边上标 I;
(3)计算其加权路径的长度 WPL.

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

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

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

   (2)入队操作 EnQueu(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) return 0;
    *data=___ (3)___;
    for(i=0; i<Q->Rear; i++) __ (4)__;
    __(5)__;
    return 1;
}

   2.假设有两个堆栈共享一个存储空间,其有关定义如下:

#define SIZE 50
struct Stacks {
    int Elements[SIZE];
    int Topl, Top2;    //Top1和Top2分别记录二个栈的栈顶
};
这二个堆栈在某个时刻的状态如下图所示.

图
图 4:第三 2 题图

   (1)初始化堆栈

void InitStacks(Stacks *stack)
{
    stack->Topl = ____ (1)___;
    stack->Top2 = ____ (2)___;
}
(2)堆栈 1(左堆栈)压栈操作
int pushl(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;
}

   3.假设二叉树 $T= < T_L,root,T_R > $ 的深度定义如下:
$Depth(T)= \left\{\begin{aligned} &0, & T\text{是空树} \\ &1, & T\text{的根结点是叶结点} \\ & max(Depth(TL), Depth(TR)) & \text{其他} \end{aligned}\right. $
已知二叉树的结点定义如下:

struct BNode {
    int Key;
    struct BNode *LChild, *RChild;
};
函数 Depth(root)是求以结点 root 为根的二叉树深度.
int Depth(BNode *root)
{
    int dl, d2;
    if(root==__(1)__) return 0;
    if(___(2)___) return 1;
    d1=____(3)____;
    d2=____(4)____;
    return(___(5)___?d1:d2);
}

4. 四、算法设计题(每题 15 分,共 30 分)

   用 C 语言或类 C 语言实现下面函数的功能.

   1.假设用链表表示集合,集合链表的结点定义如下:

struct Set {
    int element;
    struct Set next
};
例如: A={2.1,3},B=, 集合 A 和 B 的存储形式如下图所示.

图
图 5:第四 1 题图

   试实现集合的下列二个操作: (1) Set Intersection(Set *A, Set *B),其功能是返回集合 A 和 B 交集的首结点地址(10 分)
(2) int Cardinality(Set *A),其功能是返回集合 A 中的元素个数,即:求|AI (5 分)
例如有下列语句:

Set *A, *B, *C;
int NumC;
......    //集合A和B的值由其它集合操作获得
C = Intersection(A, B);    //C=A交B
NumC = Cardinality(C);     // NumC=|C|

   2.已知二叉树的结点定义如下:

struct BNode {
    int Key;
    struct BNode *LChild, *RChild;
};
编写函数 TraveralByLeve(BNode *ro0), 其功能是 “按层” 遍历以结点 roo 为根的二叉树,并输出每个结点中 Key 的信息.
在函数描述中可直接使用下列队列功能(如果需要的话,仅供参考)
Queue:队列类型定义符
InitQueue(Queue *Q):初始化队列Q为空队列
EnQueue(Queue *Q, BNode *node);:把指针node入队列Q
BNode *DeQueue(Queue *Q):若队列Q为空,则返回NULL,否则,返回队头元素,并从队列Q中删除该队头元索
int QueueEmpty(Queue *Q):若队列Q为空,则返回1,否则,返回0


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

                     

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