国家开放大学数据结构与算法期末考试复习资料汇编

数据结构与算法•模拟试题1超越高度温暮提醒：可以使用word査找功能快速査找对应题目和答案。査找快捷键：Ctrl+F一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题，每小题3分，共45分）算法的时间复杂度是指算法所需要的（）。时冋资源 B.空间资源C.输入规模 D.输出结果对线性表，在下列（）情况下应当采用链表表示。A.经常需要随机地存取元素 B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为（）。A.4 B.5 C.6 D.7若用一个大小为6的数组来实现的循环队列，且head=3,tail=O°当从队列中删除一个元素，再加入两个元素后，head和tail的值分别为（）。A.1和5A.1和5B.2和4C.4和2D.5和1串与普通的线性表相比较，它的特殊性体现在（）。A.顺序的存储结构A.顺序的存储结构C.数据元素是一个字符B.链式存储结构D.数据元素任意广义表G=(a,(b,c),(a,(b,c),d))的长度为()。7.A.2B.3C.7D.47.A.2B.3C.7D.4三个结点的二叉树有（A.3B.4）种形态。C.5D.1)条边。)条边。C.n-1D.n高度为h的二叉树最多有（）个结点。A.hB.h*（h+1）C.2h-lD.h-1n个顶点的有向强连通图至多有（A.nx（n-1）B.nx（n-l）/2图进行广度优先搜索时，下列设法错误的是（）0广度优先搜索后可以得到一个线性的顶点序列广度优先搜索过程可以生成广度优先生成树广度优先搜索和深度优先搜索得到的顶点序列一定是不同的广度优先搜索和深度优先搜索都属于图的遍历设一组初始记录关键字序列为（13,18,24,35,47,50,62,83,90,115,134）,利用顺序査找方法查找关键字90需要比较的关键字个数为（）。A.1 B.5 C.9 D.10散列技术中的冲突指的是（）。A.两个元素具有相同的序号 B.两个元素的键值不同，而其他属性相同C.数据元素过多 D.不同键值的元素对应于相同的存储地址下列（）排序算法的平均时间复杂度为O（nlog2n）°A.简单选择 B.直接插入 C.快速 D.冒泡序列状态为（ ）时，快速排序达到最好的时间复杂度。A.序列基本有序 B.序列逆序 C.序列正序 D.序列无序将大问题转化为相互独立的相同的小问题，然后各个击破，解决完各个小问题后再合成大问题的解是（ ）的算法思想。A.递归算法B.分治法C.回溯算法 D.贪心算法二、判断题（正确的在括号内打上“ 错误的打上“X”。本题共15个小题，每小题2分，共30分）数据结构从逻辑结构上可以分为顺序结构和链式结构。（）队列是后进先出的线性表。（）栈只能在栈顶端进行插入删除。（）链表是顺序存储结构的线性表。（）串的长度不同时不能进行比较。（）广义表可以用来表示树型结构。（）

