计算机考研每日一题单选题100道及答案

计算机考研每日一题单选题道及答案100在一个采用页式存储管理的系统中，页表存放在内存中如果访问内存的时间是一次

1.

0.2US,页面访问的时间是多少（假设页面不在内存时需要从磁盘读取页面，磁盘读取页面时间为）10ms,当发生缺页时？口A.10ms+

0.2sB.10ms+

0.4u sC.10ms口D.

0.2s答案A解析发生缺页时，要先从磁盘读取页面（）再访问内存中的页表（）所以一次页10ms,

0.2us,面访问时间是10ms+

0.2u So某二叉树的前序遍历序列为中序遍历序列为则该二叉树的后序遍历

2.ABCDEFG,CBDAEGF,序列是？A.CDBGFEAB.CDBFGEAC.CDBAGFED.CDBEGFA答案B解析根据前序和中序遍历序列可构建出二叉树，进而得出后序遍历序列为CDBFGEA以下哪种排序算法在最坏情况下的时间复杂度最低？

3.冒泡排序A.选择排序B.堆排序C.插入排序D.答案C解析冒泡、选择、插入排序在最坏情况下时间复杂度为

（十），堆排序在最坏情况下时间复杂度为（）O nlogn一个具有个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是？

4.10A.10X10B.9X9C.11X11D.8X8答案A解析邻接矩阵的大小是顶点数乘以顶点数，有个顶点则矩阵大小为义101010若一个栈的输入序列为以下哪个不可能是其输出序列？

5.123,4,」A.4,3,2B.3,4,2,1』,C.42,3』D.2,3,4答案C解.栈是后进先出的数据结构，先出栈说明、、都在栈中，此时只能先出栈，所以』,4123342,3不可能是输出序列在操作系统中，进程的状态不包括以下哪种？

6.运行态A.就绪态B.阻塞态C.会？从阻塞态直接进入运行态A.从阻塞态进入就绪态B.继续保持阻塞态C.终止D.答案B解析操作完成后，进程等待的事件已发生，从阻塞态进入就绪态等待调度I/O以下关于图的连通性，说法正确的是？

55.无向图的连通分量是图中的极大连通子图A.有向图的强连通分量是图中的极大强连通子图B.一个无向图是连通图当且仅当图中任意两个顶点之间都有路径C.以上说法都正确D.答案D解析无向图的连通分量是极大连通子图，有向图的强连通分量是极大强连通子图，无向图连通的定义就是任意两顶点有路径一个具有个元素的有序数组，采用折半查找，查找失败时的平均查找长度约为？

56.nA.log2n（）B.Iog2n+1C.n/2D.n答案B解析折半查找查找失败时平均查找长度约为）logXn+l以下关于操作系统的文件目录，说法错误的是？

57.文件目录的主要作用是实现文件的按名存取A.单级目录结构可以解决文件重名问题B.多级目录结构可以提高文件查找效率C.目录项中包含文件的基本信息D.答案B解析单级目录结构不能解决文件重名问题，多级目录结构可以解决且能提高查找效率，文件目录主要实现按名存取，目录项包含文件基本信息一个有向图的邻接矩阵中，第列元素之和表示？

58.j顶点的入度A.j顶点的出度B.j顶点的度C j图的边数D.答案A解析有向图邻接矩阵第列元素之和表示顶点的入度j j以下哪种数据结构适合用于实现队列？

59.数组A.栈B.链表C.和都可以D.A C答案D解析数组和链表都可以实现队列，分别为顺序队列和链队列在一个采用页面置换算法的系统中，若采用最近最少使用（）算法，当发生缺页时，应

60.LRU淘汰？最先进入内存的页面A.最近最久未使用的页面B.随机选择一个页面C.驻留时间最长的页面D.答案B解析算法淘汰最近最久未使用的页面LRU以下关于算法的复杂度分析，说法正确的是？

