雨课堂学堂在线学堂云《Data Structures and Algorithm Design Part II（清华）》单元测试考核答案

第1题What'sthedifferencebetweenabinarysearchtreeandaregularbinarytree?二叉搜索树之区别于普通的二叉树在于：AEachnodeislessthanorequaltothenodesinitsrightsub-tree,whilebeinggreaterthanorequaltothenodesinitsleftsub-tree.任意节点均不大于其右子树中的节点，不小于其左子树中的节点BEachnodeislessthanorequaltoitsrightchild,whilebeinggreaterthanorequaltoitsleftchild任意节点均不大于其右孩子，不小于其左孩子CEachnode(excepttheroot)islessthanorequaltoitsparent除了根节点外所有节点均不大于其父亲DThekeysarecomparable关键码可以比较第2题Whichorderfortraversingabinarytreealwaysresultsinincreasingsequences?二叉搜索树的何种遍历序列是递增的？Apre-order先序Bin-order中序Cpost-order后序Dhierachical层次第1题What'stheworst-casetimecomplexityforsearchinginaBSTwithnnodes?在含n个节点的BST中进行查找的最坏时间复杂度为：AO(1)BO(log2⁡(n))CO(n)DO(nlog2⁡(n))第2题Thefollowingsequenceofnodesareencounteredwhensearchingfor13inthebinarysearchtree:在以上二叉查找树中查找关键码13，经过的节点依次为：A16,11,13B16,10,5,8,13C16,10,11,15,13DThisisnotabinarysearchtree以上二叉树根本不是二叉查找树B2.BST:insertion--Homework第1题ConsiderinsertingatargetelementeintoaBST.whenitfailstobefoundduringthesearch,whichnodedoes_hotcorrespondto?对BST进行插入操作，对待插入的目标元素e进行查找后，若查找失败，_hot指向的节点为：AThenodetobeinserted待插入的节点BTheparentofeaftertheinsertione被插入后的父亲CTheleft-childofeaftertheinsertione被插入后的左孩子DTheroot根节点B3.BST:reomval--Homework第1题Whenatemptingtodeleteanodevofdegree2,what'stheactualnodebeingdeleted?

当欲删除的节点v在BST中的度为2时，实际被删除的节点为：Av'sdirectpredecessorinthein-ordersequencev在中序遍历下的直接前驱Bv'sdirectsuccessorinthepre-ordersequencev在先序遍历下的直接后继Cthelastnodeintheleftbranchofv'srightsub-treev的右子树中左侧分支的最后一个节点Dv'sparentv的父亲C.balance+equivalence--Homework第1题ABSThasnnodesandaheightofh.Whatistheworst-casetimecomplexityforsearchinginit?在含n个节点、高度为h的BST中进行查找的最坏时间复杂度为：AO(h)BO(n)CO(nh)DO(n/h)第2题ABSThasnnodesandaheightofh.ItisabalancedBSTif:含n个节点，高度为h的BST称为平衡二叉搜索树若它满足：An=O(h)Bh=O(n)Ch=O(log2⁡n)Dn=O(log2⁡h)第3题TwoequivalentbalancedBSThaveidentical:两个等价的平衡二叉搜索树有相同的：Apre-ordersequence先序遍历序列Bin-ordersequence中序遍历序列Cpost-ordersequence后序遍历序列Dhierachicalsequence层次遍历序列D1.AVL:rebalance--Homework第1题WhatisthemaximumnumberofimbalancednodesafterinsertinganodeinanAVLtree?在AVL树中刚插入一个节点后失衡节点个数最多为AO(1)BO(lglgn)CO(lgn)DO(n)第2题WhatisthemaximumnumberofimbalancednodesafterdeletinganodeinanAVLtree?在AVL树中刚删除一个节点后失衡节点个数最多为AO(1)BO(lglgn)CO(lgn)DO(n)第3题TherootoftheAVLtreeabovehasabalancefactorof:以上AVL树根节点的平衡因子为：A-1B0C1D2第4题WhatistheminumumnumberofnodesinaAVLtreeofheight3?高度为3的AVL树至少包含几个节点？____正确答案：:7D2.AVL:insertion--Homework第1题InsertingnodesintoanAVLtreecouldleadtoimbalance.Afterrebalancingthetreeviarotation,theheightofthesub-treescontainingnodeg,p,andvAVL树中插入节点引发失衡，经旋转调整后重新平衡，此时包含节点g,p,v的子树高度Adecreaseby1减小1Bremainthesame不变Cincreaseby1增加1Deitherremainthesameorincreaseby1有可能不变也有可能增加1D3.AVL:removal--Homework第1题AVL树中删除节点引发失衡，经旋转调整后重新平衡，此时包含节点g,p,v的子树高度A减小1B不变C增加1D有可能不变也有可能减小1D4.AVL:(3+4)-construction--Homework第1题The_____ofanAVLtreeisinvariantunderthe3+4reconstruction.经过3+4重构后的AVL树_____不变。Apre-ordersequence先序遍历序列Bin-ordersequence中序遍历序列Cpost-ordersequence后序遍历序列Dhierachicalsequence层次遍历序列Homework第1题WhichofthefollowingisaBST?以下哪项是二叉搜索树?ABCD第2题What'sthenumberofdistinctBSTscontainingnodes{1,2,3,4}?包含节点{1,2,3,4}的不同二叉搜索树有多少棵？____正确答案：:14第3题Whatisthe3rdelementwecomparetowhensearchingfor14intheBSTabove?在以上二叉搜索树中查找元素14，第3个和14发生比较的元素为：____正确答案：:11第4题Whatarethestepsfordeleting16?欲在以上二叉搜索树中删除节点16，可行的方案是：Aremove16,make25therightchildof10and10becomesthenewroot.

