2020年大连理工大学管理与经济学部810数据结构和计算机组成原理之数据结构考

时间：2025-05-11

考研专业课资料、辅导、答疑一站式服务平台

第 1 页，共 41 页

2020年大连理工大学管理与经济学部810数据结构和计算机组成原理之数据结构考研核心题库

（一） ..................................................................................................................................... 2 2020年大连理工大学管理与经济学部810数据结构和计算机组成原理之数据结构考研核心题库

（二） ..................................................................................................................................... 9 2020年大连理工大学管理与经济学部810数据结构和计算机组成原理之数据结构考研核心题库

（三） ................................................................................................................................... 18 2020年大连理工大学管理与经济学部810数据结构和计算机组成原理之数据结构考研核心题库

（四） ................................................................................................................................... 26 2020年大连理工大学管理与经济学部810数据结构和计算机组成原理之数据结构考研核心题库

（五） (33)

考研专业课资料、辅导、答疑一站式服务平台

第 2 页，共 41 页 2020年大连理工大学管理与经济学部810数据结构和计算机组成原理之数据结构考

研核心题库（一）

特别说明：

1-本资料为2020考研考研复习使用，精选汇编了该科目历年常考核心试题，精题精练。

2-资料仅供考研复习参考，与目标学校及研究生院官方无关，如有侵权、请联系我们立即处理。

一、单项选择题

1．有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612

B.453126

C.346521

D.234156

【答案】C

【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出枝。

2．在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（）。

A.O(1)

B.O(N)

C.O(N 2)

【答案】B

【解析】二分查找的时间复杂度为。在一个用N 个元素的有序单链表中查找具有给定

关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为0(N)。

3．有n(n ＞0)个分支结点的满二叉树的深度是（）。

A.n 2﹣l

B.log 2(n ＋1) ＋1

C.log 2(n ＋1)

D.log 2(n —1)

【答案】C

【解析】满二叉树的结点总数＝分支的结点总数＋非分支的结点总数。由于此树为满二叉树，

所以非分支的结点总数为1，所以满二叉树共有n ＋1个结点，所以满二叉树的深度为log 2 (n ＋1)。

4．

对个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中,错误的是（）。

A.该树一定是一棵完全二叉树

考研专业课资料、辅导、答疑一站式服务平台

第 3 页，共 41 页 B.树中一定没有度为1的结点

C.树中两个权值最小的结点一定是兄弟结点

D.树中任一非叶结点的权值一定不小于下一层任一结点的权值

【答案】A

【解析】哈夫曼树为带权路径长度最小的二叉树,但不一定是完全二叉树,选项A 错误;哈夫曼树中没有度为1的结点,选项B 正确;构造哈夫曼树时,最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树,C 正确;哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和,其权值不小于其左右子树根结点的权值,在与结点P 的左右子树根结点处于同一层的结点中,若存在权值大于结点P 权值的结点Q ,那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树,由此可知,哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。

5．若X 是后序线索二叉树中的叶结点,且X 存在左兄弟结点Y ,则X 的右线索指向的是（）

A.X 的父结点

B.以Y 为根的子树的最左下结点

C.X 的左兄弟结点Y

D.以Y 为根的子树的最右下结点

【答案】A

【解析】根据后续线索二叉树的定义,X 结点为叶子结点且有左兄弟,那么这个结点为右孩子结点,利用后续遍历的方式可知X 结点的后继是其父结点,即其右线索指向的是父结点。

6．下列排序算法中，占用辅助空间最多的是（）。

A.归并排序

B.快速排序

C.希尔排序

D.堆排序