1、初级程序员下午试题-53 及答案解析(总分：106.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明】 喜迎 2008年北京奥运会!以下【C 程序】能将一个给定汉字(例如，奥运会的“会”字)的点阵逆时针旋转 90，并输出旋转前后的点阵数据及字形。 图 1-15是汉字“会”字的 1616点阵字形，用数字 0表示空白位置，用数字 1表示非空白位置，“会”字的第 1行即可表示成如下的0，1序列： 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 如果把它看做一个字的 16个位，“会”字的第 1行可以用十六进制数0100来表示。同理，“会”字的第 2
2、行可以用十六进制数 0240表示，第 3行可以用十六进制数 0420表示依此类推，用 16个双字节整型数即可存放一个汉字点阵字形。“会”字的点阵数据及字形如图 1-15的左半部分所示。 将一个汉字逆时针旋转 90，就是把该汉字点阵的最右列作为旋转后新点阵的第 1行，次最右列作为旋转后新点阵的第 2行依此类推来形成一个旋转后的点阵字形。图 1-15的右半部分就是将“会”字逆时针旋转 90后的点阵数据和字形(提示：读者可将书本顺时针旋转 90，以查看旋转 90后的点阵字形)。 在【C 程序】中，数组 old存放着“会”字的 16个双字节整型点阵数据。函数turnleft能将该点阵数据逆时针旋转 9
3、0，旋转后的点阵数据存放在数组 new中。函数 display能将旋转前后的点阵数据加以编辑，用字符“.”表示值为 0的位，用字符“x”表示值为 1的位，从而将旋转前后的点阵按行输出其十六进制的数据和字形，如图 1-15所示。 （分数：15.00）_二、B试题二/B(总题数：1，分数：15.00)阅读以下技术说明和问题模型图，根据要求回答问题 1和问题 2。【说明】某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点 AP(Access Poin)。假设每个无线 AP覆盖范围的半径是 6米，因此必须使得每台笔记本电脑上的无线网卡到某个无线 AP的直线距离不超过 6米。为了简化问题，假设所有
4、无线网卡在同一直线上，并且无线 AP沿该直线放置。该问题可以建模为如图 1-16所示，其中直线表示无线网卡所在的直线，实心正方形表示无线网卡。现利用贪心策略实现用尽可能少的无线 AP覆盖所有的无线网卡。实现贪心算法的流程如图 1-17所示。其中，di(1iN)表示第 i张无线网卡到通道 A端的距离，N表示无线网卡的总数，无线网卡的编号按照无线网卡到通道 A端的距离从小到大进行编号；sk表示第k(k1)个无线 AP到通道 A端的距离。算法结束后 k的值为无线 AP的总数。（分数：15.00）(1).【问题 1】请填补图 1-17流程图中(1)-(4)空缺处的内容。（分数：7.50）_(2).【问
5、题 2】该贪心算法的时间复杂度为U (5) /U。（分数：7.50）_三、B试题三/B(总题数：1，分数：15.00)2.【说明】 以下【C 程序】的功能是从文件 text_01.ini中读入一篇英文短文，统计该短文中不同单词和它的出现次数，并按词典编辑顺序将单词及它的出现次数输出到文件 word_xml.out中。 该 C程序采用一棵有序二叉树存储这些单词及其出现的次数，一边读入一边建立。然后中序遍历该二叉树，将遍历经过的二叉树上节点的内容输出。 程序中的外部函数 int getword(FILE *fpt，char *word) 从与 fpt所对应的文件中读取单词置入 word，并返回 1
6、；若已无单词可读，即到文件尾部时，则函数返回 0。 【C 程序】#include stdio.h #include malloc.h #include ctype.h #include string.h #define INF “TEXT_01.INI“ #define OUTF “WORD_XML.OUT“ typedef struct treenode char *word; int count; struct treenode *left, *right; BNODE; int getword(FILE *fpt,char *word); void binary tree(BNODE *
7、t,char *word) BNODE *ptr, *p; int cmpres; p = NULL; U (1) /U; while (ptr) /*寻找插入位置*/ cmpres = strcmp(word,U (2) /U); /* 保存当前比较结果*/ if (!cmpres) U (3) /U return; else U (4) /U; ptr = cmpres 0 ? ptr-right : ptr-left; ptr = (BNODE *)malloc(sizeof(BNODE); ptr-right = ptr-left = NULL; ptr-word = (char *)
8、malloc(strlen(word)+1); strcpy(ptr-word,word); ptr-count = 1; if (p = NULL) U (5) /U; else if (cmpres 0) p-right = ptr; else p-left = ptr; void midorder(FILE *fpt, BNODE *t) if (U (6) /U) return; midorder(fpt , t-left); fprintf(fpt , “ %s %d/n “ , t-word , t-count); midorder(fpt , t-right); void mai
9、n() FILE *fpt; char word40; BNODE *root = NULL; if (fpt = fopen(INF , “r“) = NULL) printf(“Cant open file %s/n“,INF); return; while (getword(fpt,word) = 1) binary_tree(U (7) /U); fclose(fpt); fopen(OUTF,“w“); midorder(fpt, root); fclose(fpt); （分数：15.00）_四、B试题四/B(总题数：1，分数：15.00)阅读以下算法说明和 C程序，根据要求回答问题
10、 1和问题 2。【说明】【算法 4-1】的功能是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号而没有对应的左括号或者右括号，则给出相应的提示信息，如图 1-18所示。（分数：15.00）(1).【问题 1】请将【算法 4-1】和【算法 4-2】中，(1)(7)空缺处的内容补充完整。（分数：7.50）_(2).【问题 2】 请从以下选项中选择相应的判断逻辑填写【算法 4-2】中的“判断条件 1”至“判断条件3”。注意，如“判断条件 2”的逻辑判断结果为假，则无须对“判断条件 3”进行判断。 判断条件1：U (8) /U 判断条件 2：U (9) /U 判断条件 3：U (10) /U 【
11、供选择的答案】A栈顶元素表示的是与当前字符匹配的左括号B栈顶元素表示的是与当前字符匹配的右括号C字符是左括号D字符是右括号E栈不空 F栈空 G字符是括号（分数：7.50）_五、B试题五/B(总题数：1，分数：16.00)从下列 3道试题(试题 5至试题 7)中任选 1道解答。如果解答的试题数超过 1道，则题号小的 1道解答有效。阅读以下应用说明及 Visual Basic程序代码，根据要求回答问题 1至问题 4。【说明】某学期成绩管理系统的“增、删、改数据表中的记录”对话框如图 1-19所示。（分数：16.00）(1).【问题 1】 请根据【说明】和图 1-19的显示结果，从以下备选答案中为(
12、1)(9)空缺处选择正确的答案。(以下部分选项可重复选择) 【备选答案】 ADatal.RefreshBDatal.Recordset.UpdateCDatal.RecordsetDDatal.Recordset.CancelUpdateEDatal.Recordset.AddNewFDatal.Recordset.MoveNextGDatal.Recordset.MoveLastHcmdDelete.Enabled=NotcmdDelete.Enabled（分数：4.00）_(2).【问题 2】 在 Visual Basic中，公用标准模块文件的扩展名是U (10) /U。 Afrm Bci
13、s Cvbp Dbas（分数：4.00）_(3).【问题 3】为图 1-19对话框中的【退出】按钮新增如下的功能：运行图 1-19窗体时，该按钮上显示有“退出(C)”的字样信息，按【Alt+C】组合键或按【ESC】键，都相当于单击该按钮。要完成以上新增功能需要将退出按钮(cmdExit)的 Cancel属性和 Caption属性分别设置什么样的值?（分数：4.00）_(4).【问题 4】请说明以下语句所完成的功能。MsgBox“请检查修改输入数据!“，vbOKOnly+vbCritcal+vbDefaultBUttonl，“数据错“（分数：4.00）_六、B试题六/B(总题数：1，分数：15.
14、00)3.【说明】 以下【C+程序】用于实现两个多项式的乘积运算。多项式的每一项由类 Item描述，而多项式由类 List描述。类 List的成员函数主要有： createList()：创建按指数降序链接的多项式链表，以表示多项式： reverseList()：将多项式链表的表元链接顺序颠倒： multiplyList(ListL1，ListL2)计算多项式 L1和多项式 L2的乘积多项式。 【C+程序】 #include iostream.h class List; class Item friend class List; private: double quot ; int exp ;
15、Item *next; Public: Item(double_quot,int_exp) U (1) /U; ; class List private: Item *list; Public: List() list=NULL: void reverseList(); void multiplyList(List L1,List L2); void createList(); ; void List:createList() Item *p,*U,*pre; int exp; double quot; list = NULL; while (1) cout “输入多项式中的一项(系数、指数)
16、 :“ endl; cin quot exp: if ( exp0 ) break ; /指数小于零，结束输入 if ( quot=0 ) continue; p = list; while (U (2) /U) /查找插入点 pre = p; p = p-next; if ( p != NULL continue ; u =U (3) /U; if (p = list) list = u; else pre-next = u; u -next = p; void List:reverseList() Item *p, *u; if ( list=NULL ) return; p = list
17、 -next; list - next = NULL; while ( p != NULL) u = p - next; p -next = list; list = p; p = u; void List:multiplyList ( List L1, List L2 ) Item *pL1,*pL2,*u; int k, maxExp; double quot; maxExp =U (4) /U: L2.reverseList(); list=NULL; for ( k = maxExp;k = 0;k- ) pL1 = L1.list; while ( pL1 != NULL pL2 =
18、 L2.1ist; while (pL2 NULL quot = 0.0; while (pL1 != NULL pL2 = pL2 - next; else if ( pL1 - exp + pL2 - exp k ) pL1 = pL1 - next; else pL2 = pL2 - next; if ( quot !=0.0 ) u = new item( quot, k ); u - next = list; list = u; reverseList (); L2. reverseList (): void main() List L1,L2,L; cout “创建第一个多项式链表
19、/n“; L1.createList(); cout “创建第二个多项式链表/n“; L2.createList(); L.multiplyList (L1,L2); （分数：15.00）_七、B试题七/B(总题数：1，分数：15.00)4.【说明】 用创建 Thread类的子类的方法实现多线程，判断一个数是否是素数。如果是，打印“是素数”，如果不是，则打印“不是素数”；如果没有参数输入，显示“请输入一个命令行参数”。 【Java 程序】import java.io.* ; public class TestThread /Java Application主类 public static vo
20、id main(Sting args ) if (args lengthl) /要求用户输入一个命令行，否则程序不能进行下去 system.out.println(“请输入一个命令行参数“); system.exit(0) ; /创建用户 Thread子类的对象实例，使其处于 NewBorn状态 primeThread getPrimes = new primeThread (Integer.parseInt(args0); getPrimes.start () ; /启动用户线程，使其处于 Runnable状态 while(getPrimes.isAlive() /说明主线程在运行 try
21、Thread. sleep (500); /使主线程挂起指定毫秒数，以便用户线程取得控制权， /sleep是 static的类方法 Catch(InterruptedException e) /sleep 方法可能引起的异常，必须加以处理 return ; /while 循环结束 System.out.println (“按任意键继续“) ; /保留屏幕，以便观察 try U (1) /U; Catch(IOException e) /main 方法结束 class primeThread extends Thread /创建用户自己的 Thread子类 run()中实现程序子线程操作 boo
22、lean m_bContinue=true; /标志本线程是继续 int m_nCircleNum ; /循环的上限 prime Thread(int Num) /构造函数 m_nCircleNum =Nam; boolean ReadyToGoOn () /判断本线程是否继续执行 return (U (2) /U); public void run () /继承并重载父类 Thread的 run ()方法，在该线程被启动时自动执行 int number =3; boolean flag=true; while (true) /无限循环 for(U (3) /U; i+) /检查 number
23、是否为素数 if(number %i=0) U (4) /U; system, out. println (flag); if (flag) /打印该数是否为素数的信息 system,out.print in (number+ “是素数“) ; else sys rem.out.print In (number+ “是素数“) ; number+ ; /修改 number的数值，为下一轮素数检查做准备 if (number m_nCircleNum) /到达要求检查数值的上限 m_bCont inue= false ; /则准备结束此线程 return ; /结束 run()方法，结束线程 U
24、(5) /U; try /经过一轮检查之后，暂时休眠一段时间 sleep(500); /使主线程挂起指定毫秒数，以便父线程取得控制权 Catch(InterruptedException e) Return; /for循环结束 /while 循环结束 /run()方法结束 /primeThread 类定义结束（分数：15.00）_初级程序员下午试题-53 答案解析(总分：106.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明】 喜迎 2008年北京奥运会!以下【C 程序】能将一个给定汉字(例如，奥运会的“会”字)的点阵逆时针旋转 90，并输出旋转前后的点
25、阵数据及字形。 图 1-15是汉字“会”字的 1616点阵字形，用数字 0表示空白位置，用数字 1表示非空白位置，“会”字的第 1行即可表示成如下的0，1序列： 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 如果把它看做一个字的 16个位，“会”字的第 1行可以用十六进制数0100来表示。同理，“会”字的第 2行可以用十六进制数 0240表示，第 3行可以用十六进制数 0420表示依此类推，用 16个双字节整型数即可存放一个汉字点阵字形。“会”字的点阵数据及字形如图 1-15的左半部分所示。 将一个汉字逆时针旋转 90，就是把该汉字点阵的最右列作为旋转后新点阵的第 1行，次最
26、右列作为旋转后新点阵的第 2行依此类推来形成一个旋转后的点阵字形。图 1-15的右半部分就是将“会”字逆时针旋转 90后的点阵数据和字形(提示：读者可将书本顺时针旋转 90，以查看旋转 90后的点阵字形)。 在【C 程序】中，数组 old存放着“会”字的 16个双字节整型点阵数据。函数turnleft能将该点阵数据逆时针旋转 90，旋转后的点阵数据存放在数组 new中。函数 display能将旋转前后的点阵数据加以编辑，用字符“.”表示值为 0的位，用字符“x”表示值为 1的位，从而将旋转前后的点阵按行输出其十六进制的数据和字形，如图 1-15所示。 （分数：15.00）_正确答案：()解析：
27、(1)k=0,newlrowl=0 (2)row (3)15-k (4)“/0 (5)*old(15-col) 或 oldrow(15-col) (6)*new(15-col) 或 newrow(15-col) 要点解析 这是一道要求读者掌握数组应用的程序设计题。本题的解答思路如下。 阅读程序说明后可知，本程序可将一个给定汉字的点阵逆转 90后输出。用 16个元素的元素数组表示汉字点阵，每个无符号整数有 16位，0 表示空白位置，为 1表示非空白位置。该 C程序的功能是将上述表示形式的汉字点阵(“会”字)逆时针旋转 90后存储在数组 new中，并输出旋转前后的十六进制点阵数据和字形。 函数 t
28、urnleft完成点阵数据逆时针旋转 90，并将旋转后的点阵数据存放在数组 New中。在函数 turnleft的 for循环中，语句“newrow|=(01dkU (2) /U) int count; struct treenode *left, *right; BNODE; int getword(FILE *fpt,char *word); void binary tree(BNODE *t,char *word) BNODE *ptr, *p; int cmpres; p = NULL; U (1) /U; while (ptr) /*寻找插入位置*/ cmpres = strcmp(w
29、ord,U (2) /U); /* 保存当前比较结果*/ if (!cmpres) U (3) /U return; else U (4) /U; ptr = cmpres 0 ? ptr-right : ptr-left; ptr = (BNODE *)malloc(sizeof(BNODE); ptr-right = ptr-left = NULL; ptr-word = (char *)malloc(strlen(word)+1); strcpy(ptr-word,word); ptr-count = 1; if (p = NULL) U (5) /U; else if (cmpres
30、0) p-right = ptr; else p-left = ptr; void midorder(FILE *fpt, BNODE *t) if (U (6) /U) return; midorder(fpt , t-left); fprintf(fpt , “ %s %d/n “ , t-word , t-count); midorder(fpt , t-right); void main() FILE *fpt; char word40; BNODE *root = NULL; if (fpt = fopen(INF , “r“) = NULL) printf(“Cant open f
31、ile %s/n“,INF); return; while (getword(fpt,word) = 1) binary_tree(U (7) /U); fclose(fpt); fopen(OUTF,“w“); midorder(fpt, root); fclose(fpt); （分数：15.00）_正确答案：()解析：(1)ptr=*t (2)ptr-word (3)ptr-count+或其等价形式 (4)P=ptr (5)*t=ptr (6)t=NULL 或 !t (7) class Item friend class List; private: double quot ; int e
32、xp ; Item *next; Public: Item(double_quot,int_exp) U (1) /U; ; class List private: Item *list; Public: List() list=NULL: void reverseList(); void multiplyList(List L1,List L2); void createList(); ; void List:createList() Item *p,*U,*pre; int exp; double quot; list = NULL; while (1) cout “输入多项式中的一项(系
33、数、指数) :“ endl; cin quot exp: if ( exp0 ) break ; /指数小于零，结束输入 if ( quot=0 ) continue; p = list; while (U (2) /U) /查找插入点 pre = p; p = p-next; if ( p != NULL continue ; u =U (3) /U; if (p = list) list = u; else pre-next = u; u -next = p; void List:reverseList() Item *p, *u; if ( list=NULL ) return; p =
34、 list -next; list - next = NULL; while ( p != NULL) u = p - next; p -next = list; list = p; p = u; void List:multiplyList ( List L1, List L2 ) Item *pL1,*pL2,*u; int k, maxExp; double quot; maxExp =U (4) /U: L2.reverseList(); list=NULL; for ( k = maxExp;k = 0;k- ) pL1 = L1.list; while ( pL1 != NULL
35、pL2 = L2.1ist; while (pL2 NULL quot = 0.0; while (pL1 != NULL pL2 = pL2 - next; else if ( pL1 - exp + pL2 - exp k ) pL1 = pL1 - next; else pL2 = pL2 - next; if ( quot !=0.0 ) u = new item( quot, k ); u - next = list; list = u; reverseList (); L2. reverseList (): void main() List L1,L2,L; cout “创建第一个
36、多项式链表/n“; L1.createList(); cout “创建第二个多项式链表/n“; L2.createList(); L.multiplyList (L1,L2); （分数：15.00）_正确答案：()解析：(1)quot=_quot; exp=exp; next=NULL; (2)p!=NULL public class TestThread /Java Application主类 public static void main(Sting args ) if (args lengthl) /要求用户输入一个命令行，否则程序不能进行下去 system.out.println(“请
37、输入一个命令行参数“); system.exit(0) ; /创建用户 Thread子类的对象实例，使其处于 NewBorn状态 primeThread getPrimes = new primeThread (Integer.parseInt(args0); getPrimes.start () ; /启动用户线程，使其处于 Runnable状态 while(getPrimes.isAlive() /说明主线程在运行 try Thread. sleep (500); /使主线程挂起指定毫秒数，以便用户线程取得控制权， /sleep是 static的类方法 Catch(InterruptedE
38、xception e) /sleep 方法可能引起的异常，必须加以处理 return ; /while 循环结束 System.out.println (“按任意键继续“) ; /保留屏幕，以便观察 try U (1) /U; Catch(IOException e) /main 方法结束 class primeThread extends Thread /创建用户自己的 Thread子类 run()中实现程序子线程操作 boolean m_bContinue=true; /标志本线程是继续 int m_nCircleNum ; /循环的上限 prime Thread(int Num) /构造
39、函数 m_nCircleNum =Nam; boolean ReadyToGoOn () /判断本线程是否继续执行 return (U (2) /U); public void run () /继承并重载父类 Thread的 run ()方法，在该线程被启动时自动执行 int number =3; boolean flag=true; while (true) /无限循环 for(U (3) /U; i+) /检查 number是否为素数 if(number %i=0) U (4) /U; system, out. println (flag); if (flag) /打印该数是否为素数的信息
40、 system,out.print in (number+ “是素数“) ; else sys rem.out.print In (number+ “是素数“) ; number+ ; /修改 number的数值，为下一轮素数检查做准备 if (number m_nCircleNum) /到达要求检查数值的上限 m_bCont inue= false ; /则准备结束此线程 return ; /结束 run()方法，结束线程 U(5) /U; try /经过一轮检查之后，暂时休眠一段时间 sleep(500); /使主线程挂起指定毫秒数，以便父线程取得控制权 Catch(Interrupted
41、Exception e) Return; /for循环结束 /while 循环结束 /run()方法结束 /primeThread 类定义结束（分数：15.00）_正确答案：()解析：(1)system.in.read0 (2)m_bContinue (3)int i=2;inumber (4)flag =false (5)flag=true 要点解析 这是一道要求读者用创建 Thread类的子类的方法实现多线程的编程题。本题的解答思路如下。 多线程是 Java语言的一大特性。多线程就是同时存在 n个执行体，按几条不同的执行线索共同工作的情况。程序就是一段静态的代码，可以理解为一组计算机命令的
42、集合。进程就是这个程序一次动态的执行过程，从代码的加载到执行完毕的一个过程。线程是一个比进程更小的单位，一个进程在执行的过程中可以产生多个线程，每个线程也是由生产到销毁，可以理解为进程的子集。 线程是有状态和声明周期的，每个 Java程序都会有一个缺省的主线程，对于应用程序 applcation来说，main()方法就是一个主线程。Java语言使用的是 Thread类及其子类的对象来表示线程的。创建一个新线程的生命周期有如下工作状态。1)新建。当一个 Thread类或者其子类的对象被声明并创建时，新的线程对象处于新建状态，此时它已经有了相应的内存空间和其他资源。 2)就绪。处于新建状态的线程被
