2024年浙江省中国计量大学数据构造与操作系统考研真题
一、单项选择题：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) B．0(log2n) C．0(n2) D．O(n) 11.图1所示这棵树的中序遍历结果是〔〕。 A．DBAECF B.ABCDEF C.DBACEF D.DBAEFC 12.设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，那么顺序栈的容量至少应为()。 A.6 B.5 C.4 D.3 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个数据，且其已经有序排列，假设采用最快的查找算法和必要的存储构造，在该序列中要查找一个数据元素，那么平均比拟次数最少要多少次〔〕。 A．10 B.5 C.4 D.1 18.一棵满二叉树共有4层〔树根为第一层〕，那么叶子节点个数为〔〕。 A.15 B.16 C.8 D.7 19.假设要检查源代码文件中的括号是否匹配，采用的数据构造应该是〔〕。 A．图B.二叉树C.栈D.队列 14.假设某快递公司每天要用1辆车去100个地方送货，为尽量减少行车里程，节省汽油，需要事先规划好送货路线，请问该选用什么样的数据构造〔〕。 A．线性表B.图C.队列D.二叉树 21．以下不是操作系统根本特性的是〔〕 A．并发性B.并行性C.虚拟性D.异步性 22.假设某一机器的内存有2G,硬盘为500G,请问使用虚拟内存技术后，其虚拟内存的容量为〔〕 A.2G B.4G C.502G D.500G 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
2014年浙江省中国计量大学数据结构与操作系统考研真题
