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