【MOOC】《數(shù)據(jù)結(jié)構(gòu)與算法》(北京大學(xué))章節(jié)期末中國大學(xué)慕課答案

【MOOC】《數(shù)據(jù)結(jié)構(gòu)與算法》(北京大學(xué))章節(jié)期末中國大學(xué)慕課答案

有些題目順序不一致，下載后按鍵盤ctrl+F進(jìn)行搜索第一章概論第一章概論測(cè)驗(yàn)1.單選題：以下哪種結(jié)構(gòu)是邏輯結(jié)構(gòu)，而與存儲(chǔ)和運(yùn)算無關(guān)：Whichofthefollowingstructureisalogicalstructureregardlessofthestorageoralgorithm:（Thereisonlyonecorrectanswer）

選項(xiàng)：

A、隊(duì)列(queue)

B、雙鏈表(doublylinkedlist)

C、數(shù)組(array)

D、順序表(Sequentiallist)

答案：【隊(duì)列(queue)】2.單選題：下列不屬于線性結(jié)構(gòu)的是：Whichoneofthefollowingsdoesnotbelongtolinearstructure:（Thereisonlyonecorrectanswer）

選項(xiàng)：

A、隊(duì)列(queue)

B、散列表(hashtable)

C、向量(vector)

D、圖(graph)

答案：【圖(graph)】3.多選題：關(guān)于算法特性描述正確的有：Whichoneisrightaboutalgorithm’scharacterization:（therearemorethanonecorrectanswers）

選項(xiàng)：

A、算法保證計(jì)算結(jié)果的正確性。Algorithmwillensurethecorrectnessofthecalculationresults.

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

C、算法描述中下一步執(zhí)行的步驟不確定。Thenextstepintheimplementationofthealgorithmdescribedisuncertain.

D、算法的有窮性指算法必須在有限步驟內(nèi)結(jié)束。Thefinitenatureofalgorithmsmeansalgorithmmustbecompletedwithinalimitedstep.

答案：【算法保證計(jì)算結(jié)果的正確性。Algorithmwillensurethecorrectnessofthecalculationresults.;算法的有窮性指算法必須在有限步驟內(nèi)結(jié)束。Thefinitenatureofalgorithmsmeansalgorithmmustbecompletedwithinalimitedstep.】4.多選題：已知一個(gè)數(shù)組a的長度為n，求問下面這段代碼的時(shí)間復(fù)雜度:Anarrayofa,itslengthisknownasn.Pleaseanswerthetimecomplexityofthefollowingcode.（Therearemorethanoneanswers.）for(i=0,length=1;i<p=""><>for(j=i+1;jif(length<p=""><>length=j-i+1;}

選項(xiàng)：

A、

B、

C、

D、

答案：【;】5.多選題：下列說法正確的是：Whichoptionsmaybecorrect?（therearemorethanonecorrectanswers）

選項(xiàng)：

A、如果函數(shù)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、如果函數(shù)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、函數(shù)f(n)是O(g(n))，當(dāng)常數(shù)a足夠大時(shí)，一定有函數(shù)g(n)是O(af(n))【iff(n)是O(g(n))，Whenconstantaisbigenough，theremustbeg(n)isO(af(n))】

答案：【如果函數(shù)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))】;如果函數(shù)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.計(jì)算運(yùn)行下列程序段后m的值：Calculatethevalueofmafterrunningthefollowingprogramsegmentn=9;m=0;for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m=m+1;求m的值

答案：【20】7.由大到小寫出以下時(shí)間復(fù)雜度的序列：答案直接寫標(biāo)號(hào)，如：(1)(2)(3)(4)(5)（提示：系統(tǒng)基于字符匹配來判定答案，所以您的答案中不要出現(xiàn)空格）Writethefollowingtimecomplexityindescendingsequence:Writedowntheanswerlabelssuchas(1)(2)(3)(4)(5).（Hint：Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.）

答案：【(5)(1)(2)(4)(3)】第二章線性表第二章線性表測(cè)驗(yàn)1.多選題：完成在雙循環(huán)鏈表結(jié)點(diǎn)p之后插入s的操作為：Theoperationtoinsertsafterthedoublycircularlinkedlist’snodepis:(Therearemorethanoneanswers.)

選項(xiàng)：

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）

選項(xiàng)：

A、線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間與i的數(shù)值無關(guān)。Whenthelinearliststoredinlinkedform,thetimetofindthei-thelementisregardlessofthevalueofi.

B、線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間與i的數(shù)值成正比。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisproportionaltovaluewithi.

C、線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間與i的數(shù)值無關(guān)。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisregardlessofthevalueofi.

D、線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，插入第i個(gè)元素的時(shí)間與i的數(shù)值成正比。Whenlinearlistsstoredinthelinkedform,thetimetoinsertthei-thelementisproportionaltovaluewithi.

