雨课堂在线学堂《数据结构（下）》课后作业单元考核答案

作业单元考核第七章二叉搜索树第八章高级搜索树（上）第八章高级搜索树（下）第九章词典第十章优先级队列第十一章串（上）第十一章串（下）第十二章排序第七章二叉搜索树单选题(1分)What'sthedifferencebetweenabinarysearchtreeandaregularbinarytree?二叉搜索树之区别于普通的二叉树在于：Eachnodeislessthanorequaltothenodesinitsrightsub-tree,whilebeinggreaterthanorequaltothenodesinitsleftsub-tree.任意节点均不大于其右子树中的节点，不小于其左子树中的节点Eachnodeislessthanorequaltoitsrightchild,whilebeinggreaterthanorequaltoitsleftchild任意节点均不大于其右孩子，不小于其左孩子Eachnode(excepttheroot)islessthanorequaltoitsparent除了根节点外所有节点均不大于其父亲Thekeysarecomparable关键码可以比较正确答案：A单选题(1分)Whichorderfortraversingabinarytreealwaysresultsinincreasingsequences?二叉搜索树的何种遍历序列是递增的？pre-order先序in-order中序post-order后序hierachical层次正确答案：B单选题(1分)What'stheworst-casetimecomplexityforsearchinginaBSTwithnnodes?在含n个节点的BST中进行查找的最坏时间复杂度为：正确答案：C单选题(1分)Thefollowingsequenceofnodesareencounteredwhensearchingfor13inthebinarysearchtree:在以上二叉查找树中查找关键码13，经过的节点依次为：07-b-02_quiz16,11,1316,10,5,8,1316,10,11,15,13Thisisnotabinarysearchtree以上二叉树根本不是二叉查找树正确答案：C单选题(1分)ConsiderinsertingatargetelementeintoaBST.whenitfailstobefoundduringthesearch,whichnodedoes_hotcorrespondto?对BST进行插入操作，对待插入的目标元素e进行查找后，若查找失败，_hot指向的节点为：Thenodetobeinserted待插入的节点Theparentofeaftertheinsertione被插入后的父亲Theleft-childofeaftertheinsertione被插入后的左孩子Theroot根节点正确答案：B单选题(1分)Whenatemptingtodeleteanodevofdegree2,what'stheactualnodebeingdeleted?当欲删除的节点v在BST中的度为2时，实际被删除的节点为：v'sdirectpredecessorinthein-ordersequencev在中序遍历下的直接前驱v'sdirectsuccessorinthepre-ordersequencev在先序遍历下的直接后继thelastnodeintheleftbranchofv'srightsub-treev的右子树中左侧分支的最后一个节点v'sparentv的父亲正确答案：C单选题(1分)ABSThasnnodesandaheightofh.Whatistheworst-casetimecomplexityforsearchinginit?在含n个节点、高度为h的BST中进行查找的最坏时间复杂度为：正确答案：A单选题(1分)ABSThasnnodesandaheightofh.ItisabalancedBSTif:含n个节点，高度为h的BST称为平衡二叉搜索树若它满足：正确答案：C单选题(1分)TwoequivalentbalancedBSThaveidentical:两个等价的平衡二叉搜索树有相同的：pre-ordersequence先序遍历序列in-ordersequence中序遍历序列post-ordersequence后序遍历序列hierachicalsequence层次遍历序列正确答案：B单选题(1分)WhatisthemaximumnumberofimbalancednodesafterinsertinganodeinanAVLtree?在AVL树中刚插入一个节点后失衡节点个数最多为O(1)O(lglgn)O(lgn)O(n)正确答案：C单选题(1分)WhatisthemaximumnumberofimbalancednodesafterdeletinganodeinanAVLtree?在AVL树中刚删除一个节点后失衡节点个数最多为O(1)O(lglgn)O(lgn)O(n)正确答案：A单选题(1分)TherootoftheAVLtreeabovehasabalancefactorof:以上AVL树根节点的平衡因子为：07-d-02_quiz-1012正确答案：A填空题(1分)WhatistheminumumnumberofnodesinaAVLtreeofheight3?高度为3的AVL树至少包含几个节点？____<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"]：单选题(1分)InsertingnodesintoanAVLtreecouldleadtoimbalance.Afterrebalancingthetreeviarotation,theheightofthesub-treescontainingnodeg,p,andvAVL树中插入节点引发失衡，经旋转调整后重新平衡，此时包含节点g,p,v的子树高度decreaseby1减小1remainthesame不变increaseby1增加1eitherremainthesameorincreaseby1有可能不变也有可能增加1正确答案：B单选题(1分)AVL树中删除节点引发失衡，经旋转调整后重新平衡，此时包含节点g,p,v的子树高度减小1不变增加1有可能不变也有可能减小1正确答案：D单选题(1分)The_____ofanAVLtreeisinvariantunderthe3+4reconstruction.经过3+4重构后的AVL树_____不变。pre-ordersequence先序遍历序列in-ordersequence中序遍历序列post-ordersequence后序遍历序列hierachicalsequence层次遍历序列正确答案：B单选题(1分)WhichofthefollowingisaBST?以下哪项是二叉搜索树?PS7_Q1_APS7_Q1_CPS7_Q1_BPS7_Q1_D正确答案：B填空题(1分)What'sthenumberofdistinctBSTscontainingnodes{1,2,3,4}?包含节点{1,2,3,4}的不同二叉搜索树有多少棵？____1正确答案:["14"]填空题(1分)PS7_Q3Whatisthe3rdelementwecomparetowhensearchingfor14intheBSTabove?在以上二叉搜索树中查找元素14，第3个和14发生比较的元素为：____正确答案:["11"]单选题(1分)PS7_Q3(1)Whatarethestepsfordeleting16?欲在以上二叉搜索树中删除节点16，可行的方案是：remove16,make25therightchildof10and10becomesthenewroot.将16摘除后令25为10的右子，从而10是新的根节点executeazigoperationon16makingitnolongertheroot,andthenremoveitdirectly以16为轴进行一次zig操作使之不再是根节点，再直接摘除16exchangethekeyofnode16andnode33,andremovethenewnode16将节点16和节点33的关键码互换，再摘除新的节点16exchangethekeyofnode16andnode15,removethenewnode16andmake13therightchildof11将节点16和节点15的关键码互换，摘除新的节点16并令13为11的右子正确答案：D单选题(1分)ABSThasnnodesandaheightofh.Whichofthefollowingholds?二叉搜索树的高度h和节点个数n满足关系h=O(1)h=O(lgn)h=O(n)h=O(nlgn)正确答案：C单选题(1分)Whatistheworst-casetimecomplexityforsearchinginit?在其上进行查找的最坏时间复杂度为O(1)O(lgn)O(n)O(nlgn)正确答案：C单选题(1分)Giventhatit'sabalancedBST,whichofthefollowingholds?若已知它是平衡二叉搜索树，则n和h满足关系h=O(1)h=O(lgn)h=O(n)h=O(nlgn)正确答案：B单选题(1分)thecomplexitybecomes在其上进行查找的最坏时间复杂度为O(1)O(lgn)O(n)O(nlgn)正确答案：B单选题(1分)PS7_Q6GiventheBSTabove,whatistheresultafterazigoperationonnode19?对以上二叉搜索树，以节点19为轴进行一次zig操作后得到的树为：PS7_Q6_APS7_Q6_BPS7_Q6_CPS7_Q6_D正确答案：B单选题(1分)WhatisthetimecomplexityforsearchinginanAVLtreewithnnodes?在包含n个节点的AVL树中进行查找的时间复杂度为O(1)O(lgn)O(n)O(nlgn)正确答案：B单选题(1分)Whataboutinsertinganode?插入的时间复杂度为O(1)O(lgn)O(n)O(nlgn)正确答案：B单选题(1分)Whataboutdeletinganode?删除的时间复杂度为O(1)O(lgn)O(n)O(nlgn)正确答案：B单选题(1分)AfterinsertinganodeintoanAVLtreeandrebalancing,theheightoftherotatedsub-treeAVL树中插入节点引发失衡，经旋转调整重新平衡后发生旋转的子树的高度decreaseby1减小1remainsthesameorincreaseby1不变或增加1remainsthesame不变remainsthesameordecreaseby1不变或减小1正确答案：C单选题(1分)Whataboutthecasewhenanodeisdeleted?删除节点的情况呢？decreaesby1减小1remainsthesameorincreaseby1不变或增加1remainsthesame不变remainsthesameordecreaseby1不变或减小1正确答案：D单选题(1分)PS7_Q9TheAVLtreeaboveisimblancedbecausenode13wasjustinserted.Whichoneisthetreeafterrebalancing?以上AVL树因为刚插入节点13而失衡，利用课堂上所学重平衡算法，恢复平衡后的AVL树为：PS7_Q9_APS7_Q9_BPS7_Q9_CPS7_Q9_D正确答案：A单选题(1分)PS7_Q10Choosethesub-treeafterapplying3+4reconstructiontothetreeabove.对以上子树进行3+4重构，得到的子树为：PS7_Q10_APS7_Q10_BPS7_Q10_CPS7_Q10_D正确答案：B第八章高级搜索树（上）单选题(1分)Whichpropertyofdataaccessistakenadvantageofbysplaytrees?伸展树利用了实际问题中数据访问的何种特点：massiveness大量性locality局部性holisticity整体性diversity多样性正确答案：B单选题(1分)Whichoperationisexecutedforeachaccessednodeinasplaytree?伸展树每次访问过某节点后都会把该节点：removingit删除movingittothehigerlevel上移一层movingittotheroot移动到根节点accessingitagain再次访问该节点正确答案：C单选题(1分)InTarjan'salgorithm,howmanylayersaresplayedtogether?Tarjan提出的伸展算法每几层一起伸展？1234正确答案：B单选题(1分)Asplaytreedegeneratesintoalist.What'sitsheightafteraccessingthelowestnode?在一棵退化成单链的伸展树中访问其最深的节点，经过伸展后树高大约为原先的：onethirdoftheoriginalheight三分之一halfoftheoriginalheight一半theoriginalheight不变twicetheoriginalheight两倍正确答案：B单选题(1分)What'stheamortizedcomplexityforasinglesplayoperationinTarjan'salgorithm?按照Tarjan的伸展算法，单次伸展操作的分摊复杂度为：O(1)O(lgn)O(n)O(nlgn)正确答案：B单选题(1分)Thenodeaccessedisaright-child,andsoisitsparent.Whatshouldwedoforasinglesplayoperation?所访问的节点及其父亲都是右孩子，则双层伸展要执行的操作是：zig-zagzag-zigzig-zigzag-zag正确答案：D单选题(1分)What'stheamortizedcomplexityinasufficientlylongsequenceofaccessingknodesinasplaytreeofsizen?规模为n的伸展树中若所访问的节点只有k个，经过足够长时间的访问序列后，访问的分摊复杂度为：-未答复O(lgk)O(klgn)O(nlgk)O(lgn)正确答案：A单选题(1分)Whydoesthememorybecomessmallerandsmaller?内存“越来越小”的原因是：Withmoreandmoreprocessesrunningononecomputer,theaveragememroysizeforeachprocessisgettingsmaller机器上运行的程序越来越多，平均每个程序使用的内存变小Thereal-worldapplicationscallforrocketingmemorystorage实际应用对存储的需求急剧增长Thesiliconusedforproducingchipsissoonrunningout用于制造内存芯片的硅资源消耗殆尽Thephysicalsizeofmemorychipsisgettingsmallerthankstotheadvancesintechnology随着工艺的进步，内存的体积变小，集成度变高正确答案：B单选题(1分)Ifitwouldtakeusasecondforasinglememoryaccess,howlongwoulditcostforasingleaccesstotheexternalstorage?如果说访问一次内存需要1秒，则一次外存访问大概需要：ahour1小时aday1天amonth1月ayear1年正确答案：B单选题(1分)B-treesare树结构上的特点是：shortandchubby,witheachnodehavingatmosttwochildren矮胖，每个节点至多两个孩子shortandchubby,witheachnodehavingpotentiallymanychildren矮胖，每个节点可有多于两个孩子tallandslim,witheachnodehavingatmosttwochildren瘦高，每个节点至多两个孩子tallandslim,witheachnodehavingpotentiallymanychildren瘦高，每个节点可有多于两个孩子正确答案：B单选题(1分)B-treeshavesmallheightsoastoB树的层数少有助于：reducethenumberofI/Ooperations减少I/O次数reducethetimeconsumptionforasingleI/O减少每次I/O的时间reducetheasymptotictimecomplexityforseaching降低查找的渐进时间复杂度reducethestoragerequirement节省存储空间正确答案：A单选题(1分)HowmanychildrenarethereforeachnodeinaB-treeoforder4?4阶B树中每个节点的分支数为：1~42~52~43~5正确答案：C单选题(1分)What'sthetimecomplexityforsearchinginaB-treeoforder4andsizen?在存储了n个元素的4阶B树中查找，单个节点进行一次查找的时间复杂度为：O(1)O(lgn)O(n)O(nlgn)正确答案：A单选题(1分)What'sthereturnvalueforafailedsearchinaB-treeoforder4?B树查找算法若最终失败，返回值为：NoneNULLApointertothelastexaminednode指向最后一个所查找节点的指针Apointertotheroot指向根节点的指针正确答案：B单选题(1分)What'stheheightofaB-treeoforder128relativetoacorrespondingBBST?若B树的阶m=128，则它的高度大致是对应的BBST的：1/51/61/71/8正确答案：B第八章高级搜索树（下）单选题(1分)What'sthe'overflow'foraB-tree?B树的上溢是指：ThepropertyofaB-treeisviolatedduetoremovingakey删除关键码后违反了B树的性质ThepropertyofaB-treeisviolatedduetoinsertingakey插入新的关键码后违反了B树的性质ThepropertyofaB-treeisviolatedduetoasplit分裂后违反了B树的性质AB-treebecomestoohighB树的高度过高正确答案：B单选题(1分)WhichconsequencefollowsasaB-treebecomeshigher?B树高度的增加一定伴随着：Eachnodehasalargernumberofkeys每个节点所存放的关键码数量增加Eachnodehasasmallernumberofkeys每个节点所存放的关键码数量减少Splittingtotheroot分裂到根Splittingtotheleaves分裂到叶正确答案：C单选题(1分)TheunderflowofaB-treehappenswhenB树的下溢发生于：theheightofthetreedecreasesB树高度减少thepropertyoftheB-treeisviolatedduetoinsertingakey插入关键码后违反了B树的性质thepropertyoftheB-treeisviolatedduetodeletingakey删除关键码后违反了B树的性质insertingakeytoaleafnode在叶节点插入关键码正确答案：C单选题(1分)TheheightofaB-treedecreasesonlywhenB树高度的减少只会发生于mergingtwochildrenoftheroot根节点的两个孩子合并removingtheroot根节点被删除rotatingtheroot根节点发生旋转therearemultiplekeysintheroot根节点有多个关键码正确答案：A多选题(2分)Anodeinared-balcktreecouldbe红黑树节点的颜色有-未答red红black黑yellow黄blue蓝green绿purple紫正确答案：AB单选题(1分)What'suniqueaboutred-blacktreescomparedtoAVLtrees?红黑树相比于AVL树的特点是：Thebalancefactorofeachnodefallswithin[-1,1]每个节点的平衡因子的绝对值不超过1Itisabalancedbinarysearchtree是平衡二叉搜索树ThesearchtimeisO(lgn)支持O(lgn)时间的查找ThetopologychangesnomorethanO(1)aftereachinsertion/deletion每次插入/删除后拓扑结构的变化不超过O(1)正确答案：D单选题(1分)Therootofared-blacktreeis红黑树的根节点的颜色是red红black黑正确答案：B单选题(1分)Theexternalnodesare外部节点的颜色是red红black黑正确答案：B填空题(1分)Ared-blacktreeisequivalenttoaB-treeoforder__红黑树等价于____阶B树:1正确答案:["4"]单选题(1分)Inared-blacktreeofsizen,theblackheightwouldn'texceed__规模为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根节点为红色boththerootandtheexternalnodesarered根节点和外部节点都为红色bothaparentanditschildarered相邻的两个父子节点都为红色therearetworednodesinthetree树中有两个红色节点正确答案：C单选题(1分)Howdoesthetopologychangeswhenfixingadoubleredandtheunclenodeuisred.当叔父节点u为红色时，修正双红缺陷导致的红黑树拓扑结构的变化为：nochange没有变化itchangesnomorethanO(1)有变化，但是不超过O(1)itchangesnomorethanO(lgn)有变化，但是不超过O(lgn)itchangesnomorethanO(n)有变化，但是不超过O(n)正确答案：A判断题(1分)Splaytreeshavelargeworst-casetimecomplexityforasingleoperation,however,theyreducethenumberofI/Obyexploitinghierachicalstorage伸展树虽然单次操作的最坏时间复杂度比较大，但是可以利用存储器的层次结构降低I/O的次数正确答案：×判断题(1分)Splaytreesaredifficulttoimplement伸展树相较于AVL树的缺点是它实现起来较为复杂正确答案：×判断题(1分)SplaytreeshavelargeramortizedcomplexitythanAVLtreesforinsertion伸展树插入操作的分摊复杂度比AVL树大正确答案：×判断题(1分)Splaytreeshavelargerworst-casetimecomplexitythanAVLtreesforsearching伸展树单次查找操作的最坏时间复杂度比AVL树大正确答案：√单选题(1分)PA8_Q2.pngThisisasplaytree.Whatistheresultafteraccessingnodevandperformingatwo-layersplay?上图是伸展树，其中节点v刚被访问过，双层伸展后的结果是：PA8_Q2_A.pngPA8_Q2_B.pngPA8_Q2_C.pngPA8_Q2_D.png正确答案：D单选题(1分)PA8_Q3.pngThisisasplaytree.What'stheresultafterinsertinganode1andperformingatwo-layersplay?在以上伸展树中插入节点1并经过双层伸展后的结果是PA8_Q3_A.pngPA8_Q3_B.pngPA8_Q3_C.pngPA8_Q3_D.png正确答案：C单选题(1分)Whichstatementregarding(2,4)-treesisincorrect?关于(2,4)-树，下列命题不正确的是：(2,4)-treesareequivalenttored-blacktrees(2,4)-树等价于红黑树Eachinternalnodehasnomorethan4branches每个内部节点的分支数不超过4Eachinternalnodehasnolessthan2branches每个内部节点的分支数不小于2Eachnodehasexactly3keysexceptfortheroot除了根节点外，每个内部节点都恰好包含3个关键码正确答案：D单选题(1分)PA8_Q5.pngAnoverflowoccursafterinsertingnode52intoa(3,6)-tree,what'stheresultaftersplitting?上图是(3,6)-树中刚插入节点52后的情形，可以看出发生了上溢，分裂后的结果为：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)-树中刚删除某节点后的情形，可以看出发生了下溢，调整后的结果为：PA8_Q6_A.pngPA8_Q6_B.pngPA8_Q6_C.pngPA8_Q6_D.png正确答案：B单选题(1分)Whichstatementregardingred-blacktreesiswrong?以下关于红黑树的说法，错误的是：-未答复Ared-blacktreeofsizenhasabalckheightofO(lgn),buttheheightisnotnecessarilyO(lgn)含n个节点的红黑树，其黑高度为O(lgn)，但是总的高度却未必是O(lgn)Therecannotbetwoconsecutiverednodesinapathfromaexternalnodetotheroot从红黑树的任一外部节点上溯到根节点，沿途不可能经过连续两个红色节点Theblackheightcannotbesmallerthanhalftheheight红黑树的黑高度一定不小于总高度的一半x(black)andy(black)aretwochildrenofablacknode.Theblackheightofthesub-treesxandymustequal.红黑树中的黑色节点u有黑色左孩子x和黑色右孩子y,则x与y的黑高度一定相等正确答案：A单选题(1分)PA8_Q8.pngWhat'stheresultafterfixingthedoublered?对上图中红黑树的节点x进行双红修正的结果是：PA8_Q8_A.pngPA8_Q8_B.pngPA8_Q8_C.pngPA8_Q8_D.png正确答案：C单选题(1分)Wichpropertycouldbeviolatedafterremovinganodeinared-blacktreeusingthealgorithmforBSTnoderemoval?在红黑树中直接按照常规的BST删除节点算法删除一个节点，关于红黑树结构的四条性质是否有可能被破坏？1、therootisbalck树根必为黑色couldbeviolated有可能会被破坏won'tbeviolated不会被破坏正确答案：A单选题(1分)（接上题）2、theexternalnodesareblack外部节点必均为黑色couldbeviolated有可能会被破坏won'tbeviolated不会被破坏正确答案：B单选题(1分)（接上题）3、thechildrenofarednodeareblack红色节点的孩子必为黑couldbeviolated有可能会被破坏won'tbeviolated不会被破坏正确答案：A单选题(1分)（接上题）4、thereareequalnumberofblacknodesineachpathfromaexternalnodetotheroot从根到外部节点的不同路径途中黑色节点数目相等couldbeviolated有可能会被破坏won'tbeviolated不会被破坏正确答案：A单选题(1分)WeknowmanyBBSTsupuntilnow.至此，我们接触了以下几种平衡二叉搜索树AVLtreesAVL树Splaytrees伸展树B-treesB-树Red-blacktrees红黑树kd-trres(seePA3andthelecturenote)kd-树（见PA3以及讲义）PleasechooseaBBSTforeachofthwfollowingscenarios针对下列应用的特点，请你选取最合适的平衡二叉搜索树accessingmassiveamountofdata(whichcannotfitintothememory)对大规模的数据（不能全部存放于内存中）的存取AVLtreesAVL树Splaytrees伸展树B-treesB-树Red-blacktrees红黑树kd-trreskd-树正确答案：C单选题(1分)（接上题）EasyimplementationandO(lgn)complexity需要易于实现，而且各接口的分摊复杂度为O(lgn)AVLtreesAVL树Splaytrees伸展树B-treesB-树Red-blacktreeskd-trreskd-树正确答案：B单选题(1分)（接上题）Problemsrelatedtogeometry处理和几何有关的问题AVLtreesAVL树Splaytrees伸展树B-treesB-树Red-blacktrees红黑树kd-trreskd-树正确答案：E单选题(1分)（接上题）Implementingaversioncontrolsystem扩充后可支持对历史版本的访问AVLtreesAVL树Splaytrees伸展树B-treesB-树Red-blacktrees红黑树kd-trreskd-树正确答案：D第九章词典填空题(1分)IfBaidudeterminesitsownphonenumberintheabovemanner,thenumberis百度(baidu)如果用以上方式确定自己的电话号码，则号码是____1正确答案:["22438"]单选题(1分)Theactualstoragelocationofthekeyis:关键码key实际存放的位置是：keykey-1hash(key)hash(hash(key))正确答案：C单选题(1分)Ifthehashfunctionish(x)=x%20,thentheconflictsinthekeys25,85,15,20are:散列函数是h(x)=x%20，则关键码25,85,15,20中会发生冲突的是：25和8525和1515和8520和15正确答案：A单选题(1分)Inthehash,ifthenumberofkeysexceedstheactualspaceused,isitpossibletoavoidconflict:在散列中，关键码个数超过实际使用的空间时，有没有可能不发生冲突：possible可能impossible不可能正确答案：B单选题(1分)Thehashfunctionh(x)=x%M,theMshouldbe:散列函数h(x)=x%M中的M应该取：1Powerof22的幂Aprimenumber素数Acompositenumber合数正确答案：C单选题(1分)MADis:MAD是:h(x)=1h(x)=xh(x)=(a*x+b)%Mh(x)=MAD正确答案：C单选题(1分)Thekeytypeforthepolynomialmethodis:多项式法适用的关键码类型为：-Integer整数Float浮点数Char字符String字符串正确答案：D填空题(1分)Keytoimprovingyourprogrammingskills____1正确答案:["LearningTsinghuaDataStructures&Algorithms"]单选题(1分)Whichkindofdatastructurecanbeusedtosolvetheproblemofmultipleslotsmethod:用哪种数据结构可以解决多槽位法的不足：Vector向量List列表Stack栈Queue队列正确答案：B单选题(1分)Inalinearprobing,intheeventofaconflict,turntoprobe:在线性试探中，一旦发生冲突，转而试探：Predecessorofcurrentposition当前位置的前驱Succcessorofcurrentposition当前位置的后继Currentposition当前位置Thenextelementinthelistofcurrentposition当前位置的列表中的下一个元素正确答案：B单选题(1分)Usingthequadraticprobingmethod,thepositionsofthepreviousprobingsare0,1,4,9,andthepositionofthenextprobingis:(assumingthebucketarrayislargeenough)使用平方试探法，前几次试探的位置是0,1,4,9，则下一次试探的位置是：（假设桶数组足够大）9101516正确答案：D单选题(1分)Whenthelengthofthetableisprime,inordertomakethequadraticprobingalwayssuccessful,theloadfactorneedstobelessthan:当表的长度为素数时，为了使平方试探总是成功，装填因子需要少于：10%50%80%100%正确答案：B单选题(1分)TherangeofvaluesofNelementstobesortedis[1,M].Thetimecomplexityofcountingsortis:N个待排序元素的取值范围是[1,M]，计数排序的时间复杂度为：O(NlgN)O(N)O(M)O(M+N)正确答案：D单选题(1分)Sisthespaceofallpossibleentries,Aisthespaceofallavailableaddresses(|A|<|S|),hisahashfunction,then:S为所有可能词条的空间，A为所有可用地址的空间（|A|<|S|），h是散列函数，则：hmapsfromStoA,itmustbeasurjectiveh从S映射到A，一定是满射hmapsfromStoA,itcannotbeainjective从S映射到A，不可能是单射hmapsfromAtoS,itcannotbeasurjectiveh从A映射到S，不可能是满射hmapsfromAtoS,itmustbeainjectiveh从A映射到S，一定是单射正确答案：B判断题(1分)Inthehashtable,whatarethecharacteristicsofagoodhashfunctionh?在散列表中，一个好的散列函数h需要具有哪些特点？Itisainjective是单射正确答案：×判断题(1分)（接上题）Rangecoversasmanyaddressesaspossible值域尽可能覆盖更多的地址正确答案：√判断题(1分)（接上题）Everytimewecalculatethevalueofhinthesameentry,wegetdifferentresults每次计算h在同一个词条的取值，得到的结果均不同正确答案：×判断题(1分)Itcanefficientlycalculatethefunctionvalueofangivenentry给定词条，能够高效地计算对应的函数值正确答案：√判断题(1分)（接上题）Fordifferententries,thedistributionoffunctionvaluesisasuniformaspossibletoavoidaggregation对于不同词条，函数值的分布尽可能均匀，避免聚集正确答案：√判断题(1分)（接上题）Unabletofindapairofconflictingentrieswithinareasonablecalculatingtime无法在合理的计算时间内找到一对发生冲突的词条正确答案：×填空题(2分)ConsiderthesetofkeysS={0,8,16,24,32,40,48,56,64}考虑key的集合S={0,8,16,24,32,40,48,56,64}Hashfunctionconstructedbydivisionmethod用除余法构造的散列函数h1(key)=key%12h2(key)=key%11HowmanyelementsdoestherangeofSmappedbyh1has?h1将S映射到的值域有几个元素？____HowmanyelementsdoestherangeofSmappedbyh2has?h2将S映射到的值域有几个元素？____1正确答案:["3"]2正确答案:["9"]单选题(1分)Regardingthemethodofresolvingconflicts,whichofthefollowingstatementiscorrect:关于排解冲突的方法，以下说法正确的是：Usingseparatechainingmethodtoresolveconflicts,allentriesareactuallystoredinsidethebucketarray用独立链法排解冲突，所有词条的实际存放位置均在桶数组内部Usingopenaddressingmethodtoresolveconflicts,theactualstoragelocationofanentryisnotnecessarilythecorrespondinghashfunctionvalue用开放定址排解冲突，词条的实际存放位置不一定是对应的散列函数值Usingopenaddressingtoresolveconflicts,entriesarestoredinalist用开放定址排解冲突，词条被存放在列表中Aslongasthehashfunctionisdesignedproperly,itdoesnotnecessarilyneedtoresolveconflicts只要散列函数设计得当，不一定需要排解冲突的策略正确答案：B单选题(1分)Thecurrentstateofthebucketarrayofsize11isA={*,*,*,*,*,0,15,26,*,5,9},where*meansemptybucket规模为11的桶数组当前状态为A={*,*,*,*,*,0,15,26,*,5,9}，其中*表示空桶Thehashfunctionish(key)=(3*key+5)%11散列函数为h(key)=(3*key+5)%11UsingOpenaddressing+Linearprobingtosolveconflicts用开放定址+线性试探排解冲突Inserttheentry4,itsactualstoragelocationis插入词条4,它的实际存放位置是-未答复A[4]A[6]A[7]A[8]正确答案：D单选题(1分)Thecurrentstateofthebucketarrayofsize11isA={*,*,*,*,*,0,15,26,*,5,9},where*meansemptybucket规模为11的桶数组当前状态为A={*,*,*,*,*,0,15,26,*,5,9}，其中*表示空桶Thehashfunctionish(key)=(3*key+5)%11散列函数为h(key)=(3*key+5)%11UsingOpenaddressing+quadraticprobingtosolveconflicts用开放定址+平方试探排解冲突Inserttheentry4,itsactualstoragelocationis插入词条4,它的实际存放位置是A[4]A[6]A[7]A[8]正确答案：A填空题(1分)Thesizeofthehashtableisaprimenumber.Usingopenaddressing+quadraticprobingtoresolveconflicts.Toensurethatnewentriescanbeinserted,theloadfactorofthehashtablecannotexceed(pleasefillindecimal).散列表的规模是素数，用开放定址+平方试探法排解冲突，若要保证新的词条能够顺利插入，散列表的装填因子不能超过（请填十进制小数）____1正确答案:["0.5"]单选题(1分)Sortnintegersrangedin[0,M]bycountingsort,thetimecomplexityis用计数排序对n个[0,M)内的整数进行排序，时间复杂度为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:对[0,11)中的整数{10,4,2,9,3,1,2,2,4,9,8,5,9,10,7,6,9}用计数排序，得到的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第十章优先级队列单选题(1分)Theaccessmodeofelementsinthepriorityqueueis:优先级队列中元素的访问模式是：-未答复Smallerrankoneisfirstlyvisited.秩小者先访问Biggerrankoneisfirstlyvisited.秩大者先访问Higherpriorityoneisfirstlyvisited.优先级高者先访问Front-locatedelementisfirstlyvisited位置靠前者先访问正确答案：C单选题(1分)TheroleofdelMax()inthepriorityqueueis:优先级队列的delMax()的作用是：Deletethelargestelement.删除最大的元素Deletetheelementwithhighestpriority.删除优先级最大的元素Deletethefirstelement.删除首元素Deletethelastelement.删除末元素正确答案：B单选题(1分)WhydoweusuallynotuseBBSTtoimplementpriorityqueue?为什么我们通常不用BBST实现优先级队列？Timeefficiencyisnothighenough时间效率不够高BBSTistoocomplexforsimplefunctionsinpriorityqueues对于实现优先级队列的简单功能来说，BBST过于复杂BBSTisnotwhatwearegoingtolearninthischapter.我们本章要学的不是BBSTThevectorismoreefficient向量的效率更高正确答案：B单选题(1分)Onewaytoimplementpriorityqueuesis:优先级队列的一种实现方式是：Logically,equivalentto逻辑上，等同于vector向量stack栈Truebinarytree真二叉树Completebinarytree完全二叉树正确答案：D单选题(1分)（接上题）Physically,equivalentto物理上，等同于vector向量stack栈Truebinarytree真二叉树Completebinarytree完全二叉树正确答案：A单选题(1分)Theparentnode'spriorityinacompletebinaryheap完全二叉堆中父节点的优先级Notsmallerthanitschildren不小于它的孩子Notequaltotheirchildren不等于它的孩子Thereisnonecessaryrelationshipwithitschildrenonsize和它的孩子没有必然的大小关系Equaltoitschildren.等于它的孩子正确答案：A单选题(1分)Themethodforinsertingelementsinafullbinaryheapis在完全二叉堆中插入元素的方法是Insertintothebottom,percolateUp插入到底层，上滤Insertintotheroot,percolateDown插入到根节点，下滤Insertintothebottomdirectly直接插入到底层Insertintotherootdirectly直接插入到根节点正确答案：A单选题(1分)Thetimecomplexityofinsertingelementsinacompletebinaryheapofsizenis:规模为n的完全二叉堆中插入元素的时间复杂度为：-未答复O(nlgn)O(n)O(lgn)O(1)正确答案：C单选题(1分)Whenyouwanttodeleteanelementinacompletebinaryheap,thepositionofthiselementis:完全二叉堆中要删除一个元素时，这个元素的位置是：-未答root根节点leaf叶子节点Canbeanynode可以是任意节点Rootnodeorleafnode根节点或叶子节点正确答案：A单选题(1分)Thetimecomplexityofdeletingelementsinacompletebinaryheapofsizenis:规模为n的完全二叉堆中删除元素的时间复杂度为：-未答O(nlgn)O(n)O(lgn)O(1)正确答案：C单选题(1分)Usingatop-downupperfiltertobuildacompletebinaryheapofsizen,theworst-casetimecomplexityis:使用自上而下的上滤建立规模为n的完全二叉堆，最坏时间复杂度为：-未O(nlgn)O(n)O(lgn)O(1)正确答案：A单选题(1分)ThetimecomplexityofbuildingacompletebinaryheapofsizenbytheFloydbuild-heapalgorithmis:Floyd建堆算法建立规模为n的完全二叉堆的时间复杂度为：O(nlgn)O(n)O(lgn)O(1)正确答案：B单选题(1分)Howtousetheheaptosort:如何用堆来实现排序：-未答ContinuetocalldelMax()afterbuildingaheap建堆后不断调用delMax()ContinuetocallgetMax()afterbuildingaheap建堆后不断调用getMax()Continuetocallinsert()afterbuildingaheap建堆后不断调用insert()Buildtheheap建堆正确答案：A单选题(1分)Themeaningoftheleftheaprelativetoafullbinaryheapis:相对于完全二叉堆，左式堆存在的意义是：Moreefficientinsertion高效的插入Moreefficientdeletion高效的删除Moreefficientmergence高效的合并Moreefficientsearch高效的查找正确答案：C单选题(1分)Themeaningofleftis左倾的意义是Therightchild'sNPLofanynodedoesnotexceedtheleftchild任何节点右孩子的NPL不超过左孩子Therightchild'sNPLofanynodeisnotsmallerthantheleftchild任何节点右孩子的NPL不小于左孩子Therootnode'srightchild'sNPLdoesnotexceedtheleftchild's根节点右孩子的NPL不超过左孩子Therootnode'sleftchild'sNPLdoesnotexceedtherightchild根节点左孩子的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?使用以下哪种数据结构实现优先级队列的insert,getMax,delMax接口均可达到O(lgn)的时间复杂度？-未答复vector向量orderedvector有序向量Hashtable散列表Balancedbinarysearchtree平衡二叉搜索树正确答案：D单选题(1分)Thestackisaspecialcaseofpriorityqueueswheretheelement'spriorityis:栈作为优先级队列的一种特殊情况，其中元素的优先级：Earliertheelementispushedintothestack,thepriorityofitwillbelower.先入栈者优先级低Elementswhoispushedintothestackearlierhashigherpriority.先入栈者优先级高Allelementshavethesamepriority所有元素优先级相同Thereisnodefiniterelationshipbetweenelementpriorities元素优先级之间没有确定的关系正确答案：A单选题(1分)Theoverallfo