201005程序员下午真题
第 1 题
（共15 分）
阅读以下说明和流程图，将应填入（n）处的字句写在答题纸的对应栏内。
【说明】
下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。
设这篇文章由字符A(0)，…，A(n-1)依次组成，指定关键词由字符B(0)，…，B(m-1)依次组成，其中n>m≥1。注意，关键词的各次出现不允许有交叉重叠。例如，在“aaaa”中只出现两次“aa”。
该流程图采用的算法是：在字符串A中，从左到右寻找与字符串B相匹配的并且没有交叉重叠的所有子串。流程图中，i 为字符串 A 中当前正在进行比较的动态子串首字符的下标，j为字符串B的下标，k为指定关键词出现的次数。
【流程图】
答案与解析
- 试题难度：较难
- 知识点：流程图>流程图
- 试题答案：
- 试题解析：本题考查用流程图描述算法的能力。
在文章中查找某关键词出现的次数是经常碰的问题。例如，为了给文章建立搜索关键词，确定近期的流行语，迅速定位文章的某个待修改的段落，判断文章的用词风格，甚至判断后半本书是否与前半本书是同一作者所写（用词风格是否一致）等，都采用了这种方法。
流程图最终输出的计算结果 k就是文章字符串 A中出现关键词字符串 B的次数。显然，流程图开始时应将 k赋值 0，以后每找到一处出现该关键词，就执行增1操作 k=k+1。因此（1）处应填0→k。
字符串 A和 B的下标都是从 0开始的。所以在流程图执行的开始处，需要给它们赋值 0。接下来执行的第一个小循环就是判断 A(i)，A(i+1)，…，A(i+j一1)是否完全等于 B（0），B（1），…，B(m一1)，其循环变量j=0，l ，…，m-1。只要发现其中对应的字符有一个不相等时，该小循环就结束，不必再继续执行该循环。因此，该循环中继续执行的判断条件应该是 A（i+j）=B（j）且j<m。只要遇到 A（i+j）≠B（j）或者 j=m（关键词各字符都已判断过）就不再继续执行该循环了。因此流程图的（2）处应填i+j。
许多考生在（2）处填 i，当j 增 1 变化后，仍然使用 A（i）进行比较就不对了。因此，在检查循环程序段时应多走查一次循环。
如果（2）处整体的判断条件不成立，则该判断关键词的小循环结束。此时可能有两种情况。一是在 j=0，1 ，…，m-1 时全都成立 A（i+j）=B（j）（找到了一处关键词），直到j=m 时才结束小循环；二是在 j<m 时就发现了字符不等的情况，这说明此处并不出现关键词。 因此流程图中用 j<m来区分找到与没有找到关键词的两种情况。
对于 j=m，己找到一处关键词的情况，显然应该执行 k=k+1，对关键词出现次数的变量 k进行增 1计算。同时，为了继续进行以后的判断，应将字符串 A 的下标 i右移 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一1）的判断。下标 n-m来自从 n-1 倒数 m个数。可以先试验写出A（n-m），A（n-m+1），… ，A（n一1），再判断其个数是否为m。经检查，个数为 （n-1）-（n-m）+1=m个，所以这是正确的。也可以用例子来检查次数是否正确。检查次数是程序员的基本功，数目的计算很容易少一个或多一个。 既然最后一次判断关键词应该是对A（n-m），A（n-m+1），… ，A（n一1）的判断，即对 i=n-m进行的小循环判断，所以当 i>n-m 时就应该停止大循环，停止再查找关键词了。
第 2 题
（共 15 分）
阅读以下问题说明、C 程序和函数，将解答填入答题纸的对应栏内。
【问题 1】
分析下面的C 程序，指出错误代码（或运行异常代码）所在的行号。
【C 程序】
【问题 2】
函数inputArr(int a[]， int n)的功能是输入一组整数（输入0或输入的整数个数达到n时结束）存入数组 a，并返回实际输入的整数个数。函数 inputArr 可以成功编译。但测试函数调用inputArr后，发现运行结果不正确。
请指出错误所在的代码行号，并在不增加和删除代码行的情况下进行修改，写出修改正确后的完整代码行，使之符合上述设计意图。
【C 函数】
答案与解析
- 试题难度：较难
- 知识点：C程序设计>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]);
k++;
也就是说输入为 0 时存入了a[k]，而循环判断条件"a[k]==0"中的 a[k]相对于刚存入了0的数组元素来说已经是a[k+l] 了，因此正确的条件为 "a[k-l]!=0"。
第 3 题
（共15 分）
阅读以下说明和C 函数，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
基于管理的需要，每本正式出版的图书都有一个 ISBN 号。例如，某图书的 ISBN号为“978-7-5606-2348-1”。
ISBN 号由 13 位数字组成：前三位数字代表该出版物是图书（前缀号），中间的 9个数字分为三组，分别表示组号、出版者号和书名号，最后一个数字是校验码。其中，前缀号由国际EAN提供，已经采用的前缀号为978和979；组号用以区别出版者国家、地区或者语言区，其长度可为1～5位；出版者号为各出版者的代码，其长度与出版者的计划出书量直接相关；书名号代表该出版者该出版物的特定版次；校验码采用模10加权的算法计算得出。
校验码的计算方法如下：
第一步：前 12 位数字中的奇数位数字用 1 相乘，偶数位数字用 3 相乘（位编号从左到右依次为13到2）；
第二步：将各乘积相加，求出总和S；
第三步：将总和S 除以10，得出余数R；
第四步：将10减去余数R后即为校验码V。若相减后的数值为10，则校验码为0。
例如，对于ISBN 号“978-7-5606-2348-1”，其校验码为1，计算过程为：
S=9×1+7×3+8×1+7×3+5×1+6×3+0×1+6×3+2×1+3×3+4×1+8×3=139
R = 139 mod 10 = 9
V = 10 – 9 = 1
函数check(char code[])用来检查保存在code中的一个ISBN号的校验码是否正确，若正确则返回 true，否则返回 false。例如，ISBN 号“978-7-5606-2348-1”在 code 中的存储布局如表3-1所示（书号的各组成部分之间用“-”分隔）：
在函数check(char code[])中，先将13位ISBN号放在整型数组元素tarr[0]～tarr[12]中（如表3-2 所示，对应 ISBN 号的位13～位 1），由 tarr[0]～tarr[11]计算出校验码放入变量V，再进行判断。
【C 函数】
bool check(char code[ ])
{
int i,k = 0;
int S = 0 ，temp = 0;
int V ;
int tarr[13]={0};
if (strlen(code) < 17) return false;
for( i=0; i<17 ; i++ ) /将 13位 ISBN 号存入 tarr /
if ( code [i] != '- ' )
tarr[ （1） ]= code[i] - ' 0 ';
for (i=0;（2）;i++){
if( i%2 )
S += （3） ;
else
S += （4） ;
}
V = ( （5） == 0 )? 0 ： 10 - S %10;
if ( tarr[12] == V)
return true ;
return false;
}
答案与解析
- 试题难度：较难
- 知识点：C程序设计>C程序设计
- 试题答案：（1）k++ ，或temp++
（2）i<12 ，或i< k-1（空（1）处填 k++），或i< temp-1（空（1）处填temp++），或等价形式
（3）tarr[i]3，或(tarr+i)3，或等价形式
（4）tarr[i]，或(tarr+i) ，或等价形式
（5）S%10 ，或等价形式 - 试题解析：本题考查 C程序设计基本技术。
根据题目中的描述，在函数check(char code[]) 中要先将保存在 code中的编码存入tarr，同时根据题例中的 tarr内容示例表可知，ISBN号前12位数字中的奇数位数字会存入tarr的偶数下标，偶数位数字存入 tarr的奇数下标。将 13 位 ISBN 号存入tarr的代码如下所示：
for( i=0; i<17; i++ )
if ( code[i]!= '-' )
tarr[ （1） ] = code[i] - '0';
显然，空（1）处tarr的下标索引值不能使用 i，需要另一个整型变量，题目中提供了 k 和 temp ，因此在此处用k++或 temp++都可以。
空（2）～（4）处所在代码实现校验码的计算方法中的第一步和第二步，由于共需计算 12 位，因此空（2）处填入 "i<12"。算法中规定，ISBN 号前 12 位数字中的奇数位数字用 1 相乘，偶数位数字用 3 相乘，且将各乘积相加求出总和 S。由于在数组tarr 中，ISBN号的奇数位数字对应 tarr的偶数下标、偶数位数字对应 tarr的奇数下标。因此，空（3）处应填入"tarr[i]*3"，空（4）处应填入"tarr[i]"。
校验码计算方法的第三步和第四步是：将总和 S 除以10，得出余数R； 将10减去余数 R后即为校验码V。若相减后的数值为10，则校验码为0。由空（5）处的代码，V 的值要么为 0，要么为10-S%10。显然，校验码为0说明余数 R 为 0 ，即S %10 等于 0 ，因此空（5）处应填入"s %10"。
第 4 题
（共 15 分）
阅读以下说明和C 程序，将应填入（n）处的字句写在答题纸的对应栏内。
【说明】
某旅游服务应用程序运行时，根据输入的两个城市名查找其间的距离。各城市间的距离如表4-1所示。表格中的第一行和第一列表示城市名，表中的每个元素是一个整数，代表该元素所在行和列对应的城市之间的距离（单位：km）。
在程序中，城市名用一维全局数组cityTable存储，城市之间的距离矩阵用二维全局数组kmTable表示，并用相应的值对这两个数组进行初始化。
#define NCities 8 /* 城市个数 */
#define TRUE 1
static char * cityTable[NCities] = { /* 城市名按字典序升序排列 */
"Beijing",
...... /* 其他城市名略去 */
"Sanya",
};
static int kmTable[NCities][NCities] = {
{0, 1697, 2695, 937, 1784, 1356, 926, 2543},
{1697, 0,313, 1840,533, 940, 1409, 1505},
...... /* 剩余元素的初始值略去 */
};
程序执行时，首先按提示输入两个城市名，然后在cityTable中查找与城市名对应的下标，最后用该下标在kmTable中找到这两个城市之间的距离。
程序中定义的函数FindCityInSortedArray和GetCity说明如下：
（1）函数 FindCityInSortedArray 的功能是用二分查找法在全局数组 cityTable 中查找城市名所对应的下标值。
（2）函数GetCity的功能是读入城市名，调用函数FindCityInSortedArray来获取城市所对应的下标值。如果该城市名不存在，则提示用户重新输入。
【C 程序】
int main ( ) {
int city1，city2;
city1 = GetCity("输入第 1个城市名: ") ;
city2 = GetCity("输入第 2 个城市名: ");
printf(" %s 和%s之间的距离为：%d km.\n" ,cityTable[city1] ,
cityTable[city2] ,
kmTable[city1] [city2]);
return 0;
}
static int GetCity(char prompt) {
char • cityName;
int index;
cityName = (char )malloc(20sizeof(char));
while ( TRUE ) {
printf(" %s" ，prompt);
gets(cityName) ; /获取输入字符串/
index = FindCityInSortedArray(cityName);
if ( （1） ) break;
printf(" 城市名不存在，请重新输入。 \n") ;
}
free(cityName);
return （2）;
}
static int FindCityInSortedArray(charkey) {
int lh ，rh ，mid ，cmp;
lh = 0;
rh = NCities - 1;
while ( （3） ) {
mid = (lh + rh) / 2;
cmp = strcmp ( （4） ); /比较两个城市名是否相同/
if (cmp == 0) return （5）; /两个城市名相同/
if (cmp < 0) { rh = mid - 1; }
else { lh = mid + 1; }
}
return (-1); /城市名不存在时返回 -1 /
}
答案与解析
- 试题难度：较难
- 知识点：C程序设计>C程序设计
- 试题答案：（1）index >= 0，或等价形式 （2）index
（3）Ih <= rh ，或等价形式 （4）key，cityTable[mid] 或 key，*(cityTable+mid)
（5）mid - 试题解析：本题考查C语言程序设计基本能力。要求考生根据给出的案例和执行过程说明，认真阅读理清程序思路，然后完成题目。
本题涉及一维和二维数组操作，以及数组上的查找算法。先考察main()函数，理清程序整体结构，在该函数中提示并输入两个城市名，然后输出这两个城市之间的距离。
函数GetCity的功能是读入城市名，调用函数 FindCityInSortedArray来获取城市所对应的下标值 index。如果该城市名不存在，则提示用户重新输入。
函数 FindCityInSortedArray的功能是用二分查找法在全局数组cityTable中查找城市名所对应的下标值。
最后用该下标在kmTable中找到这两个城市之间的距离。
先考查空（1），因为GetCity在 while循环中执行完语句 index = FindCitylnSortedArray(cityName)之后，获得城市对应的下标值 index ，而有效的下标值就是城市名称在数组中的位置下标，所以 index>=0 时说明下标有效，跳出循环。
然后考查空（2），因为程序首先要获得两个城市名称所对应的下标，所以通过 GetCity读入城市名称并获取所对应的下标，然后返回所对应的下标值。此处即为获取到的 index。
接下来考查空（3）、（4）和（5），因为函数FindCityInSortedArray的功能是用二分查找法在全局数组 cityTable中查找城市名所对应的下标值。在已经排序的数组中进行二分查找，在当前数组区域中，如果下界小于上界，则目标元素和中值进行比较，如果相等则返回下标；如果目标元素小于中值元素，则在前半区域（左分支中）继续查找；如果大于中值元素，则在后半区域（右分支中）继续查找。如果最后没有找到所需查找的目标元素，则返回-1。因此，空（3）处填入lh<=rh 以判断下界是否小于上界；（4）处目标元素key 和中值元素 cityTable[mid] ，中值元素的也可以用*(cityTable+mid)表示；（5）处为比较成功时返回所在元素的下标，此处为 mid。
第 5 题
（共15 分）
阅读以下说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
现需要统计某企业员工的月平均工资，即该企业本月发给员工的工资总和除以员工数。假设企业本月发给员工的工资总和为sumSalary，该企业的员工总数为employeeNumber，下面的程序代码计算该企业员工本月的平均工资，其中需要处理employNumber为0的情况。
【C++代码】
#include <iostream>
using namespace std;
class Department{
protected:
float average(float x ，int y) {
if (y = =0) throw （1）;
return x/y;
}
public:
void caculate(void) {
float sumSalary;
int employeeNumber;
try {
cout << "请输入当月工资总和与员工数:" << end1;
cin >> sumSalary >> employeeNumber;
float k=average(sumSalary，employeeNumber);
cout << "平均工资: "<< k << end1;
}
（2）(int e) {
if(e = =0) {
cout << "请重新输入当月工资总和与员工数 :" << end1;
cin >> sumSalary >> employeeNumber;
float k =average(sumSalary,employeeNumber);
cout << "平均工资: "<< k << end1;
}
}
}
};
void main ( ) {
try {
（3）;
d.caculate ( );
}
（4）(int e) {
if ( e = = 0)
cout << "程序未正确计算平均工资! " << end1;
}
}
【问题 1】
程序运行时，若输入的员工工资总和为6000，员工数为5，则屏幕输出为：
请输入当月工资总和与员工数：
6000 5
（5）
【问题 2】
若程序运行时，第一次输入的员工工资总和为6000，员工数为0，第二次输入的员工工资总和为0，员工数为0，则屏幕输出为：
请输入当月工资总和与员工数：
6000 0
（6）
0 0
（7）
答案与解析
- 试题难度：较难
- 知识点：C++程序设计>C++程序设计
- 试题答案：（1）0，或y
（2）catch
（3）Department d
（4）catch
（5）平均工资：1200.0
（6）请重新输入当月工资总和与员工数：
（7）程序未正确计算平均工资! - 试题解析：本题考查c++程序设计语言中结构化异常的错误处理机制。要正确解答该题目，需要掌握 c++中try..catch..fmal1y 与 exception的概念与用法。
一般而言，try语句块中编写正常工作的语句，catch语句块中主要编写用于处理异常情况发生时的语句，而final1y块中则包含不论是否发生异常都需要执行的语句。
本题中，Department 类包含了一个受保护的方法 average ，用于计算参数x除以 y的值，在计算的过程中，如果 y 等于 0，则会抛出一个异常，空（1）处仅仅根据average本身无法判断异常的值与类型。因为 Department 类的 caculate 方法调用了average方法，并且在使用的过程中，需要捕获average方法产生的异常，空（2）处首先需要填写关键字catch，另外因为其捕获的异常类型为整型，因此，空（1）处应该抛出一个整型值，但在代码的逻辑判读中，判断的是e是否为 0的情况，因此空（1）处应该抛出 0或者 y值。
main方法中又使用了Department 类的 caculate方法，在使用变量 d 之前必须声明和定义，所以空（3）处应该为Departrnent d。空（4）处仍然填写 catch关键字。
若输入的数据为6000和5，则整个程序能够计算出其平均值为 1200，并且输出 caculate 中的输出语句，结果为"平均工资：1200.0"。若输入的数据为6000和 0，则程序中 caculate方法中的 catch语句会首先捕获到average抛出的异常，要求重新输入数据，并再次调用 average方法，由于输入的数据为 0和 0，所以average会再次抛出异常，这个异常将由 main方法中的 catch捕获。
第 6 题
（共 15 分）
阅读以下说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
现需要统计某企业员工的月平均工资，即该企业本月发给员工的工资总和除以员工人数。假设企业本月发给员工的工资总和为sumSalary，该企业的员工总数为employeeNumber，下面的程序代码计算该企业员工本月的平均工资，其中需要处理employNumber为0的情况。
【Java 代码】
irnport java.util.Scanner;
pub1ic c1ass JavaMain {
static float average(float x ，int y) throws Exception{
if (y = =0 ) throw new Exception( （1） );
return x/y;
}
static void cacu1ate( ) throws Exception{
float surnSa1ary;
int employeeNumber;
Scanner sc =new Scanner ( （2） ) ;
try{
System.out.println(" 请输入当月工资总和与员工数: ");
surnSalary=sc.nextFloat( ); //从标准输入获得工资总和
employeeNumber= sc.nextInt ( ) ; //从标准输入获得员工数
float k = average(surnSa1ary ，employeeNumber);
System.out.println(" 平均工资: " + k);
}
（3） (Exception e) {
if (e. getMessage ( ) .equalsIgnoreCase ("zero") ) {
System.out.println(" 请重新输入当月工资总和与员工数: ");
sumSa1ary = sc.nextFloat( );
employeeNumber = sc.nextInt( );
float k = average(surnSa1ary ，employeeNumber);
System.out.println(" 平均工资: " + k);
}
}
}
pub1ic static void main(String[ ] args) {
try {
caculate ( ) ;
}
（4） (Exception e) {
if ( e.getMessage( ) .equalsIgnoreCase(“zero”))
System.out.println(" 程序未正确计算平均工资! " );
}
}
}
【问题 1】
程序运行时，若输入的员工工资总和为6000，员工数为5，则屏幕输出为：
请输入当月工资总和与员工数：
6000 5
（5）
【问题 2】
若程序运行时，第一次输入的员工工资总和为6000，员工数为0，第二次输入的员工工资总和为0，员工数为0，则屏幕输出为：
请输入当月工资总和与员工数：
6000 0
（6）
0 0
（7）
答案与解析
- 试题难度：较难
- 知识点：Java程序设计>Java程序设计案例
- 试题答案：（1）"zero" （不区分大小写） （2）System.in （3）catch （4）catch
（5）平均工资：1200.0 （6）请重新输入当月工资总和与员工数：
（7）程序未正确计算平均工资! - 试题解析：本题考查 Java 程序设计语言中结构化异常的错误处理机制。要正确解答该题目，需要掌握 Java 中try…catch...finally与 exception的概念与用法。
一般而言，try语句块中编写的是正常工作的语句，catch语句块中主要编写的是用于处理异常情况发生时的语句，而 finally块包含不论是否发生异常都需要执行的语句。
本题中，JavaMain类包含了一个静态的方法average，用于计算参数x 除以 y 的值，在计算的过程中，如果y等于 0，则会抛出一个异常，空（1）处仅仅根据average本身无法判断异常所包含的信息。因为 caculate方法调用了average方法，并且在使用的过程中，需要捕获 average方法产生的异常，空（3）处首先需要填写关键字catch，另外因为其捕获异常后判断其值为"zero"，因此，空（1）处应该填写一个字符串"zero"。空（2）处需要构造一个扫描器对象，该对象需要一个输入流作为参数，因此可以使用System.in。main 方法中调用了caculate方法，空（4）处仍然填写 catch 关键字。
程序运行的过程中，若输入的数据为6000 和 5，则整个程序能够计算出其平均值为 1200，并且执行caculate 中的输出语句，结果为"平均工资：1200.0"。若输入的数据为 6000 和 0，则程序中caculate方法中的 catch语句会首先捕获到 average抛出的异常，要求重新输入数据，并再次调用 average方法，由于输入的数据为 0 和 0 ，所以average会再次抛出异常，这个异常将由 main方法中的 catch捕获。