Microsoft Word A.doc

Size: px

Start display at page:

Download "Microsoft Word A.doc"

楚铿陶
7 years ago
Views:

1 一单项选择题 :1~40 小题, 每小题 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.Ο(2n 2 ) B.Ο(2n 3 ) C.Ο(n 3 ) D.Ο(n 2 ) 2. 关于线性表的描述正确的是 ( ) A. 访问顺序表中第 k 个元素的时间复杂度是 Ο(N) B. 访问单链表中第 k 个节点的时间复杂度是 Ο(N) C. 把新数据插入到顺序表中第 k 个位置的时间复杂度是 Ο(1) D. 把新数据插入到单链表中第 k 个位置的时间复杂度是 Ο(1) 3. 关于队列描述正确的是 ( ) A. 用链表表示队列时, 也不可以插队 ( 插队指在队列中间插入新数据 ) B. 用环形数组表示队列时, 可以循环使用数组, 所以队列永远不会满 C. 用数组表示队列时, 数据入队的时间复杂度是 Ο(N) D. 用数组表示队列时, 数据出队的时间复杂度是 Ο(N) 4. 关于栈描述正确的是 ( ) A. 数据进出栈的原则是先入先出 B. 用数组表示栈时, 栈的操作速度要比用链表表示的栈操作快 C. 用单链表表示栈时, 出栈与入栈的时间复杂度是 Ο(N) D. 用数组表示栈时, 出栈与入栈的时间复杂度是 Ο(N) 5. 已知一颗完全二叉树的第 6 层有 7 个结点, 则该完全二叉树总共有多少个结点?( ) A.40 B.39 C.38 D 对下图从 A 出发进行广度优先遍历, 正确的是 ( ) A.A B E C F D G H B.A D G H F C B E C.A B C D E F G H D.A D C B G H F E 数据结构与操作系统试卷第 1 页共 8 页

2 7. 对下面一个有向图进行拓扑排序, 结果正确的是 ( ) A.A B D E C B. A B C D E C.A B D C E D.A C E B D 8. 采用平方探测方法解决冲突时, 散列表的装载因子一般应低于 ( ) A.0.8 B.0.7 C.0.6 D 一个有序数据序列中有 31 个数据, 采用二分查找法在其中查找一个数据, 最多要比较几次就能得到查找结果 ( ) A.5 B. 6 C.16 D 当待排记录序列已经按关键字顺序有序时, 再使用下列算法, 其时间复杂度最小的是 ( ) A. 归并排序 B. 快速排序 C. 简单选择排序 D. 直接插入排序 11. 下图所示这棵树的先序遍历结果是 ( ) A.ABDCEF B. ABCDEF C.BDACEF D. BDAECF A B C D E F 12. 关于散列表的表长度, 正确的是 ( ) A. 表长度必须大于数据个数的两倍, 且必须是素数 B. 数据个数的两倍即可 C. 数据个数的 10 倍 D. 采用分离链接法时, 只要稍大于数据个数即可, 且必须是素数数据结构与操作系统试卷第 2 页共 8 页

3 13. 在有 31 个节点的二叉排序树中查找一个数据, 下列描述正确的是 ( ) A. 最多只要比较 5 次就可以得到结果 B. 可能要比较 31 次才能得到结果 C. 最多只要比较 6 次就可以得到结果 D. 必须比较 30 次才能得到结果 14. 若数据序列 4,5,3,9,6,1,2 是采用下列方法之一得到的第一趟排序后的结果, 则该排序算法是 ( ) A. 冒泡排序 B. 直接插入排序 C. 快速排序 D. 归并排序 15. 对数据 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. 已知一个数据序列中有 15 个数据, 且其已经有序排列, 若采用最快的查找算法和必要的存储结构, 在该序列中要查找一个数据元素, 则平均比较次数最少要多少次 ( ) A.1 B. 3 C. 4 D 分别采用线性表二叉查找树 AVL 树散列表存储数据并进行查找, 下列说法正确的是 ( ) A. 线性表的查找速度最慢 B. 散列表的查找速度最快 C. 二叉查找树的查找速度肯定比线性表快 D. AVL 树的查找速度肯定比二叉查找树快 19. 一棵满二叉树共有 3 层 ( 树根为第一层 ), 则叶子节点个数为 ( ) A. 1 B. 2 C. 3 D 若要进行大数据 ( 比如 : 十进制数的位数超过 20) 之间的数学运算, 采用的数据结构应该是 ( ) A. 图 B. 二叉树 C. 链表 D. 集合数据结构与操作系统试卷第 3 页共 8 页

4 21. 以下哪种特性不是操作系统的基本特性?( ) A. 虚拟性 B. 并行性 C. 异步性 D. 共享性 22. 设置当前工作目录的主要目的是 ( ) A. 节省外存空间 B. 节省内存空间 C. 加快文件的检索速度 D. 加快文件的读 / 写速度 23. 进程从阻塞状态进入就绪状态的原因可能是 ( ) A. 等待的事件已发生 ( 或完成 ) B. 等待某一事件发生 C. 被选中占有处理机 D. 时间片用完 24. 在可变式分区分配方案中, 某一作业完成后, 系统收回其主存空间, 并与相邻空闲区合并, 为此需修改空闲区表, 造成空闲区数目无变化的情况是 ( ) A. 无上邻空闲区, 也无下邻空闲区 B. 有上邻空闲区, 也有下邻空闲区 C. 有下邻空闲区但无上邻空闲区 ; 或有上邻空闲区但无下邻空闲区 D. 上述答案都不是 25. 假设某一机器的内存有 4G, 硬盘为 500G, 请问使用虚拟内存技术后, 其虚拟内容的容量为 ( ) A. 496G B. 4G C. 500G D. 504G 26. 在基本分页存储管理中, 逻辑地址转换为物理地址时, 若页号超过页表长度, 则会引起 ( ) A. 输入输出 I/O 中断 B. 缺段中断 C. 越界中断 D. 缺页中断 27. 对于某个进程而言, 其运行的场所必须在 ( ) 中 A. 内存 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,68,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 数据结构与操作系统试卷第 4 页共 8 页

