1、计算机专业基础综合数据结构（串）历年真题试卷汇编 3 及答案与解析一、综合题1 如果两个串含有相等的字符，能否说它们相等?【西安电子科技大学 2000 一、3(5 分)】2 设 S1、S2 为串，请给出使 S1$2=S2S1 成立的所有可能的条件(为连接符)。【国防科技大学 1999 一】【长沙铁道学院 1997 三、5(3 分)】3 已知：s=(xyz)+*，t=(x+z)*。试利用联结、求子串和置换等基本运算，将 s 转化为 t。【北方交通大学 1996 一、3(5 分)】【山东科技大学 2002 一、6(5 分)】4 s 是字符数组，s0中存放的是该字符串的有效长度，假设 s17中字符串
2、的内容为“abcabaa“，说明下列程序的功能及执行结果。#define len 8int k nlen，char slen=“7abcabaa”；void unknown3(char T)int i， j；i=1； n1=0； j=0；while(in1)，返回子串在主串的位置 (i-j)。 否则，当 im 一 n 则为匹配失败。核心语句段如下： while(i6 【正确答案】 核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去
3、，直至整个字符串扫描到结束。核心语句段如下：while(ch!=#) #是字符串结束标记，字符 ch 已输入if(isdigit(ch) 是数字字符num=0； 数初始化while(isdigit(oh)if(ch!=-) 规定-是字符串输入结束标志InvertStore(A)；Ai+=ch； 字符串逆序存储Ai=0； 字符串结尾标记结束算法 InvertStore15 【正确答案】 串 s可以看作由以下两部分组成： caabcbcaa和caa ，设这两部分分别叫串 s1 和串 s2，要设法从 s、s和 s中得到这两部分，然后使用联结操作联结 s1 和 s2 得到 s。i=index(s，s)
4、 ； 利用串 S?求串 s1 在串 s 中的起始位置s1=substr(s，i，length(S)一 i+1)； 8 出串 s1j=index(s，s)； 求串 s在串 s 中的起始位置，s 串中bcb后是caas2=substr(s，j+3，length(S)一 j 一 2)； 形成串 s2s3=concat(s1，s2)；16 【正确答案】 对读入的字符串的第奇数个字符，直接放在数组前面，对第偶数个字符，先入栈，到读字符串结束，再将栈中字符出栈，送入数组中。while(ch=getchar()!=#) 读入字符串，#是字符串结束标志Si+=ch；lli 初值为 1Si=-0 ； 字符数组中
5、字符串结束标志i=1;j=1;while(Si) 改造字符串if(i2=0)stki2=8i；else Sj+=si;i+; whilei 一一；i=i2 ;i=i 先从 0后退，然后其含义是第偶数个字符的个数while(i0)sj+=stki 一一 将第偶数个字符逆序填入原字符数组17 【正确答案】 两串相等指长度相等且对应位置的字符相同。if(x1ength!=y1ength)return(0)； 判断两个串 x 和 y 是否相等p=x str； q=ystr；while(p else return(0)；18 【正确答案】 利用栈存放字符串的前半部分，将后半部分与栈中弹出元素比较。核心语句段如下：char S； 字符栈，容量足够大p=head 一next 设链表带头结点int i=0；while(ic=n2) 前一半字符入栈，链表指针后移(Si=p 一data；p=p 一 next； i+ ；)if(n2=1)p=p 一next； 若链表有奇数个结点，则跳过中间结点while(p)if(p 一data=si)(p=p 一next；i 一一；)else break； 不是回文if(!P 串长为偶数或奇数if(Sfront!=Srear)return 0;return huiwenchuan(S，front+1 ，rear-1);