答案：【線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間與i的數(shù)值無關(guān)。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisregardlessofthevalueofi.;線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，插入第i個(gè)元素的時(shí)間與i的數(shù)值成正比。Whenlinearlistsstoredinthelinkedform,thetimetoinsertthei-thelementisproportionaltovaluewithi.】3.多選題：下面關(guān)于線性表的敘述中，正確的是哪些？Whichofthefollowingsaboutlinearlistarecorrect?（Therearemorethanoneanswers.）Selecttheanswerthatmatches

選項(xiàng)：

A、線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。Linearlistsusesequentialstoragewhichmustoccupyacontinuousmemoryunits.

B、線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。Linearlistsusingsequentialstorage,itiseasytodoinsertanddeleteoperations.

C、線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。Linearlistsusingthelinkedstorage,donotoccupyacontinuousmemoryunits.

D、線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。Linearlistsusingthelinkedstorage,itiseasyforinsertanddeletingoperations.

答案：【線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。Linearlistsusesequentialstoragewhichmustoccupyacontinuousmemoryunits.;線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。Linearlistsusingthelinkedstorage,donotoccupyacontinuousmemoryunits.;線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。Linearlistsusingthelinkedstorage,itiseasyforinsertanddeletingoperations.】4.設(shè)某循環(huán)鏈表長度為n，并設(shè)其中一節(jié)點(diǎn)為p1，然后按照鏈表的順序?qū)⒑竺娴墓?jié)點(diǎn)依次命名為p2,p3,...,pn，那么請(qǐng)問pn.next=____(答案為一個(gè)節(jié)點(diǎn)名，注意所有字母為小寫且答案中不包含空格)

答案：【p1】5.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(___),在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(___)。（請(qǐng)依次填入,格式為(a)(b),如果您的答案中出現(xiàn)字母，請(qǐng)使用小寫;后一空系統(tǒng)基于字符匹配來判定答案，所以您的答案中不要出現(xiàn)空格）Forasinglelinkedlistwithnnodes,andafteraknownnode*ptoinsertanewnode,thetimecomplexityisO(___);afteragivennodewithxvalueinsertanewnode,thetimecomplexityisO(___).(Ifyouranswercontainsletters,uselowercaseone.Thesecondblankisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.)

答案：【(1)(n)】第三章棧與隊(duì)列第三章棧與隊(duì)列測(cè)驗(yàn)1.單選題：現(xiàn)有中綴表達(dá)式E=((100-4)/3+3*(36-7))*2。以下哪個(gè)是與E等價(jià)的后綴表達(dá)式？ExistinginfixexpressionE=((100-4)/3+3*(36-7))*2.WhichofthefollowingistheequivalentpostfixexpressionofE?（Thereisonlyonecorrectanswer）

選項(xiàng)：

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.單選題：設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2，e4，e3，e6，e5，e1則棧S的容量至少應(yīng)該是_____________。AssumethatthestackSandqueueQ’sinitialstateisempty,theelementse1,e2,e3,e4,e5ande6followedthroughstackS,anelementoutthestackmeansintothequeueQ.Ifthesequencethesixelementsoutofthequeueise2,e4,e3,e6,e5,e1thenstackSofcapacityshouldbeatleast_____________.（Thereisonlyonecorrectanswer）

選項(xiàng)：

A、2

B、3

C、4

D、6

答案：【3】3.多選題：以下循環(huán)隊(duì)列的實(shí)現(xiàn)方式中，長度為n的隊(duì)列，所能容納的元素個(gè)數(shù)也為n的有:Inthefollowingrealizingwaysofcircularqueue,thequeuewhoselengthisncanalsocontainthenumberofnelementsis:（Therearemorethanoneanswers.）

選項(xiàng)：

A、只用front和rear兩個(gè)指針標(biāo)記隊(duì)列的頭和尾，兩個(gè)指針均為實(shí)指Onlyusefrontandrearasthequeue’sheadandtailpointersandthetwopointersareactuallyreferringto.

B、用front和rear兩個(gè)指針標(biāo)記隊(duì)列的頭和尾，并用整型變量len記錄隊(duì)列元素?cái)?shù)Withthequeue’sheadandtailpointersmarkedasfrontandrear,usetheintegervariablelentorecordthenumberofelements.

C、用front和rear兩個(gè)指針標(biāo)記隊(duì)列的頭和尾，并用布爾型變量empty記錄隊(duì)列是否為空Withthequeue’sheadandtailpointersmarkedasfrontandrear,useBooleanvariableemptyrecordwhetherthequeueisempty.

D、只用front和rear兩個(gè)指針標(biāo)記隊(duì)列的頭和尾，兩個(gè)指針均為虛指Onlyusefrontandrearasthequeue’sheadandtailpointersandthetwopointersarevirtuallyreferringto.

