树图查找排序复习

树一、判断题：1.二叉树是一棵无序树。（×）2.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。（√）3.度为二的有序树等价于二叉树。（√）4.树的带权路径长度最小的二叉树中必定没有度为1的结点。（√）5.哈夫曼树一定是满二叉树。（×）6.满二叉树也是完全二叉树。（√）7.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（×）8.将一棵树转换成二叉树后，根结点没有左子树(×)9.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（√）10用二叉树的前序遍历和中序遍历可以导出树的后序遍历。（√）11.在完全二叉树中,若某结点无左孩子,则它必是叶结点。（√）。12．任何一棵二叉树都有n0=n2+1的关系式。（√）13．已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树。（√）二、填空题假定一棵二叉树的结点个数为32，则它的最小深度为___6___,最大深度为：32。在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，那么叶子结点有__6____个。树的双亲表示法便于实现涉及到___双亲___的操作，孩子表示法便于实现涉及到孩子的操作。对于一颗具有n个结点的二叉树，对应二叉链表中指针域有__n-1__个用于指向子结点。下图所示二叉树存储在一维数组中，则元素F的下标位置为___11___。（A为1）AABCDEF高度为k的二叉树具有的结点数目，最少为___K___,最多为___2K-1___。对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=__n2+1__。一棵含有16个结点的完全二叉树，对他按层编号，对于编号为7的结点，他的双亲结编号点为___3___左孩子编号为____14__、右孩子编号为___15___。在含100个结点的完全二叉树，叶子结点的个数为___50_____。度数为0的结点，即没有子树的结点叫作___叶子_____结点。同一个结点的儿子结点之间互称为____兄弟____结点。若一棵完全二叉树含有121个结点，则该树的深度为_____7______。已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为____ABCDFE_______。三、选择题在一棵具有n个结点的二叉树中，所有结点的空子树个数等于___C___。A.nB.n-1C.n+1D.2*n在一棵二叉树的第5层上，最多具有___B___个结点。A.14B.16C.31D.32在一棵深度为h的完全二叉树中，所含结点个数不少于___D___。A.2hB.2h+1C.2h-1D.2一棵树的广义表表示为a(b(c),d(e(g(h)),f))，则该二叉树的高度为___D___。A.2B.3C.4D.5将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为___A___。A.30 B.31C.16 D.32在一棵树中，每个结点最多有___B___个直接前驱结点。A.0B.1C.2D.任意多个7.树中所有结点的度数之和等于结点总数加___C___。A.0B.1C二叉树中第5层上的结点个数最多为____C____

A.8 B.15

C.16 D.32将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为___A___。

A.98 B.99由权值分别为3,8,6,2,5的叶子结点生成一颗赫夫曼树，它的带权路径长度为__D___。

A.24B.48C.72D.53把一棵树转换为二叉树后，这棵二叉树的形态是A。

Ａ.唯一的Ｂ.有多种

Ｃ.有多种，但根结点都没有左孩子Ｄ.有多种，但根结点都没有右孩子具有n(n>0)个结点的完全二叉树的深度为C。

