1、初级程序员下午试题-100 及答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明下面的流程图，用来完成求字符串 t 在 s 中最右边出现的位置。其思路是：做一个循环，以 s 的每一位作为字符串的开头和 t 比较，如果两字符串的首字母是相同的，则继续比下去，如果一直到 t 的最后一个字符也相同，则说明在 s 中找到了一个字符串 t; 如果还没比较到 t 的最后一个字符，就已经出现字符串不等的情况，则放弃此次比较，开始新一轮的比较。当在 s 中找到一个字符串 t 时，不应停止寻找(因为要求的是求 t 在 s 中最右边出现的位置)，应先记录这个位置 po
2、s，然后开始新一轮的寻找，若还存在相同的字符串，则更新位置的记录，直到循环结束，输出最近一次保存的位置。如果 s 为空或不包含 t，则返回-1。注：返回值用 pos 表示。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_二、试题二(总题数：1，分数：15.00)函数 2.1 说明函数 void sort(int arry,int n)的功能是对数组 a 中的 arry0arryn-1这 n 个元素进行排序。排序过程如下：第一趟对所有的偶数下标 x，比较 arrx和 arry x+1，若 arryxarryx+1，则将两者交换; 第二趟对所有的奇数下标
3、y，比较 arryy和 arryy+1，若 arryyarryy+1，则将两者交换; 第三趟对偶数下标，第四趟对奇数下标，依次类推，直至整个数组元素有序排列为止。函数 2.1void sort (int arry,int n)int i，j，tag=1;for(j=0; jn; j+)for(i= (1) ;in-1; (2) ) if (arry i arry i+1) t=arry i ;arry il =arry i+1 ;arry i+1 =t ;tag=0 ;tag+;if( (3) )break;函数 2.2 说明这是一棵二叉树排序查找元素的程序，查找的方法是：首先与树的根结点的元
4、素进行比较，若相等则找到，返回此结点的地址; 若要查找的元素小于根结点的元素值，则指针指向此结点的左子树，继续查找; 若要查找的元素大于根结点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。本题使用递归方法实现。函数 2.2typedef struct node int data;struct node *left;struct node *right;NODE;NODE *SearchSortTree(NODE *tree,int e)if (tree ! =NULL) if (tree-datae)(4) ;else if(tree-datae)
5、5) ;else return tree;return tree;（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_三、试题三(总题数：1，分数：15.00)说明已知一棵二叉树用二叉链表存储，t 指向根结点，p 指向树中任一结点。下列算法为输出从 t 到 p 之间路径上的结点。函数#define MaxSize 1000typedef struct nodeTelemType data;struct node *lchild,*rchild;BiNode, *BiTree;void Path(BiTree t， BiNode *p)BiTree *st
6、ack EMaxsize, *stack1 maxsize, *q;int tagMaxsizel, top=0, top1;q=t;/*通过前序遍历发现 P*/do while (q!=NULLq! =p)/*扫描左孩子，且相应的结点不为 p*/(1) ; stack top =q;tag top =0;(2) ; if (top0)if (stack top=P) break; /*找到 p，栈底到栈顶为 t 到 p*/if(tagtop=1) top-;else q=stacktop;q=q-rchild;tag top =1;(3) ;top-; top1=0; while(top0)
7、 q=stack top; /*反向打印准备*/top1+;(4) ;top-; while( (5) ) /*打印栈的内容*/q=stack1top1; printf (q-data); top1-;（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_四、试题四(总题数：1，分数：15.00)说明设一个环上有编号为 0n-1 的 n 粒颜色不尽相同的珠子(每粒珠子颜色用字母表示，n 粒珠子的颜色由输入的字符串表示)。从环上的某两粒珠子间剪开，则环上珠子形成一个序列然后按以下规则从序列中取走珠子：首先从序列左端取走所有连续的同色珠子; 然后从序列右端在剩下
8、的珠子中取走所有连续的同色珠子，两者之和为该剪开处可取走珠子的粒数。在不同位置剪开，能取走的珠子也不尽相同。本程序所求的是在环上哪个位置剪开，按上述规则可取走的珠子粒数最多。程序中用数组存储字符串。例如：10 粒珠子颜色对应字符串为“aaabbbadcc”，在 0 号珠子前剪开，序列为 aaabbbadcc，从左端取走3 粒 a 色珠子，从右端取走 2 粒 c 色珠子，共取走 5 粒珠子。若在 3 号珠子前剪开，即 bbbadccaaa，共取走 6 粒珠子。函数int count (char *s,int start,int end)int i,c=0, color=sstart,step=(
9、startend)?-1:1;for i=start; si =color; i+=step)if (step0 iend | (1) ) break;(2) ; return c：void main()char t，s120;int i,j,c,len,maxc,cut=0;printf(“请输入环上代表不同颜色珠子字符串：“);scanf(“%s”，s);len=strlen(s); for (i=maxc=0; ilen; i+)( /*尝试不同的剪开方式*/c=count (s, 0,len-1); if(clen) c+=count( (3) );if (cmaxc)cut=i; m
10、axc=c; /*数组 s 的元素循环向左移动一个位置*/t=s0;for(j=1; jlen; j+) (4) ;(5) ;printf(“在第%d 号珠子前面剪开，可以取走%d 个珠子./n“，cut,maxc);（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_五、试题五(总题数：1，分数：15.00)说明下面程序定义了一个类 Point 及其成员函数，然后从类 Point 派生出类 Circle 及其成员函数。C+程序/POINT. H#ifndef POINT_H# define POINT_Hclass Point public:Point
11、float x=0,float y=0) ;void setPoint (float, float) ;float getX () const return x; float getY () const return y; protected:float :x,y;#endif/POINT.CPP#include iostream.h#include “ point .h “Point : Point (float a, float b)x=a; y=bvoid Point:setPoint(float a,float b)x=a; y=b/CIRCLE . H#ifndef CIRCLE_
12、H#define CIRCLE_H#include “point.h“class Circle: (1) public :Circle (float r=0.0, float x=0, float y=0) ;void setRadius (float) ;float getRadius () const;float area() const;protected:float radius;/CIRCLE.CPP#include “iostream.h“#include “circle .h “Circle:Circle(float r,float a,float b): (2) radius=
13、r; void Circle:setRadius (float r)radius=r; float Circle:getRadius () constreturn radius; float Circle:area () constreturn 3 .14159*radius*radius ; /text.cpp#include iostream.h#include “ point .h “#include “ circle .h “main ()Circle c(2.5,3.7,4.3) ;cout “X coordinate is “c.getX ()/n Radius is: “c.ge
14、tRadius ();(3) ; /设置新的圆心 (2,2) 。Point pRef=c;cout“/n Circle printed as a point is:“ (4) “.“ (5) “;（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_六、试题六(总题数：1，分数：15.00)说明下面 Application 程序用 while 循环从键盘读入字符，记录输入的字符数并输出读入的字符，当输入字符“0”时结束 while 循环，同时结束程序。Java 程序import java.io.*;public class ContinuateInputpu
15、blic (1) void main(String args) (2) IOExceptionint ch;int counter=0; System.out .println(“请输入字符(输入 0 结束)“); while (char) (ch=System.in. (3) ) != 0)counter+;System.out .println ( (4) )ch) ;System.out .println () ;System.out.println (“counted “+counter+“ total bytes. “) ;System.out . (5) ;（分数：15.00）填空
16、项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_初级程序员下午试题-100 答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明下面的流程图，用来完成求字符串 t 在 s 中最右边出现的位置。其思路是：做一个循环，以 s 的每一位作为字符串的开头和 t 比较，如果两字符串的首字母是相同的，则继续比下去，如果一直到 t 的最后一个字符也相同，则说明在 s 中找到了一个字符串 t; 如果还没比较到 t 的最后一个字符，就已经出现字符串不等的情况，则放弃此次比较，开始新一轮的比较。当在 s 中找到一个字符串 t 时，不应停止寻找(因为要求
17、的是求 t 在 s 中最右边出现的位置)，应先记录这个位置 pos，然后开始新一轮的寻找，若还存在相同的字符串，则更新位置的记录，直到循环结束，输出最近一次保存的位置。如果 s 为空或不包含 t，则返回-1。注：返回值用 pos 表示。（分数：15.00）填空项 1:_ （正确答案：pos=-1;）解析：填空项 1:_ （正确答案：si!=/0;）解析：填空项 1:_ （正确答案：j=tk;）解析：填空项 1:_ （正确答案：k0;）解析：填空项 1:_ （正确答案：pos=i;）解析：解析 本试题考查流程图。题目中说明，如果 s 中不包含 t，则返回-1，由流程图可以看出，如果空(2)的条件
18、不满足，流程图会直接跳到最后 Return pos，所以，在开始进行查找之前，就要先将 pos 置-1，所以空(1)填入 pos=-1。循环开始，空(2)保证的条件应该是 si不是空的，即空(2)填入 si!=/0。下面就开始进行比较，由于要输出的是最右边出现的位子，所以当第一次比较到相同的字符时是不能输出，只要暂时把保存着，即空(5)填入 pos=i，然后进行下一次循环，当又出现相同的字符串时，就将 pos 的值更新，如果一直到最后都没有再次出现相同的字符串，就把 pos 输出。当比较到第一个相同的字符时，要继续比较下去，看是不是 t和 s 的每一个字符全相同，所以(3)应填入 sj=tk。
19、在什么情况下能说明 t 和 s 完全相同呢?就是当 t-直比较到最后一个字符即空格时，并且 k 大于 0(因为如果 k 等于 0，则说明第一个字母就不相同，根本没有开始比较)，所以(4)应填入 k0。二、试题二(总题数：1，分数：15.00)函数 2.1 说明函数 void sort(int arry,int n)的功能是对数组 a 中的 arry0arryn-1这 n 个元素进行排序。排序过程如下：第一趟对所有的偶数下标 x，比较 arrx和 arry x+1，若 arryxarryx+1，则将两者交换; 第二趟对所有的奇数下标 y，比较 arryy和 arryy+1，若 arryyarry
20、y+1，则将两者交换; 第三趟对偶数下标，第四趟对奇数下标，依次类推，直至整个数组元素有序排列为止。函数 2.1void sort (int arry,int n)int i，j，tag=1;for(j=0; jn; j+)for(i= (1) ;in-1; (2) ) if (arry i arry i+1) t=arry i ;arry il =arry i+1 ;arry i+1 =t ;tag=0 ;tag+;if( (3) )break;函数 2.2 说明这是一棵二叉树排序查找元素的程序，查找的方法是：首先与树的根结点的元素进行比较，若相等则找到，返回此结点的地址; 若要查找的元素小
21、于根结点的元素值，则指针指向此结点的左子树，继续查找; 若要查找的元素大于根结点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。本题使用递归方法实现。函数 2.2typedef struct node int data;struct node *left;struct node *right;NODE;NODE *SearchSortTree(NODE *tree,int e)if (tree ! =NULL) if (tree-datae)(4) ;else if(tree-datae)(5) ;else return tree;return tr
22、ee;（分数：15.00）填空项 1:_ （正确答案：j%2）解析：填空项 1:_ （正确答案：i+=2）解析：填空项 1:_ （正确答案：tag2 或 tag=3 或 tag=3）解析：填空项 1:_ （正确答案：return SearchSortTree(tree-left,e)）解析：填空项 1:_ （正确答案：return SearchSortTree(tree-right,e)）解析：解析 对于函数 1，空(1)和空(2)要求填写内循环变量初值和增量。循环变量的初值是由外循环的循环变量决定的。因为第一趟初值为 0，第二趟为 1，第三趟又为 0，因此空(1)为 j%2，因为一次比较两个
23、元素，所以循环增量为 2，空(2)为 i+=2。当连续两趟没有数据交换时就说明该数组已经有序了，可以提前退出循环，由 tag 标注，空(3)为 tag2 或 tag=3 或 tag=3。对于函数 2，首先查找键值 e 与树根结点的关键字比较，如果值小的话，就在左子树中查找，空(4)为return SearchSortTree(tree-left，e),如果值大的话，就在右子树中查找，空(5)为 return SearchSortTree(tree-right, e),如果相等的话就返回树根指针。三、试题三(总题数：1，分数：15.00)说明已知一棵二叉树用二叉链表存储，t 指向根结点，p 指向
24、树中任一结点。下列算法为输出从 t 到 p 之间路径上的结点。函数#define MaxSize 1000typedef struct nodeTelemType data;struct node *lchild,*rchild;BiNode, *BiTree;void Path(BiTree t， BiNode *p)BiTree *stack EMaxsize, *stack1 maxsize, *q;int tagMaxsizel, top=0, top1;q=t;/*通过前序遍历发现 P*/do while (q!=NULLq! =p)/*扫描左孩子，且相应的结点不为 p*/(1) ;
25、 stack top =q;tag top =0;(2) ; if (top0)if (stack top=P) break; /*找到 p，栈底到栈顶为 t 到 p*/if(tagtop=1) top-;else q=stacktop;q=q-rchild;tag top =1;(3) ;top-; top1=0; while(top0) q=stack top; /*反向打印准备*/top1+;(4) ;top-; while( (5) ) /*打印栈的内容*/q=stack1top1; printf (q-data); top1-;（分数：15.00）填空项 1:_ （正确答案：top+
26、解析：填空项 1:_ （正确答案：q=q-lchild）解析：填空项 1:_ （正确答案：while(top0)）解析：填空项 1:_ （正确答案：stack1top1=q）解析：填空项 1:_ （正确答案：top10）解析：解析 本题本质上是对二叉树的前序遍历进行考核，但不是简单地进行前序遍历，而是仅遍历从根结点到给定的结点 p 为止。本题采用非递归算法来实现，其主要思想是：初始化栈; 根结点进栈，栈不空则循环执行以下步骤直到发现结点 p; 当前结点不为空且不为 P 进栈; 栈顶为 p，则结束，否则转; 若右子树访问过，则栈顶的右孩子为当前结点，转。扫描左孩子，当相应的结点不为 P 时进栈
27、所以空(1)填 top+，空(2)填 q=q-1child。在栈不为空时则一直在 do.while 循环中查找，因此空(3)填 while(top0)。在进行反向打印准备时，读取 stacktop的信息放到 stack1top1中，即空(4)填 stack1top1=q。打印栈中所有内容，所以空(5)填 top10。四、试题四(总题数：1，分数：15.00)说明设一个环上有编号为 0n-1 的 n 粒颜色不尽相同的珠子(每粒珠子颜色用字母表示，n 粒珠子的颜色由输入的字符串表示)。从环上的某两粒珠子间剪开，则环上珠子形成一个序列然后按以下规则从序列中取走珠子：首先从序列左端取走所有连续的同色
28、珠子; 然后从序列右端在剩下的珠子中取走所有连续的同色珠子，两者之和为该剪开处可取走珠子的粒数。在不同位置剪开，能取走的珠子也不尽相同。本程序所求的是在环上哪个位置剪开，按上述规则可取走的珠子粒数最多。程序中用数组存储字符串。例如：10 粒珠子颜色对应字符串为“aaabbbadcc”，在 0 号珠子前剪开，序列为 aaabbbadcc，从左端取走3 粒 a 色珠子，从右端取走 2 粒 c 色珠子，共取走 5 粒珠子。若在 3 号珠子前剪开，即 bbbadccaaa，共取走 6 粒珠子。函数int count (char *s,int start,int end)int i,c=0, color
29、sstart,step=(startend)?-1:1;for i=start; si =color; i+=step)if (step0 iend | (1) ) break;(2) ; return c：void main()char t，s120;int i,j,c,len,maxc,cut=0;printf(“请输入环上代表不同颜色珠子字符串：“);scanf(“%s”，s);len=strlen(s); for (i=maxc=0; ilen; i+)( /*尝试不同的剪开方式*/c=count (s, 0,len-1); if(clen) c+=count( (3) );if (
30、cmaxc)cut=i; maxc=c; /*数组 s 的元素循环向左移动一个位置*/t=s0;for(j=1; jlen; j+) (4) ;(5) ;printf(“在第%d 号珠子前面剪开，可以取走%d 个珠子./n“，cut,maxc);（分数：15.00）填空项 1:_ （正确答案：step0 end）解析：填空项 1:_ （正确答案：+c）解析：填空项 1:_ （正确答案：s，len-1，c）解析：填空项 1:_ （正确答案：sj-1=sj）解析：填空项 1:_ （正确答案：slen-1=t）解析：解析 依据取珠子个数最多的规则，count 函数每次从左或从右取出相同颜色的珠子，因
31、此从右到左的条件为 step0 iend，即空(i)应填 step0 iend。当是同色珠子时，计数值加一，所以空(2)填+c。从右到左计算时，函数 count 调用的实参次序为 s，len-1，c。即空(3)应填 s，len-1，c。在尝试不同的剪开方式时，数组 s 的元素要循环向左移动一个位置，则空(4)填 sj-1=sj，空(5)填 slen-1=t。五、试题五(总题数：1，分数：15.00)说明下面程序定义了一个类 Point 及其成员函数，然后从类 Point 派生出类 Circle 及其成员函数。C+程序/POINT. H#ifndef POINT_H# define POINT_
32、Hclass Point public:Point (float x=0,float y=0) ;void setPoint (float, float) ;float getX () const return x; float getY () const return y; protected:float :x,y;#endif/POINT.CPP#include iostream.h#include “ point .h “Point : Point (float a, float b)x=a; y=bvoid Point:setPoint(float a,float b)x=a; y=b
33、/CIRCLE . H#ifndef CIRCLE_H#define CIRCLE_H#include “point.h“class Circle: (1) public :Circle (float r=0.0, float x=0, float y=0) ;void setRadius (float) ;float getRadius () const;float area() const;protected:float radius;/CIRCLE.CPP#include “iostream.h“#include “circle .h “Circle:Circle(float r,flo
34、at a,float b): (2) radius=r; void Circle:setRadius (float r)radius=r; float Circle:getRadius () constreturn radius; float Circle:area () constreturn 3 .14159*radius*radius ; /text.cpp#include iostream.h#include “ point .h “#include “ circle .h “main ()Circle c(2.5,3.7,4.3) ;cout “X coordinate is “c.
35、getX ()/n Radius is: “c.getRadius ();(3) ; /设置新的圆心 (2,2) 。Point pRef=c;cout“/n Circle printed as a point is:“ (4) “.“ (5) “;（分数：15.00）填空项 1:_ （正确答案：public Point）解析：填空项 1:_ （正确答案：Point(a，b)）解析：填空项 1:_ （正确答案：c.setPoint(2，2)）解析：填空项 1:_ （正确答案：pRef.getX(),）解析：填空项 1:_ （正确答案：pRef.getY()）解析：解析 本题以 C+语言为载体，考
36、查面向对象程序设计中的几个重要概念派生类型，构造函数，以及对象的引用。首先，根据主函数中的 c.getX()调用，我们可以判断类 Circle 对类 Point 的继承为公有继承，空(1)处应填入 public Pointo 空(2)处考查的是构造函数的初始化，在派生类的构造函数中可以调用基类的构造函数，应填入 Point(a，b)。在空(3)处我们根据题目给出的说明，要求重新设置圆心为(2，2)，可以调用基类设置点的函数 setPoint，所以空(3)处应填入 c.setPoint(2，2)。最后考察的是对象的引用，派生类对象可以初始化基类引用，在这种情况下，只能访问从相应基类中继承来的成员
37、而不允许访问从其他基类的成员或在派生类中增加的成员，所以，空(4)、空(5)处应分别填入 pRef.getX()和 pRef.getY()。六、试题六(总题数：1，分数：15.00)说明下面 Application 程序用 while 循环从键盘读入字符，记录输入的字符数并输出读入的字符，当输入字符“0”时结束 while 循环，同时结束程序。Java 程序import java.io.*;public class ContinuateInputpublic (1) void main(String args) (2) IOExceptionint ch;int counter=0; Sys
38、tem.out .println(“请输入字符(输入 0 结束)“); while (char) (ch=System.in. (3) ) != 0)counter+;System.out .println ( (4) )ch) ;System.out .println () ;System.out.println (“counted “+counter+“ total bytes. “) ;System.out . (5) ;（分数：15.00）填空项 1:_ （正确答案：static）解析：填空项 1:_ （正确答案：throws）解析：填空项 1:_ （正确答案：read()）解析：填空
39、项 1:_ （正确答案：char）解析：填空项 1:_ （正确答案：exit(0)）解析：解析 本题考查 Java 编程中的 Application 编程，包括输入输出以及异常处理。Application 的入口方法为 mam 方法，必须声明为公有 public、静态 static，以便 Java 解释器调用。故空(1)应填 static。异常抛出有两种方式，一种是用 throw 主动抛出一个特定异常，另一种是方法声明是用 throws 传播异常。故空(2)应填 throws。注意不要填成 throw。根据说明，空(3)是从键盘读入字符，应该调用 read()方法。故空(3)应填 read()。空(4)处用来将读入的字符输出，而 ch 声明为 int，需要进行类型强制转换，故空(4)应填 char。根据说明，结束循环后同时结束程序，故空(5)应填 exit(0)。
