2021年程序员模拟题1

试卷预览

1 问答题 1分

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

【说明】

模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1。

KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：

1．在串t和串s中，分别设比较的起始下标i=j=0。

2．如果串t和串s都还有字符，则循环执行下列操作：

（1）如果j=-l或者t[i]=s[j]，则将i和j分别加1，继续比较t和s的下一个字符；

（2）否则，将j向右滑动到next[j]的位置，即j =next[j]。

3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回-1。

其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。

【C代码】

（1）常量和变量说明

t，s：长度为lt和ls的字符串

next:next数组，长度为ls

（2）C程序

#include ＜stdio.h>#include＜stdlib.h>#include＜string.h>/*求next[]的值*/void get_next( int*next, char *s, int ls) { inti=0，j=-1; next[0]=-1;/*初始化next[0]*/ while(i＜ ls){/*还有字符*/ if(j==-1lls[i]==s[j]){/*匹配*/ j++; i++; if(s[i]==s[j]) next[i]= next[j]; else Next[i]= j; }else j = next[j]; }} int kmp( int*next, char *t ,char *s, int lt, int ls ) { Inti= 0,j =0 ; while(i ＜ lt && （1） ){ if(j==-1 || （2） ){ i++ ; j++ ; }else （3） ;}if (j >= ls)return （4） ;else return-1;}

【问题1】（8分）

根据题干说明，填充C代码中的空（1）～（4）.

【问题2】（2分）

根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）（主串和子串的长度分别为It和Is，用O符号表示）。

【问题3】（5分）

根据C代码，字符串"BBABBCAC"的next数组元素值为（6）（直接写素值，之间用逗号隔开）。若主串为"AABBCBBABBCACCD"，子串为"BBABBCAC"，则函数Kmp的返回值是（7）。

查看答案 开始考试

正确答案：

本题解析：

【问题1】

（1）：j＜ls;

（2）：t[i]==s[j];

（3）：get_next(next, s, ls);

j=next[j];

（4）：i+1-ls;

【问题2】（2分）

（5）O(ls+lt)

【问题3】

（6）[-1, -1,1, -1, -1, 2, 0, 0]，

（7）6

2 问答题 1分

阅读说明和流程图，填补流程图中的空缺（1）?（5），将答案填入答题纸对应栏内。【说明】本流程图用于计算菲波那契数列{a1=1，a2=1，…,an=an-1+an-2!n=3,4,…}的前n项（n>=2) 之和S。例如，菲波那契数列前6项之和为20。计算过程中，当前项之前的两项分别动态地保存在变量A和B中。【流程图】

查看答案 开始考试

正确答案：

本题解析：

（1）2或A+B（2）n（3）A+B（4）B-A（5）S+B

【解析】

菲波那契数列的特点是首2项都是1，从第3项开始，每一项都是前两项之和。该数列的前几项为1，1，2, 3，5，8，…。在流程图中，送初始值1—A，2—B后，显然前2项的和S应等于2,所以（1）处应填2 (或A+B)。此时2→i (i表示动态的项编号），说明已经计算出前2项之和。接着判断循环的结束条件。显然当i=n时表示已经计算出前n项之和，循环可以结束了。因此（2）处填n。判断框中用“>”或“≥”的效果是一样的，因为随着i的逐步增1，只要有i=n结束条件就不会遇到i>n的情况。不过编程的习惯使循环结束条件扩大些，以防止逻辑出错时继续循环。接下来i+1→i表示数列当前项的编号增1，继续往下计算。原来的前两项值（分别在变量A和B中）将变更成新的前两项再放到变量A和B中。

首先可以用A+B—B实现（原A) + (原B)—(新B)，因此（3）处填A+B。为了填新A值（原来的B值)，不能用B—A，因为变量B的内容已经改变为（原A) + (原B)，而B-A正是（（原A) + (原B))-(原A)=(原B)，因此可以用B-A—A来实现新A的赋值。这样，（4）处填B-A。最后应是前n项和值的累加（比原来的S值增加了新B值)，所以（5）处应填S+B。填完各个空后，最好再用具体的数值来模拟流程图走几个循环检查所填的结果（这是防止逻辑上出错的好办法）。

3 问答题 1分

