全国计算机技术与软件专业技术资格（初级程序员2008下半年下午试题）

第2章 程序员下午试题

试题一

阅读以下说明和流程图，填补流程图中的空缺(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)等逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，依此类推。 【流程图】

试题二

阅读以下说明和C程序代码，将应填入 (n) 处的字句写在对应栏内。 【说明】

下面C程序代码的功能是：对于输入的一个正整数n(100≤n＜1000)，先判断其是否是回文数(正读反读都一样的数)。若不是，则将n与其反序数相加，再判断得到的和数是否为回文数，若还不是，再将该和数与其反序数相加并进行判断，依此类推，直到得到一个回文数为止。例如，278不是回文数，其反序数为872，相加后得到的1150还不是回文数，再将1150与其反序数511相加，得到的1661是回文数。 函数int isPalm(long m)的功能是：将正整数m的各位数字取出存入数组中，然后判断其是否为回文数。若m是回文数则返回1，否则返回0。 【C程序代码】 #include ＜stdio.h＞ #include ＜stdlib.h＞ int isPalm(long m)

1

{ /*判断m是否为回文数*/ int i = 0, k = 0;

char str[32];

while (m ＞ 0) { /*从个位数开始逐个取出m的各位数字并存入字符数组str*/ str[k++] = (1) + '0'; m = m / 10; }

for(i = 0; i ＜ k/2; i++) /*判断str中的k个数字字符序列是否是回文*/ if ( str[i] != str[ (2) ] ) return 0; return 1; }

int main ( ) {

long n, a, t;

printf(\ scanf(\if (n ＜ 100 || n ＞ =1000) return -1 ;

while( (3) ) { /*n不是回文数时执行循环*/ printf(\＞ \ n);

for(a = 0, t = n; t ＞ 0; ) { /*计算n的反序数并存入a*/ a = (4) *10 + t % 10; t = t / 10; } /*end of for*/

n = (5) ; /*与反序数求和*/ } /*end of while*/ printf (\

system(\ return 0; }

试题三

阅读以下说明和C函数，将应填入 (n) 处的字句写在对应栏内。 【说明】

已知某二叉树的非叶子结点都有两个孩子结点，现将该二叉树存储在结构数组Ht中。结点结构及数组Ht的定义如下：

#define MAXLEAFNUM 30 struct node{

char ch; /*当前结点表示的字符，对于非叶子结点，此域不用*/ char *pstr; /*当前结点的编码指针，非叶子结点不用*/ int parent; /*当前结点的父结点，为0时表示无父结点*/ int lchild,rchild;

/*当前结点的左、右孩子结点，为0时表示无对应的孩子结点*/ };

struct node Ht[2*MAXLEAFNUM]; /*数组元素Ht[0]不用*/

该二叉树的n个叶子结点存储在下标为1～n的Ht数组元素中。例如，某二叉树如果其存储结构如下图所示，其中，与叶子结点a对应的数组元素下标为1，a的父结点存储在Ht[5]，表示为Ht[1].parent=5。Ht[7].parent=0表示7号结点是树根，Ht[7].child=3、 Ht[7].rchild=6分别表示7号结点的左孩子是3号结点、

2

右孩子是6号结点。

如果用0或1分别标识二叉树的左分支和右分支(如上图所示)，从根结点开始到叶子结点为止，按所经过分支的次序将相应标识依次排列，可得到一个0、1序列，称之为对应叶子结点的编码。例如，上图中a，b，c，d的编码分别是100，101，0，11。

函数LeafCode(Ht[],n)的功能是：求解存储在Ht中的二叉树中所有叶子结点(n个)的编码，叶子结点存储在Ht[1]～Ht[n]中，求出的编码存储区由对应的数组元素pstr域指示。 函数LeafCode从叶子到根逆向求叶子结点的编码。例如，对上图中叶子结点a求编码的过程如下图所示。

typedef enum Status {ERROR,OK} Status; 【C函数】

Status LeafCode(struct node Ht[], int n) {

int pc, pf; /*pc用于指出树中的结点，pf则指出pc所对应结点的父结点*/ int i,start;

char tstr[31] = {'\\0'}; /*临时存储给定叶子结点的编码，从高下标开始存入*/

for(i = 1; (1) ; i++){ /*对所有叶子结点求编码，i表示叶结点在HT数组中的下标*/

3

start = 29;

pc = i; pf = Ht[i].parent;

while (pf != (2) ) { /*没有到达树根时，继续求编码*/

if ( (3) .lchild == pc ) /*pc所表示的结点是其父结点的左孩子*/ tstr[--start] = '0'; else

tstr[--start] = '1';

pc = (4) ; pf = Ht[pf].parent; /*pc和pf分别向根方向回退一层*/ }/* end of while */

Ht[i].pstr = (char *) malloc(31-start); if (!Ht[i].pstr) return ERROR; strcpy(Ht[i].pstr, (5) ); }/* end of for */ return OK;

}/* and of LeafCode */ 试题四

阅读以下说明和C函数代码，回答问题并将解答写在对应栏内。 【说明】

著名的菲波那契数列定义式为

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函数代码】

【问题1】

函数fib1和fib2存在错误，只需分别修改其中的一行代码即可改正错误。

(1)函数fib1不能通过编译，请写出fib1中错误所在行修改正确后的完整代码。

(2)函数fib2在n≤2时不能获得正确结果，请写出fib2中错误所在行修改正确后的完整代码。 【问题2】

将函数fib1和fib2改正后进行测试，发现前46项都正确，而第47项的值是一个负数，请说明原因。 【问题3】

函数fib1、fib2求得菲波那契数列第n项(n＞40)的速度并不相同，请指出速度慢的函数名，并简要说明原因。

试题五（选择java可不做）

阅读以下说明和C++代码，将应填入 (n) 处的字句写在对应栏内。

4