4多选顺序栈是用一段连续的空间存储内容，本质是顺序表。链式栈则是采用单链表的方式存储。下列关于这两种存储方式的说法正确的是：Sequentialstackstoreselementsinacontiguousspace,whichisessentiallyasequentiallist.Linkedstackisimplementedbyasinglelinkedlistinstead.Whichofthefollowingaboutthetwostoragemethodsarecorrect?(multiplechoice)
A.顺序栈的压栈和出栈操作只需常数时间。Thepushandpopoperationofsequencestackonlyneedsconstanttime.
B.链式栈的压栈和出栈操作只需常数时间。Thepushandpopoperationoflinkedstackonlyneedsconstanttime.
C.顺序栈需要指定一个具体的长度Sequentialstackneedstobeassignedaspecificlength.
D.链式栈需要一个结构性开销Linkedstackneedsastructuralcost.
5填空按照课程中介绍的机械的递归转换，将下列递归过程改写为非递归过程后，程序中需要设置____个语句标号。Accordingtothedescriptioninclassaboutrecursivemechanicalconversion,rewrittenthefollowingrecursiveprocedureintononrecursiveprocess,theprogramneedsset____statementlabels.voidtest(int&sum){intx;scanf(x);if(x==0){test(sum);sum=0;}else{test(sum);sum+=x;}printf(sum);}
6填空若字符串s=”DataMining”，则其子串的数目为（字串数目应该重复计算）Ifthestrings=”DataMining”,thenthenumberofitssubstringsis:________.（Ifweencounterthesamesubstring,thetotalshouldbeaddedone）
7多选在字符{A,C,G,T}组成的DNA序列中，A——T和C——G是互补对。判断一个DNA序列中是否存在互补回文串（例如，ATCATGAT的补串是TAGTACTA，与原串形成互补回文串；即要求整个原串的补串是原串的逆序）；下面DNA序列中存在互补回文串的是：(多选)InDNAsequencesconsistingofcharacters{A,C,G,T},A-TandC-Garecomplementarypairsrespectively.DeterminewhetheraDNAsequencehasacomplementarypalindromicstring(Forexample,ATCATGAT’scomplementarystringisTAGTACTA,withisthepalindromicsequencetotheoriginalstring;insuchcasethecomplementarystringisalsothereverseoftheoriginalstring);WhichofthefollowingDNAsequenceshavecomplementarypalindromicstring?（multiplechoice）
A.CTGATCAG
B.AATTAATT
C.GTACGTAC
D.AGCTAGCT
8填空使用KMP算法求出模式p=”aabcaabbaa”的优化后的next数组。注意：只列出数字，数字之间用一个空格分隔。比如：0000000000UseKMPalgorithmtoderivetheoptimized”next”arrayforthepatternp=”aabcaabbaa”.Note:Writedownthenumbersinthenextarrayseparatedbysinglespace.Forexample:0000000000
数据结构与算法
北京大学
军职在线答案
大学网课