二叉树遍历的结果是一个线性序列。（）森林不可以转换为二又树。（）图可以只有顶点没有边。（）连通图的最小生成树是唯一的。（）平衡二叉树的左右子树是等高的。（）折半查找中第一个比较的元素是查找序列的第一个元素。（）从平均性能看，快速排序是所有基于比较的排序算法中最快的°（）待排数据量n较大时，要想排序的时间效率高旦所用辅助空间少，可以采用堆排序。（）—个问题只能由一种算法解决。（）三、综合题（本题共5个小题，每题5分，共25分）请根据程序注释为下面程序中空缺的①和②位置选择正确的语句。Stackstack=newStack（）;for（inti=i;i<6;i++） //将1,2,3,4,5添加到栈中，即入栈1,2,3,4,5{stack.CD（String.valueOfti））:}outputstack（stack）; 〃遍历并打印出该栈stack.②（）； //出栈栈顶元素A.push B.pop C.peek D.sel现有叶子权值序列为（1,2,5,7）,则①将其构造的哈夫曼树为（）。D.15②该哈夫曼树的带权路径长度WPL为（）。A.D.15②该哈夫曼树的带权路径长度WPL为（）。A.30B.26C.25对如下图所示的无向连通网图从顶点a开始用普林姆（Prim）算法构造最小生成树，在构造过程中加入最小生成树的前4条边依次是（ ）。A.(a,b)5,(b,e)3,(e,b)4C.(a,b)5,(b,e)3,D.(e,f)2,(b,e)3.34.按｛40,25,18,87｝的顺序构成的二叉排序树，其形态是（)»76.66,3345｝3345｝进行简单选择排序（每次选择最小关7806若对该关键字序列｛30851578063345｝第一趟扫描排序结果为。 35.对一组关键字序列（308515键字），第-,趙扫描排序结果为 进行从前向后的冒泡排序，A.0615 30 788506853015158515 78 3078 06 3330 78 063345334545853345数据结构与算法.模拟试题1•参考答案及评分标准一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题，每小题3分，共45分）1A2B3B4C5C6B7C8C9A10C11C12D13C14D15B二、判断题（正确的在括号内打上“ 错误的打上“X”。本题共15个小题，每小题2分，共30分）16X17X18419X20X21V22/23X24a/25X26X27X28寸29寸30X三、综合题（本题共5个小题，每题5分，共25分）31①A②B32(De②B33A34A35①B②C数据结构与算法•模拟试题2一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题，每小题3分，共45分）1.对于数据结构的描述，下列说法中错误的是（）=一种逻辑结构只能对应一种存储结构算法的设计依赖于数据的逻辑结构对数据结构基本操作的实现与存储结构有关数据的存储结构是数据的逻辑结构的机内实现2.数据结构与算法•模拟试题2一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题，每小题3分，共45分）1.对于数据结构的描述，下列说法中错误的是（）=一种逻辑结构只能对应一种存储结构算法的设计依赖于数据的逻辑结构对数据结构基本操作的实现与存储结构有关数据的存储结构是数据的逻辑结构的机内实现2.在一个长度为n的顺序表中（元素编号从0开始）的第i个位置上删除一个元素（足i<n）,需要向前移动（）个元素。A.n-i B.n-i+1C.n-i-lD.i+13.栈和队列的共同特点是（）。A.只允许在端点处插入和删除元素C.都是先进先出B.都是先进后出D.没有共同点4.设循环队列的元素存放在一维数组Q[30]中,head指向队头元素,tail指向队尾元素的后一个位置。若head=25,tai1=5,则该队列中的元素个数为（）。A.20B.10C.9D.II5.字符串S="DataStructure，啲长度为（)oA.13B.2C.14D.76.广义表G=(a,(b,c))的表尾是()。6.aB.(b,c)C.(a)7.二叉树有22个叶结点，则它有（A.21 B.20）个2度结点。C.23 1D,不确定7.二叉树有22个叶结点，则它有（A.21 B.20）个2度结点。C.23 1D,不确定8.高度为h的二叉树最少有（A.hB.h*（h+l））个结点。C.h*（h+l）/2D.h-19.n个顶点的连通图最少有（）条边。A.nx(n-l)B.nx(n-l)/2C.n-lD.n设无向图G=（V,E）和G=（V,E）如果a是G的生成树，则下面的说法中错误的是（）。A.G为G的子图 B.G为G的连通分量C.G为G的极小连通子图且V=V' D.G是G的一个无环子图其根结点是（按｛12,24,36,90,52,30｝的顺序构成的二叉排序树,其根结点是（A.12B.24C.A.12B.24C.52D.3612.设一组初始记录关键字序列为（13,12.设一组初始记录关键字序列为（13,第一个比较的关键字是（）。18,24,35,47,50,62）,则利用折半查找过程中A.13A.13B.50 C.47 D.35堆的形状是一棵（）。A.完全二叉树 B.A.完全二叉树 B.满二叉树C.二叉排序树D判定树快速排序的最坏情况下的时间复杂度为（）。D.O(nL3)A.O(n2)B.O(nlogD.O(nL3)贪心算法解决的问题应满足（）。贪心选择性质和最优子结构性质贪心选择性质和独立子问题性质最优子结构性质和重叠子问题性质试探和回溯性质二、判断题（正确的在括号内打上“错误的打上“X”。本题共15个小题，每小题2分，共30分）算法的五个基本特征是输入、输出、有穷性、确定性、可行性。（）顺序表会开辟连续的存储空间存储数据。（）已知入栈的序列是ABCD,则出栈序列可以是ABCD。（）队列中插入元素在队头进行，删除元素在队尾进行。（）字符串是一种操作受限的线性表。（）下三角矩阵压缩存储时元素的位置能通过下标ij找到°（）哈夫曼树是最优二叉树。（）

