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

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

第1页 / 共6页

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

第2页 / 共6页

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

第3页 / 共6页

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

第4页 / 共6页

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

第5页 / 共6页

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

第6页 / 共6页

2015 年浙江省中国计量大学数据结构与操作系统考研真题一、单项选择题：1～40 小题，每小题 2 分，共 80 分。在每小题给出的四个选项中，请选出一项最符合题目要求的。 1.在下面的 C 语言程序段中，加法操作的时间复杂度为（）。 Int i,j,k,sum=0; For (i=0;i

D．ACEBD 8.采用平方探测方法解决冲突时，散列表的装载因子一般应低于（）。 A．0.8B．0.7C．0.6D．0.5 9.一个有序数据序列中有 31 个数据，采用二分查找法在其中查找一个数据，最多要比较几次就能得到查找结果（）。 10.当待排记录序列已经按关键字顺序有序时，再使用下列算法，其时间复杂度最小的是（）。 A．归并排序 B．快速排序 C．简单选择排序 D．直接插入排序 11.下图所示这棵树的先序遍历结果是（）。 A．ABDCEF B.ABCDEF C.BDACEF D.BDAECF 12.关于散列表的表长度，正确的是()。 A.表长度必须大于数据个数的两倍，且必须是素数 B.数据个数的两倍即可 C.数据个数的 10 倍 D.采用分离链接法时，只要稍大于数据个数即可，且必须是素数 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.1B.3C.4D.15 18.分别采用线性表、二叉查找树、AVL 树、散列表存储数据并进行查找，下列说法正确的是（）。 A.线性表的查找速度最慢 B.散列表的查找速度最快 C.二叉查找树的查找速度肯定比线性表快 D.AVL 树的查找速度肯定比二叉查找树快 19.一棵满二叉树共有 3 层（树根为第一层），则叶子节点个数为（）。 A.1B.2C.3D.4 20.若要进行大数据（比如：十进制数的位数超过 20）之间的数学运算，采用的数据结构应该是（）。 A．图 B.二叉树 C.链表 D.集合 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 26.在基本分页存储管理中，逻辑地址转换为物理地址时，若页号超过页表长度，则会引起 ( )。 A.输入输出 I/O 中断 B.缺段中断 C.越界中断 D.缺页中断 27.对于某个进程而言，其运行的场所必须在( )中。 A.内存 B.硬盘 C.SWAPING 交换区 D.输入井或输出井 28.成组链接法可用于( ) A.磁盘空闲盘块的组织 B.磁盘的驱动调度 B.4G C.500G ) D.504G

C.文件目录的查找 D.请求分页虚拟管理中的页面调度 29.下列算法中用于磁盘调度的是( ) A.优先级高者优先算法 B.FIFO 算法 C.时间片轮转法 RRD.最短寻道时间优先(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 32.在文件索引分配时，若有一文件的索引块如下图所示：请问，存储该索引文件总共需占用磁盘多大（几块）（）？ A.9 B.7 C.6 D.5 33.在基本分页存储管理中，若采用最佳页面置换算法 OPT，则当进程分配到的物理块数目增加时，缺页中断的次数（） A.可能减少或不变 B.一定减少 C.无影响 D.可能增加也可能 34.基本分段内存管理系统中，访问一条指令需要几次访问内存（）？ A.3B.0C.1D.2 35.某基于动态分区存储管理的计算机，假设其主存容量为 55MB(初始为空闲)，采用最佳适配（BestFit）算法，分配和释放内存的顺序为：分配 15MB,分配 30MB,释放 15MB,分配 8MB, 分配 6MB,此时主存中最大空闲区的大小是()。 A.10MBB.9MBC.7MBD.15MB 36.某计算机系统中有 K 台打印机，由 4 个进程竞争使用，每个进程最多需要 3 台打印机才能完成任务。该系统不可能发生死锁时，K 的最小值是（）。 A.6 B.10 C.8 D.9 37.采用 SPOOLing 技术的主要目的是（）。 A.把独占设备改造成共享设备，提高 I/O 速度 B.提高 CPU 主机效率 C.减轻用户编程负担 D.提高程序的运行速度

38．考虑以下页表结构： D.0x567 B.地址转换错误 C.0x967 假设页的大小为 512 字节（即页内地址长度为 9 位），请把以下以十六进制表示的逻辑地址 0x567，通过页表转换为物理地址（也用十六进制表示）是（）。 A.0x3417 39.以下不是设备分配算法的是（） 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 为：要求：（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 类资源)： processMax(最大需求)Allocation（已分配）Available（系统资源）试问：（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(最近最少使用)算法这两种内存置换算法的缺页次数和置换次数分别是多少？最后，比较这两种算法后，你有何发现？上述过程要求分别写出详细的页面置换过程。 45.（10 分）请你用类 C 语言来完成程序，尝试用学过的信号量操作解决以下问题：有一个家庭，有父、子、女三人，爸爸负责不停地把水果放到水果盘中，假设一次只能允许放一个水果到水果盘中，水果品种分为苹果和香蕉两种，限制条件是儿子只能从盘中取苹果吃，女儿只能从盘中取香蕉吃。请你用信号量 WAIT 和 SIGNAL 操作来实现这三个人的进程并发操作，假设初始状态水果盘中为空

资料库

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

相关推荐

考研

热门标签

最新资料