数据结构题集答案C语言版严蔚敏吴伟民著

第1章绪论11简述下列术语数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。12试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。13设有数据结构D,R，其中，4,32,1DDRR4,3,2,1DD试按图论中图的画法惯例画出其逻辑结构图。解14试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。解ADTCOMPLEX数据对象DR,I|R,I为实数数据关系R基本操作INITCOMPLEXI1WHILEIJJELSEI7XNY0/N是不小于1的常数WHILEXY1Y1Y8X91Y100WHILEY0IFX100X10YELSEX解1N12N13N14NN1N2121N5112123123NNI12NINININI1121212346N7向下取整8110019假设N为2的乘幂，并且N2，试求下列算法的时间复杂度及变量COUNT的值（以N的函数形式表示）。INTTIMEINTNCOUNT0X2WHILEX438时，NN22LOG50114判断下列各对函数和，当时，哪个函数增长更快F1，31L2NF742，5N52G3，412FNNL4，23N52解1GN快2GN快3FN快4FN快115试用数学归纳法证明16/1212NIN0N2/10XXNNI,1X321NNI421NI1116试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值解INTMAX3INTX,INTY,INTZIFXYIFXZRETURNXELSERETURNZELSEIFYZRETURNYELSERETURNZ117已知K阶斐波那契序列的定义为，；0F1F02KF1KF，NNN2,试编写求K阶斐波那契序列的第M项值的函数算法，K和M均以值调用的形式在函数参数表中出现。解K0为阶数，N为数列的第N项INTFIBONACCIINTK,INTNIFKARRSIZE或对某个，使时，应按出错处理。注意选择你认为较NK1INTMAXK好的出错处理方法。解INCLUDEINCLUDEDEFINEMAXINT65535DEFINEARRSIZE100INTFUNINTIINTMAININTI,KINTAARRSIZECOUTKIFKARRSIZE1EXIT0FORI0IMAXINTEXIT0ELSEAI2IAI1FORI0IMAXINTEXIT0ELSECOUTINCLUDEDEFINEN10DOUBLEPOLYNOMAILINTA,INTI,DOUBLEX,INTNINTMAINDOUBLEXINTN,IINTANCOUTXCOUTNIFNN1EXIT0COUTAICOUT0RETURNANIPOLYNOMAILA,I1,X,NXELSERETURNAN本算法的时间复杂度为ON。第2章线性表21描述以下三个概念的区别头指针，头结点，首元结点（第一个元素结点）。解头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。22填空题。解1在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。2顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。3在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。4在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。23在什么情况下用顺序表比链表好解当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。24对以下单链表分别执行下列各程序段，并画出结果示意图。解25画出执行下列各行语句后各指针及链表的示意图。LLINKLISTMALLOCSIZEOFLNODEPLFORI1INEXTLINKLISTMALLOCSIZEOFLNODEPPNEXTPDATAI21PNEXTNULLFORI4I1IINS_LINKLISTL,I1,I2FORI1INEXTS2PNEXTPNEXTNEXT3PNEXTSNEXT4SNEXTPNEXT5SNEXTL6SNEXTNULL7QP8WHILEPNEXTQPPNEXT9WHILEPNEXTNULLPPNEXT10PQ11PL12LS13LP解A41B711841C512D91627已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。A删除P结点的直接后继结点的语句序列是_。B删除P结点的直接前驱结点的语句序列是_。C删除P结点的语句序列是_。D删除首元结点的语句序列是_。E删除尾元结点的语句序列是_。1PPNEXT2PNEXTP3PNEXTPNEXTNEXT4PPNEXTNEXT5WHILEPNULLPPNEXT6WHILEQNEXTNULLPQQQNEXT7WHILEPNEXTQPPNEXT8WHILEPNEXTNEXTQPPNEXT9WHILEPNEXTNEXTNULLPPNEXT10QP11QPNEXT12PL13LLNEXT14FREEQ解A11314B10128314C10127314D1211314E91131428已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。A在P结点后插入S结点的语句序列是_。B在P结点前插入S结点的语句序列是_。C删除P结点的直接后继结点的语句序列是_。D删除P结点的直接前驱结点的语句序列是_。E删除P结点的语句序列是_。1PNEXTPNEXTNEXT2PPRIOUPPRIOUPRIOU3PNEXTS4PPRIOUS5SNEXTP6SPRIOUP7SNEXTPNEXT8SPRIOUPPRIOU9PPRIOUNEXTPNEXT10PPRIOUNEXTP11PNEXTPRIOUP12PNEXTPRIOUS13PPRIOUNEXTS14PNEXTPRIOUPPRIOU15QPNEXT16QPPRIOU17FREEP18FREEQ解A73612B84513C1511118D1621018E1491729简述以下算法的功能。1STATUSALINKEDLISTL/L是无表头结点的单链表IFLLLNEXTPLWHILEPNEXTPPNEXTPNEXTQQNEXTNULLRETURNOK2VOIDBBLNODES,LNODEQPSWHILEPNEXTQPPNEXTPNEXTSVOIDAALNODEPA,LNODEPB/PA和PB分别指向单循环链表中的两个结点BBPA,PBBBPB,PA解1如果L的长度不小于2，将L的首元结点变成尾元结点。2将单循环链表拆成两个单循环链表。210指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。STATUSDELETEKSQLIST/参数不合法ELSEFORCOUNT1COUNTI1JAELEMJIAELEMJALENGTHRETURNOK解STATUSDELETEKSQLISTIFIALENGTH1|KALENGTHIRETURNINFEASIBLEFORJ0J0,XBLENGTHALENGTHBLENGTHFORI0IBELEMIJ1IFAELEMIKJ1IFBLENGTHKJ1IFALENGTHBLENGTHJ0RETURNJ213试写一算法在带头结点的单链表结构上实现线性表操作LOCATEL,X解INTLOCATEELEM_LLINKLISTLINKLISTPLWHILEPIIFPRETURN0ELSERETURNI214试写一算法在带头结点的单链表结构上实现线性表操作LENGTHL。解/返回单链表的长度INTLISTLENGTH_LLINKLISTLINKLISTPLIFPPPNEXTWHILEPPPNEXTIRETURNI215已知指针HA和HB分别指向两个单链表的头结点，并且已知两个链表的长度分别为M和N。试写一算法将这两个链表连接在一起，假设指针HC指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。解VOIDMERGELIST_LLINKLISTPAHAPBHBWHILEPANEXTPBPBNEXTIFPANEXTHCHBWHILEPBNEXTPBPBNEXTPBNEXTHANEXTELSEHCHAWHILEPANEXTPAPANEXTPANEXTHBNEXT216已知指针LA和LB分别指向两个无头结点单链表中的首元结点。下列算法是从表LA中删除自第I个元素起共LEN个元素后，将它们插入到表LB中第I个元素之前。试问此算法是否正确若有错，请改正之。STATUSDELETEANDINSERTSUBLINKEDLISTLA,LINKEDLISTLB,INTI,INTJ,INTLENIFINEXTKQPWHILEKNEXTKSLBK1WHILEKNEXTKSNEXTPQNEXTSNEXTRETURNOK解STATUSDELETEANDINSERTSUBLINKLISTINTK1IFINEXTKIFPRETURNINFEASIBLE/在LA表中查找第ILEN1个结点QPK1WHILEQKIFQRETURNINFEASIBLE/完成删除，注意，I1的情况需要特殊处理IFPREVLAQNEXTELSEPREVNEXTQNEXT/将从LA中删除的结点插入到LB中IFJ1QNEXTLBLBPELSESLBK1WHILESKIFSRETURNINFEASIBLEQNEXTSNEXTSNEXTP/完成插入RETURNOK217试写一算法，在无头结点的动态单链表上实现线性表操作INSERTL,I,B，并和在带头结点的动态单链表上实现相同操作的算法进行比较。218试写一算法，实现线性表操作DELETEL,I，并和在带头结点的动态单链表上实现相同操作的算法进行比较。219已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于MINK且小于MAXK的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，MINK和MAXK是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。解STATUSLISTDELETE_LLINKLISTIFMINKMAXKRETURNERRORPLPREVPPPNEXTWHILEPELSEPREVNEXTPNEXTQPPPNEXTFREEQRETURNOK220同219题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。解VOIDLISTDELETE_LSAMENODELINKLISTPLPREVPPPNEXTWHILEPPREVPPPNEXTIFPQPPPNEXTFREEQ221试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表逆置为。NA,11,AN解/顺序表的逆置STATUSLISTOPPOSE_SQSQLISTELEMTYPEXFORI0INEXTLNEXTNULLWHILEPQPPPNEXTQNEXTLNEXTLNEXTQRETURNOK223设线性表，试写一个按下列规则合并MAA,21NBB,21A，B为线性表C的算法，即使得当时；NBB,11当时。MNAA线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意单链表的长度值M和N均未显式存储。解/将合并后的结果放在C表中，并删除B表STATUSLISTMERGE_LLINKLISTPAANEXTPBBNEXTCAWHILEPAQBPBPAPANEXTPBPBNEXTQBNEXTQANEXTQANEXTQBIFPAQBNEXTPBPBBFREEPBRETURNOK224假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。解/将合并逆置后的结果放在C表中，并删除B表STATUSLISTMERGEOPPOSE_LLINKLISTPAAPBBQAPA/保存PA的前驱指针QBPB/保存PB的前驱指针PAPANEXTPBPBNEXTANEXTNULLCAWHILEPAPAPANEXTQANEXTANEXT/将当前最小结点插入A表表头ANEXTQAELSEQBPBPBPBNEXTQBNEXTANEXT/将当前最小结点插入A表表头ANEXTQBWHILEPAQAPAPAPANEXTQANEXTANEXTANEXTQAWHILEPBQBPBPBPBNEXTQBNEXTANEXTANEXTQBPBBFREEPBRETURNOK225假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。解/将A、B求交后的结果放在C表中STATUSLISTCROSS_SQSQLISTWHILEIBELEMJJELSELISTINSERT_SQC,K,AELEMIIKRETURNOK226要求同225题。试对单链表编写求C的算法。解/将A、B求交后的结果放在C表中，并删除B表STATUSLISTCROSS_LLINKLISTPAAPBBQAPA/保存PA的前驱指针QBPB/保存PB的前驱指针PAPANEXTPBPBNEXTCAWHILEPAPAPANEXTQANEXTPAFREEPTELSEIFPADATAPBDATAPTPBPBPBNEXTQBNEXTPBFREEPTELSEQAPAPAPANEXTWHILEPAPTPAPAPANEXTQANEXTPAFREEPTWHILEPBPTPBPBPBNEXTQBNEXTPBFREEPTPBBFREEPBRETURNOK227对225题的条件作以下两点修改，对顺序表重新编写求得表C的算法。1假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；2利用A表空间存放表C。解1/A、B求交，然后删除相同元素，将结果放在C表中STATUSLISTCROSSDELSAME_SQSQLISTWHILEIBELEMJJELSEIFCLENGTH0LISTINSERT_SQC,K,AELEMIKELSEIFCELEMCLENGTH1AELEMILISTINSERT_SQC,K,AELEMIKIRETURNOK2/A、B求交，然后删除相同元素，将结果放在A表中STATUSLISTCROSSDELSAME_SQSQLISTWHILEIBELEMJJELSEIFK0AELEMKAELEMIKELSEIFAELEMKAELEMIAELEMKAELEMIKIALENGTHKRETURNOK228对225题的条件作以下两点修改，对单链表重新编写求得表C的算法。1假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；2利用原表（A表或B表）中的结点构成表C，并释放A表中的无用结点空间。解1/A、B求交，结果放在C表中，并删除相同元素STATUSLISTCROSSDELSAME_LLINKLISTPAAPBBQAPA/保存PA的前驱指针QBPB/保存PB的前驱指针PAPANEXTPBPBNEXTCAWHILEPAPAPANEXTQANEXTPAFREEPTELSEIFPADATAPBDATAPTPBPBPBNEXTQBNEXTPBFREEPTELSEIFPADATAQADATAPTPAPAPANEXTQANEXTPAFREEPTELSEQAPAPAPANEXTWHILEPAPTPAPAPANEXTQANEXTPAFREEPTWHILEPBPTPBPBPBNEXTQBNEXTPBFREEPTPBBFREEPBRETURNOK2/A、B求交，结果放在A表中，并删除相同元素STATUSLISTCROSSDELSAME_LLINKLISTPAAPBBQAPA/保存PA的前驱指针QBPB/保存PB的前驱指针PAPANEXTPBPBNEXTWHILEPAPAPANEXTQANEXTPAFREEPTELSEIFPADATAPBDATAPTPBPBPBNEXTQBNEXTPBFREEPTELSEIFPADATAQADATAPTPAPAPANEXTQANEXTPAFREEPTELSEQAPAPAPANEXTWHILEPAPTPAPAPANEXTQANEXTPAFREEPTWHILEPBPTPBPBPBNEXTQBNEXTPBFREEPTPBBFREEPBRETURNOK229已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意题中没有特别指明同一表中的元素值各不相同）。解/在A中删除既在B中出现又在C中出现的元素，结果放在D中STATUSLISTUNION_SQSQLISTINITLIST_SQTEMPLISTCROSS_LB,C,TEMPLISTMINUS_LA,TEMP,D230要求同229题。试对单链表编写算法，请释放A表中的无用结点空间。解/在A中删除既在B中出现又在C中出现的元素，并释放B、CSTATUSLISTUNION_LLINKLISTLISTMINUS_LA,B/求集合AB，结果放在A表中，并删除B表STATUSLISTMINUS_LLINKLISTPAAPBBQAPA/保存PA的前驱指针QBPB/保存PB的前驱指针PAPANEXTPBPBNEXTWHILEPAPBPBNEXTQBNEXTPBFREEPTELSEIFPBDATAPADATAQAPAPAPANEXTELSEPTPAPAPANEXTQANEXTPAFREEPTWHILEPBPTPBPBPBNEXTQBNEXTPBFREEPTPBBFREEPBRETURNOK231假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知S为指向链表中某个结点的指针，试编写算法在链表中删除指针S所指结点的前驱结点。解/在单循环链表S中删除S的前驱结点STATUSLISTDELETE_CLLINKLISTIFSSNEXTRETURNERRORQSPSNEXTWHILEPNEXTSQPPPNEXTQNEXTPNEXTFREEPRETURNOK232已知有一个单向循环链表，其每个结点中含三个域PRE，DATA和NEXT，其中DATA为数据域，NEXT为指向后继结点的指针域，PRE也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使PRE成为指向前驱结点的指针域。解/建立一个空的循环链表STATUSINITLIST_DLDULINKLISTIFLEXITOVERFLOWLPRENULLLNEXTLRETURNOK/向循环链表中插入一个结点STATUSLISTINSERT_DLDULINKLISTPDULINKLISTMALLOCSIZEOFDULNODEIFPRETURNERRORPDATAEPNEXTLNEXTLNEXTPRETURNOK/将单循环链表改成双向链表STATUSLISTCIRTODUDULINKLISTQLPLNEXTWHILEPLPPREQQPPPNEXTIFPLPPREQRETURNOK233已知由一个线性链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。解/将单链表L划分成3个单循环链表STATUSLISTDIVIDEINTO3CLLINKLISTPLNEXTPT1S1PT2S2PT3S3WHILEPIFPDATA0QNEXTPT1NEXTPT1NEXTQPT1PT1NEXTELSEIFPDATAAQNEXTPT2NEXTPT2NEXTQPT2PT2NEXTELSEQPPPNEXTQNEXTPT3NEXTPT3NEXTQPT3PT3NEXTQLFREEQRETURNOK在234至236题中，“异或指针双向链表”类型XORLINKEDLIST和指针异或函数XORP定义为TYPEDEFSTRUCTXORNODECHARDATASTRUCTXORNODELRPTRXORNODE,XORPOINTERTYPEDESTRUCT/无头结点的异或指针双向链表XORPOINTERLEFT,RIGHT/分别指向链表的左侧和右端XORLINKEDLISTXORPOINTERXORPXORPOINTERP,XORPOINTERQ/指针异或函数XORP返回指针P和Q的异或值234假设在算法描述语言中引入指针的二元运算“异或”，若A和B为指针，则AB的运算结果仍为原指针类型，且AABAABBABBABBA则可利用一个指针域来实现双向链表L。链表L中的每个结点只含两个域DATA域和LRPTR域，其中LRPTR域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或。若设指针LLEFT指向链表中的最左结点，LRIGHT指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。解STATUSTRAVERSINGLINKLISTXORLINKEDLISTIFDL|DLPLLEFTLEFTNULLWHILEPNULLVISITINGDATAPDATALEFTPPXORPLEFT,PLRPTRELSEIFDR|DRPLRIGHTRIGHTNULLWHILEPNULLVISITINGDATAPDATARIGHTPPXORPPLRPTR,RIGHTELSERETURNERRORRETURNOK235采用234题所述的存储结构，写出在第I个结点之前插入一个结点的算法。236采用234题所述的存储结构，写出删除第I个结点的算法。237设以带头结点的双向循环链表表示的线性表。试写一时间NAL,21复杂度ON的算法，将L改造为。431,AN解/将双向链表LA1,A2,AN改造为A1,A3,AN,A2STATUSLISTCHANGE_DULDULINKLISTDULINKLISTP,Q,RPLNEXTRLPREI1WHILEPRIFI20QPPPNEXT/删除结点QPRENEXTQNEXTQNEXTPREQPRE/插入到头结点的左面QPRERNEXTPRERNEXTPREQQNEXTRNEXTRNEXTQELSEPPNEXTIRETURNOK238设有一个双向循环链表，每个结点中除有PRE，DATA和NEXT三个域外，还增设了一个访问频度域FREQ。在链表被起用之前，频度域FREQ的值均初始化为零，而每当对链表进行一次LOCATEL,X的操作后，被访问的结点（即元素值等于X的结点）中的频度域FREQ的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的算法。解DULINKLISTLISTLOCATE_DULDULINKLISTPLNEXTWHILEPLIFPLRETURNNULLELSEPFREQ/删除结点PPRENEXTPNEXTPNEXTPREPPRE/插入到合适的位置QLNEXTWHILEQLIFQLPNEXTQNEXTQNEXTPPPREQPREQPREPELSE/在Q之前插入PNEXTQPRENEXTQPRENEXTPPPREQPREQPREPRETURNP在239至240题中，稀疏多项式采用的顺序存储结构SQPOLY定义为TYPEDEFSTRUCTINTCOEFINTEXPPOLYTERMTYPEDEFSTRUCT/多项式的顺序存储结构POLYTERMDATAINTLASTSQPOLY239已知稀疏多项式，其中MEEENXCXCXP21，。试采用存储量同多项式项011EENMMICI,21数M成正比的顺序存储结构，编写求的算法（为给定值），并分析你的0XN0X算法的时间复杂度。解TYPEDEFSTRUCTINTCOEFINTEXPPOLYTERMTYPEDEFSTRUCTPOLYTERMDATAINTLASTSQPOLY/建立一个多项式STATUSPOLYINITSQPOLYPOLYTERMPCOUTLLASTLDATAPOLYTERMMALLOCLLASTSIZEOFPOLYTERMIFLDATARETURNERRORPLDATAFORI0IPCOEFCOUTPEXPPRETURNOK/求多项式的值DOUBLEPOLYSUMSQPOLYINTI,JPOLYTERMPPLDATAFORI0,PN0IEXPJXXX0PNPNPCOEFXRETURNPN240采用239题给定的条件和存储结构，编写求的算法，XPXNN21将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。解/求两多项式的差STATUSPOLYMINUSSQPOLYPLDATAP1L1DATAP2L2DATAINTI0,J0,K0WHILEIEXPEXPPCOEFP1COEFPEXPP1EXPPKP1IELSEIFP1EXPP2EXPPCOEFP2COEFPEXPP2EXPPKP2JELSEIFP1COEFP2COEFPCOEFP1COEFP2COEFPEXPP1EXPPKP1P2IJIFICOEFP1COEFPEXPP1EXPPKP1IIFJCOEFP2COEFPEXPP2EXPPKP2JLLASTKRETURNOK在241至242题中，稀疏多项式采用的循环链表存储结构LINKEDPOLY定义为TYPEDEFSTRUCTPOLYNODEPOLYTERMDATASTRUCTPOLYNODENEXTPOLYNODE,POLYLINKTYPEDEFPOLYLINKLINKEDPOLY241试以循环链表作稀疏多项式的存储结构，编写求其导函数的方法，要求利用原多项式中的结点空间存放其导函数多项式，同时释放所有无用结点。解STATUSPOLYDIFFERENTIALLINKEDPOLYQLPLNEXTWHILEPLIFPDATAEXP0PTPPPNEXTQNEXTPFREEPTELSEPDATACOEFPDATACOEFPDATAEXPPDATAEXPQPPPNEXTRETURNOK242试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。解/将单链表L划分成2个单循环链表STATUSLISTDIVIDEINTO2CLLINKEDPOLYQLPLNEXTP1L1WHILEPLIFPDATAEXP20PTPPPNEXTQNEXTPPTNEXTP1NEXTP1NEXTPTP1P1NEXTELSEQPPPNEXTRETURNOK第3章栈和队列31若按教科书311节中图31B所示铁道进行车厢调度（注意两侧铁道均为单向行驶道），则请回答1如果进站的车厢序列为123，则可能得到的出站车厢序列是什么2如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以S表示进栈和以X表示出栈的栈操作序列）。解11232313212131322可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。32简述栈和线性表的差别。解线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。33写出下列程序段的输出结果（栈的元素类型SELEMTYPE为CHAR）。VOIDMAINSTACKSCHARX,YINITSTACKSXCYKPUSHS,XPUSHS,APUSHS,YPOPS,XPUSHS,TPUSHS,XPOPS,XPUSHS,SWHILESTACKEMPTYSPOPS,YPRINTFYPRINTFX解STACK34简述以下算法的功能（栈的元素类型SELEMTYPE为INT）。1STATUSALGO1STACKSINTI,N,A255N0WHILESTACKEMPTYSNPOPS,ANFORI1I1COUT1COUTXIFX0SUM0ELSETESTSUMSUMXCOUTXPUSHS,XWHILEX0WHILESTACKEMPTYSPOPS,XSUMXCOUTPTOP0XELSECERRTOP0RETURNTOP1ELSECERRNEXTDELETEPSSIZEVOIDCLEARSTACKSTACKWHILESTOPPSTOPSTOPPNEXTDELETEPSSIZEINTSTACKLENGTHSTACKSRETURNSSIZESTATUSSTACKEMPTYSTACKSIFSSIZE0RETURNTRUEELSERETURNFALSESTATUSGETTOPSTACKS,ELEMTYPEELSEESTOPDATARETURNOKSTATUSPUSHSTACKPNEWNODETYPEIFPEXITOVERFLOWPNEXTSTOPSTOPPPDATAESSIZERETURNOKSTATUSPOPSTACKIFSTOPESTOPDATAPSTOPSTOPPNEXTDELETEPSSIZERETURNOK/从栈顶到栈底用VISIT函数遍历栈中每个数据元素VOIDSTACKTRAVERSESTACKS,STATUSVISITELEMTYPEELINKTYPEPPSTOPWHILEPVISITPDATA316假设如题31所属火车调度站的入口处有N节硬席或软席车厢（分别以H和S表示）等待调度，试编写算法，输出对这N节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。解INTMAINSTACKSCHARBUFFER80INTI0,J0INITSTACKSCOUTBUFFERCOUTINCLUDETYPEDEFSTRUCTINTXINTYPOSTYPETYPEDEFSTRUCTINTCOLORINTVISITEDPOSTYPESEATELEMTYPEINCLUDE“DVC99STACKH“DEFINEM8DEFINEN8ELEMTYPEGMNVOIDCREATEGDSELEMTYPEGMNVOIDSHOWGRAPHARRAYELEMTYPEGMNVOIDREGIONFILLINGELEMTYPEGMN,POSTYPECURPOS,INTNEWCOLORINTMAINCREATEGDSGSHOWGRAPHARRAYGPOSTYPESTARTPOSSTARTPOSX5STARTPOSY5INTFILLCOLOR6REGIONFILLINGG,STARTPOS,FILLCOLORCOUT0IFCURPOSY0VOIDCREATEGDSELEMTYPEGMNINTI,JFORI0IJRETURNTRUEELSERETURNFALSE322如题321的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。解CHARCALVAL_INVERPOLANDCHARBUFFERSTACKOPNDINITSTACKOPNDINTI0CHARCELEMTYPEE1,E2WHILEBUFFERIIFISOPERATORBUFFERIPUSHOPND,BUFFERIELSEPOPOPND,E2POPOPND,E1CCALE1,BUFFERI,E2PUSHOPND,CIRETURNCCHARCALCHARC1,CHAROP,CHARC2INTX,X1,X2CHARCH10CH0C1CH10X1ATOICHCH0C2CH10X2ATOICHSWITCHOPCASEXX1X2BREAKCASEXX1X2BREAKCASEXX1X2BREAKCASE/XX1/X2BREAKDEFAULTBREAKITOAX,CH,10RETURNCH0323如题321的假设条件，试写一个算法，判断给定的非空后缀表达式是否为正确的逆波兰表达式，如果是，则将它转化为波兰式。解INCLUDEINCLUDEINCLUDEINCLUDE“DVC99DSCONSTANTH“TYPEDEFCHARARRAY30TYPEDEFARRAYELEMTYPETYPEDEFSTRUCTNODETYPEELEMTYPEDATANODETYPENEXTNODETYPE,LINKTYPETYPEDEFSTRUCTLINKTYPETOPINTSIZESTACKVOIDINITSTACKSTACKSTATUSPUSHSTACKSTATUSPOPSTACKSTATUSISOPERATORCHARCSTATUSSTACKEMPTYSTACKSSTATUSINVTOFROPOLANDCHARAINTMAINCHARA30COUTAIFINVTOFROPOLANDACOUT0STOPPSTRCPYPDATA,ESSIZERETURNOKSTATUSPOPSTACKIFSTOPSTRCPYE,STOPDATAPSTOPSTOPPNEXTDELETEPSSIZERETURNOKSTATUSSTACKEMPTYSTACKSIFSSIZE0RETURNTRUEELSERETURNFALSESTATUSISOPERATORCHARCCHARP“/“WHILEPIFPCRETURNTRUEPRETURNFALSE324试编写如下定义的递归函数的递归算法，并根据算法画出求G5,2时栈的变化过程。0,2,10,NMNGNM解INTGINTM,INTNINTMAININTM,NCOUTMNIFN0COUT0RETURNGM1,2NNELSERETURN0假设主函数的返回地址为0，递归函数3条语句的地址分别为1、2、3。306431323216338344052325试写出求递归函数FN的递归算法，并消除递归21NFN解INCLUDEDEFINEN20INTMAININTIINTANINTNCOUTNFORI0IDOUBLESQRTDOUBLEA,DOUBLEP,DOUBLEEINTMAINDOUBLEA,P,ECOUTAPECOUTEPOPS,EEMVALENVALE1NVAL1WHILESTACKLENGTHS1|EMVAL0RETURNENVAL10,AKM2,1021GAKM2,01,AKM2,0620AKMAKMM1,1AKM1,12,AKM1,1411GAKMM,N1AKM1,03,AKM1,0610AKMAKMM1,1AKM0,14,AKM0,1401AKMN12退栈0,AKM2,1021GAKM2,01,AKM2,0620AKMAKMM1,1AKM1,12,AKM1,1411GAKMM,N1AKM1,03,AKM1,0610AKMAKMM1,1AKM0,12退栈0,AKM2,1021GAKM2,01,AKM2,0620AKMAKMM1,1AKM1,12,AKM1,1411GAKMM,N1AKM1,02AKMAKMM1,GAKM0,23,AKM0,2702AKMN13退栈0,AKM2,1021GAKM2,01,AKM2,0620AKMAKMM1,1AKM1,12,AKM1,1411GAKMM,N1AKM1,02AKMAKMM1,GAKM0,23退栈0,AKM2,1021GAKM2,01,AKM2,0620AKMAKMM1,1AKM1,13退栈0,AKM2,1021GAKM2,03AKMAKM1,31,AKM1,3613GAKM1,2AKMM1,G2,AKM1,2612GAKM1,1AKMM1,G3,AKM1,1611GAKM1,0AKMM1,G4,AKM1,0610AKMAKM0,15,AKM0,1401AKM0,12退栈0,AKM2,1021GAKM2,03AKMAKM1,31,AKM1,3613GAKM1,2AKMM1,G2,AKM1,2612GAKM1,1AKMM1,G3,AKM1,1611GAKM1,0AKMM1,G4,AKM1,0610AKMAKM0,12退栈0,AKM2,1021GAKM2,03AKMAKM1,31,AKM1,3613GAKM1,2AKMM1,G2,AKM1,2612GAKM1,1AKMM1,G3,AKM1,1611GAKM1,02AKMM1,GAKM0,24,AKM0,2702AKMN13退栈0,AKM2,1021GAKM2,03AKMAKM1,31,AKM1,3613GAKM1,2AKMM1,G2,AKM1,2612GAKM1,1AKMM1,G3,AKM1,1611GAKM1,02AKMM1,GAKM0,23退栈0,AKM2,1021GAKM2,03AKMAKM1,31,AKM1,3613GAKM1,2AKMM1,G2,AKM1,2612GAKM1,13AKMM1,GAKM0,33,AKM0,3703AKMN14退栈0,AKM2,1021GAKM2,03AKMAKM1,31,AKM1,3613GAKM1,2AKMM1,G2,AKM1,2612GAKM1,13AKMM1,GAKM0,34退栈0,AKM2,1021GAKM2,03AKMAKM1,31,AKM1,3613GAKM1,24AKMM1,GAKM0,42,AKM0,4704AKMN15退栈0,AKM2,1021GAKM2,03AKMAKM1,31,AKM1,3613GAKM1,24AKMM1,GAKM0,45退栈0,AKM2,1021GAKM2,03AKMAKM1,35退栈AKM2,15328假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列何处队列的算法。解TYPEDEFINTELEMTYPETYPEDEFSTRUCTNODETYPEELEMTYPEDATANODETYPENEXTQNODE,QPTRTYPEDEFSTRUCTQPTRREARINTSIZEQUEUESTATUSINITQUEUEQUEUEQSIZE0RETURNOKSTATUSENQUEUEQUEUEPNEWQNODEIFPRETURNFALSEPDATAEIFQREARQREARPPNEXTQREARELSEPNEXTQREARNEXTQREARNEXTPQREARPQSIZERETURNOKSTATUSDEQUEUEQUEUEIFQSIZE0RETURNFALSEIFQSIZE1PQREAREPDATAQREARNULLDELETEPELSEPQREARNEXTEPDATAQREARNEXTPNEXTDELETEPQSIZERETURNOK329如果希望循环队列中的元素都能得到利用，则需设置一个标志域TAG，并以TAG的值为0和1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。解DEFINEMAXQSIZE4TYPEDEFINTELEMTYPETYPEDEFSTRUCTELEMTYPEBASEINTFRONTINTREARSTATUSTAGQUEUESTATUSINITQUEUEQUEUEIFQBASERETURNFALSEQFRONT0QREAR0QTAG0RETURNOKSTATUSENQUEUEQUEUEELSEQBASEQREAREQREARQREAR1MAXQSIZEIFQREARQFRONTQTAG1RETURNOKSTATUSDEQUEUEQUEUEELSEEQBASEQFRONTQFRONTQFRONT1MAXQSIZEQTAG0RETURNOK设标志节省存储空间，但运行时间较长。不设标志则正好相反。330假设将循环队列定义为以域变量REAR和LENGTH分别指示循环队列中队尾元素的位置和内含元素的个数。试给