《2016年浙江省中国计量大学数据结构与操作系统考研真题》由会员分享，可在线阅读，更多相关《2016年浙江省中国计量大学数据结构与操作系统考研真题（6页珍藏版）》请在装配图网上搜索。
1、2016年浙江省中国计量大学数据结构与操作系统考研真题一、单项选择题：140小题，每小题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 resultAO( (n2/2)! ) B0(2log2n) C0(n2/2) DO(n2)2.下列排序算法中，需要额外辅助存储空间最多的是（ ）。A归并排序 B快速排序 C堆排序 D直接插入排序3.以下数据结构中，不属于线性表的是
2、（ ）。A. 队列 B. 栈 C. 图D. 循环链表4.下面关于栈的描述中，错误的是（ ）。A先进后出B两头都可以插入和删除C可以用数组来实现D可以用链表来实现5.关于环形（循环）队列，错误的是（ ）。A先进先出 B用数组来实现C可以提高空间的利用率D用循环链表来实现6.层数为8的二叉树其结点个数最多有（ ）。A1023 B511 C255 D1277.有100个结点的无向图要确保是一个连通图至少应有（ ）。A101条边 B99条边 C50条边 D6条边8.关于图的描述，错误的是（ ）。A有向图的邻接矩阵一定是对称矩阵B. 完全图中的边一定比连通图中的边多C深度优先搜索的结果可能不唯一D广度优
3、先搜索的结果可能不唯一9.下列排序算法中，哪个是不稳定的（不稳定指的是：关键字相同的两个数据，排序后它们的先后位置会变化）（ ）。A希尔排序 B简单选择排序 C插入排序 D冒泡排序10.二叉查找树中有1023个结点，查找其中一个数据时，描述正确的是（ ）。A至少要比较10次B最多比较10次C不可能超过10次D如果是平衡二叉查找树，可能要比较1023次11.图1所示这棵树的中序遍历结果是（ ）。AABCDEFB. DBACEF C. DBAECFD. BACCEF图1.树12.往栈中输入序列1,2,，n后再逐个输出，则输出序列的最后一个元素是( )。A不确定 Bn-1 Cn D113.假设N个数
4、据已经放在不同的数据结构，然后进行查找，下列描述错误的是：（ ）。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直接插入排序 C冒泡排序 D归并排
5、序16.把数据1，2，3，4，5，6，7通过插入操作构造一棵二叉查找树，下列描述错误的是（ ）。A按照3,4,1,2,6,7,5的插入顺序构造的二叉查找树，树高为3B按照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个数据，且其已经有序排列，若采用最快的查找算法和必要的存储结构，在该序列中要查找一个数据元素，则平均比较次数最少要多少次（ ）。A512B. 256C. 10D. 118.一棵满二叉树共有1
6、1层（树根为第一层），则叶子节点个数为（ ）。A. 0B. 2048C. 1024D. 51219.若要检查文件中的括号是否匹配，采用的数据结构应该是（ ）。A 图B. 二叉树C. 栈D. 栈20.快递员每天要送很多包裹给客户，为了提高效率，缩短总路程长度，请问该选用什么样的数据结构来设计路线（ ）。A线性表B. 图C.队列D. 二叉树21操作系统是一种( )A实用软件 B.系统软件 C. 应用软件 D. 工具软件22. 设置当前工作目录的主要目的是（ ）。A. 节省外存空间 B. 节省内存空间C. 加快文件的检索速度 D. 加快文件的读/写速度23.进程从阻塞状态进入就绪状态的原因可能是(
7、)A. 被选中占有处理机 B. 等待某一事件发生C. 等待的事件已发生 D. 时间片用完24.在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数无变化的情况是( )A.无上邻空闲区，也无下邻空闲区B.有上邻空闲区，也有下邻空闲区C.有下邻空闲区但无上邻空闲区;或有上邻空闲区但无下邻空闲区D. 以上三种都可以25.假设某一机器的内存有2G,硬盘为300G,请问使用虚拟内存技术后，其虚拟内容的容量为（ ）A. 2G B. 4G C. 300G D.302G26.在基本分段存储管理中，逻辑地址转换为物联地址时，若段号超过段表长度，则会引起
8、( )。A. 输入输出中断 B. 缺段中断 C. 越界中断 D. 缺页中断27.某个进程运行在( )中。A. 内存 B. 硬盘C. SWAPING交换区 D. 硬盘中的某个子目录28.成组链接法可用于( )A.磁盘空闲空间的管理 B.磁盘的驱动调度C.文件目录的查找 D.页式虚拟存贮管理中的页面调度29.下列算法中用于磁盘调度的是( )A. SSTF优先级高者优先算法 B. FIFO先进先出算法C. 时间片轮转法RRD. 最短寻道时间优先30.通道是一种（ ）。A. I/O端口 B. 数据通道C. I/O专用处理机 D. 软件工具31.假设磁头当前位于100道，正在向磁道序号增加的方向移动。现
9、有一个磁 道访问请求序列为28，55，12，68，110，180，170，195，采用先来先服务调度（FCFS）算法得到的磁道访问序列是（ ）。A. 110,170,180,195,68,55,28,12 B. 28,55,12,68,110,180,170,195C. 110,170,180,195,12,28,55,68 D. 12,28,55,68,110,170,180,19532.在通过索引分配技术时，若某一文件的索引块如下图所示：11421-1-1请问，该索引文件大小总共占有磁盘空间（ ）块？A. 4 B. 7 C. 5 D. 633.在基本分页存储管理中，若采用最佳页面置换算法O
10、PT，则当进程分配到的物理块数增加时，缺页中断的次数会（ ）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. 15MB36. 某计算机系统中有K台打印机，由4个进程竞争使
11、用，每个进程最多需要3台打印机。该系统不可能发生死锁的K的最小值是（ ）。A. 6 B. 10 C. 8 D. 937.采用SPOOLing技术的目的是（ ）。A. 提高独占设备的利用率 B. 提高主机效率C. 减轻用户编程负担 D. 提高程序的运行速度38考虑以下页表结构：页号 块号02152139假设页的大小为512字节, 即页内地址长度为 9 位，请把以下以十六进制表示的逻辑地址0x967，通过页表转换为物理地址（也用十六进制表示）是 （ ）。A. 0x3417 B. 地址转换错误 C. 0x367 D. 0x56739. 以下不是设备分配算法的是（ ）A. 先来先服务 B. 短作业优先
12、C. 优先级高的优先 D. 以上几种都不是40. 对两个并发进程，其互斥信号量为mutex；初值为1，若mutex0，则表明（ ）。A没有进程进入临界区B有一个进程进入临界区但没有进程处于阻塞状态C一个进程进入临界区而另一个进程正处于等待进入临界区状态D 有两个进程进入临界区二、综合应用题：4145小题，共70分。41.带有头节点的单链表，其节点结构为datanext带有头结点的单链表如下图所示请设计一个算法对两个有序单链表L1，L2进行求交的操作，得到新的链表L3，L3仍然保持有序的状态，要求：（1） 请描述算法的基本设计思想（5分）（2） 用伪代码描述算法的详细实现步骤（5分）（3） 根据
13、设计思想和实现步骤，采用某一程序设计语言写一个函数来实现该算法，请先给出结点类型的定义。（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分）43. 在银行家算法中，若
14、出现下述资源分配情况(5个进程，4类资源)：process Max (最大需求) Allocation（已分配） Available（系统资源）A B C D A B C DA B C DP12 7 5 0 1 0 0 0 1 6 2 2P20 6 6 10 0 0 1 4P33 6 10 9 1 3 5 4P40 9 8 4 0 3 3 2P50 0 4 3 0 0 3 1试问：（1）(6分) 该状态是否安全？若是，请给出其中一个安全序列，若不是，也请说明原因。要求：是否安全状态均要求写出具体推导过程。（2）（4分）若P3提出请求Request(1，2，1,1)，系统能否将资源分配给它？为什
15、么？要求详细说明你的理由。44.(10分) 考虑下述页面走向：6，7，2，1，6，7，5，6，7，2，1，5当内存物理块数量分别为3和4时，试问FIFO（先进先出）、LRU(最近最少使用)算法这两种内存置换算法的缺页次数和置换次数分别是多少？最后，比较这两种算法后，你有何发现？上述过程要求分别写出详细的置换过程。45.（10分）用类C语言来完成程序，尝试用学过的信号量操作解决以下问题：有一个家庭，有父、子、女三人，爸爸负责不停地把水果放到盘中，假设一次只能允许放一个水果，水果品种分为苹果和香蕉两种，限制条件是儿子只能从盘中取苹果吃，女儿只能从盘中取香蕉吃，请你用信号量WAIT和SIGNAL操作实现这三个人的进程并发操作，假设开始时盘中为空。
2016年浙江省中国计量大学数据结构与操作系统考研真题