61.最好情况下的时间复杂度一定小于最坏情况下的时间复杂度A.平均情况下的时间复杂度一定介于最好和最坏情况之间B.空间复杂度只考虑算法执行过程中的临时变量C..时间复杂度和空间复杂度没有任何关系D答案B解析平均情况下的时间复杂度通常介于最好和最坏情况之间最好情况时间复杂度不一定小于最坏情况，空间复杂度不仅考虑临时变量，时间复杂度和空间复杂度有时存在相互制约关系一个无向图的邻接表存储中，所有链表的结点数之和是图的？

62.顶点数A.边数B.边数的倍C.2顶点数的倍D.2答案C解析无向图邻接表中，每条边对应两个表结点，所以所有链表结点数之和是边数的倍2以下哪种排序算法是不稳定的，但在平均情况下效率较高？

63.冒泡排序A.插入排序B.快速排序C.归并排序D.答案C解析快速排序是不稳定排序算法，平均时间复杂度为效率较高冒泡和插入排序是Onlogn,稳定排序，归并排序也是稳定排序一个进程的状态从就绪态转换为运行态是因为？

64.时间片用完A.被更高优先级进程抢占B.获得资源C.CPU等待的事件发生D.答案C解析就绪态的进程获得资源后转换为运行态时间片用完是从运行态转就绪态，被更CPU高优先级进程抢占也是从运行态转就绪态，等待的事件发生是从阻塞态转就绪态在一个哈希表中，若哈希函数为采用二次探测法解决冲突，当插入元素

65.Hkey=key%10,发生冲突时，下一个探测地址可能是？23A.4B.5C.6D.7答案A解析H23=23%10=3,发生冲突时，二次探测法下一个探测地址可能是3+I2%10=4o以下关于图的生成树，说法错误的是？

66.一个连通图的生成树是图的一个极小连通子图A.一个连通图的生成树包含图的所有顶点B.一个连通图的生成树的边数等于顶点数减C.1一个连通图的生成树是唯一的D.答案D解析连通图的生成树是极小连通子图，包含所有顶点，边数等于顶点数减但生成树不唯一1,一个栈的输入序列为若输出序列的第二个元素是则输出序列的第四个元素可能

67.2,4,6,8,10,8,是？A.2B.4C.6D.10答案B解析:输出序列第二个元素是说明已入栈出栈,后续出栈顺序可能为等,8,2,4,6,8,86,4所以第四个元素可能是4o以下关于操作系统的死锁预防，说法正确的是？

68.破坏互斥条件可以预防死锁，但在实际中很难实现A.破坏占有并等待条件可以通过一次性分配所有资源来实现B.破坏不剥夺条件可以允许进程抢占其他进程的资源C.以上说法都正确D.答案D解析破坏互斥条件实际难实现，破坏占有并等待可一次性分配资源，破坏不剥夺条件可允许进程抢占资源一个具有个顶点的有向图，其邻接矩阵中非零元素的个数最多为？

69.nA.nn-1B.nn-1/2C.n2D.2n答案A解析有向图邻接矩阵非零元素最多时为有向完全图，个数为nn-lo以下哪种数据结构适合用于实现优先队列？

70.数组A.链表B.堆C.栈D.答案C解析堆是实现优先队列的常用数据结构，能高效地进行插入和删除操作数组和链表也可实现但效率不如堆，栈不适合实现优先队列在一个采用分页存储管理的系统中，若页表存放在内存中，访问一次内存需要若要实

71.200ns,现一次页面访问，且该页面在内存中，需要的时间是？A.200nsB.400nsC.600nsD.800ns答案B解析先访问页表再访问页面共200ns,200ns,400nso以下关于二叉树的线索化，说法错误的是？

72.线索二叉树可以加快查找前驱和后继结点的速度A.中序线索二叉树的线索是按照中序遍历的顺序建立的B.线索二叉树中每个结点的左右指针一定指向其前驱和后继结点C.线索二叉树可以节省存储空间D.答案C解析线索二叉树中只有空指针才作为线索指向其前驱或后继结点，不是每个结点的左右指针都指向其前驱和后继结点以下哪种排序算法在最坏情况下的时间复杂度与平均情况下的时间复杂度相同？

