试题四(共 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*/
}
}
●试题五
阅读以下程序说明和C程序,将应填入(n)处的子句,写在答卷纸的对应栏内。
【程序说明】
函数int commstr(char *str1,char *str2,int *sublen)从两已知字符串str1和str2中,找出它们的所有最长的公共子串。如果最长公共子串不止1个,函数将把它们全部找出并输出。约定空串不作为公共子串。
函数将最长公共子串的长度送入由参数sublen所指的变量中,并返回字符串str1和str2的最长公共子串的个数。如果字符串str1和str2没有公共子串,约定最长公共子串的个数和最长公共子串的长度均为0。
【程序】
int strlen(char *s)
{char *t=s;
while(*++);
return t-s-1;
}
intcommstr(char)*str1,char *str2,int *sublen
{char*s1,*s2;
int count=0,len1,len2,k,j,i,p;
len1=strlen(str1);
len2=strlen(str2);
if(len1>len2)
{s1=str1;s2=str2;}
else{len2=len1;s1=str2;s2=str1;}
for(j=len2;j>0;j--)/*从可能最长子串开始寻找*
{for(k=0; (1) <=len2;k++)/*k为子串s2的开始位置*/
{for(i=0;s1[ (2) ]!='\0';i++;)/* i为子串s1的开始位置*/
{/* s1的子串与s2的子串比较*/
for(p=0;p<j)&& (3) ;p++);
if ( (4) )/*如果两子串相同*/
{for(p=0);p<j;p++}/*输出子串*/
printf("%c",s2[k+p]);
printf("\n");
count++;/* 计数增1*/
}
}
}
if (count>0)break;
*sublen=(count>0)? (5) :0;
return count;
}
●试题五
【答案】(1)k+j(2)i+j-1(3)s1[i+p]==s2[k+p](4)p==j或p>=j(5)j
【解析】略。
阅读以下技术说明和流程图,根据要求回答问题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)空缺处的内容填写完整。
阅读以下说明和流程图,填补流程图中的空缺(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~2,将解答填入对应的解答栏内。
[说明]
下面的流程图描述了计算自然数1到N(N≥1)之和的过程。
[流程图]
[问题1] 将流程图中的(1)~(3)处补充完整。
[问题2] 为使流程图能计算并输出1*3+2*4+…+N*(N+2)的值,A框内应填写(4);为使流程图能计算并输出不大于N的全体奇数之和,B框内应填写(5)。
近3上半年程序员考试专项习题训练3及答案-下午卷试题一(共15分)阅读以下说明和流程图,填补流程图中的空缺,将解答填入答题纸的对应栏内。【说明】下面流程图的功能是:在给定的两个字符串中查找最长的公共子串,输出该公共子串的长度L及其在各字符串中的起始位置(L=0时不存在公共字串)。例如,字符串the light is not bright tonight ” 与“ Tonight the light is not bright ”的最长公共子串为 the light is not bright?,长度为22,起始位置分别为2和10。设A1:M表示由M个字符A1,A2,,AM依次组成的字符串;B1:N表示由N个字符B1, B2,,BN依次组成的字符串,MN1。本流程图采用的算法是:从最大可能的公共子串长度值开始逐步递减,在A、B字符串中查找是否存在长度为L的公共子串,即在A、B字符串中分别顺序取出长度为L 的子串后,调用过程判断两个长度为L的指定字符串是否完全相同(该过程的流程略)。【流程图】(1) N 或 min(M,N) (2) M-L+1 (3) N-L+1 (4) L-1 (5) L, I, J本题考查对算法流程图的理解和绘制能力。这是程序员必须具有的技能。本题的算法可用来检查某论文是否有大段抄袭了另一论文“the light is not bright tonight是著名的英语绕口令,它与onight the light is not bright大同小异。由于字符串A和B的长度分别为M和N,而且MN1,所以它们的公共子串长度 L必然小于或等于N。题中采用的算法是,从最大可能的公共子串长度值L开始逐步递减,在A、B字符串中查找是否存在长度为L的公共子串。因此初始时,应将min (M, N)送L。或直接将N送L。(1)处应填写N或min(M,N),或其他等价形式。对每个可能的L值,为查看A、B串中是否存在长度为L的公共子串,显然需要执行双重循环。A串中,长度为L的子串起始下标可以从1开始直到M-L+1 (可以用实例来检查其正确性);B串中,长度为L的子串起始下标可以从1开始直到N-L+1。因此双重循环的始值和终值就可以这样确定,即(2)处应填M-L+1,或等价形式;(3)处应填N-L+1或等价形式(注意循环的终值应是最右端子串的下标起始值)。A串中从下标I开始长度为L的子串可以描述为AI:I+L-1; B串中从下标J开始长度为L的子串可以描述为AJ:J+L-1。因此,双重循环体内,需要比较这两个子串(题中采用调用专门的函数过程或子程序来实现)。如果这两个子串比较的结果相同,那么就己经发现了 A、B串中最大长度为L的公共子串,此时,应该输出公共子串的长度值L、在A串中的起始下标I、在B串中的起 始下标J。因此,(5)处应填L, I, J (可不计顺序)。如果这两个子串比较的结果不匹配,那么就需要继续执行循环。如果直到循环结束仍然没有发现匹配子串时,就需要将L减少1 (4)处填L-1或其等价形式)。只要L非0,则还可以继续对新的L值执行双重循环。如果直到L=0,仍没有发现子串匹配,则表示A、B两串没有公共子串。试题二(共15分)阅读以下说明和C函数,填补函数代码中的空缺,将解答填入答题纸的对应栏内, 【说明1】函数f(double eps)的功能是:利用公式计算并返回的近似值。【函数1】【说明2】函数fun(Char *str)的功能是:自左至右顺序取出非空字符串str中的数字字符,形成一个十进制整数(最多8位)。例如,若str中的字符串为iyt?67kpf3g8d5.j4ia2e3p12”, 则函数返回值为67385423。【C函数2】(1)n+2 (2) -s 或-1*s (3) *p!=0或等价形式(4)num* 10或等价形式 (5) p+或等价形式本题考查c语言程序设计基本技能。考生需认真阅读题目中的说明,从而确定代码的运算逻辑,在阅读代码时,还需注意各变量的作用。函数f(double eps)的功能是计算的近似值。观察题中给出的计算公式,可知在循环中n每次递增2,因此空(1)处应填入n+2。由于公式中的各项是正负交替的,因此结合表达式term = S/n可知变量s就是起此作用的。空(2)处应填入-s或-1*s。对于函数fun(char *str),从字符序列中取出数字并组合为一个整数时,对于每个数字,只需将之前获取的部分乘以10再加上该数字的值即可。以67385423为例。67385423 = (0+6)* 10+7)* 10+3)* 10+8)* 10+5)* 10+4)* 10+2)* 10+3函数中的变量i是用来计算位数的,num用来计算所获得的整数值。显然,最多读取字符序列中的前8个数字,或者到达字符序列的末尾(*p!=0)时,计算也需结束。 因此,空(3)处应填入“*p!=0”。根据num的作用,空(4)处应填入“num* 10”。根据指针P的作用,空(5)处的代码应使得p指向下一个字符,因此应填入“ p+”。试题三(共15分)阅读以下说明和C代码,填补代码中的空缺,将解答填入答题纸的对应栏内。【说明】下面的程序代码根据某单位职工的月工资数据文件(名称为Salary.dat,文本文件), 通过调用函数GetlncomeTax计算出每位职工每月需缴纳的个人所得税额并以文件(名称为IncomeTax.dat,文本文件)方式保存。例如,有4个职工工资数据的Salary.dat内容如下,其中第一列为工号(整数),第2列为月工资(实数)。1030001 6200.001030002 5800.002010001 8500.002010010 8000.00相应地,计算所得IncomeTax.dat的内容如下所示,其中第3列为个人所得税额:1030001 6200.00 47.201030002 5800.00 35.942010001 8500.00 233.502010010 8000.00 193.00针对工资薪金收入的个人所得税计算公式为:个人所得税额=应纳税所得额X税率速算扣除数 其中,应纳税所得额=月工资三险一金起征点 税率和速算扣除数分别与不同的应,如表3-1所示。设三险一金为月工资的19%,起征点为3500元。例如,某人月工资为5800元,按规定19%缴纳三险一金,那么:其应纳税所得额X=58005800x19%3500=1198元,对应税率和速算扣除数分别为3%和0元,因此,其个人所得税额为1198X3%-0=35.94元。 【C代码】(1)double GetIncomeTax(double salary)或 double GetlncomeTax(double)(2)!fin或 fin=NULL 或 fin=0(3)!fout 或 fout=NULL 或 fout=0(4)&id, &salary(5)GetlncomeTax(salary)(6)salary *(1-RATE)或等价形式 注:RATE可替换为0.19本题考查c语言程序设计基本技能。考生需认真阅读题目中的说明,以便理解问题并确定代码的运算逻辑,在阅读代码时,还需注意各变量的作用。根据注释,空(1)处应填入double GetIncomeTax(double salary)或double GetlncomeTax(double)”,对函数GetlncomeTax 进行声明。空(2)、(3)处所在的代码是判断文件打开操作是否成功,因此应分别填入“!fin”、“! fout”。根据说明可知,变量id和salary分别表示工号和月工资数。空(4)处所在语句为从文件中读取数据的操作,从fscanf的格式控制串可知读取的两个数是整数和双精度浮点数,则输入表列的两个变量分别为接收整数值的变量id和接收整数值的变量salary,因此空(4)应填入“&id, &salary”。空(5)处所在代码向fout关联的文件写入计算出的所得税额,显然需调用函数GetlncomeTax 来计算,因此应填入 “ GetlncomeTax(salary) ”。空(6)处的代码计算应纳税所得额,根据说明中给出的计算公式及三险一金的计算方法:应纳税所得额=月工资三险一金起征点 空(6)处应填入“salary *(1-RATE)”。试题四(共15分)阅读以下说明和C函数,填补代码中的空缺,将解答填入答题纸的对应栏内。【说明】函数Combine(LinkList La, LinkList Lb)的功能是:将元素呈递减排列的两个含头结点单链表合并为元素值呈递增(或非递减)方式排列的单链表,并返回合并所得单链表的头指针。例如,元素递减排列的单链表La和Lb如图4-1所示,合并所得的单链表如图4-2所示。 【c函数】(1) LinkList (2) pa & pb (3) tp-next(4) tp (5) tp = pa本题考查数据结构应用及C语言实现。链表运算是C程序设计题中常见的考点,需熟练掌握。考生需认真阅读题目中的说朋,以便理解问题并确定代码的运算逻辑,在阅读代码时,还需注意各变量的作用。根据注释,空(1)所在的代码定义指向链表中结点的指针变量,结合链表结点类型的定义,应填入“LinkList ”。由于pa指向La链表的元素结点、pb指向Lb链表的元素结点,空(2)所在的while语句中,是将pa指向结点的数据与pb所指向结点的数据进行比较,因此空(2)处应填 入 pa & pb ,以使运算pa-datapb-data?中的pa和pb为非空指针。从空(3)所在语句的注释可知,需将tp所指结点插入Lc链表的头结点之后,空(3) 处应填入tp-next,空(4)处应填入tp,如下图所示。空(5)所在的while语句处理还有剩余结点的链表,pa是保存指针的临时变量循环中的下面4条语句执行后的链表状态如下图所示。空(5)处应填入“ tp = pa”,以继续上述的重复处理过程。 试题五(共15分)阅读下列说明和C+代码,填补代码中的空缺,将解答填入答题纸的对应栏内。【说明】设计RGB方式表示颜色的调色板,进行绘图,其类图如图5-1所示9该程序的C+ 代码附后。【C+代码】(1) free(palette) (2) this-number (3) static const(4) new MyColor (5) new Drawing()本题考查C+程序设计的能力,涉及类、对象、方法定义和相关操作、要求考生根据给出的案例和代码说明,认真阅读并理清程序思路,然后完成题目。先考查题目说明。本题目中涉及到颜色、调色板、绘图等类以及初始化和调色相关等操作。根据说明进行设计。类图中给出三个类Drawing、Palette和MyColor及其之间的关系。Drawing与Palette、MyColor之间具有关联关系,Palette与MyColor之间是聚合关系。MyColor为以RGB方式表不颜色,由属性red、green和blue表示,每个MyColor对象即为一个RGB颜色。MyColor具有两个构造器,缺省构造器将RGB颜色均初始化为0;带参数的构造方法将当前对象的RGB值设置为调用构造方法时消息中所传递的参数值。pr
阅读以下说明和流程图,填补流程图中的空缺(1)一(5),将解答填入答题纸的对应栏内。
【说明】
下面的流程图采用公式ex=1+x+x2/2 1+x3/3 1+x4/4 1+…+xn/n!+???计算ex的近似值。设x位于区间(0,1),该流程图的算法要点是逐步累积计算每项xx/n!的值(作为T),再逐步累加T值得到所需的结果s。当T值小于10-5时,结束计算。
【流程图】
阅读以下说明和流程图,填补流程图中的空缺(1)~(5),将解答填入对应栏内。
[说明]
下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。
设这篇文章由字符A(0),…,A(n-1)依次组成,指定关键词由字符B(0),…,B(m-1)依次组成,其中,n>m≥1。注意,关键词的各次出现不允许有交叉重叠。例如,在“aaaa”中只出现两次“aa”。
该流程图采用的算法是:在字符串A中,从左到右寻找与字符串B相匹配的并且没有交叉重叠的所有子串。流程图中,i为字符串A中当前正在进行比较的动态予串首字符的下标,j为字符串B的下标,k为指定关键词出现的次数。
[流程图]
阅读以下说明和流程图,将应填入(n)处的字句写在对应栏内。
[说明]
下面的流程图用于计算一个英文句子中最长单词的长度(即单词中字母个数)MAX。假设该英文句子中只含字母、空格和句点“.”,其中句点表示结尾,空格之间连续的字母串称为单词。
[流程图]
阅读下列说明和流程图,将应填入(n)处。
[流程图说明]
流程图1-1描述了一个算法,该算法将给定的原字符串中的所有前导空白和尾部空白都删除,但保留非空字符之间的空白。例如,原字符串“ File Name ”,处理后变成“File Name”。流程图1-2、流程图1-3、流程图1-4分别详细描述了流程图1-1中的框A,B,C。
假设原字符串中的各个字符依次存放在字符数组ch的各元素ch(1),ch(2),…,ch(n)中,字符常量KB表示空白字符。
流程图1-1的处理过程是:先从头开始找出该字符串中的第一个非空白字符ch(i),再从串尾开始向前找出位于最末位的非空白字符ch(j),然后将ch(i),…,ch(j)依次送入 ch(1),ch(2),…中。如果原字符串中没有字符或全是空白字符,则输出相应的说明。在流程图中,strlen是取字符串长度函数。
[问题]在流程图1-1中,判断框P中的条件可表示为:
i>(5)
阅读以下说明和流程图,填补流程图中的空缺,将解答填入答题纸的对应栏内。 【说明】 下面流程图的功能是:在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组 A[1:n](n≥2)中,要求寻找最长递增子序列 A[K: K+L-1] (即A[K]<A[K+1]<…<A[K+L-1])。流程图中,用 Kj 和Lj 分别表示动态子序列的起始下标和长度,最后输出最长递增子序列的起始下标 K 和长度 L。 例如,对于序列 A={1 ,2,4,4 ,5,6,8,9,4,5,8},将输出K=4, L=5。
【流程图】注:循环开始框内应给出循环控制变量的初值和终值,默认递增值为1,格式为: 循环控制变量=初值,终值