程序员考试专题测练及答案(2)（专项考练）
温故而知新，下笔如有神近三上半年程序员考试专项试题训练及答案-下午卷试题一【说明】下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。设这篇文章由字符A(0)，A(n-l)依次组成，指定关键词由字符B(0)，B(m-l) 依次组成，其中n>m>=l。注意，关键词的各次出现不允许有交叉重叠。例如，在“aaaa” 中只出现两次“aa”。该流程图采用的算法是：在字符串A中，从左到右寻找与字符串B相匹配的并且没有交叉重叠的所有子串。流程图中，i为字符串A中当前正在进行比较的动态子串首字符的下标，j为字符串B的下标，k为指定关键词出现的次数。 【流程图】(1) 0>k (2) i+j (3) i+m (4) i+1 (5) i本题考查用流程图描述算法的能力。 在文章中查找某关键词出现的次数是经常碰的问题。例如，为了给文章建立搜索关键词，确定近期的流行语，迅速定位文章的某个待修改的段落，判断文章的用词风格，甚至判断后半本书是否与前半本书是同一作者所写（用词风格是否一致）等，都采用了这种方法。流程图最终输出的计算结果就是文章字符串A中出现关键词字符串B的次数。显然，流程图开始时应将赋值0,以后每找到一处出现该关键词，就执行增1操作k=k+1. 因此（1)处应填0>K。字符串A和B的下标都是从0开始的。所以在流程图执行的开始处，需要给它们赋值0。接下来执行的第一个小循环就是判断A(i)，A(i+l)，A(i+j-1)是否完全等于B(0)，B(1)，B(m-l)，其循环变量j=0，1，m-1。只要发现其中对应的字符有一个不相等时，该小循环就结束，不必再继续执行该循环。因此，该循环中继续执行的判断条件应该是A(i+j)=B(j)且j<m。只要遇到或者(关键词各字符都已判断过）就不再继续执行该循环了。因此流程图的（2)处应填i+j。许多考生在（2)处填i,当j增1变化后，仍然使用A(i)进行比较就不对了。因此，在检查循环程序段时应多走查一次循环。如果（2)处整体的判断条件不成立，则该判断关键词的小循环结束。此时可能有两种情况。一是在j=0，l，m-1时全都成立(找到了一处关键词），直到j=M时才结束小循环；二是在时就发现了字符不等的情况，这说明此处并不出现关键词。因此流程图中用j<m来区分找到与没有找到关键词的两种情况。对于j=m，已找到一处关键词的情况，显然应该执行对关键词出现次数的变量进行增1计算。同时，为了继续进行以后的判断，应将字符串A的下标f右移m (这是因为题中假设关键词的出现不允许重叠）。因此（3)处应填写i+m，表示应该从已出现的关键词后面开始再继续进行判断。由于此时的j=m,书写i+J的答案也是正确的，但这不是程序员的好习惯，因为这不符合逻辑思维的顺势，在程序不断修改的过程中容易出错。不少考生在（3)处填写i+1，这意味着下次判断关键词将从A(i+1)开始，这就使关键词的出现有可能发生部分重叠的现象。流程图中，对于j<m的情况，表示刚才判断关键词时并非各个字符都完全相同，也就是说，刚才的判断结论是此处并没有出现关键词。即A(i)开始的子串并不是关键词。因此，下次判断关键词应该以A(i+1)开始，即（4)处应填i+1。在下次判断关键词之前还应该判断是否全文已经判断完。最后一次小循环判断应该是对A(n-m)，A(n-m+1)，A(n-l)的判断。下标n-m来自从n-1倒数m个数。可以先试验写出A(n-m)，A(n-m+1)，A(n-l)，再判断其个数是否为m。经检查，个数为（n-1)-(n-m)+1=m个，所以这是正确的。也可以用例子来检查次数是否正确。检查次数是程序员的基本功，数目的计算很容易少一个或多一个。既然最后一次判断关键词应该是对A(n-m)，A(n-m+1)，A(n-l)的判断，即对i=n-m进行的小循环判断，所以当i>n-m时就应该停止大循环，停止再查找关键词了。试题二阅读以下问题说明、C程序和函数，将解答填入答题纸的对应栏内。【问题1】分析下面的C程序，指出错误代码（或运行异常代码）所在的行号。【C程序】5，或 arrChar = "test" 7，或*P='0本题考查C程序编写和调试中常见错误的识别和改正。在C语言中，指针表示内存单元的地址，指针变量可用于存储指针类型的值，即内存单元的地址值。变量的值在程序运行过程中允许修改，而常量则不允许修改。可以令指针指向一个变量或常量，但若指针指向一个常量，则不允许通过指针修改该常量。第5行代码有错，即对数组名arrChar的赋值处理是错误的。在C语言中，数组名是表示数组空间首地址的指针常量，程序中不允许对常量赋值。第7行代码有错，在第6行中，通过p = "testing"使指针变量指向了一个字符串常量，此后可以再令指针p指向其他字符或字符串，但不能通过指针修改字符串常量的内容。【问题2】函数inputArr(int a, int n)的功能是输入一组整数（输入0或输入的整数个数迖到n时结束）存入数组a，并返回实际输入的整数个数。函数inputArr可以成功编译。但测试函数调用inputArr后，发现运行结果不正确。请指出错误所在的代码行号，并在不增加和删除代码行的情况下进行修改，写出修改正确后的完整代码行，使之符合上述设计意图。【C函数】该函数中出现的错误是编写C程序时的常见错误。scanf是C标准库函数中的格式化输入函数，其原型如下： .int scanf(char *format,.)；使用时，第一个实参是格式控制串，之后的实参是地址1，地址2,在本题中，要求以十进制整数格式输入一个整数并存入ak，数组元素ak实质上一个整型变量，必须用“&”求得ak的地址作为实参调用scanf函数，因此，第4行出错，正确代码应为“scanf("%d"，&ak);”。C程序中将相等运算符“=”误用为赋值运算符“=”也是常见的一个错误，由于“=”也是合法的运算符并且C语言中用0和非0来表示逻辑假和逻辑真，因此在应产生逻辑值的地方产生了其他数值也可以，因此该错误通常只能用人工检查和排除。第6行的正确代码应为“if(k=n)break;”。在该程序中，结束循环的一个条件是k等于n，另一个条件是输入的整数为0。另外，do-while的循环条件为真（非0)时要继续循环，因此，循环条件应该是判断输入的值不等于0。观察循环体中与数组元素有关的部分，如下所示：scanf("%d", &ak);k+;也就是说输入为0时存入了ak，而循环判断条件“ak=0”中的ak相对于刚存入了0的数组元素来说已经是ak+l了，.因此正确的条件为“ak-l!=0”。试题三【说明】基于管理的需要，每本正式出版的图书都有一个ISBN号。例如，某图书的ISBN号为“978-7-5606-2348-1”。ISBN号由13位数字组成：前三位数字代表该出版物是图书（前缀号），中间的9个数字分为三组，分别表示组号、出版者号和书名号，最后一个数字是校验码。其中，前缀号由国际EAN提供，已经采用的前缀号为978和979;组号用以区别出版者国家、地区或者语言区，其长度可为15位；出版者号为各出版者的代码，其长度与出版者的计划出书量直接相关；书名号代表该出版者该出版物的特定版次；校验码采用模10加权的算法计算得出。校验码的计算方法如下：第一步：前12位数字中的奇数位数字用1相乘，偶数位数字用3相乘（位编号从左到右依次为13到2)。第二步：将各乘积相加，求出总和5。第三步：将总和S除以10,得出余数R。第四步：将10减去余数R后即为校验码V。若相减后的数值为10,则校验码为0。 例如，对于ISBN号“978-7-5606-2348-1”，其校验码为1，计算过程为：S=9X1+7X3+8X1+7X3+5X1+6X3+0X1+6X3+2X1+3X3+4X1+8X3=139R=139mod10=9V=10-9= 1函数check(char code)用来检查保存在code中的一个ISBN号的校验码是否正确，若正确则返回true,否则返回false。例如，ISBN号“978-7-5606-2348-1”在code中的存储布局如表3-1所示（书号的各组成部分之间用分隔）： (1) k+,或temp+(2) i<12,或i<k<1( (空(1)处填k+)，或i< temp-1 (空(1)处填temp+)，或等价形式(3) tarri*3,或*(tarr+i)*3，或等价形式(4) tarri,或*(tarr+i)，或等价形式(5) S%10,或等价形式本题考查C程序设计基本技术。根据题目中的描述，在函数check(char code)中要先将保存在code中的编码存入tarr,同时根据题例中的tarr内容示例表可知，ISBN号前12位数字中的奇数位数字会存入tarr的偶数下标，偶数位数字存入tarr的奇数下标。将13位ISBN号存入tarr的代码如下所示：显然，空(1)处tarr的下标索引值不能使用i，需要另一个整型变量，题目中提供了k和temp,因此在此处用k+或temp+都可以。空（2)（4)处所在代码实现校验码的计算方法中的第一步和第二步，由于共需计算12位，因此空（2)处填入“i<12”。算法中规定，ISBN号前12位数字中的奇数位数字用1相乘，偶数位数字用3相乘，且将各乘积相加求出总和S。由于在数组tarr中，ISBN号的奇数位数字对应tarr的偶数下标、偶数位数字对应tarr的奇数下标。因此，空 (3)处应填入“tarri*3，空(4)处应填入“tarri”。校验码计算方法的第三步和第四步是：将总和S除以10,得出余数R;将10减去余数R后即为校验码V。若相减后的数值为10,则校验码为0。由空（5)处的代码，V 的值要么为0,要么为10-S%10。显然，校验码为0说明余数R为0,即S%10等于0, 因此空（5)处应填入“S%10”。 试题四【说明】某旅游服务应用程序运行时，根据输入的两个城市名查找其间的距离。各城市间的距离如表4-1所示。表格中的第一行和第一列表示城市名，表中的每个元素是一个整数，代表该元素所在行和列对应的城市之间的距离（单位：km)。在程序中，城市名用一维全局数组cityTable存储，城市之间的距离矩阵用二维全局数组kmTable表示，并用相应的值对这两个数组进行初始化。 程序执行时，首先按提示输入两个城市名，然后在cityTable中查找与城市名对应的下标，最后用该下标在kmTable中找到这两个城市之间的距离。程序中定义的函数FindCitylnSortedArray和GetCity说明如下：(1) 函数FindCitylnSortedArray的功能是用二分查找法在全局数组cityTable中查找城市名所对应的下标值。(2) 函数GetCity的功能是读入城市名，调用函数FindCitylnSortedArray来获取城市所对应的下标值。如果该城市名不存在，则提示用户重新输入。【C程序】(1) index >=0，或等价形式(2) index(3) lh<=rh,或等价形式(4) key, cityTable mid或key, *(cityTable+mid)(5) mid本题考查c语言程序设计基本能力。要求考生根据给出的案例和执行过程说明，认真阅读理清程序思路，然后完成题目。本题涉及一维和二维数组操作，以及数组上的查
