>>>2017年軟件設(shè)計(jì)師網(wǎng)絡(luò)課堂課
  >>>軟件設(shè)計(jì)師歷年真題題庫(kù)
  >>>2017年軟件設(shè)計(jì)師考試指南

無(wú)論頭上是怎樣的天空，都要勇敢地對(duì)自己說(shuō)：我準(zhǔn)備承受任何風(fēng)暴!所有的努力在考試時(shí)都將得到論證。下面是關(guān)于2013下半年軟件設(shè)計(jì)師下午真題，祝大家考試順利。>>>查看完整版請(qǐng)點(diǎn)擊2013下半年軟件設(shè)計(jì)師下午真題匯總.　

【4】閱讀下列說(shuō)明和C代碼，回答問(wèn)題1至問(wèn)題3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。

【說(shuō)明】

某工程計(jì)算中要完成多個(gè)矩陣相乘(鏈乘)的計(jì)算任務(wù)。

兩個(gè)矩陣相乘要求第一個(gè)矩陣的列數(shù)等于第二個(gè)矩陣的行數(shù)，計(jì)算量主要由進(jìn)行乘法運(yùn)算的次數(shù)決定。采用標(biāo)準(zhǔn)的矩陣相乘算法，計(jì)算Am×n*Bn×p，需要m*n*p次乘法運(yùn)算。

矩陣相乘滿足結(jié)合律，多個(gè)矩陣相乘，不同的計(jì)算順序會(huì)產(chǎn)生不同的計(jì)算量。以矩陣A110×100，A2100×5，A35×50三個(gè)矩陣相乘為例，若按(A1*A2)*A3計(jì)算，則需要進(jìn)行10*100*5+10*5*50=7500次乘法運(yùn)算;若按A1*(A2*A3)計(jì)算，則需要進(jìn)行100*5*50+10*100*50=75000次乘法運(yùn)算。可見(jiàn)不同的計(jì)算順序?qū)τ?jì)算量有很大的影響。

矩陣鏈乘問(wèn)題可描述為：給定n個(gè)矩陣，矩陣Ai的維數(shù)為pi-1×pi，其中i = 1,2,….n。確定一種乘法順序，使得這n個(gè)矩陣相乘時(shí)進(jìn)行乘法的運(yùn)算次數(shù)最少。

由于可能的計(jì)算順序數(shù)量非常龐大，對(duì)較大的n，用蠻力法確定計(jì)算順序是不實(shí)際的。經(jīng)過(guò)對(duì)問(wèn)題進(jìn)行分析，發(fā)現(xiàn)矩陣鏈乘問(wèn)題具有最優(yōu)子結(jié)構(gòu)，即若A1*A2*…*An的一個(gè)最優(yōu)計(jì)算順序從第k個(gè)矩陣處斷開(kāi)，即分為A1*A2*….Ak和Ak+1*Ak+2*…*An兩個(gè)子問(wèn)題，則該最優(yōu)解應(yīng)該包含A1*A2*…*Ak的一個(gè)最優(yōu)計(jì)算順序和Ak+1*Ak+2*…An的一個(gè)最優(yōu)計(jì)算順序。據(jù)此構(gòu)造遞歸式，

其中，cost[i][j]表示Ai+1*Ai+2*...Aj+1的最優(yōu)計(jì)算的計(jì)算代價(jià)。最終需要求解cost[0][n-1]。

【C代碼】

算法實(shí)現(xiàn)采用自底向上的計(jì)算過(guò)程。首先計(jì)算兩個(gè)矩陣相乘的計(jì)算量，然后依次計(jì)算3個(gè)矩陣、4個(gè)矩陣、…、n個(gè)矩陣相乘的最小計(jì)算量及最優(yōu)計(jì)算順序。下面是算法的C語(yǔ)言實(shí)現(xiàn)。

(1)主要變量說(shuō)明

n：矩陣數(shù)

seq[]：矩陣維數(shù)序列

cost[][]：二維數(shù)組，長(zhǎng)度為n*n，其中元素cost[i][j]表示Ai+1*Ai+2*…Aj+1的最優(yōu)計(jì)算的計(jì)算代價(jià)

trace[][]：二維數(shù)組，長(zhǎng)度為n*n，其中元素trace[i][j]表示Ai+1*Ai+2*Aj+1的最優(yōu)計(jì)算對(duì)應(yīng)的劃分位置，即k

(2)函數(shù)cmm

#define N 100

int cost[N][N];

int trace[N][N];

int cmm(int n,int seq[]){

int tempCost;

int tempTrace;

int i,j,k,p;

int temp;

for( i=0;i

for(p=1;p

for(i=0; (1) ;i++){

(2) ;

tempCost = -1;

for(k = i;k

temp= (3) ;

if(tempCost==-1||tempCost>temp){

tempCost = temp;

(4) ;

}

}

cost[i][j] = tempCost;

trace[i][j] = tempTrace;

}

}

return cost[0][n-1];

}

【問(wèn)題1】(8分)

根據(jù)以上說(shuō)明和C代碼，填充C代碼中的空(1)~(4)。

【問(wèn)題2】(4分)

根據(jù)以上說(shuō)明和C代碼，該問(wèn)題采用了 (5) 算法設(shè)計(jì)策略，時(shí)間復(fù)雜度 (6) 。(用O符號(hào)表示)

【問(wèn)題3】(3分)

考慮實(shí)例n=6，各個(gè)矩陣的維數(shù)：A1為5*10，A2為10*3，A3為3*12，A4為12*5，A5為5*50，A6為50*6，即維數(shù)序列為5,10,3,12,5,50,6。則根據(jù)上述C代碼得到的一個(gè)最優(yōu)計(jì)算順序?yàn)?(7) (用加括號(hào)方式表示計(jì)算順序)，所需要的乘法運(yùn)算次數(shù)為 (8) 。