答案：【用front和rear兩個(gè)指針標(biāo)記隊(duì)列的頭和尾，并用整型變量len記錄隊(duì)列元素?cái)?shù)Withthequeue’sheadandtailpointersmarkedasfrontandrear,usetheintegervariablelentorecordthenumberofelements.;用front和rear兩個(gè)指針標(biāo)記隊(duì)列的頭和尾，并用布爾型變量empty記錄隊(duì)列是否為空Withthequeue’sheadandtailpointersmarkedasfrontandrear,useBooleanvariableemptyrecordwhetherthequeueisempty.】4.多選題：隊(duì)列的特點(diǎn)包括：Queue’featuresinclude:（Therearemorethanoneanswers.）

選項(xiàng)：

A、后進(jìn)先出Last-infirst-out(LIFO)

B、先進(jìn)后出First-inlast-out(FILO)

C、先進(jìn)先出First-infirst-out(FIFO)

D、后進(jìn)后出Last-inlast-out(LILO)

答案：【先進(jìn)先出First-infirst-out(FIFO);后進(jìn)后出Last-inlast-out(LILO)】5.雙端隊(duì)列可以在隊(duì)列的兩端進(jìn)行插入和刪除操作，既可在隊(duì)尾進(jìn)行插入/刪除，又可在隊(duì)頭進(jìn)行插入/刪除?，F(xiàn)有4個(gè)不同的元素順序輸入到雙端隊(duì)列，那么可以得到_____種不同的排列。double-endedqueuecaninsertanddeleteoperationsonbothendsofthequeue.Thatitcaninsert/deleteatitstail,butalsoatthehead.Existing4differentelementssequentiallyinputtothedouble-endedqueue,youcanget_____differentpermutations.

答案：【8】6.編號(hào)為1，2，3，4的四輛列車，順序開進(jìn)一個(gè)棧式結(jié)構(gòu)的站臺(tái)；則開出車站的順序有______種可能。注釋：例如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】第四章字符串第四章字符串測(cè)驗(yàn)1.單選題：Seekthestring"BAAABBBAA"‘sfeaturevector,wherethefeaturevectorisdefinedasfollows:（Thereisonlyonecorrectanswer）

選項(xiàng)：

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.單選題：下面關(guān)于串的的敘述中，哪一個(gè)是不正確的:（單選）Whichofthefollowingdescriptionsaboutstringisnotcorrect?（Thereisonlyonecorrectanswer）

選項(xiàng)：

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

B、模式匹配是串的一種重要運(yùn)算Patternmatchingisanimportantoperation.

C、串是一種數(shù)據(jù)對(duì)象和操作都特殊的線性表Stringisalinearlistwhosedataobjectsandoperationsbothspecial

D、空串是由空格構(gòu)成的串Emptystringisastringconsistingofspaces.

答案：【空串是由空格構(gòu)成的串Emptystringisastringconsistingofspaces.】3.單選題：若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,執(zhí)行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))注意：substr(S,i,j)是對(duì)字符串S的下標(biāo)為i開始取j個(gè)字符，這里的下標(biāo)是從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）

選項(xiàng)：

A、ABC###G0123

B、ABCD###2345

C、ABCD###1234

D、ABC###G2345

答案：【ABCD###1234】4.單選題：下列說法正確的是：（單選）Whichofthefollowingstatementsiscorrect?（Thereisonlyonecorrectanswer）

選項(xiàng)：

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

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

C、串只可以采用順序存儲(chǔ)，不可以采用鏈?zhǔn)酱鎯?chǔ)Stringonlycanbestoredinsequentialmethodandcannotbestoredinlinkedmethod.

D、在C++標(biāo)準(zhǔn)中，charS[M]最多能表示長度為M的字符串InC++standards,charS[M]canrepresentuptoastringoflengthM.

答案：【空串是任意字符串的子串Emptystringisasubstringofarbitrarystring.】5.單選題：設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為()（單選）Therearetwostringspq,qisp’ssubstring.Thealgorithmtosearchthefirsttimeqappearedinpiscalled()（Thereisonlyonecorrectanswer）

選項(xiàng)：

A、求子串Seekingsubstring

B、聯(lián)接Concatenation

C、匹配Matching

D、求串長Seekinglength

答案：【匹配Matching】6.多選題：在字符{A,C,G,T}組成的DNA序列中，A和T、C和G是互補(bǔ)對(duì)。判斷一個(gè)DNA序列中是否存在互補(bǔ)回文串（例如，ATCATGAT的補(bǔ)串是TAGTACTA，與原串形成互補(bǔ)回文串）。下面DNA序列中存在互補(bǔ)回文串的是：（多選）IntheDNAsequencesconsistingofcharacter{A,C,G,T},AandT,CandGarecomplementarypairs.JudgingwhetherthereisacomplementarypalindromesequenceinaDNAsequence(e.g.,ATCATGAT’scomplementstringsisTAGTACTA,itiscomplementarypalindromesequencewiththeoriginalsequence).WhichofthefollowingDNAsequenceshavecomplementarypalindromestring?（Therearemorethanoneanswers.）

