2018年甘肃省培养单位近代物理研究所862计算机学科综合(非专业)

专注考研专业课13年，提供海量考研优质文档！

第 1 页，共 72 页

目录

2018年甘肃省培养单位近代物理研究所862计算机学科综合（非专业）之数据结构考研核心题

库（一） .................................................................................................................................. 2 2018年甘肃省培养单位近代物理研究所862计算机学科综合（非专业）之数据结构考研核心题

库（二） ................................................................................................................................ 17 2018年甘肃省培养单位近代物理研究所862计算机学科综合（非专业）之数据结构考研核心题

库（三） ................................................................................................................................ 31 2018年甘肃省培养单位近代物理研究所862计算机学科综合（非专业）之数据结构考研核心题

库（四） ................................................................................................................................ 44 2018年甘肃省培养单位近代物理研究所862计算机学科综合（非专业）之数据结构考研核心题

库（五） (58)

专注考研专业课13年，提供海量考研优质文档！

第 2 页，共 72 页 2018年甘肃省培养单位近代物理研究所862计算机学科综合（非专业）之数据结构考

研核心题库（一）

说明：本套核心题库按照考试大纲、历年真题、指定参考书等结合考试侧重点和难度，精心整理编写。核心题库更突出针对性和实战性，考研冲刺必备资料。

——————————————————————————————————————————

一、填空题

1． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

2． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。

【答案】比较；移动

3． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间.复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】O(1)；O(n)

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

4． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N －1)个非零元素。

5． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，

要加“虚结点”。

设编号为i 和j 的结点在顺序存储中的下标为s 和t ,则结点i 和j 在同一层上的条件是

。

6． 在哈希函数中，p 值最好取_____。 【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

专注考研专业课13年，提供海量考研优质文档！

第 3 页，共 72 页

7． 阅读下列程序说明和程序，填充程序中的_____。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。

本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:

(1)把根结点放入堆栈。

(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。

(3)重复(2)直到堆栈为空时为止。

【答案】 【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。

8． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】

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

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

10．假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素

在B 中的存储位置k ＝_____。(注:矩阵元素下标从1开始)

【答案】93

【解析】对于上三角矩阵，k ＝(i ﹣l)(2n ﹣i ＋2)/2＋(j ﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。

二、单项选择题

专注考研专业课13年，提供海量考研优质文档！

第 4 页，共 72 页 11．现在有一颗无重复关键字的平衡二叉树(A VL 树),对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中,正确的是（ ）。

A.根节点的度一定为2

B.树中最小元素一定是叶节点

C.最后插入的元素一定是叶节点

D.树中最大元素一定是无左子树

【答案】D

【解析】二叉树的中序遍历定义是“若二叉树为空,则空操作;否则:

①中序遍历左子树;②访问根节点;③中序遍历右子树”。

A 项错误,当树中仅有一个或者两个结点时,根节点的度就可能不为2;

B 项错误,树中最小元素是中序遍历时最后访问的节点,当没有右子树时,最后访问的节点是根节点;

C 项错误,当最后插入的元素破坏树的平衡后,树会进行调整,使其成为中间节点;

D 项正确,由中序遍历的特点可知,左子树的值大于根节点,所以最大元素一定没有左子树。

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

A.c 和e

B.d 和e

C.f 和d

D.f 和h

【答案】C

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

13．以下说法错误的是（ ）。

(1)算法原地工作的含义是指不需要任何额外的辅助空间

(2)在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度O(2n )的算法

(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

(4)同一个算法，实现语言的级别越高，执行效率就越低

A.(1)

B.(1),(2)

C.(1),(4)