1、初级程序员下午试题-87 及答案解析(总分：106.00，做题时间：90 分钟)一、试题一(总题数：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能将该点阵数据逆时针旋转 90，旋转后的点
3、阵数据存放在数组 new中。函数 display能将旋转前后的点阵数据加以编辑，用字符“.”表示值为 0的位，用字符“x”表示值为 1的位，从而将旋转前后的点阵按行输出其十六进制的数据和字形，如图 1-15所示。（分数：15.00）_二、试题二(总题数：1，分数：15.00)【说明】某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点 AP(Access Poin)。假设每个无线 AP覆盖范围的半径是 6米，因此必须使得每台笔记本电脑上的无线网卡到某个无线 AP的直线距离不超过 6米。为了简化问题，假设所有无线网卡在同一直线上，并且无线 AP沿该直线放置。该问题可以建模为如图 1-16所示
4、，其中直线表示无线网卡所在的直线，实心正方形表示无线网卡。现利用贪心策略实现用尽可能少的无线 AP覆盖所有的无线网卡。实现贪心算法的流程如图 1-17所示。其中，di(1iN)表示第 i张无线网卡到通道 A端的距离，N表示无线网卡的总数，无线网卡的编号按照无线网卡到通道 A端的距离从小到大进行编号；sk表示第k(k1)个无线 AP到通道 A端的距离。算法结束后 k的值为无线 AP的总数。（分数：15.00）_三、试题三(总题数：1，分数：15.00)2.【说明】以下【C 程序】的功能是从文件 text_01.ini中读入一篇英文短文，统计该短文中不同单词和它的出现次数，并按词典编辑顺序将单词及
5、它的出现次数输出到文件 word_xml.out中。该 C程序采用一棵有序二叉树存储这些单词及其出现的次数，一边读入一边建立。然后中序遍历该二叉树，将遍历经过的二叉树上节点的内容输出。程序中的外部函数int getword(FILE *fpt，char *word)从与 fpt所对应的文件中读取单词置入 word，并返回 1；若已无单词可读，即到文件尾部时，则函数返回0。【C 程序】#include stdio.h#include malloc.h#include ctype.h#include string.h#define INF “TEXT_01.INI“#define OUTF “WO
6、RD_XML.OUT“typedef struct treenode char *word;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;(1) ;while (ptr) /*寻找插入位置*/cmpres = strcmp(word, (2) ); /* 保存当前比较结果*/if (!cmpres) (3) return;else (4)
7、;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)(5) ;elseif (cmpres 0)p-right = ptr;elsep-left = ptr; void midorder(FILE *fpt, BNODE *t)if ( (6) )return;m
8、idorder(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 file %s/n“,INF);return;while (getword(fpt,word) = 1)binary_tree( (7) );fclose(fpt);fopen(OUTF,“w“);mid
9、order(fpt, root);fclose(fpt);（分数：15.00）_四、试题四(总题数：1，分数：15.00)【说明】【算法 4-1】的功能是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号而没有对应的左括号或者右括号，则给出相应的提示信息，如图 1-18所示。（分数：15.00）_五、试题五(总题数：1，分数：16.00)【说明】某学期成绩管理系统的“增、删、改数据表中的记录”对话框如图 1-19所示。（分数：16.00）_六、试题六(总题数：1，分数：15.00)3.【说明】以下【C+程序】用于实现两个多项式的乘积运算。多项式的每一项由类 Item描述，而多项式由类 Li
10、st描述。类 List的成员函数主要有：createList()：创建按指数降序链接的多项式链表，以表示多项式：reverseList()：将多项式链表的表元链接顺序颠倒：multiplyList(ListL1，ListL2)计算多项式 L1和多项式 L2的乘积多项式。【C+程序】#include iostream.hclass List;class Item friend class List;private:double quot ;int exp ;Item *next;Public:Item(double_quot,int_exp)(1) ;class Listprivate:Item
11、 *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 “输入多项式中的一项(系数、指数) :“ endl;cin quot exp:if ( exp0 )break ; /指数小于零，结束输入if ( quot=0 )continue;p = list;while ( (2) )
12、 /查找插入点pre = p;p = p-next;if ( p != NULL continue ;u = (3) ;if (p = list)list = u;elsepre-next = u;u -next = p;void List:reverseList()Item *p, *u;if ( list=NULL )return;p = list -next;list - next = NULL;while ( p != NULL) u = p - next;p -next = list;list = p;p = u;void List:multiplyList ( List L1, L
13、ist L2 )Item *pL1,*pL2,*u;int k, maxExp;double quot;maxExp = (4) :L2.reverseList();list=NULL;for ( k = maxExp;k = 0;k- )pL1 = L1.list;while ( pL1 != NULL 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;elsepL2 = pL2 - n
14、ext;if ( quot !=0.0 ) u = new item( quot, k );u - next = list;list = u;reverseList ();L2. reverseList ():void main()List L1,L2,L;cout “创建第一个多项式链表/n“;L1.createList();cout “创建第二个多项式链表/n“;L2.createList();L.multiplyList (L1,L2);（分数：15.00）_七、试题七(总题数：1，分数：15.00)4.【说明】用创建 Thread类的子类的方法实现多线程，判断一个数是否是素数。如果是，
15、打印“是素数”，如果不是，则打印“不是素数”；如果没有参数输入，显示“请输入一个命令行参数”。【Java 程序】import java.io.* ;public class TestThread /Java Application主类public static void main(Sting args )if (args lengthl) /要求用户输入一个命令行，否则程序不能进行下去system.out.println(“请输入一个命令行参数“);system.exit(0) ;/创建用户 Thread子类的对象实例，使其处于 NewBorn状态primeThread getPrimes =
16、 new primeThread (Integer.parseInt(args0);getPrimes.start () ; /启动用户线程，使其处于 Runnable状态while(getPrimes.isAlive() /说明主线程在运行try Thread. sleep (500); /使主线程挂起指定毫秒数，以便用户线程取得控制权，/sleep是 static的类方法Catch(InterruptedException e) /sleep方法可能引起的异常，必须加以处理return ;/while循环结束System.out.println (“按任意键继续“) ; /保留屏幕，以便观
17、察try (1) ;Catch(IOException e) /main方法结束class primeThread extends Thread /创建用户自己的 Thread子类 run()中实现程序子线程操作boolean m_bContinue=true; /标志本线程是继续int m_nCircleNum ; /循环的上限prime Thread(int Num) /构造函数m_nCircleNum =Nam;boolean ReadyToGoOn () /判断本线程是否继续执行return ( (2) );public void run () /继承并重载父类 Thread的 run
18、 ()方法，在该线程被启动时自动执行int number =3;boolean flag=true;while (true) /无限循环for( (3) ; i+) /检查 number是否为素数if(number %i=0)(4) ;system, out. println (flag);if (flag) /打印该数是否为素数的信息system,out.print in (number+ “是素数“) ;elsesys rem.out.print In (number+ “是素数“) ;number+ ; /修改 number的数值，为下一轮素数检查做准备if (number m_nCir
19、cleNum) /到达要求检查数值的上限m_bCont inue= false ; /则准备结束此线程return ; /结束 run()方法，结束线程(5) ;try /经过一轮检查之后，暂时休眠一段时间sleep(500); /使主线程挂起指定毫秒数，以便父线程取得控制权Catch(InterruptedException e) Return;/for循环结束/while循环结束/run()方法结束/primeThread类定义结束（分数：15.00）_初级程序员下午试题-87 答案解析(总分：106.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)1.【说明】喜迎
20、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行可以用十六进制数 0240表示，第 3行可以用十六进制数 0420表示依此类推，用 16个双字节整型数即可存放一个汉字点阵字形。“会”字的点阵数据及字
21、形如图 1-15的左半部分所示。将一个汉字逆时针旋转 90，就是把该汉字点阵的最右列作为旋转后新点阵的第 1行，次最右列作为旋转后新点阵的第 2行依此类推来形成一个旋转后的点阵字形。图 1-15的右半部分就是将“会”字逆时针旋转 90后的点阵数据和字形(提示：读者可将书本顺时针旋转 90，以查看旋转 90后的点阵字形)。在【C 程序】中，数组 old存放着“会”字的 16个双字节整型点阵数据。函数 turnleft能将该点阵数据逆时针旋转 90，旋转后的点阵数据存放在数组 new中。函数 display能将旋转前后的点阵数据加以编辑，用字符“.”表示值为 0的位，用字符“x”表示值为 1的位，
22、从而将旋转前后的点阵按行输出其十六进制的数据和字形，如图 1-15所示。（分数：15.00）_正确答案：(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程序的功能是将上述表示形式的汉字点阵(“会
23、”字)逆时针旋转 90后存储在数组 new中，并输出旋转前后的十六进制点阵数据和字形。函数 turnleft完成点阵数据逆时针旋转 90，并将旋转后的点阵数据存放在数组 New中。在函数turnleft的 for循环中，语句“newrow|=(01dk (2) )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;(1) ;while (ptr)
24、 /*寻找插入位置*/cmpres = strcmp(word, (2) ); /* 保存当前比较结果*/if (!cmpres) (3) return;else (4) ;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)(5) ;elseif (cmpres
25、0)p-right = ptr;elsep-left = ptr; void midorder(FILE *fpt, BNODE *t)if ( (6) )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 file %s/n“,INF);
26、return;while (getword(fpt,word) = 1)binary_tree( (7) );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 exp ;Item *next;Public:Item(double_quot,in
27、t_exp)(1) ;class Listprivate: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 “输入多项式中的一项(系数、指数) :“ endl;cin quot exp:if ( exp0 )break ; /指数小于零，结束输入if ( quot=0
28、 )continue;p = list;while ( (2) ) /查找插入点pre = p;p = p-next;if ( p != NULL continue ;u = (3) ;if (p = list)list = u;elsepre-next = u;u -next = p;void List:reverseList()Item *p, *u;if ( list=NULL )return;p = list -next;list - next = NULL;while ( p != NULL) u = p - next;p -next = list;list = p;p = u;vo
29、id List:multiplyList ( List L1, List L2 )Item *pL1,*pL2,*u;int k, maxExp;double quot;maxExp = (4) :L2.reverseList();list=NULL;for ( k = maxExp;k = 0;k- )pL1 = L1.list;while ( pL1 != NULL pL2 = L2.1ist;while (pL2 NULL quot = 0.0;while (pL1 != NULL pL2 = pL2 - next;else if ( pL1 - exp + pL2 - exp k )p
30、L1 = pL1 - next;elsepL2 = 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 “创建第一个多项式链表/n“;L1.createList();cout “创建第二个多项式链表/n“;L2.createList();L.multiplyList (L1,L2);（分数：15.00）_正确答案：(1)quot=_quot; exp=exp; nex
31、t=NULL;(2)p!=NULL public class TestThread /Java Application主类public static void main(Sting args )if (args lengthl) /要求用户输入一个命令行，否则程序不能进行下去system.out.println(“请输入一个命令行参数“);system.exit(0) ;/创建用户 Thread子类的对象实例，使其处于 NewBorn状态primeThread getPrimes = new primeThread (Integer.parseInt(args0);getPrimes.star
32、t () ; /启动用户线程，使其处于 Runnable状态while(getPrimes.isAlive() /说明主线程在运行try Thread. sleep (500); /使主线程挂起指定毫秒数，以便用户线程取得控制权，/sleep是 static的类方法Catch(InterruptedException e) /sleep方法可能引起的异常，必须加以处理return ;/while循环结束System.out.println (“按任意键继续“) ; /保留屏幕，以便观察try (1) ;Catch(IOException e) /main方法结束class primeThrea
33、d extends Thread /创建用户自己的 Thread子类 run()中实现程序子线程操作boolean m_bContinue=true; /标志本线程是继续int m_nCircleNum ; /循环的上限prime Thread(int Num) /构造函数m_nCircleNum =Nam;boolean ReadyToGoOn () /判断本线程是否继续执行return ( (2) );public void run () /继承并重载父类 Thread的 run ()方法，在该线程被启动时自动执行int number =3;boolean flag=true;while
34、(true) /无限循环for( (3) ; i+) /检查 number是否为素数if(number %i=0)(4) ;system, out. println (flag);if (flag) /打印该数是否为素数的信息system,out.print in (number+ “是素数“) ;elsesys rem.out.print In (number+ “是素数“) ;number+ ; /修改 number的数值，为下一轮素数检查做准备if (number m_nCircleNum) /到达要求检查数值的上限m_bCont inue= false ; /则准备结束此线程retur
35、n ; /结束 run()方法，结束线程(5) ;try /经过一轮检查之后，暂时休眠一段时间sleep(500); /使主线程挂起指定毫秒数，以便父线程取得控制权Catch(InterruptedException 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类的子类的方法实现多线程的编程题。本
36、题的解答思路如下。多线程是 Java语言的一大特性。多线程就是同时存在 n个执行体，按几条不同的执行线索共同工作的情况。程序就是一段静态的代码，可以理解为一组计算机命令的集合。进程就是这个程序一次动态的执行过程，从代码的加载到执行完毕的一个过程。线程是一个比进程更小的单位，一个进程在执行的过程中可以产生多个线程，每个线程也是由生产到销毁，可以理解为进程的子集。线程是有状态和声明周期的，每个 Java程序都会有一个缺省的主线程，对于应用程序 applcation来说，main()方法就是一个主线程。Java 语言使用的是 Thread类及其子类的对象来表示线程的。创建一个新线程的生命周期有如下工
37、作状态。1)新建。当一个 Thread类或者其子类的对象被声明并创建时，新的线程对象处于新建状态，此时它已经有了相应的内存空间和其他资源。2)就绪。处于新建状态的线程被启动后，将进入线程队列排队等待 CPU服务，这个时候具备了运行的条件，一旦轮到 CPU的时候，就可以脱离创建它的主线程独立开始自己的生命周期。3)运行。就绪的线程被调度并获得 CPU的处理权后进入了运行状态，每一个 Thread类及其子类的对象都有一个重要的 run()方法，当线程对象被调度执行的时候，它将自动调用本对象的 run()方法，从第一句代码开始执行。可见，对线程的操作应该写到 run()方法中。4)阻塞。一个正在执行
38、的线程如果在某种情况下不能执行而进入阻塞状态，此时它不能进入排队状态，只有引起阻塞的原因消失的时候，线程才可以继续进入排队状态等待 CPU处理。5)死亡。处于死亡状态的线程不具有继续执行的能力，线程死亡的主要原因是正常运行的线程完成了全部工作，即执行完了 run()方法，另外就是被提前强制地终止了。线程的调度也有优先级别，即同等排列的情况下，优先级高的线程可以被 CPU提前处理。Thread 类有 3个线程优先级的静态常量：MIN-PRIORITY、NORM-PRIORITY 和 MAX-PRIORITY。其中， MIN-PRIORITY 代表最小优先级，默认数值为 1：NORM-PRIORI
39、TY 代表普通优先级，默认数值为 5； MAX-PRIORITY 代表最高优先级，默认数值为 10。对于一个新建线程，系统会遵循以下原则为其指定优先级。1)新建线程将继承创建它的父线程的优先级。父线程是指执行创建新线程对象语句的线程，它可能是程序的主线程，也可能是某一个用户自定义的线程。2)通常情况下，主线程具有普通优先级。另外，可以通过调用 Thread类的方法 setPriority(int a)来修改系统自动设置的线程优先级，使之符合程序的特定需要。Java编程实现多线程有两种途径，一种是创建自己的线程子类，另一种是实现一个接口 Runnable。无论是哪种途径最终都需要使用 Threa
40、d类及其方法。Thread 类有 2种构造方法： public Thread()用来创建一个线程对象和 public Thread(Runnabler)创建线程对象，参数 r成为被创建的目标对象。这个口标必须实现 Runnbale接口，给出该接口的 run()方法的方法体，在方法体中进行操作。用两个构造方法创建完的线程就是一个新建的状态，等待处理。接着启动线程的 start()方法，启动线程对象，线程进入排队状态(即就绪状态)。然后线程操作 run()方法，该方法里的内容是被系统处理的内容。如果想使线程进入休眠状态，则可以调用 sleep(int millsecond)方法，millsecon
41、d 是以毫秒为单位的休眠时间。也可调用 sleep(int millsecond,int nanosecond)方法，其中 nanosecond是以纳秒为单位的休眠时间。终止线程用 isAlive()方法来完成。在调用 stop()方法终止一个线程之前，最好先用 isAlive()方法检查一下该线程是否仍然存活，杀死不存在的线程可能会造成系统错误。对于本试题所给出的程序是一个 Java Application，其中定义了两个类，一个是程序的主类TestThread，另一个是用户自定义的 Thread类的子类 primeThread。程序的主线程，即 TestThread主类的 main()方法
42、首先根据用户输入的命令行参数创建一个 primeThread类的对象，并调用 start()方法启动该子线程对象，使之进入就绪状态。主线程首先输出一行信息表示自己在活动，然后调用 sleep()方法使自己休眠一段时间以便子线程获取处理器。这是因为主线程创建的子线程与之优先级相同，如果主线程不让出处理器，则子线程只能等待主线程执行完毕才能获得处理器，进入运行状态的子线程将检查一个数值是否是素数并显示出来，然后休眠一段时间以便父线程获得处理器。获得处理器的父线程将显示一行信息表示自己在活动，然后调用 sleep()方法使自己也休眠一段时间以便子线程获得处理器。获得处理器的父线程将显示一行信息表示自
43、己在活动然后再休眠。如此循环，每次子线程启动都检查新增的数据是否为素数并打印，直至该数大于其预定的上限。此时子线程从 run()方法返回并结束其运行，然后主线程也结束。(1)空缺处所填写的语句用于等待一个键盘输入，否则就保留屏幕，因此(1)空缺处应填入“system.in.read()”。m_bContinue 是本线程是否继续的标志，(2)空缺处应填入该标志以判断本线程是否继续执行。由于子线程中所检查的数值大于其预定的上限之前 while循环一直都进行，根据(3)空缺处所在的 for 循环语句的“i+”和 if(number %i=0)判断语句可知，对于检查 number是否为素数的(3)空缺处应填入inti=2；inumber。flag是用来标志该数是否是素数的，如果为真，则表示是素数。number%i=0 表示数 number不是素数，所以(4)中缺处应填入“flag=false”。(5)空缺处应填入“flag=true”以恢复 flag，准备检查下一个 number。