選項(xiàng)：

A、CTGATCAG

B、AATTAATT

C、TGCAACGT

D、CATGGTAC

E、GTACGTAC

F、AGCTAGCT

答案：【CTGATCAG;AATTAATT;GTACGTAC;AGCTAGCT】7.上一題中的字符串"BAAABBBAA"，與目標(biāo)"BAAABBBCDDDCCHHHHBBBAAABBBAADD"進(jìn)行匹配，至少需要多少次字符匹配（提示：利用優(yōu)化后的Next數(shù)組):Thestringinquestionabove"BAAABBBAA"matcheswith"BAAABBBCDDDCCHHHHBBBAAABBBAADD".Howmanytimescharactermatchingwillneedatleast?(Hint:Use“Next”arrays):

答案：【31】8.下列程序判斷字符串s是否對(duì)稱，對(duì)稱則返回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)三個(gè)答案之間用空格分隔，每個(gè)答案是一個(gè)字符,不要加空格

答案：【jij】9.S=“S1S2…Sn”是一個(gè)長為n的字符串，存放在一個(gè)數(shù)組中，編程序?qū)改造之后輸出。S="S1S2...Sn"isastringoflengthn,andstoredinanarray,outputSafteritsprogrammabletransformation.1.將S的所有第偶數(shù)個(gè)字符按照其原來的下標(biāo)從大到小的次序放在S的后半部分；1.Alltheeven-numberedcharactersofSshouldbeplacedinaccordancewiththeirsubscriptdescendingorderinthesecondhalfofS;2.將S的所有第奇數(shù)個(gè)字符按照其原來的下標(biāo)從小到大的次序放在S的前半部分；2.Alltheodd-numberedcharactersofSshouldbeplacedinaccordancewiththeirsubscriptascendingorderinthefirsthalfofS.例如：S=‘ABCDEFGHIJKL’，則改造后的S為‘ACEGIKLJHFDB’。則S=’algorithm’,改造后為____________（Hint：1.答案不需要加引號(hào)2.系統(tǒng)基于字符匹配來判定答案，所以您的答案中不要出現(xiàn)空格）。Forexample:S='ABCDEFGHIJKL',thenafterthetransformationSis'ACEGIKLJHFDB'.IfS='algorithm',thenafterthetransformationSis____________(Hint:1.pleasedon’tincludeanyquotesinyouranswer.2.Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks).

答案：【agrtmhiol】10.一個(gè)文本串可用事先給定的字母映射表進(jìn)行加密。例如，設(shè)字母映射表為：Atextstringcanbeencryptedbythegivenlettersmappingtable.Forexample,thelettersmappingtableis:比如字符串"encrypt"被加密為"tkzwsdf"。則字符串“algorithm”，被加密為________________（Hint：1.答案不需要加引號(hào)2.系統(tǒng)基于字符匹配來判定答案，所以您的答案中不要出現(xiàn)空格）。Asthestring"encrypt"isencryptedas"tkzwsdf",thenthe"algorithm"isencryptedas________(Hint：1.pleasedon’tincludeanyquotesinyouranswer2.Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.).

答案：【neopwmfbl】11.設(shè)有字符串變量StringA＝“”，B＝“MULE”，C＝“OLD”，D＝“MY”;請(qǐng)計(jì)算下列表達(dá)式（3個(gè)答案本身不要出現(xiàn)空格，答案之間用空格分開）AssumethatthereisastringvariableStringA="",B="MULE",C="OLD",D="MY";Pleasecalculatethefollowingexpression:(1)D+C+B(2)B.substr(3，2)(3)A.strlength()

答案：【MYOLDMULEE0】12.若字符串s=”algorithm”，則其子串個(gè)數(shù)為：Ifthestrings="algorithm",thenthenumberofitssub-stringis:

答案：【46】13.若字符串s=“software”，則其子串個(gè)數(shù)為：Ifthestrings="software",thenthenumberofitssub-stringis:

答案：【37】第五章二叉樹（上）第五章二叉樹（上）測(cè)驗(yàn)1.多選題：下列關(guān)于二叉樹遍歷的說法正確的有:Whichsentencesofthefollowingsarerightabouttraversalofabinarytree:

選項(xiàng)：

A、前序和中序遍歷的順序恰好一樣的二叉樹，只能是空二叉樹或者獨(dú)根二叉樹這兩種情況。Onlythesequencesofpreorderandinfixorderofthebinarytreewithnonodesoronlyonenodearethesame.

B、所有結(jié)點(diǎn)左子樹為空的二叉樹的前序和中序遍歷順序恰好一樣。Thesequencesofpreorderandinfixorderofabinarytreewithallnodeswithoutleftchildtreearethesame.

C、所有結(jié)點(diǎn)右子樹為空的二叉樹的前序和中序遍歷順序恰好一樣。Thesequencesofpreorderandinfixorderofabinarytreewithallnodeswithoutrightchildtreearethesame.

