历届试题 - 1997年度高级程序员级 下午试卷.htm

几套关于程序员初级和高级的试题和答案

            node{ <BR>int data; <BR>struct node *link; <BR>} NODE; 
            <BR>NODE*s[N]; <BR>int i,j,n,t; <BR>NODE *q,*p,*x,*y,*top; 
            <BR>main() <BR>{ printf(“Enter number of parts.”); 
            <BR>scanf(“%d”,&amp;n); <BR>for(i=0;ibr&gt; printf(“Enter 
            pairs./n”); <BR>white (scanf(“%d%d”,&amp;i,&amp;j)= =2) <BR>{ 
            /*输入相连部件对，生成相连部件结点链表*/ <BR>p=(NODE *)malloc(sizeof(NODE)); 
            <BR>p-&gt;data=j; p-&gt;link=s[i]; s[i]=p; <BR>p=(NODE 
            *)malloc(sizeof(NODE)); <BR>P-&gt;data=i; p-&gt;link=s[j]; s[j];=p; 
            <BR>} <BR>for(i=0;ibr&gt; for(top=s[i],____(1)____;top!=NULL;) <BR>{ 
            /*将第i链表移入top工作链表，并顺序处理工作链表的各结点*/ <BR>q=top;____(2)____; 
            <BR>if(s[j=q-&gt;data]!=NULL) <BR>{ /将j链表也移入工作链表*/ 
            <BR>for(p=s[j];p-&gt;link ！=NULL;p=p-&gt;link); <BR>p-&gt;link=top; 
            top=s[j];____(3)____; <BR>} <BR>/*在重新生成的第i链表中寻找当前结点的插入点*/ 
            <BR>for(y=s[i];____(4)____;x=y,y=y-&gt;link); <BR>if(y!=NULL 
            &amp;&amp; y -&gt;data= =q-&gt;data) 
            <BR>free(q);/*因重新生成的第i链表已有当前结点，当前结点删除* / <BR>else { /* 
            当前结点插入重新生成的i链表*/ <BR>__-__(5)____； <BR>if(y= =s[i]) s[i]=q; <BR>else 
            x-&gt;link=q; <BR>} <BR>} <BR>for(i=0;ibr&gt; { /*输出结果*/ <BR>if 
            (s[i]= =NULL)continue; <BR>for(p=s[i];p!=NULL;) <BR>{ 
            printf(“\t%d”,p-&gt;data); <BR>q=p-&gt;link; free(p); p=q; <BR>} 
            <BR>printf(“\n”); <BR>} <BR>} <BR><BR>试题七 
            <BR>阅读以下程序说明和FORTRAN程序，将应填入__(n)__处的字句，写在答卷的对应栏内。 <BR>[程序说明] 
            <BR>本子程序实现地图的着钯。在地图上，一个国家所着的颜色必须与所有相邻的国家所着的颜色不同。现已证明，仅需四种不同的颜色就能解决地图的着钯 
            <BR>若地图上有N个国家，分别用1至N编号。子程序中用数组INDEX（N，2）和BORDER（M）存放N个国家的相邻情况。INDEX（I，1）和INDEX（I，2）分别表示与第I国相邻的国家编号在数组BORDER中的起始位置和终止位置，即这些邻国的编号存放在BORDER（INDEX（I，1））至BORDER（INDEX（I，2））中。例如，对应于图1所示的地图，数级INDEX和BORDER具有如下值： 
            <BR><BR><BR><BR>INDEX= 
            <BR><BR><BR><BR>BORDER-（2，3，4，5，1，3，1，2，4，5，1，3，5，1，3，4） 
            <BR><BR><BR>子程序中分别用1，2，3，4代表四种不同颜色，着色结果存放在数组COLOR中，即数组元素COLOR（I）的值为第I个国家所着的颜色。 
            <BR>子程序采用试控法找解。首先从第I个国家着第一种颜色开始，顺序为各个国家寻找着色方案。对第I个国家，当为它找到一种未被它的相邻国家着色的颜色时，就用该颜色对此国家着色，并准备处理下一国家；当不能为它找到一个未被它的相邻国家着色的颜色时，就回溯——即改变第I-1个国家的着色方案。直至最终为全部国家找到着色方案。 
            <BR><BR>[程序] <BR><BR>SUBROUTINE P（INDEX，BORDER，COLOR，N，M） 
            <BR>INTEGER INDEX（N，2），BORDER（M），COLOR（N） <BR>DO 10 I=1，N 
            <BR>COLOR（I）=0 <BR>I=1 <BR>IF（__(1)__）THEN <BR>K=COLOR(I)+1 
            <BR>IF(__(2)__)THEN <BR>J=INDEX(I,1) <BR>IF(J.LE.INDEX(I,2))THEN 
            <BR>IF(__(3)__)THEN <BR>J=J+1 <BR>GOTO 20 <BR>ELSE <BR>K=K+1 
            <BR>____(4)____ <BR>ENDIF <BR>___-(5)____ <BR>I=I+1 <BR>GOTO 40 
            <BR>ENDIF <BR>COLOR9I)=0 <BR>_____(6)_____ <BR>GOTO 40 <BR>ENDIF 
            <BR>IF(I.EQ.0)THEN <BR>WRITE(*,*)’NO SOLUTION’ <BR>ENDIF <BR>END 
            <BR><BR>试题八 <BR>阅读以下程序说明和C程序，将应填入__(n)__处的字句，写在答卷的对应栏内。 <BR>[程序说明] 
            <BR>一个相连的区域被不规则地分割成n个不同的小区域；每个小区域与若干其它小区域相邻接。现用cn种不同颜色为该区域着色，要求每个小区域着同一种颜色，相邻小区域着不同颜色。 
            <BR>设小区域被顺序编号为0，1，…，n-1。每个小区域与其它小区域的邻接关系用两维数组bordering表示，元素bordering[i][j]表示i号小区域与j 
            号小区域之间的邻接关系： <BR><BR>0 j小区域与i小区域不邻接 <BR>bordering[i][j]= <BR>1 
            j小区域与i小区域相邻接 
            <BR><BR>程序中，把计算结果存入于两维数组colored中，颜色编号为0,1,…,cn-1,元素colored[coler][j]的含义是 
            <BR><BR>0 j小区域不用颜色color着色 <BR>colored[color][j]= <BR>1 
            j小区域用颜色color着色 
            <BR><BR>函数colorcountry(bordering,colored,n,cn)根据所给的小区域邻接关系数组bordering、小区域个数n 
            、颜色数cn，将找到的着色方案记录在数组colored中。函数采用试探法找解。首先从第一个小区域着第一种颜色开始顺序为各小区域找着色方案。对某个小区域，当为它找到一种未被它的相邻小区域着色的颜色时，就用该颜色对该小区域着色，并准备处理下一个小区域。当不能为某个小区域找到一个未被它的相邻小区域着色的颜色时，就回溯。如最终为全部小区域找到着色方案，函数返回1；否则，函数返回0。 
            <BR>程序假定小区域个数不超过20，颜色数为4。 <BR><BR>[程序] <BR><BR>#include <BR>#define 
            n 20 <BR>#define CN 4 <BR>int colorcountry(int bordering[][N], int 
            colored[][N], int n,int cn) <BR>{ int color,used,i,c; 
            <BR>for(color=0;colorbr&gt; for(i=0;ibr&gt; c =0; /*从第1个小区域开始*/ 
            <BR>color =0; /*从着第1种颜色开始试控*/ <BR>while(cbr&gt; { /*还未对全部小区域着色时循环*/ 
            <BR>while(___(1)___)/*顺序对每种颜色作试探*/ <BR>{/*检查当前颜色是否已被某相邻小区域着色*/ 
            <BR>for (i=0, used=0; !used &amp;&amp; ibr&gt; 
            if(____(2)____)used=1; <BR>if(!used)break; /*当前颜色未被相邻小区域着色*/ 
            <BR>color++ <BR>} <BR>if(!used) <BR>{ /*找到一种可用颜色，用此色着色，并准备处理下一个小区域*/ 
            <BR>____(3)____=1; color=0; <BR>}else{/*未找到一种可用颜色，回溯*/ <BR>c--;if 
            (c&lt;0)return 0; /*发现没有解的情况*/ <BR>for(color=0;____(4)____;color++); 
            <BR>____(5)____=0 <BR>} <BR>} <BR>return 1; <BR>} <BR>print(int 
            colored[ ][N],int n,int cn) /*输出结果*/ <BR>{ char *colort[ 
            ]={“RED”,”BLUE”,”GREEN”,”YELLOW”}; <BR>int color,i; 
            <BR>for(color=0;colorbr&gt; { printf(“\n%s;\n”,colortb1[color]); 
            <BR>for(i=0;ibr&gt; if(colored[color][i]) printf(“\t%d”,i); 
            <BR>printf(“\n”); <BR>} <BR>} <BR>int 
            colored[CN][N],bordering[N][N]; <BR>main() <BR>{ int c,i,j,n; 
            <BR>printf(“Enter number of areas.”); scanf(“%d”,&amp;n); 
            <BR>printf(“Enter bordering:\n”); <BR>for(i=0;ibr&gt; 
            for(j=0;jbr&gt; for(i=0;ibr&gt; { printf(“Enter areas to link %d 
            area(&lt;0 to next).\n”,i); <BR>scanf(“&amp;d”,&amp;j); 
            <BR>while(j&gt;=0) <BR>{ if(i !=j) 
            bordering[i][j]=bordering[j][i]=1; <BR>scanf(“%d”,&amp;j); <BR>} 
            <BR>} <BR>if(colorcountry(bordering,colored,n,CN)) 
            <BR>print(colored,n,CN); <BR>else printf(“No Solution.\n”); <BR>} 
        </TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width=755 align=center bgColor=#ffffff 
border=0>
  <TBODY>
  <TR vAlign=top>
    <TD>
      <TABLE cellSpacing=0 cellPadding=0 width="98%" align=center border=0>
        <TBODY>
        <TR>
          <TD>
            <HR noShade SIZE=1>

            <TABLE cellSpacing=0 cellPadding=1 width="60%" align=center 
border=0>
              <FORM name=reviewform action=/admin/addreview.php method=post>
              <TBODY>
              <TR bgColor=#eeeeee>
                <TD colSpan=2><B>发表你的评论&gt;&gt;</B></TD></TR>
              <TR>
                <TD vAlign=top width=213>您的名字:</TD>
                <TD vAlign=top width=542><INPUT size=32 name=mf_name> </TD></TR>
              <TR>
                <TD vAlign=top width=213>E-mail:</TD>
                <TD vAlign=top width=542><INPUT size=32 name=mf_email> </TD></TR>
              <TR>
                <TD vAlign=top width=213>评论内容:</TD>
                <TD vAlign=top width=542><TEXTAREA name=mf_reviewtxt rows=4 cols=32></TEXTAREA> 
                </TD></TR>
              <TR>
                <TD>&nbsp; </TD>
                <TD><INPUT class=inputclass style="WIDTH: 35px" type=submit value=发表! name=Submit> 
                  <BR>&nbsp; </TD></TR><INPUT type=hidden value=49 name=mf_pageid> 
              <INPUT type=hidden value=submitted name=mf_action> 
            </FORM></TBODY></TABLE>
            <TABLE cellSpacing=0 cellPadding=0 width="60%" align=center 
border=0>
              <TBODY>
              <TR bgColor=#eeeeee>
                <TD width="50%"><B>关于本文的评论:</B></TD>
                <TD><A href="http://www.xiaohui.com/admin/dispallreview.php" 
                  target=_blank>点此查看所有评论&gt;&gt;</A></TD></TR>
              <TR>
                <TD 
    colSpan=2>目前暂无任何评论</TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></TD></TR>
  <TR>
    <TD>&nbsp;</TD></TR></TBODY></TABLE><!-- #EndEditable -->
<TABLE cellSpacing=0 cellPadding=0 width=755 align=center bgColor=#ffffff 
border=0>
  <TBODY>
  <TR bgColor=#dddddd height=1>
    <TD></TD></TR>
  <TR align=middle bgColor=#efefef>
    <TD><A href="http://www.xiaohui.com/about/contact.htm">联系我</A> | <A 
      href="http://www.xiaohui.com/webmap.htm">站内导航</A> | <A 
      href="http://www.xiaohui.com/about/maillist.htm" target=_self>订阅邮件</A> | 
      <SPAN id=add_bookmark style="CURSOR: hand" 
      onclick="window.external.addFavorite('http://www.XiaoHui.com','小辉程序员之路')">加入书签</SPAN> 
      | <A class=text2 
      onclick="this.style.behavior='url(#default#homepage)';this.setHomePage('http://www.XiaoHui.com');" 
      href="http://www.xiaohui.com/dev/exam/st/97x.htm#" target=_self>设为首页</A> 
    </TD></TR>
  <TR bgColor=#dddddd height=1>
    <TD></TD></TR></TBODY></TABLE>
<TABLE borderColor=#000000 height=80 cellSpacing=0 cellPadding=0 width=755 
align=center bgColor=#ffffff border=0>
  <TBODY>
  <TR align=middle borderColor=#ffffff>
    <TD><A href="http://www.xiaohui.com/">小辉程序员之路</A>(<A 
      href="http://www.chinaithero.com/">中国镜像</A>|<A 
      href="http://www.xiaohui.com/" target=_self>美国镜像</A>) ◇ 
      做一名最好的开发者是我不变的理想……<BR>Copyright(C) 1998-2004 XiaoHui.com &amp; 
      ChinaITHero.com &nbsp; All rights reserved<BR><FONT 
      color=#ff0000>声明：站内所有原创文字，未经许可，不得转载、复制。</FONT></TD></TR></TBODY></TABLE><BR><!-- #EndTemplate --></BODY></HTML>