中国大学mooc《数据结构与算法(北京大学) 》章节测试答案_第1页
中国大学mooc《数据结构与算法(北京大学) 》章节测试答案_第2页
中国大学mooc《数据结构与算法(北京大学) 》章节测试答案_第3页
中国大学mooc《数据结构与算法(北京大学) 》章节测试答案_第4页
中国大学mooc《数据结构与算法(北京大学) 》章节测试答案_第5页
已阅读5页,还剩20页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

title数据结构与算法(北京大学)中国大学mooc答案100分最新版content第一章概论第一章概论测验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:组成算法的指令可以有限也可能无限。Instructionswhichcompositealgorithmscanbeinfiniteorfinite

C:算法描述中下一步执行的步骤不确定。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)),then

f(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:如果a>b>1,是,但不一定是ifa>b>1,

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)),then

f(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;i<n-1;i++){

for(j=i+1;j<n&&a[j-1]<=a[j];j++)

if(length<j-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

分析:注意i从1到9全部遍历,j分别从2,4,6,…开始遍历到9,当i大于5时,循环不再对m进行操作.

i=1结束循环时,m=8;

i=2结束循环时,m=8+6=14;

i=3结束循环时,m=14+4=18;

i=4结束循环时,m=18+2=20;7、由大到小写出以下时间复杂度的序列:答案直接写标号,如:(1)(2)(3)(4)(5)(提示:系统基于字符匹配来判定答案,所以您的答案中不要出现空格)Writethefollowingtimecomplexityindescendingsequence:Writedowntheanswerlabelssuchas(1)(2)(3)(4)(5).(Hint:Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon’tcontainanyblanks.)

答案:(5)(1)(2)(4)(3)

分析:计算复杂度时,系数是可以忽略的。(5)和(1)是指数级复杂度,大于(2)(3)(4)多项式级复杂度,区别在于指数中是否有n。而(5)的指数里还有指数级复杂度的表达式,(1)的指数是n,为多项式级,故(5)比(1)复杂。对于(2)(3)(4),(2)的指数最大,为2.5,(4)的指数居中,为2,(3)的指数最小,解释如下:logn的任意实数次方的复杂度都小于n,故(logn)^4比n复杂度低,故n(logn)^4比nn复杂度低,故(4)比(3)复杂,故答案为(5)(1)(2)(4)(3)第二章线性表第二章线性表测验1、下面关于线性表的叙述中,正确的是哪些?Whichofthefollowingsaboutlinearlistarecorrect?(Therearemorethanoneanswers.)SelecttheanswerthatmatchesA:线性表采用顺序存储,必须占用一片连续的存储单元。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)

分析:已知结点后插入,不需要移动其他结点位置,所以为O(1)2.先要查找到值为x的结点,需要O(n),再插入,不需要移动其他结点位置,需要O(1),总共需要O(n)+O(1)=O(n)5、设某循环链表长度为n,并设其中一节点为p1,然后按照链表的顺序将后面的节点依次命名为p2,p3,…,pn,那么请问pn.next=____(答案为一个节点名,注意所有字母为小写且答案中不包含空格)

答案:p1

分析:循环链表尾结点的next会指向头结点第三章栈与队列第三章栈与队列测验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:2

B:3

C:4

D:6

答案:32、现有中缀表达式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–3672

C: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

分析:出栈次序是经典的问题,与组合数学中的卡特兰数密切相关,以下只介绍朴素的思路。

先进站的车可以先开,也可以后开。只有一种情况不可能:编号大的车开出后,比其编号小的车反序开出。也即编号大的车开出后,编号比其小的车只能由大到小依次开出(中间可以插入编号更大的车,但此车后面的编号小的车也要遵守此规则)。例如312的开出顺序是不可能的。对所有车进行全排列共有24种出法。但4开头的只能有一种:4321。所以少了3的全排列-1=5种。三开头的时候,必须先2后1开出,先1后2时4的位置有三种:3124、3142、3412,所以少了三种。1或2开头的时候,后面的车如果是4,则最后两辆必须是3、2或3、1。所以又少了1423、2413两种。总共少了5+3+2=10种,有24-10=14种开出法。

下面用+表示进站,-表示出站:

1234:1+;1-;2+;2-;3+;3-;4+;4-

1243:1+;1-;2+;2-;3+;4+;4-;3-

1324:1+;1-;2+;3+;3-;2-;4+;4-

1342:1+;1-;2+;3+;3-;4+;4-;2-

1432:1+;1-;2+;3+;4+;4-;3-;2-

2134:1+;2+;2-;1-;3+;3-;4+;4-

2143:1+;2+;2-;1-;3+;4+;4-;3-

2314:1+;2+;2-;3+;3-;1-;4+;4-

2341:1+;2+;2-;3+;3-;4+;4-;1-

2431:1+;2+;2-;3+;4+;4-;3-;1-

3214:1+;2+;3+;3-;2-;1-;4+;4-

3241:1+;2+;3+;3-;2-;4+;4-;1-

3421:1+;2+;3+;3-;4+;4-;2-;1-

4321:1+;2+;3+;4+;4-;3-;2-;1-;6、双端队列可以在队列的两端进行插入和删除操作,既可在队尾进行插入/删除,又可在队头进行插入/删除。现有4个不同的元素顺序输入到双端队列,那么可以得到_种不同的排列。double-endedqueuecaninsertanddeleteoperationsonbothendsofthequeue.Thatitcaninsert/deleteatitstail,butalsoatthehead.Existing4differentelementssequentiallyinputtothedouble-endedqueue,youcanget

___differentpermutations.

答案:8

分析:第一个元素从左或右入队没有区别,以后每个元素都有从左和从右两种入队方式,即有2^{x-1}种方法。第五章二叉树第五章二叉树前半部分(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)

答案:94、一棵有512个结点的完全二叉树的高度为多少?(独根树高度为1)Whatistheheightofacompletebinarytreewith512nodes?(theheightofatreewithonlyarootis1)

答案:105、在一棵非空二叉树中,若度为0的结点的个数n,度为2的结点个数为m,则有n=_

(系统根据字符串匹配来判定答案,所以您的答案中请不要包含空格)

Forabinarytreewithatleastonenode,iftherearennodeswithdegree0andmnodeswithdegree2,thenn=

_(Thisproblemisjudgedbystringmatching,Pleasemakesureyouranswerdon’tcontainanyblanks.)

答案:m+16、已知一棵树的前序遍历为ABDEGCF,中序遍历为DBGEACF,求这棵树的后序遍历。(字母和字母之间不要有空格)ThepreordersequenceofatreeisABDEGCF,anditsinfixordersequenceisDBGEACF,pleasewritedownitspostordersequence.(Thereisnoblankspacebetweenletters)

答案:DGEBFCA7、已知一棵树的中序遍历为DBGEACF,后序遍历为DGEBFCA,求这棵树的前序遍历。(字母和字母之间不要有空格)TheinfixordersequenceofatreeisDBGEACF,anditspostordersequenceisDGEBFCA,pleasewritedownitspreordersequence.(Thereisnoblankspacebetweenletters)

答案:ABDEGCF8、请写出下面这棵二叉树的前序遍历(字母和字母之间不要有空格)

Pleasewritedownthepreordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)

