試題一：閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對應(yīng)欄內(nèi)。
【說明】
在一塊電路板的上下兩端分別有n個接線柱。根據(jù)電路設(shè)計，用(i,π(i))表示將上端接線柱i與下端接線柱π(i)相連，稱其為該電路板上的第i條連線。如圖4-1所示的π(i)排列為{8,7,4,2,5,1,9,3,10,6}。對于任何1≤iπ(j)。
在制作電路板時，要求將這n條連線分布到若干絕緣層上，在同一層上的連線不相交?，F(xiàn)在要確定將哪些連線安排在一層上，使得該層上有盡可能多的連線，即確定連線集Nets={(i,π(i))，1≤i≤n}的最大不相交子集。

【分析問題】
記N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}。N(i,j)的最大不相交子集為MNS(i,j)，size(i,j)=|MNS(i,j)|。
經(jīng)分析，該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對規(guī)模為n的電路布線問題，可以構(gòu)造如下遞歸式：

【C代碼】
下面是算法的C語言實現(xiàn)。
（1）變量說明
size[i][j]：上下端分別有i個和j個接線柱的電路板的第一層最大不相交連接數(shù)
pi[i]：π(i)，下標(biāo)從1開始
（2）C程序   #include"stdlib.h"
#include
#define N   10         /*問題規(guī)模*/
Int m=0；            /*記錄最大連接集合中的接線柱*/
Void maxNum(intpi[],intsize[N+1][N+1],intn){/*求最大不相交連接數(shù)*/
int i,j;
for(j=0;j for(j=pi[i];j<=n;j++)（1）; /*當(dāng)j>=π(1)時*/
for(i=2;i for(j=0;j for(j=pi[i];j<=n；j++) { /*當(dāng)j>=c[i]時,考慮兩種情況*/
size[i][j]=size[i-l][j]>=size[i-l][pi[i]-l]+1?size[i-l][j]:
size[i-l][pi[i]-l]+l;
}
}
/*最大連接數(shù)*/
size[n][n]=size[n-l][n]>=size[n-l][pi[n]-l]+1?size[n-l][n]:size[n-l][pi[n]-l]+l：
}
/*構(gòu)造最大不相交連接集合，net[i]表示最大不相交子集中第i條連線的上端接線柱的序號*/
void constructSet（int pi[],int size[N+1][N+1],int n,int net[n]）{
int i,j=n;
m=0；
for(i=n；i>1;i--)     {/*從后往前*/
if(size[i][j]!=size[i-l][j]){/*(i,pi[i])是最大不相交子集的一條連線*/
（3）;                 /*將i記錄到數(shù)組net中，連接線數(shù)自增1*/
j=pi[i]-1;             /*更新擴展連線柱區(qū)間*/
}
}
if(j>=pi[l])net[m++]=l;         /*當(dāng)i=1時*/
}
【問題1】（6分）
根據(jù)以上說明和C代碼，填充C代碼中的空（1）~（3）。
【問題2】（6分）
根據(jù)題干說明和以上C代碼，算法采用了（4）算法設(shè)計策略。
函數(shù)maxNum和constructSet的時間復(fù)雜度分別為（5）和（6）（用O表示）。
【問題3】（3分）
若連接排列為{8,7,4,2,5,1,9,3,10,6}，即如圖4-1所示，則最大不相交連接數(shù)為（7），包含的連線為（8）（用(i,π(i))的形式給出）。

查看答案

試題二：閱讀以下說明和C代碼，將應(yīng)填入  (n)  處的字句寫在的對應(yīng)欄內(nèi)。
【說明】
在一個簡化的繪圖程序中，支持的圖形種類有點(point)和圓(circle)，在設(shè)計過程中采用面向?qū)ο笏枷耄J為所有的點和圓都是一種圖形(shape)，并定義了類型shape t、 point t和circle t分別表示基本圖形、點和圓，并且點和圓具有基本圖形的所有特征。
【C代碼】
typedef enum { point,circle } shape type;   /* 程序中的兩種圖形：點和圓 */
typedef struct {             /* 基本的圖形類型 */
shape_type  type;        /* 圖形中類標(biāo)識：點或者圓*/
void (*destroy) ();       /* 銷毀圖形操作的函數(shù)指針*/
void (*draw) ();          /* 繪制圖形操作的函數(shù)指針*/
} shape_t;
typedef struct {  shape_t common;  int x;  iht y;  } point_t;  /* 定義點類
型, x, y為點坐標(biāo)*/
void destroyPoint (point_t* this)  { free (this); printf ("Point destoryed!
\n"); } )  /* 銷毀點對象*/
void drawPoint(point_t* this)  { printf("P(%d,%d)", this->x, this->y);  }
/* 繪制點對象*/
shape_t* createPoint (va_list* ap)  (/* 創(chuàng)建點對象，并設(shè)置其屬性*/
point_t*  p_point;
if ( (p_point= (point_t*)malloc (sizeof (point_t)) ) ==NULL) returnNULL;
p_point-＞common, type = point; p_point->common, destroy = destroyPoint;
p_point-＞common.draw = drawPoint;
p_point-＞x = va_arg(*ap, int);       /* 設(shè)置點的橫坐標(biāo)*/
p_point-＞y = va_arg(*ap, int);       /* 設(shè)置點的縱坐標(biāo)*/
return  (shape_t*)p_ooint;               /*返回點對象指針*/
}
typedef struct {    /*定義圓類型*/
shape_t  common;
point_t  4center;     /*圓心點*/
int   radius;          /*圓半徑*/
} circle_t;
void destroyCircle(circle_t* this){
free(  (1)  );        free(this);      printf("Circle destoryed!\n");
}
void drawCircle(circle_t* this)  {
print f ("C (");
(2)  .draw(this-＞center);   /*繪制圓心*/
printf(",%d) ",  this-＞radius);
}
shape_t* createCircle(va_list4 ap)  {     /*創(chuàng)建一個圓，并設(shè)置其屬性*/
circle_t4  p circle;
if ((p_circle = (circle_t4)malloc (sizeof (circle_t)) ) ==NULL ) return NULL;
p_circle-＞common.type = circle; p_circle-＞common.destroy = destroy
Circle;
p_circle-＞common.draw = drawCircle;
(3)    = createPoint(ap);      /* 設(shè)置圓心*/
p_circle-＞radius = va_arg(*ap, int);     /* 設(shè)置圓半徑*/
return  p_circle;
}
shape_t* createShape(shape_type st, "')  {    /* 創(chuàng)建某一種具體的圖形*/
va_list   ap;                      /*可變參數(shù)列表*/
shape_t4  p_shape = NULL;
(4)   (ap, st);
if( st == point )   p shape = createPoint(&ap);   /* 創(chuàng)建點對象*/
if( st == circle )  p shape = createCircle(&ap);   /*創(chuàng)建圓對象*/
va_end (ap);
return p_shape;
}
int main( )  {
int i;                  /* 循環(huán)控制變量，用于循環(huán)計數(shù)*/
shape_t* shapes[2];     /* 圖形指針數(shù)組，存儲圖形的地址*/
shapes[0] = createShape( point, 2, 3);       /* 橫坐標(biāo)為2，比值坐標(biāo)為3*/
shapes[ii = createShape( circle, 20,  40, 10);   /* 圓心坐標(biāo)(20,40),
半徑為 10*/
for(i=0 i＜2; i++) { shapes[i]-＞draw(shapes[i]);  printf("\n");  } /*
縱制數(shù)組中圖形*/
for( i = 1; i ＞= 0; i-- )  shapes[i]-＞destroy(shapes[i]);   /* 銷毀
數(shù)組中圖形*/
return 0;
}
【運行結(jié)果】
P(2,3)
(5)
Circle destoryed !
Point destoryed !

查看答案