【MOOC】《数据结构与算法》(北京大学)章节期末中国大学慕课答案

【MOOC】《数据结构与算法》(北京大学)章节期末中国大学慕课答案

有些题目顺序不一致，下载后按键盘ctrl+F进行搜索第一章概论第一章概论测验1.单选题：以下哪种结构是逻辑结构，而与存储和运算无关：Whichofthefollowingstructureisalogicalstructureregardlessofthestorageoralgorithm:（Thereisonlyonecorrectanswer）

选项：

A、队列(queue)

B、双链表(doublylinkedlist)

C、数组(array)

D、顺序表(Sequentiallist)

答案：【队列(queue)】2.单选题：下列不属于线性结构的是：Whichoneofthefollowingsdoesnotbelongtolinearstructure:（Thereisonlyonecorrectanswer）

选项：

A、队列(queue)

B、散列表(hashtable)

C、向量(vector)

D、图(graph)

答案：【图(graph)】3.多选题：关于算法特性描述正确的有：Whichoneisrightaboutalgorithm’scharacterization:（therearemorethanonecorrectanswers）

选项：

A、算法保证计算结果的正确性。Algorithmwillensurethecorrectnessofthecalculationresults.

B、组成算法的指令可以有限也可能无限。Instructionswhichcompositealgorithmscanbeinfiniteorfinite

C、算法描述中下一步执行的步骤不确定。Thenextstepintheimplementationofthealgorithmdescribedisuncertain.

D、算法的有穷性指算法必须在有限步骤内结束。Thefinitenatureofalgorithmsmeansalgorithmmustbecompletedwithinalimitedstep.

答案：【算法保证计算结果的正确性。Algorithmwillensurethecorrectnessofthecalculationresults.;算法的有穷性指算法必须在有限步骤内结束。Thefinitenatureofalgorithmsmeansalgorithmmustbecompletedwithinalimitedstep.】4.多选题：已知一个数组a的长度为n，求问下面这段代码的时间复杂度:Anarrayofa,itslengthisknownasn.Pleaseanswerthetimecomplexityofthefollowingcode.（Therearemorethanoneanswers.）for(i=0,length=1;i<p=""><>for(j=i+1;jif(length<p=""><>length=j-i+1;}

选项：

A、

B、

C、

D、

答案：【;】5.多选题：下列说法正确的是：Whichoptionsmaybecorrect?（therearemorethanonecorrectanswers）

选项：

A、如果函数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))】

B、如果函数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))】

C、如果a>b>1,是，但不一定是【ifa>b>1,is，maynotbe】

D、函数f(n)是O(g(n))，当常数a足够大时，一定有函数g(n)是O(af(n))【iff(n)是O(g(n))，Whenconstantaisbigenough，theremustbeg(n)isO(af(n))】

答案：【如果函数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))】】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.多选题：完成在双循环链表结点p之后插入s的操作为：Theoperationtoinsertsafterthedoublycircularlinkedlist’snodepis:(Therearemorethanoneanswers.)

选项：

A、p->next->prev=s;s->prev=p;s->next=p->next;p->next=s;

B、p->next->prev=s;p->next=s;s->prev=p;s->next=p->next;

C、s->prev=p;s->next=p->next;p->next=s;p->next->prev=s;

D、s->next=p->next;p->next->prev=s;s->prev=p;p->next=s;

答案：【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;】2.多选题：下面的叙述中正确的是：Selecttheanswerthatmatches（Therearemorethanonecorrectanswers）

选项：

A、线性表在链式存储时，查找第i个元素的时间与i的数值无关。Whenthelinearliststoredinlinkedform,thetimetofindthei-thelementisregardlessofthevalueofi.

B、线性表在顺序存储时，查找第i个元素的时间与i的数值成正比。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisproportionaltovaluewithi.

C、线性表在顺序存储时，查找第i个元素的时间与i的数值无关。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisregardlessofthevalueofi.

