2016年浙江省中国计量大学数据结构与操作系统考研真题.doc-资料库

2016年浙江省中国计量大学数据结构与操作系统考研真题.doc.pdf-第1页.jpg

第1页 / 共6页

2016年浙江省中国计量大学数据结构与操作系统考研真题.doc.pdf-第2页.jpg

第2页 / 共6页

2016年浙江省中国计量大学数据结构与操作系统考研真题.doc.pdf-第3页.jpg

第3页 / 共6页

2016年浙江省中国计量大学数据结构与操作系统考研真题.doc.pdf-第4页.jpg

第4页 / 共6页

2016年浙江省中国计量大学数据结构与操作系统考研真题.doc.pdf-第5页.jpg

第5页 / 共6页

2016年浙江省中国计量大学数据结构与操作系统考研真题.doc.pdf-第6页.jpg

第6页 / 共6页

2016 年浙江省中国计量大学数据结构与操作系统考研真题一、单项选择题：1～40 小题，每小题 2 分，共 80 分。在每小题给出的四个选项中，请选出一项最符合题目要求的。 1. 函数 fun 的时间复杂度为（）。 float fun(float x, int n) { float result = 1.0f; for( i=0; i < n*n/2; ++i) { result *= x; } return result } A．O( (n2/2)! ) B．0(2log2n) C．0(n2/2) D．O(n2) 2. 下列排序算法中，需要额外辅助存储空间最多的是（）。 A．归并排序 B．快速排序 C．堆排序 D．直接插入排序 3. 以下数据结构中，不属于线性表的是（）。 A. 队列 B. 栈 C. 图 D. 循环链表 4. 下面关于栈的描述中，错误的是（）。 A．先进后出 B．两头都可以插入和删除 C．可以用数组来实现 D．可以用链表来实现 5. 关于环形（循环）队列，错误的是（）。 A．先进先出 B．用数组来实现 C．可以提高空间的利用率 D．用循环链表来实现 6. 层数为 8 的二叉树其结点个数最多有（）。 A．1023 B．511 C．255 D．127 7. 有 100 个结点的无向图要确保是一个连通图至少应有（）。 A．101 条边 B．99 条边 C．50 条边 D．6 条边 8. 关于图的描述，错误的是（）。 A．有向图的邻接矩阵一定是对称矩阵 B. 完全图中的边一定比连通图中的边多 C．深度优先搜索的结果可能不唯一 D．广度优先搜索的结果可能不唯一

9. 下列排序算法中，哪个是不稳定的（不稳定指的是：关键字相同的两个数据，排序后它们的先后位置会变化）（）。 A．希尔排序 B．简单选择排序 C．插入排序 D．冒泡排序 10. 二叉查找树中有 1023 个结点，查找其中一个数据时，描述正确的是（）。 A．至少要比较 10 次 B．最多比较 10 次 C．不可能超过 10 次 D．如果是平衡二叉查找树，可能要比较 1023 次 11. 图 1 所示这棵树的中序遍历结果是（）。 A．ABCDEF B. DBACEF C. DBAECF D. A B C D E F BACCEF 图 1.树 12. 往栈中输入序列{1,2,……，n}后再逐个输出，则输出序列的最后一个元素是 ( )。 A．不确定 B．n-1 D．1 C．n ）。 13. 假设 N 个数据已经放在不同的数据结构，然后进行查找，下列描述错误的是：（ A．如果采用合适的散列表，其查找速度最快 B．用二叉查找树来查找比用折半查找要快 C．链表上的查找要比二叉查找树快 D．平衡二叉查找树上的查找要比普通二叉查找树快 14. 若数据序列 5, 96, 12, 64, 78, 23, 49 是采用下列方法之一得到的第一趟排序后的结果，则该排序算法是（）。 A．冒泡排序 B．直接插入排序 C．快速排序 D．归并排序 15. 对数据 8，1，4，9，6，3，5，2，7，0 进行排序时，第一趟的排序结果如下： 0,1,4,2,5,3,6,9,7,8；则采用的排序算法是（ A．快速排序 B．直接插入排序 16. 把数据 1，2，3，4，5，6，7 通过插入操作构造一棵二叉查找树，下列描述错误 C．冒泡排序 D．归并排序）。

