国家开放大学2023-2024学年《数据结构与算法》模拟试卷及答案解析2（2024年）.docx
国家开放大学2023-2024学年数据结构与算法模拟试卷及答案解析模拟试2一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题，每小题3分，共45分）1 .下面的说法正确的是（A.数据结构可以分成逻辑结构和线性结构B.数据的逻辑结构是指数据及其逻辑结构在计算机中的表示C.从逻辑结构角度数据结构可以分为集合、线性结构、树结构和图结构四类D.数据的存储结构是从具体问题抽象出来的数学模型2 .线性表采用链式存储时，存储空间（A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续3 .顺序循环队列容量为20,队头表示第一个元素的位置，队尾表示最后一个元素的下一个位置，当队头为12,队尾为5的时候，队列中共有（）个元素。A.15B.14C.12D.134 .设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳。A.顺序表B.链表C.队列D.栈5 .下列有关串的操作中，（）不是串的常用操作。A.连接（COnCat）B.求子串（SUbString）C.插入（insert）D.求长度（Iength）6 .广义表GL=（a,（a）的表头是（）。A.aB.（a）C.（）D.（a）7 .二叉树高度为k,笫1层到第k-1层每层都是满的，第k层结点数不满，但该层结点从左到右满放，则该二叉树为（）。A.斜树B.有序树C.满二叉树D.完全二叉树8 .将一棵树转换为二叉树后，该转换后的二叉树的特点是（）oA.没有右子树B,没有左子树C,左右子树都有D.每层上只有一个结点9 .关于有向图的的说法错误的是（）oA.有向图中顶点V的入度（indegree）是以顶点V为终点（弧头）的弧的数目B.有向图中顶点V的出度（OUtdegree）是以顶点V为始点（弧尾）的弧的数目C.有向图中各顶点的入度之和等于各顶点的出度之和D.有向图中各顶点入度之和等于弧数e的2倍10 .在无向图的邻接表存储结构中插入一个顶点和一条边，不需要进行的操作是（）。A.在顶点表最后插入顶点信息B.找到边的第一个顶点的对应边链表，插入边信息C.找到边的第二个顶点的对应边链表，再次插入边信息D.把顶点表重新排序11 .如下图一棵平衡二叉排序树插入元素10后发生失衡，则对其应作（）型调整以使其平衡。A. LLB. LRC. RLD. RR12.设一组初始记录关键字序列为夕5, 18, 83, 35, 24, 47,找方法查找关键字24需要比较的关键字个数为（）050, 62, 90）,则利用顺序查A. 1B. 5C.9D. 1013.下面有关排序的说法正确的是（）。A.所有的排序算法都是稳定的B.排序算法中冒泡排序性能最好C.堆排序是不稳定的排序算法D.简单选择排序是稳定的排序算法14.对n个元素序列进行排序, 度分别是（）o如果利用二路归并方法进行排序，其时间复杂度和空间复杂BO(n), O(I)D. O(n2), O(n)A.O(nlog211),O(I)C.O(nlog211),O(n)）来求解。15 .当整体最优解可以通过局部最优选择得到时，该问题般可以采用（A.贪心算法B.回溯算法C分治算法D.折半查找算法二、判断题（正确的在括号内打上“J”，错误的打上“X”。本题共15个小题，每小题2分，共30分）16 .一般来说，递归只需要有递归方程就行了。（）17 .栈只能在栈底端进行插入删除。（）18 .顺序表在进行插入元素时不需要移动元素。（）19 .队列的存储结构只有顺序存储结构。（）20 .稀疏矩阵压缩存储时需要存储非零元素及其位置信息，不需要存储零元素。（）21 .空串的长度为零。（）22 .二叉树没有顺序存储结构。（）23 .线索二叉树只能加中序线索。（）24 .连通图的最小生成树可以有不同的形态。（）25 .带环图进行拓扑排序后，序列中不能包含所有顶点。（）26 .折半查找是在有序顺序表上进行的查找。（）27 .散列查找中冲突处理方法有开放地址法和链地址法。（）28 .当序列已经排好序时，快速排序退化为冒泡排序。（）29 .直接插入排序是不稳定的排序算法。（）30 .回溯法是在搜索过程中逐步构造解空间树的。（）三、综合题（本题共5个小题，每题5分，共25分）31 .请根据程序注释为下面程序中空缺的和位置选择正确的语句。List<String>list=newLinkedLiStVString>（）;创建链表list.add（"AAA"）;添加数据AAA到线性表中list.；添加数据BBB到线性表中list.©；/获取(并不删除)下标为1的元素A.remove(l);B.add("BBB")C.set(“BBB”)D.get(l)32 .请根据程序注释为下面程序中空缺的和位置选择正确的语句。voidinOrder(BinaryNode<E>p)中序次序遍历以P结点为根的子二叉树if(p!=null)inrder(®):中序次序遍历左子树System.out.print(p.data+"");inrder();中序次序遍历右子树)1A.p.leftB.pC.p.rightD.root33 .如下图所示有向图，从1顶点开始，其深度优先遍历序列为，广度优先遍历序列为。A .(123456) B. (123564)C.(I25346)D.(I25634)34.设一组初始记录关键字序列为(13, 18, 24, 35, 用折半查找过程中第一个比较的关键字是 数为。47, 50, 62, 83, 90, 115, 134),则利，查找关键字90需要比较的关键字个A. 13A. 1B.50C. 47B.2C.3D. 90D.435.设一组初始记录关键字序列为49, 27, 38, 堆)，则调整好的初始堆为()。13, 97, 76, 47),对其进行堆排序(最小134949）（97）（76）（47B数据结构与算法模拟试题3参考答案及评分标准一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题，每小题3分，共45分）1C2B3D4D5C6A7D8A9DIODHA12BBC14C15A二、判断题（正确的在括号内打上“J”，错误的打上“X”。本题共15个小题，每小题2分，共30分）16×17×18×19×202122×23×242526272829×30三、综合题（本题共5个小题，每题5分，共25分）31B32A33A34BDCBB35A
