2017年太原理工大学计算机科学与技术学院、软件学院833数据结构和计算机组成原理考研导师圈点必考题汇编
● 摘要
一、选择题
1． 某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将IP 分组正确地路由到图中所有子网，则在R1中需要増加一条路由（目的网络，子网掩码，下一跳）是（ ）。
A.192.168.2.0, 255.255.255.128, 192.168.1.1
B.192.168.2.0, 255.255.255.0, 192.168.1.1
C.192.168.2.0, 255.255.255.128, 192.168.1.2
D.192.168.2.0, 255.255.255.0, 192.168, 1, 2
【答案】D
【解析】首先从题目给出的路由表项可以确定下一跳肯定是路由器R1直接相连的R2的地址，因此是 192.168.1.2, 此时可以排除A 和B 两个选项了。进而分析路由器R2所连接的网络特点，注意其连接了 2个网络分别是192.168.2.0/25和192.168.2.128/25，但答案选项中只有一条信息，因此这里用到了超网的概念，超网是与子网类似的概念一IP 地址根据子网掩码被分为独立的网络地址和主机地址。但是，与子网把大网络分成若干小网络相反，它是把一些小网络组合成一个大网络——超网，这里192.168.2.00000000/25和192.168.2.10000000/25 前24位是相同的，因此所构成的超网就是192.168.2.0/24，那么子网掩码就是255.255.255.00000000即 255.255.255.0, 因此答案是 D 。
2． 在系统总线的数据线上，不可能传输的是（ ）。
A. 指令
B. 操作数
C. 握手（应答）信号
D. 中断类型号型号
【答案】C
【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
3． 内部异常（内中断）可分为故障（fault ）、陷讲（trap ）和终止（abort ）三类。下列有关内部异常的叙述中，错误的（ ）。
A. 内部异常的产生与当前执行指令相关
B. 内部异常的检测由CPU 内部逻辑实现
C. 内部异常的响应发生在指令执行过程中
D. 内部异常处理后返回到发生异常的指令继续执行
【答案】D
【解析】内中断分为：①由软中断指令启动的中断；②在一定条件下由CPU 自身启动的中断。D 项错误，如突然掉电引发的内中断经处理后不会继续执行。
4． 下列选项中，不可能在用户态发生的事件是（ ）。
A. 系统调用
B. 外部中断
C. 进程切换
D. 缺页
【答案】C 。
【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设
，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现）
运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制
，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻）
是在内核态（进程调度）发生的。
5． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
【答案】D
6． 一个C 语言程序在一台32位机器上运行。程序中定义了3个变量x 、Y 和z ，其中x 和z 为int 型，Y 为short 型。当x=127，Y=-9时，执行赋值语句z=x+Y后，x 、Y 和z 的值分别是（ ）。
A.x=0000007FH, Y=FFF9H, z=00000076H
B.x=0000007FH, Y=FFF9H, z=FFFF0076H
C.x=0000007FH, Y=FFF7H, z=FFFF0076H
D.x=0000007FH, Y=FFF7H, z=00000076H
【答案】D
【解析】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”。例如，x 和z 为int 型，数据长32位，Y 为short 型，数据长16位，因此首先应将y 转换成32位的数据，然后再进行加法运算。运算采用补码的形式，而x 的补码是0000007FH , Y 的补码是FFFFFFF7H , 所以x+Y=00000076H。
7． 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先
【答案】B
【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个? 我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到 调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有尚响应比优先算法。
8． 希尔排序的组内排序采用的是（ ）。
A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 归并排序
【答案】A
【解析】希尔排序基本思想是：先将整个待排元素序列按某个增量分割成若干个子序列，在子序列内进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
9． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。
A.
B.
C.