D、只有空二叉樹和一個(gè)根結(jié)點(diǎn)的二叉樹這兩種二叉樹的前序和后序遍歷的順序恰好一樣。Onlythesequencesofpreorderandpostorderofthebinarytreewithnonodesoronlyonenodearethesame.

E、所有結(jié)點(diǎn)左子樹為空的二叉樹的前序和后序遍歷順序恰好一樣。Thesequencesofpreorderandpostorderofabinarytreewithallnodeswithoutleftchildtreearethesame.

F、所有結(jié)點(diǎn)右子樹為空的二叉樹的前序和后序遍歷順序恰好一樣。Thesequencesofpreorderandpostorderofabinarytreewithallnodeswithoutleftchildtreearethesame.

G、只有空二叉樹和一個(gè)根結(jié)點(diǎn)的二叉樹這兩種二叉樹的中序和后序遍歷的順序恰好一樣。Onlythesequencesofinfixorderandpostorderofthebinarytreewithnonodesoronlyonenodearethesame.

H、所有結(jié)點(diǎn)左子樹為空的二叉樹的中序和后序遍歷順序恰好一樣。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutleftchildtreearethesame.

I、所有結(jié)點(diǎn)右子樹為空的二叉樹的中序和后序遍歷順序恰好一樣。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutrightchildtreearethesame.

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

答案：【所有結(jié)點(diǎn)左子樹為空的二叉樹的前序和中序遍歷順序恰好一樣。Thesequencesofpreorderandinfixorderofabinarytreewithallnodeswithoutleftchildtreearethesame.;只有空二叉樹和一個(gè)根結(jié)點(diǎn)的二叉樹這兩種二叉樹的前序和后序遍歷的順序恰好一樣。Onlythesequencesofpreorderandpostorderofthebinarytreewithnonodesoronlyonenodearethesame.;所有結(jié)點(diǎn)右子樹為空的二叉樹的中序和后序遍歷順序恰好一樣。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutrightchildtreearethesame.;存在一棵非空二叉樹，它的前序、中序和后序遍歷都是一樣的。Thereexistsabinarytreewithatleastonenode,whosepreorder,infixorderandpostorderareallthesame.】2.多選題：下列關(guān)于二叉樹性質(zhì)的說法正確的有：（多選）Whichsentencesofthefollowingsarerightaboutabinarytree'scharacterization:（Therearemorethanonecorrectanswers）

選項(xiàng)：

A、非空滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)一定為奇數(shù)個(gè)。Theamountofnodesofafullbinarytreewithatleastonenodemustbeodd.

B、非完全二叉樹也可以用像完全二叉樹那樣使用順序存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)。Sequentialstoringstructurecanalsobeusedtostoreanincompletebinarytreejustliketostoreacompletebinarytree.

C、當(dāng)一棵完全二叉樹是滿二叉樹時(shí)，葉子結(jié)點(diǎn)不一定集中在最下面一層。Ifacompletebinarytreeisafullbinarytree,itwillbepossiblethatleafnodesisnotonthenethermostlayer.

D、完全二叉樹最多只有最下面的一層結(jié)點(diǎn)度數(shù)可以小于2。Foracompletebinarytree,onlythedegreesofnodesonthenethermostlayercouldbelessthan2.

E、一棵非空二叉樹的為空的外部結(jié)點(diǎn)數(shù)目等于其結(jié)點(diǎn)數(shù)加1。Theamountofexternalnullnodesinabinarytreewithatleastonenodeequalstoitsamountofnodesplus1.

F、滿二叉樹的所有結(jié)點(diǎn)的度均為2。Alldegreesofnodesinafullbinarytreeare2.

答案：【非空滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)一定為奇數(shù)個(gè)。Theamountofnodesofafullbinarytreewithatleastonenodemustbeodd.;當(dāng)一棵完全二叉樹是滿二叉樹時(shí)，葉子結(jié)點(diǎn)不一定集中在最下面一層。Ifacompletebinarytreeisafullbinarytree,itwillbepossiblethatleafnodesisnotonthenethermostlayer.;一棵非空二叉樹的為空的外部結(jié)點(diǎn)數(shù)目等于其結(jié)點(diǎn)數(shù)加1。Theamountofexternalnullnodesinabinarytreewithatleastonenodeequalstoitsamountofnodesplus1.】3.一棵有512個(gè)結(jié)點(diǎn)的完全二叉樹的高度為多少？（獨(dú)根樹高度為1）Whatistheheightofacompletebinarytreewith512nodes?(theheightofatreewithonlyarootis1)

答案：【10】4.一棵有510個(gè)結(jié)點(diǎn)的完全二叉樹的高度為多少？（獨(dú)根樹高度為1)Whatistheheightofacompletebinarytreewith510nodes?(theheightofatreewithonlyarootis1)