）。 ) ）。）。）。 ) B. 二叉树 C. 栈 D. 栈 B. 256 C. 10 D. 1 C.队列 D. 二叉树 B. 2048 C. 1024 D. 512 C. 应用软件 D. 工具软件 B. 节省内存空间 D. 加快文件的读/写速度的是（ A．按照 3,4,1,2,6,7,5 的插入顺序构造的二叉查找树，树高为 3 B．按照 4,2,1,3,6,5,7 的插入顺序构造的二叉查找树的查找效率最高 C．按照 3,4,1,2,6,7,5 的插入顺序构造的二叉查找树是平衡二叉树 D．按照 4,2,1,3,6,5,7 的插入顺序构造的二叉查找树是平衡二叉树 17.已知一个数据序列中有 1024 个数据，且其已经有序排列，若采用最快的查找算法和必要的存储结构，在该序列中要查找一个数据元素，则平均比较次数最少要多少次（ A．512 18.一棵满二叉树共有 11 层（树根为第一层），则叶子节点个数为（）。 A. 0 19.若要检查文件中的括号是否匹配，采用的数据结构应该是（ A．图 20.快递员每天要送很多包裹给客户，为了提高效率，缩短总路程长度，请问该选用什么样的数据结构来设计路线（ A．线性表 B. 图 21．操作系统是一种( A．实用软件 B.系统软件 22. 设置当前工作目录的主要目的是（）。 A. 节省外存空间 C. 加快文件的检索速度 23.进程从阻塞状态进入就绪状态的原因可能是( A. 被选中占有处理机 C. 等待的事件已发生 24.在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数无变化的情况是( A.无上邻空闲区，也无下邻空闲区 B.有上邻空闲区，也有下邻空闲区 C.有下邻空闲区但无上邻空闲区;或有上邻空闲区但无下邻空闲区 D. 以上三种都可以 25.假设某一机器的内存有 2G,硬盘为 300G,请问使用虚拟内存技术后，其虚拟内容的容量为（） A. 2G 26.在基本分段存储管理中，逻辑地址转换为物联地址时，若段号超过段表长度，则会引起( A. 输入输出中断 B. 缺段中断 C. 越界中断 27.某个进程运行在( A. 内存 C. SWAPING 交换区 28.成组链接法可用于( A.磁盘空闲空间的管理 C.文件目录的查找 29.下列算法中用于磁盘调度的是( A. SSTF 优先级高者优先算法 ) B. 等待某一事件发生 D. 时间片用完 D.页式虚拟存贮管理中的页面调度 ) B. 4G C. 300G D.302G D. 硬盘中的某个子目录 B. FIFO 先进先出算法 )中。 B. 硬盘 ) B.磁盘的驱动调度 )。 D. 缺页中断

D. 最短寻道时间优先 B. 数据通道 D. 软件工具 C. 时间片轮转法 RR 30.通道是一种（）。 A. I/O 端口 C. I/O 专用处理机 31.假设磁头当前位于 100 道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为 28，55，12，68，110，180，170，195，采用先来先服务调度（FCFS）算法得到的磁道访问序列是（）。 A. 110,170,180,195,68,55,28,12 C. 110,170,180,195,12,28,55,68 32.在通过索引分配技术时，若某一文件的索引块如下图所示： B. 28,55,12,68,110,180,170,195 D. 12,28,55,68,110,170,180,195 11 4 2 1 -1 -1 请问，该索引文件大小总共占有磁盘空间（ A. 4 D. 6 B. 7 C. 5 ）块？ 33. 在基本分页存储管理中，若采用最佳页面置换算法 OPT，则当进程分配到的物理块数增加时，缺页中断的次数会（） A. 一定减少 B.一定不会增加 C. 无影响 D.可能增加也可能减少 34. 采用（）不会产生内部碎片。 A. 分页式存储管理 B. 分段式存储管理 C. 固定分区式存储管理 D. 虚拟分页存储管理 35. 某基于动态分区存储管理的计算机，其主存容量为 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. 9 37. 采用 SPOOLing 技术的目的是（）。 A. 提高独占设备的利用率 B. 提高主机效率 C. 减轻用户编程负担 D. 提高程序的运行速度 38．考虑以下页表结构：页号块号 0 1 2 2 5 1

3 9 假设页的大小为512字节, 即页内地址长度为 9 位，请把以下以十六进制表示的逻辑地址 0x967，通过页表转换为物理地址（也用十六进制表示）是（）。 A. 0x3417 B. 地址转换错误 C. 0x367 D. 0x567 39. 以下不是设备分配算法的是（） A. 先来先服务 C. 优先级高的优先 B. 短作业优先 D. 以上几种都不是 40. 对两个并发进程，其互斥信号量为 mutex；初值为 1，若 mutex＝0，则表明（）。 A．没有进程进入临界区 B．有一个进程进入临界区但没有进程处于阻塞状态 C．一个进程进入临界区而另一个进程正处于等待进入临界区状态 D．有两个进程进入临界区二、综合应用题：41～45 小题，共 70 分。 41.带有头节点的单链表，其节点结构为 data next 带有头结点的单链表如下图所示 header a1 a2 a3 a4 NULL 请设计一个算法对两个有序单链表 L1，L2 进行求交的操作，得到新的链表 L3，L3 仍然保持有序的状态，要求：（1）请描述算法的基本设计思想（5 分）（2）用伪代码描述算法的详细实现步骤（5 分）（3）根据设计思想和实现步骤，采用某一程序设计语言写一个函数来实现该算法，请先给出结点类型的定义。（5 分）（4）请采用某一程序设计语言写一个函数，其功能是：遍历单链表，输出所有结点中的 data 值。（5 分）（5）请采用某一程序设计语言写一个函数，其功能是：创建空链表。（5 分） 42. 现有数据序列{4371，1323,6173，4199,4344,9679,1989}和散列函数 h(x)=x mode 10。（1）请画出用分离链接法表示的散列表（5 分）（2）请画出用平方探测法 f(i)=i*i 表示的散列表（5 分）（3）请计算前两题中散列表的装载因子和查找成功的平均查找长度 ASL（5 分） B C D Allocation（已分配） Available（系统资源） B 43. 在银行家算法中，若出现下述资源分配情况(5 个进程，4 类资源)： process Max (最大需求) A A P1 P2 P3 P4 P5 5 6 10 8 4 D 1 0 1 3 0 0 10 9 0 0 3 3 3 1 6 2 2 0 1 5 2 1 C 0 0 A C D B 0 4 4 2 0 3 0 0 7 6 6 9 0 4 3

试问：（1）(6 分) 该状态是否安全？若是，请给出其中一个安全序列，若不是，也请说明原因。要求：是否安全状态均要求写出具体推导过程。（2）（4 分）若 P3 提出请求 Request(1，2，1,1)，系统能否将资源分配给它？为什么？要求详细说明你的理由。 44.(10 分) 考虑下述页面走向： 6，7，2，1，6，7，5，6，7，2，1，5 当内存物理块数量分别为 3 和 4 时，试问 FIFO（先进先出）、LRU(最近最少使用)算法这两种内存置换算法的缺页次数和置换次数分别是多少？最后，比较这两种算法后，你有何发现？上述过程要求分别写出详细的置换过程。 45.（10 分）用类 C 语言来完成程序，尝试用学过的信号量操作解决以下问题：有一个家庭，有父、子、女三人，爸爸负责不停地把水果放到盘中，假设一次只能允许放一个水果，水果品种分为苹果和香蕉两种，限制条件是儿子只能从盘中取苹果吃，女儿只能从盘中取香蕉吃，请你用信号量 WAIT 和 SIGNAL 操作实现这三个人的进程并发操作，假设开始时盘中为空。

资料库

2016年浙江省中国计量大学数据结构与操作系统考研真题.doc

相关推荐

考研

热门标签

最新资料