数据结构-6-10章自测题及答案(共4页).doc

《数据结构-6-10章自测题及答案(共4页).doc》由会员分享，可在线阅读，更多相关《数据结构-6-10章自测题及答案(共4页).doc（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上自测题（6-10章）一、填空题1、 二叉树第i(i=1)层上至多有_个结点，深度为k(k=1)的二叉树至多有_个结点。2、 对任何二叉树，若度为2的节点数为n2，则叶子数n0=_。3、 满二叉树上各层的节点数已达到了二叉树可以容纳的_，满二叉树也是_二叉树，但反之不然。4、 具有n个结点的完全二叉树的深度为_。5、 具有n个结点的二叉树中,一共有_个指针域,其中只有_个用来指向结点的左右孩子，其余的_个指针域为NULL。6、 二叉树有不同的链式存储结构，其中最常用的是_与_。7、 若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的

2、_个结点。8、 由_转换成二叉树时，其根结点的右子树总是空的。9、 哈夫曼树是带权路径长度_的树，通常权值较大的结点离根_。10、 有m个叶子结点的哈夫曼树，其结点总数为_。11、 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有_个叶子结点。12、 具有10个顶点的无向图，边的总数最多为_。13、 N个顶点的连通图的生成树含有_条边。14、 无向图的邻接矩阵是一个_矩阵，有向图的邻接矩阵不一定是_矩阵。15、 一个具有n个顶点的完全无向图的边数为_，一个具有n个顶点的完全有向图的弧数为_。16、 遍历图的基本方法有_优先搜索和_优先搜索两种。17、 在有向

3、图的邻接矩阵上，由第i行可得到第_个结点的_，而由第j列可得到第_个结点的_。18、 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素_比较大小。19、 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_。20、 若在线性表中采用二分查找法查找元素，该线性表应该元素_，且采用_结构。21、 对二叉排序树进行_遍历，可以得到该二叉树所有结点构成的有序序列。二、单项选择题1 以下说法错误的是 ( )树形结构的特点是一个结点可以有多个直接前趋线性结构中的一个结点至多只有一个直接后继树形结构可以表达(组织)更复杂的数据树(及一

4、切树形结构)是一种分支层次结构2. 深度为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+n4 6. 森林T中有4棵树，第一、二、三、四棵树

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

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

7、图的生成树，是该连通图的一个极大连通子图。无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。任何一个有向图，其全部顶点可以排成一个拓扑序列。有回路的图不能进行拓扑排序。15. 利用逐点插入法建立序列(51，71，43，81，74，20，34，45，64，30)对应的二叉排序树以后，查找元素34要进行( )次元素间的比较。 3 4 5 616. 哈希表的平均查找长度是( )的函数。哈希表的长度 表中元素的多少 哈希函数 装填因子三、简答及应用题1、已知一棵二叉树的中根序列和后根序列分别为BDCEAFHG和EDCBHGEA，试画出这棵二叉树。2、分别给出简答题11.1图中树的先根、后根和层

8、次遍历的结点访问序列。3、设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。4、分别给出图简答题3中从v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。5、图简答题17-1所示为一无向连通图，构造出它的最小生成树。6、若一棵排序二叉树的关键字输入序列为7，8，25，80，10，100，6， 90，请画出该二叉树。7、已知一组关键字为1,14,27,29,55,68,10,11,23，则按哈希函数H(key)=key MOD 11和链地址法处理冲突来构造哈希表。（1）画出所构造的哈希表。（2）在记录的

9、查找概率相等的前提下，计算该表查找成功时的平均查找长度。8、对于关键字序列65，97，76，49，38，13，回答下述问题：（1）写出一趟冒泡排序的结果；（2）写出一趟快速排序的结果。一、填空题1、 2i-1，2k-12、 n2+13、 最大值、完全4、 floor(log2n)+15、 2n、n-1、n+16、 二叉链表、三叉链表7、 第一个8、 树9、 最短、较近10、 2m-111、 1212、 4513、 N-114、 对称、 对称15、 n(n-1)/2、n(n-1)16、 深度、广度17、 i、出度、j、入度18、 28，6，12，2019、 散列查找 20、 按值有序、顺序存储2

10、1、 中序二、单项选择题1、 2、 3、 4、 5、 6、 7、 8、 9、 10、 11、 12、 13、 14、 15、 16、三、简答及应用题1、略2、先根序列：A B E F K L C G D H I J；后根序列：E K L F B G C H I J D A；层次序列：A B C D E F G H I J K L。3、第一步，先以给定的权值构造出哈夫曼树，如图简答题18所示。第二步，假没规定哈夫曼树上所有的左指针用0表示，所有的右指针用1表示。第三步，从根开始沿每一条通向叶子的路径上的数字，这些数字就是对应叶子结点所代表的字母的哈夫曼编码。8个字母所应的哈夫曼编码为：7-0010 19-10 2-00000 6-000132-01 3-00001 21-11 10-0011专心-专注-专业