73.冒泡排序A.选择排序B.插入排序C.快速排序D.答案B解析选择排序在最坏和平均情况下时间复杂度都是OS,冒泡和插入排序最坏是On2,平均接近快速排序最坏是平均是0/,0/,Onlogn一个进程在运行过程中，因为请求的资源得不到满足而进入阻塞态，当资源可用时，该进

74.程会？从阻塞态直接进入运行态A.从阻塞态进入就绪态B.继续保持阻塞态C.终止D.答案B解析资源可用时，进程等待的事件发生，从阻塞态进入就绪态等待调度以下关于图的遍历，若从某一顶点开始进行深度优先遍历和广度优先遍历，得到的遍历序

75.列中第一个顶点相同，则以下说法正确的是？深度优先遍历和广度优先遍历得到的序列一定相同A.深度优先遍历和广度优先遍历得到的序列一定不同B.深度优先遍历和广度优先遍历得到的序列可能相同C.以上说法都不正确D.答案C解析虽然起始顶点相同，但深度优先和广度优先遍历方式不同，得到的序列可能相同也可能不同一个具有个元素的数组，采用折半查找，若要查找的元素不在数组中，最多需要比较的

76.n次数是？A.log2nB.Iog2n+1「乂C.log n+l1D.log njL2答案C解析折半查找查找失败时最多比较次数是「］log/n+l以下关于操作系统的文件系统，若文件采用顺序结构存储，以下说法错误的是？

77.文件顺序存储适合顺序访问A.文件顺序存储不适合随机访问B.文件顺序存储的空间利用率高C.文件顺序存储在插入和删除操作时效率高D.答案D解析文件顺序存储适合顺序访问，不适合随机访问，空间利用率高，但插入和删除操作效率低一个有向图的邻接表中，若某个顶点的链表为空，则该顶点？

78.入度为A.0出度为B.0度为C.0没有任何意义D.答案B解析有向图邻接表中顶点链表为空表示该顶点没有出边，即出度为Oo以下哪种数据结构适合用于实现递归函数的调用栈？

79.数组A.栈B.链表C.队列D.答案B解析递归函数的调用和返回符合栈后进先出的特性，适合用栈实现调用栈在一个采用页面置换算法的系统中，若采用先进先出算法，当发生缺页时，应淘汰？

80.FIFO最先进入内存的页面A.最近最久未使用的页面B.随机选择一个页面C.驻留时间最长的页面D.答案A解析算法淘汰最先进入内存的页面FIFO以下关于算法的渐近表示，说法正确的是？

81.表示法表示算法的时间复杂度的上界A.0表示法表示算法的时间复杂度的下界B.Q表示法表示算法的时间复杂度的精确界C.0以上说法都正确D.答案D解析表示法描述算法时间复杂度的上界，表示法描述下界，®表示法描述精确界，所以O以上说法都正确一个无向图的连通分量个数为若要将其变为连通图且添加的边数最少，添加边的方式

82.3,是？任选个连通分量，两两相连A.3从一个连通分量向另外两个连通分量各连一条边B.从一个连通分量向另外两个连通分量各连两条边C.随机连接不同连通分量的顶点D.答案B解析要将个连通分量变为连通图，最少添加条边这里从一个连通分量向另外两k k-1k=3,个连通分量各连一条边可使图连通且边数最少以下哪种排序算法在处理小规模数据时效率较高

83.归并排序A.快速排序B.插入排序C.堆排序D.答案C解析插入排序在处理小规模数据时，由于其代码简单，常数因子小，效率较高而归并排序、快速排序和堆排序在处理大规模数据时优势更明显一个进程在执行过程中被信号中断，中断处理完成后，该进程的状态通常是？

84.运行态A.就绪态B.阻塞态C.终止态D.答案A解析进程被信号中断，中断处理完成后通常会继续之前的执行，所以状态仍为运行态在一个哈希表中，若哈希函数为尸采用链地址法解决冲突，插入元素、、

85.Hkey key%7,1421后，在地址为的链表中元素个数为？280A.1B.2C.3D.0答案C解析:所以地址为的链表中有个元素H14=14%7=0,H21=21%7=0,H28=28%7=0,03以下关于图的最小生成树，若使用普里姆算法从顶点开始构建最小生成树，在算

