计算机技术与软件专业技术资格考试(程序员考试)
问答题阅读以下说明和流程图，将应填入____处的字句写在答题纸的对应栏内。下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。设这篇文章由字符A（0），…，A（n-1）依次组成，指定关键词由字符B（0），…，B（m-1）依次组成，其中n>m≥1。注意，关键词的各次出现不允许有交叉重叠。例如，在"aaaa"中只出现两次"aa"。该流程图采用的算法是：在字符串A中，从左到右寻找与字符串B相匹配的并且没有交叉重叠的所有子串。流程图8-17中，i为字符串A中当前正在进行比较的动态子串首字符的下标，j为字符串B
题目
相似问题和答案
第1题：
●试题四
阅读下列程序说明和C程序，将应填入(n)处的字句写在答卷纸的对应栏内。
【程序说明】
该程序定义了两个子函数strsort和strmerge。它们分别实现了将一个字符串按字母顺序排序和将两个字符串合并排序，并删去相同字符。在主函数里，先输入两个字符串s1和s2，然后调用strsort函数对它们分别排序，然后调用strmerge函数将s1和s2合并，将合并后的字符串赋给字符串s3，最后输出字符串s3。
【程序】
#include<stdio.h>
void strmerge(char*a，char*b，char*c)//将字符串a，b合并到字符串c中
{
char t,*w；
w=c；
while( (1) )
{
//找到字符串a，b当前字符中较小的字符
if(*a<*b)
{
t=*a；
(2) ；
}
else if(*a>*b)
{
t=*b;
(3) ；
}
else//字符串a，b当前字符相等
{
t=*a；
a++;
b++;
}
if( (4) )//开始，可直接赋值
*w=t;
else if(t!=*w)
//如果a，b中较小的当前字符与c中当前字符不相等，才赋值 (5) ；
}
if(*a!=\′＼0′)//如果字符串a还没有结束，则将a的剩余部分赋给c
while(*a!=′＼0′)
if(*a!=*w)
{
*(++w)=*a；
a++;
}
else
(6) ；
if(*6!=′＼0′)//如果字符串b还没有结束，则将b的剩余部分赋给c
while(*b!=′＼0′)
if(*b!=*w)
{
*(++w)=*b；
b++;
}
else
b++;
(7) ；
}
void strsort(char*s)//将字符串S中的字符排序
{
int i，j，n；
char t，*w;
W=S;
for(n=0；*w!=′＼0′；n++)//得到字符串长度n
w++;
for(i=0；i<n-1；i++)//对字符串s进行排序，按字母先后顺序
for(j=i+1；j<n；j++)
if( (8) )
{
t=s[i]；s[i]=s[j]； (9) ；
}
}
void main()
{
char s1[100]，s2[100]，s3[100]；printf("＼nPlease，input the first string：")；
scanf("％s"，s1)；
printf("＼nPlease input the second string：")；
scanf("%s"，s2)；
strsort(s1)；//将字符串s1排序
strsort(s2)；//将字符串s2排序
printf("％s＼n"，s1)；
printf("％s＼n"，s2)；
s3[0]=′＼0′；//字符串s3的第一个字符先置′＼0′结束标志
(10) //将s1和s2合并，按照字母顺序排列，
//且要删去相同字符，存入s3中
printf("%s"，s3)；
}
●试题四
【答案】(1)(*a!=′＼0′)＆&(*b!=′＼0′)(2)a++
(3)b++(4)*w==′＼0′(5)*(++w)=t(6)a++
(7)*(++w)=′＼0′(8)s[i]>s[j] (9)s[j]=t(10)strmerge(s1，s2，s3)
【解析】根据题意，对字符串的处理分为三步：第一步是从键盘上输入两个字符串；第二步是将两个字符串分别排序；第三步是将字符串合并；第四步是显示处理结果。
第一步和第四步容易实现，关键是第二步和第三步的处理，下面分别加以说明。
字符串排序是指将一个字符串中各个字符按照ASCⅡ码值的大小排序。例如，字符串"Beijing"由小到大的排序结果应该是："Bejiign"。排序算法很多，第二个例子，我们就要介绍快速排序算法。在这里使用简单的冒泡排序算法：即将字符串中的每一个字符一个个进行比较，找出最小的字符，然后再在剩下的字符中找最小的字符。例如，字符"Beijing"的排序过程如下：
第一次将字符"Beijing"中的每一个字符：′B′、′e′、′i′、′j′、′i′、′n′、′g′进行比较，找到最小的字符′B′。
第二次在剩下的字符′e′、′i′、′j′、′i′、′n′、′g′中，找到最小的字符′e′。
……
第三次在剩下的字符′j′、′i′、′n′、′g′中，找到最小的字符′j′。
第三步是合并字符串，合并后的字符串仍然由小到大排序。由于待合并的两个字符串已经排好序。假定两个排好序的字符串分别为A和B，合并后的字符串为C，要使待合并后的字符串仍然由小到大排序，可采取下述步骤：
1.从前往后取A中的字符，并按从前往后的顺序与B中的字符比较，若A中的字符较小，则将该字符存入C，并移到A的下一个字符，继续与B中的字符比较。
2.若A中的字符较大，则将B中的字符存入C，并移到B的下一个字符，继续与A中的字符比较。
3.若A与B中的字符相等，则将A或B中的字符存入C，并将A和B均移到下一个字符。
4.若A或B字符串到达末尾，则将B或A的剩余部分加到字符串C中。
需要注意的是：A、B和C三个字符串均可以用字符数组来表示，C数组的长度不能小于A、B两数组的长度之和。另外，判别字符串是否结尾的方法是：从A或B中取出的字符是否为′＼0′，所有字符串都是以′＼0′结尾的。
第2题：
函数String(n，字符串)的功能是( )。
A．把数值型数据转换为字符串
B．返回由n个字符组成的字符串
C．从字符串中取出n个字符
D．从字符串中第n个字符的位置开始取子字符串
第3题：
试题四（共 15分）
阅读以下说明和C函数，将解答填入答题纸的对应栏内。
【说明】
函数del_substr(S,T)的功能是从头至尾扫描字符串 S， 删除其中与字符串T相同的所有子串，其处理过程为：首先从串 S 的第一个字符开始查找子串 T，若找到，则将后面的字符向前移动将子串T覆盖掉，然后继续查找子串T，否则从串S的第二个字符开始查找，依此类推，重复该过程，直到串S的结尾为止。该函数中字符串的存储类型 SString
定义如下：
typedef struct {
char *ch; /*串空间的首地址*/
int length; /*串长*/
}SString;
【C函数】
void del_substr(SString *S, SString T)
{
int i, j;
if ( S->length < 1 || T.length < 1 || S->length < T.length )
return;
i = 0; /* i为串S中字符的下标 */
for ( ; ; ) {
j = 0; /* j为串T中字符的下标 */
while ( i < S->length && j < T.length ) { /* 在串S中查找与T相同的子串 */
if ( S->ch[i]==T.ch[j] ) {
i++; j++;
}
else {
i = （1） ; j = 0; /* i值回退，为继续查找T做准备 */
}
}
if ( （2） ) { /* 在S中找到与T相同的子串 */
i = （3） ; /* 计算S中子串T的起始下标 */
for(k = i+T.length; k<S->length; k++) /* 通过覆盖子串T进行删除 */
S->ch[ （4） ] = S->ch[k];
S->length = （5） ; /* 更新S的长度 */
}
else break; /* 串S中不存在子串T*/
}
}
试题四参考答案
（1）i-j+1，或其等价形式 （3分）
若考生解答为i-j，则给1分
（2）j==T.length，或j>=T.length，或其等价形式 （3分）
（3）i-j （3分）
（4）k -T.length，或k-j，或其等价形式 （3分）
（5）S->length-T.length，或S->length-j （3分）
第4题：
阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入对应栏内。
【说明】
下面流程图的功能是：在已知字符串A中查找特定字符串B，如果存在，则输出B串首字符在A串中的位置，否则输出-1。设串A由n个字符A(0)，A(1)，…，A(n-1)组成，串B由m个字符B(0)，B(1)，…，B(m-1)组成，其中n≥m＞0。在串A中查找串 B的基本算法如下：从串A的首字符A(0)开始，取子串A(0)A(1)…A(m-1)与串B比较；若不同，则再取子串A(1)A(2)…A(m)与串B比较，依次类推。
例如，字符串“CABBRFFD”中存在字符子串“BRF”(输出3)，不存在字符子串“RFD”(输出-1)。
在流程图中，i用于访问串A中的字符(i=0，1，…，n-1)，j用于访问串B中的字符(j=0，1，…，m-1)。在比较A(i)A(i/1)…A(i+m-1)与B(0)B(1)…B(m-1)时，需要对 A(i)与B(0)、A(i+1)与B(1)、…、A(i+j)与B(j)等逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，依此类推。
【流程图】
(1) j+1 (2) i+1 (3) 0 (4) i (5) -1 解析：本题采用的是最简单的字符子串查找算法。
在串A中查找是否含有串B，通常是在串A中从左到右取逐个子串与串B进行比较。在比较子串时，需要从左到右逐个字符进行比较。
题中已设串A的长度为n，存储数组为A，动态指针标记为i；串B的长度为m，存储数组为B，动态指针标记为j。
如果用伪代码来描述这种算法的核心思想，则可以用以下的两重循环来说明。
外循环为：
Fori=0ton-mdo
A(i)A(i+1)...A(i+m-1)～B(0)B(1)...B(m-1)
要实现上述比较，可以采用内循环：
Forj=0tom-1do
A(i+j)～B(j)
将这两重循环合并在一起就是：
Fori = 0ton-1do
Forj = 0tom-1do
A(i+j)～B(j)
这两重循环都有一个特点：若发现比较的结果不相同时，就立即退出循环。因此，本题中的流程图可以间接使用循环概念。
初始时，i与j都赋值0，做比较A(i+j)～B(j)。
若发现相等，则继续内循环(走图的左侧)，j应该增1，继续比较，直到j=m为止，表示找到了子串(应输出子串的起始位置i)；若发现不等，则退出内循环，继续开始外循环(走图的右侧)，j应恢复为0，i应增1，继续比较，直到i＞n-m为止，表示不存在这样的子串(输出-1)。
在设计流程图时，主要的难点是确定循环的边界(何时开始，何时结束)。当难以确定边界值变量的正确性时，可以用具体的数值之例来验证。这是程序员应具备的基本素质。
第5题：
阅读以下技术说明和流程图，根据要求回答问题1至问题3。
[说明]
图4-8的流程图所描述的算法功能是将给定的原字符串中的所有前部空白和尾部空白都删除，但保留非空字符。例如，原字符串“ FileName ”，处理变成“File Name”。图4-9、图4-10和图4-11分别详细描述了图4-8流程图中的处理框A、B、C。
假设原字符串中的各个字符依次存放在字符数组ch的各元素ch(1)、ch(2)、…、ch(n)中，字符常量 KB表示空白字符。
图4-8所示的流程图的处理过程是：先从头开始找出该字符串中的第一个非空白字符ch(i)，再从串尾开始向前找出位于最末位的非空白字符ch(j)，然后将ch(i)、……、ch(j)依次送入ch(1)、ch(2)、……中。如果字符串中没有字符或全是空白字符，则输出相应的说明。
在图4-8流程图中，strlen()是取字符串长度函数。
请将图4-9、图4-10和图4-11流程图中(1)～(4)空缺处的内容填写完整。
本题用分层的流程图形式描述给定的算法。图4-8所描述的流程图是顶层图，其中用A、B、C标注了 3个处理框。而图4-9、图4-10和图4—11所描述的流程图分别对这3个处理框进行了细化。 处理框A的功能是依次检查ch(1)，ch(2)，……(即从串首开始查找)，直到找到非空白字符ch(i)。在图4-9所描述的流程图中，对i=1，2……进行循环，只要未找到字符串尾部标志(即"\0")，且ch(i)为空白字符(KB)，那么还需要继续查找。因此，(1)空缺处所填写的内容是“i=n”或“n＞=i”或其他等价形式。 处理框B的功能是依次检查ch(n)，ch(n-1)，……(即从串尾向前开始查找)，直到找到非空字符ch(j)。在图4-10所描述的流程图中，对j=n，n-1……进行循环，只要ch(j)=KB(空白字符)，那么还需要继续循环查找。由于B框处理的前提是A框中已经找到了非空字符ch(i)，因此循环最多到达“j=i”处就会结束。可见，(2)空缺处所填写的判断条件是“ch(j)=KB”。而图4-10中的判断条件“j＞i”是可有可无的。 处理框C的功能是将ch(i)，ch(i+1)…，ch(j)的内容依次送入ch(1)，ch(2)……中。在图4-11所描述的流程图中，对kf=i，i+l，…，j进行循环，只要满足“k=j”的条件，就要继续循并环做传送处理，因此(3)空缺处所填写的内容是“k=i”或其等价形式。 由于ch(i)应送往ch(1)，ch(i+1)应送往ch(2)……，因此，ch(k)应送往ch(k-i+1)。这是程序员应熟练掌握的基本功，即从几个特例，寻找普遍规律，再用特例代进去试验是否正确。因此，(4)空缺处所填写的内容是“ch(k-i+1)”。
第6题：
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。
【函数2.1说明】
函数palindrome(char s[])的功能是，判断字符串s是否为回文字符串，若是，则返回0，否则返回-1。若一个字符串顺读和倒读都一样时，称该字符串是回文字符串，例如：“LEVEL”是回文字符串，而“LEVAL”不是。
【函数2.1】
int palindrome( char s[ ] )
{ char * pi, * pj;
pi=s; pj=s+strlen(s)-1;
while( pi＜pj&&(1)){
pi ++ ;pj --
}
if((2))return -1;
else return 0;
}
【函数2.2说明】
函数f(char * str，char del)的功能是：将非空字符串str分割成若干个子字符串并输出，del表示分割时的标志字符。
例如若str的值为“33123333435”，del的值为“3”，调用此函数后，将输出3个子字符串，分别为“12”、“4”和“5”。
【函数2.2】
void f( char * str, char del)
{ int i ,j ,len;
len = strlen (str)
i=0;
while(i ＜ len) {
while((3))i++; /*忽略连续的标志字符*/
/*寻找从str[i]开始直到标志字符出现的一个子字符串*/
j=i+1;
while(str[j] != del && str[j] ! = '\0')j ++
(4): '\0'; /*给找到的字符序列置字符串结束标志*/
printf("%s\t",&str[i]);
(5);
}
}
(1)*pi==*pj (2)pipj或者等价表达式 (3)str[i]==del (4)str[j] (5)i=j+1 解析：(1)指针pi从左往右移动，指针pj从右往左移动，每移动一次，判断二者指向的元素是否相等，所以此处应填入判断语句*pi= =*pj。(2)pi如果能移动到pj右面，说明字符串是回文字符串，否则返回-1，所以此处应填入pipj或者其他等价表达式。(3)此处表达式判断当前字符是否等于标志字符del，即填入str[i]==del。(4)此处表达式为符合要求的字符串置结束标志，此时j已指向最后，所以应填入str[j]即可。(5)此处语句是修改i指针进行下一次循环，所以应填入i=j+1。
第7题：
/*写一个函数，用来返回一个字符串中重复出现的最长字串的长度及其开始地址const char*p=NULL;int len=maxsubstr("qweohiuweyowohifpw",&p);输出:len=3,substr=ohi*/#include<stdio.h>#include<string.h>int maxsubstr(const char *str,const char **p){ int len=0,templen=0;//len为字符串中重复出现的最长字串的长度，templen为判断过程中字符串中重复出现的字串的长度 int size=strlen(str); const char*i=str,*j=0; //i=str即i=str[0],i指向字符串的第一个字符 for(i=str;i<str+size;i++){ //i依次指向字符串内的各个字符 const char *temp_i=i; //temp_i指向当前i所指字符 for(j=i+1;j<str+size;++j){ //j指向当前i所指字符的下一个字符，temp_i、j依次在总字符串中取两个字符串，temp_i在前，即在temp_i后寻找 与从temp_i开始的字符串重复长度最长的字符串 if(*temp_i==*j&&templen==0){ //此处前两个if可以合并，如果所指字符相同，temp_i往后指一个字符，j在第二个循环中会自动往后指（++j） ++templen; ++temp_i; } else if(*temp_i==*j&&templen!=0){ ++templen; ++temp_i; } else{ //当前所指字符不相等,temp_i需要指回i所指位置，j指回此次循环开始位置（由于for循环有++j,实际下次循环开始时往后指了一个） if(templen>len){ //判断重复出现的最长字串的长度是否改变 len=templen; templen=0; *p=i; }else{ templen=0; //就算重复出现的最长字串的长度不改变，当前长度也得清零。。。 } } } } return len;}int main(){ char str[10000]; const char*p=0; int len=0; int i=0; printf("输入带重复字符的字符串"); scanf("%s",str); len=maxsubstr(str,&p); printf("len=%d,substr=",len); for(i=0;i<len;i++){ printf("%c",*p++); } printf("\n");}
第8题：
●试题二
阅读下列函数说明和C函数，将应填入(n)处的字句写在答题纸的对应栏内。
【函数2．1说明】
函数palindrome(char s［］)的功能是，判断字符串s是否为回文字符串，若是，则返回0，否则返回-1。若一个字符串顺读和倒读都一样时，称该字符串是回文字符串，例如："LEVEL"是回文字符串，而"LEVAL"不是。
【函数2．1】
int palindrome(char s［］)
{char*pi，*pj；
pi=s；pj=s+strlen(s)-1；
while(pi＜pj && (1) ){
pi++；pj--；
}
if( (2) )return -1；
else return 0；
}
【函数2．2说明】
函数f(char*str，char del)的功能是：将非空字符串str分割成若干个子字符串并输出，del表示分割时的标志字符。
例如若str的值为"33123333435"，del的值为"3"，调用此函数后，将输出3个子字符串，分别为"12"、"4"和"5"。
【函数2．2】
void f(char*str，char del)
{int i ，j ，len；
len=strlen(str)；
i=0；
while(i＜len){
while( (3) )i++；/*忽略连续的标志字符*/
/*寻找从str［i］开始直到标志字符出现的一个子字符串*/
j=i+1；
while(str［j］!=del && str［j］!=′＼0′)j++；
(4) =′＼0′；/*给找到的字符序列置字符串结束标志*/
printf(″%s＼t″，&str［i］)；
(5) ；
}
}
●试题二
【答案】(1)*pi==*pj(2)pi<pj或者等价表达式(3)str［i］==del(4)str［j］(5)i=j+1
【解析】(1)指针pi从左往右移动，指针pj从右往左移动，每移动一次，判断二者指向的元素是否相等，所以此处应填入判断语句*pi==*pj。(2)pi如果能移动到pj右面，说明字符串是回文字符串，否则返回-1，所以此处应填入pi<pj或者其他等价表达式。(3)此处表达式判断当前字符是否等于标志字符del，即填入 str［i］==del。(4)此处表达式为符合要求的字符串置结束标志，此时j已指向最后，所以应填入str［j］即可。(5)此处语句是修改i指针进行下一次循环，所以应填入i=j+1。
第9题：
函数f_str(char *str,char del)的功能是；将非申字符串str分割成若干个子字符串并输出，del表示分割时的标志字符。例如，若str的值为“66981636666257”，del的值为“6”，调用此函数后，将输出3个子字符串，分别为“981”、“3”和“257”。请将函数f_str中(6)～(8)空缺处的内容填写完整。
[函数]
void f_str(char *str，char del)
{ int i,j,len;
len = strlen(str);
i = 0;
while (i＜len) {
while ( (6) )
i++; /* 忽略连续的标志字符 */
/* 寻找从srt[i]开始直到标志字符出现的一个子字符串 */
j = i+1;
while (str[j] !=del && str[j] !='\0')
j++;
(7)="\0"; /* 给找到的字符序列置字符串结束标志 */
printf (" %s\t", & str [i]);
(8);
}
}
函数f_str(char*str，char del)的功能是：将非空字符串str以分割标志字符为界线，分割成若干个子字符串并输出。由函数说明和C代码可知，该函数对给定的字符串进行从左至右的扫描，找出不包含标志字符(变量del的值)的子字符串。在该函数C代码中，变量i的初值为0，len表示字符串的长度。当 ilen时进入循环体。如果当前字符(即str[i]的值)是标志字符，则不做处理，继续扫描以处理标志字符连成一串的情况。因此(6)空缺处所填写的内容是“str[i]==del”或其等价形式。 当退出第2个while循环时，当前字符str[i]不是标志字符，此时从str[i]开始继续寻找，直到标志字符出现的…个子字符串(变量i保持不变，用j标记寻找的过程)，给找到的字符序列置字符串结束标志，以便于后面语句的输出。因此(7)空缺处所填写的内容是“str[j]”。 printf输出语句结束之后，就要继续寻找后面不包含标志字符的子字符串。此时，需要把数组指针i移至j的后面，再继续扫描。因此(8)空缺处所填写的内容是“i=j+1”。
第10题：
阅读下列函数说明和C函数，将应填入______处的语句写在答题纸的对应栏内。
[函数2.1说明]
函数palindrome(char s[])的功能是：判断字符串s是否为回文字符串，若是，则返回0，否则返回-1。若一个字符串顺读和倒读都一样，称该字符串是回文字符串，例如，“LEVEL”是回文字符串，而“LEVAL”不是。
[函数2.1]
int palindrome(char s[])
{
char *pi， *pj；
pi=s；pj=s+strlen(s)-1；
while(pi＜pj&& (1) ) {
pi++；pj--；
}
if( (2) ) return-1；
else return 0；
}
[函数2.2说明]
函数f(char *str，char del)的功能是：将非空字符串str分割成若干个子字符串并输出，del表示分割时的标志字符。
例如，若str的值为“33123333435”，del的值为“3”，调用此函数后，将输出3个子字符串，分别为“12”，“4”和“5”。
[函数2.2]
void f(char *str，char del)
{
int i，j，len；
len=strlen(str)；
i=0；
While(i＜len){
While( (3) )i++； /* 忽略连续的标志字符 */
/* 寻找从str[i]开始直到标志字符出现的一个子字符串 */
j＝i+1；
while(str[j]!=del &&str[j]!'\0')j++；
(4) ='\0'； /* 给找到的字符序列置字符串结束标志 */
printf("%s\t"，&str[i])；
(5)；
}
}
(1)*pi==*pj (2)pipj或 *pi != * pj，及其等价形式 (3)str[i]==del (4)str[j] (5)i=j+1 解析：[函数2.1]
若一个字符串顺读和倒读都一样，称该字符串是回文字符串。如果使用数组s[n]来存储一个字符串，则根据这个定义，要判断一个串是否是回文字符串，需要循环比较：
(1)该字符串的第一个元素s[0]和最后一个元素s[n-1]比较，如果s[0]不等于 s[n-1]，则s不是回文字符串。
(2)如果s[0]等于s[n-1]，则第二个元素s[1]和倒数第二个元素s[n-2]比较，如果s[1]不等于s[n-2]，则s不是回文字符串。
(3)依次类推，直到最中间的2个元素也比较完毕(如果s有偶数个元素)，或者只剩下中间的1个元素(如果s有奇数个元素)。
当上述循环结束时，如果最中间的元素没有进行比较，就说明s不是回文字符串，如果进行了比较，则s是回文字符串。
在函数2.1中，pi和pj是2个指向字符的指针，程序首先将s的首地址赋给pi(即 pi=&a[0])，将元素s[strlen(s)-1)的地址赋给pj(即pj=&s[strlen(s)-1])，当pipj并且pi和pj所指向的字符相等时进行循环：pi自增，pj自减。
退出循环后，如果pipj，则s是回文字符串(如果s有偶数个元素，则为pi＞pj，如果 s有奇数个元素，则为pi=pj)；如果pipj，则s不是回文字符串。
[函数2.2]
由函数2.2说明可知，此函数对给定的字符串进行从左至右的扫描，找出不包含标志字符的子字符串。
在函数2.2中，i的初值为0，len表示字符串的长度。当ilen时进行循环：如果当前字符是标志字符，则不做处理，继续扫描以处理标志字符连成一串的情况。当退出该循环时，当前字符str[i]不是标志字符，这时开始寻找从str[i]开始，直到标志字符出现的一个子字符串(i保持不变，用j标记寻找的过程)，给找到的字符序列置字符串结束标志，以便于后面语句的输出。
输出语句结束后，就要继续寻找后面的不包含标志字符的子字符串，这时需要把指针 i移动j的后面，继续扫描。