}A.O(logn)B.O(n1/2)C.O(n)D.O(nlogn)2.以下关于栈的表达中,错误的选项是2oI.承受非递归方式重写递归程序时必需使用栈II.函数调用时,系统要用栈保存必要的信息III.只要确定了入栈的次序,即可确定出栈次序IV.栈是一种受限的线性表,允许在其两端进展操作A.仅IB.仅I、II、IIIC.仅I、III、IVD.仅II、III、IV3.适用于压缩存储稀疏矩阵的两种存储构造是3。A.三元组表和十字链表_B.三元组表和邻接矩阵C.十字链表和二叉链表D.邻接矩阵和十字链表4.要使一棵非空二叉树的先序序列与中序序列一样,其全部非叶结点须满足的条件是x0A.只有左子树B.只有右子树C.结点的度均为1D.结点的度均为25.一棵二叉树的树形如以下图所示,其后序序列为e,a,c,b,d,g,f,树中与结点a同层的结点是5A.CB.dC.fD.g6.已知字符集{a,b,c,d,e,f,g,h},假设各字符的哈夫曼编码依次是0100,10,0000,0101,001,011,11,0001,则编码序列0100011001001011110101的译码结果是_6_。A.acgabfhB.adbagbbC.afbeagdD.afeefgd7.无向图G含有16条边,其中度为4的顶点个数为3,度为3的顶点个数为4,其他顶点的度均小于3.图G所

一、单项选择题第01~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。01.将一个10×10对称矩阵M的上三角部分的元素m_{i,j}(1 \le i \le j \le 10)按列优先存入C语言的一维数组N中,元素m7,2在N中的下标是()。A.15 B.16 C.22 D.23 02.对空栈S进行Push和Pop 操作,入栈序列为a,b,c,d,e, 经过Push,Push,Pop,Push,Pop,Push, Push,Pop 操作后得到的出栈序列是()。A.b,a,c B.b,a,e C.b,c,a D.b,c,e 03.对于任意一棵高度为5且有10个结点的二叉树,若采用顺序存储结构保存,每个结点占1 个存储单元(仅存放结点的数据信息),则存放该二叉树需要的存储单元数量至少是()。A.31 B.16 C.15 D.10 04.已知森林F及与之对应的二叉树T,若F的先根遍历序列是a,b,c,d,e,f, 中根遍历序列是c,则T的后根遍历序列是()。c，b，a 4 2 5 3 05.下列给定的关键字输入序列中,不能生成如下二叉排序树的是()。3 B.4,5,1,2,3 D.4,2,1,3,5 06.修改递归方式实现的图的深度优先搜索(DFS)算法,将输出(访问)顶点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用

在答题卡指定位置上填写报考单位、考生姓名和考生编号,并涂写考生编号信息点。2.考生须把试题册上的“试卷条形码”黏贴条取下,黏贴在答题卡的“试卷条形码黏贴位置”框中,不按规定黏贴条形码而影响评卷结果的,责任由考生自负。3.选择题的答案必须涂写在答题卡和相应题号的选项上,非选择题的答案必须书写在答题卡指定位置的边框区城内,超出答题区域书写的答案无效;在草稿纸、试题册上答题无效。4.填(书)写部分必须使用黑色字迹签字笔书写，字迹工整、笔迹清楚；涂写部分必须使用2B铅笔涂写。5.考试结束,将答题卡和试题册按规定交回。(以下信息考生必须认真填写)考生编号考生姓名一、单项选择题：01~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。01.下列程序段的时间复杂度是()。 i*=2)for(intj=0; j++A.O(logn)B.O(n)C.O(n \log n)D.O(n^{2})02.给定有限符号集S, in和out均为S中所有元素的任意排列。对于初始为空的栈ST,下列叙述中,正确的是()。A.若in是ST的入

全国硕士研究生入学统一考试计算机科学与技术学科联考2022全国硕士研究生招生考试计算机学科专业基础试题参考答案一、单项选择题01.B02.D03.B04.C05.D06.D07.B08.D09.D10.A11.D12.A13.B14.A15.C16.A17.C18.B19.D20.A21.C22.C23.D24.A25.C26.B27.C28.D29.A30.D31.B32.A33.B34.C35.B36.D37.B38.C39.D40.B01.B。【解析】当外层循环的变量i取不同值时,内层循环就执行多少次,因此总循环次数为i的所有取值之和。假设外层循环共执行k次,当i=1,2,4,8, \cdots ,2^{k-1}(2^{k-1}<n \le 2^{k})时,内层循环执行i次,因此总循环次数T=1+2+4+8+\cdots+2^{k-1}=2^{k}-1,即n<T<2n,时间复杂度为O(n)。02.D。【解析】通过模拟出入栈操作,可以判断入栈序列in和出栈序列out是否合法。因此,已知in序列可以判断out序列是否为可能的出栈序列;已知out序列也可以判断in序列是否为可能的入栈序列,A和B错误。如果每个元素入栈后立即出栈,则in序列和out序列相同,C错误。如果所有元素都入栈后才依次出栈,则in序列和out序列互为倒序,D正确。03.B。【解析】对于此类题，每种情况只需举出一个反例即可。如图1所