Microsoft Word A3.doc

Transcription

1 一 单项选择题 :1~40 小题, 每小题 2 分, 共 80 分 在每小题给出的 选项中, 请选出一项最符合题目要求的 1. 下列排序算法中, 平均时间复杂度最小的是 ( ) A. 归并排序 B. 起泡排序 C. 简单选择排序 D. 直接插入排序 2. 关于线性表的描述正确的是 ( ) A. 采用顺序存储时, 其存储地址必须是连续的 B. 采用链式存储时, 其存储地址必须是连续的 C. 采用顺序存储时, 其存储地址一定是不连续的 D. 采用链式存储时, 其存储地址一定是不连续的 3. 往队列中输入序列 {1,2,3,4}, 则关于输出序列描述正确的是 ( ) A. 输出序列的第一个元素是 4 B. 输出序列为 4321 C. 输出序列不确定 D. 输出序列的最后一个元素是 4 4. 往栈中输入序列 {1,2,3,4}, 则关于输出序列描述正确的是 ( ) A. 输出序列的第二个元素是 2 B. 输出序列肯定是 4321 C. 输出序列可能是 1234 D. 输出序列的最后一个元素是 1 5. 已知一棵完全二叉树的第 4 层有 4 个叶子结点 ( 树根为第 1 层 ), 则这 棵完全二叉树的结点个数最少有 ( ) A.7 B.11 C.23 D 有 20 个结点的无向图, 关于其描述正确的是 ( ) A. 只要 10 条边就能确保它是一个连通图 B. 至少要有 20 条边才能确保它是一个连通图 C. 至少要有 19 条边才能确保它是一个连通图 D. 至少要有 21 条边才能确保它是一个连通图 7. 下列说法中错误的是 ( ) A. 有向图的邻接矩阵不一定是对称矩阵 B. 无向图的邻接矩阵不一定是对称矩阵 C. 若图 G 的邻接矩阵是对称的, 则 G 不一定是无向图 D. 若图 G 的邻接矩阵是对称的, 则 G 不一定是有向图 8. 若对已经有序的数据序列进行再次排序, 则下列算法中时间复杂度最小 的是 ( ) A. 归并排序 B. 简单选择排序 C. 堆排序 D. 冒泡排序 9. 一个有序数据序列中有 15 个数据, 采用二分查找法在其中查找一个数 据, 最多要比较几次就能得到查找结果 ( ) A.4 B. 5 C.1 D.15 数据结构与操作系统 试卷第 1 页共 7 页

2 10. 在下面的 C 语言程序段中, 除法操作的时间复杂度为 ( ) int n,fac=1; float x, p=1.0f, result=0; scanf( %f%d,&x,&n); for( i=0; i < n; ++i) { p /= x; fac *= i+1; result += fac / p; } A.O(2n) B.0(log 2 n) C.0(n 2 ) D.O(n) 11. 图 1 所示这棵树的中序遍历结果是 ( ) A.DBAECF B. ABCDEF C. DBACEF D. DBAEFC A B C D E F 图 1. 树 12. 设有一个顺序栈 S, 元素 s1, s2, s3, s4, s5, s6 依次进栈, 如果 6 个元素的出栈顺序为 s2, s3, s4, s6, s5, s1, 则顺序栈的容量至少应为 ( ) A. 6 B. 5 C. 4 D 在有 16 个节点的二叉排序树中查找一个数据, 下列描述正确的是 ( ) A. 最多只要比较 5 次就可以得到结果 B. 可能要比较 16 次才能得到结果 C. 最多只要比较 4 次就可以得到结果 D. 必须比较 15 次才能得到结果 14. 若数据序列 12, 78, 5, 64, 96, 23, 49 是采用下列方法之一得到的第一趟排序后的结果, 则该排序算法是 ( ) A. 冒泡排序 B. 直接插入排序 C. 快速排序 D. 归并排序 15. 对数据 7,3,9,2,5 进行排序时, 第一趟的排序结果如下 : 5,3,2,7,9; 数据结构与操作系统 试卷第 2 页共 7 页

