MOOC 数据结构与算法-北京大学 中国大学慕课答案

MOOC数据结构与算法-北京大学中国大学慕课答案第一章概论测验1、问题：下列不属于线性结构的是：Whichoneofthefollowingsdoesnotbelongtolinearstructure:（Thereisonlyonecorrectanswer）选项：A、队列(queue)B、散列表(hashtable)C、向量(vector)D、图(graph)正确答案:【图(graph)】2、问题：以下哪种结构是逻辑结构，而与存储和运算无关：Whichofthefollowingstructureisalogicalstructureregardlessofthestorageoralgorithm:（Thereisonlyonecorrectanswer）选项：A、队列(queue)B、双链表(doublylinkedlist)C、数组(array)D、顺序表(Sequentiallist)正确答案:【队列(queue)】3、问题：关于算法特性描述正确的有：Whichoneisrightaboutalgorithm’scharacterization:（therearemorethanonecorrectanswers）选项：A、算法保证计算结果的正确性。Algorithmwillensurethecorrectnessofthecalculationresults.B、组成算法的指令可以有限也可能无限。InstructionswhichcompositealgorithmscanbeinfiniteorfiniteC、算法描述中下一步执行的步骤不确定。Thenextstepintheimplementationofthealgorithmdescribedisuncertain.D、算法的有穷性指算法必须在有限步骤内结束。Thefinitenatureofalgorithmsmeansalgorithmmustbecompletedwithinalimitedstep.正确答案:【算法保证计算结果的正确性。Algorithmwillensurethecorrectnessofthecalculationresults.#算法的有穷性指算法必须在有限步骤内结束。Thefinitenatureofalgorithmsmeansalgorithmmustbecompletedwithinalimitedstep.】4、问题：下列说法正确的是：Whichoptionsmaybecorrect?（therearemorethanonecorrectanswers）选项：A、如果函数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、如果函数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、函数f(n)是O(g(n))，当常数a足够大时，一定有函数g(n)是O(af(n))【iff(n)是O(g(n))，Whenconstantaisbigenough，theremustbeg(n)isO(af(n))】正确答案:【如果函数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))】#如果函数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、问题：已知一个数组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)（提示：系统基于字符匹配来判定答案，所以您的答案中不要出现空格）Writethefollowingtimecomplexityindescendingsequence:Writedowntheanswerlabelssuchas(1)(2)(3)(4)(5).（Hint：Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.）正确答案:【(5)(1)(2)(4)(3)】第二章线性表测验1、问题：下面关于线性表的叙述中，正确的是哪些？Whichofthefollowingsaboutlinearlistarecorrect?（Therearemorethanoneanswers.）Selecttheanswerthatmatches选项：A、线性表采用顺序存储，必须占用一片连续的存储单元。Linearlistsusesequentialstoragewhichmustoccupyacontinuousmemoryunits.B、线性表采用顺序存储，便于进行插入和删除操作。Linearlistsusingsequentialstorage,itiseasytodoinsertanddeleteoperations.C、线性表采用链接存储，不必占用一片连续的存储单元。Linearlistsusingthelinkedstorage,donotoccupyacontinuousmemoryunits.D、线性表采用链接存储，便于插入和删除操作。Linearlistsusingthelinkedstorage,itiseasyforinsertanddeletingoperations.正确答案:【线性表采用顺序存储，必须占用一片连续的存储单元。Linearlistsusesequentialstoragewhichmustoccupyacontinuousmemoryunits.#线性表采用链接存储，不必占用一片连续的存储单元。Linearlistsusingthelinkedstorage,donotoccupyacontinuousmemoryunits.#线性表采用链接存储，便于插入和删除操作。Linearlistsusingthelinkedstorage,itiseasyforinsertanddeletingoperations.】2、问题：下面的叙述中正确的是：Selecttheanswerthatmatches（Therearemorethanonecorrectanswers）选项：A、线性表在链式存储时，查找第i个元素的时间与i的数值无关。Whenthelinearliststoredinlinkedform,thetimetofindthei-thelementisregardlessofthevalueofi.B、线性表在顺序存储时，查找第i个元素的时间与i的数值成正比。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisproportionaltovaluewithi.C、线性表在顺序存储时，查找第i个元素的时间与i的数值无关。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisregardlessofthevalueofi.D、线性表在链式存储时，插入第i个元素的时间与i的数值成正比。Whenlinearlistsstoredinthelinkedform,thetimetoinsertthei-thelementisproportionaltovaluewithi.正确答案:【线性表在顺序存储时，查找第i个元素的时间与i的数值无关。Whenthelinearliststoredsequentially,thetimetofindthei-thelementisregardlessofthevalueofi.#线性表在链式存储时，插入第i个元素的时间与i的数值成正比。Whenlinearlistsstoredinthelinkedform,thetimetoinsertthei-thelementisproportionaltovaluewithi.】3、问题：完成在双循环链表结点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),如果您的答案中出现字母，请使用小写;后一空系统基于字符匹配来判定答案，所以您的答案中不要出现空格）Forasinglelinkedlistwithnnodes,andafteraknownnode*ptoinsertanewnode,thetimecomplexityisO(___);afteragivennodewithxvalueinsertanewnode,thetimecomplexityisO(___).(Ifyouranswercontainsletters,uselowercaseone.Thesecondblankisjudgedbystringmatching,Pleasemakesureyouranswerdon'tcontainanyblanks.)正确答案:【(1)(n)】5、填空题：设某循环链表长度为n，并设其中一节点为p1，然后按照链表的顺序将后面的节点依次命名为p2,p3,...,pn，那么请问pn.next=____(答案为一个节点名，注意所有字母为小写且答案中不包含空格)正确答案:【p1】第三章栈与队列测验1、问题：设栈S和队列Q的初始状态为空，元素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、问题：现有中缀表达式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、问题：以下循环队列的实现方式中，长度为n的队列，所能容纳的元素个数也为n的有:Inthefollowingrealizingwaysofcircularqueue,thequeuewhoselengthisncanalsocontainthenumberofnelementsis:（Therearemorethanoneanswers.）选项：A、只用front和rear两个指针标记队列的头和尾，两个指针均为实指Onlyusefrontandrearasthequeue’sheadandtailpointersandthetwopointersareactuallyreferringto.B、用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数Withthequeue’sheadandtailpointersmarkedasfrontandrear,usetheintegervariablelentorecordthenumberofelements.C、用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空Withthequeue’sheadandtailpointersmarkedasfrontandrear,useBooleanvariableemptyrecordwhetherthequeueisempty.D、只用front和rear两个指针标记队列的头和尾，两个指针均为虚指Onlyusefrontandrearasthequeue’sheadandtailpointersandthetwopointersarevirtuallyreferringto.正确答案:【用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数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、填空题：双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。现有4个不同的元素顺序输入到双端队列，那么可以得到_____种不同的排列。double-endedqueuecaninsertanddeleteoperationsonbothendsofthequeue.Thatitcaninsert/deleteatitstail,butalsoatthehead.Existing4differentelementssequentiallyinputtothedouble-endedqueue,youcanget_____differentpermutations.正确答案:【8】第四章字符串测验1、问题：设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为()（单选）Therearetwostringspq,qisp’ssubstring.Thealgorithmtosearchthefirsttimeqappearedinpiscalled()（Thereisonlyonecorrectanswer）选项：A、求子串SeekingsubstringB、联接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’,执行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、串是一种数据对象和操作都特殊的线性表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”，则其子串个数为：Ifthestrings=software,thenthenumberofitssub-stringis:正确答案:【37】8、填空题：若字符串s=”algorithm”，则其子串个数为：Ifthestrings=algorithm,thenthenumberofitssub-stringis:正确答案:【46】9、填空题：设有字符串变量StringA＝“”，B＝“MULE”，C＝“OLD”，D＝“MY”;请计算下列表达式（3个答案本身不要出现空格，答案之间用空格分开）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、非空满二叉树的结点个数一定为奇数个。Theamountofnodesofafullbinarytreewithatleastonenodemustbeodd.B、非完全二叉树也可以用像完全二叉树那样使用顺序存储结构进行存储。Sequentialstoringstructurecanalsobeusedtostoreanincompletebinarytreejustliketostoreacompletebinarytree.C、当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。Ifacompletebinarytreeisafullbinarytree,itwillbepossiblethatleafnodesisnotonthenethermostlayer.D、完全二叉树最多只有最下面的一层结点度数可以小于2。Foracompletebinarytree,onlythedegreesofnodesonthenethermostlayercouldbelessthan2.E、一棵非空二叉树的为空的外部结点数目等于其结点数加1。Theamountofexternalnullnodesinabinarytreewithatleastonenodeequalstoitsamountofnodesplus1.F、满二叉树的所有结点的度均为2。Alldegreesofnodesinafullbinarytreeare2.正确答案:【非空满二叉树的结点个数一定为奇数个。Theamountofnodesofafullbinarytreewithatleastonenodemustbeodd.#当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。Ifacompletebinarytreeisafullbinarytree,itwillbepossiblethatleafnodesisnotonthenethermostlayer.#一棵非空二叉树的为空的外部结点数目等于其结点数加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的结点的个数n，度为2的结点个数为m，则有n=________(系统根据字符串匹配来判定答案，所以您的答案中请不要包含空格)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、堆是实现优先队列的惟一方法。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、问题：一组包含不同权的字母已经对应好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个关键码值中选取，平均比较次数为多少？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}，用筛选法建最小值堆，若一旦发现逆序对就进行交换，共需要交换元素多少次？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、填空题：下表展示了在一段文本中每个字母出现的次数。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的结点数分别为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的结点数分别为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