2008年下半年程序员下午试卷

考试总分：7分

考试类型：模拟试题

作答时间：60分钟

已答人数：967

试卷答案：有

试卷介绍： 2008年下半年程序员下午试卷

开始答题

试卷预览

1. 试题一（共15分）阅读以下说明和流程图，填补流程图中的空缺（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)、…逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，依此类推。[流程图][15分]

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

B(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)、…逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，依此类推。[流程图][15分]

2. 试题三（共15分）阅读以下说明和C函数，将应填入（n）处的字句写在答题纸的对应栏内。[说明]已知某二叉树的非叶子结点都有两个孩子结点，现将该二叉树存储在结构数组Ht中。结点结构及数组Ht的定义如下：#defineMAXLEAFNUM30structnode{charch;/*当前结点表示的字符，对于非叶子结点，此域不用*/char*pstr;/*当前结点的编码指针，非叶子结点不用*/intparent;/*当前结点的父结点，为0时表示无父结点*/intlchild,rchild;/*当前结点的左、右孩子结点，为0时表示无对应的孩子结点*/}；structnodeHt[2*MAXLEAFNUM];/*数组元素Ht[0]不用*/该二叉树的n个叶子结点存储在下标为1～n的Ht数组元素中。例如，某二叉树如图3-1所示，其存储结构如图3-2所示，其中，与叶子结点a对应的数组元素下标为1，a的父结点存储在Ht[5]，表示为Ht[1].parent=5。Ht[7].parent=0表示7号结点是树根，Ht[7].lchild=3、Ht[7].rchild=6分别表示7号结点的左孩子是3号结点、右孩子是6号结点。如果用“0”或“1”分别标识二叉树的左分支和右分支（如图3-1所示），从根结点开始到叶子结点为止，按所经过分支的次序将相应标识依次排列，可得到一个0、1序列，称之为对应叶子结点的编码。例如，图3-1中a、b、c、d的编码分别是100、101、0、11。函数LeafCode(Ht[],n)的功能是：求解存储在Ht中的二叉树中所有叶子结点(n个)的编码，叶子结点存储在Ht[1]～Ht[n]中，求出的编码存储区由对应的数组元素pstr域指示。函数LeafCode从叶子到根逆向求叶子结点的编码。例如，对图3-1中叶子结点a求编码的过程如图3-3所示。typedefenumStatus{ERROR,OK}Status;[C函数]StatusLeafCode(structnodeHt[],intn){intpc,pf;/*pc用于指出树中的结点，pf则指出pc所对应结点的父结点*/inti,start;chartstr[31]={'\0'};/*临时存储给定叶子结点的编码，从高下标开始存入*/for(i=1;（1）;i++){/*对所有叶子结点求编码，i表示叶结点在HT数组中的下标*/start=29;pc=i;pf=Ht[i].parent;while(pf!=（2）){/*没有到达树根时，继续求编码*/if(（3）.lchild==pc)/*pc所表示的结点是其父结点的左孩子*/tstr[--start]='0';elsetstr[--start]='1';pc=（4）;pf=Ht[pf].parent;/*pc和pf分别向根方向回退一层*/}/*endofwhile*/Ht[i].pstr=(char*)malloc(31-start);if(!Ht[i].pstr)returnERROR;strcpy(Ht[i].pstr,（5）);}/*endoffor*/returnOK;}/*endofLeafCode*/[15分]

3. 试题二（共15分）阅读以下说明和C程序代码，将应填入（n）处的字句写在答题纸的对应栏内。[说明]下面C程序代码的功能是：对于输入的一个正整数n（100≤n#includeintisPalm(longm){/*判断m是否为回文数*/inti=0,k=0;charstr[32];while(m>0){/*从个位数开始逐个取出m的各位数字并存入字符数组str*/str[k++]=（1）+'0';m=m/10;}for(i=0;i=1000)return-1;while(（3）){/*n不是回文数时执行循环*/printf("%ld->",n);for(a=0,t=n;t>0;){/*计算n的反序数并存入a*/a=（4）*10+t%10;t=t/10;}/*endoffor*/n=（5）;/*与反序数求和*/}/*endofwhile*/printf("%ld\n",n);system("pause");return0;}[15分]

4. 试题四（共15分）阅读以下说明和C函数代码，回答问题并将解答写在答题纸的对应栏内。[说明]著名的菲波那契数列定义式为f1=1f2=1fn=fn-1+fn-2（n=3,4,…）因此，从第1项开始的该数列为1,1,2,3,5,8,13,21,…。函数fib1和fib2分别用递归方式和迭代方式求解菲波那契数列的第n项（调用fib1、fib2时可确保参数n获得一个正整数）。[C函数代码][问题1]（6分）函数fib1和fib2存在错误，只需分别修改其中的一行代码即可改正错误。（1）函数fib1不能通过编译，请写出fib1中错误所在行修改正确后的完整代码；（2）函数fib2在n≤2时不能获得正确结果，请写出fib2中错误所在行修改正确后的完整代码。[问题2]（3分）将函数fib1和fib2改正后进行测试，发现前46项都正确，而第47项的值是一个负数，请说明原因。[问题3]（6分）函数fib1、fib2求得菲波那契数列第n项（n>40）的速度并不相同，请指出速度慢的函数名，并简要说明原因。[15分]