将16摘除后令25为10的右子，从而10是新的根节点Bexecuteazigoperationon16makingitnolongertheroot,andthenremoveitdirectly

以16为轴进行一次zig操作使之不再是根节点，再直接摘除16Cexchangethekeyofnode16andnode33,andremovethenewnode16

将节点16和节点33的关键码互换，再摘除新的节点16Dexchangethekeyofnode16andnode15,removethenewnode16andmake13therightchildof11将节点16和节点15的关键码互换，摘除新的节点16并令13为11的右子第5题ABSThasnnodesandaheightofh.Whichofthefollowingholds?二叉搜索树的高度h和节点个数n满足关系Ah=O(1)Bh=O(lgn)Ch=O(n)Dh=O(nlgn)第6题Whatistheworst-casetimecomplexityforsearchinginit?在其上进行查找的最坏时间复杂度为AO(1)B

O(lgn)CO(n)DO(nlgn)第7题Giventhatit'sabalancedBST,whichofthefollowingholds?若已知它是平衡二叉搜索树，则n和h满足关系Ah=O(1)Bh=O(lgn)C

h=O(n)Dh=O(nlgn)第8题thecomplexitybecomes在其上进行查找的最坏时间复杂度为AO(1)BO(lgn)CO(n)D

O(nlgn)第9题GiventheBSTabove,whatistheresultafterazigoperationonnode19?对以上二叉搜索树，以节点19为轴进行一次zig操作后得到的树为：ABCD第10题WhatisthetimecomplexityforsearchinginanAVLtreewithnnodes?在包含n个节点的AVL树中进行查找的时间复杂度为AO(1)BO(lgn)CO(n)DO(nlgn)第11题Whataboutinsertinganode?插入的时间复杂度为AO(1)BO(lgn)CO(n)DO(nlgn)第12题Whataboutdeletinganode?删除的时间复杂度为AO(1)BO(lgn)CO(n)DO(nlgn)第13题AfterinsertinganodeintoanAVLtreeandrebalancing,theheightoftherotatedsub-treeAVL树中插入节点引发失衡，经旋转调整重新平衡后发生旋转的子树的高度Adecreaseby1减小1Bremainsthesameorincreaseby1不变或增加1Cremainsthesame不变Dremainsthesameordecreaseby1不变或减小1第14题Whataboutthecasewhenanodeisdeleted?删除节点的情况呢？Adecreaesby1减小1B

