2018年武汉工程大学计算机科学与工程学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、判断题
1． 在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
【答案】√
【解析】堆排序:基本思想先将原始序列构造成一个堆(初始堆) ，使其n 个元素的最大(小) 值处于序列的第 —个位置；然后交换序列第一个元素与最后一个元素的位置。
2． AOE 网一定是有向无环图。（ ）
【答案】×
【解析】在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称这种有向图表示活动的网络，简称为AOE 网。因此对AOE 网是否是有向无环图没有要求。
3． 堆是满二叉树。（ ）
【答案】×
【解析】堆的定义:
n 个关键字序列
①②且且 称为堆，当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆；
大根堆:满足第②种情况的堆。
因此并不能保证堆是满二叉树。
4． 稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）
【答案】 √
【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。
5． m 阶B 树的任何一个结点的左右子树的高度都相等。（ ）
【答案】√
【解析】由B 树的性质得知，叶子结点都处于同一层。因此，m 阶B 树的任何一个结点的左右子树的高度都相等。
6． 两个长度不相同的串有可能相等。（ ）
【答案】 ×
【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。
二、单项选择题
7． 主机甲和主机乙间已建立一个TCP 连接，主机甲向主机乙发送了两个连续的TCP 段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 主机乙正确接收到两个段后，发送给主机甲的确认序列号是（ ）。
A.500
B.700
C.800
D.1000
【答案】D
【解析】TCP 使用滑动窗口流控协议，窗口大小的单位是字节，本题中分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 那么确认序列号为200＋300＋500＝1000。
8． 某设备中断请求的相应和处理时间为100ns , 每400ns 发出一次中断请求, 中断相应所容许的最长延迟时间为50ns , 则在该设备持续工作过程中CPU 用于该设备的
分比至少是（ ） A. B. C. D.
【答案】B
【解析】每400ns 响应一次中断并且用100ns 进行处理, 所以该设备的时间占用CPU 时间百分比为100/400=25%, 中断响应容许的延迟时间对此没有影响, 属于干扰条件。
9． 下列调整中, 不可能导致饥饿现象的是（ ）
A. 时间片转移
B. 静态优先及调度
C. 非抢占式作业优先
D. 抢占式短作业优先
【答案】A
【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间, 不会产生饥饿的现象, 其余三个都会产生饥饿。
时间占整个CPU 时间百
10．哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
【答案】D
11．在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
【答案】D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为:双亲表示法、孩子链表示法、孩子兄弟表示法。
12．，某基于动态分区存储管理的计算机，其主存容量为55MB(初始为空闲）采用最佳适配(BestFit)算法，分配和释放的顺序为:分配15MB 、分配30MB 、释放15MB 、分配8MB 、分配6MB ，此时主存中最大空闲分，区的大小是（ ）.
A.7MB
B.9MB
C.10MB
D.15MB
【答案】B
【解析】对于简单分区内存分配，需要将进程的所有代码和数据装入内存. 故55MB 先分配15MB 余40MB ，再分配30MB 后余10MB ，释放15MB 后出现一个15MB 和一个10MB 的空闲空间，分配8MB 时按最佳适配(BestFit)算法应该使用10MB 的空闲块，余2MB 的碎片，分配6MB 时占用15MB 的空间余9MB 的碎片(空闲空间），因此最大空闲区为9MB.
13．静态链表中指针表示的是（ ）。
A. 下一元素的地址
B. 内存储器的地址
C. 下一元素在数组中的位置
D. 左链或右链指向的元素的地址
【答案】C
相关内容
相关标签