国家开放大学2023-2024学年《数据结构与算法》模拟试卷及答案解析1（2024年）.docx
国家开放大学2023-2024学年数据结构与算法模拟试卷及答案解析模拟试题1一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题，每小题3分，共45分）1 .对于数据结构的描述，下列说法中错误的是（）<,A.一种逻辑结构只能对应一种存储结构B,算法的设计依赖于数据的逻辑结构C.对数据结构基本操作的实现与存储结构有关D.数据的存储结构是数据的逻辑结构的机内实现2 .在一个长度为n的顺序表中（元素编号从0开始）的第i个位置上删除一个元素（0i<n）,需要向前移动（）个元素。A.n-iB.n-i+1C.n-i-1D.i+13 .栈和队列的共同特点是（）oB.都是先进后出D.没有共同点A.只允许在端点处插入和删除元素C.都是先进先出4 .设循环队列的元素存放在一维数组Q30中,head指向队头元素,tail指向队尾元素的后一个位置。若个位置5,tail=5,则该队列中的元素个数为（）。A.20B.10C.9D.115 .字符串S="DataStrUCtUre”的长度为()。A.13B.2C.14D.76 .广义表G=(a,(b,c)的表尾是()。A.aB.(b,c)C.(a)D.(b,c)7 .二叉树有22个叶结点，则它有（）个2度结点。A.21B.20C.23D.不确定8 .高度为h的二叉树最少有（）个结点。D. h-1A.hB.h*（h+1）C.h*（h+l）29. n个顶点的连通图最少有（）条边。A. n× (n-l)B. n× (n-l)2C. n-1D. n10 .设无向图G=（VE）和G=（V；E）,如果G是G的生成树,则下面的说法中错误的是（）。A.G，为G的子图B.G，为G的连通分量C.G，为G的极小连通子图且V=VD.G，是G的一个无环子图11 .按12,24,36,90,52,30的顺序构成的二叉排序树，其根结点是（）。A.12B.24C.52D.3612 .设一组初始记录关键字序列为（13,18,24,35,47,50,62）,则利用折半查找过程中第一个比较的关键字是（）.A.13B.50C.47D.3513 .堆的形状是一棵（）。A.完全二叉树B.满二叉树C.二叉排序树D判定树14 .快速排序的最坏情况下的时间复杂度为（）。A.O（n2）B.O（nlog211）C.O（n）D.O（n,3）15 .贪心算法解决的问题应满足（）。A.贪心选择性质和最优子结构性质B.贪心选择性质和独立子问题性质C.最优子结构性质和重叠子问题性质D.试探和回溯性质二、判断题（正确的在括号内打上“”，错误的打上“X”。本题共15个小题，每小题2分，共30分）16 .算法的五个基木特征是输入、输出、有穷性、确定性、可行性。（）17 .顺序表会开辟连续的存储空间存储数据。（）18 .已知入栈的序列是ABCD,则出栈序列可以是ABCD。（）19 .队列中插入元素在队头进行，删除元素在队尾进行。（）20 .字符串是一种操作受限的线性表。（）21 .下三角矩阵压缩存储时元素的位置能通过下标ij找到。（）22 .哈夫曼树是最优二叉树。（）23 .线索链表存储结构的结点结构和二叉链表存储结构的结点结构完全相同。（）24 .有向图无法进行深度优先遍历。（）25 .图的存储结构有邻接矩阵存储结构和邻接表存储结构。（）26 .顺序查找中待查元素为首元素时比较元素的次数最少。（）27 .散列查找中，冲突越多，散列查找效率越高。（）28 .归并排序的空间复杂度是0（1）。（）29 .直接插入排序与简单选择排序相比记录移动次数更少。（）30 .用分治法解决的问题分解为子问题时子问题相互独立。（）三、综合题（本题共5个小题，每题5分，共25分）31 .请根据程序注释为下面程序中空缺的和位置选择正确的语句。List<String>list=newArrayLiSt<String>（）;/创建顺序表list.add（1'A）;添加数据A到线性表中list.;添加数据B到线性表中list.；删掉下标为1的元素A.remove（1）;B.add（"B）C.set（"B"）D.get（l）32 .现有完全二叉树顺序存储结构如下图所示，则ABCDEFGH012345675号结点F的双亲结点是（D .3号结点DA.2号结点CB.4号结点EC.1号结点B该二叉树的层序遍历结果为（）。A .(ABCDEFGH) B. (ABDHECFG)C.(HDBEAFCG) D.(HDEBFGCA)33 .如下图所示有向图，从1顶点开始，其拓扑排序序列可以为或者或者。A .(123564)B.(125634)C.( 125364)D.( 123456)34 .现有关键字序列4L68,13,25,15,48),散列函数为HaSh(Key)=Key%13,散列表长为13,则41的散列地址为，41和是同义词。 A.2B.3C.0D.13 A.13B.15C.68D.2535.对一组关键字序列30851578063345进行快速排序（30为基准值），第一趟扫描排序结果为Q;若对该关键字序列30851578063345进行两两归并排序，第一趟两两归并排序结果为.A. 06 15B.06 85C.30 15D. 30 8533 4533 4545 8533 45307885157830780633157806数据结构与算法模拟试题2参考答案及评分标准一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题，每小题3分，共45分）IAIlA2C3A4B7A8 A9C12D13A14A5CIOB15A二、判断题（正确的在括号内打上“J”，错误的打上“X”。本题共15个小题，每小题2分，共30分）16171819×20×212223X24×252627×28×29×30三、综合题（本题共5个小题，每题5分，共25分）31BA32AA33ABC34AB35AD
