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

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

第1页 / 共6页

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

第2页 / 共6页

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

第3页 / 共6页

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

第4页 / 共6页

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

第5页 / 共6页

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

第6页 / 共6页

2014 年浙江省中国计量大学数据结构与操作系统考研真题一、单项选择题：1～40 小题，每小题 2 分，共 80 分。在每小题给出的选项中，请选出一项最符合题目要求的。 1．下列排序算法中，平均时间复杂度最小的是（）。 A．归并排序 B．起泡排序 C．简单选择排序 D．直接插入排序 2．关于线性表的描述正确的是（）。 A．采用顺序存储时，其存储地址必须是连续的 B．采用链式存储时，其存储地址必须是连续的 C．采用顺序存储时，其存储地址一定是不连续的 D．采用链式存储时，其存储地址一定是不连续的 3．往队列中输入序列{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 层），则这棵完全二叉树的结点个数最少有（）。 A．7B．11C．23D．28 6．有 20 个结点的无向图，关于其描述正确的是（）。 A．只要 10 条边就能确保它是一个连通图 B．至少要有 20 条边才能确保它是一个连通图 C．至少要有 19 条边才能确保它是一个连通图 D．至少要有 21 条边才能确保它是一个连通图 7．下列说法中错误的是（）。 A．有向图的邻接矩阵不一定是对称矩阵 B.无向图的邻接矩阵不一定是对称矩阵 C．若图 G 的邻接矩阵是对称的，则 G 不一定是无向图 D．若图 G 的邻接矩阵是对称的，则 G 不一定是有向图 8．若对已经有序的数据序列进行再次排序，则下列算法中时间复杂度最小的是（）。 A．归并排序 B．简单选择排序 C．堆排序 D．冒泡排序 9．一个有序数据序列中有 15 个数据，采用二分查找法在其中查找一个数据，最多要比较几次就能得到查找结果（）。 A．4B．5C．1D．15 10．在下面的 C 语言程序段中，除法操作的时间复杂度为（）。 intn,fac=1; floatx,p=1.0f,result=0; scanf(“%f%d”,&x,&n); for(i=0;i

{ p/=x; fac*=i+1; result+=fac/p; } A．O(2n) 11.图 1 所示这棵树的中序遍历结果是（）。 A．DBAECF B.ABCDEF C.DBACEF D.DBAEFC B．0(log2n) C．0(n2) D．O(n) D.3 C.4 B.5 12.设有一个顺序栈 S，元素 s1，s2，s3，s4，s5，s6 依次进栈，如果 6 个元素的出栈顺序为 s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为()。 A.6 13.在有 16 个节点的二叉排序树中查找一个数据，下列描述正确的是（）。 A．最多只要比较 5 次就可以得到结果 B．可能要比较 16 次才能得到结果 C．最多只要比较 4 次就可以得到结果 D．必须比较 15 次才能得到结果 14.若数据序列 12,78,5,64,96,23,49 是采用下列方法之一得到的第一趟排序后的结果，则该排序算法是（）。 A．冒泡排序 B．直接插入排序 C．快速排序 D．归并排序 15.对数据 7，3，9，2，5 进行排序时，第一趟的排序结果如下：5，3，2，7，9；则采用的排序算法是（）。 A．冒泡排序 B．直接插入排序 C．快速排序 D．归并排序 13.把数据 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 的插入顺序构造的查找树的查找效率最高 D．查找效率与构造查找树时插入数据的顺序无关 14.已知一个数据序列中有 10 个数据，且其已经有序排列，若采用最快的查找算法和必要的存储结构，在该序列中要查找一个数据元素，则平均比较次数最少要多少次（）。

D.1 B.16 C.8 D.7 B.4G B.5 C.4 D.500G C.502G A．10 18.一棵满二叉树共有 4 层（树根为第一层），则叶子节点个数为（）。 A.15 19.若要检查源代码文件中的括号是否匹配，采用的数据结构应该是（）。 A．图 B.二叉树 C.栈 D.队列 14.假设某快递公司每天要用 1 辆车去 100 个地方送货，为尽量减少行车里程，节省汽油，需要事先规划好送货路线，请问该选用什么样的数据结构（）。 A．线性表 B.图 C.队列 D.二叉树 21．以下不是操作系统基本特性的是（） A．并发性 B.并行性 C.虚拟性 D.异步性 22.假设某一机器的内存有 2G,硬盘为 500G,请问使用虚拟内存技术后，其虚拟内存的容量为（） A.2G 23.进程从运行状态进入阻塞状态的原因可能是（） A.被选中占有处理机 B.等待某一事件发生 C.等待的事件已发生 D.时间片用完 16.在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数减 1 的情况是（） A.无上邻空闲区，也无下邻空闲区 B.有上邻空闲区，但无下邻空闲区 C.有下邻空闲区，但无上邻空闲区 D.有上邻空闲区，也有下邻空闲区 25.下面关于操作系统主要功能描述不正确的是（） A.算法效率管理 B.存储器管理 C.文件管理 D.处理机管理 26.在请求页式存储管理中，若所需内容不在内存中，则会引起（）。 A.输入输出中断 B.缺段中断 C.越界中断 D.缺页中断 27.以下不是设备分配算法的是（） A.先来先服务 B.短作业优先 C.优先级高的优先 28.位示图方法可用于（） A.磁盘空闲空间的管理 B.磁盘的驱动调度 C.文件目录的查找 D.页式虚拟存贮管理中的页面调度 29.下列算法中用于磁盘调度的是（） A.扫描（SCAN）算法 B.LRU 算法 C.时间片轮转法 RRD.优先级高者优先算法 30.通道是一种（）。 A.I/O 端口 B.数据通道 C.I/O 专用处理机 D.软件工具 31.假设磁头当前位于 105 道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为 35，45，12，68，110，180，170，195，采用最短寻道时间优先 SSTF 调度算法得到的磁道访问序列是（）。 A.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.在通过索引分配技术时，若某一文件的索引块如下图所示：请问，该索引文件大小共占有（）块？ D.5 B.7 C.6 A.4 33.在基本分页存储管理中，若采用最近最少使用（LRU）页面置换算法，则当进程分配到的物理块数目增加时，产生缺页中断的次数（） A.一定减少 B.一定增加 C.无影响 D.可能增加也可能减少 34.设置当前工作目录的主要目的是（）。 A.节省外存空间 B.节省内存空间 C.加快文件的检索速度 D.加快文件的读/写速度 35.某基于动态分区存储管理的计算机，其主存容量为 55MB(初始为空闲)，采用最坏适应分配（WorstFit）算法，分配和释放的顺序为：分配 15MB,分配 30MB,释放 15MB,分配 8MB,分配 6MB,此时主存中最大空闲分区的大小是（）。 A.7MB 36.某计算机系统中有 K 台打印机，由 4 个进程竞争使用，每个进程最多需要 3 台打印机。该系统不可能发生死锁的 K 的最小值是（）。 A.10 B.9 37.采用 SPOOLing 技术的目的是（）。 A.提高独占设备的利用率 B.提高主机效率 C.减轻用户编程负担 D.提高程序的运行速度 38．考虑以下页表结构： C.10MB B.9MB D.8MB C.8 D.5 假设页的大小为 1K,即页内地址长度为 10 位，请把以下 D.0x567 B.地址转换错误 C.0x367 以十六进制表示的逻辑地址 0x967，通过页表转换为物理地址（也用十六进制表示）是（）。 A.0x3417 39.在操作系统中，（）不是它所关心的问题。 A.管理计算机裸机（硬件资源） B.高级程序设计语言的编译 C.管理计算机中的信息资源 D.设计、提供用户程序与计算机硬件系统的接口 40.对两个并发进程，其互斥信号量为 mutex；初值为 1，若 mutex＝0，则表明（）。 A．没有进程进入临界区 B．有一个进程进入临界区但还没有进程处于阻塞状态 C．一个进程进入临界区而另一个进程正处于等待进入临界区状态

D．有两个进程进入临界区二、综合应用题：41～45 小题，共 70 分。 41.带有头节点的单链表，其节点结构为假设有单链表 L（指向头节点的指针）,示意图如下图所示请设计一个算法对单链表进行排序，要求：（1）请描述算法的基本设计思想（5 分）（2）描述算法的详细实现步骤（5 分）（3）根据设计思想和实现步骤，采用某一程序设计语言描述算法（使用 C 或 C++），关键之处请给出简要注释。（5 分）（4）请采用某一程序设计语言写一个函数，其功能是：在单链表头部插入新节点。（5 分）（5）请采用某一程序设计语言写一个函数，其功能是：在单链表尾部删除节点。（5 分） 42.二叉查找树如图 2 所示，（1）请画出删除关键字为 E 的节点后的二叉查找树（5 分）（2）请写出中序遍历二叉树的算法（使用 C 或 C++）（5 分）（3）请写出前序遍历二叉树的算法（使用 C 或 C++）（5 分） 43.（10 分）在银行家算法中，若出现下述资源分配情况(5 个进程，3 类资源)：试问：

（1）(6 分)该状态是否安全？若是，请给出安全序列,要求写出详细推导过程。若不是，也请说明具体原因。（要求：回答安全状态与否均要求写出具体推导过程）（2）（4 分）若 P3 提出请求 Request(0，0，2)后，系统能否将资源分配给它？为什么？（能和不能均要求写出各自的详细理由）。 44.(10 分)考虑下述页面走向： 4，3，2，1，4，3，5，4，3，2，1，5 当内存物理块数量分别为 3 和 4 时，试问先进先出 FIFO、最佳页面算法 OPT 这两种置换算法的缺页次数和置换次数分别是多少？要求写出各自详细的缺页置换过程。最后，就上述两种算法的产生缺页结果，简单说说你能从中有何发现？ 41.(10 分)完成程序:假定系统有三个并发进程为 in,outA 和 outB，它们共享缓冲器 buf(容量为 1)。约定：仅当缓冲器空时，进程 in 才可以把读入的数据放入（PUT）到缓冲器 buf 中。仅当 buf 有数据且该数为奇数时，进程 outA 才可从缓冲器 buf 中取出(GET)数据并打印，若数据为偶数，则由 outB 从缓冲器 buf 中取出(GET)数据并打印，要求上述三个进程协调完成该任务，请用信号量 WAIT 和 SIGNAL 操作写出它们的并发程序；假设开始时，缓冲器为空。

资料库

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

相关推荐

考研

热门标签

最新资料