86.Prim v法执行过程中，以下说法正确的是？每次选择的边一定是与已加入树的顶点相连的边中权值最小的边A.每次选择的边一定是图中权值最小的边B.算法执行过程中，已加入树的顶点集合是固定不变的C.算法的时间复杂度与图的边数成正比D.答案A解析算法每次从与已加入树的顶点相连的边中选择权值最小的边加入生成树不是选择Prim图中权值最小的边，已加入树的顶点集合不断变化，其时间复杂度与顶点数有关，不是与边数成正比一个栈的输入序列为若输出序列的第三个元素是则输出序列的第一个元素可

87.3,6,9,12,15,9,能是？A.3B.6C.12D.15答案B解析输出序列第三个元素是说明、、已入栈，出栈，此时输出序列第一个元素可能9,3699是6o以下关于操作系统的进程调度，若采用时间片轮转调度算法，时间片设置过短会导致？

88.A.系统开销增大进程响应时间变长B.进程平均周转时间变长C.以上都对D.答案A解析时间片设置过短，进程频繁切换，会使系统开销增大而进程响应时间可能会变短,进程平均周转时间不一定变长一个具有个顶点的无向完全图，删除一条边后，图的连通性是？

89.n一定不连通

1.一定连通

8.可能连通也可能不连通C.无法确定D.答案B解析无向完全图中任意两个顶点都有边相连，删除一条边后仍然是连通的以下哪种数据结构适合用于实现图的深度优先遍历的辅助数据结构？

90.栈A.队列B.数组C.链表D.答案A解析深度优先遍历的过程符合栈后进先出的特点，用栈作为辅助数据结构可以方便地实现深度优先遍历在一个采用分段存储管理的系统中，若段表存放在内存中，访问一次内存需要若要访

91.150ns,问一个逻辑地址对应的物理地址，且该段在内存中，需要的时间是？A.150nsB.300nsC.450nsD.600ns答案B解析先访问段表（）确定段的位置，再访问内存中的段（）共150ns150ns,300nso以下关于二叉树的高度，若一棵二叉树有个结点，其高度最大为？

92.10A.4B.5C.9D.10答案C解析当二叉树退化为单支树时高度最大，有个结点的二叉树高度最大为109o以下哪种排序算法在初始数据基本逆序的情况下性能最差？

93.冒泡排序A.选择排序B.插入排序C.希尔排序D.答案C解析插入排序在初始数据基本逆序时，每次插入都要移动大量元素，性能最差冒泡排序和选择排序受初始数据顺序影响相对较小，希尔排序性能也比插入排序好一个进程从阻塞态转换为就绪态，以下哪种情况不可能导致？

94.等待的操作完成A.I/O等待的信号到达B.时间片用完C.等待的资源可用D.答案c解析时间片用完是从运行态转换为就绪态，而等待的操作完成、信号到达、资源可用会I/O使进程从阻塞态转换为就绪态以下关于图的拓扑排序，若一个有向图存在拓扑排序，则该图？

95.一定是有向无环图（）A.DAG一定是有向连通图B.一定是无向图C.一定是完全图D.答案A解析只有有向无环图才有拓扑排序，有拓扑排序的图不一定是有向连通图、无向图或完全图一个具有个元素的有序数组，采用折半查找，查找第个元素（）最多需要比

96.n k1W kW n,较的次数是？A.log n2（）B.lo kg2（）C.T log2n+11D.log njL2答案C解析折半查找不管查找哪个元素，最多比较次数都是「）log/n+l1以下关于操作系统的文件共享，若采用基于索引结点的共享方式，以下说法错误的是？

97.多个用户可以共享同一个索引结点A.共享文件时，用户的目录项指向同一个索引结点B.对共享文件的修改会影响所有共享该文件的用户C.索引结点中不包含文件的物理地址D.答案D解析索引结点中包含文件的物理地址等信息，多个用户可共享同一个索引结点，共享时目录项指向同一索引结点，对共享文件修改会影响所有共享用户一个有向图的邻接矩阵中，若主对角线元素都不为则该图？

