试题四（共15分）

   阅读以下说明和C函数，填补C函数中的空缺(1)～(5)，将解答写在答题纸的对应栏内。

【说明】

   约瑟夫问题如下所述：有n个人(编号为1～n)围成一圈，从第1个人开始，按照顺时针方向从1开始计数到m（即数到第m个人），让其出圈，然后再从其顺时针方向的下一个人开始，依次计数到m并让其出圈，重复这个过程，直到所有人都出圈，试给出出圈者的顺序。

以n=5，m=3为例，其出圈顺序为3，1，5，2，4，过程如图4-1所示。

下面的函数Joseph()在单向循环链表表示的基础上模拟上述出圈过程。

n为5时的单向循环链表结构如图4-2所示。

   链表的结点类型定义如下：

   typedef struct Node{

        int no;

      struct Node *next;

}Node，*LinkList;

   函数Joseph(LinkList tail，int n，int m)的处理思路如下：

   (1)用k计数，每次都从O开始，当计数到m-l时结束本次计数；

   (2)通过指针p查找出圈者所对应的结点，当k的值等于m-l时，p应指向出圈者对应结点的前驱结点；

   (3)通过删除结点表示出圈处理；

   (4)当m大于圈中剩余人数时，为了避免重复计数，用模运算修改m的值；

   (5)计数和删除操作完成后再恢复m的原值。

 【C函数】

void Joseph(LinkList tail, int n,int m)

