试题一(共15 分 )
阅读以下说明和流程图,将应填入 (n) 处的字句写在答题纸的对应栏内。
【 说明 】
下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。
设这篇文章由字符A(0),…,A(n-1)依次组成,指定关键词由字符B(0),…,B(m-1)依次组成,其中n>m≥1。注意,关键词的各次出现不允许有交叉重叠。例如,在“aaaa”中只出现两次“aa”。
该流程图采用的算法是:在字符串A中,从左到右寻找与字符串B相匹配的并且没有交叉重叠的所有子串。流程图中,i 为字符串 A 中当前正在进行比较的动态子串首字符的下标,j为字符串B 的下标,k为指定关键词出现的次数。
第1题:
阅读以下说明和流程图,填补流程图中的空缺(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)等逐对字符进行比较。若发现不同,则需要取下一个子串进行比较,依此类推。
【流程图】
第2题:
阅读下列说明和流程图,将应填入(n)的字句写在对应栏内。
【说明】
下列流程图(如图4所示)用泰勒(Taylor)展开式
sinx=x-x3/3!+x5/5!-x7/7!+…+(-1)n×x2n+1/(2n+1)!+…
【流程图】
计算并打印sinx的近似值。其中用ε(>0)表示误差要求。
第3题:
阅读下列说明和流程图,将应填入(n)处的语句写在对应栏内。
【说明】
下列流程图用于从数组K中找出一切满足:K(I)+K(J)=M的元素对(K(I),K(J))(1≤I≤J≤N)。假定数组K中的N个不同的整数已按从小到大的顺序排列,M是给定的常数。
【流程图】
此流程图1中,比较“K(I)+K(J):M”最少执行次数约为(5)。
第4题:
阅读以下说明和流程图,将应填入(n)处的字句写在对应栏内。
[说明]
下面的流程图实现了正整数序列{K(1),K(2),…,K(n)}的重排,得到的新序列中,比K(1)小的数都在K(1)的左侧,比K(1)大的数都在K(1)的右侧。以n=6为例,序列{12,2,9,13,21,8}的重排过程为:
{12,2,9,13,21,8}
→{2,12,9,13,21,8}
→{9,2,12,13,21,8}
→{8,9,2,12,13,21}
[流程图]
第5题:
阅读下列说明和流程图,将应填入(n)处的语句写在对应栏内。
【说明】
下列流程图用泰勒(Taylor)展开式y=ex=1+x+x2/2!+x3/3!+…+xn/n!+…计算并打印ex的近似值,其中用ε(>0)表示误差要求。
【流程图】
第6题:
阅读以下说明和流程图,将应填入(n)处的字句写在对应栏内。
[说明]
设学生某次考试的成绩按学号顺序逐行存放于某文件中,文件以单行句点“.”为结束符。下面的流程图读取该文件,统计出全部成绩中的最高分max和最低分min。
第7题:
阅读以下说明和流程图,填补流程图中的空缺(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时,结束计算。
【流程图】
第8题:
阅读以下说明和流程图,将应填入(n)处的字句写在对应栏内。
【说明】
已知头指针分别为La和lb的有序单链表,其数据元素都是按值非递减排列。现要归并La和Lb得到单链表Lc,使得Lc中的元素按值非递减排列。程序流程图如下所示:
第9题:
阅读下列说明和流程图,将应填入(n)处的语句写在对应栏内。
【说明】
有数组A(4,4),把1到16个整数分别按顺序放入A(1,1),…,A(1,4),A(2,1),…,A(2,4),A(3,1),…,A(3,4),A(4,1),…,A(4,4)中,下面的流程图用来获取数据并求出两条对角线元素之积。
【流程图】
第10题:
阅读以下说明和流程图,填补流程图中的空缺(1)~(5),将解答填入对应栏内。
[说明]
下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。
设这篇文章由字符A(0),…,A(n-1)依次组成,指定关键词由字符B(0),…,B(m-1)依次组成,其中,n>m≥1。注意,关键词的各次出现不允许有交叉重叠。例如,在“aaaa”中只出现两次“aa”。
该流程图采用的算法是:在字符串A中,从左到右寻找与字符串B相匹配的并且没有交叉重叠的所有子串。流程图中,i为字符串A中当前正在进行比较的动态予串首字符的下标,j为字符串B的下标,k为指定关键词出现的次数。
[流程图]