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