2018年浙江理工大学理学院965软件基础之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 设系统缓冲区和用户工作均采单, 从外读入1个数据块到系统缓冲区的时间为100, 从系统缓冲区读入1个数据块到用户工作区的时间为5, 对用户工作区中的1个数据块行分析的时间为90(如下图所示) 。进程从外设读入并分析2个数据块的最短时间是（ ）
图
A.200
B.295
C.300
D.390
【答案】C
【解析】数据块1从外设到用户工作区的总时间为105, 在这段时间中数据块2没有进行操作。在数据块1进行分析处理时, 数据块2从外设到用户工作区的总时间为105, 这段时间是并行的。再加上数据块2进行处理的时间90, 总共是300, 故答案为C 。
2． 下列关于银行家算法的叙述中, 正确的是（ ）
A. 银行家算法可以预防死锁
B. 当系统处于安全状态时, 系统中一定无死锁进程
C. 当系统处于不安全状态时, 系统中一定会出现死锁进程
D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件
【答案】B
【解析】银行家算法是避免死锁的方法。利用银行家算法, 系统处于安全状态时没有死锁进程, 故答案选B 。
3． 下列介质访问控制方法中, 可能发生冲突的是（ ）
A.CDMA
B.CSMA
C.TDMAC
D.FDMA
【答案】B
【解析】介质访向控制协议中能够发生冲突的是CSMA 协议, 答案为B 。
4． 在含有n 个关键字的小根堆(堆顶元素最小) 中，关键字最大的记录有可能存储在（ ）位置上。 A. B.
C.1 D.
【答案】D
【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于Ln/2」的结点上。
5． 下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA
B.CDMA C. D.
【答案】D
【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。
6． 下列选项中, 满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先
【答案】B
【解析】分析该题目可以看到, 本题所提到的问题是涉及短任务调度也就是属于作业调度, 因此首先排除时间片轮转算法; 因为作业调度算法中没有时间片轮转的算法。其次, 因为问题提到短任务, 则先来先服务的算法也可以排除了, 它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个？我们可以通过分析得到, 非抢占式短任务优先算法不能解决饥饿问题, 因为当一个系统短任务源源不断到达是, 长任务必然会得不到调度, 产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法, 并以高响应比值优先调度。这样, 无论短任务或长任务, 均可以得到调度, 而且, 较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有高
响应比优先算法。
7． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列, 能属于同一棵哈夫曼树的是（ ）。
A.24, 10, 5和24, 10, 7
B.24, 10, 5和24, 12, 7
C.24, 10, 10和24, 14, 11
D.24, 10, 5和24, 14, 6
【答案】D
【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中, 第二个被访问的两个结点的权值要么相等, 要么和为根节点的权值, 故B 项错误。同理, 通过第三个被访问的节点排除A 项。C 项, 由两条路径可推出三个叶子节点的权值分别是:3、10和11, 而根据哈夫曼树的定义可知, 权值为3的节点应该和权值为10的结点结合, 故C 项错误。D 项, 反推出有四个叶子节点, 权值分别为:5、5、6和8, 满足哈夫曼树的条件。
8． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1, 则该平衡二叉树的结点总数为（ ）。
A.12
B.20
C.32
D.33
【答案】B 。
【解析】本题的实际问题是, 具有6层结点的平衡二叉树含有最少的结点数是多少。
深度为h 的平衡二叉树中含有的最少结点数, 有
由此可得。对应的平衡二叉树如下图所示。
表示
9． 下列各类存储器中, 不采用随机存取方式的是（ ）。
A.EPROM
B.CDR0M
C.DRAM
D.SRAM
【答案】B