Ａélog2(n)ùＢëlog2(n)ûＣëlog2(n)û+1Ｄélog2(n)+1ùù四、应用题1..将下图转换为二叉树，对转换后的二叉树进行先序、中序、后序遍历序列。AABCDEFGJ先序：ABEFCDGJ中序：EFBCGJDA后序：FEJGDCBA2.写出下图所示二叉树的先序、中序、后序序列ABABCDEF中序序列：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已知一棵二叉树的先序、中序和后序遍历序列分别为:（参看课件）先序:BE×KCJADG×HI中序:LK×CAJ××FGIH后序:KL×JCEF××GDB其中有些字母已丢失,请添写完整并画出此二叉树7.在一份电文中共使用8种字符，即a,b,c,d,e,f,g,h，它们出现的频率依次为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，试画出对应的赫夫曼树，求出每个字符的赫夫曼编码，以及带权路径长度。哈夫曼编码:a:0010b:10c:00000d:0001e:01f:000018.写出下图所示森林的先序、中序序列。将该森林转换为相应的二叉树。8812345679101112131415先序序列：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、将如下森林转化成二叉树GHIGHIJEFABCD11、已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。要求画出哈夫曼树，给出编码，并求出带权路径长度）12、假定用于通信的电文仅由a,b,c,d4个数据元素，各字母在电文中出现的频率分别为7，5，2，4，试为这4个字母设计不等长的哈夫曼编码。（要求画出哈夫曼树，给出编码，并求出带权路径长度）a:0b:10c:110d:111或a:1b:01c:001d:000wpl=7*1+5*2+2*3+4*3=3513、在一份电文中共使用8种字符，即a,b,c,d,e,f,g,h，它们出现的频率依次为0.10,0.09,0.32,0.02,0.26,0.03,0.01,0.17，试画出对应的赫夫曼树，求出每个字符的赫夫曼编码。要求画出哈夫曼树，给出编码，并求出带权路径长度）五、算法：中序遍历二叉树（对二叉排序树，按递增顺序输出）。（先写存储结构，再写算法）