remainsthesameorincreaseby1不变或增加1Cremainsthesame不变Dremainsthesameordecreaseby1不变或减小1第15题TheAVLtreeaboveisimblancedbecausenode13wasjustinserted.Whichoneisthetreeafterrebalancing?以上AVL树因为刚插入节点13而失衡，利用课堂上所学重平衡算法，恢复平衡后的AVL树为：ABCD第16题Choosethesub-treeafterapplying3+4reconstructiontothetreeabove.对以上子树进行3+4重构，得到的子树为：ABCDHomework第1题Whichpropertyofdataaccessistakenadvantageofbysplaytrees?伸展树利用了实际问题中数据访问的何种特点：Amassiveness大量性Blocality局部性Cholisticity整体性Ddiversity多样性第2题Whichoperationisexecutedforeachaccessednodeinasplaytree?伸展树每次访问过某节点后都会把该节点：Aremovingit删除Bmovingittothehigerlevel上移一层Cmovingittotheroot移动到根节点Daccessingitagain再次访问该节点Homework第1题InTarjan'salgorithm,howmanylayersaresplayedtogether?Tarjan提出的伸展算法每几层一起伸展？A1B2C3D4第2题Asplaytreedegeneratesintoalist.What'sitsheightafteraccessingthelowestnode?在一棵退化成单链的伸展树中访问其最深的节点，经过伸展后树高大约为原先的：Aonethirdoftheoriginalheight三分之一Bhalfoftheoriginalheight一半Ctheoriginalheight不变Dtwicetheoriginalheight两倍第3题What'stheamortizedcomplexityforasinglesplayoperationinTarjan'salgorithm?按照Tarjan的伸展算法，单次伸展操作的分摊复杂度为：AO(1)BO(lgn)CO(n)DO(nlgn)Homework第1题Thenodeaccessedisaright-child,andsoisitsparent.Whatshouldwedoforasinglesplayoperation?所访问的节点及其父亲都是右孩子，则双层伸展要执行的操作是：Azig-zagBzag-zigCzig-zigDzag-zag第2题What'stheamortizedcomplexityinasufficientlylongsequenceofaccessingknodesinasplaytreeofsizen?规模为n的伸展树中若所访问的节点只有k个，经过足够长时间的访问序列后，访问的分摊复杂度为：-未答复AO(lgk)BO(klgn)CO(nlgk)DO(lgn)Homework第1题Whydoesthememorybecomessmallerandsmaller?内存“越来越小”的原因是：AWithmoreandmoreprocessesrunningononecomputer,theaveragememroysizeforeachprocessisgettingsmaller机器上运行的程序越来越多，平均每个程序使用的内存变小BThereal-worldapplicationscallforrocketingmemorystorage实际应用对存储的需求急剧增长CThesiliconusedforproducingchipsissoonrunningout用于制造内存芯片的硅资源消耗殆尽DThephysicalsizeofmemorychipsisgettingsmallerthankstotheadvancesintechnology随着工艺的进步，内存的体积变小，集成度变高第2题Ifitwouldtakeusasecondforasinglememoryaccess,howlongwoulditcostforasingleaccesstotheexternalstorage?如果说访问一次内存需要1秒，则一次外存访问大概需要：Aahour1小时Baday1天Camonth1月Dayear1年Homework第1题B-treesare树结构上的特点是：Ashortandchubby,witheachnodehavingatmosttwochildren矮胖，每个节点至多两个孩子Bshortandchubby,witheachnodehavingpotentiallymanychildren矮胖，每个节点可有多于两个孩子Ctallandslim,witheachnodehavingatmosttwochildren瘦高，每个节点至多两个孩子Dtallandslim,witheachnodehavingpotentiallymanychildren瘦高，每个节点可有多于两个孩子第2题B-treeshavesmallheightsoastoB树的层数少有助于：AreducethenumberofI/Ooperations减少I/O次数BreducethetimeconsumptionforasingleI/O减少每次I/O的时间Creducetheasymptotictimecomplexityforseaching降低查找的渐进时间复杂度Dreducethestoragerequirement节省存储空间第3题HowmanychildrenarethereforeachnodeinaB-treeoforder4?4阶B树中每个节点的分支数为：A1~4B2~5C2~4D3~5Homework第1题What'sthetimecomplexityforsearchinginaB-treeoforder4andsizen?在存储了n个元素的4阶B树中查找，单个节点进行一次查找的时间复杂度为：AO(1)BO(lgn)CO(n)DO(nlgn)第2题What'sthereturnvalueforafailedsearchinaB-treeoforder4?B树查找算法若最终失败，返回值为：ANoneBNULLCApointertothelastexaminednode指向最后一个所查找节点的指针DApointertotheroot指向根节点的指针第3题What'stheheightofaB-treeoforder128relativetoacorrespondingBBST?若B树的阶m=128，则它的高度大致是对应的BBST的：A1/5B1/6

C1/7D1/8Homework第1题What'sthe'overflow'foraB-tree?B树的上溢是指：AThepropertyofaB-treeisviolatedduetoremovingakey删除关键码后违反了B树的性质BThepropertyofaB-treeisviolatedduetoinsertingakey插入新的关键码后违反了B树的性质CThepropertyofaB-treeisviolatedduetoasplit分裂后违反了B树的性质DAB-treebecomestoohighB树的高度过高第2题WhichconsequencefollowsasaB-treebecomeshigher?B树高度的增加一定伴随着：AEachnodehasalargernumberofkeys每个节点所存放的关键码数量增加BEachnodehasasmallernumberofkeys每个节点所存放的关键码数量减少CSplittingtotheroot分裂到根DSplittingtotheleaves分裂到叶Homework第1题TheunderflowofaB-treehappenswhenB树的下溢发生于：AtheheightofthetreedecreasesB树高度减少BthepropertyoftheB-treeisviolatedduetoinsertingakey插入关键码后违反了B树的性质CthepropertyoftheB-treeisviolatedduetodeletingakey删除关键码后违反了B树的性质Dinsertingakeytoaleafnode在叶节点插入关键码第2题TheheightofaB-treedecreasesonlywhenB树高度的减少只会发生于Amergingtwochildrenoftheroot根节点的两个孩子合并

