2017年河北大学计算机科学与技术学院862数据结构(计)考研冲刺密押题
● 摘要
一、选择题
1． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A.0（nlogn ）
B.O （logn ）
C.O （n ） D.
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为0（nlogn ）。
已知待排序的n 个元素可分为个组，每个组包含k 个元素，且任一组内的各元素均分别大干前一
2． 设有一棵3阶B 树，如题图所示。删除关键字78得到一棵新B 树，其最右叶结点所含的关键字是（ ）。
题图二叉树图
A.60
B.60, 62
C.62, 65
D.65
【答案】D 。
【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于则需将其兄弟结点中最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下，其最右叶结点所含的关键字是65。
3． 偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是（ ）。
A. 间接寻址
B. 基址寻址
C. 相对寻址
D. 变址寻址
【答案】A
【解析】在四种不同的寻址方式中，间接寻址按指令的形式地址从主存中取出操作数的有效地址，然后再按此有效地址从主存中读出操作数。其余三种寻址方式可以统称为偏移寻址。
4． 使用浏览器访问某大学Web 网站主页时，不可能使用的协议是（ ）
A.PPP
B.ARP
C.UDP
D.SMTP
【答案】D
【解析】SMTP 是简单邮件传输协议，访问主页时并不涉及邮件相关协议。
5． 在有向图G 的拓扑序列中，若顶点V i 在顶点V j 之前，则下列情形不可能出现的是（ ） 。
A.G 中有弧
C.G 中没有弧 【答案】D 【解析】若想实现图的一个拓扑排序，需要满足的一个条件为：若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从V j 到V i 的路径，则在拓扑序列中V i 不可能在V j 前。 6． 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。 A. 逻辑设备名 B. 物理设备名 C. 主设备号 D. 从设备号 【答案】A 【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻 辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作系统内部管理设备使用的是设备编号。 7． 若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（ ）。 A. 在进程结束时能进行处理机调度 B. 创建新进程后能进行处理机调度 C. 在进程处于临界区时不能进行处理机调度 D. 在系统调用完成并返回用户态时能进行处理机调度 【答案】C 。 【解析】对于A 、B 、D 显然是可以进行处理机调度的，对于C , 当进程处于临界区时，只要不破坏临界资源的使用规则，是不会影响处理机调度的，比如，通常访问临界资源可能是慢速的 ，如果在进程访问打印机时，不能处理机调度，那么系统的性能将是非常低的。外设（如打印机） 几种不进行处理机调度的情况如下：①在处理机中断的过程中；②进程在操作系统内核程序临界区中；③其他需要完全屏蔽中断的原子操作过程中。 8． 下列选项中，不可能在用户态发生的事件是（ ）。 A. 系统调用 B. 外部中断 C. 进程切换 D. 缺页 【答案】C 。 【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设 ，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现） 运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制 ，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻） 是在内核态（进程调度）发生的。 9． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。 A. 前序遍历 B. 中序遍历 C. 后序遍历