99热99干,国产电影在线观看一区,国产插视频

當(dāng)前位置：信管網(wǎng) >> 軟件設(shè)計師 >> 每日一練 >> 文章內(nèi)容

軟件設(shè)計師案例分析每日一練試題（2022/12/23）

來源：信管網(wǎng) 2022年12月24日【所有評論】

軟件設(shè)計師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計師案例分析每日一練試題（2022/12/23）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2022/12/23

軟件設(shè)計師案例分析每日一練試題內(nèi)容（2022/12/23）

閱讀下列說明和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))的形式給出）。
信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/st/3816623561.html
信管網(wǎng)考友試題答案分享：
信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/st/3816623561.html

掃碼關(guān)注公眾號

溫馨提示：因考試政策、內(nèi)容不斷變化與調(diào)整，信管網(wǎng)網(wǎng)站提供的以上信息僅供參考，如有異議，請以權(quán)威部門公布的內(nèi)容為準(zhǔn)！

信管網(wǎng)致力于為廣大信管從業(yè)人員、愛好者、大學(xué)生提供專業(yè)、高質(zhì)量的課程和服務(wù)，解決其考試證書、技能提升和就業(yè)的需求。

信管網(wǎng)軟考課程由信管網(wǎng)依托10年專業(yè)軟考教研傾力打造，官方教材參編作者和資深講師坐鎮(zhèn)，通過深研歷年考試出題規(guī)律與考試大綱，深挖核心知識與高頻考點，為學(xué)員考試保駕護航。面授、直播＆錄播，多種班型靈活學(xué)習(xí)，滿足不同學(xué)員考證需求，降低課程學(xué)習(xí)難度，使學(xué)習(xí)效果事半功倍。

上一篇：軟件設(shè)計師每日一練試題（2022/12