数据结构 第二版 课后答案 (陈雁 著) 高等教育出版社

第一章习题1、简述下列术语数据元素、数据、数据对象、数据结构、存储结构和算法解数据元素数据的基本单位。在计算机程序中通常作为一个整体进行考虑和处理。数据信息的载体。是描述客观事物的数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。数据对象性质相同的数据元素的集合，是数据的一个子集。数据结构相互之间存在着一种或多种关系的数据元素的集合，包括数据的逻辑结构和物理结构两方面的内容。存储结构数据的逻辑结构在计算集中的表示方式，包含顺序存储方法、链接存储方法、索引存储方法、散列存储方法。算法对特定问题求解步骤的一种描述，它是指令或语句的有限序列，并具有有穷型、确定性、可行性、输入和输出五个重要特性。2、试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值解VOIDF1VOIDINTX,Y,ZPRINTF“ENTERX,Y,Z“SCANF“D,D,D“,IFXYIFYZPRINTF“D,D,D“,X,Y,ZELSEIFXZPRINTF“D,D,D“,X,Z,YELSEPRINTF“D,D,D“,Z,X,YELSEIFXZPRINTF“D,D,D“,Y,X,ZELSEIFZYPRINTF“D,D,D“,Z,Y,XELSEPRINTF“D,D,D“,Y,Z,X3、举出一个数据结构的例子，叙述其逻辑结构、存储结构、运算等三方面的内容解4、分析下列算法的时间复杂度（1）INTPRIMEINTNFORI2ILEN0RETURN1/表已空/WHILEILENIFLELEMIXFORJIJLEN1JLELEMJLELEMJ1/被删除元素之后的元素左移/LLENELSEIRETURN14、设线性表A1，A2，AN存储在带表头结点的单链表中，试设计算法，求出该线性表中值为X的元素的序号。如果X不存在，则序号为0。INTINDEX_LINKSTLNODEH,ELEMTPXPHNEXTJ1F0/P指向第一个结点，J为计数器，F为标志/WHILEPIFPDATAXJPPNEXTELSEF1IFF1RETURNJELSERETURN05、在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍为非递减有序。分别写出用顺序表和单链表表示时的算法。顺序表INTINSERT_SQSQLISTL,ELEMTPXIFLLENMAXSIZE1RETURN1/表已满/IFXLELEMLLENLELEMLLEN1XLLEN1ELSEI1WHILEXLELEMIIFORJLLENJIJLELEMJ1LELEMJLELEMIXLLEN1RETURN1单链表INTINSERT_LINKSTLNODEH,ELEMTPXPHSLNODEMALLOCSIZEOFLNODEIFSSDATAXSNEXTNULLELSERETURN0WHILEPNEXTIFPNEXTDATANEXTELSESNEXTPNEXTPNEXTS/插入/RETURN1/INSERT_LINKST/PNEXTSRETURN16、设一个线性表LA1，A2，AN，编写算法将其逆置，即成为（AN，AN1，A2，A1）。要求逆置后的线性表仍占用原来的存储空间，并且用顺序和单链表两种方法表示，写出不同的处理过程。顺序表VOIDINVERSE_SQSQLISTL）INTIELEMTPXFORI1ILEN/2IXLELEMILELEMILELEMLLENI1LELEMLLENI1X单链表VOIDINVERSE_LINKSTLNODEH）DHNEXTIFDNULLPDNEXTWHILEPTPNEXTPNEXTDDPPTHD7、设两个单链表A和B，它们的数据元素分别为X1，X2，,XM和Y1，Y2，YN。设计一个算法将它们合并为一个单链表C，使得当MN时，CX1，Y1，X2，Y2，XN，YN，,XM当NM时，CY1，X1，Y2，X2，YM，XM，,YN。LNODELINK_LINKSTLNODEA,LNODEBPANEXTQBNEXTM0N0WHILEPMPPNEXTWHILEQNQQNEXTIFMNPANEXTQBNEXTCAELSEPBNEXTQANEXTCBWHILEQTPNEXTPNEXTQQQNEXTPNEXTNEXTTPTRETURNC8、试写一算法，在无表头结点的单链表中值为A的结点前插入一个值为B的结点,如果A不存在，则把B插在表尾。将该算法与第232节中的算法27进行比较。VOIDINSERTX_LINKSTLNODEH,ELEMTPA,ELEMTPBSLNODEMALLOCSIZEOFLNODESDATABSNEXTNULLIFHNULLHSELSEPHQPNEXTIFPDATAA/对首元节点处理/SNEXTPHSELSEWHILEQQQNEXTPNEXTSSNEXTQ9、假设有一个单向循环链表，其结点包含三个域DATA，PRE和NEXT，其中DATA为数据域，NEXT为指针域，其值为后继结点的地址，PRE也为指针域，其初值为空（NULL），试设计算法将此单向循环链表改为双向循环链表。VOIDCHANGE_LINKSTLNODEHQHPHNEXTWHILEPPPREQQPPPNEXTHPREQQNEXTH10、已知二维数组A57，其每个元素占四个存储单元，且A00的存储地址为1100，试求出元素A35的存储地址（分别讨论以行为序和以列为序方式存储时的结论）。行为序110043751204列为序11004553121211、设有一个二维数组AMN，对以下三种情况分别编写算法（1）求数组A的最外围元素之和；（2）求从A00开始的互不相邻的各元素之和；（3）当MN时，分别求两条对角线上的元素之和，否则输出MN的信息。INTA1INTAMN/求数组A的最外围元素之和/S0FORI0IM30070010200000000003A543113231312147MCHEADMRHEADCELEMKJAELEMIJCELEMKVAELEMIVKIELSEIFAELEMIJBELEMJJCELEMKIBELEMJICELEMKJBELEMJJCELEMKVBELEMJVKJELSECELEMKIBELEMJICELEMKJBELEMJJCELEMKVBELEMJVAELEMIVKJIELSEIFAELEMIIELEMJI/若A当前项的行号小于B当前项的行号，则将A项放入C/CELEMKIAELEMIICELEMKJAELEMIJCELEMKVAELEMIVKIELSE/若A当前项的行号大于B当前项的行号，则将B项放入C/CELEMKIBELEMJICELEMKJBELEMJJCELEMKVBELEMJVKJCMAM/C的行数/CNAN/C的列数/CTK1/C的非零元个数/14、设稀疏矩阵A用十字链表表示，编写算法查找元素（1）已知I，J，查找AIJ；（2）已知X的值，查找它在第几行第几列。解（1）INTFINDMATCROSSLISTM,INTI,INTJ,INTVALIFIMUWHILEPIFPCOLJVALPVALRETURN1/找到/ELSEPPRIGHTRETURN0/未找到/ELSERETURN1/行号错误/（2）INTFINDMATCROSSLISTM,INTX,INTROWN,INTCOLNFORINTI1IMUIPMRHEADIWHILEPIFPVALXROWNPROWCOLNPCOLRETURN1ELSEPPRIGHTRETURN0上机实习题1设A（A1,A2,AN）和B（B1,B2,BM）是两个线性表，其数据类型是整型。若NM且AIBI1IN,则称AB；若AIBJ（1IJ），而AJBJJNM,则称AB；除此以外，均称AB。设计一个比较A、B大小的程序。INCLUDEDEFINEMAXSIZE100TYPEDEFSTRUCTINTELEMMAXSIZE/存储线性表中的元素/INTLEN/线性表的当前表长/SQLISTSQLISTINITLISTSQLISTLLSQLISTMALLOCSIZEOFSQLISTLLEN0RETURNLINTINSERTSQLISTL,INTI,INTXINTJIFILLEN1RETURN0/不合理的插入位置I/IFLLENMAXSIZE1RETURN1/表已满/FORJLLENJIJLELEMJ1LELEMJ/插入位置及之后的元素右移/LELEMIX/插入X/LLEN/表长加1/RETURN1INTFSQLISTA,SQLISTBSQLISTASNULL,BSNULLINTI1,J,MS0,NS0ASINITLISTASBSINITLISTBSWHILEAELEMIBELEMIIFORJIJLENJINSERTAS,JI1,AELEMJFORJIJLENJINSERTBS,JI1,BELEMJMSASLENNSBSLENIFMSNSELSEIFMS0ELSERETURN1INTMAINSQLISTANULL,BNULLINTN0,M0,I0,D0AINITLISTABINITLISTBIFABPRINTF“AB“ELSEPRINTF“AB“PRINTF“NINPUTN“SCANF“D“,FORI1ILENIPRINTF“D“,AELEMIPRINTF“N“PRINTF“NINPUTM“SCANF“D“,FORI1ILENIPRINTF“D“,BELEMIPRINTF“N“PRINTF“N“FORI1ILENIPRINTF“D“,AELEMIPRINTF“N“FORI1ILENIPRINTF“D“,BELEMIIFA,BIFI0PRINTF“AB“ELSEIFIB“RETURN02设计一个程序求出约瑟夫环的出列顺序。约瑟夫（JOSEPH）问题的一种描述是编号为1，2，N的N个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值M，从第一个人开始按顺时针方向自1开始顺序报数，报到M时停止报数。报M的人出列，将他的密码作为新的M值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。例如N7,7个人的密码依次为3，1，7，2，4，8，4，M的初值取6，则正确的出列顺序应为6，1，4，7，2，3，5。要求使用单向循环链表模拟此出列过程。INCLUDETYPEDEFSTRUCTNODEINTDATASTRUCTNODENEXTINTIDLNODELNODEINSERTLNODEREAR,INTX,INTIDLNODESSLNODEMALLOCSIZEOFLNODESDATAXSIDIDIFREARNULLREARSSNEXTSRETURNREARELSESNEXTREARNEXTREARNEXTSREARSRETURNREARINTMAINLNODEREARNULL,PNULL,QNULLINTD,M,I1PRINTF“INPUT“SCANF“D“,WHILED0REARINSERTREAR,D,IPRINTF“NINPUT“SCANF“D“,PREARNEXT/显示数据/WHILEPREARPRINTF“D“,PDATAPPNEXTPRINTF“D“,PDATAPRINTF“INPUTM“/输入初始M/SCANF“D“,PREARWHILEPPNEXTFORI1INEXTQPNEXTPNEXTQNEXTMQDATAPRINTF“D“,QIDFREEQPRINTF“D“,PIDFREEPRETURN0第三章习题L假定有编号为A、B、C的3辆列车，顺序开进一个栈式结构的站台，请写出开出车站站台的列车顺序注每一列车由站台开出时均可进栈，出栈开出站台，但不允许出栈后回退。写出每一种可能的序列。解产生ABC、ACB、BAC、BCA、CBA不会产生CAB2有字符串次序为5YA/Y2，试利用栈排出将次序改变为5YAY/的操作步骤（可用X代表扫描该字符串过程中顺序取一字符进栈的操作，用S代表从栈中取出一字符加到新字符串尾的出栈的操作）。例如，ABC变为BCA的操作步骤为XXSXSS。解XSXXXSSSXXSXXSXXSSSS3写出链栈的取栈顶元素和置栈空的算法。解（1）INTGETTOPSNODETOP,ELEMTPYIFTOPNULLRETURN1ELSEYTOPDATARETURN1（2）SNODEEMPTYSNODETOPWHILETOPPTOPTOPTOPNEXTFREEPRETURNNULL4假设一个算术表达式中包含圆括弧、方括弧和花括弧，编写一个判别表达式中括弧是否正确配对的算法。解INTFINITSTACKPPUSHP,CGETCHARWHILEC|GETTOPPIFC|C|CPUSHP,CIFCPOPP,OIFORETURN1IFCPOPP,OIFORETURN1IFCPOPP,OIFORETURN1CGETCHARRETURN15写出计算表达式534/67时操作数栈和运算符栈的变化情况。解步骤OPTROPND输入字符1534/672534/673534/6745，34/6755，34/6765，3，4/6775，12/678/5，12679/5，12，67105，2，711771277137，71406对于给定的十进制正整数，打印出对应的八进制正整数。1写出递归算法。2写出非递归算法。解INTFINTN/递归算法/IFN1/退栈求值/FVALSTACKTOP0TOPSTACKTOP2FVALSTACKTOP0STACKTOP1STACKTOP2RETURNSTACKTOP08对于一个具有M个单元的循环队列，写出求队列中元素个数的公式。解SQFRONTSQREARMM9假设用一个数组QM来表示队列，该队列只设一个队头指针FRONT，不设队尾指针而改设计数器COUNT用以记录队列中元素的个数。试编写出相应的置空队列，入队列和出队列的算法。解TYPEDEFSTRUCTELEMTPELEMMAXSIZEINTFRONT/队头/INTCOUNTMYSQQUEUEVOIDEMPTYMYSQQUEUESQ/置空队列/SQFRONT0SQCOUNT0INTENQUEUEMYSQQUEUESQ，ELENTPX/在循环队列SQ的尾部插入一个新的元素X/IFSQCOUNTMAXSIZERETURN1/队列上溢/ELSESQCOUNTSQELEMSQFRONTSQCOUNTMAXSIZEXRETURN1INTDELQUEUEMYSQQUEUESQ，ELEMTPY/删除循环队列SQ的队头元素，并存人Y中/IFSQCOUNT0RETURN1/队列下溢/ELSESQFRONTSQFRONT1MAXSIZEYSQELEMSQFRONTSQCOUNTRETURN110假设以带头结点的循环链表示列队，并且只设一个指针指向队尾元素结点注意不设头指针，试编写出相应的置空队列，入队列和出队列的算法。解TYPEDEFSTRUCTNODE/结点结构/ELEMTPDATASTRUCTNODENEXTQNODETYPEDEFSTRUCTQNONEREAR/队尾指针/MYLQUEUEVOIDEMPTYMYLQUEUELQ/置空队列/IFLQREARNULL/循环队列为非空/HEADLQREARNEXTWHILEHEADLQREARPHEADHEADHEADNEXTFREEPFREEHEADLQREARNULLINTENQUEUEMYLQUEUELQ，ELENTPX/在循环队列SQ的尾部插入一个新的元素X/PQNONEMALLOCSIZEOFQNONEIFPNULLRETURN1ELSEPDATAXPNEXTNULLIFLQREARNULL/循环队列为空/LQREARPPNEXTPELSEHEADLQREARNEXTLQREARNEXTSLQREARSSNEXTHEADRETURN1INTDELQUEUEMYLQUEUELQ，ELEMTPY/删除循环队列SQ的队头元素，并存人Y中/IFLQREARNULL/队列下溢/RETURN1ELSEHEADLQREARNEXTIFHEADLQREAR/只有一个节点/YHEADDATAFREEHEADLQREARNULLELSEYHEADDATALQREARNEXTHEADNEXTFREEHEADRETURN1上机实习题1设计一个算法，检验C源程序代码中的括弧对是否正确配对。要求在某个C源程序文件上对你的算法进行验正。INCLUDETYPEDEFSTRUCTNODECHARDATASTRUCTNODENEXTSNODESNODEPUSHSNODETOP,CHARXSNODEPPSNODEMALLOCSIZEOFSNODEPDATAXPNEXTTOPTOPPRETURNTOPSNODEPOPSNODETOP,CHARY,INTFLAGSNODEPIFTOPNULLFLAG0/链栈已空/ELSE/出栈/PTOPYPDATATOPPNEXTFLAG1RETURNTOPINTMAININTARGC,CHARARGVFILEFPCHARCH,OINTFLAG1SNODEPNULLIFARGC2PRINTF“YOUFORGOTTOENTERTHEFILENAMEN“EXIT1IFFPFOPENARGV1,“R“NULLPRINTF“CANNOTOPENFILEN“EXIT1CHGETCFPWHILECHEOFIFCH|CH|CHPRINTF“PUSHCN“,CHPPUSHP,CHIFCHPPOPP,PRINTF“POPC,DN“,O,FLAGIFFLAG0PRINTF“DLOSE“ELSESWITCHOCASEBREAKCASEPRINTF“LOSE“EXIT0CASEPRINTF“LOSE“EXIT0IFCHPPOPP,PRINTF“POPC,DN“,O,FLAGIFFLAG0PRINTF“DLOSE“ELSESWITCHOCASEPRINTF“LOSE“EXIT0CASEBREAKCASEPRINTF“LOSE“EXIT0IFCHPPOPP,PRINTF“POPC,DN“,O,FLAGIFFLAG0PRINTF“DLOSE“ELSESWITCHOCASEPRINTF“LOSE“EXIT0CASEPRINTF“LOSE“EXIT0CASEBREAKCHGETCFPPPOPP,IFFLAG0PRINTF“OK“WHILEFLAG0/如果栈未空/SWITCHOCASEPRINTF“LOSE“BREAKCASEPRINTF“LOSE“BREAKCASEPRINTF“LOSE“BREAKPPOPP,FCLOSEFPRETURN02设计程序，模拟手机的某些短信息功能。功能要求（1）接受短信息，若超过存储容量（如最多可存储20条），自动将最早接受的信息删除。（2）显示短信息数量。（3）逐条显示短信息（从最新的开始）；（4）删除其中的任意一条短信息；（5）清除。/（1）接受短信息，若超过存储容量（如最多可存储20条），自动将最早接受的信息删除。（2）显示短信息数量。（3）逐条显示短信息（从最新的开始）；（4）删除其中的任意一条短信息；（5）清除。/INCLUDEINCLUDEINCLUDEDEFINEMAXSIZE20/存储容量/DEFINEINFOLEN100/信息长度/TYPEDEFSTRUCTNODE/结点结构/CHARINFOINFOLENSTRUCTNODENEXTQNODETYPEDEFSTRUCTQNODEFRONT/队头指针/QNODEREAR/队尾指针/INTCOUNTMYINFOMYINFOINIT/初始化/MYINFOPQNODEQPMYINFOMALLOCSIZEOFMYINFOPCOUNT0QQNODEMALLOCSIZEOFQNODEQNEXTNULLPFRONTQPREARQRETURNPINTGETNEWMYINFOLQ/获得新短信/TIME_TTSTRUCTTMLOCALQNODEPTTIMENULLLOCALLOCALTIME/获得时间信息，模拟短信内容/IFLQCOUNTMAXSIZEDELETELQPQNODEMALLOCSIZEOFQNODESTRCPYPINFO,ASCTIMELOCALPNEXTNULLLQREARNEXTPLQREARPLQCOUNTRETURN1INTDELETEMYINFOLQ/删除循环队列LQ的队头元素/QNODEPIFLQFRONTLQREARRETURN0PLQFRONTNEXT/P指向新的队头结点/LQFRONTNEXTPNEXTIFLQREARPLQREARLQFRONT/尾指针指向头结点/FREEPLQCOUNTRETURN1INTDELETEIMYINFOLQ,INTI/删除循环队列LQ的第I个元素/QNODEP,QINTN1IFLQFRONTLQREAR|ILQCOUNTRETURN0PLQFRONTWHILENNEXTNQPNEXTPNEXTQNEXTIFLQREARQLQREARP/尾指针指向前结点/FREEQLQCOUNTRETURN1VOIDECHOMYINFOLQ,INTI/显示第I条短信/QNODEPLQFRONTNEXTINTN1IFI0NPRINTF“MESSAGEDOFDSN“,I,LQCOUNT,PINFOVOIDREMOVEMYINFOLQWHILELQFRONTLQREARDELETELQVOIDPRINTHLPPRINTF“NNNN“PRINTF“N“PRINTF“PRESSGTOGETNEWMESSAGEN“PRINTF“PRESSETOECHOMESSAGEN“PRINTF“PRESSDTODELETEAMESSAGEN“PRINTF“PRESSPTODELETELASTMESSAGEN“PRINTF“PRESSRTOREMOVEALLN“PRINTF“N“PRINTF“N“PRINTF“PRESSQTOQUITN“PRINTF“N“PRINTF“N“PRINTF“NNNN“INTMAINCHARCMYINFOPINTIPINITPRINTHLPCGETCHWHILECQBREAKCASEE/显示消息/CASEEFORI1ICOUNTIECHOP,IBREAKCASED/删除当前消息/CASEDPRINTF“INPUTI“SCANF“D“,DELETEIP,IBREAKCASEP/删除最先的纪录/CASEPDELETEPBREAKCASER/清楚所有消息/CASERREMOVEPBREAKCGETCHPRINTHLPREMOVEPRETURN0ABDJIEKHGFC题图41树T第四章1有一棵树如题图41所示，求出树的叶子结点、非终端结点、各结点的度、树的度和树深。解（1）叶子结点E、F、G、H、K、J（2）非终端结点A、B、C、D、I（3）各结点的度度为3的结点A、C度为2的结点D度为1的结点B、I度为0的结点E、F、G、H、K、J（4）树的度3（5）树深42具有三个结点的二叉树有多少种不同的形态请分别画出。解具有三个结点的二叉树有5种不同的形态，如下所示3如果一棵树有N1个度为1的结点，N2个度为2的结点，NM个度为M的结点，则该树共有多少个叶子结点可参考二叉树性质3的证明方法来思考M叉树问题。解设树中有N0个叶子结点，那么树中总结点数N为NN0N1NM（A）由于树中除根结点外，其它各结点都有仅有一个分支指向它，所以树中的总结点数恰好比分支数少1。设B为树中总分支数，即有BN1另外，除度为0的结点没有分支外，每个度为K的结点有K个分支，所以总分支数又为B1N12N2MNM即总结点数为NN12N2MNM1（B）由式A和式B有N0N1NMN12N2MNM1即得N01N22N3（I1）NI（M1）NM1（I1）NI1（I2M）4写出按层遍历二叉树的算法。解二叉链表结点结构描述为TYPEDEFSTRUCTBTNODEELEMTPDATA/数据域/STRUCTBTNODELCHILD,RCHILD/左、右孩子指针域/BTNODEVOIDLEVORDERBTNODEBT/按层次遍历二叉树BT非递归算法，Q是BTNODE类型的队列/INITQUEUEQ/初始化队列Q/IFBTENQUEUEQ,BT/根结点入队列/WHILEQUEUEEMPTYQ/队列非空/DELQUEUEQ,/队头元素存入变量P中/VISITPDATA/访问根结点/IFPLCHILDENQUEUEQ,PLCHILDIFPRCHILDENQUEUEQ,PRCHILD/LEVORDER/5设计算法求二叉树中度为1的结点数。解设置一个初始值为0的全局变量COUNT进行计数，在对二叉树进行遍历的过程中判断当前所访问的结点是否为度为1的结点，若是则COUNT加1。因此当遍历完整个二叉树后，COUNT的值就是度为1的结点的数目。算法描述如下INTCOUNT0VOIDCOUNTDEGREE1BTNODEBTIFBTIFBTLCHILD/计数/COUNTDEGREE1BTLCHILDCOUNTDEGREE1BTRCHILD/COUNTDEGREE1/6设计递归算法，求出先根序列中第K个结点的值。解CHARLOCAT_BTBTREEBT,INTK/求先序序列中第K个结点的值的递归算法/STATICINTNNKIFBTNIFN0RETURNBTDATALOCAT_BTBTLCHILD,NIFN0LOCAT_BTBTRCHILD,NELSERETURN7现有按中根遍历二叉树的结果为ABC，请画出可以得到这一结果的全部二叉树。解8已知遍历某二叉树后的中根遍历序列CDBAFGEIHJ和后根遍历序列DCBGFIJHEA，试画出该二叉树。解根据二叉树后的中根遍历和后根遍历的特点，其中根遍历序列和后根遍历序列的形式如下所示显然，后根历序列中的最后一个结点就是二叉树的根结点，然后再在中根序列中找出根结点所在位置。根据根结点的位置可以将中根序列划分为两部分，其中在根结点之前的子序列为左子树的中根序列，而根结点之后的子序列为右子树的中根序列。由于左子树的后根序列长度应与中根序列长度相等，因此可以从二叉树的后根历序列中找出左子树的后根序列，同也可以找出右子树的后根序列。这样，我们可以根据左、右子树的中根序列和后根序列，按照上述方法继续划分，直到划分的子序列为空。在这个划分过程中，可以逐步构造出唯一的一棵二叉树。构造过程如下图（A）F所示ACDBFGEIHJABAFGEIHJCDBCDBAFGEIHJCEFGCDBAIHJDFGECDBAIHJEJHIFGECDBAFCBACABBACBACACB中根遍历序列后根遍历序列左子树中根序列根右子树中根序列左子树中根序列右子树中根序列根9画出题图42所示二叉树的先根、中根、和后根线索化树。解先根遍历序列ABDGCEHJKFI中根遍历序列BGDAEJHKCIF后根遍历序列GDBJKHEIFCAA先根线索树NULLDEBAHIFCGJKDEBAHIFCGJKNULLNULL（B）中根线索树DEBAHIFCGJK（C）后根线索树NULL题图42FBDHKGJICAE10根据442节中根线索递归算法，改写成一个结点结构仅有4个域无左标志域，试建立其后继线索的递归算法。解线索链表结点结构类型TYPEDEFSTRUCTTHRNODETELEMTPDATASTRUCTTHRNODELCHILD,RCHILDINTRTAGTHRNODE2VOIDINTHREAD2THRNODE2TTHRNODE2PREVOIDCRT_INTHREAD2THRNODE2THRT/已知THRT指向二叉树的根结点，中序遍历建立中序后继线索二叉树/PRENULLINTHREAD2THRT/中序遍历线索化/PRERTAG1/最后一个结点线索化/CRT_INTHREAD2/VOIDINTHREAD2THRNODET/中序遍历线索化以T为根的二叉树/IFTINTHREAD2TLCHILD/左子树线索化/IFPRENULLIFPRERCHILDNULL/建立PRE结点的后继线索/PRERTAG1PRERCHILDTPRET/PRE指向T的前驱/INTHREAD2TRCHILD/右子树线索化/INTHREAD2/11画出与题图42所示二叉树对应的森林。解上机实习题一、实习目的1掌握树的结构的非线性特点、递归性特点和动态数据结构等特点。2掌握二叉树的存储结构、各种遍历算法以及基于遍历算法的其他操作的实现。二、实习内容1编写一个C语言程序，对二叉树实现以下操作（1）按先根、中根和后根次序遍历二叉树；（2）按二叉树的层次输出各结点（每一行输出一层）；（3）利用遍历算法，将二叉树中所有结点的左右子树交换。2在一段文字中10个常用汉字及出现的频度如下的地得于个和在再是有2664157685185试为这些常用汉字设计哈夫曼编码表。FBDHKGJICAE第五章1V1入度2,出度1，V2入度1，出度2,V3入度1，出度0，V4入度1，出度2邻接阵G0001101000001100邻接表V1V4V2V1V3V4V1V2逆邻接表V1V2V4V2V4V3V2V4V12广度优先序列是V2,V1,V3,V6,V4,V5深度优先序列是V2,V1,V3,V4,V5,V63深度优先序列是V1,V3,V4,V2,V5（根据存储顺序，如果根据序号大小有不同结果）4给出归并顺序普里姆V1,V3V4V5V2克鲁斯卡尔V4,V5边，V4,V2边，V3,V4边，V3,V1边（有权值相同的边，不唯一）最短路径V1V35V1V615V1V419V1V220V1V5256AOV网络1234V1,V4,或者V4,V1可换V2位置不可变，V5,V3或者V3,V5，V6不可变邻接表中V1,V4,V2,V3,V5,V6第六章1算法说明本程序使用两个结点链交换的方法，比较复杂，要简化的同学可以直接交换内容。代码可以省去三分之二。/INSERTSORTVIALINKLIST/STRUCTNODEINTDATASTRUCTNODENEXTSTRUCTNODELOCATECOUNTSTRUCTNODEH,INTKINTI0STRUCTNODEH1HFORI1INEXTRETURNH1SHOWSTRUCTNODEHEADSTRUCTNODEPPHEADNEXTWHILEP0PRINTF“3D“,PDATAPPNEXTPRINTF“N“RETURNSORTSTRUCTNODEHEADSTRUCTNODEH,SEARCHGOALPTR,P,Q,QSTART,PREGOALSTRUCTNODETEMP,PT1,PT2,GOALNEXTINTCOUNT2HHEADPREGOALHEADNEXTSEARCHGOALPTRHEADNEXTNEXTQSTARTHEADWHILESEARCHGOALPTR0/GO/HDATASEARCHGOALPTRDATAQQSTARTWHILEQNEXTDATADATAQQNEXTPT1QNEXTQNEXTSEARCHGOALPTRPT2SEARCHGOALPTRNEXTSEARCHGOALPTRNEXTPT1PREGOALNEXTPT2PREGOALLOCATECOUNTHEAD,COUNTCOUNTSEARCHGOALPTRLOCATECOUNTHEAD,COUNTSHOWHEAD/WHILE/MAINSTRUCTNODEH,P1,TAILINTVAR0HSTRUCTNODEMALLOCSIZEOFSTRUCTNODEHDATA0HNEXT0/CONSTRUCTALINKEDLIST/WHILE1PRINTF“PLEASEINPUTANODE,ENTER1END“SCANF“D“,IFVAR1BREAKP1STRUCTNODEMALLOCSIZEOFSTRUCTNODEP1DATAVARP1NEXTHNEXTHNEXTP1SHOWHSORTHSHOWH/YESCONSTRUCTED/FREEHRETURN2排序过程5667594198472638755216原始数据1626384152476759759856D51626384152476756759859D31626384147525659677598D13不需要，因为排序已经完成4冒泡过141551028301014152830D快速过程1415302851010153028514101430285151053028141510514283015分左右再内部排序得10141528305直接插入5冒泡5快速146提示改动算法65的判断条件即可。7/INSERTSORTVIALINKLIST/STRUCTNODEINTDATASTRUCTNODENEXTSHOWSTRUCTNODEHEADSTRUCTNODEPPHEADNEXTWHILEP0PRINTF“3D“,PDATAPPNEXTPRINTF“N“RETURNSORTSTRUCTNODEHEADSTRUCTNODEP,PTR1,PTR2INTMININTTEMPPTR1HEADNEXTWHILEPTR1PTR2PTR1NEXTMINPTR1DATAWHILEPTR2IFPTR2DATADATAPTR1DATAPTR2DATAPTR2DATATEMP/IF/PTR2PTR2NEXT/PTR2/PTR1PTR1NEXTSHOWHEAD/WHILE/MAINSTRUCTNODEH,P1,TAILINTVAR0HSTRUCTNODEMALLOCSIZEOFSTRUCTNODEHDATA0HNEXT0/CONSTRUCTALINKEDLIST/WHILE1PRINTF“PLEASEINPUTANODE,ENTER1END“SCANF“D“,IFVAR1BREAKP1STRUCTNODEMALLOCSIZEOFSTRUCTNODEP1DATAVARP1NEXTHNEXTHNEXTP1SHOWHSORTHSHOWH/YESCONSTRUCTED/FREEHRETURN84符合堆的特性。9193426975675是一个堆先19出堆，调整75上来，得197534269756,调整后2634759756，得26调整56上来得56347597调整得34567597出34调整97上来得975675调整得569775出56最后出75和97105667594198472638755216L15667415947982638527516L24156596726384798165275L41626384147525659677598结果原因是R是一次归并结果，放在R2里临时存放，最后放回R以便下次再处理。第七章1有一个有序文件，其中各记录的关键字为3,4,5,6,7,8,10,17,19,20,27,32,43,54,65,76,87，当用折半查找算法查找关键字为4,20,65时，其比较次数分别为多少解该有序文件长度为17，根据折半查找算法画出判定树如下图所示。从图中可得出当关键字为4,20,65时，其比较次数分别为3，4，3。K46571110128213151416491317K20K65判定树、若对大小均为N的有序顺序表和无序顺序表分别进行顺序查找，试就下列三种情况分别讨论两者在等查找概率时的平均查找长度是否相同1查找失败；2查找成功；3查找成功，表中有多个关键字等于给定值的记录，一次查找要求找出所有记录。解1平均查找长度不相同。有序顺序表小于等于无序顺序表。2平均查找长度相同。3平均查找长度不相同，有序顺序表小于等于无序顺序表。、试按下列次序将各关键字插入到二叉平衡树中，画出重新平衡的情况。关键字依次为8、9、12、2、1、5、3、6、7、11解生成并调整成平衡二叉排序树的过程如下图AJ所示。89128RR89B不调整1289C调整A初始91282D不调整912821LL912281E调整9122815LR9128251LL9825112F调整39825112G不调整39825112H不调整6、已知长度为12的表（JAN,FEB,MAR,APR,MAY,JUN,JUL,AUG,SEP,OCT,NOV,DEC）。1试按表中元素的顺序，依次插入一棵初始为空的二叉树；试画出插入完成之后的二叉排序树，并求其在等查找概率情况下查找成功的平均查找长度。2）若对表中元素先进行排序构成有序表，试求在等查找概率情况下对此有序表进行二分查找时查找成功的平均查找长度。解1二叉排序树如下图所示。平均查找长度SAL112233342516/1242/12353982511267RR1985621273I调整111985621273RLRR1211985621173911185621273J调整JANONFEBMARAUGJULDECMAYAPRJUNNOVOCTSEP2对有序表（APR,AUG,DEC,FEB,JAN,JUL,JUN,MAR,MAY,NOV,OCT,SEP）进行二分查找时，其判定树如下图所示,所以平均查找长度SAL11224354/1235/125在题图71所示的3阶B树中，删除关键字37，试画出删除过程。解JULNONDECMAYAUGMAROCTAPRJUNFEBNOVSEPJAN4511523761937810128题图7145115261937810128A删除37452852619378101B双亲28下移6已知一个线性表38，25，74，63，52，48，采用的散列函数为HKEYKEYMOD7，将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为多少若利用链地址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为多少解（1）用线性探测的开放定址法解决冲突的哈希表H383873比较1次H252574比较