树图查找排序复习.docx

1、树图查找排序复习树一、判断题：1.二叉树是一棵无序树。（）2.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。（）3.度为二的有序树等价于二叉树。（）4.树的带权路径长度最小的二叉树中必定没有度为1的结点。（）5.哈夫曼树一定是满二叉树。（）6.满二叉树也是完全二叉树。（）7.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（）8.将一棵树转换成二叉树后，根结点没有左子树()9.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（）10用二叉树的前序遍历和中序遍历可以导出树的后序遍历。（）

2、11.在完全二叉树中,若某结点无左孩子,则它必是叶结点。（）。12任何一棵二叉树都有n0=n2+1的关系式。（）13已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树。（ ）二、填空题1. 假定一棵二叉树的结点个数为32，则它的最小深度为_6_,最大深度为：32。2. 在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，那么叶子结点有_6_个。3. 树的双亲表示法便于实现涉及到_双亲_的操作，孩子表示法便于实现涉及到孩子的操作。4. 对于一颗具有n个结点的二叉树，对应二叉链表中指针域有_n-1_个用于指向子结点。5. 下图所示二叉树存储在一维数组中，则元素F的下标位置为_11_。（A为1

3、）F6. 高度为k的二叉树具有的结点数目，最少为_ K _,最多为_2K-1_。7. 对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=_ n2+1_。8. 一棵含有16个结点的完全二叉树，对他按层编号，对于编号为7的结点，他的双亲结编号点为_3_左孩子编号为_14_、右孩子编号为_15_。9. 在含100个结点的完全二叉树，叶子结点的个数为_50_。10. 度数为0的结点，即没有子树的结点叫作_叶子_结点。同一个结点的儿子结点之间互称为_兄弟_结点。11. 若一棵完全二叉树含有121个结点，则该树的深度为_7_。12. 已知一棵树的前序序列为ABCDEF，后序序列

