[考研类试卷]计算机专业基础综合数据结构（串）历年真题试卷汇编2及答案与解析.doc

1、计算机专业基础综合数据结构（串）历年真题试卷汇编 2 及答案与解析一、填空题1 设 T 和 P 是两个给定的串，在 T 中寻找等于 P 的子串的过程称为(1)，又称 P 为(2)。【西安电子科技大学 1998 二、5(166 分) 】2 串是一种特殊的线性表，其特殊性表现在(1) ；串的两种最基本的存储方式是(2)、(3)；两个串相等的充分必要条件是(4) 。【中国矿业大学 2000 一、3(4 分)】3 使用“求子串 ”subString(S，pos，len)和“ 联结”concat(S1，s2) 的串操作，可从串s=conduction中的字符得到串 t=”cont”，则求 t 的串表达式

2、为_。【北京工业大学 2005 二、4(3 分)】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 分)】5 已知 U=xyxyxyxxyxy；t=xxy ；ASSIGN(S ，U)；ASSIGN(V，SUBSTR(S ，INDEX(s，t)，LENCt)+1),ASSIGN(m，ww) 求REPLACE

3、(S，y，m)=_。【东北大学 1997 一、1(5 分)】6 实现字符串拷贝的函数 strcpy 为：void strcpy(char*s，char*t)*copy t to s*while(_) 【浙江大学 1999 一、5(3 分)】7 下列程序判断字符串 s 是否对称；对称则返回 1，否则返回 0；如 f“abba”)返回1，f“abab”)返回 0。int f(1) )int i=0，j=0 ；while(8j)(2) ；for(J 一一； ilength) ( index=i； length=length1； )(3) ;else(4)；(5) 【上海大学 2000 一、2(10

4、分)】9 下列是判断是否为回文(顺读与逆读字符串一样，串中不含空格)的算法。#include#include#include#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

5、(”Stack underflow”)；return (2) ；int IsHuiwen(char*S)SeqStack T； int i，n；char tl；TTop=一 1； n=strlen(s)； 求向量长度for(i=0；i=0)tl= (3) ； 每弹出一个字符与相应字符作比较if( (4) ) return 0； 不相等则返回 0i 一一；return 1；1 比较完毕均相等则返回 1void main()if(IsHuiwen(Str)printf(“n 这个字符串是回文。”)；else printf(“n 这个字符串不是回文。”)；【北京交通大学 2006 七、2(8 分)】

6、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 listrec*listptr； int match；while(listptr!=

7、(3) )1f( (4) =match)break；else (5);return(1istptr)；【中国海洋大学 2006 四(10 分)】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， ne

8、xtval1=0；j=0；while(i=977 si一 87：si-48) a到f的 ASCII 码是 97 到 102 (2)f(s)5 【正确答案】 xyxyxywwy6 【正确答案】 *s+=*t+或(*s+=*t+)!= 07 【正确答案】 (I)char s(或 char*s) (2)j+ (3)i=j8 【正确答案】 本题算法采用顺序存储结构求串 S 和串 t 的最大公共子串。串 s用 i 指针(1is.len)。串 t 用 j 指针(1jr.len) 。算法思想是对每个 i(1is.len，即程序中第一个 while 循环) ，来求从 i 开始的连续字符串与从 f(1jt.le

9、n，即程序中第二个 while 循环) 开始的连续字符串的最大匹配。程序中第三个(即最内层的)while循环，是当 S 中某字符(si)与 t 中某字符(tf)相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串(初始为 0)，则最长公共子串的长度要修改。(1) i+kdata+s 一Top=x (2)S 一data Is 一Top 一一 (3)Si (4)si!=Ti10 【正确答案】 (1)*to ： *from (2)+to (3)null (4)listptr 一value (5)return(null)11 【正确答案】 Anextvali=nextvaljBj=nextv

10、alj12 【正确答案】 (1)第一个循环体处应是赋值语句：*(dest+i+)=*(s+len)； (2)printf 的处应该输出倒序的字符串：“ s”，dest (3)函数类型是 void，不应有返回值，要删除 return 0；二、综合题13 【正确答案】 串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表相比，其特殊性在于串的元素是字符，串的操作经常以整体(字符串) 出现。14 【正确答案】 空格是一个字符，其 ASCII 码值是 32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零，其ASCII 码值是 0。15 【

11、正确答案】 最优的 T(m，n)是 O(n)。S2 是串 S1 的子串，且在 S1 中的位置是 1。开始求出最大公共子串的长度恰是串 S2 的长度。一般情况下，T(m，n)=O(m*n)。16 【正确答案】 朴素的模式匹配(BruteForce)时间复杂度是 O(m*n)，KMP 算法有一定改进，时间复杂度达到 O(m+n)。主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP 算法的优点更为突出。17 【正确答案】 模式串的 next 函数定义如下：当此集合不空时根据此定义，可求解模式串abacabaaad的 next 和 nextval 值如下：18 【正确答案

12、】 S 的 next 与 nextval 值分别为 012123456789 和 002002002009。P 的 next 与 nextval 值分别为 012123 和 002003。19 【正确答案】 利用 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=

13、1) ( 成功) (aa)baac第四趟匹配：aabaabaabaacaabaac(i=9，j=6)第五趟匹配：aabaabaabaacaa(i=6，j=2)第六趟匹配：aabaabaabaaca(i=6，j=1)第七趟匹配：aabaabaabaac(成功 ) aabaac(i=13，j=7)20 【正确答案】 P 的 nextval 函数值为 01 10132(p 的 next 函数值为 01 11232)。21 【正确答案】 利用 KMP(改进的 nextval)算法，每趟匹配过程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5， j=5)第二趟匹配：abcaa