Bremovingtheroot根节点被删除Crotatingtheroot根节点发生旋转Dtherearemultiplekeysintheroot根节点有多个关键码Homework第1题Anodeinared-balcktreecouldbe红黑树节点的颜色有-未答Ared红Bblack黑Cyellow黄Dblue蓝Egreen绿Fpurple紫正确答案：AB第2题What'suniqueaboutred-blacktreescomparedtoAVLtrees?红黑树相比于AVL树的特点是：AThebalancefactorofeachnodefallswithin[-1,1]每个节点的平衡因子的绝对值不超过1BItisabalancedbinarysearchtree是平衡二叉搜索树CThesearchtimeisO(lgn)支持O(lgn)时间的查找DThetopologychangesnomorethanO(1)aftereachinsertion/deletion每次插入/删除后拓扑结构的变化不超过O(1)Homework第1题Therootofared-blacktreeis红黑树的根节点的颜色是Ared红Bblack黑第2题Theexternalnodesare外部节点的颜色是Ared红Bblack黑第3题Ared-blacktreeisequivalenttoaB-treeoforder__红黑树等价于____阶B树:正确答案：:4第4题Inared-blacktreeofsizen,theblackheightwouldn'texceed__规模为n的红黑树，黑高度不超过：AO(1)BO(lgn)CO(n)DO(nlgn)第5题Theheightwouldn'texceed__高度不超过：AO(1)BO(lgn)CO(n)DO(nlgn)Homework第1题Whatisa'doublered'inared-blacktree?在红黑树中，何为双红缺陷：Atherootisred根节点为红色Bboththerootandtheexternalnodesarered根节点和外部节点都为红色Cbothaparentanditschildarered相邻的两个父子节点都为红色Dtherearetworednodesinthetree树中有两个红色节点第2题Howdoesthetopologychangeswhenfixingadoubleredandtheunclenodeuisred.当叔父节点u为红色时，修正双红缺陷导致的红黑树拓扑结构的变化为：Anochange没有变化BitchangesnomorethanO(1)有变化，但是不超过O(1)CitchangesnomorethanO(lgn)有变化，但是不超过O(lgn)DitchangesnomorethanO(n)有变化，但是不超过O(n)Homework第1题Splaytreeshavelargeworst-casetimecomplexityforasingleoperation,however,theyreducethenumberofI/Obyexploitinghierachicalstorage伸展树虽然单次操作的最坏时间复杂度比较大，但是可以利用存储器的层次结构降低I/O的次数第2题Splaytreesaredifficulttoimplement伸展树相较于AVL树的缺点是它实现起来较为复杂第3题SplaytreeshavelargeramortizedcomplexitythanAVLtreesforinsertion伸展树插入操作的分摊复杂度比AVL树大第4题Splaytreeshavelargerworst-casetimecomplexitythanAVLtreesforsearching伸展树单次查找操作的最坏时间复杂度比AVL树大第5题Thisisasplaytree.Whatistheresultafteraccessingnodevandperformingatwo-layersplay?上图是伸展树，其中节点v刚被访问过，双层伸展后的结果是：ABCD第6题Thisisasplaytree.What'stheresultafterinsertinganode1andperformingatwo-layersplay?在以上伸展树中插入节点1并经过双层伸展后的结果是ABCD第7题Whichstatementregarding(2,4)-treesisincorrect?关于(2,4)-树，下列命题不正确的是：A(2,4)-treesareequivalenttored-blacktrees(2,4)-树等价于红黑树BEachinternalnodehasnomorethan4branches每个内部节点的分支数不超过4CEachinternalnodehasnolessthan2branches每个内部节点的分支数不小于2DEachnodehasexactly3keysexceptfortheroot除了根节点外，每个内部节点都恰好包含3个关键码第8题Anoverflowoccursafterinsertingnode52intoa(3,6)-tree,what'stheresultaftersplitting?上图是(3,6)-树中刚插入节点52后的情形，可以看出发生了上溢，分裂后的结果为：ABCD第9题Anunderflowoccursafterremovinganodefroma(3,6)-tree,what'stheresultaftertheadjustment?上图是(3,6)-树中刚删除某节点后的情形，可以看出发生了下溢，调整后的结果为：ABCD第10题Whichstatementregardingred-blacktreesiswrong?以下关于红黑树的说法，错误的是：-未答复AAred-blacktreeofsizenhasabalckheightofO(lgn),buttheheightisnotnecessarilyO(lgn)含n个节点的红黑树，其黑高度为O(lgn)，但是总的高度却未必是O(lgn)BTherecannotbetwoconsecutiverednodesinapathfromaexternalnodetotheroot从红黑树的任一外部节点上溯到根节点，沿途不可能经过连续两个红色节点CTheblackheightcannotbesmallerthanhalftheheight红黑树的黑高度一定不小于总高度的一半Dx(black)andy(black)aretwochildrenofablacknode.Theblackheightofthesub-treesxandymustequal.红黑树中的黑色节点u有黑色左孩子x和黑色右孩子y,则x与y的黑高度一定相等第11题What'stheresultafterfixingthedoublered?对上图中红黑树的节点x进行双红修正的结果是：ABCD第12题Wichpropertycouldbeviolatedafterremovinganodeinared-blacktreeusingthealgorithmforBSTnoderemoval?在红黑树中直接按照常规的BST删除节点算法删除一个节点，关于红黑树结构的四条性质是否有可能被破坏？1、therootisbalck树根必为黑色A