线索链表存储结构的结点结构和二叉链表存储结构的结点结构完全相同。()有向图无法进行深度优先遍历。()图的存储结构有邻接矩阵存储结构和邻接表存储结构。()26•顺序査找中待査元素为首元素时比较元素的次数最少°()散列査找中，冲突越多，散列査找效率越高。()归并排序的空间复杂度是0(1)。()直接插入排序与简单选择排序相比记录移动次数更少。()用分治法解决的问题分解为子问题时子问题相互独立。()三、综合题(本题共5个小题，每题5分，共25分)31.请根据程序注释为下面程序中空缺的①和②位置选择正确的语句。List<String>list=newArrayList<String>();//创建顺序表list.add("A"); //添加数据A到线性表中list.CD: 〃添加数据B到线性表中list.② ； 〃删掉下标为1的元素A.remove(I);B.add("B") C.set(''B")D.get(l)现有完全二叉树顺序存储结构如下图所示，则a|b|c|d|e|f|g|fT012345675号结点F的双亲结点是( )。A.2号结点CB.4号结点EC.1号结点BD.3号结点D该二叉树的层序遍历结果为(A.(ABCDEFGH)B.(ABDHECFG)C.(HDBEAFCG)D.(HDEBFGCA)如下图所示有向图，从1顶点开始，其拓扑排序序列可以为①或者②或者③ 。A.(123564)C.(125364)B,(125634)D.(123456)现有关键字序列｛41,68,13,25,15,48｝,散列函数为Hash（Key）=Key%13,散列表长为13,则41的散列地址为 ① ,41和②是同义词。A.2A.13B.3 C.O D.13B.15 C.68 D.25对一组关键字序列｛30851578063345｝进行快速排序（30为基准值），第一趟扫描排序结果为①；若对该关键字序列（30851578063345｝进行两两归并排序，第一趟两两归并排序结果为② °061506853015308530 78 85 33 4515 78 30 33 4578 06 33 45 8515 78 06 33 45数据结构与算法•模拟试题2•参考答案及评分标准一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题，每小题3分，共45分）1A2C3A4B5C6D7A8A9C10B11A12D13A14A15A二、判断题（正确的在括号内打上“ 错误的打上“X”。本题共15个小题，每小题2分，共30分）16V17V18V19X20X21V22J23X24X25V26V27X28X29X30V三、综合题（本题共5个小题，每题5分，共25分）31①B②A32①A②A33①A②B③C34①A②B35①A②D数据结构与算法数据结构与算法•模拟试题3一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题，每小题3分，共45分）下而的说法正确的是（）。数据结构可以分成逻辑结构和线性结构数据的逻辑结构是指数据及其逻辑结构在计算机中的表示从逻辑结构角度数据结构可以分为集合、线性结构、树结构和图结构四类数据的存储结构是从具体问题抽象出来的数学模型线性表釆用链式存储时，存储空间（）o必须是不连续的 B.连续与否均可C.必须是连续的 D.和头结点的存储地址相连续顺序循环队列容量为20,队头表示第一个元素的位置，队尾表示最后一个元素的下一个位置，当队头为12,队尾为5的时候，队列中共有（）个元素。15B.I4C.12D.I3设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳。顺序表 B.链表 C.队列 D.栈下列有关串的操作中，（）不是串的常用操作。A.连接（concat） B.求子串（substring） C.插入（insert） D.求长度（lengih）广义表GL=（a,（a））的表头是（）。A.a B.（a） C.（） D.（（a））二叉树高度为k,第1层到第k-1层每层都是满的，第k层结点数不满，但该层结点从左到右满放，则该二叉树为（）。A.斜树 B.有序树 C.满二叉树 D,完全二叉树将一棵树转换为二叉树后，该转换后的二叉树的特点是（）。A.没有右子树B.没有左子树 C.左右子树都有D.每层上只有一个结点关于有向图的的说法错误的是（）。有向图中顶点v的入度（indegree）是以顶点v为终点（弧头）的弧的数目有向图中顶点v的出度（outdegree）是以顶点v为始点（弧尾）的弧的数目有向图中各顶点的入度之和等于各顶点的出度之和有向图屮各顶点入度之和等于弧数e的2倍在无向图的邻接表存储结构中插入一个顶点和一条边，不需要进行的操作是（）o在顶点表最后插入顶点信息找到边的第一个顶点的对应边链表，插入边信息找到边的第二个顶点的对应边链表，再次插入边信息把顶点表重新排序11.如下图一棵平衡二叉排序树插入元素1011.如下图一棵平衡二叉排序树插入元素10后发生失衡,则对其应作（）型调整以使其平衡。A.LLB.LR C.RLD.RR12.设一组初始记录关键字序列为（15,18,83,35,24,47,A.LLB.LR C.RLD.RR12.设一组初始记录关键字序列为（15,18,83,35,24,47,50,62,90）,则利用顺序查找方法査找关键字24需要比较的关键字个数为（）。A.1B.5A.1B.5C.9D.1013.下面有关排序的说法正确的是（）。所有的排序算法都是稳定的排序算法中冒泡排序性能最好堆排序是不稳定的排序算法简单选择排序是稳定的排序算法14.对14.对n个元素序列进行排序,度分别是（）o如果利用二路归并方法进行排序，其时间复杂度和空间复杂B.O(n),0(1)B.O(n),0(1)D.O(n2),O(n)A.O(nlog2n),0(1)C.O(nlog2n).O(n)15.当整体最优解可以通过局部最优选择得到时，该问题•般可以釆用（）来求解。A.贪心算法B.回溯算法C.分治算法D.折半查找算法二、判断题（正确的在括号内打上P：错误的打上“X”。本题共15个小题，每小题2分，共30分）一般来说，递归只需要有递归方程就行了•（）栈只能在栈底端进行插入删除°（）顺序表在进行插入元素时不需要移动元素。（）队列的存储结构只有顺序存储结构。（）稀疏矩阵压缩存储时需要存储非零元素及其位置信息，不需要存储零元素。（）空串的长度为零°（）二又树没有顺序存储结构。（）线索二又树只能加中序线索。（）连通图的最小生成树可以有不同的形态。（）带环图进行拓扑排序后，序列中不能包含所有顶点。（）折半查找是在有序顺序表上进行的查找。（）散列查找中冲突处理方法有开放地址法和链地址法。（）当序列已经排好序时，快速排序退化为冒泡排序°（）直接插入排序是不稳定的排序算法。（）回溯法是在搜索过程中逐步构造解空间树的•（）四、综合题（本题共5个小题，每题5分，共25分）请根据程序注释为下面程序中空缺的①和②位置选择正确的语句。LisKString>list=newLinkedList<String>（）;//创建链表list.add（”AAA"）; //添加数据AAA到线性表中list.CD: //添加数据BBB到线性表中list.② ； //获取（并不删除）下标为1的元素A.remove（l）; B.add（"BBB"） C.set（''BBB"）D.gel（l）

32.请根据程序注释为下面程序中空缺的①和②位置选择正确的语句。voidinOrder(BinaryNode<E>p){if(p!=null)32.请根据程序注释为下面程序中空缺的①和②位置选择正确的语句。vo