1、初级程序员下午试题-89 及答案解析(总分：120.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)1.【流程图说明】下面的流程(如图 1 所示)用 N-S 盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有 3 个成员：data, left 和 right。其查找的方法是：首先与树的根节点的元素值进行比较：若相等则找到，返回此结点的地址；若要查找的元素小于根节点的元素值，则指针指向此结点的左子树，继续查找；若要查找的元素大于根节点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。【算法说明】【流程图】将上题的排序二叉树中查找
2、元素的过程用递归的方法实现。其中 NODE 是自定义类型：（分数：15.00）填空项 1:_二、试题二(总题数：1，分数：15.00)2.【说明 2.1】L 为一个带头结点的循环链表。函数 deletenode(LinkList L, int c)的功能是删除 L 中数据域 data 的值大于 c 的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。【函数 2.1】LinkList deletenode(LinkList L, int c)LinkList Lc,p,pre;pre=L;p= (1) ;Lc=(LinkList)malloc(sizeof(Lis
3、tNode) );Lc-next=Lcwhile(p!=L)if(p-datac)(2) ;(3) ;Lc-next=p;p=pre-next;elsepre=p;p=pre-next;return Lc;【说明 2.2】递归函数 dec_to_k_2(int n, int k)的功能是将十进制正整数 n 转换成 k2k9)进制数，并打印。【函数 2.2】dec_to_k_2(int n, int k)/*将十进制正整数 n 转换成 k(2k9)进制数*/if(n!=0)dec_to_k_2( (4) ,k);printf(“%d“, (5) );（分数：15.00）填空项 1:_三、试题三(
4、总题数：1，分数：15.00)3.1】假设以带头结点的单循环链表作非递减有序线性表的存储结构。函数 deleteklist(LinkList head)的功能是删除表中所有数值相同的多余元素，并释放结点空间。例如：链表初始元素为：(7, 10，10，21，30，42，42，42，51，70)经算法操作后变为：(7，10，21，30，42，51，70)【函数 3.1】void deleteklist(LinkList head)LinkNode * p, * q;p=head-next;while(p!=head)q=p-next;while( (1) )(2) ;free(q);q=p-nex
5、t;p=p-next;【说明 3.2】已知一棵完全二叉树存放于一个一维数组 Tn中，Tn中存放的是各结点的值。下面的程序的功能是：从 T0开始顺序读出各结点的值，建立该二叉树的二叉链表表示。【函数 3.2】#includeistream.h typedef struct node int data;stuct node leftChild, rightchild;BintreeNode;typedef BintreeNode * BinaryTree;void ConstrncTree(int T, int n, int i, BintreeNode * /*置根指针为空*/elseptr=-
6、(BTNode * )malloc(sizeof(BTNode) )ptr-data=Ti;ConstrucTree(T,n,2, i+1, (4) );ConstrucTree(T,n, (5) ,ptr-rightchild);main(void)/*根据顺序存储结构建立二叉链表*/Binarytree bitree;int n;printf(“please enter the number of node: /n%s“ ;n);int* A = (int *) malloc(n * sizeof(int);for(int i=0;in;i+)scanf(“ %d,A+i); /*从键盘输
7、入结点值*/for(int i=0;in;i+)printf(“ %d“,Ai);ConstructTree(A, n,0, bitree);（分数：15.00）填空项 1:_四、试题四(总题数：1，分数：15.00)4.【说明】该程序的功能是从文件 IN.DAT 中读取一篇英文文章存入到字符串数组 xx 中，以行为单位对行中以空格或标点符号为分隔的所有单词进行倒排。最后把已处理的字符串(应不含标点符号)仍按行重新存入字符串数组 xx 中，最后把结果 xx 输出到文件 OUT6.DAT 中。例如：原文：You He MeI am a student结果：Me He Youstudent a a
8、m I原始数据文件存放的格式是：每行的宽度均小于 80 个字符，含标点符号和空格。【函数】#includestring.h #includeconio.h #includectype.h#includestdio.h char xx50 80;int maxline=0; /*文章的总行数*/int ReaaDat(void);void WriteDat(void);void StrOL(void)char * p1, * p2,t80;int i;for(i=0;imaxline;i+)p1=xxi;t0=0;while(*p1)p1+;while(p1=xxi)while(!isalpha
9、(*p1) p2=p1;while( (1) )p1-;if(p1=xxi)if(isalpha(*p1)p1-;else if(!isalpha(*(p1+1)break;p2+;(2) ;strcat(t, p1+1);strcat(t,“ “);strcpy(xxi,t);void main( )if( (3) ) printf(“数据文件 in.dat 不能打开!/n/007“ );return;StroL();writeDat();getch();int ReadDat(void)FILE * fp;int i =0;char * p;if(fp=fopen(“e:/a/in.dat
10、“,“ r“ )=NULL)return 1;while(fgets(xxi,80,fp)!=NULL) p=strchr(xxi,/n)if(p)*p=0;i+;maxline= (4) fclose(fp);return 0;void WriteDat(void)FILE * fp;int i;fp=fopen(“e:/a/out6,dat“,“w“);for(i=0;i (5) ;i+)printf(“%s/n“,xxi);fprintf(fp,“%s/n“,xxi)fclose(fp)（分数：15.00）填空项 1:_五、试题五(总题数：1，分数：15.00)5.【说明】该应用程序是用
11、来求一元二次方程和一元一次方程的，其运行如图 2 所示。（分数：15.00）填空项 1:_六、试题六(总题数：1，分数：15.00)6.【说明】下面是一个 Applet 程序，程序的功能是在显示面板上输出字符串。当 html 页面被其他窗口遮挡后再次显示时，请给出输出结果。import java.awt.*;import java. (1) . *;public class MyApplet (2) Applet public void (3) (Graphics g) g.drawString(tip,20,40);tip =“I am Java Applet“;public void in
12、it() tip =“welcome“; private (4) tip;htmlheadtitle A Simple Applet /title/headbodyapplet code=“MyApplet.class“ width=800 height=400/applet/body/html网页输出 (5) （分数：15.00）填空项 1:_七、试题七(总题数：1，分数：15.00)7.【说明】以下程序的功能是计算正方体、球体和圆柱体的表面积和体积并输出。程序由 4 个类组成：类 cube、sphere 和 cylinder 分别表示正方体、球体和圆柱体；抽象类 container为抽象类
13、，提供了两个纯虚拟函数 surface_area()和 volum()，作为通用接口。【C+程序】#includeiostream.h #define pi 3.1416class container protected: double radius; public:container(double radius) container:radius=radius;virtual double surface_area()=0;virtual double velum()=0;class cube: (1) /定义正方体类public:cube(double radius):container(
14、radius);double surface_area () return 6 * radius * radius;double volum() return radius * radius * radius;class sphere: (2) /定义球体类public:sphere(double radius): container(radius);double surface_area() return (3) ;double volum() return pi * radius * radius * radius * 4/3;class cylinder: (4) /定义圆柱体类doub
15、le height;public:cylinder(double radius,double height):container(radius)container:height=height;double surface_are a () return 2 * pi * radius * (height+radius); double volum () return (5) ;void main()container * p;cube obj1 (5);sphere obj2(5);cylinder obj3(5,5);p=cout“正方体表面积”(p-surface_area()end1;c
16、ont“正方体体积”p-volume()end1;p=cout“球体表面积”p-surface_area()end1;cout“球体体积”p-volume()end1;p=cout“球体表面积”p-surface_area()end1;cout“球体体积”p-volume()end1;（分数：15.00）填空项 1:_八、试题八(总题数：1，分数：15.00)8.【说明 8.1】以下程序的功能是：生成 20 个 200300 之间的随机整数，输出其中能被 5 整除的数并求出它们的和。【程序代码 8.1】Private Sub Command1_Click()For i=1 To 20x=Int
17、( (1) *200+100)If (2) =0 ThenPrint xS=S+ (3) End IfNext iPrint“Sum=“;SEnd Sub【说明 8.2】程序 8.2 运行后，单击窗体，则在窗体上显示的内容是：a= (4) 和 b= (5) 。【程序代码 8.2】Private Sub Form_Click()Dim a As Integer,b As Integera=20:b=50p1 a,bp2 a,bp3 a,bPrint“a=“;a,“b=“;bEnd SubSub p1(x As Integer, ByValy As Integer)x=x+l0y=y+20End
18、SubSub p2(ByValAs Integer, y As Integer)x=x+l0y=y+20End SubSub p3(ByValAs Integer, ByVal y As Integer)x=x+10y=y+20End Sub（分数：15.00）填空项 1:_初级程序员下午试题-89 答案解析(总分：120.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)1.【流程图说明】下面的流程(如图 1 所示)用 N-S 盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有 3 个成员：data, left 和 right。其查找的方法是：首先与树的根节点的元素值
19、进行比较：若相等则找到，返回此结点的地址；若要查找的元素小于根节点的元素值，则指针指向此结点的左子树，继续查找；若要查找的元素大于根节点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。【算法说明】【流程图】将上题的排序二叉树中查找元素的过程用递归的方法实现。其中 NODE 是自定义类型：（分数：15.00）填空项 1:_ （正确答案：p=p-left (2)ptr=p-right (3)return P (4) return SearchSortTree(tree-left ) (5)return SearchSortTree(tree-right)
20、）解析：解析 所谓二叉排序树，指的是一棵为空的二叉树，或者是一棵具有如下特性的非空二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值。若它的右子树非空，则右子树上所有结点的值均大干根结点的值。左、右子树本身又各是一棵二叉排序树。先来分析流程图。在流程图中只使用一个变量 p，并作为循环变量来控制循环，所以循环体中必须修改这个值。当进入循环时，首先判断 p 是不是为空和该结点是不是要找的结点，如果这两个条件有一个满足就退出循环，返回 prt，(如果是空，则返回 NULL，说明查询失败；否则返回键值所在结点的指针。)因此(3)空处应当填写“return p”。如果两个条件都不满足，就用
21、查找键值 e 与当前结点的关键字进行比较，小的话，将指针 p 指向左子树继续查找，大的话将指针 P 指向右子树继续查找。于是，(1)空处应当填写“p=p-left”，(2)空处应当填写“p=p-right”。再来分析程序。虽然是递归算法，但实现思路和非递归是一样。首先用查找键值 e 与树根结点的关键字比较，如果值小的话，就在左子树中查找(即返回在左子树中查找结果)；如果值大的话在右子树中查找(即返回在右子树中查找结果)；如果相等的活就返回树根指针。因此(4)、(5)空分别应填写“return SearehSortTree(tree-left)”和“return SearehSoaTree(tr
22、ee-right)”。二、试题二(总题数：1，分数：15.00)2.【说明 2.1】L 为一个带头结点的循环链表。函数 deletenode(LinkList L, int c)的功能是删除 L 中数据域 data 的值大于 c 的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。【函数 2.1】LinkList deletenode(LinkList L, int c)LinkList Lc,p,pre;pre=L;p= (1) ;Lc=(LinkList)malloc(sizeof(ListNode) );Lc-next=Lcwhile(p!=L)if(p-
23、datac)(2) ;(3) ;Lc-next=p;p=pre-next;elsepre=p;p=pre-next;return Lc;【说明 2.2】递归函数 dec_to_k_2(int n, int k)的功能是将十进制正整数 n 转换成 k2k9)进制数，并打印。【函数 2.2】dec_to_k_2(int n, int k)/*将十进制正整数 n 转换成 k(2k9)进制数*/if(n!=0)dec_to_k_2( (4) ,k);printf(“%d“, (5) );（分数：15.00）填空项 1:_ （正确答案：pre-next 或 L-next (2)pre-next=p-ne
24、xt(3)p-next=Lc-next(4) n/k (5)n% k）解析：解析 这一题共有两个函数，第一个函数是考查链表的删除和插入操作，第二个函数是考查递归函数。先看第一个函数。(1)空所在语句是对指针 p 赋初值，通过下面的程序可以判断指针 pre 所指的结点是指针 p 所指的结点前驱结点，因此 (1)空处应填写“pre-next”或“Lnext”。(2)、(3)空所在的语句块是处理当指针 p 所指的结点是一个大于 c 的结点，则将该结点从链表 L 中删除，再将它插入到链表c 中。由指针 pre 和指针 p 的关系，从链表中删除指针 p 所指结点很简单，只需将指针 pre 的 next
25、域修改为指针 p 的 next 域即可，因此(2)空处应填写“prenextPnext”或其等价形式。将指针 p所指的结点插入到链表 Lc 的过程是，先将指针 P 的 next 域指向指针 Lc 的 next 所指的结点，再将指针Lc 的 next 指向指针 p 所指的结点。因此(3)空处应填写“p-next=Lc-next”或其等价形式。再来分析第二个函数。将十进制正整数转换成 k 进制数，采用除 k 取余法。最开始得到余数作为 k 进制数的最低位，最后得到的余数作为 k 进制数的最高位。用 n 不断地除以 k，直到商为 0。转换所得到的 k进制数是从低位开始生成，而输出则应该从高位开始。根
26、据这一特点，用递归法求解时，先应将 n/k 转换成 k 进制，再输出 n%k。因此 (4)空、(5)空处分别填写“n/k”、“n% k。当然这个问题也可以通过非递归的算法来完成，这样在转换过程中，需要一个栈来暂存 n 除以 k 所得到的各位余数。三、试题三(总题数：1，分数：15.00)3.1】假设以带头结点的单循环链表作非递减有序线性表的存储结构。函数 deleteklist(LinkList head)的功能是删除表中所有数值相同的多余元素，并释放结点空间。例如：链表初始元素为：(7, 10，10，21，30，42，42，42，51，70)经算法操作后变为：(7，10，21，30，42，5
27、1，70)【函数 3.1】void deleteklist(LinkList head)LinkNode * p, * q;p=head-next;while(p!=head)q=p-next;while( (1) )(2) ;free(q);q=p-next;p=p-next;【说明 3.2】已知一棵完全二叉树存放于一个一维数组 Tn中，Tn中存放的是各结点的值。下面的程序的功能是：从 T0开始顺序读出各结点的值，建立该二叉树的二叉链表表示。【函数 3.2】#includeistream.h typedef struct node int data;stuct node leftChild,
28、 rightchild;BintreeNode;typedef BintreeNode * BinaryTree;void ConstrncTree(int T, int n, int i, BintreeNode * /*置根指针为空*/elseptr=-(BTNode * )malloc(sizeof(BTNode) )ptr-data=Ti;ConstrucTree(T,n,2, i+1, (4) );ConstrucTree(T,n, (5) ,ptr-rightchild);main(void)/*根据顺序存储结构建立二叉链表*/Binarytree bitree;int n;pri
29、ntf(“please enter the number of node: /n%s“ ;n);int* A = (int *) malloc(n * sizeof(int);for(int i=0;in;i+)scanf(“ %d,A+i); /*从键盘输入结点值*/for(int i=0;in;i+)printf(“ %d“,Ai);ConstructTree(A, n,0, bitree);（分数：15.00）填空项 1:_ （正确答案：q!= head int maxline=0; /*文章的总行数*/int ReaaDat(void);void WriteDat(void);void
30、 StrOL(void)char * p1, * p2,t80;int i;for(i=0;imaxline;i+)p1=xxi;t0=0;while(*p1)p1+;while(p1=xxi)while(!isalpha(*p1) p2=p1;while( (1) )p1-;if(p1=xxi)if(isalpha(*p1)p1-;else if(!isalpha(*(p1+1)break;p2+;(2) ;strcat(t, p1+1);strcat(t,“ “);strcpy(xxi,t);void main( )if( (3) ) printf(“数据文件 in.dat 不能打开!/n
31、/007“ );return;StroL();writeDat();getch();int ReadDat(void)FILE * fp;int i =0;char * p;if(fp=fopen(“e:/a/in.dat“,“ r“ )=NULL)return 1;while(fgets(xxi,80,fp)!=NULL) p=strchr(xxi,/n)if(p)*p=0;i+;maxline= (4) fclose(fp);return 0;void WriteDat(void)FILE * fp;int i;fp=fopen(“e:/a/out6,dat“,“w“);for(i=0;i
32、 (5) ;i+)printf(“%s/n“,xxi);fprintf(fp,“%s/n“,xxi)fclose(fp)（分数：15.00）填空项 1:_ （正确答案：isalpha(* p1)import java. (1) . *;public class MyApplet (2) Applet public void (3) (Graphics g) g.drawString(tip,20,40);tip =“I am Java Applet“;public void init() tip =“welcome“; private (4) tip;htmlheadtitle A Simpl
33、e Applet /title/headbodyapplet code=“MyApplet.class“ width=800 height=400/applet/body/html网页输出 (5) （分数：15.00）填空项 1:_ （正确答案：applet (2)extends (3)paint (4)String (5)I am Java Applet）解析：解析 所有的 applet 程序都要导入包 java.applet*所有的 applet 程序继承自类 applet。此处填入继承关键字 extends。applet 的程序的绘制函数是 paint()。此处填入变量类型 String
34、。当 html 页面被其他窗口遮挡后再次显示时，变量 tip 被修改为“I am Java Applet”，所以这时显示的结果是“I am Java Applet”。七、试题七(总题数：1，分数：15.00)7.【说明】以下程序的功能是计算正方体、球体和圆柱体的表面积和体积并输出。程序由 4 个类组成：类 cube、sphere 和 cylinder 分别表示正方体、球体和圆柱体；抽象类 container为抽象类，提供了两个纯虚拟函数 surface_area()和 volum()，作为通用接口。【C+程序】#includeiostream.h #define pi 3.1416class
35、container protected: double radius; public:container(double radius) container:radius=radius;virtual double surface_area()=0;virtual double velum()=0;class cube: (1) /定义正方体类public:cube(double radius):container(radius);double surface_area () return 6 * radius * radius;double volum() return radius * ra
36、dius * radius;class sphere: (2) /定义球体类public:sphere(double radius): container(radius);double surface_area() return (3) ;double volum() return pi * radius * radius * radius * 4/3;class cylinder: (4) /定义圆柱体类double height;public:cylinder(double radius,double height):container(radius)container:height=he
37、ight;double surface_are a () return 2 * pi * radius * (height+radius); double volum () return (5) ;void main()container * p;cube obj1 (5);sphere obj2(5);cylinder obj3(5,5);p=cout“正方体表面积”(p-surface_area()end1;cont“正方体体积”p-volume()end1;p=cout“球体表面积”p-surface_area()end1;cout“球体体积”p-volume()end1;p=cout“
38、球体表面积”p-surface_area()end1;cout“球体体积”p-volume()end1;（分数：15.00）填空项 1:_ （正确答案：public container (2)public container(3) 4 * pi * radius * radius (4) public container(5)pi * radius * radius * height）解析：解析 类 cube、sphere 和 cylinder 分别表示正方体、球体和圆柱体，它们都需要求各自的表面积和体积，而抽象类 container 提供纯虚拟函数 surface_area()和 velum
39、()，所以类 cube、sphere 和cylinder 都以类 contain 为基类，公有继承，所以(1)、(2)和(4)空应填入“public container”。(3)空处为类 sphere 中求表面积函数的返回值，所以根据球体表面积公式应填入“4*pi*radius*radius”。(5)空处为类 cylinder 中求圆柱体体积函数的返回值，所以根据圆柱体体积公式应填入“pi*radius*radius*height”。八、试题八(总题数：1，分数：15.00)8.【说明 8.1】以下程序的功能是：生成 20 个 200300 之间的随机整数，输出其中能被 5 整除的数并求出它们
40、的和。【程序代码 8.1】Private Sub Command1_Click()For i=1 To 20x=Int( (1) *200+100)If (2) =0 ThenPrint xS=S+ (3) End IfNext iPrint“Sum=“;SEnd Sub【说明 8.2】程序 8.2 运行后，单击窗体，则在窗体上显示的内容是：a= (4) 和 b= (5) 。【程序代码 8.2】Private Sub Form_Click()Dim a As Integer,b As Integera=20:b=50p1 a,bp2 a,bp3 a,bPrint“a=“;a,“b=“;bEnd
41、 SubSub p1(x As Integer, ByValy As Integer)x=x+l0y=y+20End SubSub p2(ByValAs Integer, y As Integer)x=x+l0y=y+20End SubSub p3(ByValAs Integer, ByVal y As Integer)x=x+10y=y+20End Sub（分数：15.00）填空项 1:_ （正确答案：Rnd 或 Rnd(n)，其中 n 为任意整数(2)x Mod 5 或 Int(x/5)-x/5 或 x/5-Int(x/5)或 CInt(x/5)-x/5 或 x/5-CInt(x/5)或
42、Round(x/5)-x/5 或x/5- Round(x/5)或 x-(x/5)*5 或(x/5)*5-x 或 Fix(x/5)-x/5 或 x/5-Fix(x-5)(3)x (4)30 (5)70）解析：解析 x 用来存放 200300 之间的随机整数，因此，赋给 x 的表达式是 Int(Rnd*200+100)，即(1)空填“Rnd”；下面的 if 语句用来判断能被 5 整除的数，因此(2)空填“x Mod 5”；S 用来表示能被 5 整除数的累加和，因此(3)空填“x”。程序 5.2 主要考过程参数的值参(传值)和变参(传地址)概念。参数前有 Byval 限定词表示参数传递是传值，否则是传地址。参数传递是传值时，被调过程不能改变主调过程的参数值；而参数传递是传地址时，被调过程改变主调过程的参数值。本题中，过程 P1 的第一个参数是传地址，它在过程中的变化将带到主调程序，而第二个参数是传值，当过程执行完后，主调过程的参数值不变，因此 p1 a，b 这条语句执行后，a的值是 30，b 的值是 50；同理，语句 p2 a，b 执行后，a 的值是 30， b 的值是 70；语句 p3 a，b 执行后，a 的值仍是 30，b 的值仍是 70。