答案：【9】5.請(qǐng)寫出下面這棵二叉樹的后序遍歷（字母和字母之間不要有空格）Pleasewritedownthepostordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)

答案：【LMXCPKEQHADB】6.請(qǐng)寫出下面這棵二叉樹的中序遍歷（字母和字母之間不要有空格）Pleasewritedowntheinfixordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)

答案：【LXMECKPBQHDA】7.請(qǐng)寫出下面這棵二叉樹的前序遍歷（字母和字母之間不要有空格）Pleasewritedownthepreordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)

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

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

答案：【DGEBFCA】10.在一棵非空二叉樹中，若度為0的結(jié)點(diǎn)的個(gè)數(shù)n，度為2的結(jié)點(diǎn)個(gè)數(shù)為m，則有n=________(系統(tǒng)根據(jù)字符串匹配來判定答案，所以您的答案中請(qǐng)不要包含空格)Forabinarytreewithatleastonenode,iftherearennodeswithdegree0andmnodeswithdegree2,thenn=________（Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.）

答案：【m+1】第五章二叉樹（下）第五章二叉樹（下）測(cè)驗(yàn)1.多選題：下列關(guān)于二叉搜索樹的說法正確的有Whichsentencesofthefollowingsarerightaboutbinarysearchtree:

選項(xiàng)：

A、二叉搜索樹按照中序遍歷將各結(jié)點(diǎn)打印出將各結(jié)點(diǎn)打印出來，將得到按照由小到大的排列。Ifweprintabinarysearchtree'snodesaccordingitsinfixorder,thesequencewillbefromsmalltolarge.

B、如果結(jié)點(diǎn)χ的左子樹有右子樹，則存在某個(gè)結(jié)點(diǎn)的值介于結(jié)點(diǎn)χ的值和χ左兒子的值之間，并且這個(gè)結(jié)點(diǎn)在$$x$$的左子樹之中。Iftheleftchildtreeofanodexhasarightchildtree,thenthereexistssomenodewhosevalueisbetweenthevalueofnodexandthevalueofitsleftchildnode,andthisnodeisontheleftchildtreeofnodex.

C、當(dāng)根結(jié)點(diǎn)沒有左兒子時(shí)，根結(jié)點(diǎn)一定是值最小的結(jié)點(diǎn)。Iftherootnodedoesn'thaveleftchild,itmustbethenodewiththesmallestvalue.

D、二叉搜索樹一定是滿二叉樹。Abinarysearchtreemustbeafullbinarytree.

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

F、從根結(jié)點(diǎn)一直沿右兒子向下找不一定能找到樹中值最大的結(jié)點(diǎn)。Alongtherightchildofnodesallthetimefromtherootnode,itispossiblethatwecouldn'tfindoutthenodewiththelargestvalue.

答案：【二叉搜索樹按照中序遍歷將各結(jié)點(diǎn)打印出將各結(jié)點(diǎn)打印出來，將得到按照由小到大的排列。Ifweprintabinarysearchtree'snodesaccordingitsinfixorder,thesequencewillbefromsmalltolarge.;如果結(jié)點(diǎn)χ的左子樹有右子樹，則存在某個(gè)結(jié)點(diǎn)的值介于結(jié)點(diǎn)χ的值和χ左兒子的值之間，并且這個(gè)結(jié)點(diǎn)在$$x$$的左子樹之中。Iftheleftchildtreeofanodexhasarightchildtree,thenthereexistssomenodewhosevalueisbetweenthevalueofnodexandthevalueofitsleftchildnode,andthisnodeisontheleftchildtreeofnodex.;當(dāng)根結(jié)點(diǎn)沒有左兒子時(shí)，根結(jié)點(diǎn)一定是值最小的結(jié)點(diǎn)。Iftherootnodedoesn'thaveleftchild,itmustbethenodewiththesmallestvalue.】2.多選題：下列關(guān)于堆的說法正確的有:Whichsentencesofthefollowingsareright:

選項(xiàng)：

A、堆一定是滿二叉樹。Aheapmustbeafullbinarytree.

B、最小堆中，最下面一層最靠右的結(jié)點(diǎn)一定是權(quán)值最大的結(jié)點(diǎn)。Inaminimumheap,therightestnodeonthenethermostlayermustbethenodewiththelargestvalue.

C、堆是實(shí)現(xiàn)優(yōu)先隊(duì)列的惟一方法。Aheapistheonlymethodtoimplementapriorityqueue.

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

E、最小堆中，某個(gè)結(jié)點(diǎn)左子樹中最大的結(jié)點(diǎn)可能比右子樹中最小的結(jié)點(diǎn)小。Inaminimumheap,thelargestvalueonsomenode'sleftchildtreecouldbepossiblysmallerthanthesmallestvalueofitsrightchildtree.

F、使用篩選法建堆要比將元素一個(gè)一個(gè)插入堆來建堆效率高。Screeningmethodhasahigherefficiencythaninsertingelementsonebyonewhileconstructingaheap.

