1、计算机专业基础综合数据结构（串）历年真题试卷汇编 1及答案解析(总分：58.00，做题时间：90 分钟)一、填空题(总题数：12，分数：24.00)1.设 T和 P是两个给定的串，在 T中寻找等于 P的子串的过程称为(1)，又称 P为(2)。【西安电子科技大学 1998二、5(166 分)】（分数：2.00）_2.串是一种特殊的线性表，其特殊性表现在(1) ；串的两种最基本的存储方式是(2)、(3)；两个串相等的充分必要条件是(4)。【中国矿业大学 2000一、3(4 分)】（分数：2.00）_3.使用“求子串”subString(S，pos，len)和“联结”concat(S1，s2)的串操
2、作，可从串s=conduction中的字符得到串 t=”cont”，则求 t的串表达式为_。【北京工业大学 2005二、4(3 分)】（分数：2.00）_4.下列程序读入无符号十六进制数(出现的字母为小写)，将其转换为十进制数输出。请将程序空缺部分补全。 int f(char *s) int n=0，i； for(i=0；si!=“0“; i+)n=n*16+(1)； return n； main() char s10； scanf(“s”，s)；printf(“dn”(2) )； 【浙江大学 2002二(6 分)】（分数：2.00）_5.已知 U=xyxyxyxxyxy；t=xxy；ASSI
3、GN(S，U)；ASSIGN(V，SUBSTR(S，INDEX(s，t)，LENCt)+1),ASSIGN(m，ww)求 REPLACE(S，y，m)=_。【东北大学 1997一、1(5 分)】（分数：2.00）_6.实现字符串拷贝的函数 strcpy为：void strcpy(char*s，char*t)*copy t to s*while(_)【浙江大学 1999一、5(3 分)】（分数：2.00）_7.下列程序判断字符串 s是否对称；对称则返回 1，否则返回 0；如 f“abba”)返回 1，f“abab”)返回0。 int f(1) ) int i=0，j=0； while(8j)(2
4、) ； for(J 一一； i_8.下列算法实现求采用顺序结构存储的串 s和串 t的一个最长公共子串。 void maxcomstr(order8tring*s， *t， int index，length) (int i，j，k，lengthl，con； index=0；length=0；i=1； while(ilength) ( index=i； length=length1； ) (3) ; else(4)； (5) 【上海大学2000一、2(10 分)】（分数：2.00）_9.下列是判断是否为回文(顺读与逆读字符串一样，串中不含空格)的算法。 #include #include #inc
5、lude #define StackSize 100 定义栈类型 typedef structchar dataStackSize；int Top ;)SeqStack； char Str100=“madamimadam”； void Push(SeqStack*s，char x) 进栈 (if(S 一Top=：stacksize 一 1)printf(”Stack overflow”)； (1) ； ) char Pop(SegStack*s) 出栈 if，(S 一Top=一 1)printf(”Stack underflow”)； return (2) ； int IsHuiwen(cha
6、r*S) SeqStack T； int i，n；char tl； TTop=一 1； n=strlen(s)； 求向量长度 for(i=0；i=0) tl= (3) ； 每弹出一个字符与相应字符作比较 if( (4) ) return 0； 不相等则返回 0 i一一； return 1；1 比较完毕均相等则返回 1 void main() if(IsHuiwen(Str)printf(“n 这个字符串是回文。”)； else printf(“n 这个字符串不是回文。”)； 【北京交通大学 2006七、2(8 分)】（分数：2.00）_10.算法填空。 *copy a character st
7、ring from。fromto。to。 void copystring(to， from) char*to，*from； while(*from) (1) ；+from； (2) ；) *to=0； /*search a linked list for specified value* struct listrecint value； struct listrec*next；) struct listrec*search(listptr，match) struct listrec*listptr； int match； while(listptr!= (3) ) 1f( (4) =match
8、) break； else (5); return(1istptr)； 【中国海洋大学 2006四(10 分)】（分数：2.00）_11.设模式 T=“abcabaabc”，求它的 next函数的修正值 nextval，下面的函数用于求模式 T的 nextval之值。其中，T0用于保存模式 T的字符个数，而 T1，T2，TM依次保存模式 T的各个字符。请在该函数中的A、B处各填入一个赋值表达式，使得数组 nextval能够给出模式 T的 next函数的修正值 nextval。 void getnextval(sstring T，intnextval) i=I，nextval1=0；j=0； w
9、hile(i_12.以下程序的功能是把一个输入字符串倒序输出，请找出并改正其中的错误。 void reverse(char*s) int len=strlen(S)； char*dest=new char1en； int i=0 ; while(1en-一!=0) printf()； return 0； 【北京大学 2008三(10 分)】（分数：2.00）_二、综合题(总题数：14，分数：34.00)13.串。【大连海事大学 1996一、10(1 分)】【河海大学 1998二、5(3 分)】（分数：2.00）_14.描述以下概念的区别：空格串与空串。【大连海事大学 1996三、2(1)(2
10、分)】（分数：2.00）_15.两个字符串 S1和 S2的长度分别为 m和 n。求这两个字符串最大共同子串算法的时间复杂度为 T(m，n)。估算最优的 r(m，n)，并简要说明理由。【北京工业大学 1996_、5(6 分)】（分数：2.00）_16.KMP算法(字符串匹配算法)较 Brute算法(朴素的字符串匹配算法)有哪些改进? 【大连海事大学 1996三、l(2 分)】（分数：2.00）_17.给出字符串abacabaaad在 KMP算法中的 next和 nextval数组。【北京邮电大学 2000三、1(5 分)】（分数：2.00）_设字符串 S=“aabaabaabaac，P=aaba
11、ac。（分数：4.00）(1).给出 S和 P的 next值和 nextval值；（分数：2.00）_(2).若 S作主串，P 作模式串，试给出利用 BF算法和 KMP算法的匹配过程。【北方交通大学 1998二(15分)】（分数：2.00）_设目标为 t=“abcaabbabcabaacbacba“，模式为 p=“abcabaa“。（分数：4.00）(1).计算模式 p的 nextval函数值； (5 分)（分数：2.00）_(2).不写出算法，只画出利用 KMP算法进行模式匹配时每一趟的匹配过程。 (5 分)【清华大学 1998八(10分)】（分数：2.00）_18.模式匹配算法是在主串中快
12、速寻找模式的一种有效的方法，如果设主串的长度为 m，模式的长度为 n，则在主串中寻找模式的 KMP算法的时间复杂性是多少?如果某一模式P=-“abcaacabaca“，请给出它的NEXT。函数值及 NEXT函数的修正值 NEXTVAL之值。【上海交通大学 2000一(5 分)】（分数：2.00）_设目标为 S=“abcaabbcaaabababaabca，模式为 P=“babab“。（分数：4.00）(1).手工计算模式 P的 nextval数组的值；(5 分)（分数：2.00）_(2).写出利用求得的 nextval数组，按 KMP算法对目标 S进行模式匹配的过程。(5 分)【清华大学 19
13、97四(10 分)】（分数：2.00）_19.设模式串 t为“abcabcacabca“，给出其失败函数。 【吉林大学 2007二、6(3 分)】（分数：2.00）_20.主串$=“abbacbabbcabbcabbcabcaabbc“，子串=“abbcabcaa“，若用简单模式匹配算法，查找成功需要比较多少次?若用KMP 算法，查找成功需要比较多少次?并计算出相应的 NEXT数组和 NEXTVAL数组值。【大连理工大学 2005二、4(204 分)】（分数：2.00）_21.在字符串模式匹配的 KMP算法中，求模式的 next数组值的定义如下： （分数：2.00）_22.给出 KMP算法中失
14、败函数 f的定义，并说明利用厂进行串模式匹配的规则，该算法的技术特点是什么?【东南大学 1993一、3(9 分)1997 一、2(8 分)2001 一、6(6 分)】（分数：2.00）_23.在模试匹配 KMP算法中所用失败函数 f的定义中，为何要求 P 1 P 2 P f(f) 为 P 1 P 2 P i 两头匹配的真子串且为最大真子串?【东南大学 1996一、3(7 分)】（分数：2.00）_计算机专业基础综合数据结构（串）历年真题试卷汇编 1答案解析(总分：58.00，做题时间：90 分钟)一、填空题(总题数：12，分数：24.00)1.设 T和 P是两个给定的串，在 T中寻找等于 P的
15、子串的过程称为(1)，又称 P为(2)。【西安电子科技大学 1998二、5(166 分)】（分数：2.00）_正确答案：(正确答案：(1)模式匹配 (2)模式串)解析：2.串是一种特殊的线性表，其特殊性表现在(1) ；串的两种最基本的存储方式是(2)、(3)；两个串相等的充分必要条件是(4)。【中国矿业大学 2000一、3(4 分)】（分数：2.00）_正确答案：(正确答案：(1)其数据元素都是字符 (2)顺序存储 (3)链式存储(4)串的长度相等且两串中对应位置的字符也相等)解析：3.使用“求子串”subString(S，pos，len)和“联结”concat(S1，s2)的串操作，可从串s
16、=conduction中的字符得到串 t=”cont”，则求 t的串表达式为_。【北京工业大学 2005二、4(3 分)】（分数：2.00）_正确答案：(正确答案：t=concat(subStIling(s，1，3)，subString(s，7，1)解析：4.下列程序读入无符号十六进制数(出现的字母为小写)，将其转换为十进制数输出。请将程序空缺部分补全。 int f(char *s) int n=0，i； for(i=0；si!=“0“; i+)n=n*16+(1)； return n； main() char s10； scanf(“s”，s)；printf(“dn”(2) )； 【浙江大学
17、 2002二(6 分)】（分数：2.00）_正确答案：(正确答案：(1)(si=977 si一 87：si-48) “a“到“f“的 ASCII码是 97到 102 (2)f(s)解析：5.已知 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 分)】（分数：2.00）_正确答案：(正确答案：xyxyxywwy)解析：6.实现字符串拷贝的函数 strcpy为：void strcpy(char*s，char*t)
18、*copy t to s*while(_)【浙江大学 1999一、5(3 分)】（分数：2.00）_正确答案：(正确答案：*s+=*t+或(*s+=*t+)!= 0)解析：7.下列程序判断字符串 s是否对称；对称则返回 1，否则返回 0；如 f“abba”)返回 1，f“abab”)返回0。 int f(1) ) int i=0，j=0； while(8j)(2) ； for(J 一一； i_正确答案：(正确答案：(I)char s(或 char*s) (2)j+ (3)i=j)解析：8.下列算法实现求采用顺序结构存储的串 s和串 t的一个最长公共子串。 void maxcomstr(orde
19、r8tring*s， *t， int index，length) (int i，j，k，lengthl，con； index=0；length=0；i=1； while(ilength) ( index=i； length=length1； ) (3) ; else(4)； (5) 【上海大学2000一、2(10 分)】（分数：2.00）_正确答案：(正确答案：本题算法采用顺序存储结构求串 S和串 t的最大公共子串。串 s用 i指针(1is.len)。串 t用 j指针(1jr.len)。算法思想是对每个 i(1is.len，即程序中第一个while循环)，来求从 i开始的连续字符串与从 f(1
20、jt.len，即程序中第二个 while循环)开始的连续字符串的最大匹配。程序中第三个(即最内层的)while 循环，是当 S中某字符(si)与 t中某字符(tf)相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串(初始为 0)，则最长公共子串的长度要修改。 (1) i+kTop=：stacksize 一 1)printf(”Stack overflow”)； (1) ； ) char Pop(SegStack*s) 出栈 if，(S 一Top=一 1)printf(”Stack underflow”)； return (2) ； int IsHuiwen(char*S) SeqS
21、tack T； int i，n；char tl； TTop=一 1； n=strlen(s)； 求向量长度 for(i=0；i=0) tl= (3) ； 每弹出一个字符与相应字符作比较 if( (4) ) return 0； 不相等则返回 0 i一一； return 1；1 比较完毕均相等则返回 1 void main() if(IsHuiwen(Str)printf(“n 这个字符串是回文。”)； else printf(“n 这个字符串不是回文。”)； 【北京交通大学 2006七、2(8 分)】（分数：2.00）_正确答案：(正确答案：(1)S 一data+s 一Top=x (2)S 一d
22、ata Is 一Top 一一 (3)Si (4)si!=Ti)解析：10.算法填空。 *copy a character string from。fromto。to。 void copystring(to， from) char*to，*from； while(*from) (1) ；+from； (2) ；) *to=0； /*search a linked list for specified value* struct listrecint value； struct listrec*next；) struct listrec*search(listptr，match) struct l
23、istrec*listptr； int match； while(listptr!= (3) ) 1f( (4) =match) break； else (5); return(1istptr)； 【中国海洋大学 2006四(10 分)】（分数：2.00）_正确答案：(正确答案：(1)*to：*from (2)+to (3)null (4)listptr 一value (5)return(null)解析：11.设模式 T=“abcabaabc”，求它的 next函数的修正值 nextval，下面的函数用于求模式 T的 nextval之值。其中，T0用于保存模式 T的字符个数，而 T1，T2，T
24、M依次保存模式 T的各个字符。请在该函数中的A、B处各填入一个赋值表达式，使得数组 nextval能够给出模式 T的 next函数的修正值 nextval。 void getnextval(sstring T，intnextval) i=I，nextval1=0；j=0； while(i_正确答案：(正确答案：Anextvali=nextvaljBj=nextvalj)解析：12.以下程序的功能是把一个输入字符串倒序输出，请找出并改正其中的错误。 void reverse(char*s) int len=strlen(S)； char*dest=new char1en； int i=0 ; w
25、hile(1en-一!=0) printf()； return 0； 【北京大学 2008三(10 分)】（分数：2.00）_正确答案：(正确答案：(1)第一个循环体处应是赋值语句：*(dest+i+)=*(s+len)； (2)printf 的处应该输出倒序的字符串：“s”，dest (3)函数类型是 void，不应有返回值，要删除 return 0；)解析：二、综合题(总题数：14，分数：34.00)13.串。【大连海事大学 1996一、10(1 分)】【河海大学 1998二、5(3 分)】（分数：2.00）_正确答案：(正确答案：串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于
26、线性结构。与线性表相比，其特殊性在于串的元素是字符，串的操作经常以整体(字符串)出现。)解析：14.描述以下概念的区别：空格串与空串。【大连海事大学 1996三、2(1)(2 分)】（分数：2.00）_正确答案：(正确答案：空格是一个字符，其 ASCII码值是 32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零，其 ASCII码值是 0。)解析：15.两个字符串 S1和 S2的长度分别为 m和 n。求这两个字符串最大共同子串算法的时间复杂度为 T(m，n)。估算最优的 r(m，n)，并简要说明理由。【北京工业大学 1996_、5(6 分)】（分数：2.
27、00）_正确答案：(正确答案：最优的 T(m，n)是 O(n)。S2 是串 S1的子串，且在 S1中的位置是 1。开始求出最大公共子串的长度恰是串 S2的长度。一般情况下，T(m，n)=O(m*n)。)解析：16.KMP算法(字符串匹配算法)较 Brute算法(朴素的字符串匹配算法)有哪些改进? 【大连海事大学 1996三、l(2 分)】（分数：2.00）_正确答案：(正确答案：朴素的模式匹配(BruteForce)时间复杂度是 O(m*n)，KMP 算法有一定改进，时间复杂度达到 O(m+n)。主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP 算法的优点更为突
28、出。)解析：17.给出字符串abacabaaad在 KMP算法中的 next和 nextval数组。【北京邮电大学 2000三、1(5 分)】（分数：2.00）_正确答案：(正确答案：模式串的 next函数定义如下： 当此集合不空时根据此定义，可求解模式串“abacabaaad“的 next和 nextval值如下： )解析：设字符串 S=“aabaabaabaac，P=aabaac。（分数：4.00）(1).给出 S和 P的 next值和 nextval值；（分数：2.00）_正确答案：(正确答案：S 的 next与 nextval值分别为 012123456789和 00200200200
29、9。 P 的 next与nextval值分别为 012123和 002003。)解析：(2).若 S作主串，P 作模式串，试给出利用 BF算法和 KMP算法的匹配过程。【北方交通大学 1998二(15分)】（分数：2.00）_正确答案：(正确答案：利用 BF算法的匹配过程： 利用 KMP算法的匹配过程： 第一趟匹配：aabaabaabaac 第一趟匹配：aabaabaabaac aabaac(i=6，j=6) aabaac(i=6，j=6) 第二趟匹配：aabaabaabaac 第二趟匹配：aabaabaac aa(i=3，j=2)(aa)baac 第三趟匹配：aabaabaabaac 第三趟
30、匹配：aabaabaabaac a(i=3，j=1) (成功) (aa)baac 第四趟匹配：aabaabaabaac aabaac(i=9，j=6) 第五趟匹配：aabaabaabaac aa(i=6，j=2) 第六趟匹配：aabaabaabaac a(i=6，j=1) 第七趟匹配：aabaabaabaac (成功) aabaac(i=13，j=7)解析：设目标为 t=“abcaabbabcabaacbacba“，模式为 p=“abcabaa“。（分数：4.00）(1).计算模式 p的 nextval函数值； (5 分)（分数：2.00）_正确答案：(正确答案：P 的 nextval函数值为
31、 01 10132(p的 next函数值为 01 11232)。)解析：(2).不写出算法，只画出利用 KMP算法进行模式匹配时每一趟的匹配过程。 (5 分)【清华大学 1998八(10分)】（分数：2.00）_正确答案：(正确答案：利用 KMP(改进的 nextval)算法，每趟匹配过程如下： 第一趟匹配：abcaabbabcabaacbacba abcab(i=5，j=5) 第二趟匹配：abcaabbabcabaacbacba abc(i=7，j=3) 第三趟匹配：abcaabbabcabaacbacba a(i=7，j=1) 第四趟匹配：abcaabbabcabaacbacba (成功)
32、 abcabaa(i=15，j=8)解析：18.模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为 m，模式的长度为 n，则在主串中寻找模式的 KMP算法的时间复杂性是多少?如果某一模式P=-“abcaacabaca“，请给出它的NEXT。函数值及 NEXT函数的修正值 NEXTVAL之值。【上海交通大学 2000一(5 分)】（分数：2.00）_正确答案：(正确答案：KMP 算法的时间复杂度是 O(m+n)。P 的 NEXT和 NEXTVAL值分别为 011 12212321和 01 102201320。)解析：设目标为 S=“abcaabbcaaabababaabca，
33、模式为 P=“babab“。（分数：4.00）(1).手工计算模式 P的 nextval数组的值；(5 分)（分数：2.00）_正确答案：(正确答案：p 的 nextval函数值为 01010(next函数值为 01123)。)解析：(2).写出利用求得的 nextval数组，按 KMP算法对目标 S进行模式匹配的过程。(5 分)【清华大学 1997四(10 分)】（分数：2.00）_正确答案：(正确答案：手工模拟对 s的匹配过程，与上面第 6题类似，为节省篇幅，故略去。)解析：19.设模式串 t为“abcabcacabca“，给出其失败函数。 【吉林大学 2007二、6(3 分)】（分数：2.00）_