couldbeviolated有可能会被破坏

Bwon'tbeviolated不会被破坏第13题（接上题）2、theexternalnodesareblack外部节点必均为黑色Acouldbeviolated有可能会被破坏B

won'tbeviolated不会被破坏第14题（接上题）3、thechildrenofarednodeareblack红色节点的孩子必为黑Acouldbeviolated有可能会被破坏B

won'tbeviolated不会被破坏第15题（接上题）4、thereareequalnumberofblacknodesineachpathfromaexternalnodetotheroot从根到外部节点的不同路径途中黑色节点数目相等A

couldbeviolated有可能会被破坏

Bwon'tbeviolated不会被破坏第16题WeknowmanyBBSTsupuntilnow.至此，我们接触了以下几种平衡二叉搜索树AVLtreesAVL树Splaytrees伸展树B-treesB-树Red-blacktrees红黑树kd-trres(seePA3andthelecturenote)kd-树（见PA3以及讲义）PleasechooseaBBSTforeachofthwfollowingscenarios针对下列应用的特点，请你选取最合适的平衡二叉搜索树accessingmassiveamountofdata(whichcannotfitintothememory)对大规模的数据（不能全部存放于内存中）的存取AAVLtreesAVL树BSplaytrees伸展树CB-treesB-树DRed-blacktrees红黑树Ekd-trreskd-树第17题（接上题）EasyimplementationandO(lgn)complexity需要易于实现，而且各接口的分摊复杂度为O(lgn)AAVLtreesAVL树BSplaytrees伸展树CB-treesB-树DRed-blacktreesEkd-trreskd-树第18题（接上题）Problemsrelatedtogeometry处理和几何有关的问题AAVLtreesAVL树BSplaytrees伸展树CB-treesB-树DRed-blacktrees红黑树Ekd-trres

kd-树正确答案：E第19题（接上题）Implementingaversioncontrolsystem扩充后可支持对历史版本的访问AAVLtreesAVL树BSplaytrees伸展树CB-treesB-树DRed-blacktrees红黑树Ekd-trreskd-树Homework第1题IfBaidudeterminesitsownphonenumberintheabovemanner,thenumberis百度(baidu)如果用以上方式确定自己的电话号码，则号码是____正确答案：:22438第2题Theactualstoragelocationofthekeyis:关键码key实际存放的位置是：AkeyBkey-1Chash(key)Dhash(hash(key))第3题Ifthehashfunctionish(x)=x%20,thentheconflictsinthekeys25,85,15,20are:散列函数是h(x)=x%20，则关键码25,85,15,20中会发生冲突的是：A25和85B25和15C15和85D20和15Homework第1题Inthehash,ifthenumberofkeysexceedstheactualspaceused,isitpossibletoavoidconflict:在散列中，关键码个数超过实际使用的空间时，有没有可能不发生冲突：Apossible

可能Bimpossible

不可能第2题Thehashfunctionh(x)=x%M,theMshouldbe:散列函数h(x)=x%M中的M应该取：A1BPowerof22的幂CAprimenumber素数DAcompositenumber合数第3题MADis:MAD是:Ah(x)=1Bh(x)=xCh(x)=(a*x+b)%MDh(x)=MAD第4题Thekeytypeforthepolynomialmethodis:多项式法适用的关键码类型为：-

AInteger

整数BFloat

浮点数CChar

字符DString

字符串第5题Keytoimprovingyourprogrammingskills____正确答案：:LearningTsinghuaDataStructures&AlgorithmsHomework第1题Whichkindofdatastructurecanbeusedtosolvetheproblemofmultipleslotsmethod:用哪种数据结构可以解决多槽位法的不足：AVector

向量BList

列表CStack

栈DQueue

