1、计算机软件专业技术资格和水平考试二 000 年度程序员级 上午试卷（考试时间 9：0011：30 共 150 分钟）请按下述要求正确填写答卷，若不按下述要求解答，将不给分数1 本试卷的 15 道试题都是必答题，请全部解答。每题 5 分，满分 75 分。2 在答卷的指定位置填写你所在的省、自治区、直辖市、计划单列市的名称。3 在答卷的指定位置填写准考证编号、出生年月日和姓名。4 答卷上除填写上述内容外只能写解答。5 解答时字迹务必清楚，字迹不清时，将不评分。6 仿照下面例题，将解答写在答卷的对应栏内。例题从供选择的答案中，选出应填入下面_?_内的最确切的解答，把相应编号写在答卷的对应栏内。二 0
2、00 年度中国计算机软件专业技术资格和水平考试日期是_D_。供选择的答案D：（1）4 月 16 日（2）10 月 8 日（3）11 月 4 日因为正确的答案是“11 月 4 日”，故在答卷的对应栏 D 内写上编号“3”（参看答卷纸）。试题 1从供选择的答案中，选出应填入下面叙述中_?_内的最确切的解答，把相应编号写在答卷的对应栏内。如图所示的二叉树，有下列性质：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上一切结点的值。这是一棵_A_树。现有一菲波那契数列a n,a 0=a1=1,ak=ak-1+ak-2,k=2,3。若把a 1,a2,a9填入该二叉树，一般可采
3、用_B_遍历法遍历该树上全部结点，得到由结点的值组成的从小到大顺序排列的序列。对本题给出的二叉树图形填入a 1,a9后，其结点 n8 的值为_C_，根结点的值为_D_。若欲插入a 1,a9的平均值，则应该在_E_增加一个结点。on1/ on2 on3/ on4 on5 on6/ on7 on8 on9供选择的答案：(1)穿线树 (2)最佳查找树(3) 树 (4) 查找树：(1)前序 (2)中序 (3) 后序 (4) 广度：(1) (2) (3) (4) ：(1) (2) (3) (4) ：(1)n2 与 n4 之间 (2)n6 下 (3)n 与 n9 之间 (4)n9 下试题 2从供选择的答案
4、中，选出应填入下面叙述中_?_内的最确切的解答，把相应编号写在答卷的对应栏内。堆是一种特殊的数据结构，_A_ 是一个堆，堆排序是一种_B_排序，m 个元素进行堆排序时，其时间复杂性为_C_。排序的算法很多，若按排序的稳定性和不稳定性分类，则_D_是不稳定排序。外排序是指_E_。供选择的答案 ：(1)19,75,34,26,97,56(2)97,26,34,75,19,56(3)19,56,26,97,34,75(4)19,34,26,97,56,75：(1)归并 (2) 交换 (3) 选择 (4)插入：(1)o(m) (2)o(m 2) (3)o(log2m) (4)o(mlog2m)：(1)
5、冒泡排序(2) 归并排序(3) 直接插入排序(4)希尔(shell)排序：(1)用机器指令直接对硬盘中需排序数据排序(2)把需排序数据，用其他大容量机器排序(3)把外存中需排序数据一次性调入内存，排好序后，再输回外存(4)对外存中大于内存允许空间的需排序的数据，通过多次内外存间的交换实现排序。试题从供选择的答案中，选出应填入下面叙述中_?_内的最确切的解答，把相应编号写在答卷的对应栏内。软件语言是用于书写计算机软件的语言。它主要包括需求定义语言、_A_、_B_、程序设计语言以及_C_等，适用于软件开发的各个阶段。程序设计语言的基本成分是数据成分、运算成分、控制成分以及_D_ 。程序设计语言有多
6、种分类法，例如，按成分性质分，有顺序语言，并发语言，并行语言，_E_。供选择的答案：(1)数据定义语言(2)功能性语言(3) 面向对象语言(4) 函数式语言：(1)设计性语言 (2)结构性语言(3) 命令式语言 (4) 申述式语言：(1)过程语言 (2)非过程语言(3) 逻辑式语言 (4) 文档语言：(1)对象成分 (2)变量成分 (3) 语句成分 (4) 传输成分：(1)交互式语言 (2)分布语言 (3) 面向对象语言(4) 高级语言试题从供选择的答案中，选出应填入下面叙述中_?_内的最确切的解答，把相应编号写在答卷的对应栏内。某些操作系统，将一条命令的执行结果输出给下一条命令，作为其输入并
7、加以处理，这是系统的_A_机制。使命令所需要的信息不从键盘接收，而取自另一个文件，这是系统的_B_机制。使命令的执行结果直接引向另一个文件，而不在屏幕上显示，这是系统的_C_机制。操作系统不从键盘逐条接收命令并执行，而调用一个正文文件，执行其中的一系列命令，这种方式称为_D_ 方式，编写这样的文件应符合_E_语言的语法规则。供选择的答案：(1)链接 (2) 输入重定向(3) 管道 (4)输出重定向：(1)输入重定向(2) 管道 (3) 读保护 (4)批处理：(1)管道 (2) 输出重定向(3) 清屏 (4)显示屏蔽：(1)初始装入 (2) 批处理 (3) 管道 (4)系统生成：(1)命令定向
8、(2) 机器指令 (3) 人机会话(4)作业控制试题从供选择的答案中，选出应填入下面叙述中_?_内的最确切的解答，把相应编号写在答卷的对应栏内。编制一个好的程序首先要确保它的正确性和可靠性，除此以外，通常更注重源程序的_A_。此外，还应强调良好的编程风格，例如，选择标识符的名字时应考虑_B_；在书写语句时应考虑_C_；在书写功能性注解时应考虑 _D_。源程序中应包含一些内部文档，以帮助阅读和理解源程序，源程序的内部文档通常包括选择合适的标识符、注解和_E_。供选择的答案：(1)易使用性、易维护性和效率 (2)易使用性、易维护性和易移植性(3)易理解性、易测试性和易修改性(4)易理解性、安全性和
9、效率：(1)名字长度越短越好，以减少源程序的输入量(2)多个变量共用一个名字，以减少变量名的数目(3)选择含义明确的名字，以正确提示所代表的实体(4)尽量用关键字作名字，以使名字标准化：(1)把多个短的语句写在同一行中，以减少源程序的行数(2)尽量使用标准文本以外的有特殊功效的语句，以提高程序的功效(3)尽量消除表达式中的括号，以简化表达式(4)避免使用测试条件“非”，以提高程序的可读性：(1)仅为整个程序作注解 (2)仅为每个模块作注解(3)为程序段作注解 (4)为每个语句作注解：(1)程序的视觉组织 (2)尽量不用或少用语句(3)检查输入数据的有效性(4)设计良好的输出报表试题从供选择的答
10、案中，选出应填入下面叙述中_?_内的最确切的解答，把相应编号写在答卷的对应栏内。数据库的三级体系结构即关系子模式、关系模式与存储模式，是对_A_抽象的三个级别。主要由_B_两大部分组成。的语句中“rom”（这里为基本表名），应理解为_C_。关系代数中的 联接操作由_D_ 操作组合而成。元组比较操作(c1 ，c2)valval;q=p,p=p-next);if (p=h) _(1)_;else _(2)_;q=b;b=b-next; _(3)_;return h; 【函数 1.2 说明】递归函数 dec(int a,int n)判断数组 a的前 n 个元素是否是不递增的。不递增返回，否则返回。【
11、函数 1.2】int dec(int a,int n) if (n10;p+) if (p=a0 _(1)_;ap+1+=ap/10; ap=_(2)_;if (pa0) _(3)_;【函数 2.2 说明】函数 combine(a,b,c)是计算两个整数的组合数。由于计算结果超出 long int 的表示范围，故用本题【函数 2.1 说明】的方法存储计算结果。设整数 a 和 b (a=b) ，它们的组合 c(a,b)=a!/(a-b)!*b!)。计算 a 和 b 的组合可采用以下方法：a!/(a-b)!/b!=a*(a-1)*(a-2)*(a-b+1)/b!=u1*u2*ub/(d1*d2*d
12、b)其中 u1=a，u 2=a-1，u b=a-b+1；d 1=1，d 2=2，d b=b。从而计算 a 和 b 的组合 c(a,b)，可变成计算上述分式。为计算上述分式，先从 u1，u 2，u b 中去掉所有 d1*d2*db 的因子，得到新的u1，u 2，u b。然后再将它们相乘。以下函数中调用的外部函数 gcd(a,b)是求两整数 a 和b 最大公因子的函数；函数 formal()就是本题中的函数 2.1。【函数 2.2】void combine (int a,int b,int *c) int i,j,x,k;int dMAXN,uMAXN;for (k=0,i=a;i=a-b+1;i
13、-) u+k=i;_(4)_;for (I=1;I#include #include typedef struct node /*符号、内部编号、优先级和后继栈元指针*/char data; int code;int pri;strujct mode *link;NODE;struct Tb1/*符号、内部编号、优先级*/char data; int ckde ; int pri;opchTb1=*,1,4,/,2,4,+,3,2,-,4,2,(,5,5,),6,1,0,7,0, ,-1,0;NODE *optop;/*栈顶指针*/Char num200,*numtop;/*工作数组和存储指针
14、*/Char expStr200;/*存储中缀表达式的字符数组*/Void push(char x,int c,int p,NODE *topt)/*链接存储栈的进栈函数*/NODE q=(NODE*)malloc(sizeof(NODE);q-data=x;q-code=c; q-pri=p; (1) ;*toppt=q;int pop(char*op,int *cp,NODE *toppt)/*链接存储栈的出栈函数 */NODE q=toppt;if (*toppt=NULL) return 1;/*空栈 */op=q-data;cp=q-code; (2) ;free(q); retur
15、n 0;int expr(char *pos)struct Tb1 *op; char sop; int type ,code,n,m,I,c;optop=NULL;numtop=num;n=m=0;c= ;push(#,0,0,/*预先在栈中置一个 0 优先级的符号 */while (1) while (c= | c=t) c=*pos+; /*掠过空白符 */if (isalpha( c)/*复制变量名到工作数组*/*numtop+= ;while(isalpha(c)|isdigit( c) (3) ;c=*pos+;if (m) return 1;/*运算符个数与运算分量个数不相容 *
16、/m=1;/*运算分量比运算符多 1 个 */continue;else /*处理运算符或非法字符 */for (I=0;opchTblI.code=-1I+)if (opchTblI.code=-1) return 3;/*非法字符 */op=type=opchTblI.code; /*得到运算符的内部码 */c=*pos+; /*C 中存储下一个字符*/if (typedata=() push (op-code,1,else push(op-data, op-code, op-pri,else while(optop!=NULL if ( (7) ) /* 运算符复制到工作数组*/*numtop+= ; *numtop+=stop;if (op-data=0)return (n!=0|(m!=1else if(op-data!=)push (op-data,op-code,op-pri,
