数据结构-6-10章自测题及答案.doc

《数据结构-6-10章自测题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、自测题（6-10章）一、填空题1、二叉树第i(i>=1)层上至多有______个结点，深度为k(k>=1)的二叉树至多有______个结点。2、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。3、满二叉树上各层的节点数已达到了二叉树可以容纳的______，满二叉树也是______二叉树，但反之不然。4、具有n个结点的完全二叉树的深度为______。5、具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。6、二叉树有不同的链式存储结构，其中最

2、常用的是________与________。7、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。8、由________转换成二叉树时，其根结点的右子树总是空的。9、哈夫曼树是带权路径长度________的树，通常权值较大的结点离根________。10、有m个叶子结点的哈夫曼树，其结点总数为________。11、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有________个叶子结点。12、具有10个顶点的无向图，边的总数最多为________。13

3、、N个顶点的连通图的生成树含有________条边。14、无向图的邻接矩阵是一个________矩阵，有向图的邻接矩阵不一定是________矩阵。15、一个具有n个顶点的完全无向图的边数为________，一个具有n个顶点的完全有向图的弧数为________。16、遍历图的基本方法有________优先搜索和________优先搜索两种。17、在有向图的邻接矩阵上，由第i行可得到第________个结点的________，而由第j列可得到第________个结点的________。18、折半查找有序表（4，6，12，20，28，38，50，70，88

4、，100），若查找表中元素20，它将依次与表中元素________比较大小。19、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是________。20、若在线性表中采用二分查找法查找元素，该线性表应该元素________，且采用________结构。21、对二叉排序树进行________遍历，可以得到该二叉树所有结点构成的有序序列。二、单项选择题1．以下说法错误的是()①树形结构的特点是一个结点可以有多个直接前趋②线性结构中的一个结点至多只有一个直接后继③树形结构可以表达(组织)更复杂的数据④树(及一切树形结构)是一种"分支层次"结构2.深

5、度为6的二叉树最多有()个结点①64②63③32④313.设二叉树有n个结点，则其深度为()①n-1②n③floor(log2n)+1④无法确定4.下列说法中正确的是()①任何一棵二叉树中至少有一个结点的度为2②任何一棵二叉树中每个结点的度都为2③任何一棵二叉树中的度肯定等于2④任何一棵二叉树中的度可以小于25.设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，根结点的右子树上有（）个结点。①n1-1②n1③n1+n2+n3④n2+n3+n46.森林T中有4棵树，第一、二、三、四棵树的结点

6、个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，根结点的左子树上有（）个结点。①n1-1②n1③n1+n2+n3④n2+n3+n47.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（）①acbed②deabc③decab④cedba8.设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序()①都不相同②完全相同③先序和中序相同，而与后序不同④中序和后序相同，而与先序不同9.以下说法错误的是()①哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。②若一个二叉树的树叶是某

7、子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。③已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。④在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。10.任何一个带权的无向连通图的最小生成树（）①只有一棵②有一棵或多棵③一定有多棵④可能不存在11.在无向图中，所有顶点的度数之和是所有边数的（）倍。①0.5②1③2④412.在有向图中，所有顶点的入度之和是所有顶点出度之和的（）倍。①0.5②1③2④413.设有6个结点的无向图，该图至少应有（）条边能确保是一

8、个连通图。①5②6③7④814.以下说法正确的是（）①连通图的生成树，是该连通图的一个极大连通