2022年广东财经大学809-数据结构硕士研究生入学考试初试自命题

适用专业：085400电子信息
[ 友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！]
一、单项选择题(10题，每题2分，共20分)
1.算法的时间复杂度取决于( )。
A.问题的规模 B.待处理数据的初态 C.计算机的配置 D.A和B
2.线性表的顺序存储结构中，数据元素的逻辑位置和物理位置的关系是( )。
A.不一致的 B.一致的 C.大致相同 D.个别元素相同
3.在一个有n个元素的顺序表中，插入一个元素平均要移动的元素个数为( )。
A.(n-1)/2 B.n/2 C.(n+1)/2 D.n
4.若顺序栈S存储在数组stack[MAXSIZE]中，栈顶位置top初值为-1，则元素e进栈的操作是( )。
A.S.stack[S.top++]=e; B.S.stack[++S.top]=e;
C.S.stack[S.top--]=e; D.S.stack[--S.top]=e;
5.链队列Q的结点结构为：(data,link)，指针front指向队首元素，rear指向队尾元素，则出队元素到变量x中的操作( )。
A.x=Q.front->data; Q.front=Q.front->link;
B.Q.front=Q.front->link; x=Q.front->link;
C.x=Q.rear->data; Q.rear=Q.rear->link;
D.x=Q.rear->data; Q.rear=Q.front;
6.一个递归算法必须包括( )。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分
7.一棵非空二叉树的先序遍历序列和中序遍历序列相同，则该二叉树一定满足( )。
A.所有的结点均无左孩子 B.所有的结点均无右孩子
C.只有一个叶子结点 D.不存在这样的二叉树
8.按照满二叉树的编号顺序对深度为k的完全二叉树编号，则编号最小的叶结点的编号是( )。
A.2k-1-1 B.2k-1 C.2k-2+1 D.2k-1
9.一棵完全二叉树的第7层有24个叶子结点，则整个二叉树的结点数至多为( )个
A.87 B.206 C.207 D.231
10.G是一个非连通无向图，共有36条边，则该图至少有( )个顶点
A.7 B.8 C.9 D.10
二、名词解释(10题，每题3分，共30分)
1、队列
2、算法的空间复杂度
3、深度优先搜索
4、最小生成树
5、有向无环图
6、关键路径
7、归并排序
8、平衡树
9、邻接矩阵
10、基数排序
三、简答题(6题，每题10分，共60分)
1、二叉树和多叉树的转换。
(1)请将如下图-1的多叉树转变为二叉树;
(2)将图-2的二叉树转变为多叉树或森林。

2、对序列{81，94，11，96，12，35，17，95，28，58，41，75，15｝中的关键字按升序排序，采用希尔排序算法，增量序列分别为5，3，1。
(1)请给出第一趟排序的结果;
(2)请给出第二趟排序的结果。
3、将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中，散列表的存储空间是一个大小为10，下标从0开始的一维数组，散列函数为：H(key)=(key×3)MOD 7，处理冲突采用线性探测法。
(1)请画出所构造的散列表。
(2)计算等概率情况下，查找成功的平均查找长度。


6、有10000个未排序的数存放在数组中，请回答以下问题。
(1)请用尽量快的方法从中找出第6000大的数。
(2)若希望尽快找出介于第3000大到第6000大之间的3000个数，又该如何操作。

2、设计一个算法，判断有向图G(采用邻接表存储)中是否存在环(cycle)。算法可以采用伪代码结合文字注释的方式说明。
3、设计一个算法，判断给定的表达式中的括号是否匹配(表达式存储在字符串或字符数组中，可能包含三种类型的括号，即( )、[ ] 和{ })。如表达式“(3+2){[a+b]*(2+x)｝”中的括号是匹配的，而表达式“(3+2)[a+b]*(2+x)｝”和“(3+2){[a+b]*(2+x｝)”中的括号是不匹配的。算法可以采用伪代码结合文字注释的方式说明。