存储结构定义：typedefstructBiTNode{//结点结构Selemtypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;voidinorder(BITreet){if(t!=NULL){inorder(t->lchild);printf(“%d”，t->data);inorder(t->rchild);}}图一、判断题：1.图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。（√）2.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。（√）3.如果有向图中各个顶点的度都大于2，则该图中必有回路。（×）4.具有n个顶点的连通图的生成树具有n-1条边（√）5．在n个结点的无向图中,若边数>n-1,则该图必是连通图.(×)6.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（×）7.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。（√）8.若一个有向图的邻接矩阵中对角线以下元素均为零,则该图的拓扑有序序列必定存在（√）（超）9.无向图的邻接矩阵是对称的，有向图的邻接矩阵是不对称的。（√）10.对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（√）11.若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（×）二、填空题对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为___n2___。有一个n个顶点的有向完全图的弧数____n(n-1)_____。在无向图中，若从顶点A到顶点B存在___路径____，则称A与B之间是连通的。在一个无向图中，所有顶点的度数之和等于所有边数的____2___倍。n(n﹥0)个顶点的无向图中顶点的度的最大值为___n-1_____。如果从一个顶点出发又回到该顶点，则此路径叫做___环/回路________。一个具有个n顶点的无向图中，要连通全部顶点至少需要___n-1_____条边。三、选择题1.顶点个数为n的无向图最多有___B___条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)2.n个顶点的连通图至少有___A___条边。A.n-1B.nC.n+1D.03.在一个有向图中，所有顶点的度数之和等于所有弧数的___B___倍。A.3B.2C.1D.1/24.有向图的一个顶点的度为该顶点的__C____。A.入度B.出度C.入度与出度之和D.(入度＋出度)/25.一个连通图的生成树是包含图中所有顶点的一个___C___子图。A.极小B.连通C.极小连通D.无环6.图的深度优先遍历类似于树的___A____。A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历7.下面关于图的存储的叙述中，哪一个是正确的。____A____A.用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B.用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关8．如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是____D___A.有向完全图 B.连通图C.强连通图 D.有向无环图9.具有e条边的有向图，它的逆邻接表中有___B___个弧结点。

A.e-1B.eC.2(e-1)D.2e10.具有e条边的无向图，它的邻接表中有___D___个边结点。

A.e-1B.eC.2(e-1)D.2e11.在一个图中，所有顶点的度数之和等于图的边数的____C____倍。

A．1/2B.1

C.2D.412.用邻接表表示图进行广度优先遍历时，通常是采用B来实现算法的。

A．栈B.队列C.树D.图四、应用题无向图中每个顶点的度，有向图中每个顶点的入度，出度和度。是否是连通图/强连通图，如果不是，画出连通分量/强连通分量。（5分）010124340312顶点01234度顶点01234出度入度是连通图。不是强连通图：强连通分量为：432104321001564201564231261381541610205129请给出下图的邻接矩阵、邻接表、逆邻接表及结点V2的入度和出度。（10分）VV3V1V6V4V2V5下图是用邻接表存储的图，画出此图，写出每个顶点的度，并写出从C点开始按深度优先、广度优先遍历该图的结果。（课件上例题）深度优先遍历序列：C、D、E、A、B、F广度优先遍历序列：C、D、A、E、B、F排序和查找一、判断题进行折半查找的表必须是顺序存储的有序表。（√）在任何情况下，快速排序需要进行关键码比较的次数都是O(nlog2n)。（×）当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。（√）直接选择排序是一种稳定的排序方法。（×）堆排序是一种稳定的排序算法。(×)快速排序法是一种稳定性排序法。（×）散列法存储的基本思想是由关键字的值决定数据的存储地址（√）对n个元素的表用堆排序法进行排序，时间复杂度是O(log2n)（×）在采用线性探测法处理冲突的散列表中,所有同义词在表中一定相邻（×）。堆排序是所需辅助空间最少的排序。（√）一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（√）二、填空题若要对某二叉排序树进行遍历，保证输出元素的值序列按增序排列，应对该二叉排序树采用____________遍历法。中序元素关键字转换为该元素存储位置的函数f称为____________。哈希函数在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序。先将整个待排序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体进行一次直接插入排序，此种排序方法叫做__希尔排序__排序。每次使两个相邻的有序表合并成一个有序表的排序方法叫做______归并______排序。每次从无序表中挑选出一个最大或最小元素，把它交换到有序表的一端，此种排序方法叫做_____简单选择_______排序。每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做______直接插入______排序。每次直接或通过“枢轴”元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做_____快速_______排序。假定一组数据的关键字为{46,79,56,38,40,84}，则利用堆排序方法建立的初始小顶堆为__{38，40，56，79，46，84}__。假定一组数据的关键字为{46,79,56,38,40,84}，则以第一个记录为枢轴，对其进行第一趟快速排序的结果为________{40,38,46,56,79,84}__________。若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=keyMOD9，与18发生冲突的元素有_____9_____三、选择题对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，哨兵位在前，为查找元素26，若采用顺序查找，需要比较____D__次才能查找成功。A.3B.4C.5D.6设哈希表长为14，哈希函数f（k）=k％11，已知表中已有4个元素，关键字分别为15，38，61，84，存储位置分别为4，5，6，7，其它存储位置为空，如用二次探测再散列处理冲突，关键字为49的存储位置是__D____。A.8B.3C.5D.9对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，为查找元素26，若采用折半查找，需要比较___B___次才能查找成功。A.3B.4C.5D.6对线性表进行折半查找时，要求线性表必须__C____。

A.以顺序方式存储

B.以链接方式存储

C.以顺序方式存储，且元素按关键字有序排序

D.以链接方式存储，且元素按关键字有序排序对于哈希函数H(key)=key%13，被称为同义词的关键字是___D____

A．35和41 B.23和39

C.15和44 D.25和51适于对动态查找表进行高效率查找的组织结构是__C____。

A.有序表B.顺序表C.二叉排序树D.链表设哈希表长为14，哈希函数f（k）=k％11，已知表中已有4个元素，关键字分别为15，38，61，84，存储位置分别为4，5，6，7，其它存储位置为空，如用二次探测再散列处理冲突，关键字为49的存储位置是___D___。

A.8B.3C.5D.9用某种排序方法对关键字序列（23，72，21，47，15，27，59，35，20）进行排序时，前三趟的结果情况如下

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.快速排序在对n个元素进行简单选择排序的过程中，需要进行___B___趟选择和交换。

A.n/2B.n-1C.nD.n+1若一组记录的排序码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为____C____

Ａ.38,40,46,56,79,84

Ｂ.40,38,46,79,56,84

Ｃ.40,38，46,56,79,84

Ｄ.40,38,46,84,56,79对于哈希函数H(key)=key%13，被称为同义词（即冲突）的关键字是___D____

A．35和41 B.23和39

C.15和44 D.25和51若对n个元素进行直接插入排序，在进行i趟(2≤i≤n)排序时，为寻找插入位置最多需要进行___C___次元素的比较。

A.i+1B.i-1C.iD.1在对n个元素进行快速排序的过程中，第一趟排序最多需要交换__B____对元素。

A.n/2B.n-1C.nD.n+1在对n个元素进行简单选择排序的过程中，需要进行___B___趟选择和交换。

A.n/2B.n-1C.nD.n+1堆的形状是一棵___A____。

A.二叉排序树B.满二叉树

C.完全二叉树 D.平衡二叉树对于哈希函数H(key)=key%13，被称为同义词的关键字是___D____。

A．35和41 B.23和39

C.15和44 D.25和51从二叉搜索树中查找一个元素时，其时间复杂度大致为___C_____。

A、O(n)B、O(1)

C、O(log2n)D、O(n2)堆是一种B排序。

Ａ.插入Ｂ.选择Ｃ.交换Ｄ.归并折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中A比较大小，查找结果是失败。

A．20，70，30，50B．30，88，70，50

C．20，50D．30，88，50快速排序是一种C排序。

Ａ.插入Ｂ.选择Ｃ.交换Ｄ.归并四、应用题已知一组关键字为（26，36，41，38，44，15，68，12，06，51，25），用线性探查法解决冲突构造这组关键字的哈希表。表长取15，哈希函数H(key)=keyMOD13。用序列（46，88，45，39，70，58，101，10，66，34）建立一个平衡的二叉排序树，画出该树，并求在等概率情况下查找成功的平均查找长度。关键码的输入序列{55,31,11,37,46,73,63,02,07}请计算在二分法查找、平衡的二叉排序树两种的情况下等概率下查找成功的平均查找长度。一组键值序列为(41，66，73，52，40，37，65，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。.已知一组关键字为（19，14，23，01，68，20，84，27，55，11,10，79），则按哈希函数H(key)=keyMOD13和链地址法解决冲突构造这组关键字的哈希表。.给出一组关键字(19，01，26，92，87，11，43，87，21)，进行起泡排序，试列出每一遍排序后关键字的排列次序，并统计每遍排序关键字所进行的关键字比较次数已知一组键值序列为(41，66，73，52，40，37，65，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。（5分）已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0．．6)，待散列序列为：(25，48，32，50，68，43)。要求：（1）根据以上条件构造一散列表，并用线性探测再散列解决有关地址冲突。（2）求在等概率下查找成功的平均查找长度。散列表：已知长度为12的表如下：

｛Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec｝

建立相应的平衡二叉排序树（按字典顺序）。并求其等概率情况下的平均查找长度。(87,25,310,8,27,132,68,95,187,123,70,63,47)，散列函数为h(k)=k%13，采用链地址法处理冲突。设计出这种链表结构，并求该表平均查找长度。（写出冲突计算过程）已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=keyMOD13,哈希表长为m=16(0……15)，用线性探测再散列处理冲突构造一散列表，设每个记录的查找概率相等,求查找成功的平均查找长度。

以上题答案，部分可以参看课件。五．程序题用二叉排序树的查找关键字k。设二叉排序树的存储结构如下：存储结构定义：typedefstructBiTNode{//结点结构intdata;structBiTNode*lch,*rch;}BiTNode,*BiTree;voidbstsrch(BTnode*r,BTnode*p,BTnode*q,intk) {intflag=0; p=NULL;q=r; while((q!=NULL)&&(flag==0)) if(____q->data==k________) {printf(“succ%5d”,q->data);flag=1;} elseif(k<q->data) {p=q;__q=q->lch; __________} else{p=q;____q=q->rch;________} if(flag==0)printf(“NOnode.”); }在有序表中进行折半查找关键字k。voidsearchbinary(inta[],intn,intk){ intlow=0,high=n-1,mid,find=0;while((find==0)&&(low<=high)){____mid=(low+high)/2________if(k