计算机软件专业技术资格和水平考试

1、计算机软件专业技术资格和水平考试二000年度程序员级上午试卷(考试时间9： 0011: 30共150分钟)请按下述要求正确填写答卷，若不按下述要求解答，将不给分数1. 本试卷的15道试题都是必答题，请全部解答。每题5分，满分75分。2. 在答卷的指定位置填写你所在的省、自治区、直辖市、计划单列市的名称。3. 在答卷的指定位置填写准考证编号、出生年月日和姓名。4. 答卷上除填写上述内容外只能写解答。5. 解答时字迹务必清楚，字迹不清时，将不评分。6. 仿照下面例题，将解答写在答卷的对应栏内。例题从供选择的答案中，选出应填入下面_?_内的最确切的解答，把相应编号写在答卷的对应栏内。二000年度中国

2、计算机软件专业技术资格和水平考试日期是_D_。供选择的答案D ( 1) 4 月 16 日( 2) 10 月 8 日( 3) 11 月 4 日因为正确的答案是“ 11月4日”，故在答卷的对应栏 D内写上编号“ 3”(参看答卷 纸)。试题1从供选择的答案中，选出应填入下面叙述中_?_内的最确切的解答，把相应编号写在答卷的对应栏内。如图所示的二叉树，有下列性质：除叶子结点外，每个结点的值都大于其左子树上的 一切结点的值，并小于等于其右子树上一切结点的值。这是一棵_A_树。现有一菲波那契数列 an ,ao=a1=1,ak=ak-1+ak-2,k=2,3 。若把 a1,a 2,a 9填入该二叉树，一般可

3、采用 _B_遍历法遍历该树上全部结点，得到由结点的值组成的从小到大 顺序排列的序列。对本题给出的二叉树图形填入a1,a9后，其结点n8的值为_C_,根结点的值为_D_。若欲插入 a1,a 9的平均值，则应该在 _丘_噌加一个 结点。on 1八on 2 on 3八on 4 on 5 on 6八on 7 on 8 on 9供选择的答案A:(1)穿线树(2)最佳查找树(3) B树(4)查找树B:(1)前序中序(3)后序(4)广度C:(1) 38(3) 2 15 7D:(1) 82 1(3) 3 4(4) 6 6E:(1)n2与n4之间(2)n6 下(3)n 5与n9之间(4)n9下从供选择的答案中，

