2017年济南大学信息科学与工程学院847计算机学科专业基础综合之数据结构考研题库
● 摘要
一、选择题
1． 假定有4个整数用8位补码分别表示为
存放在一个8位寄存器中，则下列运算会发生溢出的是（ ）。
A.r1×r2 B.r2×r3 C.r1×r4 D.r2×r4 【答案】B
【解析】用补码表示时8位寄存器所能表示的整数范围为
在4个选项中，只有
都未超过127, 不发生溢出。
2． 下列选项中，不可能在用户态发生的事件是（ ）。
A. 系统调用 B. 外部中断 C. 进程切换 D. 缺页 【答案】C 。
【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现）
运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻）是在内核态（进程调度）发生的。
3． 希尔排序的组内排序采用的是（ ）。
A. 直接插入排序 B. 折半插入排序
若将运算结果
现在4个整数都是负数
，结果溢出，其余3个算式结果
C. 快速排序 D. 归并排序 【答案】A
【解析】希尔排序基本思想是：先将整个待排元素序列按某个增量分割成若干个子序列，在子序列内进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
4． 一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。
A.11 B.12 C.13 D.14
【答案】B
5． 对于循环队列（ ）。
A. 无法判断队列是否为空 B. 无法判断队列是否为满 C. 队列不可能满 D. 以上说法都不是 【答案】D
【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断：①另设一个布尔变量来区别队列是空还是满；②队满时，（rear+1）==font。
6． 在缺页处理过程中，操作系统执行的操作可能是（ ）。
I. 修改页表 II. 磁盘I/O III. 分配页框 A. 仅 I 、II B. 仅II C. 仅III D.I 、II 和III 【答案】D
【解析】首先我们要考虑的是，为什么会发生缺页中断? 当然，在一个采用虚拟存储管理技术的系统中，程 序是部分装入的，还有部分是处于外存上的，因此，当需要访问那部分位于外存上的代码或数据时，系统会产生 缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存，据此，缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页（若没有空闲的页面则要调用页面置换程序找到一处页 面，将该页面的内容处理掉，或回写
，分配妥当以后，缺页中断处理程序调用设备磁盘，或覆盖掉，然后将此页分配给需要访问的页）
驱动程序做磁盘1/0, 将位于外存（一般是磁盘）上的页面调入内存，调入后转身去修改 页表，将，将物理页表中代表该页是否在内存的标志位（一般称为存在位或有效位、在位位）修改为“真”页框号填入相应位置，若必要还需修改其它相关表项等。完成上述任务后，缺页中断处理程序返 回，继续程序的执行。 从上述过程可以看出，涉及的相关处理非常多，因此，答案就显而易见了。
7． 在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性 B. 功能特性 C. 过程特性 D. 电气特性 【答案】C 。
【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以 分析描述事件先后顺序的就是规程，也就是过程特性，答案是C 。
8． 假定用若干个2Kx4位的芯片组成一个8Kx8位的存储器，则地址0B1FH 所在芯片的最小地址是（ ）。
A.0000H B.0600H C.0700H D.0800H 【答案】D
【解析】由若干芯片构成存储器，采用字和位同时扩展方法。8片2Kx4位的芯片分成4组，每组2个芯片，各组芯片的地址分配分别为：第1组，0000H 〜07FFH ; 第2组，0800H 〜0FFFH ; 第3组，1000H 〜17FFH ; 第4组，1800H 〜1FFFH 。地址0BIFH 处于第2组内，其芯片的最小地址为0800H 。
9． 在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37 所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48
相关内容
相关标签