14、bbabcabaacbacbaabc(i=7，j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7，j=1)第四趟匹配：abcaabbabcabaacbacba(成功 ) abcabaa(i=15， j=8)22 【正确答案】 KMP 算法的时间复杂度是 O(m+n)。P 的 NEXT 和 NEXTVAL 值分别为 011 12212321 和 01 102201320。23 【正确答案】 p 的 nextval 函数值为 01010(next 函数值为 01123)。24 【正确答案】 手工模拟对 s 的匹配过程，与上面第 6 题类似，为节省篇幅，故略去。25 【正确答案】

15、 模式串“abcabcacabca“的失败函数为：011 123451234。26 【正确答案】 简单模式匹配算法，查找成功需要比较 15 趟 39 次。若用 KMP算法，查找成功需要比较，7 趟 27 次。NEXT 和 NEXTVAL数组值分别是011112312 和 011101302。27 【正确答案】 (1)当模式串中第一个字符与主串中某字符比较不等(失配)时，next1=0 表示模式串中已没有字符可与主串中当前字符 st比较，主串当前指针应后移至下一字符，再和模式串中第一个字符进行比较。 (2)当主串第 i 个字符与模式串中第 j 个字符失配时，若主串 f 不回溯，则假定模式串第 k

16、 个字符与主串第 i个字符比较，k 值应满足条件 1kj 并且。 p1pk-1=pi-k+1pi-1，即 k 为模式串向后移动的距离，k 值可能有多个，为了不使向右移动丢失可能的匹配，k 要取大，由于 maxk表示移动的最大距离，所以取 maxk，k 的最大值为广 1。 (3)在上面两种情况外发生失配时，主串指针 i 不回溯，在最坏情况下，模式串从第 1 个字符开始与主串第 i 个字符比较，以便不丢失可能的匹配。28 【正确答案】 这里失败函数 f，即是通常讲的模式串的 next 函数，其定义见本章应用题的第 5 题。进行模式匹配时，若主串第 i 个字符与模式串第 j 个字符发生失配，主串指针

17、 i 不回溯，和主串第 i 个字符进行比较的是模式串的第 nextj个字符。模式串的 next 函数值只依赖于模式串，和主串无关，可以预先求出。该算法的技术特点是主串指针 i 不回溯。在经常发生“部分匹配”和主串很大不能一次调入内存时，优点特别突出。29 【正确答案】 失败函数(即 next)的值只取决于模式串自身，若第 j 个字符与主串第 i 个字符失配时，假定主串不回溯，模式串用第 k(即 nextj)个字符与第 i 个相比，有 i 个相比，有p 1pk-1=p1pj-1，为了不因模式串右移与主串第 i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个 k 值，应取其中最大的一个。这样，因 j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能的匹配的丢失。