国家开放大学2023-2024学年《数据结构与算法》模拟试卷及答案解析（2024年）.docx

《国家开放大学2023-2024学年《数据结构与算法》模拟试卷及答案解析（2024年）.docx》由会员分享，可在线阅读，更多相关《国家开放大学2023-2024学年《数据结构与算法》模拟试卷及答案解析（2024年）.docx（6页珍藏版）》请在优知文库上搜索。

1、国家开放大学2023-2024学年数据结构与算法模拟试卷及答案解析一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题，每小题3分，共45分）1 .算法的时间复杂度是指算法所需要的（）。A.时间资源B.空间资源C.输入规模D.输出结果2 .对线性表，在下列（）情况下应当采用链表表示。A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变3 .若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为（）。A.4B.5C.6D.74 .若用一个大小为6的数组来实现的循环队列,且he

2、ad=3,tail=00当从队列中删除一个元素，再加入两个元素后，head和tail的值分别为（）。A. 1 和 5B.2和4C.4和2D.5和15 .串与普通的线性表相比较，它的特殊性体现在（）oA.顺序的存储结构B.链式存储结构C.数据元素是一个字符D.数据元素任意6 .广义表6=母电*电*(1)的长度为()oA.2B.3C.7D.47.三个结点的二叉树有（A.3 B. 4）种形态。C.5D. 18 .高度为h的二叉树最多有（）个结点。A.hB.h*（h+1）C.2h-lD.h-19 .n个顶点的有向强连通图至多有（）条边。C. n-1 D. nA.n(n-l)B.n(n-l)210 .图

3、进行广度优先搜索时，下列说法错误的是()。A.广度优先搜索后可以得到一个线性的顶点序列B.广度优先搜索过程可以生成广度优先生成树C.广度优先搜索和深度优先搜索得到的顶点序列一定是不同的D.广度优先搜索和深度优先搜索都属于图的遍历11 .设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),利用顺序查找方法查找关键字90需要比较的关键字个数为()oA.1B.5C.9D.1012 .散列技术中的冲突指的是()。A.两个元素具有相同的序号B.两个元素的键值不同，而其他属性相同C.数据元素过多D.不同键值的元素对应于相同的存储地址13 .下列()排序算法的

4、平均时间复杂度为O(nlog2n),A.简单选择B.直接插入C.快速D.冒泡14 .序列状态为()时，快速排序达到最好的时间复杂度。A.序列基本有序B.序列逆序C.序列正序D.序列无序15 .将大问题转化为相互独立的相同的小问题，然后各个击破，解决完各个小问题后再合成大问题的解是()的算法思想。A.递归算法B.分治法C.回溯算法D.贪心算法二、判断题(正确的在括号内打上“J”，错误的打上“X”。本题共15个小题，每小题2分，共30分)16 .数据结构从逻辑结构上可以分为顺序结构和链式结构。()17 .队列是后进先出的线性表。()18 .栈只能在栈顶端进行插入删除。()19 .链表是顺序存储结构

5、的线性表。()20 .串的长度不同时不能进行比较。()21 .广义表可以用来表示树型结构。()22 .二叉树遍历的结果是一个线性序列。()23 .森林不可以转换为二叉树。（）24 .图可以只有顶点没有边。（）25 .连通图的最小生成树是唯一的。（）26 .平衡二叉树的左右子树是等高的。（）27 .折半查找中第一个比较的元素是查找序列的第一个元素。（）28 .从平均性能看，快速排序是所有基于比较的排序算法中最快的。（）29 .待排数据量n较大时,要想排序的时间效率高且所用辅助空间少,可以采用堆排序。（）30 .一个问题只能由一种算法解决。（）三、综合题（本题共5个小题，每题5分，共25分）31

6、.请根据程序注释为下面程序中空缺的和位置选择正确的语句。Stackstack=newStack();for(inti=l;i6;i+)/将1,2,3,4,5添加到栈中，即入栈1,2,3,4,5stack.(String.valueQf(i);)Outputstack(Stack);遍历并打印出该栈stack.(2)()；/出栈栈顶元素A.pushB.popC.peekD.set32 .现有叶子权值序列为（1,2,5,7）,则将其构造的哈夫曼树为（）o该哈夫曼树的带权路径长度WPL为（）。A.30B.26C.25D.1533 .对如下图所示的无向连通网图从顶点a开始用普林姆（Prim）算法构造最

7、小生成树，在A. (a,b)5,(b,e)3,）。构造过程中加入最小生成树的前4条边依次是（B. (a,b)5,(b,f)4,(f,e)2,(e,b)4C. (a,b)5,(b,e)3,(b,f)4,(f,e)2D.(e,f)2,(b,e)3,(d,f)4,(b,f)434.按40, 25, 18, 76, 66, 87的顺序构成的二叉排序树，其形态是（）。A. 06 15B. 06 85C.30 15D. 15 8533 4533 4545 8533 4535.对一组关键字序列30851578063345进行简单选择排序（每次选择最小关键字），第一趟扫描排序结果为_Q_；若对该关键字序列30851578063345）进行从前向后的冒泡排序，第一趟扫描排序结果为。307885157830780633307806数据结构与算法模拟试题参考答案及评分标准一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共15个小题,每小题3分，共45分）1A2B3B4C5C6B7C8C9AIOCHC 12D13C14D15B二、判断题（正确的在括号内打上“J”，错误的打上“X”。本题共15个小题，每小题2分，共30分）161718192021222324252627282930三、综合题（本题共5个小题，每题5分，共25分）31AB32CB33 A34 A35BC