作業(yè)單元考核第七章二叉搜索樹第八章高級(jí)搜索樹（上）第八章高級(jí)搜索樹（下）第九章詞典第十章優(yōu)先級(jí)隊(duì)列第十一章串（上）第十一章串（下）第十二章排序第七章二叉搜索樹單選題(1分)What'sthedifferencebetweenabinarysearchtreeandaregularbinarytree?二叉搜索樹之區(qū)別于普通的二叉樹在于：Eachnodeislessthanorequaltothenodesinitsrightsub-tree,whilebeinggreaterthanorequaltothenodesinitsleftsub-tree.任意節(jié)點(diǎn)均不大于其右子樹中的節(jié)點(diǎn)，不小于其左子樹中的節(jié)點(diǎn)Eachnodeislessthanorequaltoitsrightchild,whilebeinggreaterthanorequaltoitsleftchild任意節(jié)點(diǎn)均不大于其右孩子，不小于其左孩子Eachnode(excepttheroot)islessthanorequaltoitsparent除了根節(jié)點(diǎn)外所有節(jié)點(diǎn)均不大于其父親Thekeysarecomparable關(guān)鍵碼可以比較正確答案：A單選題(1分)Whichorderfortraversingabinarytreealwaysresultsinincreasingsequences?二叉搜索樹的何種遍歷序列是遞增的？pre-order先序in-order中序post-order后序hierachical層次正確答案：B單選題(1分)What'stheworst-casetimecomplexityforsearchinginaBSTwithnnodes?在含n個(gè)節(jié)點(diǎn)的BST中進(jìn)行查找的最壞時(shí)間復(fù)雜度為：正確答案：C單選題(1分)Thefollowingsequenceofnodesareencounteredwhensearchingfor13inthebinarysearchtree:在以上二叉查找樹中查找關(guān)鍵碼13，經(jīng)過的節(jié)點(diǎn)依次為：07-b-02_quiz16,11,1316,10,5,8,1316,10,11,15,13Thisisnotabinarysearchtree以上二叉樹根本不是二叉查找樹正確答案：C單選題(1分)ConsiderinsertingatargetelementeintoaBST.whenitfailstobefoundduringthesearch,whichnodedoes_hotcorrespondto?對(duì)BST進(jìn)行插入操作，對(duì)待插入的目標(biāo)元素e進(jìn)行查找后，若查找失敗，_hot指向的節(jié)點(diǎn)為：Thenodetobeinserted待插入的節(jié)點(diǎn)Theparentofeaftertheinsertione被插入后的父親Theleft-childofeaftertheinsertione被插入后的左孩子Theroot根節(jié)點(diǎn)正確答案：B單選題(1分)Whenatemptingtodeleteanodevofdegree2,what'stheactualnodebeingdeleted?當(dāng)欲刪除的節(jié)點(diǎn)v在BST中的度為2時(shí)，實(shí)際被刪除的節(jié)點(diǎn)為：v'sdirectpredecessorinthein-ordersequencev在中序遍歷下的直接前驅(qū)v'sdirectsuccessorinthepre-ordersequencev在先序遍歷下的直接后繼thelastnodeintheleftbranchofv'srightsub-treev的右子樹中左側(cè)分支的最后一個(gè)節(jié)點(diǎn)v'sparentv的父親正確答案：C單選題(1分)ABSThasnnodesandaheightofh.Whatistheworst-casetimecomplexityforsearchinginit?在含n個(gè)節(jié)點(diǎn)、高度為h的BST中進(jìn)行查找的最壞時(shí)間復(fù)雜度為：正確答案：A單選題(1分)ABSThasnnodesandaheightofh.ItisabalancedBSTif:含n個(gè)節(jié)點(diǎn)，高度為h的BST稱為平衡二叉搜索樹若它滿足：正確答案：C單選題(1分)TwoequivalentbalancedBSThaveidentical:兩個(gè)等價(jià)的平衡二叉搜索樹有相同的：pre-ordersequence先序遍歷序列in-ordersequence中序遍歷序列post-ordersequence后序遍歷序列hierachicalsequence層次遍歷序列正確答案：B單選題(1分)WhatisthemaximumnumberofimbalancednodesafterinsertinganodeinanAVLtree?在AVL樹中剛插入一個(gè)節(jié)點(diǎn)后失衡節(jié)點(diǎn)個(gè)數(shù)最多為O(1)O(lglgn)O(lgn)O(n)正確答案：C單選題(1分)WhatisthemaximumnumberofimbalancednodesafterdeletinganodeinanAVLtree?在AVL樹中剛刪除一個(gè)節(jié)點(diǎn)后失衡節(jié)點(diǎn)個(gè)數(shù)最多為O(1)O(lglgn)O(lgn)O(n)正確答案：A單選題(1分)TherootoftheAVLtreeabovehasabalancefactorof:以上AVL樹根節(jié)點(diǎn)的平衡因子為：07-d-02_quiz-1012正確答案：A填空題(1分)WhatistheminumumnumberofnodesinaAVLtreeofheight3?高度為3的AVL樹至少包含幾個(gè)節(jié)點(diǎn)？____<divdata-v-a6a09fb6=""class="input"><divdata-v-a6a09fb6=""class="inputCon"><divdata-v-a6a09fb6=""class="expandingAreareadonlyTK"><predata-v-a6a09fb6=""><spandata-v-a6a09fb6="">3<brdata-v-a6a09fb6=""></pre><textareadata-v-a6a09fb6=""type="text"placeholder=""readonly="readonly"rows="1"></textarea><spandata-v-a6a09fb6=""class="label"><spandata-v-a6a09fb6="">1<spandata-v-a6a09fb6=""class="line"><idata-v-a6a09fb6=""class="iconfontanother_statured"></i><pdata-v-a6a09fb6=""class="rightAnswer">正確答案:["7"]：?jiǎn)芜x題(1分)InsertingnodesintoanAVLtreecouldleadtoimbalance.Afterrebalancingthetreeviarotation,theheightofthesub-treescontainingnodeg,p,andvAVL樹中插入節(jié)點(diǎn)引發(fā)失衡，經(jīng)旋轉(zhuǎn)調(diào)整后重新平衡，此時(shí)包含節(jié)點(diǎn)g,p,v的子樹高度decreaseby1減小1remainthesame不變increaseby1增加1eitherremainthesameorincreaseby1有可能不變也有可能增加1正確答案：B單選題(1分)AVL樹中刪除節(jié)點(diǎn)引發(fā)失衡，經(jīng)旋轉(zhuǎn)調(diào)整后重新平衡，此時(shí)包含節(jié)點(diǎn)g,p,v的子樹高度減小1不變?cè)黾?有可能不變也有可能減小1正確答案：D單選題(1分)The_____ofanAVLtreeisinvariantunderthe3+4reconstruction.經(jīng)過3+4重構(gòu)后的AVL樹_____不變。pre-ordersequence先序遍歷序列in-ordersequence中序遍歷序列post-ordersequence后序遍歷序列hierachicalsequence層次遍歷序列正確答案：B單選題(1分)WhichofthefollowingisaBST?以下哪項(xiàng)是二叉搜索樹?PS7_Q1_APS7_Q1_CPS7_Q1_BPS7_Q1_D正確答案：B填空題(1分)What'sthenumberofdistinctBSTscontainingnodes{1,2,3,4}?包含節(jié)點(diǎn){1,2,3,4}的不同二叉搜索樹有多少棵？____1正確答案:["14"]填空題(1分)PS7_Q3Whatisthe3rdelementwecomparetowhensearchingfor14intheBSTabove?在以上二叉搜索樹中查找元素14，第3個(gè)和14發(fā)生比較的元素為：____正確答案:["11"]單選題(1分)PS7_Q3(1)Whatarethestepsfordeleting16?欲在以上二叉搜索樹中刪除節(jié)點(diǎn)16，可行的方案是：remove16,make25therightchildof10and10becomesthenewroot.將16摘除后令25為10的右子，從而10是新的根節(jié)點(diǎn)executeazigoperationon16makingitnolongertheroot,andthenremoveitdirectly以16為軸進(jìn)行一次zig操作使之不再是根節(jié)點(diǎn)，再直接摘除16exchangethekeyofnode16andnode33,andremovethenewnode16將節(jié)點(diǎn)16和節(jié)點(diǎn)33的關(guān)鍵碼互換，再摘除新的節(jié)點(diǎn)16exchangethekeyofnode16andnode15,removethenewnode16andmake13therightchildof11將節(jié)點(diǎn)16和節(jié)點(diǎn)15的關(guān)鍵碼互換，摘除新的節(jié)點(diǎn)16并令13為11的右子正確答案：D單選題(1分)ABSThasnnodesandaheightofh.Whichofthefollowingholds?二叉搜索樹的高度h和節(jié)點(diǎn)個(gè)數(shù)n滿足關(guān)系h=O(1)h=O(lgn)h=O(n)h=O(nlgn)正確答案：C單選題(1分)Whatistheworst-casetimecomplexityforsearchinginit?在其上進(jìn)行查找的最壞時(shí)間復(fù)雜度為O(1)O(lgn)O(n)O(nlgn)正確答案：C單選題(1分)Giventhatit'sabalancedBST,whichofthefollowingholds?若已知它是平衡二叉搜索樹，則n和h滿足關(guān)系h=O(1)h=O(lgn)h=O(n)h=O(nlgn)正確答案：B單選題(1分)thecomplexitybecomes在其上進(jìn)行查找的最壞時(shí)間復(fù)雜度為O(1)O(lgn)O(n)O(nlgn)正確答案：B單選題(1分)PS7_Q6GiventheBSTabove,whatistheresultafterazigoperationonnode19?對(duì)以上二叉搜索樹，以節(jié)點(diǎn)19為軸進(jìn)行一次zig操作后得到的樹為：PS7_Q6_APS7_Q6_BPS7_Q6_CPS7_Q6_D正確答案：B單選題(1分)WhatisthetimecomplexityforsearchinginanAVLtreewithnnodes?在包含n個(gè)節(jié)點(diǎn)的AVL樹中進(jìn)行查找的時(shí)間復(fù)雜度為O(1)O(lgn)O(n)O(nlgn)正確答案：B單選題(1分)Whataboutinsertinganode?插入的時(shí)間復(fù)雜度為O(1)O(lgn)O(n)O(nlgn)正確答案：B單選題(1分)Whataboutdeletinganode?刪除的時(shí)間復(fù)雜度為O(1)O(lgn)O(n)O(nlgn)正確答案：B單選題(1分)AfterinsertinganodeintoanAVLtreeandrebalancing,theheightoftherotatedsub-treeAVL樹中插入節(jié)點(diǎn)引發(fā)失衡，經(jīng)旋轉(zhuǎn)調(diào)整重新平衡后發(fā)生旋轉(zhuǎn)的子樹的高度decreaseby1減小1remainsthesameorincreaseby1不變或增加1remainsthesame不變r(jià)emainsthesameordecreaseby1不變或減小1正確答案：C單選題(1分)Whataboutthecasewhenanodeisdeleted?刪除節(jié)點(diǎn)的情況呢？decreaesby1減小1remainsthesameorincreaseby1不變或增加1remainsthesame不變r(jià)emainsthesameordecreaseby1不變或減小1正確答案：D單選題(1分)PS7_Q9TheAVLtreeaboveisimblancedbecausenode13wasjustinserted.Whichoneisthetreeafterrebalancing?以上AVL樹因?yàn)閯偛迦牍?jié)點(diǎn)13而失衡，利用課堂上所學(xué)重平衡算法，恢復(fù)平衡后的AVL樹為：PS7_Q9_APS7_Q9_BPS7_Q9_CPS7_Q9_D正確答案：A單選題(1分)PS7_Q10Choosethesub-treeafterapplying3+4reconstructiontothetreeabove.對(duì)以上子樹進(jìn)行3+4重構(gòu)，得到的子樹為：PS7_Q10_APS7_Q10_BPS7_Q10_CPS7_Q10_D正確答案：B第八章高級(jí)搜索樹（上）單選題(1分)Whichpropertyofdataaccessistakenadvantageofbysplaytrees?伸展樹利用了實(shí)際問題中數(shù)據(jù)訪問的何種特點(diǎn)：massiveness大量性locality局部性holisticity整體性diversity多樣性正確答案：B單選題(1分)Whichoperationisexecutedforeachaccessednodeinasplaytree?伸展樹每次訪問過某節(jié)點(diǎn)后都會(huì)把該節(jié)點(diǎn)：removingit刪除movingittothehigerlevel上移一層movingittotheroot移動(dòng)到根節(jié)點(diǎn)accessingitagain再次訪問該節(jié)點(diǎn)正確答案：C單選題(1分)InTarjan'salgorithm,howmanylayersaresplayedtogether?Tarjan提出的伸展算法每幾層一起伸展？1234正確答案：B單選題(1分)Asplaytreedegeneratesintoalist.What'sitsheightafteraccessingthelowestnode?在一棵退化成單鏈的伸展樹中訪問其最深的節(jié)點(diǎn)，經(jīng)過伸展后樹高大約為原先的：onethirdoftheoriginalheight三分之一halfoftheoriginalheight一半theoriginalheight不變twicetheoriginalheight兩倍正確答案：B單選題(1分)What'stheamortizedcomplexityforasinglesplayoperationinTarjan'salgorithm?按照Tarjan的伸展算法，單次伸展操作的分?jǐn)倧?fù)雜度為：O(1)O(lgn)O(n)O(nlgn)正確答案：B單選題(1分)Thenodeaccessedisaright-child,andsoisitsparent.Whatshouldwedoforasinglesplayoperation?所訪問的節(jié)點(diǎn)及其父親都是右孩子，則雙層伸展要執(zhí)行的操作是：zig-zagzag-zigzig-zigzag-zag正確答案：D單選題(1分)What'stheamortizedcomplexityinasufficientlylongsequenceofaccessingknodesinasplaytreeofsizen?規(guī)模為n的伸展樹中若所訪問的節(jié)點(diǎn)只有k個(gè)，經(jīng)過足夠長時(shí)間的訪問序列后，訪問的分?jǐn)倧?fù)雜度為：-未答復(fù)O(lgk)O(klgn)O(nlgk)O(lgn)正確答案：A單選題(1分)Whydoesthememorybecomessmallerandsmaller?內(nèi)存“越來越小”的原因是：Withmoreandmoreprocessesrunningononecomputer,theaveragememroysizeforeachprocessisgettingsmaller機(jī)器上運(yùn)行的程序越來越多，平均每個(gè)程序使用的內(nèi)存變小Thereal-worldapplicationscallforrocketingmemorystorage實(shí)際應(yīng)用對(duì)存儲(chǔ)的需求急劇增長Thesiliconusedforproducingchipsissoonrunningout用于制造內(nèi)存芯片的硅資源消耗殆盡Thephysicalsizeofmemorychipsisgettingsmallerthankstotheadvancesintechnology隨著工藝的進(jìn)步，內(nèi)存的體積變小，集成度變高正確答案：B單選題(1分)Ifitwouldtakeusasecondforasinglememoryaccess,howlongwoulditcostforasingleaccesstotheexternalstorage?如果說訪問一次內(nèi)存需要1秒，則一次外存訪問大概需要：ahour1小時(shí)aday1天amonth1月ayear1年正確答案：B單選題(1分)B-treesare樹結(jié)構(gòu)上的特點(diǎn)是：shortandchubby,witheachnodehavingatmosttwochildren矮胖，每個(gè)節(jié)點(diǎn)至多兩個(gè)孩子shortandchubby,witheachnodehavingpotentiallymanychildren矮胖，每個(gè)節(jié)點(diǎn)可有多于兩個(gè)孩子tallandslim,witheachnodehavingatmosttwochildren瘦高，每個(gè)節(jié)點(diǎn)至多兩個(gè)孩子tallandslim,witheachnodehavingpotentiallymanychildren瘦高，每個(gè)節(jié)點(diǎn)可有多于兩個(gè)孩子正確答案：B單選題(1分)B-treeshavesmallheightsoastoB樹的層數(shù)少有助于：reducethenumberofI/Ooperations減少I/O次數(shù)reducethetimeconsumptionforasingleI/O減少每次I/O的時(shí)間reducetheasymptotictimecomplexityforseaching降低查找的漸進(jìn)時(shí)間復(fù)雜度reducethestoragerequirement節(jié)省存儲(chǔ)空間正確答案：A單選題(1分)HowmanychildrenarethereforeachnodeinaB-treeoforder4?4階B樹中每個(gè)節(jié)點(diǎn)的分支數(shù)為：1~42~52~43~5正確答案：C單選題(1分)What'sthetimecomplexityforsearchinginaB-treeoforder4andsizen?在存儲(chǔ)了n個(gè)元素的4階B樹中查找，單個(gè)節(jié)點(diǎn)進(jìn)行一次查找的時(shí)間復(fù)雜度為：O(1)O(lgn)O(n)O(nlgn)正確答案：A單選題(1分)What'sthereturnvalueforafailedsearchinaB-treeoforder4?B樹查找算法若最終失敗，返回值為：NoneNULLApointertothelastexaminednode指向最后一個(gè)所查找節(jié)點(diǎn)的指針Apointertotheroot指向根節(jié)點(diǎn)的指針正確答案：B單選題(1分)What'stheheightofaB-treeoforder128relativetoacorrespondingBBST?若B樹的階m=128，則它的高度大致是對(duì)應(yīng)的BBST的：1/51/61/71/8正確答案：B第八章高級(jí)搜索樹（下）單選題(1分)What'sthe'overflow'foraB-tree?B樹的上溢是指：ThepropertyofaB-treeisviolatedduetoremovingakey刪除關(guān)鍵碼后違反了B樹的性質(zhì)ThepropertyofaB-treeisviolatedduetoinsertingakey插入新的關(guān)鍵碼后違反了B樹的性質(zhì)ThepropertyofaB-treeisviolatedduetoasplit分裂后違反了B樹的性質(zhì)AB-treebecomestoohighB樹的高度過高正確答案：B單選題(1分)WhichconsequencefollowsasaB-treebecomeshigher?B樹高度的增加一定伴隨著：Eachnodehasalargernumberofkeys每個(gè)節(jié)點(diǎn)所存放的關(guān)鍵碼數(shù)量增加Eachnodehasasmallernumberofkeys每個(gè)節(jié)點(diǎn)所存放的關(guān)鍵碼數(shù)量減少Splittingtotheroot分裂到根Splittingtotheleaves分裂到葉正確答案：C單選題(1分)TheunderflowofaB-treehappenswhenB樹的下溢發(fā)生于：theheightofthetreedecreasesB樹高度減少thepropertyoftheB-treeisviolatedduetoinsertingakey插入關(guān)鍵碼后違反了B樹的性質(zhì)thepropertyoftheB-treeisviolatedduetodeletingakey刪除關(guān)鍵碼后違反了B樹的性質(zhì)insertingakeytoaleafnode在葉節(jié)點(diǎn)插入關(guān)鍵碼正確答案：C單選題(1分)TheheightofaB-treedecreasesonlywhenB樹高度的減少只會(huì)發(fā)生于mergingtwochildrenoftheroot根節(jié)點(diǎn)的兩個(gè)孩子合并removingtheroot根節(jié)點(diǎn)被刪除rotatingtheroot根節(jié)點(diǎn)發(fā)生旋轉(zhuǎn)therearemultiplekeysintheroot根節(jié)點(diǎn)有多個(gè)關(guān)鍵碼正確答案：A多選題(2分)Anodeinared-balcktreecouldbe紅黑樹節(jié)點(diǎn)的顏色有-未答red紅black黑yellow黃blue藍(lán)green綠purple紫正確答案：AB單選題(1分)What'suniqueaboutred-blacktreescomparedtoAVLtrees?紅黑樹相比于AVL樹的特點(diǎn)是：Thebalancefactorofeachnodefallswithin[-1,1]每個(gè)節(jié)點(diǎn)的平衡因子的絕對(duì)值不超過1Itisabalancedbinarysearchtree是平衡二叉搜索樹ThesearchtimeisO(lgn)支持O(lgn)時(shí)間的查找ThetopologychangesnomorethanO(1)aftereachinsertion/deletion每次插入/刪除后拓?fù)浣Y(jié)構(gòu)的變化不超過O(1)正確答案：D單選題(1分)Therootofared-blacktreeis紅黑樹的根節(jié)點(diǎn)的顏色是red紅black黑正確答案：B單選題(1分)Theexternalnodesare外部節(jié)點(diǎn)的顏色是red紅black黑正確答案：B填空題(1分)Ared-blacktreeisequivalenttoaB-treeoforder__紅黑樹等價(jià)于____階B樹:1正確答案:["4"]單選題(1分)Inared-blacktreeofsizen,theblackheightwouldn'texceed__規(guī)模為n的紅黑樹，黑高度不超過：O(1)O(lgn)O(n)O(nlgn)正確答案：B單選題(1分)Theheightwouldn'texceed__高度不超過：O(1)O(lgn)O(n)O(nlgn)正確答案：B單選題(1分)Whatisa'doublered'inared-blacktree?在紅黑樹中，何為雙紅缺陷：therootisred根節(jié)點(diǎn)為紅色boththerootandtheexternalnodesarered根節(jié)點(diǎn)和外部節(jié)點(diǎn)都為紅色bothaparentanditschildarered相鄰的兩個(gè)父子節(jié)點(diǎn)都為紅色therearetworednodesinthetree樹中有兩個(gè)紅色節(jié)點(diǎn)正確答案：C單選題(1分)Howdoesthetopologychangeswhenfixingadoubleredandtheunclenodeuisred.當(dāng)叔父節(jié)點(diǎn)u為紅色時(shí)，修正雙紅缺陷導(dǎo)致的紅黑樹拓?fù)浣Y(jié)構(gòu)的變化為：nochange沒有變化itchangesnomorethanO(1)有變化，但是不超過O(1)itchangesnomorethanO(lgn)有變化，但是不超過O(lgn)itchangesnomorethanO(n)有變化，但是不超過O(n)正確答案：A判斷題(1分)Splaytreeshavelargeworst-casetimecomplexityforasingleoperation,however,theyreducethenumberofI/Obyexploitinghierachicalstorage伸展樹雖然單次操作的最壞時(shí)間復(fù)雜度比較大，但是可以利用存儲(chǔ)器的層次結(jié)構(gòu)降低I/O的次數(shù)正確答案：×判斷題(1分)Splaytreesaredifficulttoimplement伸展樹相較于AVL樹的缺點(diǎn)是它實(shí)現(xiàn)起來較為復(fù)雜正確答案：×判斷題(1分)SplaytreeshavelargeramortizedcomplexitythanAVLtreesforinsertion伸展樹插入操作的分?jǐn)倧?fù)雜度比AVL樹大正確答案：×判斷題(1分)Splaytreeshavelargerworst-casetimecomplexitythanAVLtreesforsearching伸展樹單次查找操作的最壞時(shí)間復(fù)雜度比AVL樹大正確答案：√單選題(1分)PA8_Q2.pngThisisasplaytree.Whatistheresultafteraccessingnodevandperformingatwo-layersplay?上圖是伸展樹，其中節(jié)點(diǎn)v剛被訪問過，雙層伸展后的結(jié)果是：PA8_Q2_A.pngPA8_Q2_B.pngPA8_Q2_C.pngPA8_Q2_D.png正確答案：D單選題(1分)PA8_Q3.pngThisisasplaytree.What'stheresultafterinsertinganode1andperformingatwo-layersplay?在以上伸展樹中插入節(jié)點(diǎn)1并經(jīng)過雙層伸展后的結(jié)果是PA8_Q3_A.pngPA8_Q3_B.pngPA8_Q3_C.pngPA8_Q3_D.png正確答案：C單選題(1分)Whichstatementregarding(2,4)-treesisincorrect?關(guān)于(2,4)-樹，下列命題不正確的是：(2,4)-treesareequivalenttored-blacktrees(2,4)-樹等價(jià)于紅黑樹Eachinternalnodehasnomorethan4branches每個(gè)內(nèi)部節(jié)點(diǎn)的分支數(shù)不超過4Eachinternalnodehasnolessthan2branches每個(gè)內(nèi)部節(jié)點(diǎn)的分支數(shù)不小于2Eachnodehasexactly3keysexceptfortheroot除了根節(jié)點(diǎn)外，每個(gè)內(nèi)部節(jié)點(diǎn)都恰好包含3個(gè)關(guān)鍵碼正確答案：D單選題(1分)PA8_Q5.pngAnoverflowoccursafterinsertingnode52intoa(3,6)-tree,what'stheresultaftersplitting?上圖是(3,6)-樹中剛插入節(jié)點(diǎn)52后的情形，可以看出發(fā)生了上溢，分裂后的結(jié)果為：PA8_Q5_A.pngPA8_Q5_B.pngPA8_Q5_C.pngPA8_Q5_D.png正確答案：A單選題(1分)PA8_Q6.pngAnunderflowoccursafterremovinganodefroma(3,6)-tree,what'stheresultaftertheadjustment?上圖是(3,6)-樹中剛刪除某節(jié)點(diǎn)后的情形，可以看出發(fā)生了下溢，調(diào)整后的結(jié)果為：PA8_Q6_A.pngPA8_Q6_B.pngPA8_Q6_C.pngPA8_Q6_D.png正確答案：B單選題(1分)Whichstatementregardingred-blacktreesiswrong?以下關(guān)于紅黑樹的說法，錯(cuò)誤的是：-未答復(fù)Ared-blacktreeofsizenhasabalckheightofO(lgn),buttheheightisnotnecessarilyO(lgn)含n個(gè)節(jié)點(diǎn)的紅黑樹，其黑高度為O(lgn)，但是總的高度卻未必是O(lgn)Therecannotbetwoconsecutiverednodesinapathfromaexternalnodetotheroot從紅黑樹的任一外部節(jié)點(diǎn)上溯到根節(jié)點(diǎn)，沿途不可能經(jīng)過連續(xù)兩個(gè)紅色節(jié)點(diǎn)Theblackheightcannotbesmallerthanhalftheheight紅黑樹的黑高度一定不小于總高度的一半x(black)andy(black)aretwochildrenofablacknode.Theblackheightofthesub-treesxandymustequal.紅黑樹中的黑色節(jié)點(diǎn)u有黑色左孩子x和黑色右孩子y,則x與y的黑高度一定相等正確答案：A單選題(1分)PA8_Q8.pngWhat'stheresultafterfixingthedoublered?對(duì)上圖中紅黑樹的節(jié)點(diǎn)x進(jìn)行雙紅修正的結(jié)果是：PA8_Q8_A.pngPA8_Q8_B.pngPA8_Q8_C.pngPA8_Q8_D.png正確答案：C單選題(1分)Wichpropertycouldbeviolatedafterremovinganodeinared-blacktreeusingthealgorithmforBSTnoderemoval?在紅黑樹中直接按照常規(guī)的BST刪除節(jié)點(diǎn)算法刪除一個(gè)節(jié)點(diǎn)，關(guān)于紅黑樹結(jié)構(gòu)的四條性質(zhì)是否有可能被破壞？1、therootisbalck樹根必為黑色couldbeviolated有可能會(huì)被破壞won'tbeviolated不會(huì)被破壞正確答案：A單選題(1分)（接上題）2、theexternalnodesareblack外部節(jié)點(diǎn)必均為黑色couldbeviolated有可能會(huì)被破壞won'tbeviolated不會(huì)被破壞正確答案：B單選題(1分)（接上題）3、thechildrenofarednodeareblack紅色節(jié)點(diǎn)的孩子必為黑couldbeviolated有可能會(huì)被破壞won'tbeviolated不會(huì)被破壞正確答案：A單選題(1分)（接上題）4、thereareequalnumberofblacknodesineachpathfromaexternalnodetotheroot從根到外部節(jié)點(diǎn)的不同路徑途中黑色節(jié)點(diǎn)數(shù)目相等couldbeviolated有可能會(huì)被破壞won'tbeviolated不會(huì)被破壞正確答案：A單選題(1分)WeknowmanyBBSTsupuntilnow.至此，我們接觸了以下幾種平衡二叉搜索樹AVLtreesAVL樹Splaytrees伸展樹B-treesB-樹Red-blacktrees紅黑樹kd-trres(seePA3andthelecturenote)kd-樹（見PA3以及講義）PleasechooseaBBSTforeachofthwfollowingscenarios針對(duì)下列應(yīng)用的特點(diǎn)，請(qǐng)你選取最合適的平衡二叉搜索樹accessingmassiveamountofdata(whichcannotfitintothememory)對(duì)大規(guī)模的數(shù)據(jù)（不能全部存放于內(nèi)存中）的存取AVLtreesAVL樹Splaytrees伸展樹B-treesB-樹Red-blacktrees紅黑樹kd-trreskd-樹正確答案：C單選題(1分)（接上題）EasyimplementationandO(lgn)complexity需要易于實(shí)現(xiàn)，而且各接口的分?jǐn)倧?fù)雜度為O(lgn)AVLtreesAVL樹Splaytrees伸展樹B-treesB-樹Red-blacktreeskd-trreskd-樹正確答案：B單選題(1分)（接上題）Problemsrelatedtogeometry處理和幾何有關(guān)的問題AVLtreesAVL樹Splaytrees伸展樹B-treesB-樹Red-blacktrees紅黑樹kd-trreskd-樹正確答案：E單選題(1分)（接上題）Implementingaversioncontrolsystem擴(kuò)充后可支持對(duì)歷史版本的訪問AVLtreesAVL樹Splaytrees伸展樹B-treesB-樹Red-blacktrees紅黑樹kd-trreskd-樹正確答案：D第九章詞典填空題(1分)IfBaidudeterminesitsownphonenumberintheabovemanner,thenumberis百度(baidu)如果用以上方式確定自己的電話號(hào)碼，則號(hào)碼是____1正確答案:["22438"]單選題(1分)Theactualstoragelocationofthekeyis:關(guān)鍵碼key實(shí)際存放的位置是：keykey-1hash(key)hash(hash(key))正確答案：C單選題(1分)Ifthehashfunctionish(x)=x%20,thentheconflictsinthekeys25,85,15,20are:散列函數(shù)是h(x)=x%20，則關(guān)鍵碼25,85,15,20中會(huì)發(fā)生沖突的是：25和8525和1515和8520和15正確答案：A單選題(1分)Inthehash,ifthenumberofkeysexceedstheactualspaceused,isitpossibletoavoidconflict:在散列中，關(guān)鍵碼個(gè)數(shù)超過實(shí)際使用的空間時(shí)，有沒有可能不發(fā)生沖突：possible可能impossible不可能正確答案：B單選題(1分)Thehashfunctionh(x)=x%M,theMshouldbe:散列函數(shù)h(x)=x%M中的M應(yīng)該?。?Powerof22的冪Aprimenumber素?cái)?shù)Acompositenumber合數(shù)正確答案：C單選題(1分)MADis:MAD是:h(x)=1h(x)=xh(x)=(a*x+b)%Mh(x)=MAD正確答案：C單選題(1分)Thekeytypeforthepolynomialmethodis:多項(xiàng)式法適用的關(guān)鍵碼類型為：-Integer整數(shù)Float浮點(diǎn)數(shù)Char字符String字符串正確答案：D填空題(1分)Keytoimprovingyourprogrammingskills____1正確答案:["LearningTsinghuaDataStructures&Algorithms"]單選題(1分)Whichkindofdatastructurecanbeusedtosolvetheproblemofmultipleslotsmethod:用哪種數(shù)據(jù)結(jié)構(gòu)可以解決多槽位法的不足：Vector向量List列表Stack棧Queue隊(duì)列正確答案：B單選題(1分)Inalinearprobing,intheeventofaconflict,turntoprobe:在線性試探中，一旦發(fā)生沖突，轉(zhuǎn)而試探：Predecessorofcurrentposition當(dāng)前位置的前驅(qū)Succcessorofcurrentposition當(dāng)前位置的后繼Currentposition當(dāng)前位置Thenextelementinthelistofcurrentposition當(dāng)前位置的列表中的下一個(gè)元素正確答案：B單選題(1分)Usingthequadraticprobingmethod,thepositionsofthepreviousprobingsare0,1,4,9,andthepositionofthenextprobingis:(assumingthebucketarrayislargeenough)使用平方試探法，前幾次試探的位置是0,1,4,9，則下一次試探的位置是：（假設(shè)桶數(shù)組足夠大）9101516正確答案：D單選題(1分)Whenthelengthofthetableisprime,inordertomakethequadraticprobingalwayssuccessful,theloadfactorneedstobelessthan:當(dāng)表的長度為素?cái)?shù)時(shí)，為了使平方試探總是成功，裝填因子需要少于：10%50%80%100%正確答案：B單選題(1分)TherangeofvaluesofNelementstobesortedis[1,M].Thetimecomplexityofcountingsortis:N個(gè)待排序元素的取值范圍是[1,M]，計(jì)數(shù)排序的時(shí)間復(fù)雜度為：O(NlgN)O(N)O(M)O(M+N)正確答案：D單選題(1分)Sisthespaceofallpossibleentries,Aisthespaceofallavailableaddresses(|A|<|S|),hisahashfunction,then:S為所有可能詞條的空間，A為所有可用地址的空間（|A|<|S|），h是散列函數(shù)，則：hmapsfromStoA,itmustbeasurjectiveh從S映射到A，一定是滿射hmapsfromStoA,itcannotbeainjective從S映射到A，不可能是單射hmapsfromAtoS,itcannotbeasurjectiveh從A映射到S，不可能是滿射hmapsfromAtoS,itmustbeainjectiveh從A映射到S，一定是單射正確答案：B判斷題(1分)Inthehashtable,whatarethecharacteristicsofagoodhashfunctionh?在散列表中，一個(gè)好的散列函數(shù)h需要具有哪些特點(diǎn)？Itisainjective是單射正確答案：×判斷題(1分)（接上題）Rangecoversasmanyaddressesaspossible值域盡可能覆蓋更多的地址正確答案：√判斷題(1分)（接上題）Everytimewecalculatethevalueofhinthesameentry,wegetdifferentresults每次計(jì)算h在同一個(gè)詞條的取值，得到的結(jié)果均不同正確答案：×判斷題(1分)Itcanefficientlycalculatethefunctionvalueofangivenentry給定詞條，能夠高效地計(jì)算對(duì)應(yīng)的函數(shù)值正確答案：√判斷題(1分)（接上題）Fordifferententries,thedistributionoffunctionvaluesisasuniformaspossibletoavoidaggregation對(duì)于不同詞條，函數(shù)值的分布盡可能均勻，避免聚集正確答案：√判斷題(1分)（接上題）Unabletofindapairofconflictingentrieswithinareasonablecalculatingtime無法在合理的計(jì)算時(shí)間內(nèi)找到一對(duì)發(fā)生沖突的詞條正確答案：×填空題(2分)ConsiderthesetofkeysS={0,8,16,24,32,40,48,56,64}考慮key的集合S={0,8,16,24,32,40,48,56,64}Hashfunctionconstructedbydivisionmethod用除余法構(gòu)造的散列函數(shù)h1(key)=key%12h2(key)=key%11HowmanyelementsdoestherangeofSmappedbyh1has?h1將S映射到的值域有幾個(gè)元素？____HowmanyelementsdoestherangeofSmappedbyh2has?h2將S映射到的值域有幾個(gè)元素？____1正確答案:["3"]2正確答案:["9"]單選題(1分)Regardingthemethodofresolvingconflicts,whichofthefollowingstatementiscorrect:關(guān)于排解沖突的方法，以下說法正確的是：Usingseparatechainingmethodtoresolveconflicts,allentriesareactuallystoredinsidethebucketarray用獨(dú)立鏈法排解沖突，所有詞條的實(shí)際存放位置均在桶數(shù)組內(nèi)部Usingopenaddressingmethodtoresolveconflicts,theactualstoragelocationofanentryisnotnecessarilythecorrespondinghashfunctionvalue用開放定址排解沖突，詞條的實(shí)際存放位置不一定是對(duì)應(yīng)的散列函數(shù)值Usingopenaddressingtoresolveconflicts,entriesarestoredinalist用開放定址排解沖突，詞條被存放在列表中Aslongasthehashfunctionisdesignedproperly,itdoesnotnecessarilyneedtoresolveconflicts只要散列函數(shù)設(shè)計(jì)得當(dāng)，不一定需要排解沖突的策略正確答案：B單選題(1分)Thecurrentstateofthebucketarrayofsize11isA={*,*,*,*,*,0,15,26,*,5,9},where*meansemptybucket規(guī)模為11的桶數(shù)組當(dāng)前狀態(tài)為A={*,*,*,*,*,0,15,26,*,5,9}，其中*表示空桶Thehashfunctionish(key)=(3*key+5)%11散列函數(shù)為h(key)=(3*key+5)%11UsingOpenaddressing+Linearprobingtosolveconflicts用開放定址+線性試探排解沖突Inserttheentry4,itsactualstoragelocationis插入詞條4,它的實(shí)際存放位置是-未答復(fù)A[4]A[6]A[7]A[8]正確答案：D單選題(1分)Thecurrentstateofthebucketarrayofsize11isA={*,*,*,*,*,0,15,26,*,5,9},where*meansemptybucket規(guī)模為11的桶數(shù)組當(dāng)前狀態(tài)為A={*,*,*,*,*,0,15,26,*,5,9}，其中*表示空桶Thehashfunctionish(key)=(3*key+5)%11散列函數(shù)為h(key)=(3*key+5)%11UsingOpenaddressing+quadraticprobingtosolveconflicts用開放定址+平方試探排解沖突Inserttheentry4,itsactualstoragelocationis插入詞條4,它的實(shí)際存放位置是A[4]A[6]A[7]A[8]正確答案：A填空題(1分)Thesizeofthehashtableisaprimenumber.Usingopenaddressing+quadraticprobingtoresolveconflicts.Toensurethatnewentriescanbeinserted,theloadfactorofthehashtablecannotexceed(pleasefillindecimal).散列表的規(guī)模是素?cái)?shù)，用開放定址+平方試探法排解沖突，若要保證新的詞條能夠順利插入，散列表的裝填因子不能超過（請(qǐng)?zhí)钍M(jìn)制小數(shù)）____1正確答案:["0.5"]單選題(1分)Sortnintegersrangedin[0,M]bycountingsort,thetimecomplexityis用計(jì)數(shù)排序?qū)個(gè)[0,M)內(nèi)的整數(shù)進(jìn)行排序，時(shí)間復(fù)雜度為O(n+M)O(min{n,M})O(nlgn)O(n^2)正確答案：A單選題(1分)Sorttheintegers{10,4,2,9,3,1,2,2,4,9,8,5,9,10,7,6,9}in[0,11)bythecountingsort.TheAccum[]tableis:對(duì)[0,11)中的整數(shù){10,4,2,9,3,1,2,2,4,9,8,5,9,10,7,6,9}用計(jì)數(shù)排序，得到的accum[]表為：{0,1,3,1,2,1,1,1,1,4,2}{10,4,2,9,3,1,2,2,4,9,8,5,9,10,7,6,9}{0,1,4,5,7,8,9,10,11,15,17}{0,1,4,7,9,12,13,14,15,16,17}正確答案：C第十章優(yōu)先級(jí)隊(duì)列單選題(1分)Theaccessmodeofelementsinthepriorityqueueis:優(yōu)先級(jí)隊(duì)列中元素的訪問模式是：-未答復(fù)Smallerrankoneisfirstlyvisited.秩小者先訪問Biggerrankoneisfirstlyvisited.秩大者先訪問Higherpriorityoneisfirstlyvisited.優(yōu)先級(jí)高者先訪問Front-locatedelementisfirstlyvisited位置靠前者先訪問正確答案：C單選題(1分)TheroleofdelMax()inthepriorityqueueis:優(yōu)先級(jí)隊(duì)列的delMax()的作用是：Deletethelargestelement.刪除最大的元素Deletetheelementwithhighestpriority.刪除優(yōu)先級(jí)最大的元素Deletethefirstelement.刪除首元素Deletethelastelement.刪除末元素正確答案：B單選題(1分)WhydoweusuallynotuseBBSTtoimplementpriorityqueue?為什么我們通常不用BBST實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列？Timeefficiencyisnothighenough時(shí)間效率不夠高BBSTistoocomplexforsimplefunctionsinpriorityqueues對(duì)于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的簡(jiǎn)單功能來說，BBST過于復(fù)雜BBSTisnotwhatwearegoingtolearninthischapter.我們本章要學(xué)的不是BBSTThevectorismoreefficient向量的效率更高正確答案：B單選題(1分)Onewaytoimplementpriorityqueuesis:優(yōu)先級(jí)隊(duì)列的一種實(shí)現(xiàn)方式是：Logically,equivalentto邏輯上，等同于vector向量stack棧Truebinarytree真二叉樹Completebinarytree完全二叉樹正確答案：D單選題(1分)（接上題）Physically,equivalentto物理上，等同于vector向量stack棧Truebinarytree真二叉樹Completebinarytree完全二叉樹正確答案：A單選題(1分)Theparentnode'spriorityinacompletebinaryheap完全二叉堆中父節(jié)點(diǎn)的優(yōu)先級(jí)Notsmallerthanitschildren不小于它的孩子Notequaltotheirchildren不等于它的孩子Thereisnonecessaryrelationshipwithitschildrenonsize和它的孩子沒有必然的大小關(guān)系Equaltoitschildren.等于它的孩子正確答案：A單選題(1分)Themethodforinsertingelementsinafullbinaryheapis在完全二叉堆中插入元素的方法是Insertintothebottom,percolateUp插入到底層，上濾Insertintotheroot,percolateDown插入到根節(jié)點(diǎn)，下濾Insertintothebottomdirectly直接插入到底層Insertintotherootdirectly直接插入到根節(jié)點(diǎn)正確答案：A單選題(1分)Thetimecomplexityofinsertingelementsinacompletebinaryheapofsizenis:規(guī)模為n的完全二叉堆中插入元素的時(shí)間復(fù)雜度為：-未答復(fù)O(nlgn)O(n)O(lgn)O(1)正確答案：C單選題(1分)Whenyouwanttodeleteanelementinacompletebinaryheap,thepositionofthiselementis:完全二叉堆中要?jiǎng)h除一個(gè)元素時(shí)，這個(gè)元素的位置是：-未答root根節(jié)點(diǎn)leaf葉子節(jié)點(diǎn)Canbeanynode可以是任意節(jié)點(diǎn)Rootnodeorleafnode根節(jié)點(diǎn)或葉子節(jié)點(diǎn)正確答案：A單選題(1分)Thetimecomplexityofdeletingelementsinacompletebinaryheapofsizenis:規(guī)模為n的完全二叉堆中刪除元素的時(shí)間復(fù)雜度為：-未答O(nlgn)O(n)O(lgn)O(1)正確答案：C單選題(1分)Usingatop-downupperfiltertobuildacompletebinaryheapofsizen,theworst-casetimecomplexityis:使用自上而下的上濾建立規(guī)模為n的完全二叉堆，最壞時(shí)間復(fù)雜度為：-未O(nlgn)O(n)O(lgn)O(1)正確答案：A單選題(1分)ThetimecomplexityofbuildingacompletebinaryheapofsizenbytheFloydbuild-heapalgorithmis:Floyd建堆算法建立規(guī)模為n的完全二叉堆的時(shí)間復(fù)雜度為：O(nlgn)O(n)O(lgn)O(1)正確答案：B單選題(1分)Howtousetheheaptosort:如何用堆來實(shí)現(xiàn)排序：-未答ContinuetocalldelMax()afterbuildingaheap建堆后不斷調(diào)用delMax()ContinuetocallgetMax()afterbuildingaheap建堆后不斷調(diào)用getMax()Continuetocallinsert()afterbuildingaheap建堆后不斷調(diào)用insert()Buildtheheap建堆正確答案：A單選題(1分)Themeaningoftheleftheaprelativetoafullbinaryheapis:相對(duì)于完全二叉堆，左式堆存在的意義是：Moreefficientinsertion高效的插入Moreefficientdeletion高效的刪除Moreefficientmergence高效的合并Moreefficientsearch高效的查找正確答案：C單選題(1分)Themeaningofleftis左傾的意義是Therightchild'sNPLofanynodedoesnotexceedtheleftchild任何節(jié)點(diǎn)右孩子的NPL不超過左孩子Therightchild'sNPLofanynodeisnotsmallerthantheleftchild任何節(jié)點(diǎn)右孩子的NPL不小于左孩子Therootnode'srightchild'sNPLdoesnotexceedtheleftchild's根節(jié)點(diǎn)右孩子的NPL不超過左孩子Therootnode'sleftchild'sNPLdoesnotexceedtherightchild根節(jié)點(diǎn)左孩子的NPL不超過右孩子正確答案：A單選題(1分)CombiningtheleftistheapsAandtheleftistheapsB,wherethelargestelementofAisgreaterthanallelementsinB,therecursivestepsare:合并左式堆A和左式堆B，其中A的最大元素比B中所有元素都大，則遞歸的步驟為：MergeA'sleftchildheapandB合并A的左子堆和BMergeA'srightchildheapandB合并A的右子堆和BMergeB'sleftchildheapandB合并B的左子堆和AMergeB'srightchildheapandB合并B的右子堆和A正確答案：B單選題(1分)Whichofthefollowingdatastructuresisusedtoimplementthepriorityqueue'sinsert,getMax,anddelMaxinterfacestoachieveO(lgn)timecomplexity?使用以下哪種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的insert,getMax,delMax接口均可達(dá)到O(lgn)的時(shí)間復(fù)雜度？-未答復(fù)vector向量orderedvector有序向量Hashtable散列表Balancedbinarysearchtree平衡二叉搜索樹正確答案：D單選題(1分)Thestackisaspecialcaseofpriorityqueueswheretheelement'spriorityis:棧作為優(yōu)先級(jí)隊(duì)列的一種特殊情況，其中元素的優(yōu)先級(jí)：Earliertheelementispushedintothestack,thepriorityofitwillbelower.先入棧者優(yōu)先級(jí)低Elementswhoispushedintothestackearlierhashigherpriority.先入棧者優(yōu)先級(jí)高Allelementshavethesamepriority所有元素優(yōu)先級(jí)相同Thereisnodefiniterelationshipbetweenelementpriorities元素優(yōu)先級(jí)之間沒有確定的關(guān)系正確答案：A單選題(1分)Theoverallfo