队列第2题Inalinearprobing,intheeventofaconflict,turntoprobe:在线性试探中，一旦发生冲突，转而试探：APredecessorofcurrentposition

当前位置的前驱BSucccessorofcurrentposition

当前位置的后继CCurrentposition

当前位置DThenextelementinthelistofcurrentposition

当前位置的列表中的下一个元素Homework第1题Usingthequadraticprobingmethod,thepositionsofthepreviousprobingsare0,1,4,9,andthepositionofthenextprobingis:(assumingthebucketarrayislargeenough)使用平方试探法，前几次试探的位置是0,1,4,9，则下一次试探的位置是：（假设桶数组足够大）A9B10C15D16第2题Whenthelengthofthetableisprime,inordertomakethequadraticprobingalwayssuccessful,theloadfactorneedstobelessthan:当表的长度为素数时，为了使平方试探总是成功，装填因子需要少于：A10%B50%C80%D100%Homework第1题TherangeofvaluesofNelementstobesortedis[1,M].Thetimecomplexityofcountingsortis:N个待排序元素的取值范围是[1,M]，计数排序的时间复杂度为：AO(NlgN)BO(N)CO(M)DO(M+N)Homework第1题Sisthespaceofallpossibleentries,Aisthespaceofallavailableaddresses(|A|<|S|),hisahashfunction,then:S为所有可能词条的空间，A为所有可用地址的空间（|A|<|S|），h是散列函数，则：AhmapsfromStoA,itmustbeasurjective

h从S映射到A，一定是满射BhmapsfromStoA,itcannotbeainjective

从S映射到A，不可能是单射ChmapsfromAtoS,itcannotbeasurjective

h从A映射到S，不可能是满射DhmapsfromAtoS,itmustbeainjective

h从A映射到S，一定是单射第2题Inthehashtable,whatarethecharacteristicsofagoodhashfunctionh?在散列表中，一个好的散列函数h需要具有哪些特点？Itisainjective是单射第3题（接上题）Rangecoversasmanyaddressesaspossible值域尽可能覆盖更多的地址第4题（接上题）Everytimewecalculatethevalueofhinthesameentry,wegetdifferentresults每次计算h在同一个词条的取值，得到的结果均不同第5题Itcanefficientlycalculatethefunctionvalueofangivenentry给定词条，能够高效地计算对应的函数值第6题（接上题）Fordifferententries,thedistributionoffunctionvaluesisasuniformaspossibletoavoidaggregation对于不同词条，函数值的分布尽可能均匀，避免聚集第7题（接上题）Unabletofindapairofconflictingentrieswithinareasonablecalculatingtime无法在合理的计算时间内找到一对发生冲突的词条第8题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映射到的值域有几个元素？____正确答案：:3正确答案：:9第9题Regardingthemethodofresolvingconflicts,whichofthefollowingstatementiscorrect:关于排解冲突的方法，以下说法正确的是：AUsingseparatechainingmethodtoresolveconflicts,allentriesareactuallystoredinsidethebucketarray

用独立链法排解冲突，所有词条的实际存放位置均在桶数组内部BUsingopenaddressingmethodtoresolveconflicts,theactualstoragelocationofanentryisnotnecessarilythecorrespondinghashfunctionvalue

用开放定址排解冲突，词条的实际存放位置不一定是对应的散列函数值CUsingopenaddressingtoresolveconflicts,entriesarestoredinalist

用开放定址排解冲突，词条被存放在列表中DAslongasthehashfunctionisdesignedproperly,itdoesnotnecessarilyneedtoresolveconflicts

只要散列函数设计得当，不一定需要排解冲突的策略第10题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,它的实际存放位置是-未答复AA[4]BA[6]CA[7]DA[8]第11题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+

quadratic

