数据结构画图题复习资料

2．应用题（1）试找出满足下列条件的二叉树①先序序列与后序序列相同②中序序列与后序序列相同③先序序列与中序序列相同④中序序列与层次遍历序列相同先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下：（１）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树（２）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树．（３）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．（４）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树（2）设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC①画出这棵二叉树。②画出这棵二叉树的后序线索树。③将这棵二叉树转换成对应的树（或森林）。(1)(2)（4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。初态:weightparentlchildrchild13000212000370004400052000680007110008000900010000110001200013000ABMFD(3)CEMHGAEDCBHGFAEDCBHGFnull终态2．应用题（1）已知如图6.27所示的有向图，请给出：①每个顶点的入度和出度；②邻接矩阵；③邻接表；④逆邻接表。（2）已知如图6.28所示的无向网，请给出：①邻接矩阵；②邻接表；③最小生成树weightparentlchildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112图6.28无向网图6.27有向图6456252363794567555553955434a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。（4）有向网如图6.30所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。D终点i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e∞10(a,c,e)10(a,c,e)f∞6(a,c,f)g∞∞16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S终点集{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,f,e,d,g,b}图6.29邻接矩阵图6.30有向网（5）试对图6.31所示的AOE-网：①求这个工程最早可能在什么时间结束；②求每个活动的最早开始时间和最迟开始时间；③确定哪些活动是关键活动【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l-e=0?来确定关键活动，从而确定关键路径。123456Ve01915293843Vl019153738431,21,33,22,42,53,54,65,6e00151919152938l170152719273738l-e1700801280此工程最早完成时间为43。关键路径为1,33,22,55,6（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：①画出描述折半查找过程的判定树；②若查找元素54，需依次与哪些元素比较？③若查找元素90，需依次与哪些元素比较？④假定每个元素的查找概率相等，求查找成功时的平均查找长度。①先画出判定树如下（注：mid=(1+12)/2=6）：30563374287424547295②查找元素54，需依次与30,63,42,54元素比较；③查找元素90，需依次与30,63,87,95元素比较；④求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.08图6.31AOE-网（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。1271721116214913验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17，21（3）已知如下所示长度为12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）①试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。②若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。③按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。解：（4）对下面的3阶B-树，依次执行下列操作，画出各步操作的结果。①插入90②插入25③插入45④删除60503010060808203540（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：①画出哈希表的示意图；②若查找关键字63，需要依次与哪些关键字进行比较？③若查找关键字60，需要依次与哪些关键字比较？④假定每个关键字的查找概率相等，求查找成功时的平均查找长度。①画表如下：012345678910111213141516173217634924401030314647②查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！③查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。④对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3+6）＝23/11（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key%7，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0123456789关键字140192384275520比较次数11123412平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以关键字27为例：H（27）=27%7=6（冲突）H1=（6+1）%10=7（冲突）H2=（6+22）%10=0（冲突）H3=（6+33）%10=5所以比较了4次。（7）设哈希函数H（K）=3Kmod11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。①线性探测法；②链地址法。①散列地址012345678910关键字412493813243221比较次数11121212ASLsucc=（1+1+1+2+1+2+1+2）/8=11/8ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11②ASLsucc=（1*5+2*3）/8=11/8ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：①画出哈希表的示意图；②若查找关键字63，需要依次与哪些关键字进行比较？③若查找关键字60，需要依次与哪些关键字比较？④假定每个关键字的查找概率相等，求查找成功时的平均查找长度。解：（1）画表如下：012345678910111213141516173217634924401030314647（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。（4）对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3+6）＝23/11（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key%7，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0123456789关键字140192384275520比较次数11123412平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以关键字27为例：H（27）=27%7=6（冲突）H1=（6+1）%10=7（冲突）H2=（6+22）%10=0（冲突）H3=（6+33）%10=5所以比较了4次。（7）设哈希函数H（K）=3Kmod11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。①线性探测法；②链地址法。散列地址012345678910关键字412493813243221比较次数11121212ASLsucc=（1+1+1+2+1+2+1+2）/8=11/8ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/112．应用题（1）设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。①直接插入排序②折半插入排序③希尔排序（增量选取5，3，1）④冒泡排序⑤快速排序⑥简单选择排序⑦堆排序⑧二路归并排序①直接插入排序[212]1630281016*20618[21216]30281016*20618[2121630]281016*20618[212162830]1016*20618[21012162830]16*20618[210121616*2830]20618[210121616*202830]618[2610121616*202830]18[2610121616*18202830]②折半插入排序排序过程同①③希尔排序（增量选取5，3，1）102166181216*203028（增量选取5）621210181616*203