【MOOC】数据结构与算法-北京大学 中国大学慕课MOOC答案

【MOOC】数据结构与算法-北京大学中国大学慕课MOOC答案第一章概论测验1、【单选题】下列不属于线性结构的是：Whichoneofthefollowingsdoesnotbelongtolinearstructure:（Thereisonlyonecorrectanswer）本题答案：【图(graph)】2、【单选题】以下哪种结构是逻辑结构，而与存储和运算无关：Whichofthefollowingstructureisalogicalstructureregardlessofthestorageoralgorithm:（Thereisonlyonecorrectanswer）本题答案：【队列(queue)】3、【多选题】关于算法特性描述正确的有：Whichoneisrightaboutalgorithm’scharacterization:（therearemorethanonecorrectanswers）本题答案：【算法保证计算结果的正确性。Algorithmwillensurethecorrectnessofthecalculationresults.#算法的有穷性指算法必须在有限步骤内结束。Thefinitenatureofalgorithmsmeansalgorithmmustbecompletedwithinalimitedstep.】4、【多选题】下列说法正确的是：Whichoptionsmaybecorrect?（therearemorethanonecorrectanswers）本题答案：【如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)是O(h(n))【iff(n)isO(g(n))，g(n)isO(h(n))，thenf(n)isO(h(n))】#如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)+g(n)是O(h(n))【iff(n)isO(g(n))，g(n)isO(h(n))，sof(n)+g(n)isO(h(n))】】5、【多选题】已知一个数组a的长度为n，求问下面这段代码的时间复杂度:Anarrayofa,itslengthisknownasn.Pleaseanswerthetimecomplexityofthefollowingcode.（Therearemorethanoneanswers.）for(i=0,length=1;in-1;i++){for(j=i+1;jna[j-1]=a[j];j++)if(lengthj-i+1)length=j-i+1;}本题答案：【#】6、【填空题】计算运行下列程序段后m的值：Calculatethevalueofmafterrunningthefollowingprogramsegmentn=9;m=0;for(i=1;i=n;i++)for(j=2*i;j=n;j++)m=m+1;求m的值本题答案：【20】7、【填空题】由大到小写出以下时间复杂度的序列：答案直接写标号，如：(1)(2)(3)(4)(5)（提示：系统基于字符匹配来判定答案，所以您的答案中不要出现空格）Writethefollowingtimecomplexityindescendingsequence:Writedowntheanswerlabelssuchas(1)(2)(3)(4)(5).（Hint：Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.）本题答案：【(5)(1)(2)(4)(3)】第二章线性表测验1、【多选题】下面关于线性表的叙述中，正确的是哪些？Whichofthefollowingsaboutlinearlistarecorrect?（Therearemorethanoneanswers.）Selecttheanswerthatmatches本题答案：【线性表采用顺序存储，必须占用一片连续的存储单元。Linearlistsusesequentialstoragewhichmustoccupyacontinuousmemoryunits.#线性表采用链接存储，不必占用一片连续的存储单元。Linearlistsusingthelinkedstorage,donotoccupyacontinuousmemoryunits.#线性表采用链接存储，便于插入和删除操作。Linearlistsusingthelinkedstorage,itiseasyforinsertanddeletingoperations.】2、【多选题】下面的叙述中正确的是：Selecttheanswerthatmatches（Therearemorethanonecorrectanswers）本题答案：【线性表在顺序存储时，查找第i个元素的时间与i的数值无关。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisregardlessofthevalueofi.#线性表在链式存储时，插入第i个元素的时间与i的数值成正比。Whenlinearlistsstoredinthelinkedform,thetimetoinsertthei-thelementisproportionaltovaluewithi.】3、【多选题】完成在双循环链表结点p之后插入s的操作为：Theoperationtoinsertsafterthedoublycircularlinkedlist’snodepis:(Therearemorethanoneanswers.)本题答案：【p-next-prev=s;s-prev=p;s-next=p-next;p-next=s;#s-next=p-next;p-next-prev=s;s-prev=p;p-next=s;】4、【填空题】对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(___),在给定值为x的结点后插入一个新结点的时间复杂度为O(___)。（请依次填入,格式为(a)(b),如果您的答案中出现字母，请使用小写;后一空系统基于字符匹配来判定答案，所以您的答案中不要出现空格）Forasinglelinkedlistwithnnodes,andafteraknownnode*ptoinsertanewnode,thetimecomplexityisO(___);afteragivennodewithxvalueinsertanewnode,thetimecomplexityisO(___).(Ifyouranswercontainsletters,uselowercaseone.Thesecondblankisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.)本题答案：【(1)(n)】5、【填空题】设某循环链表长度为n，并设其中一节点为p1，然后按照链表的顺序将后面的节点依次命名为p2,p3,...,pn，那么请问pn.next=____(答案为一个节点名，注意所有字母为小写且答案中不包含空格)本题答案：【p1】第三章栈与队列测验1、【单选题】设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是_____________。AssumethatthestackSandqueueQ’sinitialstateisempty,theelementse1,e2,e3,e4,e5ande6followedthroughstackS,anelementoutthestackmeansintothequeueQ.Ifthesequencethesixelementsoutofthequeueise2,e4,e3,e6,e5,e1thenstackSofcapacityshouldbeatleast_____________.（Thereisonlyonecorrectanswer）本题答案：【3】2、【单选题】现有中缀表达式E=((100-4)/3+3*(36-7))*2。以下哪个是与E等价的后缀表达式？ExistinginfixexpressionE=((100-4)/3+3*(36-7))*2.WhichofthefollowingistheequivalentpostfixexpressionofE?（Thereisonlyonecorrectanswer）本题答案：【1004–3/3367–*+2*】3、【多选题】队列的特点包括：Queue’featuresinclude:（Therearemorethanoneanswers.）本题答案：【先进先出First-infirst-out(FIFO)#后进后出Last-inlast-out(LILO)】4、【多选题】以下循环队列的实现方式中，长度为n的队列，所能容纳的元素个数也为n的有:Inthefollowingrealizingwaysofcircularqueue,thequeuewhoselengthisncanalsocontainthenumberofnelementsis:（Therearemorethanoneanswers.）本题答案：【用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数Withthequeue’sheadandtailpointersmarkedasfrontandrear,usetheintegervariablelentorecordthenumberofelements.#用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空Withthequeue’sheadandtailpointersmarkedasfrontandrear,useBooleanvariableemptyrecordwhetherthequeueisempty.】5、【填空题】编号为1，2，3，4的四辆列车，顺序开进一个栈式结构的站台；则开出车站的顺序有______种可能。注释：例如1,2,3,4或4,3,2，1就是其中两种可能出站序列；而4,3,1,2是非法序列。Numbered1,2,3,4fourtrains,orderlyenteredastackstructurestation.Howmanypossibleleavingsequencesofthatfourtrains?______.Note:Forinstance,theleavingsequencecouldbe1,2,3,4or4,3,2,1thesetwopossibilities,but4,3,1,2isnotapossiblesequence.本题答案：【14】6、【填空题】双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。现有4个不同的元素顺序输入到双端队列，那么可以得到_____种不同的排列。double-endedqueuecaninsertanddeleteoperationsonbothendsofthequeue.Thatitcaninsert/deleteatitstail,butalsoatthehead.Existing4differentelementssequentiallyinputtothedouble-endedqueue,youcanget_____differentpermutations.本题答案：【8】第四章字符串测验1、【单选题】设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为()（单选）Therearetwostringspq,qisp’ssubstring.Thealgorithmtosearchthefirsttimeqappearedinpiscalled()（Thereisonlyonecorrectanswer）本题答案：【匹配Matching】2、【单选题】下列说法正确的是：（单选）Whichofthefollowingstatementsiscorrect?（Thereisonlyonecorrectanswer）本题答案：【空串是任意字符串的子串Emptystringisasubstringofarbitrarystring.】3、【单选题】若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))注意：substr(S,i,j)是对字符串S的下标为i开始取j个字符，这里的下标是从0开始的(单选)IfthestringS1='ABCDEFG',S2='9898',S3='###',S4='012345',executeconcat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,'8'),length(S2)))Notesubstr(S,i,j)istheoperationtotakestringS’sjcharactersfromsubscripti.Subscripthereisstartingfrom0.（Thereisonlyonecorrectanswer）H、2345I、ABCDL、1234M、ABCP、G2345本题答案：【ABCD###1234】4、【单选题】下面关于串的的叙述中，哪一个是不正确的:（单选）Whichofthefollowingdescriptionsaboutstringisnotcorrect?（Thereisonlyonecorrectanswer）本题答案：【空串是由空格构成的串Emptystringisastringconsistingofspaces.】5、【单选题】SeekthestringBAAABBBAA‘sfeaturevector,wherethefeaturevectorisdefinedasfollows:（Thereisonlyonecorrectanswer）本题答案：【{-1,0,0,0,0,1,1,1,2}】6、【多选题】在字符{A,C,G,T}组成的DNA序列中，A和T、C和G是互补对。判断一个DNA序列中是否存在互补回文串（例如，ATCATGAT的补串是TAGTACTA，与原串形成互补回文串）。下面DNA序列中存在互补回文串的是：（多选）IntheDNAsequencesconsistingofcharacter{A,C,G,T},AandT,CandGarecomplementarypairs.JudgingwhetherthereisacomplementarypalindromesequenceinaDNAsequence(e.g.,ATCATGAT’scomplementstringsisTAGTACTA,itiscomplementarypalindromesequencewiththeoriginalsequence).WhichofthefollowingDNAsequenceshavecomplementarypalindromestring?（Therearemorethanoneanswers.）本题答案：【CTGATCAG#AATTAATT#GTACGTAC#AGCTAGCT】7、【填空题】若字符串s=“software”，则其子串个数为：Ifthestrings=software,thenthenumberofitssub-stringis:本题答案：【37】8、【填空题】若字符串s=”algorithm”，则其子串个数为：Ifthestrings=algorithm,thenthenumberofitssub-stringis:本题答案：【46】9、【填空题】设有字符串变量StringA＝“”，B＝“MULE”，C＝“OLD”，D＝“MY”;请计算下列表达式（3个答案本身不要出现空格，答案之间用空格分开）AssumethatthereisastringvariableStringA=,B=MULE,C=OLD,D=MY;Pleasecalculatethefollowingexpression:(1)D+C+B(2)B.substr(3，2)(3)A.strlength()本题答案：【MYOLDMULEE0】10、【填空题】一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：Atextstringcanbeencryptedbythegivenlettersmappingtable.Forexample,thelettersmappingtableis:本题答案：【neopwmfbl】11、【填空题】S=“S1S2…Sn”是一个长为n的字符串，存放在一个数组中，编程序将S改造之后输出。S=S1S2...Snisastringoflengthn,andstoredinanarray,outputSafteritsprogrammabletransformation.1.将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分；1.Alltheeven-numberedcharactersofSshouldbeplacedinaccordancewiththeirsubscriptdescendingorderinthesecondhalfofS;2.将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；2.Alltheodd-numberedcharactersofSshouldbeplacedinaccordancewiththeirsubscriptascendingorderinthefirsthalfofS.例如：S=‘ABCDEFGHIJKL’，则改造后的S为‘ACEGIKLJHFDB’。则S=’algorithm’,改造后为____________（Hint：1.答案不需要加引号2.系统基于字符匹配来判定答案，所以您的答案中不要出现空格）。Forexample:S='ABCDEFGHIJKL',thenafterthetransformationSis'ACEGIKLJHFDB'.IfS='algorithm',thenafterthetransformationSis____________(Hint:1.pleasedon’tincludeanyquotesinyouranswer.2.Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks).本题答案：【agrtmhiol】12、【填空题】下列程序判断字符串s是否对称，对称则返回1，否则返回0；如f(abba)返回1，f(abab)返回0；Usethefollowingprocedurestodeterminewhetherthestringsissymmetry,symmetryreturns1,otherwisereturn0;suchasf(abab)returns0;intf(chars[]){inti=0,j=0;while(s[j])(1)__++;for(j--;ijs[i]==s[j];i++,j--);return((2)__=(3)__);}注：(1)和(2)和(3)三个答案之间用空格分隔，每个答案是一个字符,不要加空格本题答案：【jij】13、【填空题】上一题中的字符串BAAABBBAA，与目标BAAABBBCDDDCCHHHHBBBAAABBBAADD进行匹配，至少需要多少次字符匹配（提示：利用优化后的Next数组):ThestringinquestionaboveBAAABBBAAmatcheswithBAAABBBCDDDCCHHHHBBBAAABBBAADD.Howmanytimescharactermatchingwillneedatleast?(Hint:Use“Next”arrays):本题答案：【31】第五章二叉树前半部分（5.1~5.4）测验1、【多选题】下列关于二叉树性质的说法正确的有：（多选）Whichsentencesofthefollowingsarerightaboutabinarytree'scharacterization:（Therearemorethanonecorrectanswers）本题答案：【非空满二叉树的结点个数一定为奇数个。Theamountofnodesofafullbinarytreewithatleastonenodemustbeodd.#当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。Ifacompletebinarytreeisafullbinarytree,itwillbepossiblethatleafnodesisnotonthenethermostlayer.#一棵非空二叉树的为空的外部结点数目等于其结点数加1。Theamountofexternalnullnodesinabinarytreewithatleastonenodeequalstoitsamountofnodesplus1.】2、【多选题】下列关于二叉树遍历的说法正确的有:Whichsentencesofthefollowingsarerightabouttraversalofabinarytree:H、所有结点左子树为空的二叉树的中序和后序遍历顺序恰好一样。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutleftchildtreearethesame.I、所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutrightchildtreearethesame.J、存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。Thereexistsabinarytreewithatleastonenode,whosepreorder,infixorderandpostorderareallthesame.本题答案：【所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。Thesequencesofpreorderandinfixorderofabinarytreewithallnodeswithoutleftchildtreearethesame.#只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历的顺序恰好一样。Onlythesequencesofpreorderandpostorderofthebinarytreewithnonodesoronlyonenodearethesame.#所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutrightchildtreearethesame.#存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。Thereexistsabinarytreewithatleastonenode,whosepreorder,infixorderandpostorderareallthesame.】3、【填空题】一棵有510个结点的完全二叉树的高度为多少？（独根树高度为1)Whatistheheightofacompletebinarytreewith510nodes?(theheightofatreewithonlyarootis1)本题答案：【9】4、【填空题】一棵有512个结点的完全二叉树的高度为多少？（独根树高度为1）Whatistheheightofacompletebinarytreewith512nodes?(theheightofatreewithonlyarootis1)本题答案：【10】5、【填空题】在一棵非空二叉树中，若度为0的结点的个数n，度为2的结点个数为m，则有n=________(系统根据字符串匹配来判定答案，所以您的答案中请不要包含空格)Forabinarytreewithatleastonenode,iftherearennodeswithdegree0andmnodeswithdegree2,thenn=________（Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.）本题答案：【m+1】6、【填空题】已知一棵树的前序遍历为ABDEGCF，中序遍历为DBGEACF，求这棵树的后序遍历。（字母和字母之间不要有空格）ThepreordersequenceofatreeisABDEGCF,anditsinfixordersequenceisDBGEACF,pleasewritedownitspostordersequence.(Thereisnoblankspacebetweenletters)本题答案：【DGEBFCA】7、【填空题】已知一棵树的中序遍历为DBGEACF，后序遍历为DGEBFCA，求这棵树的前序遍历。（字母和字母之间不要有空格）TheinfixordersequenceofatreeisDBGEACF,anditspostordersequenceisDGEBFCA,pleasewritedownitspreordersequence.(Thereisnoblankspacebetweenletters)本题答案：【ABDEGCF】8、【填空题】请写出下面这棵二叉树的前序遍历（字母和字母之间不要有空格）Pleasewritedownthepreordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)本题答案：【BEXLMKCPDHQA】9、【填空题】请写出下面这棵二叉树的中序遍历（字母和字母之间不要有空格）Pleasewritedowntheinfixordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)本题答案：【LXMECKPBQHDA】10、【填空题】请写出下面这棵二叉树的后序遍历（字母和字母之间不要有空格）Pleasewritedownthepostordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)本题答案：【LMXCPKEQHADB】第五章二叉树后半部分（5.5~5.7）测验1、【多选题】下列关于二叉搜索树的说法正确的有Whichsentencesofthefollowingsarerightaboutbinarysearchtree:本题答案：【二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。Ifweprintabinarysearchtree'snodesaccordingitsinfixorder,thesequencewillbefromsmalltolarge.#如果结点χ的左子树有右子树，则存在某个结点的值介于结点χ的值和χ左儿子的值之间，并且这个结点在$$x$$的左子树之中。Iftheleftchildtreeofanodexhasarightchildtree,thenthereexistssomenodewhosevalueisbetweenthevalueofnodexandthevalueofitsleftchildnode,andthisnodeisontheleftchildtreeofnodex.#当根结点没有左儿子时，根结点一定是值最小的结点。Iftherootnodedoesn'thaveleftchild,itmustbethenodewiththesmallestvalue.】2、【多选题】下列关于堆的说法正确的有:Whichsentencesofthefollowingsareright:本题答案：【堆一定是完全二叉树。Aheapmustbeacompletebinarytree.#最小堆中，某个结点左子树中最大的结点可能比右子树中最小的结点小。Inaminimumheap,thelargestvalueonsomenode'sleftchildtreecouldbepossiblysmallerthanthesmallestvalueofitsrightchildtree.#使用筛选法建堆要比将元素一个一个插入堆来建堆效率高。Screeningmethodhasahigherefficiencythaninsertingelementsonebyonewhileconstructingaheap.】3、【多选题】下列关于Huffman树和Huffman编码的说法正确的有:WhichsentencesofthefollowingsarerightaboutHuffmantreeandHuffmancode:本题答案：【Huffman树一定是满二叉树。AHuffmantreemustbeafullbinarytree.#Huffman编码是一种前缀编码。Huffmancodeisakindofprefixcode.#对于同样的一组权值两两不同的内容可以得到不同的Huffman编码方案。DifferentcontentwiththesamegroupofweightscangetdifferentHuffmancodes.】4、【多选题】一组包含不同权的字母已经对应好Huffman编码，如果某一个字母对应编码001,下面说法正确的有AgroupofletterswithdifferentweightshascorrespondedwithHuffmancodes,ifaletter'scorrespondingcodeis001,whichsentencesofthefollowingsareright:本题答案：【以001开头的编码不可能对应其他字母。Acodebeginningwith001couldn'tcorrespondwithotherletters.#以01开头和1开头的编码肯定对应某个字母。Codesbeginningwith01or1mustcorrespongdingwithsomeletters.#建好的Huffman树至少包含4个叶结点。TheHuffmantreecontainsatleast4leafnodes.】5、【填空题】如果按关键码值递增的顺序依次将n个关键码值插入到二叉搜索树中，如果对这样的二叉搜索树进行检索时，每次检索的字符都等概率的从这n个关键码值中选取，平均比较次数为多少？Ifweinsertnkeyvaluestoabinarysearchtreesuccessivelyfromsmalltolarge,whenwesearchthisbinarysearchtree,eachtimethesearchcharacterisselectedfromthesenkeyvalueswiththesamepossibility,thenhowmanytimeswillthecomparisonbeonaverage?本题答案：【(n+1)/2##%_YZPRLFH_%##(1+n)/2】6、【填空题】从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜索树，对该二叉搜索树按照前序遍历得到的序列为？（答案中每两个元素之间用一个空格隔开）Fromanullbinarytree,insertkeyvalues{18,73,10,5,68,99,27,41,51,32,25}successivelyaccordingtotheinsertionalgorithmofabinarysearchtreestrictly(norotationandbalance)toconstructabinarysearchtree.Pleasewritedownthesequenceofpreorderofthisbinarysearchtree.(Thereisoneblankspacebetweentwoelements)本题答案：【181057368272541325199】7、【填空题】从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜索树，对该二叉搜索树按照后序遍历得到的序列为？（答案中每两个元素之间用一个空格隔开）Fromanullbinarytree,insertkeyvalues{18,73,10,5,68,99,27,41,51,32,25}successivelyaccordingtotheinsertionalgorithmofabinarysearchtreestrictly(norotationandbalance)toconstructabinarysearchtree.Pleasewritedownthesequenceofpostorderofthisbinarysearchtree.(Thereisoneblankspacebetweentwoelements)本题答案：【510253251412768997318】8、【填空题】从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码构造出一棵二叉树，以怎样的顺序插入关键码集合{14，32，47，6，9，12，78，63，29，81}可以使得树的深度最小？请依次写出插入到树中的元素，每两个元素之间用一个空格隔开。如果有多组满足要求的方案，请使得你的答案中先插入的元素尽可能的小。Fromanullbinarytree,insertkeyvaluessuccessivelyaccordingtotheinsertionalgorithmofabinarysearchtreestrictly(norotationandbalance)toconstructabinarysearchtree.Whatistheinsertionsequencethatcouldmakethetreehaveasmallestdepthwithakeyvalueset{14，32，47，6，9，12，78，63，29，81}?Pleasewritedowntheelementssuccessively,andthereisoneblankspacebetweentwoelements.Iftherearemorethanoneanswerthatmeetthecondition,pleasemaketheelementwhichneedstobeinsertedfirstassmallaspossibleinyouranswer.本题答案：【126947291432786381】9、【填空题】对于关键码序列{38，64，52，15，73，40，48，55，26，12}，用筛选法建最小值堆，若一旦发现逆序对就进行交换，共需要交换元素多少次？Forthekeyvaluesequence{38，64，52，15，73，40，48，55，26，12},usethescreeningmethodtoconstuctaminimumheap,ifweexchangethemwhenwefindreversedorder,thenhowmanytimesshouldweexchangethem?本题答案：【6】10、【填空题】对于如下图所示的最大堆，删除掉最大的元素后，堆的前序遍历结果是Forthefollowingmaximumheap,afterdeletingthemaximumelement,thepreordertraversalsequenceis请依次写出插入到树中的元素，每两个元素之间用一个空格隔开。Pleasewritedowntheelementssuccessively,andthereisoneblankspacebetweentwoelements.本题答案：【59432412233728557483】11、【填空题】对于如下图所示的最大堆，删除掉最大的元素后，堆的后序遍历结果是Forthefollowingmaximumheap,afterdeletingthemaximumelement,thepostordertraversalsequenceis本题答案：【12232428537434835759】12、【填空题】下表展示了在一段文本中每个字母出现的次数。Thefrequenciesthateachletterappearsinaparagraphisrepresentedasfollow.本题答案：【36】13、【填空题】对于给定的一组权W={1,4,9,16,25,36,49,64,81,100}，构造一棵具有最小带权外部路径长度的三叉树，写出这棵树的带权外部路径长度。ForagivengroupofweightsW={1,4,9,16,25,36,49,64,81,100},pleaseconstructaternarytreewithaminimumweightedroutelengthandwritedownthisweightedroutelength.本题答案：【705】14、【填空题】请阅读下面一段代码PleasereadthefollowingcodeC++：本题答案：【1】15、【填空题】请阅读下面一段代码PleasereadthefollowingcodeC++：本题答案：【2】16、【填空题】请阅读下面一段代码PleasereadthefollowingcodeC++：本题答案：【3】第六章树测验1、【单选题】一个深度为h的满k叉树，最多有多少个叶结点？（独根树深度为0）(单选)Thereisafullk-arytree,whosedepthish.Howmanyleafnodescanithaveatmost?(Thedepthofatree,whichonlyhasarootnode,is0.)（Thereisonlyonecorrectanswer）本题答案：【】2、【单选题】一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0）Thereisafullk-arytree,whosedepthish.Howmanynodescanithaveatmost?(Thedepthofatree,whichonlyhasarootnode,is0.)本题答案：【】3、【单选题】设F是由T1,T2,T3三棵树组成的森林，其中T1,T2,T3的结点数分别为n1,n2和n3，与F对应的二叉树为B，则二叉树B的右子树中有_____________个结点(单选）AssumethatFisaforest,madeupoftreeT1,T2,T3,andthenodenumbersofT1,T2,T3aren1,n2,n3.LetBbethecorrespondingbinarytreeofF,thenB'srightsub-treewillhas__________nodes.(Thereisonlyonecorrectanswer)本题答案：【n2+n3】4、【单选题】设F是由T1,T2,T3三棵树组成的森林，其中T1,T2,T3的结点数分别为n1,n2和n3，与F对应的二叉树为B，则二叉树B的左子树中有_____________个结点(单选）AssumethatFisaforest,madeupoftreeT1,T2,T3,andthenodenumbersofT1,T2,T3aren1,n2,n3.LetBbethecorrespondingbinarytreeofF,thenB'sleftsub-treewillhas__________nodes.(Thereisonlyonecorrectanswer)本题答案：【n1-1】5、【单选题】将一棵树T转换为左子/右兄链表表示的二叉树B，则T的后根次序遍历序列是B的相应_________序列。（单选）TransformatreeTintoabinarytreeB,whichisrepresentedbyLeft-Child/Right-Siblingimplementation.Thenthepost-ordertraversalsequenceofTisthesameasthe__________sequenceofB.（Thereisonlyonecorrectanswer）本题答案：【中序遍历】6、【多选题】2-3树是一种特殊的树，它满足两个条件：（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同；如果一棵2-3树有9个叶结点，那么它可能有_________个非叶结点。(多项)2-3treeisaspecialkindoftree,itsatisfy:（1）Everyinternalnodehas2or3childnodes.(2)Alltheleafnodeshavethesamelengthofthepathtotherootnode.Ifa2-3treehas9leafnodes,thenitmayhave__________non-leafnodes.（Therearemorethanonecorrectanswers）本题答案：【4#7】7、【填空题】给出一棵树的逻辑结构T=(N,R),其中：N={A,B,C,D,E,F,G,H,I,J,K}R={r}r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)}Givenalogicalstructureofatree,T=(N,R),andN={A,B,C,D,E,F,G,H,I,J,K},R={r},r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)}试回答下列问题：Pleaseanswerthesequestions:（1）哪个是根结点？whichistherootnode?（2）哪些是F的孩子？whicharethechildnodesofNodeF?（3）结点K的层次是多少？（注：根的层数为0，独根树深度为0，高度为1，其他题目同样如此；同一个选项的答案如果有多个字母，按照字典序排列，且不要以空格分隔）(P.S.theleveloftherootnodeis0,thedepthofatree,whichonlyhasarootnode,is0,anditsheightis1.Otherproblemshavethesameregulations.Ifthereareseveralalphabetsinonequestion,orderthembylexicographicalorder,anddonotaddspaces.)本题答案：【AGH3】8、【填空题】给出一棵树的逻辑结构T=(N,R),其中：N={A,B,C,D,E,F,G,H,I,J,K}R={r}r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)}试回答下列问题：Givenalogicalstructureofatree,T=(N,R),andN={A,B,C,D,E,F,G,H,I,J,K},R={r},r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)}Pleaseanswerthesequestions:（1）哪个是F的父结点？whichistheparentnodeofNodeF?（2）哪些是B的子孙？whicharetheoffspringofNodeB?（3）以结点C为根的子树的深度是多少？whatisthedepthofthesub-treewhoserootnodeisNodeC?（注：根的层数为0，独根树深度为0，高度为1，其他题目同样如此；各个选项之间的答案用空格分隔就好；同一个选项的答案如果有多个字母，按照字典序排列，且不要以空格分隔）（P.S.theleveloftherootnodeis0,thedepthofatree,whichonlyhasarootnode,is0,anditsheightis1.Otherproblemshavethesameregulations.Ifthereareseveralalphabetsinonequestion,orderthembylexicographicalorder,anddonotaddspaces.)本题答案：【BEFGH2】9、【填空题】给出一棵树的逻辑结构T=(N,R),其中：N={A,B,C,D,E,F,G,H,I,J,K}R={r}r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)}试回答下列问题：Givenalogicalstructureofatree,T=(N,R),andN={A,B,C,D,E,F,G,H,I,J,K},R={r},r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)}Pleaseanswerthesequestions:（1）哪些是叶结点？whicharetheleafnodes?（2）哪些是F的祖先？whichistheparentnodeofNodeF?（3）树的深度是多少？whatisthedepthofthetree?（注：根的层数为0，独根树深度为0，高度为1，其他题目同样如此；同一个小题的答案如果有多个字母，按照字典序排列，且不要以空格分隔，不同小题用一个空格隔开）本题答案：【DEGHIKAB3】10、【填空题】若一个具有N个顶点，K条边的无向图是一个森林（NK且2K=N），则该森林有多少棵树？Thereisanundirectedgraph.IthasNnodesandKedges.(NKand2K=N).Ifitisaforest,thenhowmanytreeswillithas?本题答案：【N-K】11、【填空题】将下图的二叉树转换为对应的森林，按照先根次序列出其结点。（答案的字母之间没有空格）Transformthisbinarytreeintothecorrespondingforest,andwritedownthepre-ordernodesequence.(Donotaddspacesinyouranswer.)本题答案：【ABECFDGHIJKL】12、【填空题】将下图的二叉树转换为对应的森林，按照后根次序列出其结点。（答案的字母之间没有空格）Transformthisbinarytreeintothecorrespondingforest,andwritedownthepost-ordernodesequence.(Donotaddspacesinyouranswer.)本题答案：【EBFCDAIJKHGL】13、【填空题】一棵完全三叉树，下标为121的结点在第几层？（注：下标号从0开始，根的层数为0）Inacomplete3-arytree,whatlevelisthenode,whosesubscriptis121,standon?(P.S.thesubscriptstartsform0,andthelevelofrootnodeis0)本题答案：【5】14、【填空题】一棵完全三叉树，下标为120的结点在第几层？（注：下标号从0开始，根的层数为0）Inacomplete3-arytree,whatlevelisthenode,whosesubscriptis120,standon?(P.S.thesubscriptstartsform0,andthelevelofrootnodeis0)本题答案：【4】15、【填空题】根据树的双标记层次遍历序列，求其带度数的后根遍历序列Giventhedouble-tagginglevel-ordertraversalsequenceofatree,pleasewritedownthepost-ordertraversalsequencewithdegree.比如：已知一棵树的双标记层次遍历序列如下：Forexample,assumethatatree'sdouble-tagginglevel-ordertraversalsequenceisshownasfollowed:本题答案：【H0C1D0G0B3F0I0E2A2】16、【填空题】根据树的双标记层次遍历序列，求其带度数的后根遍历序列Giventhedouble-tagginglevel-ordertraversalsequenceofatree,pleasewritedownthepost-ordertraversalsequencewithdegree.比如：已知一棵树的双标记层次遍历序列如下：Forexample,assumethatatree'sdouble-tagginglevel-ordertraversalsequenceisshownasfollowed:本题答案：【G0B1H0D1C1E0I0F1A4】17、【填空题】根据树的双标记层次遍历序列，求其带度数的后根遍历序列Giventhedouble-tagginglevel-ordertraversalsequenceofatree,pleasewritedownthepost-ordertraversalsequencewithdegree.本题答案：【D0E0C2H0I0F2B2G0A2】18、【填空题】对于以下等价类，采用“加权合并规则”（也称“重量权衡合并规则”），进行并查运算，给出最后父节点索引序列。Forthefollowingequivalenceclass,pleaseuseweightedunionruleandUNION/FINDalgorithmtowritedownthefinalparentnodeindexsequence.4-06-28-49-43-59-55-21-27-1注意：当合并大小相同的两棵树的时候，将第二棵树的根指向第一棵树的根；根节点的索引是它本身；数字之间用空格隔开。Notice:Whenwejointwotreeswiththesamesize,welettherootofthesecondtreepointtotherootofthefirsttree.Theindexoftherootnodeisitself.Separatethenumberswithonlyonespaces.本题答案：【4464434444】19、【填空题】对于以下等价类，采用“加权合并规则”（也称“重量权衡合并规则”），进行并查运算，给出最后父节点索引序列。Forthefollowingequivalenceclass,pleaseuseweightedunionruleandUNION/FINDalgorithmtowritedownthefinalparentnodeindexsequence.8-93-27-45-96-18-67-32-58-0注意：当合并大小相同的两棵树的时候，将第二棵树的根指向第一棵树的根；根节点的索引是它本身；数字之间用空格隔开。Notice:Whenwejointwotreeswiththesamesize,welettherootofthesecondtreepointtotherootofthefirsttree.Theindexoftherootnodeisitself.Separatethenumberswithonlyonespaces.本题答案：【8637788888】数据结构与算法期中考试（范围：前六章）1、【单选题】一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0）Forafullk-arytreewithdepthh,howmanynodescouldithaveatmost?(thedepthofatreewithonlyonenodeis0)本题答案：【】2、【单选题】对二叉排序树（即BST，也称“二叉搜索树”）进行什么遍历，可以得到该二叉树所有结点构成的排序序列？Fromwhichtraversalcanwegettheorderedsequenceofthenodesofabinarysearchtree?本题答案：【中序inorder】3、【多选题】顺序栈是用一段连续的空间存储内容，本质是顺序表。链式栈则是采用单链表的方式存储。下列关于这两种存储方式的说法正确的是：Sequentialstackstoreselementsinacontiguousspace,whichisessentiallyasequentiallist.Linkedstackisimplementedbyasinglelinkedlistinstead.Whichofthefollowingaboutthetwostoragemethodsarecorrect?(multiplechoice)本题答案：【顺序栈的压栈和出栈操作只需常数时间。Thepushandpopoperationofsequencestackonlyneedsconstanttime.#链式栈的压栈和出栈操作只需常数时间。Thepushandpopoperationoflinkedstackonlyneedsconstanttime.#顺序栈需要指定一个具体的长度Sequentialstackneedstobeassignedaspecificlength.#链式栈需要一个结构性开销Linkedstackneedsastructuralcost.】4、【多选题】在字符{A,C,G,T}组成的DNA序列中，A——T和C——G是互补对。判断一个DNA序列中是否存在互补回文串（例如，ATCATGAT的补串是TAGTACTA，与原串形成互补回文串；即要求整个原串的补串是原串的逆序）；下面DNA序列中存在互补回文串的是：(多选)InDNAsequencesconsistingofcharacters{A,C,G,T},A-TandC-Garecomplementarypairsrespectively.DeterminewhetheraDNAsequencehasacomplementarypalindromicstring(Forexample,ATCATGAT'scomplementarystringisTAGTACTA,withisthepalindromicsequencetotheoriginalstring;insuchcasethecomplementarystringisalsothereverseoftheoriginalstring);WhichofthefollowingDNAsequenceshavecomplementarypalindro