2017年山西财经大学计算机应用技术814数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 某网络的IP 地址空间为采用定长子网划分，子网掩码为则该网络的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）。
A.32, 8
B.32, 6
C.8, 32
D.8, 30
【答案】B
【解析】子网号为5位，在CIDR 中可以表示个子网，主机号为3位，除去全0和全1的情况可以表示6个主机地址，答案为B 。
2． 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先
【答案】B
【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个? 我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到 调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有尚响应比优先算法。
3． 设无向图的顶点个数为m 则该图最多有（ ）条边。
A.n-1
B.n （n-l ）/2
C.n （n+l）/2
D.0
E.n2
【答案】B
【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。
因此边数最多时，构成的是无向完全图。此时的边数为n （n-l ）/2。
4． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257
B.258
C.384
D.385
【答案】C
【解析】由
：
_
则和
__可知
，
即显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
5． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
【答案】A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语句
6． 对给定的关键字序列110, 119, 007, 911，114，120, 122进行基数排序，则第2趟分配收集后得到的关键字序列是（ ）
A.
B.
C.
D.
【答案】C
，则有设其执行时间为T （n ）
【解析】基数排序的第1趟排序是按照个位数字来排序的，第2趟排序是按然十位数字的大小进行排序的，故答案是C 选项。
7． 设与某资源相关联的信号量初值为3, 当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。
A.0、1
B.1、0
C.1、2
D.2、0
【答案】B
【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。
8． 某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，
把一个磁盘块读人缓冲区的时间为
传送到用户区的时间是CPU 对一块数据进行分析的时间为
构下，读人并分析完该文件的时间分别是（ ）。
A.
B.
C.
D.
【答案】B
【解析】这是一个简单的缓冲区的问题。由于缓冲区的访问是互斥的，所以对单一缓冲区，从磁盘写入和读 出到用户区的操作必须串行执行，也就是要保证互斥操作。而CPU 对数据的分析与从用户区读数据也是需要互斥操作，但是CPU 分析与从磁盘写入缓冲区的操作可以并行。从本题看，由于分析所用的时间小于从磁盘写入 缓冲区的时间，因此，CPU 会空闲。单缓冲区的总时间=（磁盘写入缓冲区时间+缓冲区读出时间
）处理最后一块数据的时
间
当采用双缓冲区时，每块缓冲区的操作也必须满足互斥操作，但是，
对两块缓冲区的操作却可以并行，所以，当第一个缓冲区写满以后，磁盘紧接着写另一个缓冲区，
同时，前一个已经满了的缓冲区被读出到用户区，并立即进行CPU 的数据分析。读出操作和数据分析必须互斥进行，故从时间上看，当数据被读出并分析后，恰好另一个缓冲区也写满了，可以立即进行读出数据到用户区并 进行数据分析。两块缓冲区交替进行读写，直到数据分析完毕，因此，总时间=（磁盘写入缓冲区时间）读出最后一块数据时间+CPU分析最后一块数据时间
=
9． 知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。
A.CBEFDA
B.FEDCBA
C.CBEDFA
D. 不定
【答案】A
【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。
将缓冲区的数据，在单缓冲区和双缓冲区结
相关内容
相关标签