【5】閱讀下列說(shuō)明和C++代碼，將應(yīng)填入(n)處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【說(shuō)明】

欲開(kāi)發(fā)一個(gè)繪圖軟件，要求使用不同的繪圖程序繪制不同的圖形。以繪制直線和圓形為例，對(duì)應(yīng)的繪圖程序如表5-1所示。

該繪圖軟件的擴(kuò)展性要求，將不斷擴(kuò)充新的圖形和新的繪圖程序。為了避免出現(xiàn)類爆炸的情況，現(xiàn)采用橋接(Bridge)模式來(lái)實(shí)現(xiàn)上述要求，得到如圖5-1所示的類圖。

　　圖5-1 類圖 【C++代碼】

class DP1{

public:

static void draw_a_line(double x1,double y1,double x2,double y2){/*代碼省略*/}

static void draw_a_circle(double x,double y,double r){ /*代碼省略*/}

};

class DP2{

public:

static void drawline(double x1,double x2,double y1,double y2){/*代碼省略*/}

static void drawcircle(double x,double y,double r){/*代碼省略*/}

};

class Drawing{

public:

(1) ;

(2) ;

};

class V1Drawing:public Drawing{

public:

void drawLine(double x1,double y1,double x2, double y2){/*代碼省略*/}

void drawCircle(double x, double y, double r){ (3) ;}

};

class V2Drawing:public Drawing{

public:

void drawLine(double x1,double y1,double x2, double y2){/*代碼省略*/}

void drawCircle(double x, double y, double r){ (4) ;}

};

class Shape{

public:

(5) ;

Shape(Drawing * dp){ _dp = dp;}

void drawLine(double x1, double y1,double x2, double y2){_dp->drawLine(x1,y1,x2,y2);}

void drawCircle(double x, double y, double r){_dp->drawCircle(x,y,r);}

private: Drawing * _dp;

};

class Rectangle:public Shape{

public:

void draw__(17)__{/*代碼省略*/}

//其余代碼省略

};

class Circle:public Shape{

private: double _x,_y,_r;

public:

Circle(Drawing * dp, double x, double y, double r): (6) {_x = x; _y = y; _r = r;}

void draw__(18)__{ drawCircle(_x, _y, _r);}

};

【6】閱讀下列說(shuō)明和Java代碼，將應(yīng)填入(n)處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【說(shuō)明】

欲開(kāi)發(fā)一個(gè)繪圖軟件，要求使用不同的繪圖程序繪制不同的圖形。以繪制直線和圓形為例，對(duì)應(yīng)的繪圖程序如表6-1所示。

該繪圖軟件的擴(kuò)展性要求，將不斷擴(kuò)充新的圖形和新的繪圖程序。為了避免出現(xiàn)類爆炸的情況，現(xiàn)采用橋接(Bridge)模式來(lái)實(shí)現(xiàn)上述要求，得到如圖6-1所示的類圖。

　　圖6-1 類圖

【Java代碼】

(1) Drawing{

(2) ;

(3) ;

}

class DP1{

static public void draw_a_line(double x1, double y1, double x2, double y2) {/*代碼省略*/}

static public void draw_a_circle(double x, double y, double r) {/*代碼省略*/}

}

class DP2{

static public void drawline(double x1, double y1, double x2 ,double y2){/*代碼省略*/}

static public void drawcircle (double x, double y, double r){/*代碼省略*/}

}

class V1Drawing implements Drawing{

public void drawLine(double x1, double y1, double x2 ,double y2){/*代碼省略*/}

public void drawCircle(double x, double y, double r){ (4) ;}

}

class V2Drawing implements Drawing{

public void drawLine(double x1, double y1, double x2 ,double y2){/*代碼省略*/}

public void drawCircle (double x, double y, double r){ (5) ;}

}

abstract class Shape{

private Drawing _dp;

(6) ;

Shape(Drawing dp) {_dp=dp;}

public void drawLine(double x1, double y1, double x2 ,double y2){_dp.drawLine(x1,y1,x2,y2); }

public void drawCircle (double x, double y, double r){ _dp.drawCircle(x,y,r);}

}

class Rectangle extends Shape{

private double _x1,_x2,_y1,_y2;

public Rectangle(Drawing dp,double x1, double y1, double x2 ,double y2) {/*代碼省略*/}

public void draw__(21)__{/*代碼省略*/}

}

class Circle extends Shape{

private double _x, _y, _r;

public Circle(Drawing dp,double x, double y, double r) {/*代碼省略*/}

public void draw__(22)__{drawCircle(_x,_y,_r);}

}