DOC《一、单项选择题（每小题2分,共60分）》

180 假设磁头当前位于100道,现有一个磁道访问请求序列为45,12,68,110,180,170,35,95.采用最短寻道时间优先调度(SSTF)算法得到的磁道访问序列是( ). A. 95,110, 170, 180, 68, 45, 35,

12 B. 45, 12, 68, 110, 180, 170,35,

95 C. 110, 170, 180, 95, 12, 35, 45,

68 D. 12, 35, 45, 68, 95,110, 170,

180 假设磁头当前位于100道,正在向磁道序号增加的方向移动.现有一个磁道访问请求序列为45,12,68,110,180,170,35,95.采用扫描调度(SCAN)算法得到的磁道访问序列是( ). A. 95,110, 170, 180, 68, 45, 35,

12 B. 45, 12, 68, 110, 180, 170, 35,

95 C. 110, 170, 180, 95, 68,45,35,

12 D. 110, 170, 180, 12,35,45,68,

95 假设某一机器的内存有4G,硬盘为200G,请问使用虚拟内存技术后,其虚拟内容的容量为( ) A. 4G B. 8G C. 200G D. 204G 在基本分页存储管理中,若采用最佳页面置换算法OPT,则当进程分配到的物理块数目增加时,缺页中断的次数( ) A. 可能减少,也可能不变 B.一定减少 C. 不变 D.一定增加 设置当前工作目录的主要目的是( ). A. 节省外存空间 B. 节省内存空间 C. 加快文件的检索速度 D. 加快文件本身的读/写速度 考虑以下表1结构: 表1 页号 块号

0 3

1 2

2 4

3 1 假设页的大小为512字节( 即页内地址长度为9位),请把以下以十六进制表示的逻辑地址0x965,通过页表转换为物理地址(也用十六进制表示)是(). A. 0xA65 B. 地址转换错误 C. 0x965 D. 0x765 空闲链表法可用于( ) A.文件的空闲盘块组织 B.磁盘的设备调度 C.CPU调度算法 D.请求分页虚拟管理中的页面置换 基本分页内存管理系统中,访问一条指令需要几次访问内存( )? A.

3 B.

0 C.

1 D.

2 对于某个活动进程而言,其运行的场所必须在( )中. A. 内存 B. 硬盘 C. SWAPING交换区 D. 输入井或输出井 下列算法中用于磁盘调度的是( ) A. 最近最少使用LRU算法 B. FIFO算法 C. 时间片轮转法RR D. 循环扫描算法(CSCAN) 在I/O设备管理中,通道是一种( ). A.I/O端口 B.设备控制器 C. I/O专用处理机 D.软件工具 进程从阻塞状态进入就绪状态的原因可能是( ) A. 时间片用完 B. 正等待某一事件发生 C. 被选中占有处理机 D. 等待的事件已发生(或完成)

二、综合应用题(共90分). 31.(25分)把数据序列{73,23,44,99,21,78}依次插入到二叉查找树中, (5分)请画出最终的二叉查找树 (5分)请写出:上一步完成后,二叉查找树的后序遍历结果 (15分)请在下列编程语言中选择任意一种(C、C++、Java),写出 中序遍历二叉查找树的函数,函数的输入参数为树根结点,结点类型 需要自己定义. 32.(25分)把数据序列{73,23,44,99,21,78}放入表长为7的散列(哈希)表中,散列函数h(x)=x % 7,用双散列(二次散列Double Hashing)探测法解决冲突,探测函数为f(i)= i * (

7 C x %

7 ),在依次插入数据时,用上述探测法解决冲突,会碰到始终无法解决冲突的情况,即无法为新数据找到合适的存放位置,这时需要进行重散列(Rehashing),请完成以下问题. (5分)请画出重散列前的散列表 (5分)重散列时,请写出合理的新散列表的长度、散列函数(但探 测函数不变) (5分)请画出重散列后的散列表 (5分)请写出:在上一步散列表上查找成功情况下的平均比较次数. (5分)如果同样的数据序列放在链表中,请写出查找成功情况下的 平均比较次数. 33.(10分)在银行家算法中,若出现下述资源分配情况(5个进程,3类资源): Process Allocation(已分配),MAX(最大需求),Available(系统剩余资源) A B C A B C A B C P1