probingtosolveconflicts用开放定址+平方试探排解冲突Inserttheentry4,itsactualstoragelocationis插入词条4,它的实际存放位置是AA[4]BA[6]CA[7]DA[8]第12题Thesizeofthehashtableisaprimenumber.Usingopenaddressing+quadraticprobingtoresolveconflicts.Toensurethatnewentriescanbeinserted,theloadfactorofthehashtablecannotexceed(pleasefillindecimal).散列表的规模是素数，用开放定址+平方试探法排解冲突，若要保证新的词条能够顺利插入，散列表的装填因子不能超过（请填十进制小数）____正确答案：:0.5第13题Sortnintegersrangedin[0,M]bycountingsort,thetimecomplexityis用计数排序对n个[0,M)内的整数进行排序，时间复杂度为AO(n+M)BO(min{n,M})CO(nlgn)DO(n^2)第14题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[]表为：A{0,1,3,1,2,1,1,1,1,4,2}B{10,4,2,9,3,1,2,2,4,9,8,5,9,10,7,6,9}C{0,1,4,5,7,8,9,10,11,15,17}D{0,1,4,7,9,12,13,14,15,16,17}Homework第1题Theaccessmodeofelementsinthepriorityqueueis:优先级队列中元素的访问模式是：-未答复ASmallerrankoneisfirstlyvisited.秩小者先访问BBiggerrankoneisfirstlyvisited.秩大者先访问CHigherpriorityoneisfirstlyvisited.优先级高者先访问DFront-locatedelementisfirstlyvisited位置靠前者先访问第2题TheroleofdelMax()inthepriorityqueueis:优先级队列的delMax()的作用是：ADeletethelargestelement.删除最大的元素BDeletetheelementwithhighestpriority.删除优先级最大的元素CDeletethefirstelement.删除首元素DDeletethelastelement.删除末元素Homework第1题WhydoweusuallynotuseBBSTtoimplementpriorityqueue?为什么我们通常不用BBST实现优先级队列？ATimeefficiencyisnothighenough时间效率不够高BBBSTistoocomplexforsimplefunctionsinpriorityqueues对于实现优先级队列的简单功能来说，BBST过于复杂CBBSTisnotwhatwearegoingtolearninthischapter.我们本章要学的不是BBSTDThevectorismoreefficient向量的效率更高Homework第1题Onewaytoimplementpriorityqueuesis:优先级队列的一种实现方式是：Logically,equivalentto逻辑上，等同于Avector向量Bstack栈CTruebinarytree真二叉树DCompletebinarytree完全二叉树第2题（接上题）Physically,equivalentto物理上，等同于Avector向量Bstack栈CTruebinarytree真二叉树DCompletebinarytree完全二叉树第3题Theparentnode'spriorityinacompletebinaryheap完全二叉堆中父节点的优先级ANotsmallerthanitschildren不小于它的孩子BNotequaltotheirchildren不等于它的孩子CThereisnonecessaryrelationshipwithitschildrenonsize和它的孩子没有必然的大小关系DEqualtoitschildren.等于它的孩子Homework第1题Themethodforinsertingelementsinafullbinaryheapis在完全二叉堆中插入元素的方法是AInsertintothebottom,percolateUp插入到底层，上滤BInsertintotheroot,percolateDown插入到根节点，下滤CInsertintothebottomdirectly直接插入到底层DInsertintotherootdirectly直接插入到根节点第2题Thetimecomplexityofinsertingelementsinacompletebinaryheapofsizenis:规模为n的完全二叉堆中插入元素的时间复杂度为：-未答复AO(nlgn)BO(n)CO(lgn)DO(1)Homework第1题Whenyouwanttodeleteanelementinacompletebinaryheap,thepositionofthiselementis:完全二叉堆中要删除一个元素时，这个元素的位置是：-未答Aroot根节点Bleaf叶子节点CCanbeanynode可以是任意节点DRootnodeorleafnode根节点或叶子节点第2题Thetimecomplexityofdeletingelementsinacompletebinaryheapofsizenis:规模为n的完全二叉堆中删除元素的时间复杂度为：-未答AO(nlgn)BO(n)CO(lgn)DO(1)Homework第1题Usingatop-downupperfiltertobuildacompletebinaryheapofsizen,theworst-casetimecomplexityis:使用自上而下的上滤建立规模为n的完全二叉堆，最坏时间复杂度为：-未AO(nlgn)BO(n)CO(lgn)DO(1)第2题ThetimecomplexityofbuildingacompletebinaryheapofsizenbytheFloydbuild-heapalgorithmis:Floyd建堆算法建立规模为n的完全二叉堆的时间复杂度为：AO(nlgn)BO(n)CO(lgn)DO(1)Homework第1题Howtousetheheaptosort:如何用堆来实现排序：-未答AContinuetocalldelMax()afterbuildingaheap建堆后不断调用delMax()BContinuetocallgetMax()afterbuildingaheap建堆后不断调用getMax()CContinuetocallinsert()afterbuildingaheap建堆后不断调用insert()DBuildtheheap建堆Homework第1题Themeaningoftheleftheaprelativetoafullbinaryheapis:相对于完全二叉堆，左式堆存在的意义是：AMoreefficientinsertion高效的插入BMoreefficientdeletion高效的删除CMoreefficientmergence高效的合并DMoreefficientsearch高效的查找第2题Themeaningofleftis左倾的意义是ATherightchild'sNPLofanynodedoesnotexceedtheleftchild任何节点右孩子的NPL不超过左孩子BTherightchild'sNPLofanynodeisnotsmallerthantheleftchild任何节点右孩子的NPL不小于左孩子CTherootnode'srightchild'sNPLdoesnotexceedtheleftchild's