D、线性表在链式存储时，插入第i个元素的时间与i的数值成正比。Whenlinearlistsstoredinthelinkedform,thetimetoinsertthei-thelementisproportionaltovaluewithi.

答案：【线性表在顺序存储时，查找第i个元素的时间与i的数值无关。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisregardlessofthevalueofi.;线性表在链式存储时，插入第i个元素的时间与i的数值成正比。Whenlinearlistsstoredinthelinkedform,thetimetoinsertthei-thelementisproportionaltovaluewithi.】3.多选题：下面关于线性表的叙述中，正确的是哪些？Whichofthefollowingsaboutlinearlistarecorrect?（Therearemorethanoneanswers.）Selecttheanswerthatmatches

选项：

A、线性表采用顺序存储，必须占用一片连续的存储单元。Linearlistsusesequentialstoragewhichmustoccupyacontinuousmemoryunits.

B、线性表采用顺序存储，便于进行插入和删除操作。Linearlistsusingsequentialstorage,itiseasytodoinsertanddeleteoperations.

C、线性表采用链接存储，不必占用一片连续的存储单元。Linearlistsusingthelinkedstorage,donotoccupyacontinuousmemoryunits.

D、线性表采用链接存储，便于插入和删除操作。Linearlistsusingthelinkedstorage,itiseasyforinsertanddeletingoperations.

答案：【线性表采用顺序存储，必须占用一片连续的存储单元。Linearlistsusesequentialstoragewhichmustoccupyacontinuousmemoryunits.;线性表采用链接存储，不必占用一片连续的存储单元。Linearlistsusingthelinkedstorage,donotoccupyacontinuousmemoryunits.;线性表采用链接存储，便于插入和删除操作。Linearlistsusingthelinkedstorage,itiseasyforinsertanddeletingoperations.】4.设某循环链表长度为n，并设其中一节点为p1，然后按照链表的顺序将后面的节点依次命名为p2,p3,...,pn，那么请问pn.next=____(答案为一个节点名，注意所有字母为小写且答案中不包含空格)

答案：【p1】5.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(___),在给定值为x的结点后插入一个新结点的时间复杂度为O(___)。（请依次填入,格式为(a)(b),如果您的答案中出现字母，请使用小写;后一空系统基于字符匹配来判定答案，所以您的答案中不要出现空格）Forasinglelinkedlistwithnnodes,andafteraknownnode*ptoinsertanewnode,thetimecomplexityisO(___);afteragivennodewithxvalueinsertanewnode,thetimecomplexityisO(___).(Ifyouranswercontainsletters,uselowercaseone.Thesecondblankisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.)

答案：【(1)(n)】第三章栈与队列第三章栈与队列测验1.单选题：现有中缀表达式E=((100-4)/3+3*(36-7))*2。以下哪个是与E等价的后缀表达式？ExistinginfixexpressionE=((100-4)/3+3*(36-7))*2.WhichofthefollowingistheequivalentpostfixexpressionofE?（Thereisonlyonecorrectanswer）

选项：

A、((1004–)3/3(367–)*+)2*

B、*+/–10043*3–3672

C、1004–3/3367–*+2*

D、*(+/(–1004)3*3(–367))2

答案：【1004–3/3367–*+2*】2.单选题：设栈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）

选项：

A、2

B、3

C、4

D、6

答案：【3】3.多选题：以下循环队列的实现方式中，长度为n的队列，所能容纳的元素个数也为n的有:Inthefollowingrealizingwaysofcircularqueue,thequeuewhoselengthisncanalsocontainthenumberofnelementsis:（Therearemorethanoneanswers.）

选项：

A、只用front和rear两个指针标记队列的头和尾，两个指针均为实指Onlyusefrontandrearasthequeue’sheadandtailpointersandthetwopointersareactuallyreferringto.

B、用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数Withthequeue’sheadandtailpointersmarkedasfrontandrear,usetheintegervariablelentorecordthenumberofelements.

