1、初级程序员下午试题-58 及答案解析(总分：120.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)阅读以下技术说明、流程图和 C程序，根据要求回答问题 1和问题 2。【说明】如图 6-13所示的程序流程图描述了对 8位二进制整数求补的算法。该算法的计算过程如下：从二进制数的低位(最右位)开始，依次向高位逐位查看，直到首次遇到“1”时，停止查看。然后，对该“1”位左面的更高位(如果存在的话)，逐位求反，所得的结果就是对原二进制数求补的结果。例如：对二进制整数10010110求补的结果时 01101010。设 8位二进制整数中的各位，从低位到高位，依次存放在整型数组
2、BIT的 BIT1BIT8中。例如，二进制整数 10010110存放在数组 BIT后，则有 BIT1=0，BIT2=1，BIT7=0，BIT8=1。若流程图中存在空操作，则用 NOP表示。（分数：15.00）(1).【问题 1】请将图 6-13流程图中(1)(5)空缺处的内容补充完整。其中，(1)空缺处按“循环变量名：循环初值，增量，循环终值”格式描述。（分数：7.50）_(2).【问题 2】待修改的【C 程序】中存在 3个错误，请指出各个错误所在的行号，并给出相应的修改意见。（分数：7.50）_二、B试题二/B(总题数：1，分数：15.00)1.【说明】 以下【C 程序】的功能是，逐一从指定
3、课程成绩文件中读入学生的考号和成绩，对同一学生汇总他(她)的总成绩，并按如图 6-14所示格式输出名次(按总成绩由高到底的顺序)、总成绩、同一名次的学生人数、同一名次学生的学号(按学号由小到大的顺序)。 （分数：15.00）_三、B试题三/B(总题数：1，分数：15.00)2.【说明】 著名的四色定理指出任何平面区域图均可用 4种颜色着色，使相邻区域着不同的颜色。以下C程序对给定的区域图找出所有可能的不超过 4种颜色的着色方案。该程序中用 14 分别表示 4种颜色。要着色的 N个区域用 0-1 编号，区域相邻关系用 adj矩阵表示，矩阵的 i行 j列的元素为 1，表示区域 i与区域了相邻；矩阵
4、的 i行 j列的元素为 0，表示区域 i与区域 j不相邻。数组 color用来存储着色结果，colori的值为区域 i，所着颜色。 【C 程序】 #include stdio.h #define N 10 void output(int color) /*输出一种着色方案*/ int i ; for ( i = 0 ; i N ; i+ ) printf( “%4d“ , colori ) ; printf (“/n“) ; int back(int *ip ,int color ) /*回溯*/ intc = 4 ; while ( c = 4 ) if ( *ip = 0 ) return
5、 0 ; - (*ip) ; c =U (1) /U; color*ip =-1 ; return c ; /*检查区域 i，对 c种颜色的可用性*/ int colorOk(int i , intc , int N ,int color ) int j ; for (j = 0 ; j i ; j+ ) if (U (2) /U) return 0 ; return 1 ; /*为区域 i选一种可着色的颜色*/ int select (int i ,int c ,int adj N ,int color ) int k ; for(k = c ; k = 4 ; k+ ) if( color
6、OK(U (3) /U) return k ; return 0 ; int coloring(int adj N) /*寻找各种着色方案*/ int colorN , i , c , cnt ; for(i = 0 ; i N ; i+) colori =-1 ; i = c = 0 ; cnt = 0 ; while(1) if(c =U (4) /U) = 0 c = back( if( c = 0 ) return cnt; else U (5) /U; i+ ; if i = N) output(color); +cnt ; c = back( else c = 0 ; void m
7、ain()( int adjN N = 0,1,0,1,1,1,1,1,1,1, 1,0,1,1,0,1,1,1,1,0, 0,1,0,1,0,1,1,0,1,1, 1,1,1,0,1,1,0,0,1,1, 1,0,0,1,0,1,0,0,0,0, 1,1,1,1,1,0,1,0,0,1, 1,1,1,0,0,1,0,0,1,0, 1,1,0,0,0,0,0,0,1,1, 1,1,1,1,0,0,1,1,0,1, 1,0,1,1,0,1,0,1,1,0, ; printf(“共有%d 组解./n“,coloring(adj); （分数：15.00）_四、B试题四/B(总题数：1，分数：15.0
8、0)3.【说明】对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合a,b,c,d及其权值 2、7、4、5，可构造如图 6-15所示的最优二叉树，以及相应的结构数组 Ht(如表 6-14所示，其中数组元素 Ht0不用)。B表 6-14 结构数组 Ht/B B数组下标/B ch weight parent lchild rchild1 a 2 5 0 02 b 7 7 0 03 c 4 5 0 04 e 5 6 0 05 6 6 1 36 11 7 4 57 18 0 2 6结构数组 Ht的类型定义如下：#define MAXLEAFNUM
9、20struct nodechar ch; /*扫当前节点表示的字符，对于非叶子节点，此域不用*/Int weight； /*当前节点的权值*/int parent; /*当前节点的父节点的下标，为 0时表示无父节点*/int lchild, rchild;/*当前节点的左、右孩子节点的下标，为 0时表示无对应的孩子节点*/)Ht2*MAXLEAFNUM;用“0”或“广标识最优二叉树中分支的规则是：从一个节点进入其左(右)孩子节点，就用“0”(或“1”)标识该分支，如图 6-15所示。若用上述规则标识最优二叉树的每条分支后，从根节点开始到叶子节点为止，按经过分支的次序将相应标识依次排列，可得到
10、由“0”、“1”组成的一个序列，称此序列为该叶子节点的前缀编码。例如，图 6-15所示的叶子节点 a、b、c、d 的前缀编码分别是 110、0、111、10。（分数：15.00）_五、B试题五/B(总题数：1，分数：15.00)从下列 3道试题(试题 5至试题 7)中任选 1道解答。如果解答的试题数超过 1道，则题号小的 1道解答有效。阅读以下应用说明及 Visual Basic程序代码，根据要求回答问题 1至问题 3。【说明】在 Visual Basic程序中，设计一个“个人所得税计算器”，其应用程序的运行窗口如图 6-16所示。（分数：15.00）(1).【问题 1】请根据【说明】信息和如
11、图 6-16的显示效果，将【Visual Basic 程序】中(1)(5)空缺处的程序语句填写完整。（分数：5.00）_(2).【问题 2】若要求在图 6-16窗口中，用户输入月工资(或薪金收入)后，直接按回车键或向下方向箭就能使焦点(当前光标)跳到应扣除的基本费用的输入文本框，而不用【Tab】键进行切换。请将以下文本框 ht_salary的 KeyDown(按键)事件过程中空缺的程序代码填写完整。If KeyCode = 13 Or KeyCode = 40 ThenU (6) /UEnd If（分数：5.00）_(3).【问题 3】为使应用程序启动时所载入的窗口(图 6-16)中具有背景图
12、像(取自用户自定义的某个图像文件“C:/user/background.bmp”)，并且在程序运行时，当被遮的该窗口又重现时，其背景图像会自动重画。在开发如图 6-16所示窗体时，应对窗体属性对话框(图 6-17)中哪些关键属性进行什么样的设置?（分数：5.00）_六、B试题六/B(总题数：1，分数：15.00)请认真阅读以下关于某传输系统的技术说明、状态转换图及 C+代码，根据要求回答问题 1和问题 2。【说明】传输门是传输系统中的重要装置。传输门具有 Open(打开)、Closed(关闭)、Opening(正在打开)、StayOpen(保持打开)和 Closing(正在关闭)5 种状态。触
13、发状态的转换事件有 click、complete 和 timeout 3种，事件与其相应的状态转换如图 6-18所示。（分数：15.00）(1).【问题 1】请将以上【C+代码 1】与【C+代码 2】程序段中的(1)(7)空缺处的语句填写完整。（分数：7.50）_(2).【问题 2】请用 150字以内的文字简要说明【C+代码 1】、【C+代码 2】这两种对传输门进行状态模拟的设计思路的区别之处。（分数：7.50）_七、B试题七/B(总题数：1，分数：15.00)阅读以下技术说明、Java 源程序和运行测试部分，根据要求回答问题 1和问题 2。【说明】1HTTP HTTP 请求消息示例GET/i
14、ndex,htmlHTTP/1.1Accept:image/gif,image/jpeg,*/*Accept-Language:zh-chAccept-encoding:gzip,deflateUser-Agent:Mozilla/4.0(compatible: MSIE6.0;Windows 2003)Host:localhost:8080Connection:Keep-Alive HTTP 响应消息示例HTTP/1.1 200 OKServert:Microsoft-IIS/6.0Date:Mon,3 Jan 2008 13:13:33 GMTContent-Type:text/htmlL
15、ast-Modified:Mon,11 Jan 2008 13:23:42 GMTContelit-Length:112html./html2相关类及主要成员函数 ServerSocket 类服务器端套接字，它监听固定端口，以接收来自客户端的连接请求，一旦建立连接就返回一个 Socket类型的对象，类中的主要成员函数如表 6-16所示。B表 6-16 ServerSocket类的主要成员函数/B B函数名/B B功能说明/BServerSocket(PORT) 构造函数Accept() 返回建立连接的 Socket类型的对象Close() 关闭当前的 ServerSocket类型的对象Sock
16、et 类 基于连接的套接字，类中的主要成员函数如表 6-17所示。B表 6-17 Socket类的主要成员函数/B B函数名/B B功能说明/BGetnetAddress() 返回 InetAddress类型的对象，该对象封装了与该套接字所关联的客房机的 IP地址GetInputSffeam 返回当前对象所关联的输入流GetOutputStream 返回当前对象所关联的输出流Close() 关闭当前对象【Java 源程序：一个简单的 Web服务器】/* WebScrvc.java */packageobjclass;import .*;import java.io.*;public class
17、 WebServerpublic static final int PORT=8080; /Web服务器侦听的端口号public static final String WEB_ROOT= SyStem.getProperty(“user.dir“)+File.separator+“webroot“;/WEB_ROOT变量存放 Web服务器工作目录，HTML, GIF 图片等静态文件资源private static final String SHUTDOWN_COMMAND=“/shutdown“;/SHUTDOWN_COMM_AND变量保存关闭服务器的命令private Boolean sh
18、utdown=false; /是否收到关闭服务器命令的标志public static void main(Sting args) WebServer server=new WebServer();Server.await ()public void await() ServerSocket serverSocket = null;try serverSocket = newU (1) /U;/创建侦听端口号为 PORT的 ServerSocket类型的对象System.out.println (“WebServerStarted!“);catch(IOException e) e.printS
19、tackTrace ();SyStem. exit (1);while(!shutdown) /循环等待客房端连接Socket socket = null;InputStream input = null;OutputStream output = null;trySocket =U (2) /U; /创建来自客房端的连接套接字Input = socket.U (3) /U; /创建输入流Output = socket.U (4) /U; /创建输出流Request request = new Request (input); /创建 request对象Request.U (5) /U; /解
20、析客户端 HTTP请求Response response = new ReSponse(output); /创建 Response对象response, setRequest (request); /将 request对象传递给 response对象response.U (6) /U; /给客户端发送所请求的静态资源U (7) /U; /关闭连接套接字shutdown = request.U (8) /U.equals (SHUTDOWN_COMMAND);/凑数当前 HTTP请求中的 URL是否是关闭服务器命令Catch(Exception e) e.printStackTrace ();c
21、ontinue;/* Request.java */package objclass;import java.io.InputStream;import java.iO.IOException;public Class Requestprivate InputStream input;private String url;public Request(InputStream input)this.input = input;public void parse() . parseUrl() ;. /解析客户端 HTTP请求消息private String parseUrl(String requ
22、estString). /解析客户端 HTTP请求中的 URLpublic String getUrl()return url;/* Response.java */package objclass;import java.io.*;public class Responseprivate static final int BUFFER_ SIZE=1024;Request request;OutputStream output;public Response(Output Strearm output) this.output=output;public void setRequest(Re
23、quest request)this.request=request;public void sendStaticResource()throwsIOmxception. /向客户端发送所请求的静态资源（分数：15.00）(1).【问题 1】请将以上【Java 源程序】中的(1)(8)空缺处的内容填写完整。（分数：7.50）_(2).【问题 2】对以上【Java 源程序】进行运行测试，请将以下(9)、(10)空缺处的测试命令填写完整。在本机运行 WebServer程序，然后打开 IE浏览器。1)在 IE地址栏中，输入请求“/index.html”页面的命令：U (9) /U。2)在 IE地址栏
24、中，输入关闭 Web服务器的命令：U (10) /U。（分数：7.50）_八、B试题八/B(总题数：1，分数：15.00)4.【说明】 使用 MFC的 CSocket类在两个或者多个应用程序之间建立通信。服务器应用程序先创建一个特殊的 Socket，用于监听客户应用程序的连接请求，然后再创建新的 Socket来完成连接。从客户和服务器两端读取该连接，直到一个需要处理的报文到来为止。以下 Visual C+程序将封装这些功能，这样所有应用程序需要完成的只是创建一个 Socket连接，然后处理到来的报文。这将包括一个新的服务器 Socket类、新客户端Socket类和新的报文队列类。 创建新的服务
25、器 Socket类程序的框架如下。第 1个函数 ListenEx()用于通知Socket开始监听客户应用程序。第 2个函数 OnAccept()在接收到连接请求时被调用。在其中创建新的Socket，并立刻设置它开始从客户应用程序读取报文，这些是通过调用第 3个函数 RecvThread()来完成的，该函数位于它自己的线程中。 【Visual C+程序】 【ListenEX()函数】 void CWzdServer:ListenEx( int hdrSz, int bodyPos, CWzdQueue *pQueue,CWnd *pWnd, UINT id ) /初始化接收数据 m_RecvDa
26、ta.hdrSz = hdrSz; m_RecvData.bodyPos = bodyPos; m_RecvData.pQueue = pQueue; m_RecvData.pWnd = pWnd; m_id = id; /启动标志 /开始监听 U(1) /U 【OnAccept()函数】 void CWzdServer:OnAccept ( iht nErrorCode ) if ( nErrorCode = 0 ) CSocket *pSocket =U (2) /U; /创建新的套接字并添加到映射图中 m_mapSocketsm_id = pSocket; Accept( ( Casyn
27、cSocket /用该新的套接字去连接客户端 /置套接字于同步模式 DWORD arg = 0; pSocket - AsyncSelect( 0 ); pSocket - IOCtl( FIONBIO, m_RecvData.pSocket = pSocket; m_RecvData.id = m_id+; /启用线程 AfxBeginThread( RecvThread, 【RecvThread()函数】 UINT RecvThread( LPVOID pParam ) /从线程中苑取数据 RECVDATA *pRecv = ( RECVDATA * )pParam; int len =
28、1; int error = 0; char *pBody = NULL; char *pHdr = NULL; /两个套接字都开放 while (TRUE) /开始读报文头部 iht res; pBody = NULL; pHdr = new charpRecv - hdrSz; if ( ( res = pRecv - pSocket - CAsyncSocket:Receive( pHdr, pRecv -hdrSz ) =SOCKET_ERROR ) error = :GetLastError(); else len = res; /如果完毕，则退出线程 if ( len = 0 |
29、error = WSAECONNRESET | error = WSAECONNABORTED ) break; if ( !error pBody = new charbodyLen; if(res=pRecv - pSocket CAsyncSocket:Receive(pBody,bodyLen)=SOCKET_ERROR) error = :GetLastError(); else U (3) /U; /如果完毕，则退出线程 if(len = 0 | error = WSAECONNRESET | error = WSAECONNABORTED) break; /将消息排入队列 pRe
30、cv - pQueue -Add(new CWzdMsg(pRecv - id,pHdr, p B o d y,len,error) ); /传送消息到窗口来处理新信息 pRecv - pWnd - PostMessage(WM_NEW_MESSAGE); /清记录 delete pHdr; delete pBody; /向相关对象发送停止通知 pRecv-pWnd-SendMessage(WM_DONE_MESSAGE, WPARAM)pRecv-id, (LPARAM)error); U(4) /U; 【SendEx()函数】 void CWzdServer:SendEx( int id,
31、 LPSTR lpBuf, int len ) /为该标识符设置套接字 CSocket *pSocket =U (5) /U; if ( pSocket ) m_SendData.pSocket = pSocket; m_SendData.lpBuf = lpBuf; m_SendData.len = len; /启动线程 AfxBeginThread( SendThread, 【SendThread()函数】 UINT SendThread( LPVOID pParam ) SENDDATA *pSend = ( SENDDATA * )pParam; /从线程中获取数据 pSend - p
32、Socket -U (6) /U( pSend - lpBuf, pSend - len ); /执行写入操作 return 0; 【CloseEx()函数】 void CWzdServer:CloseEx() int id; CSocket *pSocket; for ( POSITION pos = m_mapSockets.GetStartPosition(); pos; ) m_mapSockets.GetNextAssoc( pos,id,pSocket ); pSocket - Close(); U(7) /U; （分数：15.00）_初级程序员下午试题-58 答案解析(总分：12
33、0.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)阅读以下技术说明、流程图和 C程序，根据要求回答问题 1和问题 2。【说明】如图 6-13所示的程序流程图描述了对 8位二进制整数求补的算法。该算法的计算过程如下：从二进制数的低位(最右位)开始，依次向高位逐位查看，直到首次遇到“1”时，停止查看。然后，对该“1”位左面的更高位(如果存在的话)，逐位求反，所得的结果就是对原二进制数求补的结果。例如：对二进制整数10010110求补的结果时 01101010。设 8位二进制整数中的各位，从低位到高位，依次存放在整型数组 BIT的 BIT1BIT8中。例如，二进制整数
34、10010110存放在数组 BIT后，则有 BIT1=0，BIT2=1，BIT7=0，BIT8=1。若流程图中存在空操作，则用 NOP表示。（分数：15.00）(1).【问题 1】请将图 6-13流程图中(1)(5)空缺处的内容补充完整。其中，(1)空缺处按“循环变量名：循环初值，增量，循环终值”格式描述。（分数：7.50）_正确答案：()解析：(1)i：1，1，8 (2)1sw (3)0BITi (4)NOP，或空操作 (5)1BITi 要点解析 由于题目中给出了对 8位二进制整数求补的算法，并且指明将 8位二进制整数中的各位，从低位到高位，依次存放在整型数组 BIT的 BIT1BIT8中，
35、因此，循环控制变量的初值应该为 1(从二进制数中的最低位开始)、终值为 8(二进制数中的每一位都要检查)、增量为 1(每次检查 1位)，按照“循环变量名：循环初值，增量，循环终值”格式描述，则(1)空缺处所填写的内容为“i：1，1，8”。0 由题目中给出的算法可知，从最右位开始向左找到的第一个“1”及其右边的各位是不取反的，因此需要一个标志，sw 起的就是这个作用。由于 SW的初始值为 0，因此在找到从右边数的第 1个“1”之前，当 BITi等于“0”且 SW=O时，则说明这些二进制位无须取反，对应于流程图的(4)空缺处的操作应为空操作(即 NOP)。 当某个 BITi的值等于“1”且 SW的
36、值等于 0，则说明找到了从右边数的第 1个“1”，此时应将 SW的值置为非“0”，因此流程图中(2)空缺处的操作要对 SW置 1，即该空缺处所填写的内容是“1sw”。 最后，应将其余各位取反，即 BITi等于 1时，要在流程图的(3)空缺处将其置 0(即 0BITi)；反之，则要在流程图的(5)空缺处将其置 1(即 1BITi)。(2).【问题 2】待修改的【C 程序】中存在 3个错误，请指出各个错误所在的行号，并给出相应的修改意见。（分数：7.50）_正确答案：()解析：第 3行，变量 num没有初始化，应将其初始值设为 0第 7行，scanf 函数参数错，应将语句“scanf(“%1d“,
37、n);”中的 n修改为“”。由于变量num没有赋初值，因此系统不保证对其进行初始化，导致程序的运行结果不确定建议将其初始值设为 0第 7行scanf函数参数错，即输入变量时忘记使用地址符号(动态语义错误)，导致程序运行时，变量 n不能正确接收输入的数据建议将语句“scanf(“%1d“,n);”修改为“scarlf(“%1d“,”第 10行 循环条件错误，可能导致无穷循环建议将语句“for(i=1;n=O;i+)”修改为“for(i=1;n0;i+)”二、B试题二/B(总题数：1，分数：15.00)1.【说明】 以下【C 程序】的功能是，逐一从指定课程成绩文件中读入学生的考号和成绩，对同一学生
38、汇总他(她)的总成绩，并按如图 6-14所示格式输出名次(按总成绩由高到底的顺序)、总成绩、同一名次的学生人数、同一名次学生的学号(按学号由小到大的顺序)。 （分数：15.00）_正确答案：()解析：(1)isp 或 i!=sp或其他等价的形式 (2)h=p (3)u-next=p (4)u-next (5)u-next (6)C+,u=u-next (7)i=c，或 c-!=0，或 u!=v，或 c-0，或 c-或其他等价的形式 要点解析 通读题干说明和 C程序之后可知，该 C程序首先从指定的文件中输入某个科目的学生学号和成绩，并进行合法性检查，全部输入完成后，按总成绩进行排序。程序采用链表
39、结构进行存储，最后按指定的格式输出。 该应用程序首先输入数据，(1)空缺处所在的 for循环语句是对输入的数据进行检查，数组 s的作用是记录已经输入的科目。当输入一个科目之后，就在数组 s中进行检查处理。如果已有该科目，就提示“该科目的成绩已输入，请输入别的科目成绩文件”信息，要求用户重新输入。其中，if 语句用于判断是否有该科目，因此(1)空缺处所填写的内容是“isp”或“i!=sp”。 接着在链表中寻找最近输入的学号，循环语句“for(v=h;v!=NULL u=v,v=v-next);”结束之后，通过 if.else语句对循环的出口进行判断，(2)、(3)空缺处是对应没有该学生的成绩(即
40、是一位新学生)的情况，此时需要申请存储空间，然后进行赋值并把它插入到链表中。由于链表是排序的，因此需要判断插入点是否是第 1个节点。如果是第 1个节点，就需要修改表头节点的指针，因此(2)空缺处所填写的内容是“h=p”，(3)空缺处所填写的内容为“u-next=p”。 接下来程序通过 while循环对链表按总成绩的高低和学号从小到大的顺序进行排序。通读 C程序可知，指针 p所指向的节点应在指针 u所指向的节点之前(或等于)，指针v所指向的节点为当前节点。在内循环结束之后，若 p!=v，则表示找到一个满足排序条件的节点，此时就需要移动指针。因此(4)、(5)空缺处所填写的内容均为“u-next”
41、。 应用程序的最后一个 while循环语句，其功能是对排序后的链表按指定的格式进行输出。变量 c的功能是计数器，用来记录总成绩相等的人数，因此(6)空缺处所填写的内容的作用是使指针 u下移，计数器加 1，即该空缺处应填入“c+,u=u-next”。 变量 Order的作用是记录名次，而(7)空缺处所在的 for循环语句的功能是，输出成绩相同的学生的学号。由于计数器 c的初值为 1，因此该 for循环的结束条件为 c=O或 i=c。由此进一步推知，(7)空缺处所填写的内容是“c-!=0”或“i=c”或其他等价的形式。三、B试题三/B(总题数：1，分数：15.00)2.【说明】 著名的四色定理指出
42、任何平面区域图均可用 4种颜色着色，使相邻区域着不同的颜色。以下C程序对给定的区域图找出所有可能的不超过 4种颜色的着色方案。该程序中用 14 分别表示 4种颜色。要着色的 N个区域用 0-1 编号，区域相邻关系用 adj矩阵表示，矩阵的 i行 j列的元素为 1，表示区域 i与区域了相邻；矩阵的 i行 j列的元素为 0，表示区域 i与区域 j不相邻。数组 color用来存储着色结果，colori的值为区域 i，所着颜色。 【C 程序】 #include stdio.h #define N 10 void output(int color) /*输出一种着色方案*/ int i ; for ( i = 0 ; i N ; i+ ) printf( “%4d“ , colori ) ; printf (“/n“) ; int back(int *ip ,int color ) /*回溯*/ intc = 4 ; while ( c = 4 ) if ( *ip = 0 ) return 0 ; - (*ip) ; c =U (1) /U
