2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研强化模拟题
● 摘要
目录
2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研强化模拟题（一） ... 2 2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研强化模拟题（二） ... 8 2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研强化模拟题（三） . 15 2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研强化模拟题（四） . 21 2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研强化模拟题（五） . 27
一、填空题
1． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
2． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
3． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
4． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
5． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
．已
知
求REPLACE （S ，V , m ）=_____。
【答案】
其中
队头和队尾指针分别为front 和rear , 则此循
6
7． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
8． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
9． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
10．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
11．如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为
12．深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】 13．
【答案】5
14．数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
15．在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
=_____
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
二、选择题
16．—个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms 到达。它们的计算和P1:计算60ms ，作顺序如下：
计算
计算
计算
虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。
A.240ms B.260ms C.340ms D.360ms
【答案】B 。
【解析】考查处理系统的性能计算，由于P2比PI 晚5ms 到达，PI 先占用CPU ，根据PI 和P2的执行过程，作业运行的甘特图如下所示，故答案为B 。
操若不考
17．某数采用IEEE754单精度浮点数格式表示为C640 0000H, 则该数的值是（ ）
A. B. C. D. 【答案】A
IEEE754单精度浮点数格式为C640 0000H表示为二进制格式为1100 0110 0100 0000 【解析】
0000 0000 0000 0000, 转换为标准的格式为：
. 因此，浮点数的值为
18．下列有关接口的叙述中错误的是：（ ）
A. 状态端口和控制端口可以合用同一寄存器 B.
接口中CPU 可访问寄存器，称为
端口
端口
指令，
C. 采用独立编址方式时，【答案】D
【解析】采用统一编码方式，存储器和任何对存储器数据进行操作的指令都可用于
端口共用统一的地址空间，不需要专用的端口的数据操作。所以D 错误
端口地址和主存地址可能相同
D. 采用统一编址方式时，CPU 不能用访存指令访问