5 32. 在文件索引分配时, 若有一文件的索引块如下图所示 : 请问, 存储该索引文件总共需占用磁盘多大 ( 几块 )( )? A. 9 B. 7 C. 6 D 在基本分页存储管理中, 若采用最佳页面置换算法 OPT, 则当进程分配到的物理块数目增加时, 缺页中断的次数 ( ) A. 可能减少或不变 B. 一定减少 C. 无影响 D. 可能增加也可能 34. 基本分段内存管理系统中, 访问一条指令需要几次访问内存 ( )? A. 3 B. 0 C. 1 D 某基于动态分区存储管理的计算机, 假设其主存容量为 55MB( 初始为空闲 ), 采用最佳适配 (Best Fit) 算法, 分配和释放内存的顺序为 : 分配 15MB, 分配 30MB, 释放 15MB, 分配 8MB, 分配 6MB, 此时主存中最大空闲区的大小是 ( ) A. 10MB B. 9MB C. 7MB D. 15MB 36. 某计算机系统中有 K 台打印机, 由 4 个进程竞争使用, 每个进程最多需要 3 台打印机才能完成任务该系统不可能发生死锁时,K 的最小值是 ( ) A. 6 B. 10 C. 8 D 采用 SPOOLing 技术的主要目的是 ( ) A. 把独占设备改造成共享设备, 提高 I/O 速度 B. 提高 CPU 主机效率 C. 减轻用户编程负担 D. 提高程序的运行速度数据结构与操作系统试卷第 5 页共 8 页

6 38. 考虑以下页表结构 : 页号块号假设页的大小为 512 字节 ( 即页内地址长度为 9 位 ), 请把以下以十六进制表示的逻辑地址 0x567, 通过页表转换为物理地址 ( 也用十六进制表示 ) 是 ( ) A. 0x3417 B. 地址转换错误 C. 0x967 D. 0x 以下不是设备分配算法的是 ( ) A. 先来先服务 B. 短作业优先 C. 优先级高的优先 D. ABC 选项都是 40. 对两个并发进程, 其互斥信号量为 mutex; 初值为 1, 若 mutex=0, 则表明 ( ) A. 没有进程进入临界区 B. 有一个进程进入临界区但没有进程处于阻塞状态 C. 一个进程进入临界区而另一个进程正处于阻塞状态 D. 有两个进程进入临界区二综合应用题 :41~45 小题, 共 70 分 41. (25 分 ) 带有头尾节点的双向链表, 其节点结构为 prev data next 请设计一个算法对两个有序链表进行合并, 合并结果仍然要保持有序例如 : 假设有序链表 L1, 如下图所示有序链表 L2 如下图所示 : 合并后结果链表 L3 为 : 数据结构与操作系统试卷第 6 页共 8 页

7 要求 : (1) 请描述算法的基本设计思想 (5 分 ) (2) 用伪代码描述算法的详细实现步骤 (5 分 ) (3) 请采用某一程序设计语言写一个函数, 其功能是 : 在双向链表尾部插入新节点 (5 分 ) (4) 根据设计思想和实现步骤, 采用某一程序设计语言描述算法 ( 可 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( 已分配 ) Available( 系统资源 ) A B C D A B C D A B C D P P P P P 试问 : (1) 该状态是否安全? 若是, 请给出其中一个安全序列, 若不是, 也请说明原因 ( 本题要求对是否存在安全状态, 都要写出详细的推导过程 ) (7 分 ) (2) 若 P3 提出请求 Request(1,2,1,1), 系统能否将资源分配给它? 为什么? 要求详细说明你的理由 (3 分 ) 44.(10 分 ) 考虑下述页面走向 :2,3,1,4,2,3,5,2, 3, 1,4,5, 当内存物理块数量分别为 3 和 4 时, 试问 FIFO( 先进先出 ) LRU( 最近最少使用 ) 算法这两种内存置换算法的缺页次数和置换次数分别是多少? 最后, 比较这两种算法后, 你有何发现? 上述过程要求分别写出详细的页面置换过程数据结构与操作系统试卷第 7 页共 8 页

8 45.(10 分 ) 请你用类 C 语言来完成程序, 尝试用学过的信号量操作解决以下问题 : 有一个家庭, 有父子女三人, 爸爸负责不停地把水果放到水果盘中, 假设一次只能允许放一个水果到水果盘中, 水果品种分为苹果和香蕉两种, 限制条件是儿子只能从盘中取苹果吃, 女儿只能从盘中取香蕉吃请你用信号量 WAIT 和 SIGNAL 操作来实现这三个人的进程并发操作, 假设初始状态水果盘中为空完数据结构与操作系统试卷第 8 页共 8 页

Microsoft Word A3.doc

Microsoft Word A3.doc 一单项选择题 :1~40 小题, 每小题 2 分, 共 80 分在每小题给出的选项中, 请选出一项最符合题目要求的 1. 下列排序算法中, 平均时间复杂度最小的是 ( ) A. 归并排序 B. 起泡排序 C. 简单选择排序 D. 直接插入排序 2. 关于线性表的描述正确的是 ( ) A. 采用顺序存储时, 其存储地址必须是连续的 B. 采用链式存储时, 其存储地址必须是连续的 C. 采用顺序存储时,