C、用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空Withthequeue’sheadandtailpointersmarkedasfrontandrear,useBooleanvariableemptyrecordwhetherthequeueisempty.

D、只用front和rear两个指针标记队列的头和尾，两个指针均为虚指Onlyusefrontandrearasthequeue’sheadandtailpointersandthetwopointersarevirtuallyreferringto.

答案：【用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数Withthequeue’sheadandtailpointersmarkedasfrontandrear,usetheintegervariablelentorecordthenumberofelements.;用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空Withthequeue’sheadandtailpointersmarkedasfrontandrear,useBooleanvariableemptyrecordwhetherthequeueisempty.】4.多选题：队列的特点包括：Queue’featuresinclude:（Therearemorethanoneanswers.）

选项：

A、后进先出Last-infirst-out(LIFO)

B、先进后出First-inlast-out(FILO)

C、先进先出First-infirst-out(FIFO)

D、后进后出Last-inlast-out(LILO)

答案：【先进先出First-infirst-out(FIFO);后进后出Last-inlast-out(LILO)】5.双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。现有4个不同的元素顺序输入到双端队列，那么可以得到_____种不同的排列。double-endedqueuecaninsertanddeleteoperationsonbothendsofthequeue.Thatitcaninsert/deleteatitstail,butalsoatthehead.Existing4differentelementssequentiallyinputtothedouble-endedqueue,youcanget_____differentpermutations.

答案：【8】6.编号为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】第四章字符串第四章字符串测验1.单选题：Seekthestring"BAAABBBAA"‘sfeaturevector,wherethefeaturevectorisdefinedasfollows:（Thereisonlyonecorrectanswer）

选项：

A、{-1,0,0,0,0,0,0,1,2}

B、{-1,0,0,0,0,1,1,1,2}

C、{-1,0,0,0,0,0,1,1,2}

D、{-1,0,0,0,1,1,1,1,2}

答案：【{-1,0,0,0,0,1,1,1,2}】2.单选题：下面关于串的的叙述中，哪一个是不正确的:（单选）Whichofthefollowingdescriptionsaboutstringisnotcorrect?（Thereisonlyonecorrectanswer）

选项：

A、串是字符的有限序列Stringisafinitesequenceofcharacters.

B、模式匹配是串的一种重要运算Patternmatchingisanimportantoperation.

C、串是一种数据对象和操作都特殊的线性表Stringisalinearlistwhosedataobjectsandoperationsbothspecial

D、空串是由空格构成的串Emptystringisastringconsistingofspaces.

答案：【空串是由空格构成的串Emptystringisastringconsistingofspaces.】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）

选项：

A、ABC###G0123

B、ABCD###2345

C、ABCD###1234

D、ABC###G2345

答案：【ABCD###1234】4.单选题：下列说法正确的是：（单选）Whichofthefollowingstatementsiscorrect?（Thereisonlyonecorrectanswer）

选项：

A、空串就是空白串“Emptystring”isblankstring.

B、空串是任意字符串的子串Emptystringisasubstringofarbitrarystring.

C、串只可以采用顺序存储，不可以采用链式存储Stringonlycanbestoredinsequentialmethodandcannotbestoredinlinkedmethod.

D、在C++标准中，charS[M]最多能表示长度为M的字符串InC++standards,charS[M]canrepresentuptoastringoflengthM.

答案：【空串是任意字符串的子串Emptystringisasubstringofarbitrarystring.】5.单选题：设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为()（单选）Therearetwostringspq,qisp’ssubstring.Thealgorithmtosearchthefirsttimeqappearedinpiscalled()（Thereisonlyonecorrectanswer）

选项：

A、求子串Seekingsubstring

B、联接Concatenation

C、匹配Matching

D、求串长Seekinglength

答案：【匹配Matching】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.）

选项：

A、CTGATCAG

B、AATTAATT

C、TGCAACGT

D、CATGGTAC

E、GTACGTAC

F、AGCTAGCT

