1、计算机水平考试初级程序员 2008 年下半年下午真题及答案解析(总分：105.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明】 下面流程图的功能是：在已知字符串 A 中查找特定字符串 B，如果存在，则输出 B 串首字符在 A 串中的位置，否则输出-1。设串 A 由 n 个字符 A(0)，A(1)，A(n-1)组成，串 B 由 m 个字符 B(0)，B(1)，B(m-1)组成，其中 nm0。在串 A 中查找串 B 的基本算法如下：从串 A 的首字符 A(0)开始，取子串 A(0)A(1)A(m-1)与串 B 比较；若不同，则再取子串 A(1)A(2)A(m
2、)与串 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)等逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，依此类推。 【流程图】 （分数：15.00）_二、B试题二/B(总题数：1，分数：15.00)2.【说明】 下面 C 程序代码
3、的功能是：对于输入的一个正整数 n(100n1000)，先判断其是否是回文数(正读反读都一样的数)。若不是，则将 n 与其反序数相加，再判断得到的和数是否为回文数，若还不是，再将该和数与其反序数相加并进行判断，依此类推，直到得到一个回文数为止。例如，278 不是回文数，其反序数为 872，相加后得到的 1150 还不是回文数，再将 1150 与其反序数 511 相加，得到的 1661 是回文数。 函数 int isPalm(long m)的功能是：将正整数 m 的各位数字取出存入数组中，然后判断其是否为回文数。若 m 是回文数则返回 1，否则返回 0。 【C 程序代码】 #include st
4、dio.h #include stdlib.h int isPalm(long m) /*判断 m 是否为回文数*/ int i = 0, k = 0; char str32; while (m 0) /*从个位数开始逐个取出 m 的各位数字并存入字符数组 str*/ strk+ = U(1) /U + 0; m = m / 10; for(i = 0; i k/2; i+) /*判断 str 中的 k 个数字字符序列是否是回文*/ if ( stri != strU (2) /U ) return 0; return 1; int main ( ) long n, a, t; printf(
5、“input a positive integer:“); scanf(“%ld“, if (n 100 | n =1000) return -1 ; while(U (3) /U) /*n 不是回文数时执行循环*/ printf(“%ld- “, n); for(a = 0, t = n; t 0; ) /*计算 n 的反序数并存入 a*/ a = U(4) /U*10 + t % 10; t = t / 10; /*end of for*/ n =U (5) /U; /*与反序数求和*/ /*end of while*/ printf (“%id/n“,n); system(“pause“
6、); return 0; （分数：15.00）_三、B试题三/B(总题数：1，分数：15.00)3.【说明】 已知某二叉树的非叶子结点都有两个孩子结点，现将该二叉树存储在结构数组 Ht 中。结点结构及数组 Ht 的定义如下： #define MAXLEAFNUM 30 struct node char ch; /*当前结点表示的字符，对于非叶子结点，此域不用*/ char *pstr; /*当前结点的编码指针，非叶子结点不用*/ int parent; /*当前结点的父结点，为 0 时表示无父结点*/ int lchild,rchild; /*当前结点的左、右孩子结点，为 0 时表示无对应的孩
7、子结点*/ ; struct node Ht2*MAXLEAFNUM; /*数组元素 Ht0不用*/ 该二叉树的 n 个叶子结点存储在下标为 1n 的 Ht 数组元素中。例如，某二叉树如果其存储结构如下图所示，其中，与叶子结点 a 对应的数组元素下标为 1，a 的父结点存储在 Ht5，表示为 Ht1.parent=5。Ht7.parent=0表示 7 号结点是树根，Ht7.child=3、Ht7.rchild=6 分别表示 7 号结点的左孩子是 3 号结点、右孩子是 6 号结点。 如果用 0 或 1 分别标识二叉树的左分支和右分支(如上图所示)，从根结点开始到叶子结点为止，按所经过分支的次序将
8、相应标识依次排列，可得到一个 0、1 序列，称之为对应叶子结点的编码。例如，上图中 a，b，c，d 的编码分别是 100，101，0，11。 函数 LeafCode(Ht,n)的功能是：求解存储在 Ht 中的二叉树中所有叶子结点(n 个)的编码，叶子结点存储在 Ht1Htn中，求出的编码存储区由对应的数组元素 pstr 域指示。 函数 LeafCode 从叶子到根逆向求叶子结点的编码。例如，对上图中叶子结点 a 求编码的过程如下图所示。 （分数：15.00）_四、B试题四/B(总题数：1，分数：15.00)阅读以下说明和 C 函数代码，回答问题并将解答写在对应栏内。【说明】著名的菲波那契数列定
9、义式为f1=1 f2=1 fn=fn-1+fn-2 (n=3，4，)因此，从第 1 项开始的该数列为 1，1，2，3，5，8，13，21，。函数 fibl 和 fib2 分别用递归方式和迭代方式求解菲波那契数列的第 n 项(调用 fib1、fib2 时可确保参数 n 获得一个正整数)。【C 函数代码】（分数：15.00）(1).【问题 1】函数 fib1 和 fib2 存在错误，只需分别修改其中的一行代码即可改正错误。(1)函数 fib1 不能通过编译，请写出 fib1 中错误所在行修改正确后的完整代码。(2)函数 fib2 在 n2 时不能获得正确结果，请写出 fib2 中错误所在行修改正确
10、后的完整代码。（分数：5.00）_(2).【问题 2】将函数 fib1 和 fib2 改正后进行测试，发现前 46 项都正确，而第 47 项的值是一个负数，请说明原因。（分数：5.00）_(3).【问题 3】函数 fib1、fib2 求得菲波那契数列第 n 项(n40)的速度并不相同，请指出速度慢的函数名，并简要说明原因。（分数：5.00）_五、B试题五/B(总题数：1，分数：15.00)4.【应用说明】本应用运行时，由用户输入一个正整数 n 后自动产生 n 个正整数，然后按照用户的指定要求对该组数进行处理。该应用的运行界面如下图所示：（分数：15.00）_六、B试题六/B(总题数：1，分数：
11、15.00)5.【说明】C+标准模板库中提供了 vector 模板类，可作为动态数组使用，并可容纳任意数据类型，其所属的命名空间为 std。vector 模板类的部分方法说明如下表所示： 方 法 含 义push_back(k) 向 vector 对象的尾部添加一个元素 kbegin() 返回一个迭代器对象，该对象指向 vector 中的第一个元素end() 返回一个迭代器对象，该对象指向 vector 中的最后一个元素empty() 测试 vector 对象是否为空erase(ptr) 删除 vector 中 ptr 指向的元素【C+代码】#include iostream#include v
12、ectorusing namespace U(1) /U;typedef vectorU (2) /U INTVECTOR;const int ARRAY_SIZE = 6;void ShowVector (INTVECTOR int main() INTVECTOR theVector;/ 初始化 theVector, 将 theVector 的元素依次设置为 0 至 5for (int cEachItem = 0; cEachItem ARRAY_SIZE; cEachItem+theVector.push_back(U (3) /U);ShowVector(theVector); / 依
13、次输出 theVector 中的元素theVector.erase (theVector.begin () + 3;ShowVector(theVector);void ShowVector (INTVECTOR return;INTVECTOR:iterator U(4) /U;for (theIterator=theVector.begin(); theIterator !=theVector.end(); theIterator+) cout *theIterator;if (theIterator != theVector.end()-1) cout “, “;cout end1;该程
14、序运行后的输出结果为：0，1，2，3，4，5U (5) /U（分数：15.00）_七、B试题七/B(总题数：1，分数：15.00)6.【说明】java.util 库中提供了 Vector 模板类，可作为动态数组使用，并可容纳任意数据类型。该类的部分方法说明如下表所示： 方法名 含 义add(k) 向 vector 对象的尾部添加一个元素 kremoveElementAt(i) 删除序号为 i 的元素(vector 元素序号从 0 开始)isEmpty() 判断 vector 对象是否含有元素size() 返回 vector 对象中所包含的元素个数【Java 代码】import U(1) /U;
15、public class JavaMain static private final int U(2) /U = 6;public static void main(String args)VectorInteger theVector = new VectorU (3) /U();/ 初始化 theVector, 将 theVector 的元素设置为 0 至 5for (int cEachItem = 0; cEachItem ARRAY_SIZE; cEachItem+)theVector.add(U (4) /U);showVector(theVector); / 依次输出 theVec
16、tor 中的元素theVector.removeElementAt(3);showVector(theVector);public static void showVector(VectorInteger theVectorif (theVector.isEmpty() System.out.println(“theVectcr is empty.“);return;for (int loop = 0; loop theVector.size(); loop+)System.out.print(theVector.get(loop);System.out.print(“, “);System.
17、out.println();该程序运行后的输出结果为：0，1，2，3，4，5U (5) /U（分数：15.00）_计算机水平考试初级程序员 2008 年下半年下午真题答案解析(总分：105.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明】 下面流程图的功能是：在已知字符串 A 中查找特定字符串 B，如果存在，则输出 B 串首字符在 A 串中的位置，否则输出-1。设串 A 由 n 个字符 A(0)，A(1)，A(n-1)组成，串 B 由 m 个字符 B(0)，B(1)，B(m-1)组成，其中 nm0。在串 A 中查找串 B 的基本算法如下：从串 A 的首字
18、符 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)等逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，依此类推。 【
19、流程图】 （分数：15.00）_正确答案：()解析：(1) j+1 (2) i+1 (3) 0 (4) i (5) -1 分析 本题采用的是最简单的字符子串查找算法。 在串A 中查找是否含有串 B，通常是在串 A 中从左到右取逐个子串与串 B 进行比较。在比较子串时，需要从左到右逐个字符进行比较。 题中已设串 A 的长度为 n，存储数组为 A，动态指针标记为 i；串 B 的长度为m，存储数组为 B，动态指针标记为 j。 如果用伪代码来描述这种算法的核心思想，则可以用以下的两重循环来说明。 外循环为： For i=0 to n-m do A(i)A(i+1).A(i+m-1)B(0)B(1).B
20、(m-1) 要实现上述比较，可以采用内循环： For j=0 to m-1 do A(i+j)B(j) 将这两重循环合并在一起就是： For i = 0 to n-1 do For j = 0 to m-1 do A(i+j)B(j) 这两重循环都有一个特点：若发现比较的结果不相同时，就立即退出循环。因此，本题中的流程图可以间接使用循环概念。 初始时，i 与 j 都赋值 0，做比较A(i+j)B(j)。 若发现相等，则继续内循环(走图的左侧)，j 应该增 1，继续比较，直到 j=m 为止，表示找到了子串(应输出子串的起始位置 i)；若发现不等，则退出内循环，继续开始外循环(走图的右侧)，j应恢
21、复为 0，i 应增 1，继续比较，直到 in-m 为止，表示不存在这样的子串(输出-1)。 在设计流程图时，主要的难点是确定循环的边界(何时开始，何时结束)。当难以确定边界值变量的正确性时，可以用具体的数值之例来验证。这是程序员应具备的基本素质。二、B试题二/B(总题数：1，分数：15.00)2.【说明】 下面 C 程序代码的功能是：对于输入的一个正整数 n(100n1000)，先判断其是否是回文数(正读反读都一样的数)。若不是，则将 n 与其反序数相加，再判断得到的和数是否为回文数，若还不是，再将该和数与其反序数相加并进行判断，依此类推，直到得到一个回文数为止。例如，278 不是回文数，其反
22、序数为 872，相加后得到的 1150 还不是回文数，再将 1150 与其反序数 511 相加，得到的 1661 是回文数。 函数 int isPalm(long m)的功能是：将正整数 m 的各位数字取出存入数组中，然后判断其是否为回文数。若 m 是回文数则返回 1，否则返回 0。 【C 程序代码】 #include stdio.h #include stdlib.h int isPalm(long m) /*判断 m 是否为回文数*/ int i = 0, k = 0; char str32; while (m 0) /*从个位数开始逐个取出 m 的各位数字并存入字符数组 str*/ st
23、rk+ = U(1) /U + 0; m = m / 10; for(i = 0; i k/2; i+) /*判断 str 中的 k 个数字字符序列是否是回文*/ if ( stri != strU (2) /U ) return 0; return 1; int main ( ) long n, a, t; printf(“input a positive integer:“); scanf(“%ld“, if (n 100 | n =1000) return -1 ; while(U (3) /U) /*n 不是回文数时执行循环*/ printf(“%ld- “, n); for(a =
24、0, t = n; t 0; ) /*计算 n 的反序数并存入 a*/ a = U(4) /U*10 + t % 10; t = t / 10; /*end of for*/ n =U (5) /U; /*与反序数求和*/ /*end of while*/ printf (“%id/n“,n); system(“pause“); return 0; （分数：15.00）_正确答案：()解析：(1) m%10，或其等价表示 (2) k-1-i (3) !isPalm(n)，或 isPalm(n)!=1，或 isPalm(n)= =0 (4) a (5) n+a 分析 本题考查 C 程序设计的基本
25、能力。 函数 isPalm(long m)的功能是判断 m 是否为回文数，其方法是先将 m 的各位数字依次取出转换为对应的数字字符保存在数组 str 中，然后再判断 str 中的字符序列是否对称。代码如下： while (m0) /*从个位数开始逐个取出 m 的各位数字并存入字符数组str*/ strk+ = m % 10 + 0; m=m/10; 因此，空(1)处应填入“m%10“，将数 m 的个位数字取出。以上 while 循环结束时，k 的值即为 m 取初始值时的位数。 若需判断 str0、str1、strk-1中的 k 个数字字符序列是否对称，则应依次比较 str0与 strk-1、s
26、tr1与 strk-2、strk/2-1与strk2+1是否相等，若都相等，则是回文数；若其中有一处不等，则不是回文数。代码如下： for(i=0; ik/2; i+) if ( stri !=strU (2) /U ) return 0; 因此，空(2)处应填入“k-1-i”。 根据题目描述，从最初输入的数开始，直到得到一个回文数时结束，因此对于数 n，调用函数 is Palm(n)，根据返回值确定 n 是否为一个回文数，空(3)处应填入“!isPalm(n)”。 为了求一个数 t 的反序数，可从其个位数字开始，依次取出其各位数字并进行组合。下面以 t=345 举例说明通过整除取余“%”、整
27、除“/”取出各位数字并组合出 543 的过程。 初始时：a=0 t=345 下一步：345%10=5 a*10+5=a=5 t/10=345/10=t=34 下一步：34%10=4 a*10+4=a=54 t/10=34/10=t=3 下一步：3%10=3 a*10+3=a=543 t/10=3/10=t=0 因此，可知空(4)处应填入“a”。 最后数 n 与其反序数 a 相加得到新的数，继续产生回文数的过程。空(5)处应填入“n+a”。三、B试题三/B(总题数：1，分数：15.00)3.【说明】 已知某二叉树的非叶子结点都有两个孩子结点，现将该二叉树存储在结构数组 Ht 中。结点结构及数组
28、Ht 的定义如下： #define MAXLEAFNUM 30 struct node char ch; /*当前结点表示的字符，对于非叶子结点，此域不用*/ char *pstr; /*当前结点的编码指针，非叶子结点不用*/ int parent; /*当前结点的父结点，为 0 时表示无父结点*/ int lchild,rchild; /*当前结点的左、右孩子结点，为 0 时表示无对应的孩子结点*/ ; struct node Ht2*MAXLEAFNUM; /*数组元素 Ht0不用*/ 该二叉树的 n 个叶子结点存储在下标为 1n 的 Ht 数组元素中。例如，某二叉树如果其存储结构如下图所
29、示，其中，与叶子结点 a 对应的数组元素下标为 1，a 的父结点存储在 Ht5，表示为 Ht1.parent=5。Ht7.parent=0表示 7 号结点是树根，Ht7.child=3、Ht7.rchild=6 分别表示 7 号结点的左孩子是 3 号结点、右孩子是 6 号结点。 如果用 0 或 1 分别标识二叉树的左分支和右分支(如上图所示)，从根结点开始到叶子结点为止，按所经过分支的次序将相应标识依次排列，可得到一个 0、1 序列，称之为对应叶子结点的编码。例如，上图中 a，b，c，d 的编码分别是 100，101，0，11。 函数 LeafCode(Ht,n)的功能是：求解存储在 Ht 中
30、的二叉树中所有叶子结点(n 个)的编码，叶子结点存储在 Ht1Htn中，求出的编码存储区由对应的数组元素 pstr 域指示。 函数 LeafCode 从叶子到根逆向求叶子结点的编码。例如，对上图中叶子结点 a 求编码的过程如下图所示。 （分数：15.00）_正确答案：()解析：(1) i=n，或其等价表示 (2) 0 (3) Htpf，或(*(Ht+pf) (4) pf (5) typedef vectorU (2) /U INTVECTOR;const int ARRAY_SIZE = 6;void ShowVector (INTVECTOR int main() INTVECTOR the
31、Vector;/ 初始化 theVector, 将 theVector 的元素依次设置为 0 至 5for (int cEachItem = 0; cEachItem ARRAY_SIZE; cEachItem+theVector.push_back(U (3) /U);ShowVector(theVector); / 依次输出 theVector 中的元素theVector.erase (theVector.begin () + 3;ShowVector(theVector);void ShowVector (INTVECTOR return;INTVECTOR:iterator U(4)
32、/U;for (theIterator=theVector.begin(); theIterator !=theVector.end(); theIterator+) cout *theIterator;if (theIterator != theVector.end()-1) cout “, “;cout end1;该程序运行后的输出结果为：0，1，2，3，4，5U (5) /U（分数：15.00）_正确答案：()解析：(1) std (2) int (3) cEachItem (4) theIterator (5) 0,1,2,4,5 分析 本题主要考查 C+语言的基本使用以及类库的应用。
33、 在使用标准 C+库中所提供的对象时，一般需要引用标准的命名空间。所以空(1)需要填入标准的命名空间 std。空(2)处主要考查是否会使用 C+提供的模板类。C+中 Vector模板类可存储任意类型，在定义 Vector 模板类的对象时，需要指定 Vector 对象的类型。从后面的代码可以看出，Vector 被用于存储整型数，所以，空(2)处应填写整型血。初始化代码将 0 到 5 共 6 个整数存储到 theVector 对象中，所以，空(3)处将循环变量的值存入 theVector 中。空(4)处代码部分主要是循环输出 theVector 对象的内容，使用了迭代器的访问方式，因此空(4)处应
34、该为定义迭代器变量，在后续的循环中使用该变量。程序运行时将首先输出 0 至 5，其次会删除第 3 个元素，再次输出时将不再包含整数3。七、B试题七/B(总题数：1，分数：15.00)6.【说明】java.util 库中提供了 Vector 模板类，可作为动态数组使用，并可容纳任意数据类型。该类的部分方法说明如下表所示： 方法名含 义add(k)向vector对象的尾部添加一个元素 kremoveElementAt(i)删除序号为 i的元素(vector元素序号从 0开始)isEmpty()判断vector对象是否含有元素size()返回vector对象中所包含的元素个数【Java 代码】imp
35、ort U(1) /U;public class JavaMain static private final int U(2) /U = 6;public static void main(String args)VectorInteger theVector = new VectorU (3) /U();/ 初始化 theVector, 将 theVector 的元素设置为 0 至 5for (int cEachItem = 0; cEachItem ARRAY_SIZE; cEachItem+)theVector.add(U (4) /U);showVector(theVector); /
36、 依次输出 theVector 中的元素theVector.removeElementAt(3);showVector(theVector);public static void showVector(VectorInteger theVectorif (theVector.isEmpty() System.out.println(“theVectcr is empty.“);return;for (int loop = 0; loop theVector.size(); loop+)System.out.print(theVector.get(loop);System.out.print(“
37、, “);System.out.println();该程序运行后的输出结果为：0，1，2，3，4，5U (5) /U（分数：15.00）_正确答案：()解析：(1) java.util.Vector，或 java.util.* (2) ARRAY_SIZE (3) Integer (4) cEachItem (5) 0,1,2,4,5 分析 本题主要考查 Java 语言的基本使用和类库的应用。 在使用 Java 库中所提供的类时，一般需要导入该类库所处的包。所以，空(1)需要填入 Vector 类所在的包。空(2)处主要考查变量在使用前需要先定义的基本概念，后续的代码中使用了 ARRAY_SIZE 变量，但其使用前没有定义，因此，空(2)处应该为该变量的定义。Java 中 Vector 模板类可存储任意类型，在定义 Vector 模板类的对象时，需要指定 Vector 对象的类型。从后面的代码可以看出，Vector 被用于存储整型数，所以，空(3)处应填写整型。初始化代码将 0 到 5 共 6 个整数存储到 theVector 对象中，所以，空(4)处将循环变量的值存入theVector 中。程序运行时将首先输出 0 至 5，其次会删除第 3 个元素，再次输出时将不再包含整数 3。