阅读以下说明和C函数，填充（1）~（5）的空缺，将解答填入答题纸的对应栏内。【说明】编写程序，对于从键盘输入的3个实数a、b、c，计算实系数一元二次方程的根并输出所求的根。 【函数】 #include＜stdio.h＞ #include＜stdlib.h＞ #include＜math.h＞ Main() { float a,b,c,delta,x1,x2; printf("Enter a,b,c"); scanf("%f%f%f",&a,&b,&c)); if(（1）) if(（2）) printf("Input error!\n"); else printf("The single root is %f\n",（3）); else { delta=b*b-4*a*c; if(（4）) { x1=(-b+sqrt(delta))/(2*a); x2=(-b-sqrt(delta))/(2*a); printf("x1=%8.2f\nx2=%8.2f\n",x1,x2,); } else if(delta==0) printf("x1=x2=%8.2f\n",（5）); else { Printf("z2=%8.2f+%8.2f*i\n",-b/(2*a),sqrt(-delta)/)(2*abs(a))); Printf("z2=%8.2f-%8.2f*i\n",-b/(2*a),sqrt(-delta)/(2*abs(a))); } }}

查看答案 开始考试

正确答案：

本题解析：

（1）a==0

（2）b==0

（3）-c/b （4）delta＞0(或b*b-4*a*c＞0)

（5）-b/(2*a) (或-b/2/a)

【解析】

对于如何求出一元二次方程的根，是解决这个题目的关键。首先我们来回忆一下数学中求一元二次方程根的方法。在数学中求一元二次方程根的步骤如下。第一步是确定方程是否为一元二次方程，这需要判断二次方系数和一次方系数是否为0，如果都为0，则方程有错。如果只是二次方系数为零，则方程为一元一次方程，方程有一个解。第二步是用Δ=b*b-4*a*c与0的关系来判断解的个数，如果Δ＞0，方程有2个不同的解；如果Δ=0，方程有一个解；而Δ＜0时，方程无解。 第三步才是求解。 现在我们来看主函数，在主函数中，首先声明了一些实数变量，其中变量a、b、c分别存放我们从键盘输入的3个实数，而detal中存放的是Δ的值，x1、x2中存放方程根的值。接下来是从键盘输入3个值，作为一元二次方程的系数，在对一元二次方程求解以前我们需要考虑系数值为0的情况，因此，第1空应该填“a==0”，第2空应该填“b==0”。 在a等于0而b不等于0的情况下，方程为一元一次方程，可以直接用-c/b求得其解，第3空明显是要输出这个解。再往下看，程序计算了Δ的值，那么接下来应该是判断Δ与0的关系了，从程序中可以看出，方程在第4空的条件下有两个解，那么第4空应该填“delta＞0”。而第5空是在delta=0的条件下方程的解，因此第5空应该填“-b/(2*a)”。

4 问答题 1分

