2022年北京市培养单位光电研究院866计算机原理之数据结构考研基

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

第 1 页，共 58 页

目录

2018年北京市培养单位光电研究院866计算机原理之数据结构考研基础五套测试题（一） ... 2 2018年北京市培养单位光电研究院866计算机原理之数据结构考研基础五套测试题（二） . 13 2018年北京市培养单位光电研究院866计算机原理之数据结构考研基础五套测试题（三） . 26 2018年北京市培养单位光电研究院866计算机原理之数据结构考研基础五套测试题（四） . 36 2018年北京市培养单位光电研究院866计算机原理之数据结构考研基础五套测试题（五） . 47

专注考研专业课13年，提供海量考研优质文档！ 第 2 页，共 58 页 2018年北京市培养单位光电研究院866计算机原理之数据结构考研基础五套测试题

（一）

说明：根据本校该考试科目历年考研命题规律，结合出题侧重点和难度，精心整理编写。基础检测使用。共五套试题，均含有详细答案解析，也是众多专业课辅导机构参考借鉴资料，考研必备。 ——————————————————————————————————————————

一、填空题

1． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，

而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n 2)。

2． 已知有序表为(12，18，24，35，47，50，62，83，90，115，134)当用二分法查找90时，需次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。

【答案】2;4;3

【解析】二分法查找元素次数列表

查找100是找到115就停止了。

3． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l)，则a 85的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则的地址为l ＋2＋... ＋i ﹣l ＋j ＝i(i ﹣l)/2＋j 。若i ＜j 。则的地址为j(j ﹣l)/2＋i 。将i ＝8，j ＝5代入得33。

4． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。

【答案】2(n －1)

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。

5． 在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____;若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。 【答案】

【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少

专注考研专业课13年，提供海量考研优质文档！ 第 3 页，共 58 页 6． 已知一循环队列的存储空间为

，其中n ＞m ，队头和队尾指针分别为front 和rear ，则此循环队列判满的条件是_____ 【答案】

7．

给定一组数据

以它构造一棵哈夫曼树，则树高为_____，带权路径长度

WPL 的值为_____。

【答案】5；96 【解析】每次找两个最小的权值构建哈夫曼树:

8． 二进制地址为011011110000,大小为和块的伙伴地址分别为:_____ 【答案】011011110100；011011100000

【解析】011011110000是块的起始地址，大小分别为和其伙伴块的起始地址计算公式如下:

当大小为4时，起始地址为011011110000+0100。当大小为16时，起始地址为:011011110000-010000。

9． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】

【解析】哈夫曼树只有度为0和2的节点。

10．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____；而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；(动态)链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

二、判断题

专注考研专业课13年，提供海量考研优质文档！ 第 4 页，共 58 页 11．取线性表的第i 个元素的时间同i 的大小有关。（ ）

【答案】 ×

【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是O(1)。

12．哈希函数越复杂越好，因为这样随机性好，冲突概率小。（ ）

【答案】×

【解析】随机性好和冲突概率小跟哈希函数的复杂程度无关，是根据具体情况而定的，跟实际的数据有很大关系。

13．在链队列中，即使不设置尾指针也能进行入队操作。（ ）

【答案】 √

【解析】因为存在头指针，根据链表的性质，根据头指针可以找到为指针。

14．负载因子(装填因子)是哈希表的一个重要参数，它反映哈希表的装满程度。（ ）

【答案】√

【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素:哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。

15．两个长度不相同的串有可能相等。（ ）

【答案】 ×

【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。

16．不同的求最小生成树的方法最后得到的生成树是相同的。（ ）

【答案】×

【解析】对于一个带权连通无向图G=(V ，E),生成树不同，每棵树的权也可能不同。若生成树T 上的所有边的权值之和最小，则T 称为G 的最小生成树。因此可以看出，最小生成树不是唯一的，最小生成树的权值之和总是唯一的。

17．无环有向图才能进行拓扑排序。（ ）

【答案】√

【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。

18．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（ ）

【答案】√

【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所以该图的拓扑有序序列必定存在。

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