1、数据结构与操作系统试卷 第1页 共 8 页 一、 单项选择题：140 小题，每小题 2 分，共 80 分。在每小题给出的四个选项中，请选出一项最符合题目要求的。 一、 单项选择题：140 小题，每小题 2 分，共 80 分。在每小题给出的四个选项中，请选出一项最符合题目要求的。 1. 在下面的 C 语言程序段中，加法操作的时间复杂度为（ ）。 int i, j, k, sum = 0; for( i=0; i n; +i) for( j=0; j i*i; +j) sum+; A(2n2) B(2n3) C(n3) D(n2) 2. 关于线性表的描述正确的是（ ）。 A访问顺序表中第 k 个元
2、素的时间复杂度是(N) B访问单链表中第 k 个节点的时间复杂度是(N) C把新数据插入到顺序表中第 k 个位置的时间复杂度是(1) D把新数据插入到单链表中第 k 个位置的时间复杂度是(1) 3. 关于队列描述正确的是（ ）。 A用链表表示队列时，也不可以插队（插队指在队列中间插入新数据） B用环形数组表示队列时，可以循环使用数组，所以队列永远不会满 C用数组表示队列时，数据入队的时间复杂度是(N) D用数组表示队列时，数据出队的时间复杂度是(N) 4. 关于栈描述正确的是（ ）。 A. 数据进出栈的原则是“先入先出” B. 用数组表示栈时，栈的操作速度要比用链表表示的栈操作快 C. 用单链
3、表表示栈时，出栈与入栈的时间复杂度是(N) D. 用数组表示栈时，出栈与入栈的时间复杂度是(N) 5. 已知一颗完全二叉树的第6层有7个结点，则该完全二叉树总共有多少个结点?（ ）。 A40 B39 C38 D37 6. 对下图从 A 出发进行广度优先遍历，正确的是（ ）。 AA B E C F D G H BA D G H F C B E CA B C D E F G H DA D C B G H F E 数据结构与操作系统试卷 第2页 共 8 页 7. 对下面一个有向图进行拓扑排序，结果正确的是（ ）。 AA B D E C B. A B C D E CA B D C E DA C E B
4、 D 8. 采用平方探测方法解决冲突时，散列表的装载因子一般应低于 （ ） 。 A0.8 B0.7 C0.6 D0.5 9. 一个有序数据序列中有 31 个数据，采用二分查找法在其中查找一个数据，最多要比较几次就能得到查找结果（ ）。 A5 B 6 C16 D15 10. 当待排记录序列已经按关键字顺序有序时，再使用下列算法，其时间复杂度最小的是（ ）。 A归并排序 B快速排序 C简单选择排序 D直接插入排序 11. 下图所示这棵树的先序遍历结果是（ ）。 AABDCEF B. ABCDEF C.BDACEF D. BDAECF BCADEF 12. 关于散列表的表长度，正确的是( )。 A.
5、 表长度必须大于数据个数的两倍，且必须是素数 B. 数据个数的两倍即可 C. 数据个数的 10 倍 D. 采用分离链接法时，只要稍大于数据个数即可，且必须是素数 数据结构与操作系统试卷 第3页 共 8 页 13. 在有 31 个节点的二叉排序树中查找一个数据，下列描述正确的是（ ）。 A最多只要比较 5 次就可以得到结果 B可能要比较 31 次才能得到结果 C最多只要比较 6 次就可以得到结果 D必须比较 30 次才能得到结果 14. 若数据序列4,5,3,9,6,1,2是采用下列方法之一得到的第一趟排序后的结果，则该排序算法是（ ）。 A冒泡排序 B直接插入排序 C快速排序 D归并排序 15
6、. 对数据 7，3，9，2，5 进行排序时，第一趟的排序结果如下： 3, 7, 2, 5, 9； 则采用的排序算法是（ ） 。 A冒泡排序 B直接插入排序 C快速排序 D归并排序 16. 把数据1，2，3，4，5，6，7通过插入操作构造一棵AVL树时，下列描述正确的是（ ）。 A按照 1，2，3，4，5，6，7 的插入顺序构造的 AVL 树的查找效率最高 B按照 7，6，5，4，3，2，1 的插入顺序构造的 AVL 树的查找效率最高 C按照 4, 2, 1, 3, 6, 5, 7 的插入顺序构造的 AVL 树的查找效率最高 D上述三棵 AVL 树的查找效率相同 17. 已知一个数据序列中有 1
7、5 个数据，且其已经有序排列，若采用最快的查找算法和必要的存储结构，在该序列中要查找一个数据元素，则平均比较次数最少要多少次（ ）。 A1 B. 3 C. 4 D. 15 18. 分别采用线性表、二叉查找树、AVL 树、散列表存储数据并进行查找，下列说法正确的是（ ）。 A线性表的查找速度最慢 B. 散列表的查找速度最快 C. 二叉查找树的查找速度肯定比线性表快 D. AVL 树的查找速度肯定比二叉查找树快 19. 一棵满二叉树共有 3 层（树根为第一层），则叶子节点个数为（ ）。 A. 1 B. 2 C. 3 D. 4 20. 若要进行大数据 （比如：十进制数的位数超过 20） 之间的数学运
8、算，采用的数据结构应该是（ ）。 A 图 B. 二叉树 C. 链表 D. 集合 数据结构与操作系统试卷 第4页 共 8 页 21以下哪种特性不是操作系统的基本特性？( ) A虚拟性 B.并行性 C. 异步性 D. 共享性 22. 设置当前工作目录的主要目的是（ ） 。 A. 节省外存空间 B. 节省内存空间 C. 加快文件的检索速度 D. 加快文件的读/写速度 23. 进程从阻塞状态进入就绪状态的原因可能是( ) A. 等待的事件已发生（或完成） B. 等待某一事件发生 C. 被选中占有处理机 D. 时间片用完 24. 在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区
9、合并，为此需修改空闲区表，造成空闲区数目无变化的情况是( ) A.无上邻空闲区，也无下邻空闲区 B. 有上邻空闲区，也有下邻空闲区 C.有下邻空闲区但无上邻空闲区;或有上邻空闲区但无下邻空闲区 D.上述答案都不是 25. 假设某一机器的内存有 4G,硬盘为 500G,请问使用虚拟内存技术后，其虚拟 内容的容量为（ ） A. 496G B. 4G C. 500G D. 504G 26.在基本分页存储管理中，逻辑地址转换为物理地址时，若页号超过页表长度，则会引起( )。 A. 输入输出 I/O 中断 B.缺段中断 C.越界中断 D.缺页中断 27.对于某个进程而言，其运行的场所必须在( )中。 A
10、. 内存 B. 硬盘 C. SWAPING 交换区 D. 输入井或输出井 28.成组链接法可用于( ) A.磁盘空闲盘块的组织 B.磁盘的驱动调度 C.文件目录的查找 D.请求分页虚拟管理中的页面调度 29.下列算法中用于磁盘调度的是( ) A. 优先级高者优先算法 B. FIFO 算法 C. 时间片轮转法 RR D. 最短寻道时间优先(SSTF) 30.在 I/O 设备管理中，通道是一种（ ）。 A. I/O 端口 B. 设备控制器 C. I/O 专用处理机 D. 软件工具 31. 假设磁头当前位于 100 道，正在向磁道序号增加的方向移动。现有一个磁 道访问请求序列为 35，45，12，6
11、8，110，180，170，195，采用先来先服务调度（FCFS）算法得到的磁道访问序列是（ ） 。 A. 110, 170, 180, 195, 68, 45, 35, 12 B. 35, 45, 12, 68, 110, 180, 170, 195 C. 110, 170, 180, 195, 12, 35, 45, 68 D. 12, 35, 45, 68, 110, 170, 180, 195 数据结构与操作系统试卷 第5页 共 8 页 32. 在文件索引分配时，若有一文件的索引块如下图所示： 5 8 2 4 10 -1 -1 请问，存储该索引文件总共需占用磁盘多大（几块） （ ）？
12、A. 9 B. 7 C. 6 D. 5 33. 在基本分页存储管理中，若采用最佳页面置换算法 OPT，则当进程分配到的物理块数目增加时，缺页中断的次数（ ） A. 可能减少或不变 B.一定减少 C. 无影响 D.可能增加也可能 34. 基本分段内存管理系统中，访问一条指令需要几次访问内存（ ）？ A. 3 B. 0 C. 1 D. 2 35. 某基于动态分区存储管理的计算机，假设其主存容量为 55MB(初始为空闲)，采用最佳适配（Best Fit）算法，分配和释放内存的顺序为：分配15MB,分配 30MB,释放 15MB,分配 8MB,分配 6MB,此时主存中最大空闲区的大小是( )。 A.
13、10MB B. 9MB C. 7MB D. 15MB 36. 某计算机系统中有 K 台打印机，由 4 个进程竞争使用，每个进程最多需要 3 台打印机才能完成任务。该系统不可能发生死锁时，K 的最小值是（ ） 。 A. 6 B. 10 C. 8 D. 9 37. 采用 SPOOLing 技术的主要目的是（ ）。 A. 把独占设备改造成共享设备，提高 I/O 速度 B. 提高 CPU 主机效率 C. 减轻用户编程负担 D. 提高程序的运行速度 数据结构与操作系统试卷 第6页 共 8 页 38考虑以下页表结构： 页号 块号 0 3 1 1 2 4 3 7 假设页的大小为512字节（ 即页内地址长度为
14、9位） ，请把以下以十六进制表示的逻辑地址0 x567， 通过页表转换为物理地址 （也用十六进制表示）是 （ ） 。 A. 0 x3417 B. 地址转换错误 C. 0 x967 D. 0 x567 39. 以下不是设备分配算法的是（ ） A. 先来先服务 B. 短作业优先 C. 优先级高的优先 D. ABC 选项都是 40. 对两个并发进程，其互斥信号量为 mutex；初值为 1，若 mutex0，则表明（ ） 。 A没有进程进入临界区 B有一个进程进入临界区但没有进程处于阻塞状态 C一个进程进入临界区而另一个进程正处于阻塞状态 D有两个进程进入临界区 二、 综合应用题：4145 小题，共
15、70 分。 二、 综合应用题：4145 小题，共 70 分。 41. （25 分）带有头、尾节点的双向链表，其节点结构为 prev data next 请设计一个算法对两个有序链表进行合并，合并结果仍然要保持有序。例如：假设有序链表 L1,如下图所示 有序链表 L2 如下图所示： 合并后结果链表 L3 为： 数据结构与操作系统试卷 第7页 共 8 页 要求： （1） 请描述算法的基本设计思想（5 分） （2） 用伪代码描述算法的详细实现步骤（5 分） （3） 请采用某一程序设计语言写一个函数，其功能是：在双向链表尾部插入新节点。 （5 分） （4） 根据设计思想和实现步骤，采用某一程序设计语言
16、描述算法（可 C、 C+、Java） ，关键之处请给出简要注释。 （5 分） （5） 请采用某一程序设计语言写一个函数，其功能是：在双向链表头部删除节点。 （5 分） 42. （15 分）把 7 个字母 ABCDEFG，依次插入到树上，请： （1）构造一棵 AVL 树，要求：每插入一个字母，画一棵 AVL 树，共 7 棵（7分） （2）构造一棵二叉查找树，要求：画出最终的这棵树（4 分） （3）分析这棵二叉查找树与 AVL 树的区别（4 分） 43. (10 分) 在银行家算法中，若出现下述资源分配情况(5 个进程，4 类资源)： process Max (最大需求) Allocation（已
17、分配） Available（系统资源） A B C D A B C D A B C D P1 2 7 5 0 1 0 0 0 1 6 2 2 P2 0 6 6 10 0 0 1 4 P3 3 6 10 9 1 3 5 4 P4 0 9 8 4 0 3 3 2 P5 0 0 4 3 0 0 3 1 试问： （1）该状态是否安全？若是，请给出其中一个安全序列，若不是，也请说明原因 （本题要求对是否存在安全状态， 都要写出详细的推导过程） 。 (7 分) （2）若 P3 提出请求 Request(1，2，1,1)，系统能否将资源分配给它？为什么？要求详细说明你的理由。 （3 分） 44.(10 分)
18、 考虑下述页面走向：2，3，1，4，2，3，5，2， 3， 1，4，5， 当内存物理块数量分别为 3 和和 4 时，试问 FIFO（先进先出） 、LRU(最近最少使用)算法这两种内存置换算法的缺页次数和置换次数分别是多少？最后，比较这两种算法后，你有何发现？上述过程要求分别写出详细的页面置换过程。 数据结构与操作系统试卷 第8页 共 8 页 45.（10 分）请你用类 C 语言类 C 语言来完成程序，尝试用学过的信号量操作解决以下问题： 有一个家庭，有父、子、女三人，爸爸负责不停地把水果放到水果盘中，假设一次只能允许放一个水果到水果盘中，水果品种分为苹果和香蕉两种，限制条件是儿子只能从盘中取苹果吃，女儿只能从盘中取香蕉吃。请你用信号量 WAIT 和 SIGNAL 操作来实现这三个人的进程并发操作，假设初始状态水果盘中为空。 【完】