答案：【CTGATCAG;AATTAATT;GTACGTAC;AGCTAGCT】7.上一题中的字符串"BAAABBBAA"，与目标"BAAABBBCDDDCCHHHHBBBAAABBBAADD"进行匹配，至少需要多少次字符匹配（提示：利用优化后的Next数组):Thestringinquestionabove"BAAABBBAA"matcheswith"BAAABBBCDDDCCHHHHBBBAAABBBAADD".Howmanytimescharactermatchingwillneedatleast?(Hint:Use“Next”arrays):

答案：【31】8.下列程序判断字符串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--;i<j&&s[i]==s[j];i++,j--);return((2)__>=(3)__);}注：(1)和(2)和(3)三个答案之间用空格分隔，每个答案是一个字符,不要加空格

答案：【jij】9.S=“S1S2…Sn”是一个长为n的字符串，存放在一个数组中，编程序将S改造之后输出。S="S1S2...Sn"isastringoflengthn,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】10.一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：Atextstringcanbeencryptedbythegivenlettersmappingtable.Forexample,thelettersmappingtableis:比如字符串"encrypt"被加密为"tkzwsdf"。则字符串“algorithm”，被加密为________________（Hint：1.答案不需要加引号2.系统基于字符匹配来判定答案，所以您的答案中不要出现空格）。Asthestring"encrypt"isencryptedas"tkzwsdf",thenthe"algorithm"isencryptedas________(Hint：1.pleasedon’tincludeanyquotesinyouranswer2.Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.).

答案：【neopwmfbl】11.设有字符串变量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】12.若字符串s=”algorithm”，则其子串个数为：Ifthestrings="algorithm",thenthenumberofitssub-stringis:

答案：【46】13.若字符串s=“software”，则其子串个数为：Ifthestrings="software",thenthenumberofitssub-stringis:

答案：【37】第五章二叉树（上）第五章二叉树（上）测验1.多选题：下列关于二叉树遍历的说法正确的有:Whichsentencesofthefollowingsarerightabouttraversalofabinarytree:

选项：

A、前序和中序遍历的顺序恰好一样的二叉树，只能是空二叉树或者独根二叉树这两种情况。Onlythesequencesofpreorderandinfixorderofthebinarytreewithnonodesoronlyonenodearethesame.

B、所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。Thesequencesofpreorderandinfixorderofabinarytreewithallnodeswithoutleftchildtreearethesame.

C、所有结点右子树为空的二叉树的前序和中序遍历顺序恰好一样。Thesequencesofpreorderandinfixorderofabinarytreewithallnodeswithoutrightchildtreearethesame.

D、只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历的顺序恰好一样。Onlythesequencesofpreorderandpostorderofthebinarytreewithnonodesoronlyonenodearethesame.

E、所有结点左子树为空的二叉树的前序和后序遍历顺序恰好一样。Thesequencesofpreorderandpostorderofabinarytreewithallnodeswithoutleftchildtreearethesame.

F、所有结点右子树为空的二叉树的前序和后序遍历顺序恰好一样。Thesequencesofpreorderandpostorderofabinarytreewithallnodeswithoutleftchildtreearethesame.

G、只有空二叉树和一个根结点的二叉树这两种二叉树的中序和后序遍历的顺序恰好一样。Onlythesequencesofinfixorderandpostorderofthebinarytreewithnonodesoronlyonenodearethesame.

H、所有结点左子树为空的二叉树的中序和后序遍历顺序恰好一样。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutleftchildtreearethesame.

I、所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutrightchildtreearethesame.

J、存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。Thereexistsabinarytreewithatleastonenode,whosepreorder,infixorderandpostorderareallthesame.

答案：【所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。Thesequencesofpreorderandinfixorderofabinarytreewithallnodeswithoutleftchildtreearethesame.;只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历的顺序恰好一样。Onlythesequencesofpreorderandpostorderofthebinarytreewithnonodesoronlyonenodearethesame.;所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutrightchildtreearethesame.;存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。Thereexistsabinarytreewithatleastonenode,whosepreorder,infixorderandpostorderareallthesame.】2.多选题：下列关于二叉树性质的说法正确的有：（多选）Whichsentencesofthefollowingsarerightaboutabinarytree'scharacterization:（Therearemorethanonecorrectanswers）

