MOOC 數(shù)據(jù)結構與算法-北京大學 中國大學慕課答案

MOOC數(shù)據(jù)結構與算法-北京大學中國大學慕課答案第一章概論測驗1、問題：下列不屬于線性結構的是：Whichoneofthefollowingsdoesnotbelongtolinearstructure:（Thereisonlyonecorrectanswer）選項：A、隊列(queue)B、散列表(hashtable)C、向量(vector)D、圖(graph)正確答案:【圖(graph)】2、問題：以下哪種結構是邏輯結構，而與存儲和運算無關：Whichofthefollowingstructureisalogicalstructureregardlessofthestorageoralgorithm:（Thereisonlyonecorrectanswer）選項：A、隊列(queue)B、雙鏈表(doublylinkedlist)C、數(shù)組(array)D、順序表(Sequentiallist)正確答案:【隊列(queue)】3、問題：關于算法特性描述正確的有：Whichoneisrightaboutalgorithm’scharacterization:（therearemorethanonecorrectanswers）選項：A、算法保證計算結果的正確性。Algorithmwillensurethecorrectnessofthecalculationresults.B、組成算法的指令可以有限也可能無限。InstructionswhichcompositealgorithmscanbeinfiniteorfiniteC、算法描述中下一步執(zhí)行的步驟不確定。Thenextstepintheimplementationofthealgorithmdescribedisuncertain.D、算法的有窮性指算法必須在有限步驟內結束。Thefinitenatureofalgorithmsmeansalgorithmmustbecompletedwithinalimitedstep.正確答案:【算法保證計算結果的正確性。Algorithmwillensurethecorrectnessofthecalculationresults.#算法的有窮性指算法必須在有限步驟內結束。Thefinitenatureofalgorithmsmeansalgorithmmustbecompletedwithinalimitedstep.】4、問題：下列說法正確的是：Whichoptionsmaybecorrect?（therearemorethanonecorrectanswers）選項：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、如果ab1,是，但不一定是【ifab1,is，maynotbe】D、函數(shù)f(n)是O(g(n))，當常數(shù)a足夠大時，一定有函數(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))】】5、問題：已知一個數(shù)組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;}選項：A、B、C、D、正確答案:【#】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)（提示：系統(tǒng)基于字符匹配來判定答案，所以您的答案中不要出現(xiàn)空格）Writethefollowingtimecomplexityindescendingsequence:Writedowntheanswerlabelssuchas(1)(2)(3)(4)(5).（Hint：Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.）正確答案:【(5)(1)(2)(4)(3)】第二章線性表測驗1、問題：下面關于線性表的敘述中，正確的是哪些？Whichofthefollowingsaboutlinearlistarecorrect?（Therearemorethanoneanswers.）Selecttheanswerthatmatches選項：A、線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。Linearlistsusesequentialstoragewhichmustoccupyacontinuousmemoryunits.B、線性表采用順序存儲，便于進行插入和刪除操作。Linearlistsusingsequentialstorage,itiseasytodoinsertanddeleteoperations.C、線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。Linearlistsusingthelinkedstorage,donotoccupyacontinuousmemoryunits.D、線性表采用鏈接存儲，便于插入和刪除操作。Linearlistsusingthelinkedstorage,itiseasyforinsertanddeletingoperations.正確答案:【線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。Linearlistsusesequentialstoragewhichmustoccupyacontinuousmemoryunits.#線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。Linearlistsusingthelinkedstorage,donotoccupyacontinuousmemoryunits.#線性表采用鏈接存儲，便于插入和刪除操作。Linearlistsusingthelinkedstorage,itiseasyforinsertanddeletingoperations.】2、問題：下面的敘述中正確的是：Selecttheanswerthatmatches（Therearemorethanonecorrectanswers）選項：A、線性表在鏈式存儲時，查找第i個元素的時間與i的數(shù)值無關。Whenthelinearliststoredinlinkedform,thetimetofindthei-thelementisregardlessofthevalueofi.B、線性表在順序存儲時，查找第i個元素的時間與i的數(shù)值成正比。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisproportionaltovaluewithi.C、線性表在順序存儲時，查找第i個元素的時間與i的數(shù)值無關。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisregardlessofthevalueofi.D、線性表在鏈式存儲時，插入第i個元素的時間與i的數(shù)值成正比。Whenlinearlistsstoredinthelinkedform,thetimetoinsertthei-thelementisproportionaltovaluewithi.正確答案:【線性表在順序存儲時，查找第i個元素的時間與i的數(shù)值無關。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisregardlessofthevalueofi.#線性表在鏈式存儲時，插入第i個元素的時間與i的數(shù)值成正比。Whenlinearlistsstoredinthelinkedform,thetimetoinsertthei-thelementisproportionaltovaluewithi.】3、問題：完成在雙循環(huán)鏈表結點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;】4、填空題：對于一個具有n個結點的單鏈表，在已知的結點*p后插入一個新結點的時間復雜度為O(___),在給定值為x的結點后插入一個新結點的時間復雜度為O(___)。（請依次填入,格式為(a)(b),如果您的答案中出現(xiàn)字母，請使用小寫;后一空系統(tǒng)基于字符匹配來判定答案，所以您的答案中不要出現(xiàn)空格）Forasinglelinkedlistwithnnodes,andafteraknownnode*ptoinsertanewnode,thetimecomplexityisO(___);afteragivennodewithxvalueinsertanewnode,thetimecomplexityisO(___).(Ifyouranswercontainsletters,uselowercaseone.Thesecondblankisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.)正確答案:【(1)(n)】5、填空題：設某循環(huán)鏈表長度為n，并設其中一節(jié)點為p1，然后按照鏈表的順序將后面的節(jié)點依次命名為p2,p3,...,pn，那么請問pn.next=____(答案為一個節(jié)點名，注意所有字母為小寫且答案中不包含空格)正確答案:【p1】第三章棧與隊列測驗1、問題：設棧S和隊列Q的初始狀態(tài)為空，元素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、2B、3C、4D、6正確答案:【3】2、問題：現(xiàn)有中綴表達式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–3672C、1004–3/3367–*+2*D、*(+/(–1004)3*3(–367))2正確答案:【1004–3/3367–*+2*】3、問題：隊列的特點包括：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)】4、問題：以下循環(huán)隊列的實現(xiàn)方式中，長度為n的隊列，所能容納的元素個數(shù)也為n的有:Inthefollowingrealizingwaysofcircularqueue,thequeuewhoselengthisncanalsocontainthenumberofnelementsis:（Therearemorethanoneanswers.）選項：A、只用front和rear兩個指針標記隊列的頭和尾，兩個指針均為實指Onlyusefrontandrearasthequeue’sheadandtailpointersandthetwopointersareactuallyreferringto.B、用front和rear兩個指針標記隊列的頭和尾，并用整型變量len記錄隊列元素數(shù)Withthequeue’sheadandtailpointersmarkedasfrontandrear,usetheintegervariablelentorecordthenumberofelements.C、用front和rear兩個指針標記隊列的頭和尾，并用布爾型變量empty記錄隊列是否為空Withthequeue’sheadandtailpointersmarkedasfrontandrear,useBooleanvariableemptyrecordwhetherthequeueisempty.D、只用front和rear兩個指針標記隊列的頭和尾，兩個指針均為虛指Onlyusefrontandrearasthequeue’sheadandtailpointersandthetwopointersarevirtuallyreferringto.正確答案:【用front和rear兩個指針標記隊列的頭和尾，并用整型變量len記錄隊列元素數(shù)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、填空題：雙端隊列可以在隊列的兩端進行插入和刪除操作，既可在隊尾進行插入/刪除，又可在隊頭進行插入/刪除。現(xiàn)有4個不同的元素順序輸入到雙端隊列，那么可以得到_____種不同的排列。double-endedqueuecaninsertanddeleteoperationsonbothendsofthequeue.Thatitcaninsert/deleteatitstail,butalsoatthehead.Existing4differentelementssequentiallyinputtothedouble-endedqueue,youcanget_____differentpermutations.正確答案:【8】第四章字符串測驗1、問題：設有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為()（單選）Therearetwostringspq,qisp’ssubstring.Thealgorithmtosearchthefirsttimeqappearedinpiscalled()（Thereisonlyonecorrectanswer）選項：A、求子串SeekingsubstringB、聯(lián)接ConcatenationC、匹配MatchingD、求串長Seekinglength正確答案:【匹配Matching】2、問題：下列說法正確的是：（單選）Whichofthefollowingstatementsiscorrect?（Thereisonlyonecorrectanswer）選項：A、空串就是空白串“Emptystring”isblankstring.B、空串是任意字符串的子串Emptystringisasubstringofarbitrarystring.C、串只可以采用順序存儲，不可以采用鏈式存儲Stringonlycanbestoredinsequentialmethodandcannotbestoredinlinkedmethod.D、在C++標準中，charS[M]最多能表示長度為M的字符串InC++standards,charS[M]canrepresentuptoastringoflengthM.正確答案:【空串是任意字符串的子串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)是對字符串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、ABCD、G0123E、ABCDH、2345I、ABCDL、1234M、ABCP、G2345正確答案:【ABCD###1234】4、問題：下面關于串的的敘述中，哪一個是不正確的:（單選）Whichofthefollowingdescriptionsaboutstringisnotcorrect?（Thereisonlyonecorrectanswer）選項：A、串是字符的有限序列Stringisafinitesequenceofcharacters.B、模式匹配是串的一種重要運算Patternmatchingisanimportantoperation.C、串是一種數(shù)據(jù)對象和操作都特殊的線性表StringisalinearlistwhosedataobjectsandoperationsbothspecialD、空串是由空格構成的串Emptystringisastringconsistingofspaces.正確答案:【空串是由空格構成的串Emptystringisastringconsistingofspaces.】5、問題：SeekthestringBAAABBBAA‘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}】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、CTGATCAGB、AATTAATTC、TGCAACGTD、CATGGTACE、GTACGTACF、AGCTAGCT正確答案:【CTGATCAG#AATTAATT#GTACGTAC#AGCTAGCT】7、填空題：若字符串s=“software”，則其子串個數(shù)為：Ifthestrings=software,thenthenumberofitssub-stringis:正確答案:【37】8、填空題：若字符串s=”algorithm”，則其子串個數(shù)為：Ifthestrings=algorithm,thenthenumberofitssub-stringis:正確答案:【46】9、填空題：設有字符串變量StringA＝“”，B＝“MULE”，C＝“OLD”，D＝“MY”;請計算下列表達式（3個答案本身不要出現(xiàn)空格，答案之間用空格分開）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:正確答案:【31】第五章二叉樹前半部分（5.1~5.4）測驗1、問題：下列關于二叉樹性質的說法正確的有：（多選）Whichsentencesofthefollowingsarerightaboutabinarytree'scharacterization:（Therearemorethanonecorrectanswers）選項：A、非空滿二叉樹的結點個數(shù)一定為奇數(shù)個。Theamountofnodesofafullbinarytreewithatleastonenodemustbeodd.B、非完全二叉樹也可以用像完全二叉樹那樣使用順序存儲結構進行存儲。Sequentialstoringstructurecanalsobeusedtostoreanincompletebinarytreejustliketostoreacompletebinarytree.C、當一棵完全二叉樹是滿二叉樹時，葉子結點不一定集中在最下面一層。Ifacompletebinarytreeisafullbinarytree,itwillbepossiblethatleafnodesisnotonthenethermostlayer.D、完全二叉樹最多只有最下面的一層結點度數(shù)可以小于2。Foracompletebinarytree,onlythedegreesofnodesonthenethermostlayercouldbelessthan2.E、一棵非空二叉樹的為空的外部結點數(shù)目等于其結點數(shù)加1。Theamountofexternalnullnodesinabinarytreewithatleastonenodeequalstoitsamountofnodesplus1.F、滿二叉樹的所有結點的度均為2。Alldegreesofnodesinafullbinarytreeare2.正確答案:【非空滿二叉樹的結點個數(shù)一定為奇數(shù)個。Theamountofnodesofafullbinarytreewithatleastonenodemustbeodd.#當一棵完全二叉樹是滿二叉樹時，葉子結點不一定集中在最下面一層。Ifacompletebinarytreeisafullbinarytree,itwillbepossiblethatleafnodesisnotonthenethermostlayer.#一棵非空二叉樹的為空的外部結點數(shù)目等于其結點數(shù)加1。Theamountofexternalnullnodesinabinarytreewithatleastonenodeequalstoitsamountofnodesplus1.】2、問題：下列關于二叉樹遍歷的說法正確的有: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.】3、填空題：一棵有510個結點的完全二叉樹的高度為多少？（獨根樹高度為1)Whatistheheightofacompletebinarytreewith510nodes?(theheightofatreewithonlyarootis1)正確答案:【9】4、填空題：一棵有512個結點的完全二叉樹的高度為多少？（獨根樹高度為1）Whatistheheightofacompletebinarytreewith512nodes?(theheightofatreewithonlyarootis1)正確答案:【10】5、填空題：在一棵非空二叉樹中，若度為0的結點的個數(shù)n，度為2的結點個數(shù)為m，則有n=________(系統(tǒng)根據(jù)字符串匹配來判定答案，所以您的答案中請不要包含空格)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:選項：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、堆是實現(xiàn)優(yōu)先隊列的惟一方法。Aheapistheonlymethodtoimplementapriorityqueue.D、堆一定是完全二叉樹。Aheapmustbeacompletebinarytree.E、最小堆中，某個結點左子樹中最大的結點可能比右子樹中最小的結點小。Inaminimumheap,thelargestvalueonsomenode'sleftchildtreecouldbepossiblysmallerthanthesmallestvalueofitsrightchildtree.F、使用篩選法建堆要比將元素一個一個插入堆來建堆效率高。Screeningmethodhasahigherefficiencythaninsertingelementsonebyonewhileconstructingaheap.正確答案:【堆一定是完全二叉樹。Aheapmustbeacompletebinarytree.#最小堆中，某個結點左子樹中最大的結點可能比右子樹中最小的結點小。Inaminimumheap,thelargestvalueonsomenode'sleftchildtreecouldbepossiblysmallerthanthesmallestvalueofitsrightchildtree.#使用篩選法建堆要比將元素一個一個插入堆來建堆效率高。Screeningmethodhasahigherefficiencythaninsertingelementsonebyonewhileconstructingaheap.】3、問題：下列關于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.】4、問題：一組包含不同權的字母已經(jīng)對應好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.】5、填空題：如果按關鍵碼值遞增的順序依次將n個關鍵碼值插入到二叉搜索樹中，如果對這樣的二叉搜索樹進行檢索時，每次檢索的字符都等概率的從這n個關鍵碼值中選取，平均比較次數(shù)為多少？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}，用篩選法建最小值堆，若一旦發(fā)現(xiàn)逆序對就進行交換，共需要交換元素多少次？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、填空題：下表展示了在一段文本中每個字母出現(xiàn)的次數(shù)。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）選項：A、B、C、D、正確答案:【】2、問題：一個深度為h的滿k叉樹，最多有多少個結點？（獨根樹深度為0）Thereisafullk-arytree,whosedepthish.Howmanynodescanithaveatmost?(Thedepthofatree,whichonlyhasarootnode,is0.)選項：A、B、C、D、正確答案:【】3、問題：設F是由T1,T2,T3三棵樹組成的森林，其中T1,T2,T3的結點數(shù)分別為n1,n2和n3，與F對應的二叉樹為B，則二叉樹B的右子樹中有_____________個結點(單選）AssumethatFisaforest,madeupoftreeT1,T2,T3,andthenodenumbersofT1,T2,T3aren1,n2,n3.LetBbethecorrespondingbinarytreeofF,thenB'srightsub-treewillhas__________nodes.(Thereisonlyonecorrectanswer)選項：A、n2B、n3C、n1+n3D、n2+n3正確答案:【n2+n3】4、問題：設F是由T1,T2,T3三棵樹組成的森林，其中T1,T2,T3的結點數(shù)分別為n1,n2和n3，與F對應的二叉樹為B，則二叉樹B的左子樹中有_____________個結點(單選）AssumethatFisaforest,madeupoftreeT1,T2,T3,andthenodenumbersofT1,T2,T3aren1,n2,n3.LetBbethecorrespondingbinarytreeofF,thenB'sleftsub-treewillhas__________nodes.(Thereisonlyonecorrectanswer)選項：A、n2-1B、n3-1C、n1-1D、n2正確答案:【n1-1】5、問題：將一棵樹T轉換為左子/右兄鏈表表示的二叉樹B，則T的后根次序遍歷序列是B的相應_________序列。（單選）TransformatreeTintoabinarytreeB,whichisrepresentedbyLeft-Child/Right-Siblingimplementation.Thenthepost-ordertraversalsequenceofTisthesameasthe__________sequenceofB.（Thereisonlyonecorrectanswer）選項：A、前序遍歷B、后序遍歷C、中序遍歷D、層次遍歷正確答案:【中序遍歷】6、問題：2-3樹是一種特殊的樹，它滿足兩個條件：（1）每個內部結點有兩個或三個子結點；（2）所有的葉結點到根的路徑長度相同；如果一棵2-3樹有9個葉結點，那么它可能有_________個非葉結點。(多項)2-3treeisaspecialkindoftree,itsatisfy:（1）Everyinternalnodehas2or3childnodes.(2)Alltheleafnodeshavethesamelengthofthepathtotherootnode.Ifa2-3treehas9leafnodes,thenitmayhave__________non-leafnodes.（Therearemorethanonecorrectanswers）選項：A、4B、5C、6D、7正確答案:【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)}試回答下列問題：Pleaseanswerthesequesti