3 则采用的排序算法是 ( ) A. 冒泡排序 B. 直接插入排序 C. 快速排序 D. 归并排序 16. 把数据 1,2,3,4,5,6,7 通过插入操作构造一棵二叉查找树时, 下 列描述正确的是 ( ) A. 按照 1,2,3,4,5,6,7 的插入顺序构造的查找树的查找效率最 高 B. 按照 7,6,5,4,3,2,1 的插入顺序构造的查找树的查找效率最 高 C. 按照 4, 2, 1, 3, 6, 5, 7 的插入顺序构造的查找树的查找效率最 高 D. 查找效率与构造查找树时插入数据的顺序无关 17. 已知一个数据序列中有 10 个数据, 且其已经有序排列, 若采用最快的 查找算法和必要的存储结构, 在该序列中要查找一个数据元素, 则平 均比较次数最少要多少次 ( ) A.10 B. 5 C. 4 D 一棵满二叉树共有 4 层 ( 树根为第一层 ), 则叶子节点个数为 ( ) A. 15 B. 16 C. 8 D 若要检查源代码文件中的括号是否匹配, 采用的数据结构应该是 ( ) A. 图 B. 二叉树 C. 栈 D. 队列 20. 假设某快递公司每天要用 1 辆车去 100 个地方送货, 为尽量减少行车里 程, 节省汽油, 需要事先规划好送货路线, 请问该选用什么样的数据结 构 ( ) A. 线性表 B. 图 C. 队列 D. 二叉树 21. 以下不是操作系统基本特性的是 ( ) A. 并发性 B. 并行性 C. 虚拟性 D. 异步性 22. 假设某一机器的内存有 2G, 硬盘为 500G, 请问使用虚拟内存技术后, 其虚 拟内存的容量为 ( ) A. 2G B. 4G C. 502G D.500G 23. 进程从运行状态进入阻塞状态的原因可能是 ( ) A. 被选中占有处理机 B. 等待某一事件发生 C. 等待的事件已发生 D. 时间片用完 24. 在可变式分区分配方案中, 某一作业完成后, 系统收回其主存空间, 并 与相邻空闲区合并, 为此需修改空闲区表, 造成空闲区数减 1 的情况是 ( ) A. 无上邻空闲区, 也无下邻空闲区 B. 有上邻空闲区, 但无下邻空闲区 C. 有下邻空闲区, 但无上邻空闲区 D. 有上邻空闲区, 也有下邻空闲区 25. 下面关于操作系统主要功能描述不正确的是 ( ) A. 算法效率管理 B. 存储器管理 C. 文件管理 D. 处理机管理 数据结构与操作系统 试卷第 3 页共 7 页

4 26. 在请求页式存储管理中, 若所需内容不在内存中, 则会引起 ( ) A. 输入输出中断 B. 缺段中断 C. 越界中断 D. 缺页中断 27. 以下不是设备分配算法的是 ( ) A. 先来先服务 B. 短作业优先 C. 优先级高的优先 28. 位示图方法可用于 ( ) A. 磁盘空闲空间的管理 B. 磁盘的驱动调度 C. 文件目录的查找 D. 页式虚拟存贮管理中的页面调度 29. 下列算法中用于磁盘调度的是 ( ) A. 扫描 (SCAN) 算法 B. LRU 算法 C. 时间片轮转法 RR D. 优先级高者优先算法 30. 通道是一种 ( ) A. I/O 端口 B. 数据通道 C. I/O 专用处理机 D. 软件工具 31. 假设磁头当前位于 105 道, 正在向磁道序号增加的方向移动 现有一个磁 道访问请求序列为 35,45,12,68,110,180,170,195, 采用最短寻道 时间优先 SSTF 调度算法得到的磁道访问序列是 ( ) A. 110,170,180,195,68,45,35,12 B. 110,68,45,35,12,170,180,195 C. 110,170,180,195,12,35,45,68 D. 12,35,45,68,110,170,180, 在通过索引分配技术时, 若某一文件的索引块如下图所示 : 请问, 该索引文件大小共占有 ( ) 块? A. 4 B. 7 C. 6 D 在基本分页存储管理中, 若采用最近最少使用 (LRU) 页面置换算法, 则 当进程分配到的物理块数目增加时, 产生缺页中断的次数 ( ) A. 一定减少 B. 一定增加 C. 无影响 D. 可能增加也可能减少 34. 设置当前工作目录的主要目的是 ( ) A. 节省外存空间 B. 节省内存空间 C. 加快文件的检索速度 D. 加快文件的读 / 写速度 35. 某基于动态分区存储管理的计算机, 其主存容量为 55MB( 初始为空闲 ), 采用最坏适应分配 (Worst Fit) 算法, 分配和释放的顺序为 : 分配 15MB, 数据结构与操作系统 试卷第 4 页共 7 页