98.0,一定有自环A.一定是连通图B.一定是有向完全图C.一定没有回路D.答案A解析邻接矩阵主对角线元素不为表示每个顶点都有到自身的边，即一定有自环不能据此0判断图是否连通、是否为有向完全图或有无回路以下哪种数据结构适合用于实现一个先进先出的缓存？

99.栈A.队列B.堆C.哈希表D.答案B解析队列是先进先出的数据结构，适合用于实现先进先出的缓存栈是后进先出，堆主要用于实现优先队列，哈希表用于快速查找在一个采用页面置换算法的系统中，若采用时钟（）算法，当发生缺页时，扫描到

100.Clock一个页面的访问位为则该页面？0,直接淘汰A.将访问位设为继续扫描B.1随机选择是否淘汰C.等待一段时间后再淘汰D.答案A解析时钟算法中，扫描到访问位为的页面时直接淘汰，若访问位为则将其设为继续扫010描挂起态D.答案D解析进程基本状态有运行态、就绪态、阻塞态，挂起态不是基本状态,对于一个具有个顶点和条边的无向图，采用邻接表存储时，表头结点和表结点的总数是？7n eA.n+2eB.n+eC.2n+eD.2n+2e答案A解析表头结点数为每条边对应两个表结点，所以表结点数为总数是n,2e,n+2e以下关于算法的时间复杂度，说法正确的是？

8.时间复杂度只取决于问题的规模A.时间复杂度与算法的具体实现无关B.时间复杂度是指算法执行的绝对时间C.时间复杂度是指算法执行的基本操作次数与问题规模之间的增长关系D.答案D解析时间复杂度是描述算法执行的基本操作次数与问题规模之间的增长关系，不是绝对时间，也受算法实现影响一个完全二叉树有个结点，其叶子结点数是？

9.100A.50B.49C.51D.48答案A解析根据完全二叉树的性质，设总结点数为当为偶数时，叶子结点数为所以个n,n n/2,100结点的完全二叉树叶子结点数是50o若用一个大小为的数组来实现循环队列，且当前和的值分别为和当从队列

10.6rear front3,中删除一个元素，再插入两个元素后，和的值分别为？和rear frontA.24和B.14和C.23和D.13答案A解析删除一个元素插入两个元素front=front+1%6=4,rear=rear+2%6=2以下哪种查找算法在有序表上的平均查找长度最小？

11.顺序查找A.折半查找B.分块查找C.哈希查找D.答案B解析顺序查找平均查找长度为折半查找平均查找长度为分块查找介于两者n+1/2,log/n+l-l,之间，哈希查找平均查找长度接近但有冲突情况，有序表上折半查找平均查找长度最小1一个进程从运行态转换为阻塞态的原因可能是

12.时间片用完A.被更高优先级进程抢占B.等待某一事件发生C.进程完成任务D.答案C解析时间片用完或被更高优先级进程抢占会从运行态转为就绪态，进程完成任务会结束,等待某一事件发生会从运行态转为阻塞态以下关于图的遍历，说法错误的是？

13.深度优先遍历和广度优先遍历都可以遍历图的所有顶点A.深度优先遍历使用栈实现，广度优先遍历使用队列实现B.深度优先遍历和广度优先遍历的时间复杂度相同C.深度优先遍历和广度优先遍历得到的遍历序列一定相同D.答案D解析深度优先遍历和广度优先遍历都能遍历图的所有顶点，分别用栈和队列实现，时间复杂度相同，但遍历序列不一定相同一个具有个元素的有序数组，采用折半查找，查找成功时的平均查找长度约为？

14.nA.log n2B.n/2C.nD.210g2n答案A解析折半查找在有序数组中查找成功时平均查找长度约为log no2若要对一个包含个元素的数组进行快速排序，其最坏情况下的时间复杂度是？

15.100A.OnB.OnlognC.On2D.Ologn答案C解析快速排序在最坏情况下，如数组已经有序，时间复杂度为0/以下关于操作系统的文件系统，说法正确的是？

