数据结构与算法-模拟试题1（附参考答案）.docx

《数据结构与算法-模拟试题1（附参考答案）.docx》由会员分享，可在线阅读，更多相关《数据结构与算法-模拟试题1（附参考答案）.docx（6页珍藏版）》请在优知文库上搜索。

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

2、，再加入两个元素后，head和Iail的值分别为（）。A.1和5B.2和4C.4和2D.5和15 .串与普通的线性表相比较，它的特殊性体现在（）。A.顺序的存储结构B.链式存储结构C.数据元素是一个字符D.数据元素任意6 .广义表6二9仆曲,伯心w）的长度为（6A.2B.3C.7D.47 .三个结点的二叉树有（）种形态。A.3B.4C.5D.18 .高度为h的二叉树最多有（）个结点。A.hB.h*（h+1）C.2h-lD.h-19 .n个顶点的有向强连通图至多有（）条边。A.n（n-l）B.n（n-l）2C.n-1D.n10 .图进行广度优先搜索时，下列说法错误的是（）。A.广度优先搜索后可以

3、得到一个线性的顶点序列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 .下列（）排序算法的平均时间复杂度为O（nlog2n）,A.简单选择B.直接插入C.

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

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

6、kstack=newStack();for(inti=l;i6;i+)/将1,2,3,4,5添加到栈中，即入栈1,2,3,4,5stack.(String.valuef(i);Outputstack(Stack);遍历并打印出该栈stack.(2)()；/出栈栈顶元素A.pushB.popC.peekD.set32 .现有叶子权值序列为（1,2,5,7）,则将其构造的哈夫曼树为（）o该哈夫曼树的带权路径长度WPL为（）。A.30B.26C.25D.1533 .对如下图所示的无向连通网图从顶点a开始用普林姆（Prim）算法构造最小生成树，在）。A. (a,b)5,(b,e)3,(e,f)2, (

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