答案:BEXLMKCPDHQA9、请写出下面这棵二叉树的中序遍历(字母和字母之间不要有空格)

Pleasewritedowntheinfixordersequenceofthefollowingbinarytree.(Thereisnoblankspacebetweenletters)

答案:LXMECKPBQHDA10、请写出下面这棵二叉树的后序遍历(字母和字母之间不要有空格)

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;

(1+n)/26、从空二叉树开始,严格按照二叉搜索树的插入算法(不进行旋转平衡),逐个插入关键码{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)

答案:1810573682725413251997、从空二叉树开始,严格按照二叉搜索树的插入算法(不进行旋转平衡),逐个插入关键码{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)

答案:5102532514127689973188、从空二叉树开始,严格按照二叉搜索树的插入算法(不进行旋转平衡),逐个插入关键码构造出一棵二叉树,以怎样的顺序插入关键码集合{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.

答案:1269472914327863819、对于关键码序列{38,64,52,15,73,40,48,55,26,12},用筛选法建最小值堆,若一旦发现逆序对就进行交换,共需要交换元素多少次?Forthekeyvaluesequence

{38,64,52,15,73,40,48,55,26,12},usethescreeningmethodtoconstuctaminimumheap,ifweexchangethemwhenwefindreversedorder,thenhowmanytimesshouldweexchangethem?

答案:610、对于如下图所示的最大堆,删除掉最大的元素后,堆的前序遍历结果是Forthefollowingmaximumheap,afterdeletingthemaximumelement,thepreordertraversalsequenceis请依次写出插入到树中的元素,每两个元素之间用一个空格隔开。Pleasewritedowntheelementssuccessively,andthereisoneblankspacebetweentwoelements.

答案:5943241223372855748311、对于如下图所示的最大堆,删除掉最大的元素后,堆的后序遍历结果是Forthefollowingmaximumheap,afterdeletingthemaximumelement,thepostordertraversalsequenceis

答案:1223242853743483575912、下表展示了在一段文本中每个字母出现的次数。Thefrequenciesthateachletterappearsinaparagraphisrepresentedasfollow.对于这段文本使用Huffman编码相较使用等长编码能够节约多少比特的空间?Comparingtousecodesthathavethesamelength,howmanybitsofspacecouldbesavedwhenweuseHuffmancodefortheparagraph?

答案:3613、对于给定的一组权W={1,4,9,16,25,36,49,64,81,100},构造一棵具有最小带权外部路径长度的三叉树,写出这棵树的带权外部路径长度。ForagivengroupofweightsW={1,4,9,16,25,36,49,64,81,100},pleaseconstructaternarytreewithaminimumweightedroutelengthandwritedownthisweightedroutelength.

答案:70514、请阅读下面一段代码

PleasereadthefollowingcodeC++:Python:若此段代码的作用是用来进行前序遍历,那么应该在几号访问点进行访问?(只需要填写数字)ifthiscodeisusedtodoapreordertraversal,whichvisitingpointshouldbevisited?(Youonlyneedtowritedownthenumber)

答案:115、请阅读下面一段代码PleasereadthefollowingcodeC++:Python:若此段代码的作用是用来进行中序遍历,那么应该在几号访问点进行访问?(只需要填写数字)ifthiscodeisusedtodoaninfixordertraversal,whichvisitingpointshouldbevisited?(Youonlyneedtowritedownthenumber)

答案:216、请阅读下面一段代码Pleasereadthefollowingcode

C++:Python:若此段代码的作用是用来进行后序遍历,那么应该在几号访问点进行访问?(只需要填写数字)ifthiscodeisusedtodoanpostordertraversal,whichvisitingpointshouldbevisited?(Youonlyneedtowritedownthenumber)

答案:3第四章字符串第四章字符串测验1、设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为()(单选)Therearetwostringspq,qisp’ssubstring.Thealgorithmtosearchthefirsttimeqappearedinpiscalled()(Thereisonlyonecorrectanswer)A:求子串Seekingsubstring

B:联接Concatenation

C:匹配

Matching

D:求串长

Seekinglength

答案:匹配

Matching2、下列说法正确的是:(单选)

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:ABC###G0123

B:ABCD###2345

C:ABCD###1234

D:ABC###G2345

答案:ABCD###12344、下面关于串的的叙述中,哪一个是不正确的:(单选)

Whichofthefollowingdescriptionsaboutstringisnotcorrect?(Thereisonlyonecorrectanswer)A:串是字符的有限序列Stringisafinitesequenceofcharacters.

B:模式匹配是串的一种重要运算Patternmatchingisanimportantoperation.

C:串是一种数据对象和操作都特殊的线性表Stringisalinearlist

whosedataobjectsandoperationsbothspecial

D:空串是由空格构成的串

Emptystringisastringconsistingofspaces.

答案:空串是由空格构成的串

Emptystringisastringconsistingofspaces.5、Seekthestring“BAAABBBAA”‘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).WhichofthefollowingDNAsequenceshavecomplementarypal

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论