16.文件系统只负责文件的存储A.文件系统不管理文件的访问权限B.文件系统可以实现文件的逻辑组织和物理组织C.文件系统不处理文件的共享和保护D.答案C解析文件系统不仅负责文件存储，还管理访问权限、处理文件共享和保护，能实现文件的逻辑组织和物理组织一个有向图的邻接矩阵中，第行元素之和表示？

17.i顶点的入度A.i顶点的出度B.i顶点的度C.i图的边数D.答案B解析有向图邻接矩阵第行元素之和表示顶点的出度i i以下哪种数据结构不适合用于实现优先队列？

18.数组A.链表B.堆C.栈D.答案D解析栈是后进先出的数据结构，不适合实现优先队列，堆、数组、链表都可用于实现优先队列在一个采用虚拟存储管理的系统中，页面置换算法有多种，以下哪种算法性能最好？

19.先进先出（）算法A.FIFO最近最少使用（）算法B.LRU时钟（）算法C.Clock随机置换算法D,答案B解析算法依据页面的使用频率和最近使用情况，能较好地反映程序的局部性原理，性能LRU相对较好一个二叉排序树中，删除一个结点后，要保持其仍然是二叉排序树，以下操作正确的是？

20.直接删除该结点A.用其左子树中的最大结点替换该结点B.用其右子树中的最小结点替换该结点C.以上操作都不正确D.答案C解析在二叉排序树中删除结点，通常用其右子树中的最小结点替换该结点，可保持二叉排序树性质以下关于算法的空间复杂度，说法错误的是？

21.空间复杂度是指算法执行过程中所占用的存储空间A.空间复杂度只考虑算法的额外存储空间B.递归算法的空间复杂度可能较高C.空间复杂度与问题的规模无关D.答案D解析空间复杂度与问题规模有关，一般是问题规模的函数，它指算法执行过程中占用的存储空间，包括额外存储空间，递归算法可能因栈深度问题空间复杂度较高一个无向图的连通分量个数为若要将其变为连通图，至少需要添加的边数是？

22.k,A.k-1B.kC.k+1D.2k答案A解析要将个连通分量的无向图变为连通图，至少需要添加条边k k-1以下哪种排序算法是稳定的？

23.快速排序A.堆排序B.归并排序C希尔排序D.答案C解析快速排序、堆排序、希尔排序是不稳定排序算法，归并排序是稳定排序算法一个进程的（进程控制块）中不包含以下哪种信息？

24.PCB进程标识符A.进程状态B.程序代码C.进程优先级D.答案C解析包含进程标识符、进程状态、进程优先级等信息，不包含程序代码PCB在一个哈希表中，采用链地址法解决冲突，若哈希表的大小为有个元素，则平均查找

25.m,n长度约为？A.n/mB.1+n/m汨C.logD.n答案B解析链地址法解决冲突时，平均查找长度约为1+n/m以下关于图的最小生成树，说法正确的是？

26.一个图的最小生成树是唯一的A.普里姆算法和克鲁斯卡尔算法都能得到图的最小生成树B.Prim Kruskal普里姆算法的时间复杂度与图的边数有关C.克鲁斯卡尔算法的时间复杂度与图的顶点数有关D.答案B解析一个图的最小生成树不一定唯一，普里姆和克鲁斯卡尔算法都可求最小生成树，普里姆算法时间复杂度与顶点数有关，克鲁斯卡尔算法时间复杂度与边数有关一个栈的初始状态为空，现将元素依次入栈，然后依次出栈，出栈序列是？

27.123,4,5A.1,2,345』B.543,2C.2,3,4,5,1』,D.3,4,52答案B解析栈是后进先出的数据结构，依次入栈再出栈，出栈序列是5,4,321以下关于操作系统的死锁，说法错误的是？

28.死锁的四个必要条件是互斥条件、占有并等待条件、不剥夺条件和循环等待条件A.可以通过破坏死锁的四个必要条件之一来预防死锁B.银行家算法是用于检测死锁的算法C.死锁避免是在资源分配时避免系统进入不安全状态D.答案C解析银行家算法是用于避免死锁的算法，不是检测死锁的算法一个具有个顶点的有向完全图，其边数是？

