最全数据结构答案耿国华高等教育出版社

数据结构耿国华高等教育出版社第1章绪论习题一、问答题1什么是数据结构2四类基本数据结构的名称与含义。3算法的定义与特性。4算法的时间复杂度。5数据类型的概念。6线性结构与非线性结构的差别。7面向对象程序设计语言的特点。8在面向对象程序设计中，类的作用是什么9参数传递的主要方式及特点。10抽象数据类型的概念。二、判断题1线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。2算法就是程序。3在高级语言（如C、或PASCAL）中，指针类型是原子类型。三、计算下列程序段中XX1的语句频度FORI1INEXTS（2）PNEXTPNEXTNEXT（3）PNEXTSNEXT（4）SNEXTPNEXT（5）SNEXTL（6）SNEXTNULL（7）QP（8）WHILEPNEXTQPPNEXT（9）WHILEPNEXTNULLPPNEXT（10）PQ（11）PL（12）LS（13）LP24已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。提示VOIDINSERTSEQLISTLELEMTYPEX（1）找出应插入位置I，（2）移位，（3）参P22925写一算法，从顺序表中删除自第I个元素开始的K个元素。提示注意检查I和K的合法性。（集体搬迁，“新房”、“旧房”）以待移动元素下标M（“旧房号”）为中心，计算应移入位置（“新房号”）FORMI1KMLASTMLELEMMKLELEMM同时以待移动元素下标M和应移入位置J为中心以应移入位置J为中心，计算待移动元素下标26已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于MINK且小于MAXK的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意MINK和MAXK是给定的两个参变量，它们的值为任意的整数）。提示注意检查MINK和MAXK的合法性MINKNEXTWHILEPNULL（2）找到最后一个应删结点的后继S，边找边释放应删结点SPWHILESNULLFREET（3）PRENEXTS27试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（A1,A2,AN）逆置为（AN,AN1,A1）。（1）以一维数组作存储结构，设线性表存于A1ARRSIZE的前ELENUM个分量中。（2）以单链表作存储结构。方法1在原头结点后重新头插一遍方法2可设三个同步移动的指针P,Q,R，将Q的后继R改为P28假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C提示参P28例21VOIDMERGELINKLISTALINKLISTBLINKLISTCPAANEXTPBBNEXTCACNEXTNULLWHILEPANULLPAPANEXTSMALLERNEXTCNEXT/头插法/CNEXTSMALLERELSESMALLERPBPBPBNEXTSMALLERNEXTCNEXTCNEXTSMALLERWHILEPANULLSMALLERPAPAPANEXTSMALLERNEXTCNEXTCNEXTSMALLERWHILEPBNULLSMALLERPBPBPBNEXTSMALLERNEXTCNEXTCNEXTSMALLERLINKLISTMERGELINKLISTALINKLISTBLINKLISTC；PAANEXTPBBNEXTCACNEXTNULLRETURNC29假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知S为指向链表某个结点的指针，试编写算法在链表中删除指针S所指结点的前趋结点。提示设指针P指向S结点的前趋的前趋，则P与S有何关系210已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。211设线性表AA1,A2,AM，BB1,B2,BN，试写一个按下列规则合并A、B为线性表C的算法，使得CA1,B1,AM,BM,BM1,BN当MN时；或者CA1,B1,AN,BN,AN1,AM当MN时。线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意单链表的长度值M和N均未显式存储。提示VOIDMERGELINKLISTALINKLISTBLINKLISTC或LINKLISTMERGELINKLISTALINKLISTB212将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。提示注明用头指针还是尾指针。213建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的DATA域存放一个二进制位。并在此链表上实现对二进制数加1的运算。提示可将低位放在前面。214设多项式PX采用课本中所述链接方法存储。写一算法，对给定的X值，求PX的值。提示FLOATPOLYVALUEPOLYLISTPFLOATX实习题1将若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标。要求（1）给定一个城市名，返回其位置坐标；（2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。2约瑟夫环问题。约瑟夫问题的一种描述是编号为1，2，N的N个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值M,从第一个人开始顺时针自1开始顺序报数，报到M时停止报数。报M的人出列，将他的密码作为新的M值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如M的初值为20；N7，7个人的密码依次是3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5。第二章答案约瑟夫环问题约瑟夫问题的一种描述为编号1,2,N的N个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值M,从第一个人开始顺时针自1开始顺序报数，报到M时停止报数。报M的人出列，将他的密码作为新的M值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如M的初值为20；N7，7个人的密码依次是3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5。【解答】算法如下TYPEDEFSTRUCTNODEINTPASSWORDINTNUMSTRUCTNODENEXTNODE,LINKLISTVOIDJOSEPHUSLINKLISTLNODEP,R,QINTM,N,C,JLNODEMALLOCSIZEOFNODE/初始化单向循环链表/IFLNULLPRINTF“N链表申请不到空间“RETURNLNEXTNULLRLPRINTF“请输入数据N的值N0“SCANF“D“,FORJ1JPASSWORDCPNUMJRNEXTPRPRNEXTLNEXTPRINTF“请输入第一个报数上限值MM0“SCANF“D“,PRINTF“N“PRINTF“出列的顺序为N“QLPLNEXTWHILEN1/计算出列的顺序/J1WHILEJNEXTJPRINTF“D“,PNUMMPPASSWORD/获得新密码/NQNEXTPNEXT/P出列/RPPPNEXTFREERPRINTF“DN“,PNUM27试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（A1,A2,AN）逆置为AN,AN1,A1。【解答】（1）用一维数组作为存储结构VOIDINVERTSEQLISTL,INTNUMINTJELEMTYPETMPFORJ0JNEXTNULLRETURN/链表为空/PLNEXTQPNEXTPNEXTNULL/摘下第一个结点，生成初始逆置表/WHILEQNULL/从第二个结点起依次头插入当前逆置表/RQNEXTQNEXTLNEXTLNEXTQQR211将线性表AA1,A2,AM,BB1,B2,BN合并成线性表C,CA1,B1,AM,BM,BM1,BN当MN时,线性表A、B、C以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意单链表的长度值M和N均未显式存储。【解答】算法如下LINKLISTMERGELINKLISTA,LINKLISTB,LINKLISTCNODEPA,QA,PB,QB,PPAANEXT/PA表示A的当前结点/PBBNEXTPA/利用P来指向新连接的表的表尾，初始值指向表A的头结点/WHILEPANULLQBQBNEXTPNEXTPA/交替选择表A和表B中的结点连接到新链表中；/PPAPNEXTPBPPBPAQAPBQBIFPANULLPNEXTPA/A的长度大于B的长度/IFPBNULLPNEXTPB/B的长度大于A的长度/CARETURNC第3章限定性线性表栈和队列习题1按图31B所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答如进站的车厢序列为123，则可能得到的出站车厢序列是什么123、213、132、231、321（312）如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X62设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。直到队列成为空队列为止，则是否可能得到输出序列（1）A、C、E、C、C（2）A、C、E（3）A、C、E、C、C、C（4）A、C、E、C提示A、B、C、D、E（输出队首元素A）A、B、C、D、E、A（把队首元素A插入到队尾）B、C、D、E、A（删除队首元素A）C、D、E、A（再次删除队首元素B）C、D、E、A（输出队首元素C）C、D、E、A、C（把队首元素C插入到队尾）D、E、A、C（删除队首元素C）E、A、C（再次删除队首元素D）3给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满4按照四则运算加、减、乘、除和幂运算（）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程AB5试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列1CHARCH,TEMPINITSTACKPRINTF“N请输入字符序列”CHGETCHARWHILECHCHGETCHARDO/判断序列2是否是序列1的逆序列/CHGETCHARPOPIFCHTEMP/序列2不是序列1的逆序列/RETURNFALSEPRINTF“NNO”WHILECHPRINTF“NYES”/序列2是序列1的逆序列/ELSERETURNFALSEPRINTF“NNO”/ISHUIWEN/38要求循环队列不损失一个空间全部都能得到利用，设置一个标志TAG,以TAG为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队算法INTENTERQUEUESEQQUEUEQ,QUEUEELEMENTTYPEX/将元素X入队/IFQFRONTQFRONTIFQFRONTQFRONTQELEMEMTQREARXQREARQREAR1MAXSIZE/设置队尾指针/RETURNTRUE出队算法INTDELETEQUEUESEQQUEUEQ,QUEUEELEMENTTYPEX/删除队头元素，用X返回其值/IFQFRONTQREARXQELEMENTQFRONTQFRONTQFRONT1MAXSIZE/重新设置队头指针/IFQFRONTQREARTAG0/队头元素出队后队列为空，重新设置标志域/RETURNTUUE编写求解HANOI问题的算法，并给出三个盘子搬动时的递归调用过程。【解答】算法VOIDHANOIINTN,CHARX,CHARY,CHARZ/将塔座X上按直径由小到大且至上而下编号为1到N的N个圆盘按规则搬到塔座Z上，Y可用做辅助塔座/IFN1MOVEX,1,ZELSEHANOIN1,X,Z,YMOVEX,N,ZHANOIN1,Y,X,ZHANOI3,A,B,C的递归调用过程HANOI2,A,C,BHANOI1,A,B,CMOVEAC1号搬到CMOVEAB2号搬到BHANOI1,C,A,BMOVECB1号搬到BMOVEAC3号搬到CHANOI2,B,A,CHANOI1,B,C,AMOVEBA1号搬到AMOVEBC2号搬到CHANOI1,A,B,CMOVEAC1号搬到C第4章串习题1设SIAMASTUDENT,TGOOD,QWORKER。给出下列操作的结果STRLENGTHSSUBSTRINGSUB1,S,1,7SUBSTRINGSUB2,S,7,1STRINDEXS,A,4STRREPLACES,STUDENT,QSTRCATSTRCATSUB1,T,STRCATSUB2,Q参考答案STRLENGTHS14SUB1IAMA_SUB2_STRINDEXS,A,46STRREPLACES,STUDENT,QIAMAWORKERSTRCATSTRCATSUB1,T,STRCATSUB2,QIAMAGOODWORKER2编写算法，实现串的基本操作STRREPLACES,T,V。3假设以块链结构表示串，块的大小为1，且附设头结点。试编写算法，实现串的下列基本操作STRASIGNS,CHARS；STRCOPYS,T；STRCOMPARES,T；STRLENGTHS；STRCATS,T；SUBSTRINGSUB,S,POS,LEN。说明用单链表实现。4叙述以下每对术语的区别空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。5已知S”XYZ”,T”XZY”。试利用联接、求子串和置换等操作，将S转换为T6S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。7S是用结点大小为4的单链表存储的串,分别编写算法在第K个字符后插入串T，及从第K个字符删除LEN个字符。以下算法用定长顺序串8写下列算法（1）将顺序串R中所有值为CH1的字符换成CH2的字符。（2）将顺序串R中所有字符按照相反的次序仍存放在R中。（3）从顺序串R中删除其值等于CH的所有字符。（4）从顺序串R1中第INDEX个字符起求出首次与串R2相同的子串的起始位置。（5）从顺序串R中删除所有与串R1相同的子串。9写一个函数将顺序串S1中的第I个字符到第J个字符之间的字符用S2串替换。提示（1）用静态顺序串（2）先移位，后复制10写算法，实现顺序串的基本操作STRCOMPARES,T。11写算法，实现顺序串的基本操作STRREPLACESUBSTRINGSUB1,S,1,7SUB1IAMASUBSTRINGSUB2,S,7,1SUB2STRINDEXS,4,A6STRREPLACES,STUDENT,QSIAMAWORKERSTRCATSTRCATSUB1,T,STRCATSUB2,QSUB1IAMAGOODWORKER。42编写算法，实现串的基本操作STRREPLACES,T,V。【解答】算法如下INTSTRREPLACESSTRINGS,SSTRINGT,SSTRINGV/用串V替换S中的所有子串T/INTPOS,IPOSSTRINDEXS,1,T/求S中子串T第一次出现的位置/IFPOS0RETURN0WHILEPOS0/用串V替换S中的所有子串T/SWITCHTLENVLENCASE0/串T的长度等于串V的长度/FORI0ICHPOSIVCHICASE0/串T的长度大于串V的长度/FORIPOSTIENILENI/将S中子串T后的所有字符SCHITLENVLENSCHI前移TLENVLEN个位置/FORI0ICHPOSIVCHISLENSLENTLENVLENCASELENTLENVLENLENTLENVLENIPOSTLENISCHISCHITLENVLENFORI0ICHPOSIVCHISLENSLENTLENVLENELSE/替换后串长MAXLEN,但串V可以全部替换/IFPOSVLENPOSTLENISCHISCHITLENVLENFORI0ICHPOSIVCHISLENMAXLENELSE/串V的部分字符要舍弃/FORI0ICHIPOSVCHISLENMAXLEN/SWITCH/POSSTRINDEXS,POSVLEN,T/求S中下一个子串T的位置/WHILE/RETURN1/STRREPLACE/附加题用链式结构实现定位函数。【解答】TYPEDEFSTRUCTNODECHARDATASTRUCTNODENEXTNODE,LSTRINGINTSTRINDEXLSTRINGS,INTPOS,LSTRINGT/从串S的POS序号起，串T第一次出现的位置/NODEP,Q,PPOSINTI0，,J0IFTNEXTNULL|SNEXTNULLRETURN0PSNEXTQTNEXTWHILEPNULLJIFJPOSRETURN0WHILEPNULL/PPOS指向当前匹配的起始字符/IFPDATAQDATAPPNEXTQQNEXTELSE/从PPOS指向字符的下一个字符起从新匹配/PPPOSNEXTQTHEADNEXTIIFQNULLRETURNPOSI/匹配成功/ELSERETURN0/失败/第五章数组和广义表参考题实习题习题1假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，计算（1）数组A共占用多少字节；（288）（2）数组A的最后一个元素的地址；（1282）（3）按行存储时，元素A36的地址；（1126）（4）按列存储时，元素A36的地址；（1192）注意本章自定义数组的下标从1开始。2设有三对角矩阵（AIJ）NN,将其三条对角线上的元素逐行地存于数组B13N2中，使得BKAIJ，求（1）用I,J表示K的下标变换公式；（2）用K表示I,J的下标变换公式。IK/31,JK3I1K3K/3或IK/31,JK2K/32假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。提示参考P28例、P47例。4在稀疏矩阵的快速转置算法52中，将计算POSITIONCOL的方法稍加改动，使算法只占用一个辅助向量空间。提示（1）POSITIONK中为第K列非零元素个数，K1,2,N（2）POSITION01（第1列中第一个非零元素的正确位置）（3）POSITIONKPOSITIONK1POSITIONK,K1,2,N（4）POSITIONKPOSITIONK1,KN,N1,15写一个在十字链表中删除非零元素AIJ的算法。提示“删除”两次，释放一次。6画出下面广义表的两种存储结构图示A,B,D,E,F第一种存储结构（自底向上看）111110F0E0A11111110B0D7求下列广义表运算的结果（1）HEADA,B,C,D（2）TAILA,B,C,D（3）TAILHEADA,B,C,D（4）HEADTAILHEADA,B,C,DB（5）TAILHEADTAILA,B,C,DD参考题8试设计一个算法，将数组A（0N1）中的元素循环右移K位，并要求只用一个元素大小的附加存储，元素移动或交换次数为ON。9假设按低下标优先（以最左的下标为主序）存储整数数组A（18,12,14,17）时，第一个元素的字节地址是100，每个整数占4个字节，问元素A4,2,3,5的存储地址是什么10高下标优先（以最右的下标为主序）存储整数数组A（18,12,14,17）时，顺序列出数组A的所有元素。11试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。实习题1若矩阵AMN中的某个元素AIJ是第I行中的最小值，同时又是第J列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。第五章答案52设有三对角矩阵ANN,将其三条对角线上的元素逐行的存于数组B13N2中，使得BKAIJ，求（1）用I,J表示K的下标变换公式；（2）用K表示I、J的下标变换公式。【解答】（1）K2I1J2IK/31,JK/3K3（取整，取余）54在稀疏矩阵的快速转置算法52中，将计算POSITIONCOL的方法稍加改动，使算法只占用一个辅助向量空间。【解答】算法（一）FASTTRANSPOSETSMATRIXTSMARTRIXA,TSMATRIXB/把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示/INTCOL,T,P,QINTPOSITIONMAXSIZEBLENALENBNAMBMANIFBLEN0POSITION11FORT1TDATAQROWADATAPCOLBDATAQCOLADATAPROWBDATAQEADATAPEPOSITIONCOL算法二FASTTRANSPOSETSMATRIXTSMARTRIXA,TSMATRIXBINTCOL,T,P,QINTPOSITIONMAXSIZEBLENALENBNAMBMANIFBLEN0FORCOL1COL0COLTTPOSITIONCOLPOSITIONCOLT1FORP1PDATAQROWADATAPCOLBDATAQCOLADATAPROWBDATAQEADATAPEPOSITIONCOL56画出下面广义表的两种存储结构图示A,B,D,E,F【解答】第一种存储结构第二种存储结构57求下列广义表运算的结果（6）HEADA,B,C,DA,B（7）TAILA,B,C,DC,D（8）TAILHEADA,B,C,DB（9）HEADTAILHEADA,B,C,DB（10）TAILHEADTAILA,B,C,DD第六章实习题习题1试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。3已知一棵度为K的树中有N1个度为1的结点，N2个度为2的结点，NK个度为K的结点，则该树中有多少个叶子结点提示参考P116性质3NN0N1NKBN12N23N3KNKNB1N0N1NKN12N23N3KNK1N0N22N3K1NK14假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。提示参考P1486已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个提示方法1（1）一个叶子结点，总结点数至多有多少个结论可压缩一度结点。（2）满二叉树或完全二叉树具有最少的一度结点（3）可能的最大满二叉树是几层有多少叶结点如何增补25DATAXFREETREEBTBTNULLELSEDELTREEBT,XVOIDDELTREEBITREEBT,DATATYPEXIFBTIFBTLCHILDBTLCHILDNULLIFBTRCHILDBTRCHILDNULLDELTREEBTLCHILD,XDELTREEBTRCHILD,X方法2（1）先序查找；（2）直接查看当前根结点（3）用指针参数；方法3（1）先序查找；（2）直接查看当前根结点（3）通过函数值，返回删除后结果；（参示例程序）14分别写函数完成在先序线索二叉树T中，查找给定结点P在先序序列中的后继。在后序线索二叉树T中，查找给定结点P在后序序列中的前驱。提示（1）先查看线索，无线索时用下面规律（2）结点P在先序序列中的后继为其左子或右子；（3）结点P在后序序列中的前驱也是其左子或右子。15分别写出算法，实现在中序线索二叉树中查找给定结点P在中序序列中的前驱与后继。（参例题）16编写算法，对一棵以孩子兄弟链表表示的树统计其叶子的个数。提示（1）可将孩子兄弟链表划分为根、首子树、兄弟树，递归处理。（2）可利用返回值，或全局变量。17对以孩子兄弟链表表示的树编写计算树的深度的算法。18已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。（参课本）19设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指在二叉树中不存在子树个数为1的结点。提示可利用任何递归、非递归遍历算法。20计算二叉树最大宽度的算法。二叉树的最大宽度是指二叉树所有层中结点个数的最大值。21已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。22证明给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；23二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。实习题1问题描述建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。基本要求从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。测试数据ABCDEGF（其中表示空格字符）输出结果为先序ABCDEGF中序CBEGDFA后序CGBFDBA2已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。提示（1）参习题620，实现逐层遍历（2）队中保存每个结点的打印位置，其左、右子的距离3如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如图634所示。ABCDE图6344按凹入表形式打印树形结构，如图635所示。提示参P129例，用先根遍历。AABDCGFEABEFCGDCFEADBFBCDEFG图635第六章答案61分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。【解答】具有3个结点的树具有3个结点的二叉树63已知一棵度为K的树中有N1个度为1的结点，N2个度为2的结点，NK个度为K的结点，则该树中有多少个叶子结点【解答】设树中结点总数为N,则NN0N1NK树中分支数目为B,则BN12N23N3KNK因为除根结点外，每个结点均对应一个进入它的分支，所以有NB1即N0N1NKN12N23N3KNK1由上式可得叶子结点数为N0N22N3K1NK165已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个【解答】N0表示叶子结点数，N2表示度为2的结点数，则N0N21所以N2N0149，当二叉树中没有度为1的结点时，总结点数NN0N29966试分别找出满足以下条件的所有二叉树1前序序列与中序序列相同2中序序列与后序序列相同3前序序列与后序序列相同。【解答】1前序与中序相同空树或缺左子树的单支树；2中序与后序相同空树或缺右子树的单支树；3前序与后序相同空树或只有根结点的二叉树。69假设通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为007，019，002，006，032，003，021，010请为这8个字母设计哈夫曼编码。【解答】构造哈夫曼树如下哈夫曼编码为I111111I51100I211110I610I31110I701I41101I800611画出如下图所示树对应的二叉树。【解答】615分别写出算法，实现在中序线索二叉树T中查找给定结点P在中序序列中的前驱与后继。在先序线索二叉树T中，查找给定结点P在先序序列中的后继。在后序线索二叉树T中，查找给定结点P在后序序列中的前驱。（1）找结点的中序前驱结点BITNODEINPREBITNODEP/在中序线索二叉树中查找P的中序前驱结点，并用PRE指针返回结果/IFPLTAG1PREPLCHILD/直接利用线索/ELSE/在P的左子树中查找“最右下端”结点/FORQPLCHILDQRTAG0QQRCHILDPREQRETURNPRE（2）找结点的中序后继结点BITNODEINSUCCBITNODEP/在中序线索二叉树中查找P的中序后继结点，并用SUCC指针返回结果/IFPRTAG1SUCCPRCHILD/直接利用线索/ELSE/在P的右子树中查找“最左下端”结点/FORQPRCHILDQLTAG0QQLCHILDSUCCQRETURNSUCC3找结点的先序后继结点BITNODEPRESUCCBITNODEP/在先序线索二叉树中查找P的先序后继结点，并用SUCC指针返回结果/IFPLTAG0SUCCPLCHILDELSESUCCPRCHILDRETURNSUCC4找结点的后序前驱结点BITNODESUCCPREBITNODEP/在后序线索二叉树中查找P的后序前驱结点，并用PRE指针返回结果/IFPLTAG1PREPLCHILDELSEPREPRCHILDRETURNPRE621已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。【解答】VOIDPREORDERBITREEROOT/先序遍历二叉树的非递归算法/INITSTACKPROOTWHILEPNULL|ISEMPTYSIFPNULLVISITPDATAPUSHPPLCHILDELSEPOPPPRCHILD624已知二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。【解答】算法一VOIDEXCHANGEBITREEROOTPROOTIFPLCHILDNULL|PRCHILDNULLTEMPPLCHILDPLCHILDPRCHILDPRCHILDTEMPEXCHANGEPLCHILDEXCHANGEPRCHILD算法二VOIDEXCHANGEBITREEROOTPROOTIFPLCHILDNULL|PRCHILDNULLEXCHANGEPLCHILDEXCHANGEPRCHILDTEMPPLCHILDPLCHILDPRCHILDPRCHILDTEMP第七章补充题参考题实习题习题71已知如图所示的有向图，请给出该图的（1）每个顶点的入度、出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）十字链表；（6）强连通分量。156243题1图72已知如图所示的无向图，请给出该图的（1）邻接多重表；（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。）（2）从顶点1开始，深度优先遍历该图所得顶点序列和边的序列；（给出深度优先搜索树）（3）从顶点1开始，广度优先遍历该图所得顶点序列和边的序列。（给出广度优先搜索树）737475已知如图731所示的AOE网，试求（1）每个事件的最早发生时间和最晚发生时间；（2）每个活动的最早开始时间和最晚开始时间；（3）给出关键路径。76777879710已知如图730所示的有向网，试利用DIJKSTRA算法求顶021435768944354336614522图731题73用图142536题2图点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。757677编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。参例题78试在邻接矩阵存储结构上实现图的基本操作INSERTVERTEXG,VINSERTARCG,V,WDELETEVERTEXG,V和DELETEARCG,V,W。79试对邻接表存储结构重做题6。710试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点VI到顶点VJ的路径（IJ）。注意算法中涉及的图的基本操作必须在此存储结构上实现。711同上题要求。试基于图的广度优先搜索策略写一算法。712试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法。算法中不规定具体的存储结构，而将图GRAPH看成是一种抽象数据类型。713采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为K的简单路径（指顶点序列中不含有重现的顶点）的算法。提示利用深度搜索，增设一个深度参数，深度超过K则停止对该结点的搜索。714下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（A），广度遍历图G所得结点序列为（B）；G的一个拓扑序列是（C）；从图730题74用图654321101521043020152010结点V1到结点V8的最短路径为（D）；从结点V1到结点V8的关键路径为（E）。其中A、B、C的选择有V1,V2,V3,V4,V5,V6,V7,V8V1,V2,V4,V6,V5,V3,V7,V8V1,V2,V4,V6,V3,V5,V7,V8V1,V2,V4,V6,V7,V3,V5,V8V1,V2,V3,V8,V4,V5,V6,V7V1,V2,V3,V8,V4,V5,V7,V6V1,V2,V3,V8,V5,V7,V4,V6D、E的选择有V1,V2,V4,V5,V3,V8V1,V6,V5,V3,V8V1,V6,V7,V8V1,V2,V5,V7,V8713二叉树的层次遍历。_TOP实习题1分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。16V1V2V5V3V40123431550243463117841223862441V6V7V8567612720题12图2校园导游程序。用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求实现以下功能（1）查询各景点的相关信息；（2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。3编程求解关键路径问题。_TOP补充题1将图731所示的有向网改为无向网，并要求（1）用普里姆算法从顶点9开始，手工构造最小生成树。（最小代价连通网）（2）用克鲁斯卡尔算法手工构造最小生成树。（注可将结点看成电脑，将权值看成电缆代价；也可将结点看成城市，将权值看成电缆代价；还可将结点看成城市，将权值看成修路代价；）2将图731所示的AOE网改为AOV网（去掉权值即可），并给出一个拓扑序列。（要求优先输出编号小的顶点）。_TOP021435768944354336614522图731题73用图参考题1已知有向图，试基于图的深度优先搜索策略写一算法，求顶点VI到顶点VJ的一条简单路径（IJ）。提示有向图可用邻接表存储，并在表结点中增加一个PRIOR域。第七章答案71已知如图所示的有向图，请给出该图的（1）每个顶点的入度、出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）十字链表；（6）强连通分量。【解答】（1）顶点入度出度130222312413521623（3）邻接矩阵156243题1图（3）邻接表（4）逆邻接表（5）十字链表（6）强连通分量72已知如图所示的无向图，请给出该图的（2）深度优先遍历该图所得顶点序列和边的序列；（3）广度优先遍历该图所得顶点序列和边的序列。【解答】（2）深度优先搜索顶点序列123456边的序列（1，2）（2，3）（3，4）（4，5）（5，6）深度优先搜索树（2）广度优先搜索顶点序列123654边的序列（1，2）（1，3）（1，6）（1，5）（5，4）深度优先搜索树注本题中所求深度优先序列和广度优先序列有多种，以上为其中一种。73【解答】源点终点最短路径路径长度121，3，21931，31541，3，2，42951，3，52961，3，2，4，644712【解答】1深度遍历1，2，3，8，4，5，7，6或1，2，3，8，5，7，4，2广度遍历1，2，4，6，3，5，7，83拓扑序列1，2，4，6，5，3，7，84最短路径1，2，5，7，85关键路径1，6，5，3，8713【解答】按层遍历二叉树LAYERORDERBITREEROOTLINKQUEUEQINITQUEUEIFROOTNULLRETURNENTERQUEUEWHILEEMPTYVISITEPDATAIFPLCHILDNULLENTERQUEUEIFPRCHILDNULLENTERQUEUE第八章实习题习题81若对大小均为N的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同（1）查找不成功，即表中没有关键字等于给定值K的记录。（2）查找成功，且表中只有一个关键字等于给定值K的记录。（3）查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。提示均用顺序查找法。82画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。提示根据P191ASL定义计算平均查找长度。83试推导含12个结点的平衡二叉树的最大深度并画出一棵这样的树。提示沿最左分支生长，前提是其任一祖先的右分支与左分支等深，如不等深，则先生长右分支，而生长右分支的前提是其任一祖先的左分支与右分支等深，如不等深，则先生长左分支，如此交互考虑，逐步生长，直到12个结点。84试从空树开始，画出按以下次序向23树，即3阶B树中插入关键码的建树过程20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后23树的状态。85选取哈希函数HK3K11，用线性探测再散列法处理冲突。试在010的散列地址空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。提示平均查找长度参考P225。012345678910224130015346136711221126ASLSUCC14236/82ASLUNSUCC21876543211/1140/1186试为下列关键字建立一个装载因子不小于075的哈希表，并计算你所构造的哈希表的平均查找长度。（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN）提示（1）由装填因子求出表长，（2）可利用字母序号设计哈希函数，（3）确定解决冲突的方法。87试编写利用折半查找确定记录所在块的分块查找算法。88试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。提示检验中序遍历序列是否递增有序方法1用非递归中序遍历算法，设双指针PRE,P一旦PREDATAPDATA则返回假方法2用递归中序遍历算法，设全局指针PRE，（参中序线索化算法）一旦PREDATAPDATA则返回假方法3用递归（中序或后序）算法（1）空树是（2）单根树是（3）左递归真（4）右递归真（5）左子树的右端小于根（6）右子树的左端大于根89编写算法，求出指定结点在给定的二叉排序树中所在的层数。810编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结点A、B中，A是B的祖先，则认为A是A、B的最近公共祖先）。提示（1）假设AAI1,则将两者交换；第一趟对所有奇数I,第二趟对所有偶数I，,依次类推直至整个序列有序为止。（1）这种排序方法的结束条件是什么（2）分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。（3）写出奇偶交换排序的算法。912设计一个用链表表示的直接选择排序算法。（与98重）913插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。（与95重复）914一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。（与97类似）915为什么通常使用一维数组作为堆的存放形式916已知（K1,K2,，KN）是堆，写一个算法将（K1,K2,，KN，KN1）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。917试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、稳定性和适用情况。918在供选择的答案中填入正确答案1）、排序（分类）的方法有许多种_A_法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；_B_法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。_C_和_D_是基于这类方法的两种排序方法，而_D_是比_C_效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是_E_。供选择答案选择排序快速排序插入排序冒泡排序归并排序二分排序哈希排序基数排序2）、一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为C。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，793）、下列排序算法中，C算法可能会出现下面情况初始数据有序时，花费时间反而最多。A、堆排序B、冒泡排序C、快速排序D、SHELL排序919判断正误（）在一个大堆中，最小元素不一定在最后。（X）对N个记录采用快速排序方法进行排序，最坏情况下所需时间是O（NLOG2N）。（X）在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。实习题一、随机生成30个数，试比较直接插入排序、简单选择排序、起泡排序、快速排序、堆排序和希尔排序的时空性能和稳定性。二、统计成绩。给出N个学生的考试成绩表，每条信息由姓名与分数组成。三、按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；四、按名次列出每个学生的姓名与分数。911无序表顺序查找不成功时，查找长度为N1；成功时，平均查找长度为1/N112N1N2/2；两者不相同。（2）表中只有一个关键字等于给定值K的记录，无序表、有序表顺序查找成功时，平均查找长度均为1/N12NN1/2；两者相同。（3）表中只有M个关键字等于给定值K的记录，无序表ASLN1；有序表ASL（N1）/2M；两者不相同。93ASL1/10（1224334）2991191465283197410删除50后删除68后9192267413053461301012345678910ASL（412236）/817/8925INTSEARCHSEQSSTABLEST