1、初级程序员下午试题-92 及答案解析(总分：120.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)1.说明下面的流程图实现了正整数序列 K(1),K(2),K(n)的重排，得到的新序列中，比 K(1)小的数都在 K(1)的左侧，比 K(1)大的数都在 K(1)的右侧。以 n=6为例，序列 12，2，9，13，21，8 的重排过程为：12,2,9,13,21,82,12,9,13,21,89,2,12,13,21,88,9,2,12,13,21流程图（分数：15.00）_二、试题二(总题数：1，分数：15.00)2.函数 2.1说明下面程序的功能是：将由键盘输入的某个十进
2、制数转换成对应的 R进制数并输出。这里 R是 2 到 16的整数，由键盘输入。例如，输入 n=128，base=13 后的输出为 9B。函数 2.1#include stdio.hmain()char b16=0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F;int c64,n,i=0,base;printf(“Enter a number:“);scaaf(“%d“,printf(“Enter new base:“);scanf(“%d“,doci= (1) ;i+;n=n/base;while( (2) );printf(“Transmit new base:“);for(-
3、 -i;i=0;- -i)printf(“%c“, (3) );函数 2.2说明所谓回文字符中是指正序和逆序拼写相同的字符串，例如 astrtsa，adgdtdgda 等。下面函数 int fun(char *str)的功能是判断字符串 str是否是回文，当字符串是回文时，函数返回 1，否则返回 0。函数 2.2int fun(char *str)int i,j,l;for(i=0;stri! =/0;i+);l=i/2;for(j=0,i- -;j=1; (4) )if( (5) ) return 0;return 1;（分数：15.00）_三、试题三(总题数：1，分数：15.00)3.说明
4、邻接表是图的一种顺序存储与链式存储结合的存储方法。其思想是：对于图 G中的每个顶点 vi，将所有邻接于 vi的顶点 vj连成一个单链表，这个单链表就称为顶点 vi的邻接表，其中表头称作顶点表结点VertexNode，其余结点称作边表结点 EdgeNode。将所有的顶点表结点放到数组中，就构成了图的邻接表AdjList。邻接表表示的形式描述如下： #define MaxVerNum 100 /*最大顶点数为 100*/typedef struct node /*边表结点*/int adjvex; /*邻接点域*/struct node *next; /*指向下一个边表结点的指针域*/ EdgeN
5、ode;typedef struct vnode /*顶点表结点*/int vertex; /*顶点域*/EdgeNode *firstedge; /*边表头指针*/VertexNode;typedef VertexNode AdjListMaxVerNum; /*AdjList是邻接表类型*/typedef structAdjList adjlist; /*邻接表*/int n; /*顶点数*/ALGraph; /*ALGraph是以邻接表方式存储的图类型*/深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。下面的函数利用递归算法，对以邻接表形式存储的图进行深度优先搜索：设初始状态是
6、图中所有顶点未曾被访问，算法从某顶点 v出发，访问此顶点，然后依次从 v的邻接点出发进行搜索，直至所有与 v相连的顶点都被访问；若图中尚有顶点未被访问，则选取这样的一个点作起始点，重复上述过程，直至对图的搜索完成。程序中的整型数组 visited的作用是标记顶点 i是否已被访问。函数void DFSTraverseAL(ALGraph *G)/*深度优先搜索以邻接表存储的图 G*/int i;for(i=0;i (1) ;i+) visitedi=0;for(i=0;i (1) ;i+)if( (2) ) DFSAL(G,i);void DFSAL(ALGraph *G,int i) /*从
7、Vi出发对邻接表存储的图 G进行搜索*/EdgeNode *p;(3) ;p= (4) ;while(p!=NULL) /*依次搜索 Vi的邻接点 Vj*/if(! visited (5) ) DFSAL(G, (5) );p=p-next; /*找 Vi的下一个邻接点*/（分数：15.00）_四、试题四(总题数：1，分数：15.00)4.说明Kruskal算法是一种构造图的最小生成树的方法。设 G为一无向连通图，令 T是由 G的顶点构成的于图，Kmskal算法的基本思想是为 T添加适当的边使之成为最小生成树：初始时，T 中的点互相不连通；考察 G的边集 E中的每条边，若它的两个顶点在 T中不
8、连通，则将此边添加到 T中，同时合并其两顶点所在的连通分量，如此下去，当添加了 n-1条边时，T 的连通分量个数为 1，T 便是 G的一棵最小生成树。下面的函数 void Kruskal(EdgeType edges,int n)利用 Kruskal算法，构造了有 n个顶点的图 edges的最小生成树。其中数组 father用于记录 T中顶点的连通性质：其初值为 fatheri=-1 (i=0,1,n-1)，表示各个顶点在不同的连通分量上；若有 fatheri=j，j-1，则顶点 i，j 连通；函数 int Find(int father,int v)用于返回顶点 v所在树形连通分支的根结点。
9、函数#define MAXEDGE 1000typedef structint v1;int v2;EdgeType;void Kruskal(EdgeType edges,int n)int fatherMAXEDGE;int i,j,vf1,vt2;for(i=0;in;i+ +) fatheri=-1;i=0;j=0;while(iMAXEDGE vf2=Find(father,edgesi.v2);if( (2) )(3) =vf1;(4) ;printf(“%3d%3d/n“,edgesi.v1,edgesi.v2);(5) ;int Find(int father,int v)in
10、t t;t=v;while(fathert=0) t=fathert;return(t);（分数：15.00）_五、试题五(总题数：1，分数：15.00)5.说明下面的程序演示了根据随机产生的奖牌数，生成金银奖牌榜的过程。程序使用的排序法是简单排序法。以金牌得数为例，其思想是选择最大的元素，将它交换到最前面；然后对剩下的部分采用同样的方法，直到全部排序完成。（分数：15.00）_六、试题六(总题数：1，分数：15.00)6.说明有若干教师，每个教师只有姓名，一个教师可以指导多名研究生；每名研究生有姓名和研究方向，程序最后输出每个教师指导的所有研究生的姓名和研究方向。Java程序public c
11、lass Teacher String name;int top=0;Student student=new Student20;public Teacher() public Teacher(String name) this.name=name;boolean add(Student stu)int len=this.student.length;if (toplen-1) this.studenttop=siu;(1) ;return true;elsereturn (2) ;void disp()System.out.println(“指导老师“”+this.name);System.
12、out.println(“研究生:”);for(int i=0;i (3) ;i+)System.out.println(“姓名:”+this.studenti.name+“/t 研究方向:”+this.studenti. search);public static void main(String args)Teacher t=new Teacher(“李明”),new Teacher(“王华”);Student s1 = new Student(“孙强”，“数据库”);Student s2 = new Student(“陈文”，“软件工程”);Student s3 = new Studen
13、t(“章锐”，“计算机网络”);if(! t0.add(s1) System.out.println(“每个老师最多只能指导 20个学生!”);if(! t0.add(a2) System.out.println(“每个老师最多只能指导 20个学生!”);if(! t1.add(s3) System.out.println(“每个老师最多只能指导 20个学生!”);for(int i=0;i2;i+)(4) ;class (5) String name;String search;public Student()public Student(String name,String search)
14、this.name=name;this.search=search;String getName()return this.name;String getSearch()return this.search;（分数：15.00）_七、试题七(总题数：1，分数：15.00)7.说明设有一张学生成绩表 scores存放在 Access数据库 Student中，其中包括学生编号、姓名以及各科目考试成绩。下面的应用程序利用 ADO Data和 DataGrid控件实现了对成绩数据的基本管理，其操作包括：(1)添加新记录：单击“添加”按钮，光标将指向最后一条数据记录，在其后编辑好新的数据记录后，再单击“
15、更新”按钮，该数据即被加入成绩表；(2)删除记录：单击“删除”按钮将删除当前所指记录，其后的数据记录依次上移；(3)更新记录：直接编辑某条已有记录，再单击“更新”按钮将更新成绩表；(4)记录排序：选中单列字段后，单击“排序”按钮，记录集将按该字段升序排列。程序的运行界面为：（分数：15.00）_八、试题八(总题数：1，分数：15.00)8.说明下面的词典类 Dic实现了简单的英译汉功能。程序运行后的输出为“我是一个学生”。C+程序#include iostream.h#include string.h#define Max 100class Dicint top;char wordsMax 1
16、2;char meanMax 20;public:Die()top=0;void add(char w,char m)strcpy(wordstop,w);strcpy(meantop,m);(1) ;void trans(char str) int i=0,j=0,k=0,s;char w12,h200;while(l) if(stri! = /读取单词的一个字符，记录在 w中else wj=/0;for(s=0;s top;s+)if(strcmp(wordss,w) (2) 0) break;if(stop) /找到了，翻译成对应的 meansstrcpy(w,means); j= (3
17、) ;else /未找到，翻译成(unknown)strcpy(w,“(unknown)“; j=9; for(s=0;sj;s+)hk+=ws;if(stri=/0) (4) ; break;j=0;i+;couthendl;void main()Dic obj;obj.add(“I“,“我“);obj.add(“am“,“是“);obj.add(“student“,“学生“);obj.add(“a“,“一个“);obj.trans(“ (5) “);（分数：15.00）_初级程序员下午试题-92 答案解析(总分：120.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)
18、1.说明下面的流程图实现了正整数序列 K(1),K(2),K(n)的重排，得到的新序列中，比 K(1)小的数都在 K(1)的左侧，比 K(1)大的数都在 K(1)的右侧。以 n=6为例，序列 12，2，9，13，21，8 的重排过程为：12,2,9,13,21,82,12,9,13,21,89,2,12,13,21,88,9,2,12,13,21流程图（分数：15.00）_正确答案：(1) K(s)K(t) (2) K(s) (3) ii-1 (4) tt+1 (5) ss+1)解析：考点分析 考查算法的流程图表示。解析 算法中变量 K(t)始终代表原始序列中的 K(1)值，t 则代表它在当前
19、序列中的位置编号，初始值为1； k(s)代表待比较的数。算法首先拿 K(t)和其后的数做比较，若 K(s)比 K(t)小，则 K(s)移至序列的最左侧，同时顺次把第 i，is 位的元素向右移一位。让 s自增 1，重复这一步骤，直至到达序列末端(即s=n)为止。二、试题二(总题数：1，分数：15.00)2.函数 2.1说明下面程序的功能是：将由键盘输入的某个十进制数转换成对应的 R进制数并输出。这里 R是 2 到 16的整数，由键盘输入。例如，输入 n=128，base=13 后的输出为 9B。函数 2.1#include stdio.hmain()char b16=0,1,2,3,4,5,6,
20、7,8,9,A,B,C,D,E,F;int c64,n,i=0,base;printf(“Enter a number:“);scaaf(“%d“,printf(“Enter new base:“);scanf(“%d“,doci= (1) ;i+;n=n/base;while( (2) );printf(“Transmit new base:“);for(- -i;i=0;- -i)printf(“%c“, (3) );函数 2.2说明所谓回文字符中是指正序和逆序拼写相同的字符串，例如 astrtsa，adgdtdgda 等。下面函数 int fun(char *str)的功能是判断字符串
21、str是否是回文，当字符串是回文时，函数返回 1，否则返回 0。函数 2.2int fun(char *str)int i,j,l;for(i=0;stri! =/0;i+);l=i/2;for(j=0,i- -;j=1; (4) )if( (5) ) return 0;return 1;（分数：15.00）_正确答案：(1) n% base (2) n! =0 (3) bci (4) j+, i- (5) stri! =strj)解析：考点分析 考查 C语言程序设计，包括数值和字符中的处理。解析 (1)(3)函数 2.1的基本思想是“除 base取余”，即从低位开始以 n除以 base的余数
22、作为转化后的一位 ci，再以 n除以 base的商作为新的 n，继续进行转化，直至除法商 0为止。最后将所得的ci作为下标，从数组 b中找出对应的数码表示，即 bci。(4)(5)此循环初始时，i 和 j充当 str的头和尾指针，循环执行过程中，两指针同时以步长 1向 str的中间移动，比较所指字符是否相等，若不等则表明 str不是回文字符串。三、试题三(总题数：1，分数：15.00)3.说明邻接表是图的一种顺序存储与链式存储结合的存储方法。其思想是：对于图 G中的每个顶点 vi，将所有邻接于 vi的顶点 vj连成一个单链表，这个单链表就称为顶点 vi的邻接表，其中表头称作顶点表结点Verte
23、xNode，其余结点称作边表结点 EdgeNode。将所有的顶点表结点放到数组中，就构成了图的邻接表AdjList。邻接表表示的形式描述如下： #define MaxVerNum 100 /*最大顶点数为 100*/typedef struct node /*边表结点*/int adjvex; /*邻接点域*/struct node *next; /*指向下一个边表结点的指针域*/ EdgeNode;typedef struct vnode /*顶点表结点*/int vertex; /*顶点域*/EdgeNode *firstedge; /*边表头指针*/VertexNode;typedef
24、VertexNode AdjListMaxVerNum; /*AdjList是邻接表类型*/typedef structAdjList adjlist; /*邻接表*/int n; /*顶点数*/ALGraph; /*ALGraph是以邻接表方式存储的图类型*/深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。下面的函数利用递归算法，对以邻接表形式存储的图进行深度优先搜索：设初始状态是图中所有顶点未曾被访问，算法从某顶点 v出发，访问此顶点，然后依次从 v的邻接点出发进行搜索，直至所有与 v相连的顶点都被访问；若图中尚有顶点未被访问，则选取这样的一个点作起始点，重复上述过程，直至对图的
25、搜索完成。程序中的整型数组 visited的作用是标记顶点 i是否已被访问。函数void DFSTraverseAL(ALGraph *G)/*深度优先搜索以邻接表存储的图 G*/int i;for(i=0;i (1) ;i+) visitedi=0;for(i=0;i (1) ;i+)if( (2) ) DFSAL(G,i);void DFSAL(ALGraph *G,int i) /*从 Vi出发对邻接表存储的图 G进行搜索*/EdgeNode *p;(3) ;p= (4) ;while(p!=NULL) /*依次搜索 Vi的邻接点 Vj*/if(! visited (5) ) DFSAL
26、(G, (5) );p=p-next; /*找 Vi的下一个邻接点*/（分数：15.00）_正确答案：(1) G-n (2) ! visitedi (3) visitedi=1 (4) G-adjlisti.firstedge (5) p-adjvex)解析：考点分析 考查用 C语言实现图的深度优先搜索算法。解析 (1)此处循环是访问标志向量的初始化，应遍历 G 的全体点，共计 Gn 个；(2)若 Vi未被访问，则从 Vi开始搜索；(3)标记 Vi已访问；(4)为递归搜索 Vi的邻接点，需先取出 Vi边表的头指针；(5)若 Vi的邻接点 p-adjvex 尚未被访问，则从它出发进行纵深搜索。四
27、、试题四(总题数：1，分数：15.00)4.说明Kruskal算法是一种构造图的最小生成树的方法。设 G为一无向连通图，令 T是由 G的顶点构成的于图，Kmskal算法的基本思想是为 T添加适当的边使之成为最小生成树：初始时，T 中的点互相不连通；考察 G的边集 E中的每条边，若它的两个顶点在 T中不连通，则将此边添加到 T中，同时合并其两顶点所在的连通分量，如此下去，当添加了 n-1条边时，T 的连通分量个数为 1，T 便是 G的一棵最小生成树。下面的函数 void Kruskal(EdgeType edges,int n)利用 Kruskal算法，构造了有 n个顶点的图 edges的最小生
28、成树。其中数组 father用于记录 T中顶点的连通性质：其初值为 fatheri=-1 (i=0,1,n-1)，表示各个顶点在不同的连通分量上；若有 fatheri=j，j-1，则顶点 i，j 连通；函数 int Find(int father,int v)用于返回顶点 v所在树形连通分支的根结点。函数#define MAXEDGE 1000typedef structint v1;int v2;EdgeType;void Kruskal(EdgeType edges,int n)int fatherMAXEDGE;int i,j,vf1,vt2;for(i=0;in;i+ +) fathe
29、ri=-1;i=0;j=0;while(iMAXEDGE vf2=Find(father,edgesi.v2);if( (2) )(3) =vf1;(4) ;printf(“%3d%3d/n“,edgesi.v1,edgesi.v2);(5) ;int Find(int father,int v)int t;t=v;while(fathert=0) t=fathert;return(t);（分数：15.00）_正确答案：(1) n-1 (2) vf1! =vf2 (3) fathervf2 (4) j+ (5) i+)解析：考点分析 考查用 C语言实现构造最小生成树的 Kruskal 算法。解
30、析 (1)由上下文可知，变量 j记录了添加进最小生成树的边数，当 j超出 n-1时循环终止，构造过程结束；(2)此处的判别条件应该是：v1 和 V2连通。由于 Vf1和 vf2 分别是边 edgesi两顶点 v1、v2 所在连通分支的根，v1 和 v2连通当且仅当 vf1和 vf2相等；(3)(4)根据程序说明，当 v1和 v2不连通时，需添加 edgesi进最小生成树且合并 v1和 v2所在连通分支。后者就是令 j自增 1；后者即连接 vf1和 vf2。(5)对图中的边循环，继续考虑下一条边。五、试题五(总题数：1，分数：15.00)5.说明下面的程序演示了根据随机产生的奖牌数，生成金银奖牌
31、榜的过程。程序使用的排序法是简单排序法。以金牌得数为例，其思想是选择最大的元素，将它交换到最前面；然后对剩下的部分采用同样的方法，直到全部排序完成。（分数：15.00）_正确答案：(1) TextBox (2) ByRef (3) medals(k,0) medals(j,0) (4) Exit For (5) medals(k,1)medals(j,1)解析：考点分析 考查用 VB语言及数组结构进行选择排序。解析 (1)由 printOut过程中“txt.Text”及按钮单击事件中调用语句“printOut Text1”可知，txt是一个文本框控件(TextBox)类型的参数；(2)过程 e
32、xchange的作用是交换两个参数的值，因此参数调用方式应为传址调用；(3)此处，仅当第 k个国家金牌数大于第 j个国家金牌数，即 medals(k,0)medals(j,0)时，才需要更新j的值；(4)由于金牌数已按降序排列，medals(k,0)medals(j,0)表明第 k个位置及以后各国家的金牌数都小于第 j个国家金牌数。而对银牌二次排序时，只需要考虑金牌数相同的情形，因此此处应即刻退出 For循环；(5)参考(3)，此处是比较银牌数，仅当第 k个国家银牌数人于第 j个国家银牌数，即 medals(k,1)medals (j,1)时，才需要更新 j的值。六、试题六(总题数：1，分数：
33、15.00)6.说明有若干教师，每个教师只有姓名，一个教师可以指导多名研究生；每名研究生有姓名和研究方向，程序最后输出每个教师指导的所有研究生的姓名和研究方向。Java程序public class Teacher String name;int top=0;Student student=new Student20;public Teacher() public Teacher(String name) this.name=name;boolean add(Student stu)int len=this.student.length;if (toplen-1) this.studenttop
34、=siu;(1) ;return true;elsereturn (2) ;void disp()System.out.println(“指导老师“”+this.name);System.out.println(“研究生:”);for(int i=0;i (3) ;i+)System.out.println(“姓名:”+this.studenti.name+“/t 研究方向:”+this.studenti. search);public static void main(String args)Teacher t=new Teacher(“李明”),new Teacher(“王华”);Stud
35、ent s1 = new Student(“孙强”，“数据库”);Student s2 = new Student(“陈文”，“软件工程”);Student s3 = new Student(“章锐”，“计算机网络”);if(! t0.add(s1) System.out.println(“每个老师最多只能指导 20个学生!”);if(! t0.add(a2) System.out.println(“每个老师最多只能指导 20个学生!”);if(! t1.add(s3) System.out.println(“每个老师最多只能指导 20个学生!”);for(int i=0;i2;i+)(4)
36、;class (5) String name;String search;public Student()public Student(String name,String search)this.name=name;this.search=search;String getName()return this.name;String getSearch()return this.search;（分数：15.00）_正确答案：(1) top+及其等效形式 (2) false (3) top (4) ti.disp() (5) Student)解析：考点分析 考查 Java语言程序设计，主要是类的
37、使用。解析 (1)(2)：add 函数是给 Teacher类的 student数组增加一个学生，每个老师最多能指导 20个学生，如果增加成功则返回 true；否则返回 false。Top 是一个表示 student数组里面有多少个学生的标志。每增加一个学生，top 就要加 1；(3)disp函数是用一个循环来显示老师所指导的所有学生，循环变量从 0开始，上限是 top-1；(4)此处是调用 disp函数来显示所有老师指导的学生。(5)根据程序大意，这是 Student类的定义。七、试题七(总题数：1，分数：15.00)7.说明设有一张学生成绩表 scores存放在 Access数据库 Stud
38、ent中，其中包括学生编号、姓名以及各科目考试成绩。下面的应用程序利用 ADO Data和 DataGrid控件实现了对成绩数据的基本管理，其操作包括：(1)添加新记录：单击“添加”按钮，光标将指向最后一条数据记录，在其后编辑好新的数据记录后，再单击“更新”按钮，该数据即被加入成绩表；(2)删除记录：单击“删除”按钮将删除当前所指记录，其后的数据记录依次上移；(3)更新记录：直接编辑某条已有记录，再单击“更新”按钮将更新成绩表；(4)记录排序：选中单列字段后，单击“排序”按钮，记录集将按该字段升序排列。程序的运行界面为：（分数：15.00）_正确答案：(1) RecordSource (2)
39、DataSource (3) MoveLast (4) (5) DataGrid1.SelEndCol 或DataGrid1.SelStartCol)解析：考点分析 考查 VB语言程序设计，主要是数据库的使用。解析 (1)界面上呈现的数据集是整个成绩表，即 Adodc1 的 RecordSource；(2)DataGrid控件通过 DataSource属性实现与 ADO Data控件的绑定；(3)根据程序说明，单击“添加”按钮，光标指向最后一条数据记录；(4)DataGrid1.SelStartCol0 表示用户没有选择列， DataGrid1.SelStartColDataGrid1.Sel
40、EndCol 表示用户选定了多列，都与程序说明中不符；(5)DataGrid1的 Columns属性返回一个列的集合变量，因此此处应填入所选列的序号，由前文可知，填入 DataGrid1.SelEndCol或 DataGfid1.SelStartCol均可。八、试题八(总题数：1，分数：15.00)8.说明下面的词典类 Dic实现了简单的英译汉功能。程序运行后的输出为“我是一个学生”。C+程序#include iostream.h#include string.h#define Max 100class Dicint top;char wordsMax 12;char meanMax 20;p
41、ublic:Die()top=0;void add(char w,char m)strcpy(wordstop,w);strcpy(meantop,m);(1) ;void trans(char str) int i=0,j=0,k=0,s;char w12,h200;while(l) if(stri! = /读取单词的一个字符，记录在 w中else wj=/0;for(s=0;s top;s+)if(strcmp(wordss,w) (2) 0) break;if(stop) /找到了，翻译成对应的 meansstrcpy(w,means); j= (3) ;else /未找到，翻译成(un
42、known)strcpy(w,“(unknown)“; j=9; for(s=0;sj;s+)hk+=ws;if(stri=/0) (4) ; break;j=0;i+;couthendl;void main()Dic obj;obj.add(“I“,“我“);obj.add(“am“,“是“);obj.add(“student“,“学生“);obj.add(“a“,“一个“);obj.trans(“ (5) “);（分数：15.00）_正确答案：(1) top+ (2) = = (3) strlen(w) (4) hk=/0 (5) I am a student)解析：考点分析 考查 C+语
43、言程序设计，主要是类的使用。解析 词典类 Dic包括 top(当前单词指针)，words(英语单词库)mean(对应中文单词库)数据成员，以及一个构造函数、add()(添加单词)和 trans(英汉翻译)成员函数。trans 函数通过检索单词的方式将一段英语翻译成对应的汉语，其算法是：循环读取输入的英文串 str，每遇到空格或者到达末尾时提取一个单词w；然后在词典中搜索 w，若找到了，将 w替换成对应的中文单词，否则用“(unkown)”替代；将 w追加到结果串 h末尾，若到达 str末尾时退出循环并输出 h。(1)词典中添加一个单词，top 应增 1；(2)此处 for循环用于在词典英文单词中查找 w，一旦匹配即刻退出该循环；(3)下文需要将 w追加到 h末尾，因此需要获取 w的长度并存放于 j中；(4)如果达到输入字符串的末尾，则翻译过程结束，应给结果串 h添加结束符号；(5)由程序输出易知。