4、选出应填入下面叙述中_?_内的最确切的解答，把相应编号写在答卷的对应栏内。堆是一种特殊的数据结构，_A_是一个堆，堆排序是一种_B_排序，m个元素进行堆排序时，其时间复杂性为_C_。排序的算法很多，若按排序的稳定性和不稳定性分类，则_D_是不稳定排序。外排序是指_E_。 供选择的答案A: (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,75B: (1)归并交换选择插入C: (1)o(m)(2)o(m )(3)o(log 2 m)(4)o(mlog 2m)D： (1)冒泡排序 归并排序

5、直接插入排序 希尔(shell)排序E： (1)用机器指令直接对硬盘中需排序数据排序(2) 把需排序数据，用其他大容量机器排序(3) 把外存中需排序数据一次性调入内存，排好序后，再输回外存(4) 对外存中大于内存允许空间的需排序的数据，通过多次内外存间的交换实现排 序。试题3从供选择的答案中，选出应填入下面叙述中_?_内的最确切的解答，把相应编号写在答卷的对应栏内。软件语言是用于书写计算机软件的语言。它主要包括需求定义语言、A 、_B_程序设计语言以及_C_等，适用于软件开发的各个阶段。程序设计语言的基本成分是数 据成分、运算成分、控制成分以及_D_。程序设计语言有多种分类法，例如，按成分性质

6、分，有顺序语言，并发语言，并行语言，_E_。供选择的答案A: (1)数据定义语言(2)功能性语言(3)面向对象语言(4)函数式语言B: (1)设计性语言(2)结构性语言(3)命令式语言(4)申述式语言C:(1)过程语言(2)非过程语言(3)逻辑式语言(4)文档语言D:(1)对象成分(2)变量成分(3)语句成分(4)传输成分E:(1)交互式语言(2)分布语言(3)面向对象语言(4)高级语言试题4从供选择的答案中，选出应填入下面叙述中_?_内的最确切的解答，把相应编号写在答卷的对应栏内。某些操作系统，将一条命令的执行结果输出给下一条命令，作为其输入并加以处理， 这是系统的_A_机制。使命令所需要的

7、信息不从键盘接收，而取自另一个文件，这是系 统的_B_机制。使命令的执行结果直接引向另一个文件，而不在屏幕上显示，这是系统 的_C_机制。操作系统不从键盘逐条接收命令并执行，而调用一个正文文件，执行其中 的一系列命令，这种方式称为 _D_方式，编写这样的文件应符合_E_语言的语法规则。供选择的答案(3)管道(4)输出重定向读保护批处理(3)清屏(4)显示屏蔽管道(4)系统生成(3)人机会话(4)作业控制A:(1)链接(2)输入重定向B: (1)输入重定向管道C:(1)管道(2)输出重定向D:(1)初始装入(2)批处理E:(1)命令定向机器指令从供选择的答案中，选出应填入下面叙述中_?_内的最确

8、切的解答，把相应编号写在答卷的对应栏内。编制一个好的程序首先要确保它的正确性和可靠性，除此以外，通常更注重源程序的_A_。此外，还应强调良好的编程风格，例如，选择标识符的名字时应考虑_B_；在书写语句时应考虑_C_;在书写功能性注解时应考虑 _D_。源程序中应包含一些内部文档，以帮助阅读和理解源程序，源程序的内部文档通常包 括选择合适的标识符、注解和 _E_。供选择的答案A:(1)易使用性、易维护性和效率(2)易使用性、易维护性和易移植性(3)易理解性、易测试性和易修改性 (4)易理解性、安全性和效率B:(1) 名字长度越短越好，以减少源程序的输入量(2) 多个变量共用一个名字，以减少变量名的

9、数目(3) 选择含义明确的名字，以正确提示所代表的实体(4) 尽量用关键字作名字，以使名字标准化C:(1)把多个短的语句写在同一行中，以减少源程序的行数尽量使用标准文本以外的有特殊功效的语句，以提高程序的功效(3)尽量消除表达式中的括号，以简化表达式避免使用测试条件“非”，以提高程序的可读性D:(1)仅为整个程序作注解(2)仅为每个模块作注解(3)为程序段作注解(4)为每个语句作注解E:(1)程序的视觉组织(2)尽量不用或少用GOTO语句检查输入数据的有效性设计良好的输出报表试题6从供选择的答案中，选出应填入下面叙述中_?_内的最确切的解答，把相应编号写在答卷的对应栏内。数据库的三级体系结构即

10、关系子模式、关系模式与存储模式，是对_A_抽象的三个级别。DBMS主要由_B_两大部分组成SQL的SELECT语句中“F rom Q” (这 里Q为基本表名)，应理解为C。关系代数中的B联接操作由_D_操作组合而成。元组比较操作 (cl , c2)=(d1,d2)，其 意义等价于E 。供选择的答案A:(1)存储器(2)数据库系统(3)数据(4)数据库管理系统B:(1)文件管理器和查询处理器(2)事务处理器和存储管理器(3)文件管理器和数据库语言编译器(4)存储管理器和查询处理器C:(1) Q中的兀组序号(2)关系Q的元组变量(3)基本表Q的结构定义(4) Q中的全部元组D:(1) b和nb和X

11、(3) n、 b和X n和XE:(1)(c1=d1)OR(c2=d2)(2)(c1=d1)OR(c 1=d1)AND(c2=d2)(3) (c1=d1)AND(c2=d2)(4) (c1d1)OR(c 1=d1)AND(c2valval;q=p,p=p-n ext);if (p=h) _(1)_;else _(2)_;q=b;b=b-n ext; _(3)_; return h;【函数1.2说明】递归函数dec(int a,int n)判断数组a的前n个元素是否是不递增的。不递增返回1, 否则返回0。【函数1.21int dec(i nt a,i nt n) if (n =1) _(4)_;i

12、f (a0a1) return 0;return _(5)_; 试题二(18分)阅读下列函数说明和C代码，将应填入_(n)_处的字句写在答卷的对应栏内。【函数2.1说明】设长正整数用数组存储，如有k位的长整数 m用数组a存储：k-1K-210m=ak*10ak-1*10+ +a2*10 +a1*10并用a0存储长整数 m的位数，即a0=k。通常，存储长整数数组的每个元素只存储长整数的一位数字。长整数运算时，为了运 算方便，产生的中间结果的某位数字可能会大于9。这时，就应调用本函数将它规整，使数组的每个元素只存储长整数的一位数字。规整运算函数formal。nt *a)就实现这个特殊要求。【函数2

