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

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

1、数据结构与算法模拟试题1一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。本题共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的数组来实现的循环队列，且head=3,tai1=。当从队列中删除一个元

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

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

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

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

6、置选择正确的语句。Stackstack=newStack（）;for（inti=1;i6;i+）/将1,2,3,4,5添加到栈中，即入栈1,2,3,4,5stack.（String.va1uef（i）;Outputstack（Stack）;/遍历并打印出该栈stack.（）;/出栈栈顶元素A.pushB.pop32.现有叶子权值序列为（1,2,5,7）,则将其构造的哈夫曼树为（）o501AB该哈夫曼树的带权路径长度WP1为（）oA.30B.26C.25C. peekD.set50,257CDD. 1533.对如下图所示的无向连通网图从顶点a开始用普林姆（Prim）算法构造最小生成树，在)o34

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