初级程序员下午试题-3

1、初级程序员下午试题-3(总分：120.00，做题时间：90分钟)一、(B试题一(/B(总题数：1,分数：15.00)【流程图说明】下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有3个成员：data,left和right。其查找的方法是：首先与树的根节点的元素值进行比较：若相等则找到，返回此结点的地址；若要查找的元素小于根节点的元素值，则指针指向此结点的左子树，继续查找；若要查找的元素大于根节点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。【算法说明】【流程图】将上题的排序二叉树中查找元素的过程用递归的方法实现。

2、其中NOD虎自定义类型：Itypedefstructnodeintdata;structnode*left;structnode*right;NODE;【算法】NODE*SearchSortTree(NODE*tree,inte)if(tree!=NULL)if(tree->data<e)U(4)/U;/小于查找左子树elseif(tree->data<e)U(5)/U;/大于查找左子树elsereturntree;returntree;(分数：15.00)填空项1:(正确答案：p=p->left(2)ptr=p->right(3)returnP(4)ret

3、urnSearchSortTree(tree->left)(5)returnSearchSortTree(tree->right)解析：解析所谓二叉排序树，指的是一棵为空的二叉树，或者是一棵具有如下特性的非空二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值。若它的右子树非空，则右子树上所有结点的值均大干根结点的值。左、右子树本身又各是一棵二叉排序树。先来分析流程图。在流程图中只使用一个变量p,并作为循环变量来控制循环，所以循环体中必须修改这个值。当进入循环时，首先判断p是不是为空和该结点是不是要找的结点，如果这两个条件有一个满足就退出循环，返回prt,(如果是空，则

4、返回NULL说明查询失败；否则返回键值所在结点的指针。)因此(3)空处应当填写"returnp"。如果两个条件都不满足，就用查找键值e与当前结点的关键字进行比较，小的话，将指针p指向左子树继续查找，大的话将指针P指向右子树继续查找。于是，(1)空处应当填写"p=p->left”，空处应当填写“p=p->right”。再来分析程序。虽然是递归算法，但实现思路和非递归是一样。首先用查找键值e与树根结点的关键字比较，如果值小的话，就在左子树中查找(即返回在左子树中查找结果)；如果值大的话在右子树中查找(即返回在右子树中查找结果)；如果相等的活就返回树根指针。

5、因此(4)、(5)空分别应填写"returnSearehSortTree(tree->left)"养口"returnSearehSoaTree(tree->right)"。二、B试题二/B(总题数：1,分数：15.00)【说明2.1】L为一个带头结点的循环链表。函数deletenode(LinkListL,intc)的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。【函数2.1】LinkListdeletenode(LinkListL,intc)LinkListLc,p

6、,pre;pre=L;p=U(1)/U;Lc=(LinkList)malloc(sizeof(ListNode);Lc->next=Lcwhile(p!=L)if(p->data>c)U(2)/U;U(3)/U;Lc->next=p;p=pre->next;elsepre=p;p=pre->next;returnLc;【说明2.2】递归函数dec_to_k_2(intn,intk)的功能是将十进制正整数n转换成k<2<k<9)进制数，并打印。【函数2.2】dec_to_k_2(intn,intk)/*将十进制正整数n转换成k(2<k&

7、lt;9)进制数*/if(n!=0)dec_to_k_2(U(4)/U,k);printf("%d",U(5)/U);(分数：15.00)填空项1:(正确答案：pre->next或L->next(2)pre->next=p->next)解析：(3)p->next=Lc->next(4)n/k(5)n%k解析这一题共有两个函数，第一个函数是考查链表的删除和插入操作，第二个函数是考查递归函数。先看第一个函数。(1)空所在语句是对指针p赋初值，通过下面的程序可以判断指针pre所指的结点是指针p所指的结点前驱结点，因此(1)空处应填写"

8、pre->next”或“L>next”。(2)、(3)空所在的语句块是处理当指针p所指的结点是一个大于c的结点，则将该结点从链表L中删除，再将它插入至ij链表Lc中。由指针pre和指针p的关系，从链表中删除指针p所指结点很简单，只需将指针pre的next域修改为指针p的next域即可，因此(2)空处应填写"pre>next=P->next”或其等价形式。将指针p所指的结点插入到链表Lc的过程是，先将指针P的next域指向指针Lc的next所指的结点，再将指针Lc的next指向指针p所指的结点。因此(3)空处应填写"p->next=Lc->

9、next”或其等价形式。再来分析第二个函数。将十进制正整数转换成k进制数，采用除k取余法。最开始得到余数作为k进制数的最低位，最后得到的余数作为k进制数的最高位。用n不断地除以k,直到商为0。转换所得到的k进制数是从低位开始生成，而输出则应该从高位开始。根据这一特点，用递归法求解时，先应将n/k转换成k进制，再输出n%k因此(4)空、(5)空处分别填写“n/k”、“n%k。当然这个问题也可以通过非递归的算法来完成，这样在转换过程中，需要一个栈来暂存n除以k所得到的各位余数。三、(B试题三(/B(总题数：1,分数：15.00)3.1】假设以带头结点的单循环链表作非递减有序线性表的存储结构。函数d

10、eleteklist(LinkListhead)的功能是删除表中所有数值相同的多余元素，并释放结点空间。例如：链表初始元素为：(7,10,10,21,30,42,42,42,51,70)经算法操作后变为：(7,10,21,30,42,51,70)【函数3.1】voiddeleteklist(LinkListhead)LinkNode*p,*q;p=head->next;while(p!=head)q=p->next;while(U(1)/U)U(2)/U;free(q);q=p->next;p=p->next;【说明3.2已知一棵完全二叉树存放于一个一维数组Tn中，Tn

11、中存放的是各结点的值。下面的程序的功能是：从T0开始顺序读出各结点的值，建立该二叉树的二叉链表表示。【函数3.2】#include<istream.h>typedefstructnodeintdata;stuctnodeleftChild,rightchild;BintreeNode;typedefBintreeNode*BinaryTree;voidConstrncTree(intT,intn,inti,BintreeNode*&ptr)if(i=n)U(3)/U;/*置根指针为空*/elseptr=-(BTNode*)malloc(sizeof(BTNode)ptr-&

12、gt;data=Ti;ConstrucTree(T,n,2,i+1,U(4)/U);ConstrucTree(T,n,U(5)/U,ptr-rightchild);main(void)/*根据顺序存储结构建立二叉链表*/Binarytreebitree;intn;printf("pleaseenterthenumberofnode:/n%s"n);int*A=(int*)malloc(n*sizeof(int);for(inti=0;ivn;i+)scanf("%d,A+i);/*从键盘输入结点值*/for(inti=0;ivn;i+)printf("%

13、d",Ai);ConstructTree(A,n,0,bitree);(分数：15.00)填空项1:(正确答案：q!=head&&q->data=p->data(2)p->next=q->next(3)ptr=NULL)解析：(4)ptr->leftchild(5)2*i+2解析这一题共有两个程序，第一个函数是考查链表操作，第二个程序是使用递归法创建链式存储的二叉树。先看第一个函数。这个函数由于while循环实现对链表的遍历，在这个while循环中又嵌套着一个while循环，内循环实现了删除相同元素的功能。由说明和程序可知，p指针指向当前

14、遍历结点，q指向当前结点的后继结点，如果这两个结点的数据域相等，则将其删除。这个循环何时结束呢？显然，当这两个结点的数据域不相等时要结束，或者当q指向链表头结时，整个链表已经遍历完了也要结束，因此(1)空处应填写"q!=head&&q->data=p->data”或其等价形式。如果指针P和指针q所指的结点的数据域相等，则要将指针q所指的结点删除，从内存中释放空间必须要使指针q所指的结点的后继结点接到指针p所指的结点后，因此(2)空处应填写"p->next=q->next"。再来分析第二个程序。该程序由两个函数组成，函数mai

15、n()实现数据输入，函数ConstrueTree(intT,intn,inti,BintreeNode*&ptr)用于建立二叉链表。根据(3)空所在语句的注释，很容易填写。当i>=n时，就说明二叉树不存这个结点，即将根指针置空，因此(3)空应填写"ptr=NULL",当ivn时，先生成一个结点，将数组T第i个元素数据填入该结点，建立结点的左子树和右子树。根据完全二叉树的顺序存储的定义，可以第i个元素左子树根结点为2*i+1，右子树的根结点为2*i+2o因此第一条递归调用是建立左子树，第二条递归调用是建立右子树。因此(4)空应填写"ptr->le

16、ftchild”，(5)空应填写“2*i+2”。四、B试题四/B(总题数：1,分数：15.00)【说明】该程序的功能是从文件IN.DAT中读取一篇英文文章存入到字符串数组xx中，以行为单位对行中以空格或标点符号为分隔的所有单词进行倒排。最后把已处理的字符串(应不含标点符号)仍按行重新存入字符串数组xx中，最后把结果xx输出到文件OUT6.DA忡。例如：原文：YouHeMelamastudent.结果：MeHeYoustudentaamI原始数据文件存放的格式是：每行的宽度均小于80个字符，含标点符号和空格。【函数】#include<string.h>#include<coni

17、o.h>#include<ctype.h>#includevstdio.h>charxx5080;intmaxline=0;/*文章的总行数*/intReaaDat(void);voidWriteDat(void);voidStrOL(void)char*p1,*p2,t80;inti;for(i=0;i<maxline;i+)(p1=xxi;t0=0;while(*p1)p1+;while(p1>=xxi)(while(!isalpha(*p1)&&p1!=xxi)p1-;p2=p1;while(U(1)/U)p1-;if(p1=xxi)i

18、f(isalpha(*p1)p1-;elseif(!isalpha(*(p1+1)break;p2+;U(2)/U;strcat(t,p1+1);strcat(t,"");strcpy(xxi,t);voidmain()if(U(3)/U)printf("数据文件in.dat不能打开!/n/007");return;StroL();writeDat();getch();intReadDat(void)FILE*fp;inti=0;char*p;if(fp=fopen("e:/a/in.dat”,"r")=NULL)retur

19、n1;while(fgets(xxi,80,fp)!=NULL)p=strchr(xxi,'/n')if(p)*p=0;i+;maxline=U(4)/Ufclose(fp);return0;voidWriteDat(void)FILE*fp;inti;fp=fopen("e:/a/out6,dat","w");for(i=0;ivU(5)/U;i+)printf("%s/n”,xxi);fprintf(fp,"%s/n”,xxi)fclose(fp)(分数：15.00)填空项1:(正确答案：isalpha(*p1)&

20、amp;&p1!=xxi(2)*p2=0(3)ReadDat()(4)i(5)maxline)解析：解析在主函数中首先调用函数ReadDat()，从文件IN.DAT中读取一篇英文文章存入到字符串数组xx中，所以(3)空应填入"ReadDat()”。用变量maxline表示文章的行数，所以空(4)应填入"i”。函数StrOL()的功能是以行为单位对行中以空格或标点符号为分隔的所有单词进行倒排，然后把已处理的字符串(应不含标点符号)仍按行重新存入字符串数组xx中，采用的算法是先让两字符指针都指向串尾，然后使一指针(p1)往前移动，当出现不是字母时，则表示在p1+1与P2

21、之间是一个单词，并将该单词存入一变量(t1)，最后将t1连接到新串中(t);接着再往前找第二个单词，依次类推直到字符串头。br循环中的第一个while循环将字符指针移到串尾，在第二个while循环中，首先要去掉不是字母的字符，将p2也指向串尾，然后向前找一个单词及P1所指向的应为字母，且要保证仍然在本行，所以(1)空可填入“isalPha(*p1)&&p1!=xxi”(或等价形式)，这样p1+1与p2之间是一个单词，要作字符串处理，P2加1,指向字符串结束标记，所以(2)空应填入“*p2='/0'”或者“*p2=0”。最后通过调用函数WriteDat()把结果n

22、输出到文件中，(5)空为输入的行数，显然应填入"maxline"。五、B试题五/B(总题数：1,分数：15.00)I【说明】该应用程序是用来求一元二次方程和一元一次方程的，其运行如图2所示。|当用户在对应方程系数的文本框(txt1、txt2和txt3)中输入数值后，单击"解方程”按钮(cmdcalculate),解方程并将解显示在XI和K2对应的文本框中(txt4和txt5)中。若是一个一元一次方程，只显示在X1对应的文本框中，若无解则弹出对话框。下面的代码是“解方程”按钮的Click事件的代码。【程序代码】PrivateSubU(1)/U()a=Val(Txt1

23、.Text):b=Val(Txt2.Text);c=Val(Txt3.Text)Ifa=0ThenIfb=0ThenMsgBox"方程无解!",vbOKOnly,"提示"Txt4.Text=""Txt5.Text=""ElseTxt4.Text=U(2)/UTxt5.Text=""EndIfElsedelta=U(3)/UIfU(4)/UThenMsgBox"方程无解!",vbOKOnly,"提示”Txt4.Text=""Txt5.Text=&q

24、uot;"ElseTxt4.Text=Str$(-1)*b+Sqr(delta)/(2*a)Txt5.Text=U(5)/UEndIfEndIfEndSub(分数：15.00)填空项1:(正确答案：cmdcalculate_Click(2)Str$(-l*c/b)或Str(-l*c/b)或其等价形式)解析：(3)b*-b-4*a*c或其等价形式(4)delta<0或其等价形式(5)Str$(-1)*b-Sqr(delta)/(2*a)或其等价形式解析(1)空需要填写该函数的名称，说明中已经明确这是“解方程”按钮的Click事件的代码，因此，(1)空应填写“cmdcalculat

25、e_Click”。空处是求一元一次方程的解，若a=0,b气则x=-c/b，并将它转换字符串。因此(2)空应填写“Str$(-1*c/b)”或“Str(-1*c/b)”。(3)空处要为delta赋值，由(5)空的上一条语句可以判断，可以看出delta=b2-4ac,再通过这个值进行判断一元二次方程是否有解。因此(3)空应填写"b*b-4*a*c”或其等价形式。在一元二次方程中，若delta<0方程无解，因此(4)空应填写"delta<0"或其等价形式。(5)空是要写出一元二次方程的另一个解表达式，因此(5)空处应填写"Str$(-1)*b-Sq

26、r(deha)/(2*a)”。> 六、（B试题六（/B（总题数：1,分数：15.00）【说明】下面是一个Applet程序，程序的功能是在显示面板上输出字符串。当html页面被其他窗口遮挡后再次显示时，请给出输出结果。importjava.awt.*;importjava.U(1)/U.*;publicclassMyAppletU(2)/UAppletpublicvoidU(3)/U(Graphicsg)g.drawString(tip,20,40);tip="IamJavaApplet"publicvoidinit()tip="welcome"pr

27、ivateU(4)/Utip;<html><head><title>ASimpleApplet</title></head<body><appletcode="MyApplet.class"width=800height=400></applet></body></html网页输出U(5)/U(分数：15.00)填空项1:(正确答案：applet(2)extends(3)paint(4)String(5)IamJavaApplet)解析：解析所有的applet程序都要

28、导入包java.applet.*所有的applet程序继承自类applet。此处填入继承关键字extends。applet的程序的绘制函数是paint()。此处填入变量类型String。当html页面被其他窗口遮挡后再次显示时，变量tip被修改为"IamJavaApplet”,所以这时显示的结果是"IamJavaApplet"。4. 七、B试题七/B(总题数：1,分数：15.00)【说明】以下程序的功能是计算正方体、球体和圆柱体的表面积和体积并输出。程序由4个类组成:)和volum()，作为通用接口。【C+碓序】#include<iostream.h>

29、#defineprotected:doubleradius;public:container(doubleradius)virtualdoublesurface_area()=0;virtualdoublevelum()=0;class定义正方体类public:cube(doubleradius):container(radius);double6*radius*radius;doublevolum()returnradius*radius*radius;/U/定义球体类public:sphere(doubleradius):container(radius);*类cube、sphere和cy

30、linder分别表示正方体、球体和圆柱体；抽象类container为抽象类，提供了两个纯虚拟函数surface_area()pi3.1416classcontainercontainer:radius=radius;cube:U(1)/U/surface_area()returnclasssphere:U(2)doublesurface_area()returnU(3)/U;doublevolum()returnpi*radius*radiusradius*4/3;classcylinder:U(4)/U/定义圆柱体类doubleheight;public:cylinder(doublerad

31、ius,doubleheight):container(radius)container:height=height;doublesurface_area()return2*pi*radius*(height+radius);doublevolum()returnU(5)/U;voidmain()container*p;cubeobj1(5);sphereobj2(5);cylinderobj3(5,5);p=&obj1;cout<“正方体表面积”(vvp->surface_area()<<end1;contvv"正方体体积”vvp->volum

32、e()<<end1;p=&obj2;cout<v"球体表面积"vvp->surface_area()<<end1;coutvv"球体体积”vvp->volume()<<end1;p=&obj3;coutvv"球体表面积"vvp->surface_area()<<end1;coutvv"球体体积"vvp->volume()<<end1;(分数：15.00)填空项1:(正确答案:publiccontainer(2)publi

33、ccontainer)解析：(3)4*pi*radius*radius(4)publiccontainer(5)pi*radius*radius*height解析类cube、sphere和cylinder分别表示正方体、球体和圆柱体，它们都需要求各自的表面积和体积，而抽象类container提供纯虚拟函数surface_area()和velum()，所以类cube、sphere和cylinder都以类contain为基类，公有继承，所以(1)、(2)和(4)空应填入“publiccontainer”。(3)空处为类sphere中求表面积函数的返回值，所以根据球体表面积公式应填入"4*pi*radius*radius”。(5)空处为类cylinder中求圆柱体体积函数的返回值，所以根据圆柱体体积公式应填入"pi*radius*radius*height”。八