13、.11void formal(i nt *a) int p;for (p=1;p10;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*d 2* *d

14、 b) 其中 u1 =a, u2=a-1,，ub=a-b+1 ; d1=1, d2=2,，db=b。从而计算a和b的组合c(a,b)，可变成计算上述分式。为计算上述分式，先从 U1, U2,，Ub中去掉所有di*d2*db的因子，得到新的U1, U2,，Ub。相乘。以下函数中调用的外部函数gcd(a,l 两整数a和b最大公因子的函数；函数 formal。就是本题中的函数 2.1。【函数2.2】void comb ine (int a,i nt b,i nt *c) int i,j,x,k;int dMAXN,uMAXN;for (k=0,i=a;i=a-b+1;i-) u+k=i;_；for

15、(l=1;l=b;l+) dl=l; /* 将整数 1 至 b 顺序存于数组 d*/for (l=1;l=u0;l+) /* 从u的各元素中，去掉d中整数的所有因子*/if (ul!=1)for (j=1;j=b;j+)if (_(5)_) x=gcd(ul,dj); ul/=x; dj/=x;c0=c1=1; /*长整数c初始化*/for (l=1;l=u0;l+) /* 将u中各整数相乘，存于长整数c*/if (ul!=1) for (j=1;j=c0;j+) cj=_(6)_;formal(c); /*将存于c中的长整数规整*/试题三(21分)阅读下列函数说明和C代码，将应填入_(n)_

16、处的字句写在答卷的对应栏内。【程序3说明】本程序中的函数 expr()实现将中缀表达式转换成后缀表达式。设中缀表达式只有加 (+)、减(-)、乘(*)和除(/)四则运算符(双目)，运算分量只能是变量，变量用英文字母开头 英文字母和数字符组成的标识符命名。与平常四则运算的计算规则相一致，即先乘除，后 加减，括号内的子表达式优先计算。例如，中缀表达式a*(c3-x2z/y)+u的后缀表达式为ac3x2zy/-*u+程序给每个运算符和括号设定一个优先级，并引入一个栈和一个存储后缀表达式的 工作数组。函数 expr()工作时，按自左至右逐个顺序扫描中缀表达式，如当前符号是变量 名，就将该变量名直接复制

17、到工作数组；如当前符号是运算符或括号，将当前符号的优先 级和栈顶符号的优先级进行比较；若当前符号的优先级高，则当前符号进栈；反之，则进 行出栈处理，并将从栈中退出的运算符依次复制到工作数组中，直到栈顶符号的优先级比 当前符号的优先级低为止，然后将当前的运算符或左括号进栈。为使子表达式能优先处 理，所以给左括号设定较高的优先级，但又为了能正确处理随后的子表达式，在左括号进 栈时，它在栈中的优先级作了一定的改变。初始时，expr()函数预先在栈底设置一个符号#,其优先级比所有运算符和括号 的优先级都低。程序还检查输入表达式的运算符和运算分量的合理性，以及括号是否正确 配对。【程序3】#i nclu

18、de #in clude #in clude typedef struct node /*符号、内部编号、优先级和后继栈元指针*/char data; int code;i nt pri;strujct mode *li nk;NODE;struct Tb1/*符号、内部编号、优先级 */char data; int ckde ; int pri;opchTb1= * ,1,4, / ,2,4,- ,4,2+, ,3,2, ( ,5,5,)0伽0, -1,0; ，NODE *optop;/* 栈顶指针 */Char num200,*numtop;/*工作数组和存储指针 */Char expSt

19、r200;/*存储中缀表达式的字符数组*/Void push(char x,int c,in t p,NODE *topt)/*链接存储栈的进栈函数*/NODE q=(NODE *)malloc(sizeof(NODE);q-data=x;q-code=c; q-pri=p; (1) ;*toppt=q;in t pop(char*op,i nt *cp,NODE *toppt)/*链接存储栈的出栈函数*/NODE q=toppt;if (*toppt=NULL) return 1;/* 空栈 */ op=q-data; cp=q-code; (2) ;free(q); return 0;in

20、t expr(char *pos) struct Tb1 *op; char sop; int type ,code ,n, m,l,c;optop=NULL ;nu mtop=num;n=m=0;c=；push( # ,0,0,&optop预先在栈中置一个 0优先级的符号*/ while (1) while (c= t ) c=*pos+; /掠过空白符 */if (isalpha( c)/*复制变量名到工作数组*/*nu mtop+=；while(isalpha(c)|isdigit( c)(3);c=*pos+;if (m) return 1;/*运算符个数与运算分量个数不相容*/m=1

21、;/*运算分量比运算符多1个*/con ti nue;else /*处理运算符或非法字符*/for (I=0;opchTblI.code=-1 &(4) ;I+)if (opchTblI.code=-1) return 3;/* 非法字符 */ op=&opchTbll;type=opchTbll.code; /*得到运算符的内部码*/c=*pos+; /*C 中存储下一个字符 */if (typedata= ( )push(oipde,1,&optop); else push(op-data, op-code, op-pri,&optop);else while(optop!=NULL &o

22、p-pripri)pop( (6);if (7) /*运算符复制到工作数组*/*numtop+= ； *numtop+=stop;if (op- data= 0) return (n!=0|(m!=1 &numtopnum)?4( *numtop= 0);else if(op- data!=)push (op-data,op-code,op-pri,&optop);void mai n()int d;printf(请输入表达式n ” );gets(expStr);if (d=expr(expStr)=0) printf(后缀表达式为n”，num);else printf(表达式句法错！错误类型

23、为n” ,d);试题四(21分)阅读下列程序说明和C代码，将应填入(n)处的字句写在答卷的对应栏内。程序4说明有一种单人玩的游戏：设有n(2=n0)堆，和将k张薄片移至l+1(ln-1)堆。所以当有两个堆与I堆相邻时，I堆原先至少有2k张薄片；只有一个堆与I堆相邻时，I堆原先至少有k张薄片。游戏的目标是对给定的堆数，和各堆上的薄片数，按上述规则移动薄片，最终使各堆的薄片数相同。为了使移动次数较少些，移动哪一堆薄片，和移多少薄片先作以下估算： 设Ci：l 堆的薄片数(0=In,0=c i=ai ；若I堆是中间堆，则要求=2ai。(2) 因在a0的所有堆中，薄片数最多的堆在平分过程中被它的相邻堆取走的薄片数也最多。在用策略(1)搜索移动时，当发生没有满足条件(1)的可移走薄片的堆时，采用本策略，让在ai0的所有堆中，薄片数最多的堆被它的相邻堆取走它的全部薄片。程序4#in clude #defi ne N 200#defi ne M 200#defi ne Limit 2000struct int id; int k;wayLimit;/*存储每次移动的位置和薄片张数*/i