5. 试题五（共15分）阅读以下应用说明、属性设置以及VisualBasic程序代码，将解答写在答题纸的对应栏内。[应用说明]本应用运行时，由用户输入一个正整数n后自动产生n个正整数，然后按照用户的指定要求对该组数进行处理。该应用的运行界面如下图所示：1.窗体中有两个文本框（txtSrc，txtObj）、两个标签（lblSrc，lblObj）、三个命令按钮（cmdGendat，cmdProc，cmdQuit）和一个弹出式菜单（procMenu，初始时不可见）。2．文本框txtSrc（由标签lblSrc提示）用于显示产生的数据，文本框txtObj（由标签lblObj提示）用于显示处理结果，要求每行显示一个整数。3.程序启动时，命令按钮cmdProc（运算要求）不可用。点击命令按钮cmdGendat（产生数据）后，提示用户输入一个n的值并生成n个正整数存入数组元素a(1)～a(n)，然后将数据逐行显示在txtSrc中，并设置命令按钮cmdProc可用。4.点击命令按钮cmdProc（运算要求）后弹出菜单。选择菜单项并单击后，进行相应处理并将结果显示在txtObj中，同时将lblObj的标题改为该菜单项表示的处理命令。弹出式菜单“运算要求”的结构如下表所示：一个整数序列的中位数指对该序列进行非递减（增）排列后最中间位置上的元素。若序列长度为偶数，则取中间两个元素的平均值为其中位数。[属性设置]为实现单击命令按钮cmdProc后弹出“运算要求”菜单（procMenu），设计时需将procMenu的（1）属性设置成false。供（1）选择的属性：DefaultEnabledScaleModeStyleVisible[VisualBasic程序代码]Dima()AsInteger,nAsIntegerPrivateSubForm_Load()txtSrc.Text="":txtObj.Text="":（2）=FalseEndSubPrivateSubcmdGendat_Click()'生成正整数序列并存入数组aOnErrorGoToError_handlern=InputBox$("请输入数组元素个数：","输入序列长度")If(niThena(k)=a(i):a(i)=a(0)EndIfNextIfn/2-n\2>0Then'n为奇数时，取中间一个数txtObj.Text=Str$(a(（5）))Else'n为偶数时，取中间两个数的平均值txtObj.Text=Str$(Int((a(n\2)+a(n\2+1))/2))EndIfEndSub'其他代码略[15分]

A(1)～a(n)，然后将数据逐行显示在txtSrc中，并设置命令按钮cmdProc可用。4.点击命令按钮cmdProc（运算要求）后弹出菜单。选择菜单项并单击后，进行相应处理并将结果显示在txtObj中，同时将lblObj的标题改为该菜单项表示的处理命令。弹出式菜单“运算要求”的结构如下表所示：一个整数序列的中位数指对该序列进行非递减（增）排列后最中间位置上的元素。若序列长度为偶数，则取中间两个元素的平均值为其中位数。[属性设置]为实现单击命令按钮cmdProc后弹出“运算要求”菜单（procMenu），设计时需将procMenu的（1）属性设置成false。供（1）选择的属性：DefaultEnabledScaleModeStyleVisible[VisualBasic程序代码]Dima()AsInteger,nAsIntegerPrivateSubForm_Load()txtSrc.Text="":txtObj.Text="":（2）=FalseEndSubPrivateSubcmdGendat_Click()'生成正整数序列并存入数组aOnErrorGoToError_handlern=InputBox$("请输入数组元素个数：","输入序列长度")If(niThena(k)=a(i):a(i)=a(0)EndIfNextIfn/2-n\2>0Then'n为奇数时，取中间一个数txtObj.Text=Str$(a(（5）))Else'n为偶数时，取中间两个数的平均值txtObj.Text=Str$(Int((a(n\2)+a(n\2+1))/2))EndIfEndSub'其他代码略[15分]

6. 试题六（共15分）阅读以下说明和C++代码，将应填入（n）处的字句写在答题纸的对应栏内。[说明]C++标准模板库中提供了vector模板类，可作为动态数组使用，并可容纳任意数据类型，其所属的命名空间为std。vector模板类的部分方法说明如下表所示：[C++代码]#include#includeusingnamespace（1）;typedefvectorINTVECTOR;constintARRAY_SIZE=6;voidShowVector(INTVECTOR&theVector);intmain(){INTVECTORtheVector;//初始化theVector，将theVector的元素依次设置为0至5for(intcEachItem=0;cEachItem<ARRAY_SIZE;cEachItem++)theVector.push_back(（3）);ShowVector(theVector);//依次输出theVector中的元素theVector.erase(theVector.begin()+3);ShowVector(theVector);}voidShowVector(INTVECTOR&theVector){if(theVector.empty()){cout<<"theVectorisempty."<<endl;return;}INTVECTOR::iterator（4）;for(theIterator=theVector.begin();theIterator!=theVector.end();theIterator++){cout<<*theIterator;if(theIterator!=theVector.end()-1)cout<<",";}cout<<endl;}该程序运行后的输出结果为：0,1,2,3,4,5（5）[15分]

7. 试题七（共15分）阅读以下说明和Java代码，将应填入（n）处的字句写在答题纸的对应栏内。[说明]java.util库中提供了Vector模板类，可作为动态数组使用，并可容纳任意数据类型。该类的部分方法说明如下表所示：[Java代码]import（1）;publicclassJavaMain{staticprivatefinalint（2）=6;publicstaticvoidmain(String[]args){VectortheVector=newVector();//初始化theVector，将theVector的元素设置为0至5for(intcEachItem=0;cEachItemtheVector){if(theVector.isEmpty()){System.out.println("theVectorisempty.");return;}for(intloop=0;loop<theVector.size();loop++){System.out.print(theVector.get(loop));System.out.print(",");}System.out.println();}}该程序运行后的输出结果为：0,1,2,3,4,5（5）[15分]