根节点右孩子的NPL不超过左孩子DTherootnode'sleftchild'sNPLdoesnotexceedtherightchild根节点左孩子的NPL不超过右孩子Homework第1题CombiningtheleftistheapsAandtheleftistheapsB,wherethelargestelementofAisgreaterthanallelementsinB,therecursivestepsare:合并左式堆A和左式堆B，其中A的最大元素比B中所有元素都大，则递归的步骤为：AMergeA'sleftchildheapandB合并A的左子堆和BBMergeA'srightchildheapandB合并A的右子堆和BCMergeB'sleftchildheapandB合并B的左子堆和ADMergeB'srightchildheapandB合并B的右子堆和AHomework第1题Whichofthefollowingdatastructuresisusedtoimplementthepriorityqueue'sinsert,getMax,anddelMaxinterfacestoachieveO(lgn)timecomplexity?使用以下哪种数据结构实现优先级队列的insert,getMax,delMax接口均可达到O(lgn)的时间复杂度？-未答复Avector向量Borderedvector有序向量CHashtable散列表DBalancedbinarysearchtree平衡二叉搜索树第2题Thestackisaspecialcaseofpriorityqueueswheretheelement'spriorityis:栈作为优先级队列的一种特殊情况，其中元素的优先级：AEarliertheelementispushedintothestack,thepriorityofitwillbelower.

先入栈者优先级低BElementswhoispushedintothestackearlierhashigherpriority.

先入栈者优先级高CAllelementshavethesamepriority所有元素优先级相同DThereisnodefiniterelationshipbetweenelementpriorities元素优先级之间没有确定的关系第3题Theoverallformofthecompletebinarytree:完全二叉树从整体上看的形态是：-未答复ACompletetriangle完整的三角形BMissingrighttriangle缺右角的三角形CMissinglefttriangle缺左角的三角形DZigzagbottomtriangle底部呈锯齿状的三角形第4题Acompletebinaryheapisphysicallyavectoranditsstoredorderofelementsis完全二叉堆在物理上是向量，其所存储的元素次序是APre-ordertraversalofcompletebinarytree完全二叉树的先序遍历次序BMid-ordertraversalofcompletebinarytree完全二叉树的中序遍历次序CPostordertraversalofcompletebinarytree完全二叉树的后序遍历次序DHierarchicaltraversalofcompletebinarytree完全二叉树的层次遍历次序第5题Inthecompletebinarystack(biggestnodeintheroot),itisincorrect在完全二叉堆中（大顶堆），不正确的是-未答复AThevalueofanynodedoesnotexceeditsfather任何节点的数值不超过其父亲BSizerelationshipbetweensiblingsisuncertain兄弟节点之间的没有确定的大小关系CThevalueofthenodedoesnotexceedanyofitsancestors节点的数值不超过其任何一个祖先DThelargestelementintheentireheapisatthebottomoftheleafnode整个堆中的最大元素在底部的叶子节点第6题Thecurrentcompletebinaryheapisphysically{10,5,8,3,2,7}asavector.Afterinsertingthenewelement9,itbecomes:当前完全二叉堆物理上作为向量是{10,5,8,3,2,7}，插入新元素9后变为：-未答复A{2,3,5,7,8,9,10}B{10,9,8,7,5,3,2}C{10,5,8,3,2,7,9}D{10,5,9,3,2,7,8}第7题Thecurrentcompletebinaryheapisphysically{10,5,8,3,2,7}asavector,andaftercallingdelMax()becomes:当前完全二叉堆物理上作为向量是{10,5,8,3,2,7},调用delMax()后变为：A{5,8,3,2,7}B{2,3,5,7,8}C{8,5,7,3,2}D{8,7,5,3,2}第8题Existingnelementsneedtobeorganizedintoacompletebinarystack现有n个元素需要组织成一个完全二叉堆Ifyouusethemethodofconstantlyinsertingalltheelements若使用不断插入所有元素的方法Thewholeprocessis:整个过程是:ATop-downpercolateUp自上而下的上滤BTop-downpercolateDown自上而下的下滤CDown-toppercolateUp自下而上的上滤DDown-toppercolateDown自下而上的下滤第9题（接上题）Thetimecomplexityis:时间复杂度为:AO(lgn)BO(n)CO(nlgn)DO(n^2)第10题IfuseFloydmethod若使用Floyd算法Thewholeprocessis:整个过程是:ATop-downpercolateUp自上而下的上滤BTop-downpercolateDown自上而下的下滤CDown-toppercolateUp自下而上的上滤DDown-toppercolateDown自下而上的下滤第11题（接上题）Timecomplexityis:时间复杂度为:AO(lgn)BO(n)CO(nlgn)DO(n^2)第12题Heapsortingissimilartowhatsortofsortingyoulearnedintheproce