29.nA.nn-1/2B.nn-1C.n2D.n答案B解析有向完全图中，每个顶点都与其他个顶点有两条方向相反的边，所以边数是n-1nn以下哪种数据结构适合用于实现图的广度优先遍历？

30.栈A.队列B.数组C.链表D.答案B解析广度优先遍历使用队列来实现在一个采用分页存储管理的系统中，页的大小为逻辑地址空间为位，则页号的位

31.4KB,32数是？A.10B.12C.20D.22答案C解析页大小为逻辑地址空间位，页号位数为位4KB=212B,3232-12=20以下关于二叉树的遍历，说法正确的是？

32.前序遍历和中序遍历可以唯一确定一棵二叉树A.前序遍历和后序遍历可以唯一确定一棵二叉树B.中序遍历和后序遍历不能唯一确定一棵二叉树C.只有三种遍历序列都知道才能唯一确定一棵二叉树D.答案A解析前序遍历和中序遍历、中序遍历和后序遍历可以唯一确定一棵二叉树，前序遍历和后序遍历不能唯一确定以下哪种排序算法的比较次数与初始数据的排列顺序无关？

33.冒泡排序A.选择排序B.插入排序C.快速排序D.答案B解析选择排序无论初始数据排列如何，比较次数都是固定的，冒泡、插入、快速排序比较次数与初始数据排列有关一个进程从阻塞态转换为就绪态的原因可能是？

34.等待的事件发生A.时间片用完B.被更高优先级进程抢占C.进程完成任务D.答案A而析等待的事件发生，进程从阻塞态转为就绪态，时间片用完或被更高优先级进程抢占是从运行态转就绪态，进程完成任务会结束以下关于图的拓扑排序，说法错误的是？

35.拓扑排序只能用于有向无环图A.DAG拓扑排序可以得到图的所有顶点的一个线性序列B.拓扑排序的时间复杂度是其中是顶点数，是边数C.On+e,n e拓扑排序的结果是唯一的D.答案D解析拓扑排序只能用于有向无环图，能得到顶点的线性序列，时间复杂度是结果不On+e,唯一一个具有个元素的数组，采用顺序查找，查找不成功时的平均查找长度是？

36.nA.nB.n+1C.n+1/2D.n/2答案B解析顺序查找不成功时要比较次，平均查找长度是n+1n+1以下关于操作系统的内存管理，说法正确的是？

37.内存管理只负责内存的分配和回收A.虚拟存储技术可以解决内存不足的问题B.分页存储管理不需要进行地址转换C.分段存储管理的碎片问题比分页存储管理更严重D.答案B解析内存管理还涉及地址转换等，分页存储管理需要地址转换，分段存储管理碎片问题更严重的说法错误，虚拟存储技术可解决内存不足问题一个有向图的邻接表中，第个链表的结点数表示？

38.i顶点的入度A.i顶点的出度B.i顶点的度C.i图的边数D.答案B解析有向图邻接表中第个链表的结点数表示顶点的出度i i以下哪种数据结构适合用于实现递归算法？

39.栈A.队列B.数组C.链表D.答案A解析递归算法的调用和返回过程符合栈后进先出的特点，适合用栈实现在一个采用页面置换算法的系统中，若发生缺页时，页面不在内存中，且内存已满，以下

40.操作正确的是？直接淘汰一个页面A.先将新页面调入内存，再淘汰一个页面B.先淘汰一个页面，再将新页面调入内存C.以上操作都不正确D.答案C解析内存已满时发生缺页，要先淘汰一个页面，再将新页面调入内存以下关于算法的正确性，说法正确的是？

41.算法只要能运行就是正确的A.算法的正确性只与输入数据有关B.算法对于所有合法输入都能得到正确的输出才是正确的C.算法的正确性与时间复杂度和空间复杂度有关D.答案C解析算法对于所有合法输入都能得到正确输出才是正确的，与运行和输入数据、时空复杂度无关一个无向图的邻接矩阵是对称矩阵，若该矩阵的主对角线元素都为则该图？