答案：【堆一定是完全二叉樹。Aheapmustbeacompletebinarytree.;最小堆中，某個(gè)結(jié)點(diǎn)左子樹中最大的結(jié)點(diǎn)可能比右子樹中最小的結(jié)點(diǎn)小。Inaminimumheap,thelargestvalueonsomenode'sleftchildtreecouldbepossiblysmallerthanthesmallestvalueofitsrightchildtree.;使用篩選法建堆要比將元素一個(gè)一個(gè)插入堆來建堆效率高。Screeningmethodhasahigherefficiencythaninsertingelementsonebyonewhileconstructingaheap.】3.多選題：一組包含不同權(quán)的字母已經(jīng)對(duì)應(yīng)好Huffman編碼，如果某一個(gè)字母對(duì)應(yīng)編碼001,下面說法正確的有AgroupofletterswithdifferentweightshascorrespondedwithHuffmancodes,ifaletter'scorrespondingcodeis001,whichsentencesofthefollowingsareright:

選項(xiàng)：

A、以001開頭的編碼不可能對(duì)應(yīng)其他字母。Acodebeginningwith001couldn'tcorrespondwithotherletters.

B、以000開頭的編碼不可能對(duì)應(yīng)任何字母。Codesbeginningwith000couldn'tcorrespondwithanyletter.

C、以01開頭和1開頭的編碼肯定對(duì)應(yīng)某個(gè)字母。Codesbeginningwith01or1mustcorrespongdingwithsomeletters.

D、建好的Huffman樹至少包含4個(gè)葉結(jié)點(diǎn)。TheHuffmantreecontainsatleast4leafnodes.

E、編碼0和00可能對(duì)應(yīng)于其他字母。Code0and00couldcorrespondingwithotherletters.

答案：【以001開頭的編碼不可能對(duì)應(yīng)其他字母。Acodebeginningwith001couldn'tcorrespondwithotherletters.;以01開頭和1開頭的編碼肯定對(duì)應(yīng)某個(gè)字母。Codesbeginningwith01or1mustcorrespongdingwithsomeletters.;建好的Huffman樹至少包含4個(gè)葉結(jié)點(diǎn)。TheHuffmantreecontainsatleast4leafnodes.】4.多選題：下列關(guān)于Huffman樹和Huffman編碼的說法正確的有:WhichsentencesofthefollowingsarerightaboutHuffmantreeandHuffmancode:

選項(xiàng)：

A、Huffman樹一定是滿二叉樹。AHuffmantreemustbeafullbinarytree.

B、Huffman編碼是一種前綴編碼。Huffmancodeisakindofprefixcode.

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

D、Huffman編碼中所有編碼都是等長的。AllcodesinaHuffmancodehavethesamelength.

E、對(duì)于同樣的一組權(quán)值兩兩不同的內(nèi)容可以得到不同的Huffman編碼方案。DifferentcontentwiththesamegroupofweightscangetdifferentHuffmancodes.

F、使用頻率越高的字母，Huffman編碼越長。Thehigheraletter'sfrequencyis,thelongeritsHuffmancodeis.

答案：【Huffman樹一定是滿二叉樹。AHuffmantreemustbeafullbinarytree.;Huffman編碼是一種前綴編碼。Huffmancodeisakindofprefixcode.;對(duì)于同樣的一組權(quán)值兩兩不同的內(nèi)容可以得到不同的Huffman編碼方案。DifferentcontentwiththesamegroupofweightscangetdifferentHuffmancodes.】5.對(duì)于如下圖所示的最大堆，刪除掉最大的元素后，堆的后序遍歷結(jié)果是Forthefollowingmaximumheap,afterdeletingthemaximumelement,thepostordertraversalsequenceis

答案：【12232428537434835759】6.對(duì)于如下圖所示的最大堆，刪除掉最大的元素后，堆的前序遍歷結(jié)果是Forthefollowingmaximumheap,afterdeletingthemaximumelement,thepreordertraversalsequenceis請(qǐng)依次寫出插入到樹中的元素，每?jī)蓚€(gè)元素之間用一個(gè)空格隔開。Pleasewritedowntheelementssuccessively,andthereisoneblankspacebetweentwoelements.

答案：【59432412233728557483】7.對(duì)于關(guān)鍵碼序列{38，64，52，15，73，40，48，55，26，12}，用篩選法建最小值堆，若一旦發(fā)現(xiàn)逆序?qū)瓦M(jìn)行交換，共需要交換元素多少次？Forthekeyvaluesequence{38，64，52，15，73，40，48，55，26，12},usethescreeningmethodtoconstuctaminimumheap,ifweexchangethemwhenwefindreversedorder,thenhowmanytimesshouldweexchangethem?

