数据结构与算法单元测试题3及答案.docx

《数据结构与算法单元测试题3及答案.docx》由会员分享，可在线阅读，更多相关《数据结构与算法单元测试题3及答案.docx（8页珍藏版）》请在课桌文档上搜索。

1、一、单选题1、一个具有n个顶点的有向图中，要连通全部顶点至少需要（）条弧。A.nB.n-1C.n+1D.2n正确答案：A2、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示,则占用的存储空间为（）。A.n+2eB.2eC.nD.n+e正确答案：A3、如果含有n个顶点的图形成一个环，则它有（）棵生成树。A.不确定B.n-1C.nD.n+1正确答案：C4、关键路径是事件结点网络中（）。A.最短回路B.从源点到汇点的最短路径C.从源点到汇点的最长路径D.最长回路正确答案：C5、图G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A.11B.10C.9D.8正确答案：C6、已知一个图的

2、邻接矩阵表示，删除所有从第i个顶点出发的弧方法是（）0A.将矩阵第i列删除，后序列左移B.将矩阵第i行上的元素全部置OC.将矩阵第i行删除，后序行上移D.将矩阵第i列上的元素全部置O正确答案：B7、连通分量是（）的极大连通子图。A.有向图B.无向图C.图D.树正确答案：B8、下面关于图的存储结构的叙述中正确的是（）oA.邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关B.用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关C.用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关D.用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关正确答案：D9、下图中，

3、度为3的结点是（）。A.V1B.V3C.V4D.V2正确答案：D10、如下图所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（）。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,d,f,c,bD.a,e,b,c,f,d正确答案：A11、具有12个关键字的有序表，折半查找的平均查找长度（）oA.25B.25/12C.37/12D.10/12正确答案：C12、以下适合用分块查的数据集是（）。A.数据分成若干块，每块（除最后一块外）中数据个数需相同B.数据分成若干块，块内数据不必有序，但块间必须有序C.数据分成大小相等的若干块，块内数据有序D.数据分成若干块，块内数

4、据必须有序，块间不必有序正确答案：B13、由同一关键字集合构造的各棵二叉排序树（）oA.形态和平均查找长度都不一定相同B.形态相同，但平均查找长度不一定相同C.形态不一定相同，但平均查找长度相同D.形态和平均查找长度都相同正确答案：A14、对二叉排序树进行（）遍历,可以得到各结点键值的非递减序列。A层次B.中序C后序D冼序正确答案：B15、如果按关键码值递增的顺序依次将99个关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，在等概率情况下查找成功时的平均查找长度ASL为（）。A.45B.48C.50D.47正确答案：C16、在有N个元素的顺序表中顺序查找，则等概率情况下查找成功的平均查找

5、长度为()。A.(N+1)2B.N(N+1)2C.N/2D.N+1正确答案：A17、冲突指的是()。A.两个元素具有相同序号B.两个元素的键值不同C.不同关键字记录对应相同的存储地址D.两个元素的键值相同正确答案：C18、对包含n个元素的散列表进行查找，其平均查找长度()。A.0(n2)B.O(n)C.O(log2n)D.不直接依赖于n正确答案：D19、衡量查找算法效率的主要标准是()0A.元素个数B.平均查找长度C.所需的存储量D.算法难易程度正确答案：B20、在查找过程中，不做增加、删除或修改的查找称为（）oA.动态查找B.内查找C.静态查找D外查找正确答案：C二、判断题1、图可以没有边，

6、但不能没有顶点。正确答案：X2、关键路径上的活动都是关键活动，它们是否按时完成会影响工期。正确答案：3、求稀疏图的最小生成树，用克鲁斯卡尔算法来求解较好。正确答案：4、迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。正确答案：5、存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。正确答案：6、HaSh表的平均查找长度与处理冲突的方法无关。正确答案：X7、在二叉树排序树中插入一个新结点，总是插入到叶结点下面。正确答案：X8、二分查找法要求待查表的关键字值必须有序。正确答案：9、哈希表是一种将关键字转换为存储地址的存储方法。正确答案：10、在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找速度。正确答案：X