1、数据结构与操作系统试卷 第1页 共 7 页 一、 一、 单项选择题：140 小题，每小题 2 分，共 80 分。在每小题给出的选项中，请选出一项最符合题目要求的。单项选择题：140 小题，每小题 2 分，共 80 分。在每小题给出的选项中，请选出一项最符合题目要求的。 1下列排序算法中，平均时间复杂度最小的是（ ） 。 A归并排序 B起泡排序 C简单选择排序 D直接插入排序 2关于线性表的描述正确的是（ ） 。 A采用顺序存储时，其存储地址必须是连续的 B采用链式存储时，其存储地址必须是连续的 C采用顺序存储时，其存储地址一定是不连续的 D采用链式存储时，其存储地址一定是不连续的 3往队列中输
2、入序列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 层） ，则这棵完全二叉树的结点个数最少有（ ） 。 A7 B11 C23 D28 6有 20 个结点的无向图，关于其描述正确的是（ ） 。 A只要 10 条边就能确
3、保它是一个连通图 B至少要有 20 条边才能确保它是一个连通图 C至少要有 19 条边才能确保它是一个连通图 D至少要有 21 条边才能确保它是一个连通图 7下列说法中错误的是（ ） 。 A有向图的邻接矩阵不一定是对称矩阵 B. 无向图的邻接矩阵不一定是对称矩阵 C若图 G 的邻接矩阵是对称的，则 G 不一定是无向图 D若图 G 的邻接矩阵是对称的，则 G 不一定是有向图 8若对已经有序的数据序列进行再次排序，则下列算法中时间复杂度最小的是（ ） 。 A归并排序 B简单选择排序 C堆排序 D冒泡排序 9一个有序数据序列中有 15 个数据，采用二分查找法在其中查找一个数据，最多要比较几次就能得到
4、查找结果（ ） 。 A4 B 5 C1 D15 数据结构与操作系统试卷 第2页 共 7 页 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; AO(2n) B0(log2n) C0(n2) DO(n) 11. 图 1 所示这棵树的中序遍历结果是（ ） 。 ADBAECF B. ABCDEF C. DBACEF D. DBAEFC BCADEF
5、图 1.树 12. 设有一个顺序栈 S，元素 s1， s2， s3， s4， s5， s6 依次进栈，如果 6 个元素的出栈顺序为 s2， s3， s4， s6， s5， s1，则顺序栈的容量至少应为( )。 A. 6 B. 5 C. 4 D.3 13. 在有 16 个节点的二叉排序树中查找一个数据，下列描述正确的是（ ） 。 A最多只要比较 5 次就可以得到结果 B可能要比较 16 次才能得到结果 C最多只要比较 4 次就可以得到结果 D必须比较 15 次才能得到结果 14. 若数据序列 12, 78, 5, 64, 96, 23, 49 是采用下列方法之一得到的第一趟排序后的结果，则该排序
6、算法是（ ） 。 A冒泡排序 B直接插入排序 C快速排序 D归并排序 15. 对数据 7，3，9，2，5 进行排序时，第一趟的排序结果如下： 5，3，2，7，9； 数据结构与操作系统试卷 第3页 共 7 页 则采用的排序算法是（ ） 。 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 的插入顺
7、序构造的查找树的查找效率最高 D查找效率与构造查找树时插入数据的顺序无关 17. 已知一个数据序列中有 10 个数据，且其已经有序排列，若采用最快的查找算法和必要的存储结构，在该序列中要查找一个数据元素，则平均比较次数最少要多少次（ ） 。 A10 B. 5 C. 4 D. 1 18. 一棵满二叉树共有 4 层（树根为第一层） ，则叶子节点个数为（ ） 。 A. 15 B. 16 C. 8 D. 7 19. 若要检查源代码文件中的括号是否匹配， 采用的数据结构应该是 （ ） 。 A 图 B. 二叉树 C. 栈 D. 队列 20. 假设某快递公司每天要用 1 辆车去 100 个地方送货，为尽量减
8、少行车里程，节省汽油，需要事先规划好送货路线，请问该选用什么样的数据结构（ ） 。 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. 在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲
9、区合并，为此需修改空闲区表，造成空闲区数减 1 的情况是( ) A.无上邻空闲区，也无下邻空闲区 B.有上邻空闲区，但无下邻空闲区 C.有下邻空闲区，但无上邻空闲区 D.有上邻空闲区，也有下邻空闲区 25.下面关于操作系统主要功能描述不正确的是（ ） A. 算法效率管理 B. 存储器管理 C. 文件管理 D. 处理机管理 数据结构与操作系统试卷 第4页 共 7 页 26.在请求页式存储管理中，若所需内容不在内存中，则会引起( )。 A. 输入输出中断 B. 缺段中断 C. 越界中断 D. 缺页中断 27.以下不是设备分配算法的是（ ） A. 先来先服务 B. 短作业优先 C. 优先级高的优先
10、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
11、. 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,195 32. 在通过索引分配技术时，若某一文件的索引块如下图所示： 11 6 2 8 9 -1 -1 请问，该索引文件大小共占有（ ）块？ A. 4 B. 7 C. 6 D. 5 33. 在基本分页存储管理中，若采用最近最少使用（LRU）页面置换算法，则当进程分配到的物理块数目增加时，产生缺页中断的次数（ ） A. 一定减少 B. 一定增加 C. 无影响 D
12、.可能增加也可能减少 34. 设置当前工作目录的主要目的是（ ） 。 A. 节省外存空间 B. 节省内存空间 C. 加快文件的检索速度 D. 加快文件的读/写速度 35. 某基于动态分区存储管理的计算机，其主存容量为 55MB(初始为空闲)，采用最坏适应分配（Worst Fit）算法，分配和释放的顺序为：分配 15MB,数据结构与操作系统试卷 第5页 共 7 页 分配30MB,释放15MB,分配8MB,分配6MB,此时主存中最大空闲分区的大小是( )。 A. 7MB B. 9MB C. 10MB D. 8MB 36. 某计算机系统中有 K 台打印机，由 4 个进程竞争使用，每个进程最多需要 3
13、 台打印机。该系统不可能发生死锁的 K 的最小值是（ ） 。 A. 10 B. 9 C. 8 D. 5 37. 采用 SPOOLing 技术的目的是（ ） 。 A. 提高独占设备的利用率 B. 提高主机效率 C. 减轻用户编程负担 D. 提高程序的运行速度 38考虑以下页表结构： 页号 块号 0 3 1 4 2 1 3 7 假设页的大小为1K, 即页内地址长度为 10 位，请把以下以十六进制表示的逻辑地址0 x967，通过页表转换为物理地址（也用十六进制表示）是 （ ）。 A. 0 x3417 B. 地址转换错误 C. 0 x367 D. 0 x567 39. 在操作系统中， （ ）不是它所关
14、心的问题。 A. 管理计算机裸机（硬件资源） B. 高级程序设计语言的编译 C. 管理计算机中的信息资源 D. 设计、提供用户程序与计算机硬件系统的接口 40. 对两个并发进程，其互斥信号量为 mutex；初值为 1，若 mutex0，则表明（ ） 。 A没有进程进入临界区 B有一个进程进入临界区但还没有进程处于阻塞状态 C一个进程进入临界区而另一个进程正处于等待进入临界区状态 D有两个进程进入临界区 二、 综合应用题：4145 小题，共 70 分。 二、 综合应用题：4145 小题，共 70 分。 41.带有头节点的单链表，其节点结构为 数据结构与操作系统试卷 第6页 共 7 页 Data
15、next 假设有单链表 L（指向头节点的指针）,示意图如下图所示 a1a2a3a4headerNULL 请设计一个算法对单链表进行排序，要求： （1） 请描述算法的基本设计思想（5 分） （2） 描述算法的详细实现步骤（5 分） （3） 根据设计思想和实现步骤， 采用某一程序设计语言描述算法 （使用 C 或 C+） ，关键之处请给出简要注释。 （5 分） （4） 请采用某一程序设计语言写一个函数，其功能是：在单链表头部插入新节点。 （5 分） （5） 请采用某一程序设计语言写一个函数，其功能是：在单链表尾部删除节点。 （5 分） 42. 二叉查找树如图 2 所示， 图 2.二叉查找树 （1）请
16、画出删除关键字为 E 的节点后的二叉查找树（5 分） （2）请写出中序遍历二叉树的算法（使用 C 或 C+） （5 分） （3）请写出前序遍历二叉树的算法（使用 C 或 C+） （5 分） AEBCGFD数据结构与操作系统试卷 第7页 共 7 页 43. （10 分）在银行家算法中，若出现下述资源分配情况(5 个进程，3 类资源)： process Allocation（已分配） MAX（最大需求） Available（系统资源） A B C A B C A B C P1 0 1 3 2 1 9 1 2 2 P2 3 2 2 3 9 7 P3 0 2 2 2 5 4 P4 0 2 3 0 4
17、4 P5 1 0 0 1 4 5 试问： （1）(6 分) 该状态是否安全？若是，请给出安全序列,要求写出详细推导过程。若不是，也请说明具体原因。 （要求：回答安全状态与否均要求写出具体推导过程） （2） （4 分）若 P3 提出请求 Request(0，0，2)后，系统能否将资源分配给它？为什么？（能和不能均要求写出各自的详细理由） 。 44.(10 分) 考虑下述页面走向： 4，3，2，1，4，3，5，4，3，2，1，5 当内存物理块数量分别为 3 和 43 和 4 时， 试问先进先出 FIFO、 最佳页面算法 OPT这两种置换算法的缺页次数和置换次数分别是多少？要求写出各自详细的缺页置换
18、过程。最后，就上述两种算法的产生缺页结果，简单说说你能从中有何发现？ 45. (10 分)完成程序: 假定系统有三个并发进程为 in, outA 和 outB，它们共享缓冲器 buf(容量为 1)。约定：仅当缓冲器空时，进程 in 才可以把读入的数据放入 （PUT） 到缓冲器 buf 中。 仅当 buf 有数据且该数为奇数时，进程 outA 才可从缓冲器 buf 中取出(GET)数据并打印，若数据为偶数，则由 outB 从缓冲器 buf 中取出(GET)数据并打印，要求上述三个进程协调完成该任务，请用信号量 WAIT 和 SIGNAL 操作写出它们的并发程序；假设开始时，缓冲器为空。 【完】