4、为CEDFBA，则对该树进行层次遍历得到的序列为_ ABCDFE _。三、选择题1. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_C_。A. n B. n-1 C. n+1 D. 2*n2. 在一棵二叉树的第5层上，最多具有_B_个结点。A. 14 B. 16 C. 31 D. 323. 在一棵深度为h的完全二叉树中，所含结点个数不少于_D_。A. 2h B. 2h+1 C. 2h -1 D. 2h-14. 一棵树的广义表表示为a(b(c), d(e(g(h), f)，则该二叉树的高度为_D_。A. 2 B. 3 C. 4 D. 55. 将一棵有40个结点的完全二叉树从上到下，从左

5、到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为_A_。A.30 B.31 C.16 D.326. 在一棵树中，每个结点最多有_B_个直接前驱结点。A. 0 B. 1 C. 2 D. 任意多个7. 7. 树中所有结点的度数之和等于结点总数加_C_。A. 0 B. 1 C. -1 D. 28. 二叉树中第5层上的结点个数最多为_C_A.8 B.15 C.16 D.329. 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为_A_。A.98 B.99 C.50 D.4810. 由权值分别为3, 8,

6、 6, 2, 5的叶子结点生成一颗赫夫曼树，它的带权路径长度为_D_。A. 24 B. 48 C. 72 D. 5311. 把一棵树转换为二叉树后，这棵二叉树的形态是 A 。.唯一的 .有多种.有多种，但根结点都没有左孩子 .有多种，但根结点都没有右孩子12. 具有n(n0)个结点的完全二叉树的深度为 C 。 log2(n) log2(n) log2(n) +1 log2(n)+113. 四、应用题1.将下图转换为二叉树，对转换后的二叉树进行先序、中序、后序遍历序列。J先序：ABEFCDGJ中序：EFBCGJDA后序：FEJGDCBA2.写出下图所示二叉树的先序、中序、后序序列F 先序序列：A

7、BDEFC中序序列：DBFEAC后序序列：DFEBCA3.已知一棵二叉树的先根和中根序列，画出其对应的二叉树并求其后根序列。先根序列：A, B, C, D, E, F, G, H, I, J中根序列：C, B, A, E, F, D, I, H, J,G后根序列：C, B, F, E, I, J, H, G, D, A6已知一棵二叉树的先序、中序和后序遍历序列分别为: （参看课件）先序: BEKCJADGHI 中序: LKCAJFGIH后序: KLJCEFGDB 其中有些字母已丢失,请添写完整并画出此二叉树7.在一份电文中共使用8种字符，即a, b, c, d, e, f, g, h，它们出现

8、的频率依次为0.07, 0.19, 0.02,0.06, 0.32, 0.03, 0.21, 0.10，试画出对应的赫夫曼树，求出每个字符的赫夫曼编码，以及带权路径长度。哈夫曼编码:a:0010 b:10 c:00000 d:0001 e:01 f:00001 g:11 树和wpl：略。8.写出下图所示森林的先序、中序序列。将该森林转换为相应的二叉树。15先序序列：1、2、3、4、5、6、8、7、9、10、11、12、13、15、14中序序列：3、4、8、6、7、5、2、1、10、9、11、15、13、14、129. 设二叉树后根遍历为BAC，画出所有可能的二叉树。10、将如下森林转化成二叉树

9、JFD11、已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。要求画出哈夫曼树，给出编码，并求出带权路径长度）12、假定用于通信的电文仅由a,b,c,d 4个数据元素，各字母在电文中出现的频率分别为7，5，2，4，试为这4个字母设计不等长的哈夫曼编码。（要求画出哈夫曼树，给出编码，并求出带权路径长度）a:0 b:10 c:110 d:111 或 a:1 b:01 c:001 d:000wpl=7*1+5*2+2*3+4*3=3513、在一份电文中共使用8种字符，即a, b, c, d, e, f, g, h，它们出现的频率依

10、次为0.10, 0.09, 0.32, 0.02,0.26, 0.03, 0.01, 0.17 ，试画出对应的赫夫曼树，求出每个字符的赫夫曼编码。要求画出哈夫曼树，给出编码，并求出带权路径长度）五、算法：1. 中序遍历二叉树（对二叉排序树，按递增顺序输出）。（先写存储结构，再写算法）存储结构定义：typedef struct BiTNode / 结点结构 Selemtype data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree; void inorder(BITree t)if(t!=NULL)inorder(t-lchild);pri

11、ntf(“%d”，t-data);inorder(t-rchild);图一、判断题：1.图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。（）2.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。（）3.如果有向图中各个顶点的度都大于2，则该图中必有回路。（）4.具有n个顶点的连通图的生成树具有n-1条边（） 5在n个结点的无向图中,若边数n-1,则该图必是连通图.()6.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（）7.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边

12、数远小于顶点数的平方）。（）8. 若一个有向图的邻接矩阵中对角线以下元素均为零,则该图的拓扑有序序列必定存在（）（超）9.无向图的邻接矩阵是对称的，有向图的邻接矩阵是不对称的。（）10.对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（）11.若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（）二、填空题1. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为_ n2_。2. 有一个n个顶点的有向完全图的弧数_ n(n-1)_。3. 在无向图中，若从顶点

13、A到顶点B存在_路径_，则称A与B之间是连通的。4. 在一个无向图中，所有顶点的度数之和等于所有边数的_2_倍。5. n (n0) 个顶点的无向图中顶点的度的最大值为_n-1_。6. 如果从一个顶点出发又回到该顶点，则此路径叫做_环/回路_。7. 一个具有个n顶点的无向图中，要连通全部顶点至少需要_n-1_条边。三、选择题1.顶点个数为n的无向图最多有_B_条边。A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)2.n个顶点的连通图至少有_A_条边。A. n-1 B. n C. n+1 D. 03.在一个有向图中，所有顶点的度数之和等于所有弧数的_B_倍。A. 3

14、 B. 2 C. 1 D. 1/24.有向图的一个顶点的度为该顶点的_C_。A. 入度 B. 出度 C. 入度与出度之和 D. (入度出度)/25.一个连通图的生成树是包含图中所有顶点的一个_C_子图。A. 极小 B. 连通 C. 极小连通 D. 无环6.图的深度优先遍历类似于树的_A_。A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历7.下面关于图的存储的叙述中，哪一个是正确的。 _A_A.用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B.用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C用邻接表法存储图，占用的存储空间数只与图中结点个数有

15、关，而与边数无关D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关8如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是_D_A.有向完全图 B.连通图C.强连通图 D.有向无环图9.具有e条边的有向图，它的逆邻接表中有_B_个弧结点。A. e-1 B. e C. 2(e-1) D. 2e10.具有e条边的无向图，它的邻接表中有_ D _个边结点。A. e-1 B. e C. 2(e-1) D. 2e11.在一个图中，所有顶点的度数之和等于图的边数的_C_倍。A1/2 B. 1 C. 2 D. 412. 用邻接表表示图进行广度优先遍历时，通常是采用 B 来实现算法的。

16、A栈 B. 队列 C. 树 D. 图四、应用题1. 无向图中每个顶点的度，有向图中每个顶点的入度，出度和度。是否是连通图/强连通图，如果不是，画出连通分量/强连通分量。（5分）32顶点01234度顶点01234出度入度是连通图。不是强连通图：强连通分量为：432102. 9请给出下图的邻接矩阵，利用普里姆（prim）算法，构造下图最小生成树，（以0为根结点）。(写出步骤)，（克鲁斯卡尔算法怎么做？）3. 请给出下图的邻接矩阵、邻接表、逆邻接表及结点V2的入度和出度。（10分）V54. 下图是用邻接表存储的图，画出此图，写出每个顶点的度，并写出从C点开始按深度优先、广度优先遍历该图的结果。（课件

17、上例题）深度优先遍历序列：C、D、E、A、B、F广度优先遍历序列：C、D、A、E、B、F排序和查找一、判断题1. 进行折半查找的表必须是顺序存储的有序表。（ ）2. 在任何情况下，快速排序需要进行关键码比较的次数都是O(nlog2n)。（）3. 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。（）4. 直接选择排序是一种稳定的排序方法。（）5. 堆排序是一种稳定的排序算法。()6. 快速排序法是一种稳定性排序法。（）7. 散列法存储的基本思想是由关键字的值决定数据的存储地址（）8. 对n个元素的表用堆排序法进行排序，时间复杂度

18、是O(log2n)（）9. 在采用线性探测法处理冲突的散列表中,所有同义词在表中一定相邻（）。10. 堆排序是所需辅助空间最少的排序。（）11. 一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（）二、填空题1. 若要对某二叉排序树进行遍历，保证输出元素的值序列按增序排列，应对该二叉排序树采用_遍历法。中序2. 元素关键字转换为该元素存储位置的函数f称为_。哈希函数3. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。4. 将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序。5. 先将整个待排序列分割成若干

19、子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体进行一次直接插入排序，此种排序方法叫做_希尔排序_排序。6. 每次使两个相邻的有序表合并成一个有序表的排序方法叫做_归并_排序。7. 每次从无序表中挑选出一个最大或最小元素，把它交换到有序表的一端，此种排序方法叫做_简单选择_排序。8. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_直接插入_排序。9. 每次直接或通过“枢轴”元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做_快速_排序。10. 假定一组数据的关键字为46,79,56,38,40,84，则利用堆排序方法建立的初始小

20、顶堆为_38，40，56，79，46，84_。11. 假定一组数据的关键字为46,79,56,38,40,84，则以第一个记录为枢轴，对其进行第一趟快速排序的结果为_40,38,46,56,79,84_。12. 若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=keyMOD9，与18发生冲突的元素有_9_三、选择题1. 对于顺序存储的有序表(5, 12, 20, 26, 37, 42, 46, 50, 64)，哨兵位在前，为查找元素26，若采用顺序查找，需要比较_D_次才能查找成功。A. 3 B. 4 C. 5 D. 62. 设哈希表长为14，哈希函数f（k）

21、=k11，已知表中已有4个元素，关键字分别为15，38，61，84，存储位置分别为4，5，6，7，其它存储位置为空，如用二次探测再散列处理冲突，关键字为49的存储位置是_D_。A. 8 B. 3 C. 5 D. 93. 对于顺序存储的有序表(5, 12, 20, 26, 37, 42, 46, 50, 64)，为查找元素26，若采用折半查找，需要比较_B_次才能查找成功。A. 3 B. 4 C. 5 D. 64. 对线性表进行折半查找时，要求线性表必须_C_。A. 以顺序方式存储B. 以链接方式存储C. 以顺序方式存储，且元素按关键字有序排序D. 以链接方式存储，且元素按关键字有序排序5. 对

22、于哈希函数H(key)=key%13，被称为同义词的关键字是_D_A35和41 B.23和39 C.15和44 D.25和516. 适于对动态查找表进行高效率查找的组织结构是_C_。A. 有序表 B. 顺序表 C. 二叉排序树 D. 链表7. 设哈希表长为14，哈希函数f（k）=k11，已知表中已有4个元素，关键字分别为15，38，61，84，存储位置分别为4，5，6，7，其它存储位置为空，如用二次探测再散列处理冲突，关键字为49的存储位置是_D_。A. 8 B. 3 C. 5 D. 98. 用某种排序方法对关键字序列（23，72，21，47，15，27，59，35，20）进行排序时，前三趟的

23、结果情况如下 23，21，47，15，27，59，35，20，72 21，23，15，27，47，35，20，59，72 21，15，23，27，35，20，47，59，72则所采用的排序方法是_B_A.选择排序 B.起泡排序 C.归并排序 D.快速排序9. 在对n个元素进行简单选择排序的过程中，需要进行_ B _趟选择和交换。A. n/2 B. n-1 C. n D. n+110. 若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_ C _. 38, 40, 46, 56, 79, 84 . 40, 38, 4

24、6 , 79, 56, 84 . 40, 38，46, 56, 79, 84 . 40, 38, 46, 84, 56, 7911. 对于哈希函数H(key)=key%13，被称为同义词（即冲突）的关键字是_ D _A35和41 B.23和39 C.15和44 D.25和5112. 若对n个元素进行直接插入排序，在进行i趟(2in)排序时，为寻找插入位置最多需要进行_C_次元素的比较。A. i+1 B. i-1 C. i D. 113. 在对n个元素进行快速排序的过程中，第一趟排序最多需要交换_B_对元素。A. n/2 B. n-1 C. n D. n+114. 在对n个元素进行简单选择排序的

25、过程中，需要进行_B_趟选择和交换。A. n/2 B. n-1 C. n D. n+115. 堆的形状是一棵_A_。A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树16. 对于哈希函数H(key)=key%13，被称为同义词的关键字是_D_。A35和41 B.23和39 C. 15和44 D.25和5117. 从二叉搜索树中查找一个元素时，其时间复杂度大致为_C_。A、 O(n) B、 O(1) C、 O(log2n) D、 O(n2) 18. 堆是一种 B 排序。. 插入 .选择 . 交换 . 归并19. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）

26、。若查找表中元素58，则它将依次与表中 A 比较大小，查找结果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，5020. 快速排序是一种 C 排序。. 插入 .选择 . 交换 . 归并四、应用题1. 已知一组关键字为（26，36，41，38，44，15，68，12，06，51，25），用线性探查法解决冲突构造这组关键字的哈希表。表长取15，哈希函数H(key)=key MOD 13。2. 用序列（46，88，45，39，70，58，101，10，66，34）建立一个平衡的二叉排序树，画出该树，并求在等概率情况下查找成功的平均查找长度。3. 关键码的输入序

27、列 55, 31, 11, 37, 46, 73, 63, 02, 07 请计算在二分法查找、平衡的二叉排序树两种的情况下等概率下查找成功的平均查找长度。4. 一组键值序列为(41，66，73，52，40，37，65，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。5. .已知一组关键字为（19，14，23，01，68，20，84，27，55，11,10，79），则按哈希函数H(key)=key MOD 13和链地址法解决冲突构造这组关键字的哈希表。6. .给出一组关键字(19，01，26，92，87，11，43，87，21)，进行起泡排序，试列出每一遍排序后关键字的排列

28、次序，并统计每遍排序关键字所进行的关键字比较次数7. 已知一组键值序列为(41，66，73，52，40，37，65，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。（5分） 已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为06)，待散列序列为：(25，48，32，50，68，43)。要求：（1）根据以上条件构造一散列表，并用线性探测再散列解决有关地址冲突。（2）求在等概率下查找成功的平均查找长度。散列表：8. 已知长度为12的表如下： Jan,Feb,Mar,Apr,May,June,July, Aug,Sep,Oct,Nov,Dec 建立相应的平衡

29、二叉排序树（按字典顺序）。并求其等概率情况下的平均查找长度。9. (87, 25, 310, 8, 27, 132, 68, 95, 187, 123, 70, 63, 47)，散列函数为h(k)=k%13，采用链地址法处理冲突。设计出这种链表结构，并求该表平均查找长度。（写出冲突计算过程）10. 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16(015)， 用线性探测再散列处理冲突构造一散列表，设每个记录的查找概率相等,求查找成功的平均查找长度。以上题答案，部分可以参看课件。五程序题1. 用二叉排序树的查找关键字k。设二叉排序树的存储结构如下：存储结构定义：typedef struct BiTNode / 结点结构