2022年中北大学计算机与控制工程学院821数据结构与算法之数据结

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

第 1 页，共 74 页

目录

2018年中北大学计算机与控制工程学院821数据结构与算法之数据结构考研核心题库（一） 2 2018年中北大学计算机与控制工程学院821数据结构与算法之数据结构考研核心题库（二）

.............................................................................................................................................. 18 2018年中北大学计算机与控制工程学院821数据结构与算法之数据结构考研核心题库（三）

.............................................................................................................................................. 31 2018年中北大学计算机与控制工程学院821数据结构与算法之数据结构考研核心题库（四）

.............................................................................................................................................. 43 2018年中北大学计算机与控制工程学院821数据结构与算法之数据结构考研核心题库（五）

(59)

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

第 2 页，共 74 页 2018年中北大学计算机与控制工程学院821数据结构与算法之数据结构考研核心题

库（一）

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

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

一、单项选择题

1． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。

A.选择排序法

B.插入排序法

C.快速排序法

D.堆排序法

【答案】A

【解析】选择排序的基本思想是:

第i 趟排序开始时，当前有序区和无序区分别为和，该趟排序则是从当前无序区中选出关键字最小的记录

，将它与无序区的第1个记录R[i]交换，使和分别变为新的有序区和新的无序区。

2． 先序序列为a ,b ,c ,d 的不同二叉树的个数是（ ）。

A.13

B.14

C.15

D.16

【答案】B

【解析】二叉树的先序遍历定义为:若二叉树为空,则空操作;否则,访问根节点,然后先序遍历左子树,最后先序遍历右子树。本题中,结点a 为二叉树的根节点,左右子树的先序遍历可能存在下面四种情况:

①左子树为空,bcd 为右子树;②b 为左子树,cd 为右子树;③bc 为左子树,d 为右子树;④bcd 为左子树,右子树为空。

然后将左右子树继续分解,如第①种情况的右子树先序遍历(bcd)可能有:

A.左子树为空,右子树为cd ;

b.左子树为c ,右子树为d ;

c.左子树为cd ,右子树为空。

按照这种方法继续分解左右子树,直到不能再分解为止,可得第①和④种情况各包含5种不同情况,第②和③种情况各包含2种情况,因此总共有14种不同的二叉树。

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

第 3 页，共 74 页 3． 假设某计算机的存储系统由Cache 和主存组成.某程序执行过程中访存1000次，其中访问Cache 缺失(未命中)50次，则Cache 的命中率是（ ）.

A.5%

B.

C.50%

D.95%

【答案】D

【解析】Cache 的命中率H ＝N 1(N 1＋N 2)，其中N 1为访问Cache 的次数，N 2为访存主存的次数，程序总访存次数为N 1＋N 2，程序访存次数减去失效次数就是访问Cache 的次数队.所以根据公式可得：H ＝(1000﹣50) /100＝95%.

4． 设有数组A[i ，j]，数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（ ）。

A.BA+141

B.BA+180

C.BA+222

D.BA+225

【答案】B

【解析】在计算中，可以考虑按照列存放时，A[5，8]在内存的位置，比较容易计算元素的首地址。比如A[5，8]顺序存放时，它是第7*8＋5＝61个元素，由于首地址为BA ，所以它的存储首地址为BA ＋(61﹣1)*3＝180+BA 。

5． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。

A.4

B.5

C.6

D.7

【答案】C

【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个(n ＞0)结点的完全二叉树的高度为或由完全二叉树类推到完全三叉树可知，n 个结点的完全三叉树的高度为

或》

6． 下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。

A.二叉排序树

B.哈夫曼树

C.A VL 树

D.堆

【答案】D

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

第 4 页，共 74 页 【解析】堆的定义:

n 个关键字序列K 1，K 2，...，K n 称为堆，当且仅当该序列满足如下性质(简称为堆性质):

(1)

且或

(2)

且

满足第(1)种情况的堆，称为小顶堆；满足第(2)种情况的堆，称为大顶堆。

由堆的定义可知堆可以满足上述性质。

7． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。

A.N

B.2N －1

C.2N

D.N －1

【答案】A

【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O(n)。

8．

操作系统的

子系统通常由四个层次组成,每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（ ）。 A.用户级

软件、设备无关软件、设备驱动程序、中断处理程序 B.用户级

软件、设备无关软件、中断处理程序、设备驱动程序 C.用户级

软件、设备驱动程序、设备无关软件、中断处理程序 D.用户级

软件、中断处理程序、设备无关软件、设备驱动程序 【答案】A 。

【解析】对于一次设备的调用,操作系统为用户准备了系统调用的接口,当用户使用设备时,首先在用户程序中发起一次系统调用,操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理,根据调用格式和形参,再转到相应的设备驱动程序去处理;大部分设备在运行时是需要时间的,所以设备驱动程序会以中断方式驱动设备,即设置好控制寄存器参数和中断向量等参数后阻塞自己;当设备准备好或所需数据到达后设备硬件发出中断,设备驱动程序唤醒,将数据按上述调用顺序逆向回传到用户程序中,或继续驱动设备执行下一条指令。因此,软件从上到下分为四个层次:用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。

9． 某磁盘的转速为10,000转/分,平均寻道时间是6ms ,磁盘传输速率是,磁盘控制器延迟

为,读取一个4KB 的扇区所需平均时间约为（ ）

A.9ms

B.

C.12ms

D.

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