{

   LinkListp，q；

   Int k i，old_m=m;

   p= tail;

   for(i=n; i>l; --i){            /*i表示圈中剩余人数*/

      m=m%i;                /*避免重复计数*/

      if(0==m=  (1) ，

      k=0；

      while( k< (2)   ){

              (3) ；

          k++;

      }

      print("%d\n",   (4) )；  /*输出出圈者的编号*/

      q=p->next;

        (5) =q->next;         /*删除出圈者对应的结点*/

      free(q);

      m= old_m;

   }

   printf("%d\n", p->No);

 }

试题五（共15分）

   阅读以下说明、图和C++代码，填补C++代码中的空缺(1)～(5)，将解答写在答题纸的对应栏内。

【说明】

   已知某公司主要有两大类耗电资产(Asset)：计算机(ComputerAsset)和建筑物(Building Asset)。为了节约能源，通过控制各种电源，将可关闭的房灯、计算机显示器等在夜间关闭。

   为了实现上述需求，设计了如图5-1所示的类图，并用下面的C++代码加以实现。

【C++代码】

#include

#include

using namespace std;

class Asset{                      /*通用资产，基类*/

 public: virtual~Asset(){}

}；

class PowerSwitchable{            /*抽象基类，可在夜间关闭电源的物体接口*/

 public: virtualvoidpowerDown()=0; /*powerDown()函数接口*/

   virtual void powerUp()=0； /*powerUp函数接口*/

}；

class ComputerAsset：public Asset{  /*计算机资产*/

protected:int deskNumber;

public:

 ComputerAsset(int deskNumber){ this->deskNumber=deskNumber; }

   }；

   class ComputerCPU (1)   {   /*计算机主机，永不关闭*/

   public:

   ComputerCPU(intdeskNumber):ComputerAsset(deskNumber){ }

   }；

class ComputerMonitor   (2) { /*计算机显示器*/

 public:

 ComputerMonitor(int roomNumber):ComputerAsset(roomNumber),PowerSwitchable0{}

   ~ComputerMonitor(){}

   void powerDown(){ /*关电源，代码略*/ }

void powerUp(){ /*开电源，代码略*/ }

}；

/*BuildingAsset、BuildingLight、EmergencyLight 和 RoomLights 代码略*/

class BuildingManagement{

 private:

   Asset* things[24];int numltems,

 public:

   void goodNight(){/*值班员定时“关闭”时调用，关闭可关闭的电源*/

       for (int i=0; 1

           (3) ps= dynamic_cast(things[i]);

          if(ps !=0)

              ps->powerDown();

       }

   }

   /*goodMorning()与goodNight()类似，依次调用powerUp()，实现略*/

   void add(Asset* thing){ /*为建筑添加资产*/

       things[   (4)   ]=thing;

   }

}；

int main(){

   BuildingManagement* bl= (5)   BuildingManagement();

   bl->add(new RoomLights(101));      //101房间的控制灯

   bl->add(new EmergencyLight(101));   //101房间的应急灯

   bl->add(new ComputerCPU(10104));   //101房间4号桌上的计算机主机

   bl->add(new ComputerMonitor(10104)); //101房间4号桌上的计算机显示器

   bl->goodNight()；

   delete bl;

}

试题六（共15分）

 阅读以下说明和Java代码，填补Java代码中的空缺(1)～(5)，将解答写在答题纸的对应栏内。

【说明】

   已知某公司主要有两大类耗电资产( Asset):计算机(ComputerAsset)和建筑物( Building Asset)。为了节约能源，通过控制各种电源，将可关闭的房灯、计算机显示器等在夜间关闭。

为了实现上述需求，设计了如图6-1所示的类图，并用下面的Java代码加以实现。

   【Java代码】

   abstract class Asset{         /*通用资产，基类*/}

   interface PowerSwitchable{   /*可在夜间关闭电源的物体实现该接口*/

       public void powerDown();

       public void powerUp();

   }

   abstract class BuildingAsset extends Asset{/*建筑物资产*/

       protected int room;

       public BuildingAsset(int room){   this.room= room; }

   }

abstract class BuildingLight extends BuildingAsset{

       //灯的通用信息：flourescent/incandescent等，略

       BuildingLight(int roomNumber){ super(roomNumber);}

   }

   classEmergencyLight (1) {/*应急灯，永不关闭*/

      EmergencyLight(int roomNumber){

           super(roomNumber);

     }

   }

   class RoomLights   (2)   {

       RoomLights(int roomNumber){   super(roomNumber); }

       public void powerDown(){ /*关电源，代码略*/}

       public void powerUp(){/*开电源，代码略*/}

   }

   /*ComputerAsset、 Computer CPU和Computer Monitor代码略*/

   public class BuildingManagement{

       Asset things[]= new Asset[24];

       int numltems=0；

       public void goodNight(){/*值班员定时“关闭”时调用，关闭可关闭的电源*/

           for (int i=0; i

               if( things[i] instanceof  (3) )

((PowerSwitchable)things[i]).powerDown();

       }

       /*goodMorning()与goodNight()类似，依次调用powerUp()，其实现细节此处略*/

       public void add(Asset thing){   /*为建筑添加资产*/

           things[   (4)   ]=thing;

       }

       public static void main(String[] args){

           BuildingManagementbl= (5)   BuildingManagement();

           bl.add(new RoomLights(101));   //101房间的控制灯

           bl.add(new EmergencyLight(101));   //101房间的应急灯

           bl.add(new ComputerCPU(10104));//101房间4号桌上的计算机主机

           bl.add(new ComputerMonitor(10104));   // 101房间4号桌上的计算机显示器

           bl.goodNight()；

       }

   }

试题三（共15分）

   阅读以下说明和C代码，填补C代码中的空缺(1)～(5)，将解答写在答题纸的对应栏内。

【说明】

   某市在进行市长选举，该市共分为M个选区（1

   现已将选票数据存入文本文件data.txt，该文件内容格式如下：共有M行，每行N+l个整数，第一个整数为选区编号，随后为N个候选者在该选区所得票数。

 下面的程序先从文件中读入选票数据存入二维数组data，然后完成下列功能：

 a．计算并显示每个竞选者获得的选票数及占总选票数的百分比；

 b．如果任一竞选者获得的选票数超过总选票数的50%，则显示该竞选者获胜；

 c．如果没有竞选者获得总选票数的50%以上，则显示两位得票最高的竞选者需再进行决选。

 在下面的程序代码中，竞选者A的编号为l，竞选者B的编号为2，以此类推。

【C代码】

#include

#include

#defineM 5   /*选区数*/

#define N 4   /*竞选者人数*/

int main(int argc,char argv[])

{

   FILE *fin;

   int data[M+l][N+1]； /*data[] [0]存放选区编号，data[M][j]存放j号竞选者得票总数*/

   int MAXP1，cdl；   /*MAXP1、cdl存放得票最多者的票数和竞选者编号*/

   int MAXP2，cd2;    /*MAXP2、cd2存放得票次多者的票数和竞选者编号*/

   int i,j,totalP;         /*totalP存放总票数*/

   fin= fopen(“data.txt”，“r”);

   if(!fin) return-1；

   1=0； j=0；

   while (!feof(fin)){ /*从文件读入数据*/

       fscanf(fin,"%d",&data[i] [j]);

          (1) ；

       if(j>N)   {j=0；i++；)

   }

   fclose(fin);

totalP=0;MAXPl=0;MAXP2=0;cdl=0;cd2=0;

   for(j=l；j

       data[M][j]= (2) ；   /*设置j号竞选者得票总数初始值*/

       for(i=0；i

          data[M][j]+=data[i][j];

       if(data[M][j]>MAXPl){

           (3) ： cd2= cdl;

          MAXPl=data[M][j];  cdl =j;

       }

       else

          if(data[M][j]>MAXP2) {MAXP2= data[M][j];  cd2 =j;)

         (4)；   /*计算总票数*/

}

for(j=1；j

     printf("Candidate-%c: %d  ",j+'A'-1,data[M][j]);

     printf("%.21f\n" ,(double)data[M] [j]/totalP);

}

 printf("\n"),

if(  (5) >0.5)   /*判断得票数最多者的得票率*/

    printf("Winner: Candidate-%c\n",cdl+'A'-l);

else

printf("Result:Candidate-%c PK Candidate-%c\n",cdl+'A'-l,cd2+'A'-l);

system("pause");

return0；

}

试题四（共15分）

   阅读以下说明和C函数，填补C函数中的空缺(1)～(5)，将解答写在答题纸的对应栏内。

【说明】

   约瑟夫问题如下所述：有n个人(编号为1～n)围成一圈，从第1个人开始，按照顺时针方向从1开始计数到m（即数到第m个人），让其出圈，然后再从其顺时针方向的下一个人开始，依次计数到m并让其出圈，重复这个过程，直到所有人都出圈，试给出出圈者的顺序。

以n=5，m=3为例，其出圈顺序为3，1，5，2，4，过程如图4-1所示。

下面的函数Joseph()在单向循环链表表示的基础上模拟上述出圈过程。

n为5时的单向循环链表结构如图4-2所示。

   链表的结点类型定义如下：

   typedef struct Node{

        int no;

      struct Node *next;

}Node，*LinkList;

   函数Joseph(LinkList tail，int n，int m)的处理思路如下：

   (1)用k计数，每次都从O开始，当计数到m-l时结束本次计数；

   (2)通过指针p查找出圈者所对应的结点，当k的值等于m-l时，p应指向出圈者对应结点的前驱结点；

   (3)通过删除结点表示出圈处理；

   (4)当m大于圈中剩余人数时，为了避免重复计数，用模运算修改m的值；

   (5)计数和删除操作完成后再恢复m的原值。

 【C函数】

void Joseph(LinkList tail, int n,int m)

{

   LinkListp，q；

   Int k i，old_m=m;

   p= tail;

   for(i=n; i>l; --i){            /*i表示圈中剩余人数*/

      m=m%i;                /*避免重复计数*/

      if(0==m=  (1) ，

      k=0；

      while( k< (2)   ){

              (3) ；

          k++;

      }

      print("%d\n",   (4) )；  /*输出出圈者的编号*/

      q=p->next;

        (5) =q->next;         /*删除出圈者对应的结点*/

      free(q);

      m= old_m;

   }

   printf("%d\n", p->No);

 }

试题二（共15分）

   阅读以下说明和C程序代码，将解答写在答题纸的对应栏内。

【说明】

   下面是一个待修改的C程序，其应该完成的功能是：对于输入的一个整数num，计算其位数k，然后将其各位数字按逆序转换为字符串保存并输出。若num为负整数，则输出字符串应有前缀“-”。例如，将该程序修改正确后，运行时若输入“14251”，则输出“15241”；若输入“-6319870”，则输出“-0789136”。

   下面给出的C程序代码中有五处错误，请指出错误代码所在的行号并给出修改正确后的完整代码行。

【C程序代码】

试题一（共15分）

   阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入答题纸的对应栏内。

【说明】

   以下流程图用于检查数组A[1：n]中的元素是否为自然数1~n的一个排列（含有1~n各数）。若是，则输出OK，否则输出所缺的自然数及其个数m。

   为检查A[1：n]中是否含有k，只要判断P(k)=(A(1)-k)^*(A(2)-k)^*…^*(A(n)-k)是否等于0即可。