浙江省中国计量大学数据结构与操作系统考研模拟题

2021年浙江省中国计量大学数据结构与操作系统考研模拟试题一、单项选择题：1～40小题，每题2分，共80分。在每题给出的四个选项中，请选出一项最切合题目要求的。在下边的C语言程序段中，加法操作的时间复杂度为（）。Inti,j,k,sum=0;For(i=0;i<n;++i)For(j=0;j<i*i;++j)Sum++;A．Ο(2n2)B．Ο(2n3)C．Ο(n3)．Ο(n2)对于线性表的描绘正确的选项是（）。A．接见次序表中第k个元素的时间复杂度是Ο(N)B．接见单链表中第k个节点的时间复杂度是Ο(N)C．把新数据插入到次序表中第k个地点的时间复杂度是Ο(1)D．把新数据插入到单链表中第k个地点的时间复杂度是Ο(1)对于行列描绘正确的选项是（）。A．用链表表示行列时，也不能够插队（插队指在行列中间插入新数据）B．用环形数组表示行列时，能够循环使用数组，因此行列永久不会满C．用数组表示行列时，数据入队的时间复杂度是Ο(N)D．用数组表示行列时，数据出队的时间复杂度是Ο(N)对于栈描绘正确的选项是（）。数据出入栈的原则是“先入先出”用数组表示栈时，栈的操作速度要比用链表表示的栈操作快已知一颗完整二叉树的第6层有7个结点，则该完整二叉树总合有多少个结点?（）。对以下图从A出发进行广度优先遍历，正确的选项是（）。A．ABECFDGHB．ADGHFCBEC．ABCDEFGHD．ADCBGHFE7.对下边一个有向图进行拓扑排序，结果正确的选项是（）。A．ABDECB.ABCDEC．ABDCED．ACEBD8.采纳平方探测方法解决矛盾时，散列表的装载因子一般应低于（）。A．0.8B．0.7C．0.6D．0.5一个有序数据序列中有31个数据，采纳二分查找法在此中查找一个数据，最多要比较几次就能获得查找结果（）。当待排记录序列已经按重点字次序有序时，再使用以下算法，其时间复杂度最小的是（）。11.以下图所示这棵树的先序遍历结果是（）。A．ABDCEF

B.ABCDEF

C.BDACEF

D.BDAECF对于散列表的表长度，正确的选项是( )。表长度一定大于数据个数的两倍，且一定是素数数据个数的两倍即可C.数据个数的10倍D.采纳分别链接法时，只需稍大于数据个数即可，且一定是素数13.在有31个节点的二叉排序树中查找一个数据，以下描绘正确的选项是（）。A.最多比较5次就能够获得结果B.可能比较31次才能获得结果C.最多比较6次就能够获得结果D.一定比较30次才能获得结果若数据序列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树的查找效率最高

。已知一个数据序列中有15个数据，且其已经有序摆列，若采纳最快的查找算法和必需的储存结构，在该序列中要查找一个数据元素，则均匀比较次数最少要多少次（）。分别采纳线性表、二叉查找树、AVL树、散列表储存数据并进行查找，以下说法正确的选项是（）。线性表的查找速度最慢散列表的查找速度最快一棵满二叉树共有3层（树根为第一层），则叶子节点个数为（）。20.若要进行大数据（比方：十进制数的位数超出20）之间的数学运算，采纳的数据结构应该是（）。A．图B.二叉树C.链表D.会合21．以下哪一种特征不是操作系统的基本特征？( )A．虚构性B.并行性C.异步性D.共享性设置目前工作目录的主要目的是（）。23.进度从堵塞状态进入就绪状态的原由可能是( )在可变式分划分派方案中，某一作业达成后，系统回收其主存空间，并与相邻安闲区合并，为此需改正安闲区表，造成安闲区数目无变化的状况是( )无上邻安闲区，也无下邻安闲区有上邻安闲区，也有下邻安闲区假定某一机器的内存有4G,硬盘为500G,请问使用虚构内存技术后，其虚构内容的容量为（）在基安分页储存管理中，逻辑地点变换为物理地点时，若页号超出页表长度，则会惹起( )。对于某个进度而言，其运转的场所一定在( )中。A.内存B.硬盘C.SWAPING互换区D.输入井或输出井成组链接法可用于( )A.磁盘安闲盘块的组织B.磁盘的驱动调动C.文件目录的查找D.恳求分页虚构管理中的页面调动以下算法顶用于磁盘调动的是( )A.优先级高者优先算法B.FIFO算法在I/O设施管理中，通道是一种（）。假定磁头目前位于100道，正在向磁道序号增添的方向挪动。现有一个磁道接见恳求序列为35，45，12，68，110，180，170，195，采纳先来先服务调动（FCFS）算法获得的磁道接见序列是（）。A.110,170,180,195,68,45,35,12B.35,45,12,68,110,180,170,195C.110,170,180,195,12,35,45,68D.12,35,45,68,110,170,180,19532.在文件索引分派时，如有一文件的索引块以以下图所示：请问，储存该索引文件总合需占用磁盘多大（几块）（）？33.在基安分页储存管理中，若采纳最正确页面置换算法OPT，则当进度分派到的物理块数目增添时，缺页中止的次数（）可能减少或不变必定减少基安分段内存管理系统中，接见一条指令需要几次接见内存（）？35.某鉴于动向分区储存管理的计算机，假定其主存容量为配（BestFit）算法，分派和开释内存的次序为：分派分派6MB,此时主存中最大安闲区的大小是( )。

55MB(初始为安闲15MB,分派30MB,开释

)，采纳最正确适15MB,分派8MB,36.某计算机系统中有K台打印机，由能达成任务。该系统不行能发存亡锁时，

4个进度竞争使用，每个进度最多需要K的最小值是（）。

3台打印机才采纳SPOOLing技术的主要目的是（）。A.把独占设施改造成共享设施，提升I/O速度B.提升CPU主机效率C.减少用户编程负担D.提升程序的运转速度38．考虑以下页表结构：假定页的大小为512字节（即页内陆点长度为9位），请把以下以十六进制表示的逻辑地点0x567，经过页表变换为物理地点（也用十六进制表示）是（）。A.0x3417B.地点变换错误以下不是设施分派算法的是（）A.先来先服务B.短作业优先C.优先级高的优先D.ABC选项都是对两个并发进度，其互斥信号量为mutex；初值为1，若mutex＝0，则表示（）。A．没有进度进入临界区B．有一个进度进入临界区但没有进度处于堵塞状态C．一个进度进入临界区而另一个进度正处于堵塞状态D．有两个进度进入临界区二、综合应用题：41～45小题，共70分。（25分）带有头、尾节点的双向链表，其节点结构为prev

data

next请设计一个算法对两个有序链表进行合并，

合并结果仍旧要保拥有序。

比如：假定有序链表L1,以以下图所示有序链表L2以以下图所示：合并后结果链表L3为：要求：（1）请描绘算法的基本设计思想（5分）（2）用伪代码描绘算法的详尽实现步骤（5分）（3）请采纳某一程序设计语言写一个函数，其功能是：在双向链表尾部插入新节点。（5分）（4）依据设计思想和实现步骤，采纳某一程序设计语言描绘算法（可C、C++、Java），关键之处请给出简要说明。（5分）（5）请采纳某一程序设计语言写一个函数，其功能是：在双向链表头部删除节点。（5分）（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(近来最少使用)算法这两种内存置换算法的缺页次数和置换次数分别是多少？最后，比较这两种算法后，你有何发现？上述过程