程序员-3期（PX014） 初级程序员2009上半年试题及解答 初级程序员2009年上半年下午试题.doc

全国计算机技术与软件专业技术资格（水平）考试 2009年上半年 程序员 下午试卷 （考试时间 14 : 00～16 : 30 共150分钟） 请按下述要求正确填写答题卡 在答题纸的指定位置填写你所在的省、自治区、计划单列市和名称。 在答题纸的指定位置填写准考证号、出生年月日和姓名。 答题纸上除填写上述内容外只能写解答。 本试卷共6道题。试题一至试题四是必答题目，试题五至试题六选答1道。 每题15分，满分75分。 试题号 一~四 五~六 选择方法 必答题 选答一题 5．解答时字迹务必清楚，字迹不清时，将不评分。 依照下面例题，将解答写在答题纸对应的栏内。 例题 2001年下半年全国计算机技术与软件专业技术资料（水平）考试日期是（1）月（2）日。 因为正确的解答是“11月13日”，故在答题纸的对应栏内写上“11月13日”（参看下表）。 例题 解答栏 （1） 11 （2） 13 试题一（共15分） 阅读以下说明和流程图，填补流程图中的空缺（1）～（5），将解答填入答题纸的对应栏内。 【说明】 下面的流程图采用公式ex=1+x+x2/2!+x3/3!+x4/4!+…+xn/n!+…计算的ex近似值。 设x位于区间 （0,1）， 该流程图的算法要点是逐步累积计算每项Xn/n!的值 （作为T），再逐步累加T 值得到所需的结果S。当T 值小于10-5 时，结束计算。 【流程图】 试题二（共15分） 阅读以下说明和C函数，将应填入______处的字句写在答题纸的对应栏内。　　【说明】　　C 语言常用整型（int）或长整型（long）来说明需要处理的整数，在一般情况下可以满足表示及运算要求，而在某些情况下，需要表示及运算的整数比较大，即使采用更长的整型（例如，long long类型，某些C系统会提供）也无法正确表示，此时可用一维数组来表示一个整数。　　假设下面要处理的大整数均为正数，将其从低位到高位每4位一组进行分组（最后一组可能不足4位），每组作为1个整数存入数组。例如，大整数2543698845679015847在数组A 中的表示如下（特别引入-1表示分组结束）： 在上述表示机制下，函数add_large_number(A,B,C)将保存在一维整型数组A和B中的两个大整数进行相加，结果（和数）保存在一维整型数组C 中。　　【C 函数】　　void add_large_number(int A[], int B[], int C[])　　{　　int i, cf ;????????????????? /*cf存放进位*/　　int t, *p;????????????????? /*t为临时变量，p为临时指针*/　　cf =???? （1）??? ;　　for(i = 0; A[i]-1 B[i]-1; i++) {　　/*将数组A、B 对应分组中的两个整数进行相加*/　　t =???? （2）??? ;　　C[i] = t % 10000;　　cf =???? （3）??? ;　　}　　if (???? （4）????? )??? p = B;　　else??? p = A;　　for( ; p[i]-1; i++) {????????? /*将分组多的其余各组整数带进位复制入数组C*/　　C[i] = (p[i] + cf) %10000;??? cf = (p[i] + cf) /10000;　　}　　if ( cf 0 )????? C[i++] = cf;　　（5）????? = -1;??????????????? /*标志和数的分组结束*/　　} 试题三（共15分）　　阅读以下说明、C 函数和问题，将解答填入答题纸的对应栏内。　　【说明】　　二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：　　● 若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；　　● 若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；　　● 左、右子树本身就是二叉查找树。 　　设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：　　typedef struct BiTnode{　　int??? key_value;?????????????????? /*结点的键值，为非负整数*/　　struct BiTnode *left,*right;??????????? /*结点的左、右子树指针*/　　}*BSTree;　　函数find_key(root, key)的功能是用递归方式在给定的二叉查找树 （root指向根结点）中查找键值为key的结点并返回结点的指针；若找不到，则返回空指针。　　【C函数】　　BSTree f