数据结构练习第四章串

1数据结构练习第四章串一、选择题1．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。A.“STRUCTURE”B.“DATA”C.“ASTRUCTUR”D.“DATASTRUCTURE”2．字符串的长度是指（）。A.串中不同字符的个数B.串中不同字母的个数C.串中所含字符的个数D.串中不同数字的个数3．两个字符串相等的充要条件是（）。A.两个字符串的长度相等B.两个字符串中对应位置上的字符相等C.同时具备(A)和(B)两个条件D.以上答案都不对4．关于串的叙述中，正确的是（）A．空串是只含有零个字符的串B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有一个或多个字符的有穷序列5．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储6．设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作()A．求子串B.判断是否相等C．模型匹配D.连接7．若串S=’software’,其子串的数目是()。A．8B．37C．36D．98．串的长度是指（）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数9．串是一种特殊的线性表，其特殊性体现在()。A．数据元素是一个字符B.可以顺序存储C.数据元素可以是多个字符D.可以链接存储10．下面关于串的的叙述中，哪一个是不正确的（B）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储11．若串＝‘software’，其非平凡子串（非空且不同于串本身）的数目是（C）A.8B.37C.35D.912．串是一种特殊的线性表，其特殊性体现在（B）A.可以顺序存储B.数组元素是一个字符C.可以连续存储D.数据元素可以是多个字符13.下面关于串的的叙述中，哪一个是不正确的？（B）2A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储二、填空题1．两个串是相等的，当且仅当两个串的长度相等且___对应位置_____的字符都相同。2．串是一种特殊的线性表，串常见的存储结构有顺序存储和_____链式存储_两种方式。3．空格串是指_______，其长度等于_______。(1)由空格字符（ASCII值32）所组成的字符串(2)空格个数4．一个字符串中________称为该串的子串。任意个连续的字符组成的子序列5．字符串’ababaaab’的nextval函数值为________。010104216．串是一种特殊的线性表，其特殊性表现在__(1)__；串的两种最基本的存储方式是__(2)__、__(3)__；两个串相等的充分必要条件是__(4)__。(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等7．下列程序读入无符号16进制数（出现的字母为小写），将其转换为十进制数输出。请将程序空缺部分补全。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));｝(1)(s[i]=97?s[i]-87:s[i]-48)∥‘a’到’f’的ASCII码是97到102(2)f(s)8．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。voidmaxcomstr(orderstring*s,*t,intindex,length){inti,j,k,length1,con;index=0;length=0;i=1;while(i=s.len){j=1;while(j=t.len){if(s[i]==t[j]){k=1;length1=1;con=1;while(con)if(1)_{length1=length1+1;k=k+1;}else(2)__;if(length1length){index=i;length=length1;}3(3)____;}else(4)___;}(5)__}}[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i指针（1=i=s.len）。t串用j指针（1=j=t.len）。算法思想是对每个i（1=i=s.len，即程序中第一个while循环），来求从i开始的连续字符串与从j（1=j=t.len，即程序中第二个while循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的while循环，是当s中某字符(s[i])与t中某字符(t[j])相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。(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）。9．试利用下列栈和串的基本操作完成下述填空题。initstack(s)置s为空栈；push(s,x)元素x入栈;pop(s)出栈操作;gettop(s)返回栈顶元素；sempty(s)判栈空函数；setnull(st)置串st为空串；length(st)返回串st的长度；equal(s1,s2)判串s1和s2是否相等的函数；concat(s1,s2)返回联接s1和s2之后的串；sub(s,i,1)返回s中第i个字符；empty(st)判串空函数FUNCinvert(pre:string;VARexp:string):boolean;{若给定的表达式的前缀式pre正确，本过程求得和它相应的表达式exp并返回“true”，否则exp为空串，并返回“false”。已知原表达式中不包含括弧，opset为运算符的集合。}VARs:stack;i,n:integer;succ:boolean;ch:char;BEGINi:=1;n:=length(pre);succ:=true;(1)__;(2)__;WHILE(in)ANDsuccDOBEGINch:=sub（pre,i,l）;IF(3)_THEN(4)__ELSEIF(5)__THEN(6)_ELSEBEGIN4exp:=concat((7)___,(8)____);exp:=concat((9)___,(10)___);(11)__;END;i:=i+1END;IF(12)___THENBEGINexp:=concat(exp,sub(pre,n,1));invert:=trueENDELSEBEGINsetnull(exp);invert:=falseENDEND;注意：每个空格只填一个语句。（1）initstack（s）∥栈s初始化为空栈(2)setnull(exp)∥串exp初始化为空串(3)chinopset∥判取出字符是否是操作符(4)push(s,ch)∥如ch是运算符，则入运算符栈s(5)sempty(s)∥判栈s是否为空(6)succ:=false∥若读出ch是操作数且栈为空，则按出错处理(7)exp(8)ch∥若ch是操作数且栈非空，则形成部分中缀表达式(9)exp(10)gettop(s)∥取栈顶操作符(11)pop(s)∥操作符取出后，退栈(12)sempty(s)∥将pre的最后一个字符（操作数）加入到中缀式exp的最后三、判断题1．()子串“ABC”在主串“AABCABCD”中的位置为2。T2．（）KMP算法的特点是在模式匹配时指示主串的指针不会变小。√3．（）设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。√4．（）串是一种数据对象和操作都特殊的线性表。√5．（）串长度是指串中不同字符的个数。×6．()如果两个串含有相同的字符，则这两个串相等。X7．（）KMP算法的最大特点是指示主串的指针不回溯。√四、简答题1．KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进?朴素的模式匹配（Brute－Force）时间复杂度是Ｏ(m＊n），KMP算法有一定改进，时间复杂度达到Ｏ(m＋n）。主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。2．给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。模式串的next函数定义如下：5根据此定义，可求解模式串’abacabaaad’的next和nextval值如下：3．模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m，模式的长度为n，则在主串中寻找模式的KMP算法的时间复杂性是多少？如果，某一模式P=’abcaacabaca’，请给出它的NEXT函数值及NEXT函数的修正值NEXTVAL之值。KMP算法的时间复杂性是O（m+n）。p的next和nextval值分别为01112212321和01102201320。4．设目标为S=‘abcaabbcaaabababaabca’，模式为P=‘babab’。（1）手工计算模式P的nextval数组的值；（2）写出利用求得的nextval数组，按KMP算法对目标S进行模式匹配的过程。（1）p的nextval函数值为01010。（next函数值为01123）（2）利用所得nextval数值，手工模拟对s的匹配过程。5．s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串的内容为“abcabaa”，说明下列程序的功能及执行结果。#definelen8intk,n[len]；chars[len]=“7abcabaa”；voidunknown3(charT[]）{inti,j;i=1;n[1]=0;j=0;while(ilen){if(j==0||T[i]==T[j]){++i;++j;if(T[i]!=T[j])n[i]=j;elsen[i]=n[j];}elsej=n[j];}}main()j12345678910t串abacabaaadnext[j]0112123422nextval[j]01020104226{unknown3(s);for(k=1;klen;k++)printf(“%d”,n[k];)本程序的功能是求字符串的nextval函数，程序执行结果是0110132。6．给出KMP算法中失败函数f的定义，并说明利用f进行串模式匹配的规则，该算法的技术特点是什么？这里失败函数f，即是通常讲的模式串的next函数，其定义见本章应用题的第5题。进行模式匹配时，若主串第i个字符与模式串第j个字符发生失配，主串指针i不回溯，和主串第i个字符进行比较的是模式串的第next[j]个字符。模式串的next函数值，只依赖于模式串，和主串无关，可以预先求出。该算法的技术特点是主串指针i不回溯。在经常发生“部分匹配”和主串很大不能一次调入内存时，优点特别突出。7．已知：s='(xyz)+＊'，t='(x+z)*y'。试利用联结、求子串和置换等基本运算，将s转化为t。【北方交通大学1996一.3（5分）】题中所给操作的含义如下：∥：连接函数，将两个串连接成一个串substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连续j个字符本题有多种解法，下面是其中的一种：（1）s1=substr(s,3,1）∥取出字符：‘y’（2）s2=sub