2020年浙江大学人文学院408计算机学科专业基础综合之数据结构考研核心题库

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

第 1 页，共 76 页

目录

2020年浙江大学人文学院408计算机学科专业基础综合之数据结构考研核心题库（一） (2)

2020年浙江大学人文学院408计算机学科专业基础综合之数据结构考研核心题库（二） (18)

2020年浙江大学人文学院408计算机学科专业基础综合之数据结构考研核心题库（三） (33)

2020年浙江大学人文学院408计算机学科专业基础综合之数据结构考研核心题库（四） (48)

2020年浙江大学人文学院408计算机学科专业基础综合之数据结构考研核心题库（五） (63)

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

第 2 页，共 76 页 2020年浙江大学人文学院408计算机学科专业基础综合之数据结构考研核心题库

（一）

特别说明：

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

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

一、单项选择题

1． 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。

A.必定快

B.不一定

C.在大部分情况下要快

D.取决于表递增还是递减

【答案】C

【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。

2． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）

A.G 的邻接多重表需要n(n －1)个边结点和n 个顶点结点

B.G 的连通分量个数最少

C.G 为连通图

D.G 所有顶点的度的总和为n(n —1)

【答案】A

【解析】

A 项中G 的邻接多重表中需要个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n －1，则

n 个结点的度的总和为n(n －1)。

3． 下列排序算法中，其中（ ）是稳定的。

A.堆排序，起泡排序

B.快速排序，堆排序

C.直接选择排序，归并排序

D.归并排序，起泡排序

【答案】D

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

第 3 页，共 76 页 4． 设桟S 和队列Q 的初始状态为空，元素el ，e2，e3，e4，e5和e6依次通过栈S ，一个元素出栈后即进队列Q ，若6个元素出队的序列是e2，e4，e3，e6，e5，el ，则栈S 的容量至少应该是（ ）。

A.6

B.4

C.3

D.2

【答案】C

5． 已知三叉树T 中6个叶结点的权分别是2,3,4,5,6,7,T 的带权(外部)路径长度最小是（ ）

A.27

B.46

C.54

D.56

【答案】B

【解析】利用三叉树的6个叶子结点的权构建最小带权生成树,最小的带权路径长度为

6．

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

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

B.树中一定没有度为1的结点

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

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

【答案】A

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

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

第 4 页，共 76 页 7． 下列AOE 网表示一项包含8个活动的工程。通过同时加快若干进度可以缩短整个工程的工期。下列选项中,加快其进度就可以缩短工程工期的是（ ）

A.c 和e

B.d 和e

C.f 和d

D.f 和h

【答案】C

【解析】根据AOE 网的定义可知,同时缩短几条关键路径上的活动期间,可以缩短整个工期。

8． 在下列表述中，正确的是（ ）

A.含有一个或多个空格字符的串称为空格串

B.对n(n ＞0)个顶点的网，求出权最小的n ﹣1条边便可构成其最小生成树

C.选择排序算法是不稳定的

D.平衡二叉树的左右子树的结点数之差的绝对值不超过1

【答案】C

【解析】平衡二叉树的左右子树的深度之差的绝对值不超过1。求最小生成树时，每次挑最小权值边，是要求该边的两点都在不同的连通分量上的。

9． 用有向无环图描述表达式，至少需要顶点的数目为（ ）。

A.5

B.6

C.8

D.9

【答案】A

【解析】一共5个结点，6条边。

10．用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移动的操作为（ ）。

A.j ＝r[j].next

B.j ＝j ＋l

C.j ＝j ﹣＞next

D.j ＝r[j]﹣＞next

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

第 5 页，共 76 页

【答案】A

【解析】因为是用数组存储，这里所说的工作指针j 相当于数组的下标，结点是存储一个值域和next 域，next 域就是存放下一个结点的下表，所以只要将next 域中的值赋给j 就可以实现j 沿链移动。

二、填空题

11．n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注:(1)图的顶点号从0开始计；

(2)indegree 是有n 个分量的一维数组，放顶点的入度， (3)函数crein 用于记算顶点入度； (4)有三个函数其含义为数据data 入栈，出栈和测试栈是否空(不空返

回1，否则0)。

("图有回路");

【答案】

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

12．阅读下列程序，指出其功能，并写出空格处应填上的语句。

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

第 6 页，共 76 页

【答案】

【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。

13．如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】

【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为

。

14．已知一循环队列的存储空间为，其中n ＞m ，队头和队尾指针分别为front 和rear ，

则此循环队列判满的条件是_____ 【答案】

15．—棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为_____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

16．表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。 【答案】(表达式中的点(.)是数分隔符，如是三个数)

17．起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32,则其伙伴块的起始地址为_____;。

【答案】480+8=488，480－32=448

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:

根据上述公式起始地址就为488。

18．在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ；栈底；两栈顶指针相邻(即值之差的绝对值为1)

三、判断题

本文来源：https://www.bwwdw.com/article/j54e.html