广东财经大学809数据结构2022年考研真题
2024-10-28
999+
637.06KB
4 页
侵权投诉
欢迎报考广东财经大学硕士研究生，祝你考试成功！（第 1 页 共 4 页）
1
广东财经大学硕士研究生入学考试试卷
考试年度：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、关键路径
欢迎报考广东财经大学硕士研究生，祝你考试成功！（第 2 页 共 4 页）
2
7、归并排序
8、平衡树
9、邻接矩阵
10、基数排序
三、简答题（6题，每题10分，共60分）
1、二叉树和多叉树的转换。
（1）请将如下图-1 的多叉树转变为二叉树；
（2）将图-2 的二叉树转变为多叉树或森林。
A
C
FE
DB
G
H
I
A
E
D
C F
B
图-1 图-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）计算等概率情况下，查找成功的平均查找长度。
4、对于图-3 的AVL树（平衡树），依次插入关键字35，28。
（1）请画出插入关键字35 后AVL树的形状。
（2）请画出随后再插入关键字28 后AVL树的形状。
80
92704010
98906020
9550
30
图-3
5、给定图G的邻接表如图-4 所示。
摘要：
展开>>
收起<<
欢迎报考广东财经大学硕士研究生，祝你考试成功！（第1页共4页）1广东财经大学硕士研究生入学考试试卷考试年度：2022年 考试科目代码及名称：809-数据结构（自命题）适用专业：085400电子信息［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！］一、单项选择题（10题，每题2分，共20分）1.算法的时间复杂度取决于（）。A.问题的规模B.待处理数据的初态C.计算机的配置D.A和B2.线性表的顺序存储结构中，数据元素的逻辑位置和物理位置的关系是（）。A.不一致的B.一致的C.大致相同D.个别元素相同3.在一个有n个元素的顺序表中，插入一个元素平均要移动的元素个数为（）。...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