选项：

A、非空满二叉树的结点个数一定为奇数个。Theamountofnodesofafullbinarytreewithatleastonenodemustbeodd.

B、非完全二叉树也可以用像完全二叉树那样使用顺序存储结构进行存储。Sequentialstoringstructurecanalsobeusedtostoreanincompletebinarytreejustliketostoreacompletebinarytree.

C、当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。Ifacompletebinarytreeisafullbinarytree,itwillbepossiblethatleafnodesisnotonthenethermostlayer.

D、完全二叉树最多只有最下面的一层结点度数可以小于2。Foracompletebinarytree,onlythedegreesofnodesonthenethermostlayercouldbelessthan2.

E、一棵非空二叉树的为空的外部结点数目等于其结点数加1。Theamountofexternalnullnodesinabinarytreewithatleastonenodeequalstoitsamountofnodesplus1.

F、满二叉树的所有结点的度均为2。Alldegreesofnodesinafullbinarytreeare2.

答案：【非空满二叉树的结点个数一定为奇数个。Theamountofnodesofafullbinarytreewithatleastonenodemustbeodd.;当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。Ifacompletebinarytreeisafullbinarytree,itwillbepossiblethatleafnodesisnotonthenethermostlayer.;一棵非空二叉树的为空的外部结点数目等于其结点数加1。Theamountofexternalnullnodesinabinarytreewithatleastonenodeequalstoitsamountofnodesplus1.】3.一棵有512个结点的完全二叉树的高度为多少？（独根树高度为1）Whatistheheightofacompletebinarytreewith512nodes?(theheightofatreewithonlyarootis1)

答案：【10】4.一棵有510个结点的完全二叉树的高度为多少？（独根树高度为1)Whatistheheightofacompletebinarytreewith510nodes?(theheightofatreewithonlyarootis1)

答案：【9】5.请写出下面这棵二叉树的后序遍历（字母和字母之间不要有空格）Pleasewritedownthepostordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)

答案：【LMXCPKEQHADB】6.请写出下面这棵二叉树的中序遍历（字母和字母之间不要有空格）Pleasewritedowntheinfixordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)

答案：【LXMECKPBQHDA】7.请写出下面这棵二叉树的前序遍历（字母和字母之间不要有空格）Pleasewritedownthepreordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)

答案：【BEXLMKCPDHQA】8.已知一棵树的中序遍历为DBGEACF，后序遍历为DGEBFCA，求这棵树的前序遍历。（字母和字母之间不要有空格）TheinfixordersequenceofatreeisDBGEACF,anditspostordersequenceisDGEBFCA,pleasewritedownitspreordersequence.(Thereisnoblankspacebetweenletters)

答案：【ABDEGCF】9.已知一棵树的前序遍历为ABDEGCF，中序遍历为DBGEACF，求这棵树的后序遍历。（字母和字母之间不要有空格）ThepreordersequenceofatreeisABDEGCF,anditsinfixordersequenceisDBGEACF,pleasewritedownitspostordersequence.(Thereisnoblankspacebetweenletters)

答案：【DGEBFCA】10.在一棵非空二叉树中，若度为0的结点的个数n，度为2的结点个数为m，则有n=________(系统根据字符串匹配来判定答案，所以您的答案中请不要包含空格)Forabinarytreewithatleastonenode,iftherearennodeswithdegree0andmnodeswithdegree2,thenn=________（Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.）

答案：【m+1】第五章二叉树（下）第五章二叉树（下）测验1.多选题：下列关于二叉搜索树的说法正确的有Whichsentencesofthefollowingsarerightaboutbinarysearchtree:

选项：

A、二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。Ifweprintabinarysearchtree'snodesaccordingitsinfixorder,thesequencewillbefromsmalltolarge.