5 分配 30MB, 释放 15MB, 分配 8MB, 分配 6MB, 此时主存中最大空闲分区的大小是 ( ) A. 7MB B. 9MB C. 10MB D. 8MB 36. 某计算机系统中有 K 台打印机, 由 4 个进程竞争使用, 每个进程最多需 要 3 台打印机 该系统不可能发生死锁的 K 的最小值是 ( ) A. 10 B. 9 C. 8 D 采用 SPOOLing 技术的目的是 ( ) A. 提高独占设备的利用率 B. 提高主机效率 C. 减轻用户编程负担 D. 提高程序的运行速度 38. 考虑以下页表结构 : 页号 块号 假设页的大小为 1K, 即页内地址长度为 10 位, 请把以下以十六进制表示的逻辑地 址 0x967, 通过页表转换为物理地址 ( 也用十六进制表示 ) 是 ( ) A. 0x3417 B. 地址转换错误 C. 0x367 D. 0x 在操作系统中,( ) 不是它所关心的问题 A. 管理计算机裸机 ( 硬件资源 ) B. 高级程序设计语言的编译 C. 管理计算机中的信息资源 D. 设计 提供用户程序与计算机硬件系统的接口 40. 对两个并发进程, 其互斥信号量为 mutex; 初值为 1, 若 mutex=0, 则表明 ( ) A. 没有进程进入临界区 B. 有一个进程进入临界区但还没有进程处于阻塞状态 C. 一个进程进入临界区而另一个进程正处于等待进入临界区状态 D. 有两个进程进入临界区 二 综合应用题 :41~45 小题, 共 70 分 41. 带有头节点的单链表, 其节点结构为 数据结构与操作系统 试卷第 5 页共 7 页

6 Data next 假设有单链表 L( 指向头节点的指针 ), 示意图如下图所示 header a1 a2 a3 a4 NULL 请设计一个算法对单链表进行排序, 要求 : (1) 请描述算法的基本设计思想 (5 分 ) (2) 描述算法的详细实现步骤 (5 分 ) (3) 根据设计思想和实现步骤, 采用某一程序设计语言描述算法 ( 使用 C 或 C++), 关键之处请给出简要注释 (5 分 ) (4) 请采用某一程序设计语言写一个函数, 其功能是 : 在单链表头部插入新节点 (5 分 ) (5) 请采用某一程序设计语言写一个函数, 其功能是 : 在单链表尾部删除节点 (5 分 ) 42. 二叉查找树如图 2 所示, B A E C F D G 图 2. 二叉查找树 (1) 请画出删除关键字为 E 的节点后的二叉查找树 (5 分 ) (2) 请写出中序遍历二叉树的算法 ( 使用 C 或 C++)(5 分 ) (3) 请写出前序遍历二叉树的算法 ( 使用 C 或 C++)(5 分 ) 数据结构与操作系统 试卷第 6 页共 7 页

7 43. (10 分 ) 在银行家算法中, 若出现下述资源分配情况 (5 个进程,3 类资 源 ): process Allocation( 已分配 ) MAX( 最大需求 ) Available( 系统资源 ) A B C A B C A B C P P P P P 试问 : (1)(6 分 ) 该状态是否安全? 若是, 请给出安全序列, 要求写出详细推 导过程 若不是, 也请说明具体原因 ( 要求 : 回答安全状态与否均要求写 出具体推导过程 ) (2)(4 分 ) 若 P3 提出请求 Request(0,0,2) 后, 系统能否将资源分配给它? 为什么?( 能和不能均要求写出各自的详细理由 ) 44.(10 分 ) 考虑下述页面走向 : 4,3,2,1,4,3,5,4,3,2,1,5 当内存物理块数量分别为 3 和 4 时, 试问先进先出 FIFO 最佳页面算法 OPT 这两种置换算法的缺页次数和置换次数分别是多少? 要求写出各自详细的缺页置换过程 最后, 就上述两种算法的产生缺页结果, 简单说说你能从中有何发现? 45. (10 分 ) 完成程序 : 假定系统有三个并发进程为 in, outa 和 outb, 它们共享缓冲器 buf( 容量为 1) 约定: 仅当缓冲器空时, 进程 in 才可以把读入的数据放入 (PUT) 到缓冲器 buf 中 仅当 buf 有数据且该数为奇数时, 进程 outa 才可从缓冲器 buf 中取出 (GET) 数据并打印, 若数据为偶数, 则由 outb 从缓冲器 buf 中取出 (GET) 数据并打印, 要求上述三个进程协调完成该任务, 请用信号量 WAIT 和 SIGNAL 操作写出它们的并发程序 ; 假设开 始时, 缓冲器为空 完 数据结构与操作系统 试卷第 7 页共 7 页