计算机专业基础综合数据结构历年真题试卷汇编1

计算机专业基础综合数据结构（串）历年真题试卷汇编1（总分:58.00，做题时间：90分钟）一、填空题（总题数：12,分数：24.00）设T和P是两个给定的串，在T中寻找等于P的子串的过程称为（1），又称P为（2）。【西安电子科技大学1998二、5（16/6分）】正确答案：（正确答案：（1）模式匹配（2）模式串）串是一种特殊的线性表，其特殊性表现在（1）;串的两种最基本的存储方式是（2）、（3）；两个串相等的充分必要条件是（4）。【中国矿业大学2000一、3（4分）】正确答案：（正确答案：（1）其数据元素都是字符（2）顺序存储（3）链式存储（4）串的长度相等且两串中对应位置的字符也相等）使用“求子串”subString（S,pos,len）和''联结"concat（S1,s2）的串操作，可从串s='conduction'中的字符得到串t=”cont”，则求t的串表达式为。【北京工业大学2005二、4（3分）】正确答案：（正确答案：t=concat（subStIling（s，1，3），subString（s，7，1）））下列程序读入无符号十六进制数（出现的字母为小写），将其转换为十进制数输出。请将程序空缺部分补全。intf（char*s）{intn=0，i；for（i=0；s[i]!="\0";i++）n=n*16+（1）；returnn；}main（）{chars[10]；scanf（"％s”，s）；printf（"％d\n”（2））；}【浙江大学2002二（6分）】正确答案：(正确答案：(1)(s[i]>=977s[i]—87：s[i]-48)//"a"到"f”的ASCII码是97到102(2)f(s))巳知U='xyxyxyxxyxy'；t='xxy'；ASSIGN(S，U)；ASSIGN(V，SUBSTR(S，INDEX(s，t)，LENCt)+1)),ASSIGN(m，'ww')求REPLACE(S，y，m)=。【东北大学1997一、1(5分)】正确答案：（正确答案：'xyxyxywwy'）实现字符串拷贝的函数strcpy为：voidstrcpy（char*s，char*t）/*copyttos*/{while（））【浙江大学1999一、5（3分）】正确答案：（正确答案：*s++=*t++或（*s++=*t++）!='\0'）下列程序判断字符串s是否对称；对称则返回1，否则返回0；如f“abba”）返回1，f"abab”）返回0。intf（（1））{inti=0，j=0；while（8[j]）（2）；for（J一一；i正确答案：(正确答案：(I)chars[](或char*s)(2)j++(3)i>=j)下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。voidmaxcomstr(order8tring*s，*t，intindex，length)(inti，j，k，lengthl，con；index=0；length=0；i=1；while(i<=s.1en){j=1；while(j<=t.1en){if(S[i]_=t[j])ik=1;lengthl=1;con=1;while(con)if(1){lengthl=leng七h1+1;k=k+1;)else(2);if(1engthl>length)(index=i；length=length1；)(3);}else(4)；}(5)}}【上海大学2000一、2(10分)】正确答案：（正确答案：本题算法采用顺序存储结构求串S和串t的最大公共子串。串s用i指针（1WiWs.len）。串t用j指针（1WjWr.len）。算法思想是对每个i（1WiWs.len，即程序中第一个while循环），来求从i开始的连续字符串与从f（1WjWt.len，即程序中第二个while循环）开始的连续字符串的最大匹配。程序中第三个（即最内层的）while循环，是当S中某字符（s[i]）与t中某字符（t[f]）相等时，求出局部公共子串。若该子串长度大于巳求出的最长公共子串（初始为0），则最长公共子串的长度要修改。（1）i+k<=s.len&&J+k<=t.len&&s[i+k]==t[j+k]//如果在s和t的长度内，对应字符相等，则指针k后移（加1）（2）con=0//s和t对应字符不等时置标记退出（3）j=j+k//在t串中，从第j+k字符再与s[i]比较（4）j=j+1//t串取下一字符（5）i=i+1//s串指针i后移（加1））下列是判断是否为回文(顺读与逆读字符串一样，串中不含空格)的算法。#include#include#include#defineStackSize100//定义栈类型typedefstruct{chardata[StackSize]；intTop;)SeqStack；charStr[100]="madamimadam”；voidPush(SeqStack*s,charx)//进栈(if(S—>Top=：stacksize一1)printf("Stackoverflow”)；(1)；)charPop(SegStack*s)//出栈{if,(S—>Top==—1)printf(”Stackunderflow”)；return(2)；}intIsHuiwen(char*S){SeqStackT；inti,n；chartl；T.Top=一1；n=strlen(s)；//求向量长度for(i=0；i<n/2；i++)Push(&T,S[i])；//将一半字符入栈i=n/2—1；while(i>=0){tl=(3)；//每弹出一个字符与相应字符作比较if((4))return0；//不相等则返回0i一一；}return1；1//比较完毕均相等则返回1voidmain(){if(IsHuiwen(Str))printf("\n这个字符串是回文。")；elseprintf("\n这个字符串不是回文。")；}【北京交通大学2006七、2(8分)】正确答案：(正确答案：(1)S—>data[++s—>Top]=x(2)S—>dataIs—>Top一一](3)S[i](4)s[i]!=T[i])算法填空。/*copyacharacterstringfrom。from'to。to。’/voidcopystring(to,from)char*to,*from；{while(*from){(1)；++from；(2)；)*to='\0'；}/*searchalinkedlistforspecifiedvalue*/structlistrec{intvalue；structlistrec*next；)structlistrec*search(listptr,match)structlistrec*listptr；intmatch；{while(listptr!=(3))1f((4)==match)breakelse(5);return(1istptr)；}【中国海洋大学2006四(10分)】正确答案：(正确答案：(1)*to：*from(2)++to(3)null(4)listptr—>value(5)return(null))设模式T="abcabaabc"，求它的next函数的修正值nextval,下面的函数用于求模式T的nextval之值。其中，T[0]用于保存模式T的字符个数，而T[1],T[2],……，T[M]依次保存模式T的各个字符。请在该函数中的[A]、[B]处各填入一个赋值表达式，使得数组nextval能够给出模式T的next函数的修正值nextval。voidget一nextval(sstringT,int&nextval[]){i=I,nextval[1]=0；j=0；while(i正确答案：(正确答案：[A]nextval[i]=nextval[j][B]j=nextval[j])以下程序的功能是把一个输入字符串倒序输出，请找出并改正其中的错误。voidreverse(char*s){intlen=strlen(S)；char*dest=newchar[1en]；inti=0;while(1en-一！=0){}printf(…)；return0；}【北京大学2008三(10分)】正确答案：(正确答案：(1)第一个循环体…处应是赋值语句：*(dest+i++)=*(s+len)；(2)printf的…处应该输出倒序的字符串：“％s”，dest(3)函数类型是void，不应有返回值，要删除return0；)二、综合题(总题数：14，分数：34.00)串。【大连海事大学1996一、10(1分)】【河海大学1998二、5(3分)】正确答案：(正确答案：串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表相比，其特殊性在于串的元素是字符，串的操作经常以整体(字符串)出现。)描述以下概念的区别：空格串与空串。【大连海事大学1996三、2.(1)(2分)】正确答案：(正确答案：空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零，其ASCII码值是0。)两个字符串S1和S2的长度分别为m和n。求这两个字符串最大共同子串算法的时间复杂度为T(m,n)。估算最优的r(m,n),并简要说明理由。【北京工业大学1996_、5(6分)】正确答案：(正确答案：最优的T(m,n)是O(n)。S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度。一般情况下，T(m,n)=O(m*n)。)KMP算法(字符串匹配算法)较Brute算法(朴素的字符串匹配算法)有哪些改进？【大连海事大学1996三、l(2分)】正确答案：（正确答案：朴素的模式匹配（Brute-Force）时间复杂度是O（m*n）,KMP算法有一定改进，时间复杂度达到O（m+n）。主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。）给出字符串’abacabaaad’在KMP算法中的next和nextval数组。【北京邮电大学2000三、1（5分）】正确答案：（正确答案：模式串的next函数定义如下：当此集合不空时根据此定义，可求解模式串IWn-inj"abacabaaad"的next和nextval值如下：）设字符串S="aabaabaabaac’，P=aabaac’。（分数：4.00）（1）.给出S和P的next值和nextval值;正确答案：（正确答案：S的next与nextval值分别为012123456789和002002002009。P的next与nextval值分别为012123和002003o）（2）.若S作主串，P作模式串，试给出利用BF算法和KMP算法的匹配过程。【北方交通大学1998二（15分）】正确答案：（正确答案：利用BF算法的匹配过程：利用KMP算法的匹配过程：第一趟匹配：aabaabaabaac第一趟匹配：aabaabaabaacaabaac（i=6，j=6）aabaac（i=6，j=6）第二趟匹配：aabaabaabaac第二趟匹配：aabaabaacaa（i=3，j=2）（aa）baac第三趟匹配：aabaabaabaac第三趟匹配：aabaabaabaaca（i=3，j=1）（成功）（aa）baac第四趟匹配：aabaabaabaacaabaac（i=9，j=6）第五趟匹配：aabaabaabaacaa（i=6，j=2）第六趟匹配：aabaabaabaaca（i=6，j=1）第七趟匹配：aabaabaabaac（成功）aabaac（i=13，j=7））设目标为t="abcaabbabcabaacbacba"，模式为p="abcabaa"°（分数：4.00）（1）.计算模式p的nextval函数值；（5分）正确答案：（正确答案：P的nextval函数值为0110132（p的next函数值为0111232）。）（2）.不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。（5分）【清华大学1998八（10分）】正确答案：（正确答案：利用KMP（改进的nextval）算法，每趟匹配过程如下：第一趟匹配：abcaabbabcabaacbacbaabcab（i=5，j=5）第二趟匹配：abcaabbabcabaacbacbaabc（i=7，j=3）第三趟匹配：abcaabbabcabaacbacbaa（i=7，j=1）第四趟匹配：abcaabbabcabaacbacba（成功）abcabaa（i=15，j=8））模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m，模式的长度为n，则在主串中寻找模式的KMP算法的时间复杂性是多少？如果某一模式’P=-"abcaacabaca”，请给出它的NEXT。函数值及NEXT函数的修正值NEXTVAL之值。【上海交通大学2000一（5分）】正确答案：（正确答案：KMP算法的时间复杂度是O（m+n）。P的NEXT和NEXTVAL值分别为01112212321和01102201320。）设目标为S="abcaabbcaaabababaabca’，模式为P="babab"°（分数：4.00）（1）.手工计算模式P的nextval数组的值；（5分）正确答案：（正确答案：p的nextval函数值为01010（next函数值为01123）。）（2）.写出利用求得的nextval数组，按KMP算法对目标S进行模式匹配的过程。（5分）【清华大学1997四（10分）】正确答案：（正确答案：手工模拟对s的匹配过程，与上面第6题类似，为节省篇幅，故略去。）设模式串t为"abcabcacabca"，，给出其失败函数。【吉林大学2007二、6（3分）】正确答案：（正确答案：模式串"abcabcacabca"的失败函数为：011123451234。）主串$="abbacbabbcabbcabbcabcaabbc”，子串=“abbcabcaa"，若用简单模式匹配算法，查找成功需要比较多少次?若用.KMP算法，查找成功需要比较多少次?并计算出相应的NEXT[]数组和NEXTVAL：]数组值。【大连理工大学2005二、4（20/4分）】正确答案：（正确答案：简单模式匹配算法，查找成功需要比较15趟39次。若用KMP算法，查找成功需要比较，7趟27次。NEXT[]和NEXTVAL：]数组值分别是011112312和011101.302。）I-在字符串模式匹配的KMP算法中，求模式的next数组值的定义如下：——请问：（1）当j=1时，为什么要取next[1]=0?（2）为什么要取max{埘，尼最大是多少？（3）其他情况是什么情况?为什么取next[j]=17【北京邮电大学1994二（8分）】正确答案：（正确答案：（1）当模式串中第一个字符与主串中某字符比较不等（失配）时，next[1]=0表示模式串中巳没有字符可与主串中当前字符s[t]比较，主串当前指针应后移至下一字符，再和模式串中第一个字符进行比较。（2）当主串第i个字符与模式串中第j个字符失配时，若主串f不回溯，则假定模式串第k个字符与主串第i个字符比较，k值应满足条件1<k<j并且。"p1pk-1"="pi-k+1--pi-1-，即k为模式串向后移动的距离，k