阅读以下Java代码，填充（1）~（5）的空缺，将解答填入答题纸的对应栏内。【说明】进行两个整数之间的比较，由考生通过输入窗口分别输入两个整数，程序比较出结果。例如：先后输入的两个数分别为25和36。 比较结果显示： 25!=36 25＜36 25＜=36 【Java代码】 import javax.swing.JOptionPane; public class Java3 { public static void main(String args[]) { String （1） //用户输入第1个字符串 secondNuimber, //用户输入第2个字符串 result; //包含输出结果的字符串 int number1, //比较的第1个数 number2; //比较的第2个数 //读用户输入的第1个字符串 firstNumber= JOptionPane（2）("Enter first integer:"); //读用户输入的第2个字符串 secondNumber= JOpttionPane.showlnputDialog("Enter second integer:"); //将字符串类型转换成整数类型 number1=Integer.（3）(firstNumber); number2=Integer.parselnt(secondNumber); result=""; if(（4）) result=number1+"=="+number2; if(number1!=number2) result=number1+"!=”"+number2; if(number1＜number2) result=result+"\n"+number1+"＜"+number2; if(numbe1＞number2) result=result+"\n"+number1+"＞"+number2; if(number1＜=number2) result=result+"\n"+number1+"＜="+number2; if(number1＞=number2) result=result+"\n"+number1+"＞="+number2; //显示结果 JOptionPane.（5）( null,result,"Comparison Results", JOptionPane.INFORMATION_MESSAGE.; //程序正常退出 System.exit(0); }}

查看答案 开始考试

正确答案：

本题解析：

（1）firstNumber（2）showInputDialog（3）parseInt（4）number1==number2（5）showMessageDialog

【解析】

试题要求由考生通过输入窗口分别输入两个整数，比较其大小并输出结果。下面来分析程序代码，程序中定义了一个类Java3，在这个类中实现题目要求的功能。第1空所在代码行的注释是用户输入第1个字符串，但这在程序的开始，没有进行输入操作，应该是声明一个字符串型变量用来存放用户输入的第1个字符串，而在这个空的前面有一个关键字String用来表明所声明的变量是字符串型的，结合后面的程序，我们知道用来存放输入的第1个字符串的变量是firstNumber，因此，此空答案为“firstNumber。根据注释，第2空所在代码行的作用是读用户输入的第1个字符串，而实现这个功能的是JOptionPane包中的showInputDialog()函数，结合后面的程序，我们不难找出此空的答案为“showlnputDialog”。再根据注释，我们知道第3空所在代码行的作用是将第1个字符串类型的内容转换成整数类型，在Java中，一般通过类型对象的parseInt()方法，结合后面的程序，我们也不难找出此空的答案为“parseInt”。第4空是条件判断语句中的条件，根据整个程序，我们不难发现变量result中存放的是要输出的结果，而语句result=number1+"=="+number2是将number1=number2这样一个结果存放到result中，那么只有当number1等于number2时，才输出这个结果，因此，第4空的作用应该是确定number1等于number2。所以，此空答案为“number1==number2”。第5空在注释显示结果下面，从上面的程序中我们知道，变量result中存放的是要输出的结果，根据下面的程序，很明显是要调用包JOptionPane中的某个方法来实现输出。此方法应该是showMessageDialog()，因此，此空答案为“showMessageDialog”。

5 问答题 1分

阅读以下问题说明、C 程序和函数，将解答填入答题纸的对应栏内。

【问题 1】

分析下面的C 程序，指出错误代码（或运行异常代码）所在的行号。

【C 程序】

【问题 2】

函数inputArr(int a[]， int n)的功能是输入一组整数（输入0或输入的整数个数达到n时结束）存入数组 a，并返回实际输入的整数个数。函数 inputArr 可以成功编译。但测试函数调用inputArr后，发现运行结果不正确。

请指出错误所在的代码行号，并在不增加和删除代码行的情况下进行修改，写出修改正确后的完整代码行，使之符合上述设计意图。

【C 函数】

查看答案 开始考试

正确答案：

本题解析：

【问题1】

5，或arrChar="test"

7，或*P='0';

【问题2】

【解析】

本题考查 C 程序编写和调试中常见错误的识别和改正。

【问题1】在C语言中，指针表示内存单元的地址，指针变量可用于存储指针类 型的值，即内存单元的地址值。变量的值在程序运行过程中允许修改，而常量则不允许修改。可以令指针指向一个变量或常量，但若指针指向一个常量，则不允许通过指针修改该常量。

第 5 行代码有错，即对数组名arrChar的赋值处理是错误的。在 C语言中，数组名是表示数组空间首地址的指针常量，程序中不允许对常量赋值。

第 7行代码有错，在第 6行中，通过 p = "testing"使指针变量指向了一个字符串常量，此后可以再令指针 p指向其他字符或字符串，但不能通过指针修改字符串常量的内容。

【问题2】该函数中出现的错误是编写 C程序时的常见错误。scanf 是 C标准库函数中的格式化输入函数，其原型如下：

int scanf(char *format ，...);

使用时，第一个实参是格式控制串，之后的实参是地址1，地址 2，…

在本题中，要求以十进制整数格式输入一个整数并存入 a[k] ，数组元素a[k]实质上一个整型变量，必须用"&"求得 a[k]的地址作为实参调用 scanf 函数，因此，第 4行出错，正确代码应为"scanf("%d&a[k]);"。

C程序中将相等运算符"="误用为赋值运算符"="也是常见的一个错误，由于"="也是合法的运算符并且 C语言中用 0 和非 0来表示逻辑假和逻辑真，因此在应产生逻辑值的地方产生了其他数值也可以，因此该错误通常只能用人工检查和排除。第 6 行的正确代码应为"if (k==n)break;"。

在该程序中，结束循环的一个条件是k等于n，另一个条件是输入的整数为0。另 外，do-whi1e的循环条件为真（非0）时要继续循环，因此，循环条件应该是判断输入的值不等于 0。观察循环体中与数组元素有关的部分，如下所示：

scanf("%d"，&a[k]);