B、如果结点χ的左子树有右子树，则存在某个结点的值介于结点χ的值和χ左儿子的值之间，并且这个结点在$$x$$的左子树之中。Iftheleftchildtreeofanodexhasarightchildtree,thenthereexistssomenodewhosevalueisbetweenthevalueofnodexandthevalueofitsleftchildnode,andthisnodeisontheleftchildtreeofnodex.

C、当根结点没有左儿子时，根结点一定是值最小的结点。Iftherootnodedoesn'thaveleftchild,itmustbethenodewiththesmallestvalue.

D、二叉搜索树一定是满二叉树。Abinarysearchtreemustbeafullbinarytree.

E、二叉搜索树一定是完全二叉树。Abinarysearchtreemustbeacompletebinarytree.

F、从根结点一直沿右儿子向下找不一定能找到树中值最大的结点。Alongtherightchildofnodesallthetimefromtherootnode,itispossiblethatwecouldn'tfindoutthenodewiththelargestvalue.

答案：【二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。Ifweprintabinarysearchtree'snodesaccordingitsinfixorder,thesequencewillbefromsmalltolarge.;如果结点χ的左子树有右子树，则存在某个结点的值介于结点χ的值和χ左儿子的值之间，并且这个结点在$$x$$的左子树之中。Iftheleftchildtreeofanodexhasarightchildtree,thenthereexistssomenodewhosevalueisbetweenthevalueofnodexandthevalueofitsleftchildnode,andthisnodeisontheleftchildtreeofnodex.;当根结点没有左儿子时，根结点一定是值最小的结点。Iftherootnodedoesn'thaveleftchild,itmustbethenodewiththesmallestvalue.】2.多选题：下列关于堆的说法正确的有:Whichsentencesofthefollowingsareright:

选项：

A、堆一定是满二叉树。Aheapmustbeafullbinarytree.

B、最小堆中，最下面一层最靠右的结点一定是权值最大的结点。Inaminimumheap,therightestnodeonthenethermostlayermustbethenodewiththelargestvalue.

C、堆是实现优先队列的惟一方法。Aheapistheonlymethodtoimplementapriorityqueue.

D、堆一定是完全二叉树。Aheapmustbeacompletebinarytree.

E、最小堆中，某个结点左子树中最大的结点可能比右子树中最小的结点小。Inaminimumheap,thelargestvalueonsomenode'sleftchildtreecouldbepossiblysmallerthanthesmallestvalueofitsrightchildtree.

F、使用筛选法建堆要比将元素一个一个插入堆来建堆效率高。Screeningmethodhasahigherefficiencythaninsertingelementsonebyonewhileconstructingaheap.

答案：【堆一定是完全二叉树。Aheapmustbeacompletebinarytree.;最小堆中，某个结点左子树中最大的结点可能比右子树中最小的结点小。Inaminimumheap,thelargestvalueonsomenode'sleftchildtreecouldbepossiblysmallerthanthesmallestvalueofitsrightchildtree.;使用筛选法建堆要比将元素一个一个插入堆来建堆效率高。Screeningmethodhasahigherefficiencythaninsertingelementsonebyonewhileconstructingaheap.】3.多选题：一组包含不同权的字母已经对应好Huffman编码，如果某一个字母对应编码001,下面说法正确的有AgroupofletterswithdifferentweightshascorrespondedwithHuffmancodes,ifaletter'scorrespondingcodeis001,whichsentencesofthefollowingsareright:

选项：

A、以001开头的编码不可能对应其他字母。Acodebeginningwith001couldn'tcorrespondwithotherletters.

B、以000开头的编码不可能对应任何字母。Codesbeginningwith000couldn'tcorrespondwithanyletter.

C、以01开头和1开头的编码肯定对应某个字母。Codesbeginningwith01or1mustcorrespongdingwithsomeletters.

D、建好的Huffman树至少包含4个叶结点。TheHuffmantreecontainsatleast4leafnodes.