42.0,一定是连通图A.一定是无环图B.一定没有自环C.一定是完全图D.答案c解析邻接矩阵主对角线元素为表示图中每个顶点没有到自身的边，即一定没有自环不能由此判断图是否连通、有无环以及是否为完全图以下哪种排序算法在数据基本有序的情况下效率最高？

43.冒泡排序A.选择排序B.插入排序C.快速排序D.答案C解析插入排序在数据基本有序时，比较和移动次数较少，效率较高冒泡排序在基本有序时也有一定优势，但插入排序更优选择排序不受数据初始顺序影响，快速排序在基本有序时效率会降低一个进程的时间片用完后，其状态会从运行态转换为？

44.就绪态A.阻塞态B.终止态C.挂起态D.答案A而析时间片用完后，进程暂时停止执行，进入就绪态等待下一次调度在一个哈希表中，若哈希函数为为哈希表大小，采用线性探测法解决

45.Hkey=key%m m冲突，当插入一个元素发生冲突时，下一个探测地址是？A.Hkey+l%mB.Hkey+1C.Hkey-1%mD.Hkey-1答案A解析线性探测法发生冲突时，下一个探测地址是以循环的方式继续查找空位Hkey+l%m,以下关于图的最短路径，说法错误的是？

46.迪杰斯特拉算法可以求单源最短路径A.Dijkstra弗洛伊德算法可以求所有顶点对之间的最短路径B.Floyd迪杰斯特拉算法不能处理负权边的情况C.弗洛伊德算法不能处理负权边的情况D.答案D解析迪杰斯特拉算法不能处理负权边，弗洛伊德算法可以处理负权边，但不能处理负权回路一个栈的输入序列为若输出序列的第一个元素是则输出序列的第三个元素可能

47.135,7,9,9,是？A.1B.3C.5D.7答案B解析输出序列第一个元素是说明都已入栈，出栈顺序为所以第三个元素可9,135,7,9975,3,1,能是而这里选项中只有符合逻辑，因为出栈顺序后续可能还未完整呈现5,3以下关于操作系统的进程同步，说法正确的是

48.进程同步是为了让进程按顺序执行A.信号量机制可以实现进程同步B.临界区是指进程中访问临界资源的那段代码C.以上说法都正确D.答案D解析进程同步目的是让进程按顺序执行，信号量机制可实现进程同步，临界区就是进程中访问临界资源的代码一个具有个顶点的无向图，其边数最多为？

49.nA.nn-1/2B.nn-1C.n2D.n答案A解析无向图边数最多时为完全图，边数为nn-1/2以下哪种数据结构适合用于实现栈？

50.数组A.队列B.链表C.和都可以D.A C答案D解析数组和链表都可以实现栈，数组实现的栈是顺序栈，链表实现的栈是链栈在一个采用段页式存储管理的系统中，逻辑地址分为段号、页号和页内地址，若段号占

51.4位，页号占位，页内地址占位，则逻辑地址空间的大小是？812A.224BB.21沿C.220BD.212B答案A解析逻辑地址空间大小由段号、页号和页内地址位数决定，总位数为位，4+8+12=24所以大小是224Bo以下关于二叉树的性质，说法错误的是？

52.二叉树第层上最多有个结点A.i2深度为的二叉树最多有个结点B.k2k-1任意一棵二叉树中，度为的结点数比度为的结点数多C.021完全二叉树的叶子结点只可能在最后两层D.答案无正确选项此题应是题目有误，四个选项说法均正确解析根据二叉树性质，、、、选项的描述都是正确的A BC D以下哪种排序算法的空间复杂度是

53.01归并排序A.快速排序B.堆排序C.希尔排序D.答案C解析堆排序的空间复杂度是归并排序空间复杂度是快速排序平均空间复杂度是01,On,希尔排序空间复杂度是但综合来看堆排序更典型符合Ologn,01,一个进程在执行过程中，因请求操作而进入阻塞态，当操作完成后，该进程

54.I/O I/O。