【MOOC】數(shù)據(jù)結(jié)構(gòu)與算法-北京大學(xué) 中國(guó)大學(xué)慕課MOOC答案

【MOOC】數(shù)據(jù)結(jié)構(gòu)與算法-北京大學(xué)中國(guó)大學(xué)慕課MOOC答案第一章概論測(cè)驗(yàn)1、【單選題】下列不屬于線性結(jié)構(gòu)的是：Whichoneofthefollowingsdoesnotbelongtolinearstructure:（Thereisonlyonecorrectanswer）本題答案：【圖(graph)】2、【單選題】以下哪種結(jié)構(gòu)是邏輯結(jié)構(gòu)，而與存儲(chǔ)和運(yùn)算無(wú)關(guān)：Whichofthefollowingstructureisalogicalstructureregardlessofthestorageoralgorithm:（Thereisonlyonecorrectanswer）本題答案：【隊(duì)列(queue)】3、【多選題】關(guān)于算法特性描述正確的有：Whichoneisrightaboutalgorithm’scharacterization:（therearemorethanonecorrectanswers）本題答案：【算法保證計(jì)算結(jié)果的正確性。Algorithmwillensurethecorrectnessofthecalculationresults.#算法的有窮性指算法必須在有限步驟內(nèi)結(jié)束。Thefinitenatureofalgorithmsmeansalgorithmmustbecompletedwithinalimitedstep.】4、【多選題】下列說(shuō)法正確的是：Whichoptionsmaybecorrect?（therearemorethanonecorrectanswers）本題答案：【如果函數(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))】】5、【多選題】已知一個(gè)數(shù)組a的長(zhǎng)度為n，求問(wèn)下面這段代碼的時(shí)間復(fù)雜度: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、【填空題】計(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、【填空題】由大到小寫(xiě)出以下時(shí)間復(fù)雜度的序列：答案直接寫(xiě)標(biāo)號(hào)，如：(1)(2)(3)(4)(5)（提示：系統(tǒng)基于字符匹配來(lái)判定答案，所以您的答案中不要出現(xiàn)空格）Writethefollowingtimecomplexityindescendingsequence:Writedowntheanswerlabelssuchas(1)(2)(3)(4)(5).（Hint：Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.）本題答案：【(5)(1)(2)(4)(3)】第二章線性表測(cè)驗(yàn)1、【多選題】下面關(guān)于線性表的敘述中，正確的是哪些？Whichofthefollowingsaboutlinearlistarecorrect?（Therearemorethanoneanswers.）Selecttheanswerthatmatches本題答案：【線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。Linearlistsusesequentialstoragewhichmustoccupyacontinuousmemoryunits.#線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。Linearlistsusingthelinkedstorage,donotoccupyacontinuousmemoryunits.#線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。Linearlistsusingthelinkedstorage,itiseasyforinsertanddeletingoperations.】2、【多選題】下面的敘述中正確的是：Selecttheanswerthatmatches（Therearemorethanonecorrectanswers）本題答案：【線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間與i的數(shù)值無(wú)關(guān)。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisregardlessofthevalueofi.#線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，插入第i個(gè)元素的時(shí)間與i的數(shù)值成正比。Whenlinearlistsstoredinthelinkedform,thetimetoinsertthei-thelementisproportionaltovaluewithi.】3、【多選題】完成在雙循環(huán)鏈表結(jié)點(diǎn)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、【填空題】對(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)使用小寫(xiě);后一空系統(tǒng)基于字符匹配來(lái)判定答案，所以您的答案中不要出現(xiàn)空格）Forasinglelinkedlistwithnnodes,andafteraknownnode*ptoinsertanewnode,thetimecomplexityisO(___);afteragivennodewithxvalueinsertanewnode,thetimecomplexityisO(___).(Ifyouranswercontainsletters,uselowercaseone.Thesecondblankisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.)本題答案：【(1)(n)】5、【填空題】設(shè)某循環(huán)鏈表長(zhǎng)度為n，并設(shè)其中一節(jié)點(diǎn)為p1，然后按照鏈表的順序?qū)⒑竺娴墓?jié)點(diǎn)依次命名為p2,p3,...,pn，那么請(qǐng)問(wèn)pn.next=____(答案為一個(gè)節(jié)點(diǎn)名，注意所有字母為小寫(xiě)且答案中不包含空格)本題答案：【p1】第三章棧與隊(duì)列測(cè)驗(yàn)1、【單選題】設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過(guò)棧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）本題答案：【3】2、【單選題】現(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）本題答案：【1004–3/3367–*+2*】3、【多選題】隊(duì)列的特點(diǎn)包括：Queue’featuresinclude:（Therearemorethanoneanswers.）本題答案：【先進(jìn)先出First-infirst-out(FIFO)#后進(jìn)后出Last-inlast-out(LILO)】4、【多選題】以下循環(huán)隊(duì)列的實(shí)現(xiàn)方式中，長(zhǎng)度為n的隊(duì)列，所能容納的元素個(gè)數(shù)也為n的有:Inthefollowingrealizingwaysofcircularqueue,thequeuewhoselengthisncanalsocontainthenumberofnelementsis:（Therearemorethanoneanswers.）本題答案：【用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.】5、【填空題】編號(hào)為1，2，3，4的四輛列車(chē)，順序開(kāi)進(jìn)一個(gè)棧式結(jié)構(gòu)的站臺(tái)；則開(kāi)出車(chē)站的順序有______種可能。注釋：例如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、【填空題】雙端隊(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】第四章字符串測(cè)驗(yàn)1、【單選題】設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為()（單選）Therearetwostringspq,qisp’ssubstring.Thealgorithmtosearchthefirsttimeqappearedinpiscalled()（Thereisonlyonecorrectanswer）本題答案：【匹配Matching】2、【單選題】下列說(shuō)法正確的是：（單選）Whichofthefollowingstatementsiscorrect?（Thereisonlyonecorrectanswer）本題答案：【空串是任意字符串的子串Emptystringisasubstringofarbitrarystring.】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開(kāi)始取j個(gè)字符，這里的下標(biāo)是從0開(kāi)始的(單選)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、【單選題】下面關(guān)于串的的敘述中，哪一個(gè)是不正確的:（單選）Whichofthefollowingdescriptionsaboutstringisnotcorrect?（Thereisonlyonecorrectanswer）本題答案：【空串是由空格構(gòu)成的串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是互補(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.）本題答案：【CTGATCAG#AATTAATT#GTACGTAC#AGCTAGCT】7、【填空題】若字符串s=“software”，則其子串個(gè)數(shù)為：Ifthestrings=software,thenthenumberofitssub-stringis:本題答案：【37】8、【填空題】若字符串s=”algorithm”，則其子串個(gè)數(shù)為：Ifthestrings=algorithm,thenthenumberofitssub-stringis:本題答案：【46】9、【填空題】設(shè)有字符串變量StringA＝“”，B＝“MULE”，C＝“OLD”，D＝“MY”;請(qǐng)計(jì)算下列表達(dá)式（3個(gè)答案本身不要出現(xiàn)空格，答案之間用空格分開(kāi)）AssumethatthereisastringvariableStringA=,B=MULE,C=OLD,D=MY;Pleasecalculatethefollowingexpression:(1)D+C+B(2)B.substr(3，2)(3)A.strlength()本題答案：【MYOLDMULEE0】10、【填空題】一個(gè)文本串可用事先給定的字母映射表進(jìn)行加密。例如，設(shè)字母映射表為：Atextstringcanbeencryptedbythegivenlettersmappingtable.Forexample,thelettersmappingtableis:本題答案：【neopwmfbl】11、【填空題】S=“S1S2…Sn”是一個(gè)長(zhǎng)為n的字符串，存放在一個(gè)數(shù)組中，編程序?qū)改造之后輸出。S=S1S2...Snisastringoflengthn,andstoredinanarray,outputSafteritsprogrammabletransformation.1.將S的所有第偶數(shù)個(gè)字符按照其原來(lái)的下標(biāo)從大到小的次序放在S的后半部分；1.Alltheeven-numberedcharactersofSshouldbeplacedinaccordancewiththeirsubscriptdescendingorderinthesecondhalfofS;2.將S的所有第奇數(shù)個(gè)字符按照其原來(lái)的下標(biāo)從小到大的次序放在S的前半部分；2.Alltheodd-numberedcharactersofSshouldbeplacedinaccordancewiththeirsubscriptascendingorderinthefirsthalfofS.例如：S=‘ABCDEFGHIJKL’，則改造后的S為‘ACEGIKLJHFDB’。則S=’algorithm’,改造后為_(kāi)___________（Hint：1.答案不需要加引號(hào)2.系統(tǒng)基于字符匹配來(lái)判定答案，所以您的答案中不要出現(xiàn)空格）。Forexample:S='ABCDEFGHIJKL',thenafterthetransformationSis'ACEGIKLJHFDB'.IfS='algorithm',thenafterthetransformationSis____________(Hint:1.pleasedon’tincludeanyquotesinyouranswer.2.Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks).本題答案：【agrtmhiol】12、【填空題】下列程序判斷字符串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--;ijs[i]==s[j];i++,j--);return((2)__=(3)__);}注：(1)和(2)和(3)三個(gè)答案之間用空格分隔，每個(gè)答案是一個(gè)字符,不要加空格本題答案：【jij】13、【填空題】上一題中的字符串BAAABBBAA，與目標(biāo)BAAABBBCDDDCCHHHHBBBAAABBBAADD進(jìn)行匹配，至少需要多少次字符匹配（提示：利用優(yōu)化后的Next數(shù)組):ThestringinquestionaboveBAAABBBAAmatcheswithBAAABBBCDDDCCHHHHBBBAAABBBAADD.Howmanytimescharactermatchingwillneedatleast?(Hint:Use“Next”arrays):本題答案：【31】第五章二叉樹(shù)前半部分（5.1~5.4）測(cè)驗(yàn)1、【多選題】下列關(guān)于二叉樹(shù)性質(zhì)的說(shuō)法正確的有：（多選）Whichsentencesofthefollowingsarerightaboutabinarytree'scharacterization:（Therearemorethanonecorrectanswers）本題答案：【非空滿二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)一定為奇數(shù)個(gè)。Theamountofnodesofafullbinarytreewithatleastonenodemustbeodd.#當(dāng)一棵完全二叉樹(shù)是滿二叉樹(shù)時(shí)，葉子結(jié)點(diǎn)不一定集中在最下面一層。Ifacompletebinarytreeisafullbinarytree,itwillbepossiblethatleafnodesisnotonthenethermostlayer.#一棵非空二叉樹(shù)的為空的外部結(jié)點(diǎn)數(shù)目等于其結(jié)點(diǎn)數(shù)加1。Theamountofexternalnullnodesinabinarytreewithatleastonenodeequalstoitsamountofnodesplus1.】2、【多選題】下列關(guān)于二叉樹(shù)遍歷的說(shuō)法正確的有:Whichsentencesofthefollowingsarerightabouttraversalofabinarytree:H、所有結(jié)點(diǎn)左子樹(shù)為空的二叉樹(shù)的中序和后序遍歷順序恰好一樣。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutleftchildtreearethesame.I、所有結(jié)點(diǎn)右子樹(shù)為空的二叉樹(shù)的中序和后序遍歷順序恰好一樣。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutrightchildtreearethesame.J、存在一棵非空二叉樹(shù)，它的前序、中序和后序遍歷都是一樣的。Thereexistsabinarytreewithatleastonenode,whosepreorder,infixorderandpostorderareallthesame.本題答案：【所有結(jié)點(diǎn)左子樹(shù)為空的二叉樹(shù)的前序和中序遍歷順序恰好一樣。Thesequencesofpreorderandinfixorderofabinarytreewithallnodeswithoutleftchildtreearethesame.#只有空二叉樹(shù)和一個(gè)根結(jié)點(diǎn)的二叉樹(shù)這兩種二叉樹(shù)的前序和后序遍歷的順序恰好一樣。Onlythesequencesofpreorderandpostorderofthebinarytreewithnonodesoronlyonenodearethesame.#所有結(jié)點(diǎn)右子樹(shù)為空的二叉樹(shù)的中序和后序遍歷順序恰好一樣。Thesequencesofinfixorderandpostorderofabinarytreewithallnodeswithoutrightchildtreearethesame.#存在一棵非空二叉樹(shù)，它的前序、中序和后序遍歷都是一樣的。Thereexistsabinarytreewithatleastonenode,whosepreorder,infixorderandpostorderareallthesame.】3、【填空題】一棵有510個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為多少？（獨(dú)根樹(shù)高度為1)Whatistheheightofacompletebinarytreewith510nodes?(theheightofatreewithonlyarootis1)本題答案：【9】4、【填空題】一棵有512個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為多少？（獨(dú)根樹(shù)高度為1）Whatistheheightofacompletebinarytreewith512nodes?(theheightofatreewithonlyarootis1)本題答案：【10】5、【填空題】在一棵非空二叉樹(shù)中，若度為0的結(jié)點(diǎn)的個(gè)數(shù)n，度為2的結(jié)點(diǎn)個(gè)數(shù)為m，則有n=________(系統(tǒng)根據(jù)字符串匹配來(lái)判定答案，所以您的答案中請(qǐng)不要包含空格)Forabinarytreewithatleastonenode,iftherearennodeswithdegree0andmnodeswithdegree2,thenn=________（Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.）本題答案：【m+1】6、【填空題】已知一棵樹(shù)的前序遍歷為ABDEGCF，中序遍歷為DBGEACF，求這棵樹(shù)的后序遍歷。（字母和字母之間不要有空格）ThepreordersequenceofatreeisABDEGCF,anditsinfixordersequenceisDBGEACF,pleasewritedownitspostordersequence.(Thereisnoblankspacebetweenletters)本題答案：【DGEBFCA】7、【填空題】已知一棵樹(shù)的中序遍歷為DBGEACF，后序遍歷為DGEBFCA，求這棵樹(shù)的前序遍歷。（字母和字母之間不要有空格）TheinfixordersequenceofatreeisDBGEACF,anditspostordersequenceisDGEBFCA,pleasewritedownitspreordersequence.(Thereisnoblankspacebetweenletters)本題答案：【ABDEGCF】8、【填空題】請(qǐng)寫(xiě)出下面這棵二叉樹(shù)的前序遍歷（字母和字母之間不要有空格）Pleasewritedownthepreordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)本題答案：【BEXLMKCPDHQA】9、【填空題】請(qǐng)寫(xiě)出下面這棵二叉樹(shù)的中序遍歷（字母和字母之間不要有空格）Pleasewritedowntheinfixordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)本題答案：【LXMECKPBQHDA】10、【填空題】請(qǐng)寫(xiě)出下面這棵二叉樹(shù)的后序遍歷（字母和字母之間不要有空格）Pleasewritedownthepostordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)本題答案：【LMXCPKEQHADB】第五章二叉樹(shù)后半部分（5.5~5.7）測(cè)驗(yàn)1、【多選題】下列關(guān)于二叉搜索樹(shù)的說(shuō)法正確的有Whichsentencesofthefollowingsarerightaboutbinarysearchtree:本題答案：【二叉搜索樹(shù)按照中序遍歷將各結(jié)點(diǎn)打印出將各結(jié)點(diǎn)打印出來(lái)，將得到按照由小到大的排列。Ifweprintabinarysearchtree'snodesaccordingitsinfixorder,thesequencewillbefromsmalltolarge.#如果結(jié)點(diǎn)χ的左子樹(shù)有右子樹(shù)，則存在某個(gè)結(jié)點(diǎn)的值介于結(jié)點(diǎn)χ的值和χ左兒子的值之間，并且這個(gè)結(jié)點(diǎn)在$$x$$的左子樹(shù)之中。Iftheleftchildtreeofanodexhasarightchildtree,thenthereexistssomenodewhosevalueisbetweenthevalueofnodexandthevalueofitsleftchildnode,andthisnodeisontheleftchildtreeofnodex.#當(dāng)根結(jié)點(diǎn)沒(méi)有左兒子時(shí)，根結(jié)點(diǎn)一定是值最小的結(jié)點(diǎn)。Iftherootnodedoesn'thaveleftchild,itmustbethenodewiththesmallestvalue.】2、【多選題】下列關(guān)于堆的說(shuō)法正確的有:Whichsentencesofthefollowingsareright:本題答案：【堆一定是完全二叉樹(shù)。Aheapmustbeacompletebinarytree.#最小堆中，某個(gè)結(jié)點(diǎn)左子樹(shù)中最大的結(jié)點(diǎn)可能比右子樹(shù)中最小的結(jié)點(diǎn)小。Inaminimumheap,thelargestvalueonsomenode'sleftchildtreecouldbepossiblysmallerthanthesmallestvalueofitsrightchildtree.#使用篩選法建堆要比將元素一個(gè)一個(gè)插入堆來(lái)建堆效率高。Screeningmethodhasahigherefficiencythaninsertingelementsonebyonewhileconstructingaheap.】3、【多選題】下列關(guān)于Huffman樹(shù)和Huffman編碼的說(shuō)法正確的有:WhichsentencesofthefollowingsarerightaboutHuffmantreeandHuffmancode:本題答案：【Huffman樹(shù)一定是滿二叉樹(shù)。AHuffmantreemustbeafullbinarytree.#Huffman編碼是一種前綴編碼。Huffmancodeisakindofprefixcode.#對(duì)于同樣的一組權(quán)值兩兩不同的內(nèi)容可以得到不同的Huffman編碼方案。DifferentcontentwiththesamegroupofweightscangetdifferentHuffmancodes.】4、【多選題】一組包含不同權(quán)的字母已經(jīng)對(duì)應(yīng)好Huffman編碼，如果某一個(gè)字母對(duì)應(yīng)編碼001,下面說(shuō)法正確的有AgroupofletterswithdifferentweightshascorrespondedwithHuffmancodes,ifaletter'scorrespondingcodeis001,whichsentencesofthefollowingsareright:本題答案：【以001開(kāi)頭的編碼不可能對(duì)應(yīng)其他字母。Acodebeginningwith001couldn'tcorrespondwithotherletters.#以01開(kāi)頭和1開(kāi)頭的編碼肯定對(duì)應(yīng)某個(gè)字母。Codesbeginningwith01or1mustcorrespongdingwithsomeletters.#建好的Huffman樹(shù)至少包含4個(gè)葉結(jié)點(diǎn)。TheHuffmantreecontainsatleast4leafnodes.】5、【填空題】如果按關(guān)鍵碼值遞增的順序依次將n個(gè)關(guān)鍵碼值插入到二叉搜索樹(shù)中，如果對(duì)這樣的二叉搜索樹(shù)進(jìn)行檢索時(shí)，每次檢索的字符都等概率的從這n個(gè)關(guān)鍵碼值中選取，平均比較次數(shù)為多少？Ifweinsertnkeyvaluestoabinarysearchtreesuccessivelyfromsmalltolarge,whenwesearchthisbinarysearchtree,eachtimethesearchcharacterisselectedfromthesenkeyvalueswiththesamepossibility,thenhowmanytimeswillthecomparisonbeonaverage?本題答案：【(n+1)/2##%_YZPRLFH_%##(1+n)/2】6、【填空題】從空二叉樹(shù)開(kāi)始，嚴(yán)格按照二叉搜索樹(shù)的插入算法（不進(jìn)行旋轉(zhuǎn)平衡），逐個(gè)插入關(guān)鍵碼{18,73,10,5,68,99,27,41,51,32,25}構(gòu)造出一棵二叉搜索樹(shù)，對(duì)該二叉搜索樹(shù)按照前序遍歷得到的序列為？（答案中每?jī)蓚€(gè)元素之間用一個(gè)空格隔開(kāi)）Fromanullbinarytree,insertkeyvalues{18,73,10,5,68,99,27,41,51,32,25}successivelyaccordingtotheinsertionalgorithmofabinarysearchtreestrictly(norotationandbalance)toconstructabinarysearchtree.Pleasewritedownthesequenceofpreorderofthisbinarysearchtree.(Thereisoneblankspacebetweentwoelements)本題答案：【181057368272541325199】7、【填空題】從空二叉樹(shù)開(kāi)始，嚴(yán)格按照二叉搜索樹(shù)的插入算法（不進(jìn)行旋轉(zhuǎn)平衡），逐個(gè)插入關(guān)鍵碼{18,73,10,5,68,99,27,41,51,32,25}構(gòu)造出一棵二叉搜索樹(shù)，對(duì)該二叉搜索樹(shù)按照后序遍歷得到的序列為？（答案中每?jī)蓚€(gè)元素之間用一個(gè)空格隔開(kāi)）Fromanullbinarytree,insertkeyvalues{18,73,10,5,68,99,27,41,51,32,25}successivelyaccordingtotheinsertionalgorithmofabinarysearchtreestrictly(norotationandbalance)toconstructabinarysearchtree.Pleasewritedownthesequenceofpostorderofthisbinarysearchtree.(Thereisoneblankspacebetweentwoelements)本題答案：【510253251412768997318】8、【填空題】從空二叉樹(shù)開(kāi)始，嚴(yán)格按照二叉搜索樹(shù)的插入算法（不進(jìn)行旋轉(zhuǎn)平衡），逐個(gè)插入關(guān)鍵碼構(gòu)造出一棵二叉樹(shù)，以怎樣的順序插入關(guān)鍵碼集合{14，32，47，6，9，12，78，63，29，81}可以使得樹(shù)的深度最??？請(qǐng)依次寫(xiě)出插入到樹(shù)中的元素，每?jī)蓚€(gè)元素之間用一個(gè)空格隔開(kāi)。如果有多組滿足要求的方案，請(qǐng)使得你的答案中先插入的元素盡可能的小。Fromanullbinarytree,insertkeyvaluessuccessivelyaccordingtotheinsertionalgorithmofabinarysearchtreestrictly(norotationandbalance)toconstructabinarysearchtree.Whatistheinsertionsequencethatcouldmakethetreehaveasmallestdepthwithakeyvalueset{14，32，47，6，9，12，78，63，29，81}?Pleasewritedowntheelementssuccessively,andthereisoneblankspacebetweentwoelements.Iftherearemorethanoneanswerthatmeetthecondition,pleasemaketheelementwhichneedstobeinsertedfirstassmallaspossibleinyouranswer.本題答案：【126947291432786381】9、【填空題】對(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】10、【填空題】對(duì)于如下圖所示的最大堆，刪除掉最大的元素后，堆的前序遍歷結(jié)果是Forthefollowingmaximumheap,afterdeletingthemaximumelement,thepreordertraversalsequenceis請(qǐng)依次寫(xiě)出插入到樹(shù)中的元素，每?jī)蓚€(gè)元素之間用一個(gè)空格隔開(kāi)。Pleasewritedowntheelementssuccessively,andthereisoneblankspacebetweentwoelements.本題答案：【59432412233728557483】11、【填空題】對(duì)于如下圖所示的最大堆，刪除掉最大的元素后，堆的后序遍歷結(jié)果是Forthefollowingmaximumheap,afterdeletingthemaximumelement,thepostordertraversalsequenceis本題答案：【12232428537434835759】12、【填空題】下表展示了在一段文本中每個(gè)字母出現(xiàn)的次數(shù)。Thefrequenciesthateachletterappearsinaparagraphisrepresentedasfollow.本題答案：【36】13、【填空題】對(duì)于給定的一組權(quán)W={1,4,9,16,25,36,49,64,81,100}，構(gòu)造一棵具有最小帶權(quán)外部路徑長(zhǎng)度的三叉樹(shù)，寫(xiě)出這棵樹(shù)的帶權(quán)外部路徑長(zhǎng)度。ForagivengroupofweightsW={1,4,9,16,25,36,49,64,81,100},pleaseconstructaternarytreewithaminimumweightedroutelengthandwritedownthisweightedroutelength.本題答案：【705】14、【填空題】請(qǐng)閱讀下面一段代碼PleasereadthefollowingcodeC++：本題答案：【1】15、【填空題】請(qǐng)閱讀下面一段代碼PleasereadthefollowingcodeC++：本題答案：【2】16、【填空題】請(qǐng)閱讀下面一段代碼PleasereadthefollowingcodeC++：本題答案：【3】第六章樹(shù)測(cè)驗(yàn)1、【單選題】一個(gè)深度為h的滿k叉樹(shù)，最多有多少個(gè)葉結(jié)點(diǎn)？（獨(dú)根樹(shù)深度為0）(單選)Thereisafullk-arytree,whosedepthish.Howmanyleafnodescanithaveatmost?(Thedepthofatree,whichonlyhasarootnode,is0.)（Thereisonlyonecorrectanswer）本題答案：【】2、【單選題】一個(gè)深度為h的滿k叉樹(shù)，最多有多少個(gè)結(jié)點(diǎn)？（獨(dú)根樹(shù)深度為0）Thereisafullk-arytree,whosedepthish.Howmanynodescanithaveatmost?(Thedepthofatree,whichonlyhasarootnode,is0.)本題答案：【】3、【單選題】設(shè)F是由T1,T2,T3三棵樹(shù)組成的森林，其中T1,T2,T3的結(jié)點(diǎn)數(shù)分別為n1,n2和n3，與F對(duì)應(yīng)的二叉樹(shù)為B，則二叉樹(shù)B的右子樹(shù)中有_____________個(gè)結(jié)點(diǎn)(單選）AssumethatFisaforest,madeupoftreeT1,T2,T3,andthenodenumbersofT1,T2,T3aren1,n2,n3.LetBbethecorrespondingbinarytreeofF,thenB'srightsub-treewillhas__________nodes.(Thereisonlyonecorrectanswer)本題答案：【n2+n3】4、【單選題】設(shè)F是由T1,T2,T3三棵樹(shù)組成的森林，其中T1,T2,T3的結(jié)點(diǎn)數(shù)分別為n1,n2和n3，與F對(duì)應(yīng)的二叉樹(shù)為B，則二叉樹(shù)B的左子樹(shù)中有_____________個(gè)結(jié)點(diǎn)(單選）AssumethatFisaforest,madeupoftreeT1,T2,T3,andthenodenumbersofT1,T2,T3aren1,n2,n3.LetBbethecorrespondingbinarytreeofF,thenB'sleftsub-treewillhas__________nodes.(Thereisonlyonecorrectanswer)本題答案：【n1-1】5、【單選題】將一棵樹(shù)T轉(zhuǎn)換為左子/右兄鏈表表示的二叉樹(shù)B，則T的后根次序遍歷序列是B的相應(yīng)_________序列。（單選）TransformatreeTintoabinarytreeB,whichisrepresentedbyLeft-Child/Right-Siblingimplementation.Thenthepost-ordertraversalsequenceofTisthesameasthe__________sequenceofB.（Thereisonlyonecorrectanswer）本題答案：【中序遍歷】6、【多選題】2-3樹(shù)是一種特殊的樹(shù)，它滿足兩個(gè)條件：（1）每個(gè)內(nèi)部結(jié)點(diǎn)有兩個(gè)或三個(gè)子結(jié)點(diǎn)；（2）所有的葉結(jié)點(diǎn)到根的路徑長(zhǎng)度相同；如果一棵2-3樹(shù)有9個(gè)葉結(jié)點(diǎn)，那么它可能有_________個(gè)非葉結(jié)點(diǎn)。(多項(xiàng))2-3treeisaspecialkindoftree,itsatisfy:（1）Everyinternalnodehas2or3childnodes.(2)Alltheleafnodeshavethesamelengthofthepathtotherootnode.Ifa2-3treehas9leafnodes,thenitmayhave__________non-leafnodes.（Therearemorethanonecorrectanswers）本題答案：【4#7】7、【填空題】給出一棵樹(shù)的邏輯結(jié)構(gòu)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)}試回答下列問(wèn)題：Pleaseanswerthesequestions:（1）哪個(gè)是根結(jié)點(diǎn)？whichistherootnode?（2）哪些是F的孩子？whicharethechildnodesofNodeF?（3）結(jié)點(diǎn)K的層次是多少？（注：根的層數(shù)為0，獨(dú)根樹(shù)深度為0，高度為1，其他題目同樣如此；同一個(gè)選項(xiàng)的答案如果有多個(gè)字母，按照字典序排列，且不要以空格分隔）(P.S.theleveloftherootnodeis0,thedepthofatree,whichonlyhasarootnode,is0,anditsheightis1.Otherproblemshavethesameregulations.Ifthereareseveralalphabetsinonequestion,orderthembylexicographicalorder,anddonotaddspaces.)本題答案：【AGH3】8、【填空題】給出一棵樹(shù)的邏輯結(jié)構(gòu)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)}試回答下列問(wèn)題：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）哪個(gè)是F的父結(jié)點(diǎn)？whichistheparentnodeofNodeF?（2）哪些是B的子孫？whicharetheoffspringofNodeB?（3）以結(jié)點(diǎn)C為根的子樹(shù)的深度是多少？whatisthedepthofthesub-treewhoserootnodeisNodeC?（注：根的層數(shù)為0，獨(dú)根樹(shù)深度為0，高度為1，其他題目同樣如此；各個(gè)選項(xiàng)之間的答案用空格分隔就好；同一個(gè)選項(xiàng)的答案如果有多個(gè)字母，按照字典序排列，且不要以空格分隔）（P.S.theleveloftherootnodeis0,thedepthofatree,whichonlyhasarootnode,is0,anditsheightis1.Otherproblemshavethesameregulations.Ifthereareseveralalphabetsinonequestion,orderthembylexicographicalorder,anddonotaddspaces.)本題答案：【BEFGH2】9、【填空題】給出一棵樹(shù)的邏輯結(jié)構(gòu)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)}試回答下列問(wèn)題：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）哪些是葉結(jié)點(diǎn)？whicharetheleafnodes?（2）哪些是F的祖先？whichistheparentnodeofNodeF?（3）樹(shù)的深度是多少？whatisthedepthofthetree?（注：根的層數(shù)為0，獨(dú)根樹(shù)深度為0，高度為1，其他題目同樣如此；同一個(gè)小題的答案如果有多個(gè)字母，按照字典序排列，且不要以空格分隔，不同小題用一個(gè)空格隔開(kāi)）本題答案：【DEGHIKAB3】10、【填空題】若一個(gè)具有N個(gè)頂點(diǎn)，K條邊的無(wú)向圖是一個(gè)森林（NK且2K=N），則該森林有多少棵樹(shù)？Thereisanundirectedgraph.IthasNnodesandKedges.(NKand2K=N).Ifitisaforest,thenhowmanytreeswillithas?本題答案：【N-K】11、【填空題】將下圖的二叉樹(shù)轉(zhuǎn)換為對(duì)應(yīng)的森林，按照先根次序列出其結(jié)點(diǎn)。（答案的字母之間沒(méi)有空格）Transformthisbinarytreeintothecorrespondingforest,andwritedownthepre-ordernodesequence.(Donotaddspacesinyouranswer.)本題答案：【ABECFDGHIJKL】12、【填空題】將下圖的二叉樹(shù)轉(zhuǎn)換為對(duì)應(yīng)的森林，按照后根次序列出其結(jié)點(diǎn)。（答案的字母之間沒(méi)有空格）Transformthisbinarytreeintothecorrespondingforest,andwritedownthepost-ordernodesequence.(Donotaddspacesinyouranswer.)本題答案：【EBFCDAIJKHGL】13、【填空題】一棵完全三叉樹(shù)，下標(biāo)為121的結(jié)點(diǎn)在第幾層？（注：下標(biāo)號(hào)從0開(kāi)始，根的層數(shù)為0）Inacomplete3-arytree,whatlevelisthenode,whosesubscriptis121,standon?(P.S.thesubscriptstartsform0,andthelevelofrootnodeis0)本題答案：【5】14、【填空題】一棵完全三叉樹(shù)，下標(biāo)為120的結(jié)點(diǎn)在第幾層？（注：下標(biāo)號(hào)從0開(kāi)始，根的層數(shù)為0）Inacomplete3-arytree,whatlevelisthenode,whosesubscriptis120,standon?(P.S.thesubscriptstartsform0,andthelevelofrootnodeis0)本題答案：【4】15、【填空題】根據(jù)樹(shù)的雙標(biāo)記層次遍歷序列，求其帶度數(shù)的后根遍歷序列Giventhedouble-tagginglevel-ordertraversalsequenceofatree,pleasewritedownthepost-ordertraversalsequencewithdegree.比如：已知一棵樹(shù)的雙標(biāo)記層次遍歷序列如下：Forexample,assumethatatree'sdouble-tagginglevel-ordertraversalsequenceisshownasfollowed:本題答案：【H0C1D0G0B3F0I0E2A2】16、【填空題】根據(jù)樹(shù)的雙標(biāo)記層次遍歷序列，求其帶度數(shù)的后根遍歷序列Giventhedouble-tagginglevel-ordertraversalsequenceofatree,pleasewritedownthepost-ordertraversalsequencewithdegree.比如：已知一棵樹(shù)的雙標(biāo)記層次遍歷序列如下：Forexample,assumethatatree'sdouble-tagginglevel-ordertraversalsequenceisshownasfollowed:本題答案：【G0B1H0D1C1E0I0F1A4】17、【填空題】根據(jù)樹(shù)的雙標(biāo)記層次遍歷序列，求其帶度數(shù)的后根遍歷序列Giventhedouble-tagginglevel-ordertraversalsequenceofatree,pleasewritedownthepost-ordertraversalsequencewithdegree.本題答案：【D0E0C2H0I0F2B2G0A2】18、【填空題】對(duì)于以下等價(jià)類(lèi)，采用“加權(quán)合并規(guī)則”（也稱“重量權(quán)衡合并規(guī)則”），進(jìn)行并查運(yùn)算，給出最后父節(jié)點(diǎn)索引序列。Forthefollowingequivalenceclass,pleaseuseweightedunionruleandUNION/FINDalgorithmtowritedownthefinalparentnodeindexsequence.4-06-28-49-43-59-55-21-27-1注意：當(dāng)合并大小相同的兩棵樹(shù)的時(shí)候，將第二棵樹(shù)的根指向第一棵樹(shù)的根；根節(jié)點(diǎn)的索引是它本身；數(shù)字之間用空格隔開(kāi)。Notice:Whenwejointwotreeswiththesamesize,welettherootofthesecondtreepointtotherootofthefirsttree.Theindexoftherootnodeisitself.Separatethenumberswithonlyonespaces.本題答案：【4464434444】19、【填空題】對(duì)于以下等價(jià)類(lèi)，采用“加權(quán)合并規(guī)則”（也稱“重量權(quán)衡合并規(guī)則”），進(jìn)行并查運(yùn)算，給出最后父節(jié)點(diǎn)索引序列。Forthefollowingequivalenceclass,pleaseuseweightedunionruleandUNION/FINDalgorithmtowritedownthefinalparentnodeindexsequence.8-93-27-45-96-18-67-32-58-0注意：當(dāng)合并大小相同的兩棵樹(shù)的時(shí)候，將第二棵樹(shù)的根指向第一棵樹(shù)的根；根節(jié)點(diǎn)的索引是它本身；數(shù)字之間用空格隔開(kāi)。Notice:Whenwejointwotreeswiththesamesize,welettherootofthesecondtreepointtotherootofthefirsttree.Theindexoftherootnodeisitself.Separatethenumberswithonlyonespaces.本題答案：【8637788888】數(shù)據(jù)結(jié)構(gòu)與算法期中考試（范圍：前六章）1、【單選題】一個(gè)深度為h的滿k叉樹(shù)，最多有多少個(gè)結(jié)點(diǎn)？（獨(dú)根樹(shù)深度為0）Forafullk-arytreewithdepthh,howmanynodescouldithaveatmost?(thedepthofatreewithonlyonenodeis0)本題答案：【】2、【單選題】對(duì)二叉排序樹(shù)（即BST，也稱“二叉搜索樹(shù)”）進(jìn)行什么遍歷，可以得到該二叉樹(shù)所有結(jié)點(diǎn)構(gòu)成的排序序列？Fromwhichtraversalcanwegettheorderedsequenceofthenodesofabinarysearchtree?本題答案：【中序inorder】3、【多選題】順序棧是用一段連續(xù)的空間存儲(chǔ)內(nèi)容，本質(zhì)是順序表。鏈?zhǔn)綏t是采用單鏈表的方式存儲(chǔ)。下列關(guān)于這兩種存儲(chǔ)方式的說(shuō)法正確的是：Sequentialstackstoreselementsinacontiguousspace,whichisessentiallyasequentiallist.Linkedstackisimplementedbyasinglelinkedlistinstead.Whichofthefollowingaboutthetwostoragemethodsarecorrect?(multiplechoice)本題答案：【順序棧的壓棧和出棧操作只需常數(shù)時(shí)間。Thepushandpopoperationofsequencestackonlyneedsconstanttime.#鏈?zhǔn)綏５膲簵：统鰲２僮髦恍璩?shù)時(shí)間。Thepushandpopoperationoflinkedstackonlyneedsconstanttime.#順序棧需要指定一個(gè)具體的長(zhǎng)度Sequentialstackneedstobeassignedaspecificlength.#鏈?zhǔn)綏Ｐ枰粋€(gè)結(jié)構(gòu)性開(kāi)銷(xiāo)Linkedstackneedsastructuralcost.】4、【多選題】在字符{A,C,G,T}組成的DNA序列中，A——T和C——G是互補(bǔ)對(duì)。判斷一個(gè)DNA序列中是否存在互補(bǔ)回文串（例如，ATCATGAT的補(bǔ)串是TAGTACTA，與原串形成互補(bǔ)回文串；即要求整個(gè)原串的補(bǔ)串是原串的逆序）；下面DNA序列中存在互補(bǔ)回文串的是：(多選)InDNAsequencesconsistingofcharacters{A,C,G,T},A-TandC-Garecomplementarypairsrespectively.DeterminewhetheraDNAsequencehasacomplementarypalindromicstring(Forexample,ATCATGAT'scomplementarystringisTAGTACTA,withisthepalindromicsequencetotheoriginalstring;insuchcasethecomplementarystringisalsothereverseoftheoriginalstring);WhichofthefollowingDNAsequenceshavecomplementarypalindro