E、编码0和00可能对应于其他字母。Code0and00couldcorrespondingwithotherletters.

答案：【以001开头的编码不可能对应其他字母。Acodebeginningwith001couldn'tcorrespondwithotherletters.;以01开头和1开头的编码肯定对应某个字母。Codesbeginningwith01or1mustcorrespongdingwithsomeletters.;建好的Huffman树至少包含4个叶结点。TheHuffmantreecontainsatleast4leafnodes.】4.多选题：下列关于Huffman树和Huffman编码的说法正确的有:WhichsentencesofthefollowingsarerightaboutHuffmantreeandHuffmancode:

选项：

A、Huffman树一定是满二叉树。AHuffmantreemustbeafullbinarytree.

B、Huffman编码是一种前缀编码。Huffmancodeisakindofprefixcode.

C、Huffman树一定是完全二叉树。AHuffmantreemustbeacompletebinarytree.

D、Huffman编码中所有编码都是等长的。AllcodesinaHuffmancodehavethesamelength.

E、对于同样的一组权值两两不同的内容可以得到不同的Huffman编码方案。DifferentcontentwiththesamegroupofweightscangetdifferentHuffmancodes.

F、使用频率越高的字母，Huffman编码越长。Thehigheraletter'sfrequencyis,thelongeritsHuffmancodeis.

答案：【Huffman树一定是满二叉树。AHuffmantreemustbeafullbinarytree.;Huffman编码是一种前缀编码。Huffmancodeisakindofprefixcode.;对于同样的一组权值两两不同的内容可以得到不同的Huffman编码方案。DifferentcontentwiththesamegroupofweightscangetdifferentHuffmancodes.】5.对于如下图所示的最大堆，删除掉最大的元素后，堆的后序遍历结果是Forthefollowingmaximumheap,afterdeletingthemaximumelement,thepostordertraversalsequenceis

答案：【12232428537434835759】6.对于如下图所示的最大堆，删除掉最大的元素后，堆的前序遍历结果是Forthefollowingmaximumheap,afterdeletingthemaximumelement,thepreordertraversalsequenceis请依次写出插入到树中的元素，每两个元素之间用一个空格隔开。Pleasewritedowntheelementssuccessively,andthereisoneblankspacebetweentwoelements.

答案：【59432412233728557483】7.对于关键码序列{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】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.从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码{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】10.从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码{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】11.如果按关键码值递增的顺序依次将n个关键码值插入到二叉搜索树中，如果对这样的二叉搜索树进行检索时，每次检索的字符都等概率的从这n个关键码值中选取，平均比较次数为多少？Ifweinsertnkeyvaluestoabinarysearchtreesuccessivelyfromsmalltolarge,whenwesearchthisbinarysearchtree,eachtimethesearchcharacterisselectedfromthesenkeyvalueswiththesamepossibility,thenhowmanytimeswillthecomparisonbeonaverage?

答案：【(n+1)/2/(1+n)/2】12.请阅读下面一段代码PleasereadthefollowingcodeC++：Python：若此段代码的作用是用来进行后序遍历，那么应该在几号访问点进行访问？（只需要填写数字）ifthiscodeisusedtodoanpostordertraversal,whichvisitingpointshouldbevisited?(Youonlyneedtowritedownthenumber)

答案：【3】13.请阅读下面一段代码PleasereadthefollowingcodeC++：Python：若此段代码的作用是用来进行中序遍历，那么应该在几号访问点进行访问？（只需要填写数字）ifthiscodeisusedtodoaninfixordertraversal,whichvisitingpointshouldbevisited?(Youonlyneedtowritedownthenumber)

答案：【2】14.请阅读下面一段代码PleasereadthefollowingcodeC++：Python：若此段代码的作用是用来进行前序遍历，那么应该在几号访问点进行访问？（只需要填写数字）ifthiscodeisusedtodoapreordertraversal,whichvisitingpointshouldbevisited?(Youonlynee