答案：【6】8.從空二叉樹開始，嚴(yán)格按照二叉搜索樹的插入算法（不進(jìn)行旋轉(zhuǎn)平衡），逐個(gè)插入關(guān)鍵碼構(gòu)造出一棵二叉樹，以怎樣的順序插入關(guān)鍵碼集合{14，32，47，6，9，12，78，63，29，81}可以使得樹的深度最??？請(qǐng)依次寫出插入到樹中的元素，每?jī)蓚€(gè)元素之間用一個(gè)空格隔開。如果有多組滿足要求的方案，請(qǐng)使得你的答案中先插入的元素盡可能的小。Fromanullbinarytree,insertkeyvaluessuccessivelyaccordingtotheinsertionalgorithmofabinarysearchtreestrictly(norotationandbalance)toconstructabinarysearchtree.Whatistheinsertionsequencethatcouldmakethetreehaveasmallestdepthwithakeyvalueset{14，32，47，6，9，12，78，63，29，81}?Pleasewritedowntheelementssuccessively,andthereisoneblankspacebetweentwoelements.Iftherearemorethanoneanswerthatmeetthecondition,pleasemaketheelementwhichneedstobeinsertedfirstassmallaspossibleinyouranswer.

答案：【126947291432786381】9.從空二叉樹開始，嚴(yán)格按照二叉搜索樹的插入算法（不進(jìn)行旋轉(zhuǎn)平衡），逐個(gè)插入關(guān)鍵碼{18,73,10,5,68,99,27,41,51,32,25}構(gòu)造出一棵二叉搜索樹，對(duì)該二叉搜索樹按照后序遍歷得到的序列為？（答案中每?jī)蓚€(gè)元素之間用一個(gè)空格隔開）Fromanullbinarytree,insertkeyvalues{18,73,10,5,68,99,27,41,51,32,25}successivelyaccordingtotheinsertionalgorithmofabinarysearchtreestrictly(norotationandbalance)toconstructabinarysearchtree.Pleasewritedownthesequenceofpostorderofthisbinarysearchtree.(Thereisoneblankspacebetweentwoelements)

答案：【510253251412768997318】10.從空二叉樹開始，嚴(yán)格按照二叉搜索樹的插入算法（不進(jìn)行旋轉(zhuǎn)平衡），逐個(gè)插入關(guān)鍵碼{18,73,10,5,68,99,27,41,51,32,25}構(gòu)造出一棵二叉搜索樹，對(duì)該二叉搜索樹按照前序遍歷得到的序列為？（答案中每?jī)蓚€(gè)元素之間用一個(gè)空格隔開）Fromanullbinarytree,insertkeyvalues{18,73,10,5,68,99,27,41,51,32,25}successivelyaccordingtotheinsertionalgorithmofabinarysearchtreestrictly(norotationandbalance)toconstructabinarysearchtree.Pleasewritedownthesequenceofpreorderofthisbinarysearchtree.(Thereisoneblankspacebetweentwoelements)

答案：【181057368272541325199】11.如果按關(guān)鍵碼值遞增的順序依次將n個(gè)關(guān)鍵碼值插入到二叉搜索樹中，如果對(duì)這樣的二叉搜索樹進(jìn)行檢索時(shí)，每次檢索的字符都等概率的從這n個(gè)關(guān)鍵碼值中選取，平均比較次數(shù)為多少？Ifweinsertnkeyvaluestoabinarysearchtreesuccessivelyfromsmalltolarge,whenwesearchthisbinarysearchtree,eachtimethesearchcharacterisselectedfromthesenkeyvalueswiththesamepossibility,thenhowmanytimeswillthecomparisonbeonaverage?

答案：【(n+1)/2/(1+n)/2】12.請(qǐng)閱讀下面一段代碼PleasereadthefollowingcodeC++：Python：若此段代碼的作用是用來進(jìn)行后序遍歷，那么應(yīng)該在幾號(hào)訪問點(diǎn)進(jìn)行訪問？（只需要填寫數(shù)字）ifthiscodeisusedtodoanpostordertraversal,whichvisitingpointshouldbevisited?(Youonlyneedtowritedownthenumber)

答案：【3】13.請(qǐng)閱讀下面一段代碼PleasereadthefollowingcodeC++：Python：若此段代碼的作用是用來進(jìn)行中序遍歷，那么應(yīng)該在幾號(hào)訪問點(diǎn)進(jìn)行訪問？（只需要填寫數(shù)字）ifthiscodeisusedtodoaninfixordertraversal,whichvisitingpointshouldbevisited?(Youonlyneedtowritedownthenumber)

答案：【2】14.請(qǐng)閱讀下面一段代碼PleasereadthefollowingcodeC++：Python：若此段代碼的作用是用來進(jìn)行前序遍歷，那么應(yīng)該在幾號(hào)訪問點(diǎn)進(jìn)行訪問？（只需要填寫數(shù)字）ifthiscodeisusedtodoapreordertraversal,whichvisitingpointshouldbevisited?(Youonlynee