2005年上半年軟件設計師下午試題(編輯修改稿)
2025-02-10 13:17 本頁面
【文章內(nèi)容簡介】 2所示。在圖34中，設置電路板初始格局即將可布線方格置為數(shù)值已布線方格（即封鎖方格）置為9。設置方格陣列圍墻的目的是省略方格位置的邊界條件判定，方法是在四周附加格，并將其標記為9（與封鎖標記相同）。[表32]符號含義Grid全局二維數(shù)組Grid[N+2,M+2],表示電路板方格陣列，初始時數(shù)組元素Grid[i,j]r的值為1表示當前方格可布線，為9表示前方格不可布線。Offset一維數(shù)組offset[4]:offset[i](0≤i≤3)的分量為r（行偏移量）和c(列偏移量)，按照表31的內(nèi)容設置其值。Startpos、Endpos、Curpos、T分別表示起始方格、目標方格、當前方格和臨時方格，其位置用分量度row和col確定。(s)將方格s的位置信息加入隊列()刪除非空隊列的隊頭元素，并返回該元素。()若隊列Q為空，則返回true。否則返回false。[圖33][圖34] ●供選擇的答案 [a] Found≠true [b] Found = true [c] T = EndPos [d] (T) [e] T ← () [f] CurPos = EndPos [g] i≥4 [h] CurPos ← () [i] Grid[,] = 1 [j] Grid[,]≠1試題四（15分） 閱讀以下說明和C程序，將應填入__(n)__ 處的字句寫在答題紙對應欄內(nèi)。[說明] 假設需要將N個任務分配給N個工人同時去完成，每個人都能承擔這N個任務，但費用不同。下面的程序用回溯法計算總費用最小的一種工作分配方案，在該方案中，為每個人分配1個不同的任務?！ 〕绦蛑?，N個任務從0開始依次編號，N個工人也從0開始依次編號，主要的變量說明如下： c[i][j]:將任務i分配給工人j的費用； task[i]:值為0表示任務i未分配，值為j表示任務i分配給工人j； worker[k]:值為0表示工人k未分配任務，值為1表示工人k已分配任務； mincost:最小總費用。[C程序] ＃include ?。efine N 8 /*N 表示任務數(shù)和工人數(shù)*/ int c[N][N]； unsigned int mincost = 65535； /*設置的初始值，大于可能的費用*/ int task[N]，temp[N]，worker[N]； void plan(int k,unsigned int cost) { int i； if（ __(1)__ amp。amp。 costmincost）{ mincost = cost； for(i=0；iN；i++) temp[i]=task[i]；} else{ for(i=0；iN；i++) /*分配任務 k*/ if (worker[i]==0 amp。amp。 __(2)__){ worker[i]=1；task[k]= __(3)__； Plan( __(4)__，cost+c[k][i])； __(5)__； task[k] = 0； }/*if*/ } }/*Plan*/ void main() { int i,j； for(i=o；iN；i++){ /*設置每個人任務由不同工人承擔時的費用及全局數(shù)組的初值*/ worker[i]=0；task[i]=0；temp[i]=0； for(j=0；jn；j++) scanf(%d,amp。c[i][j])； } Plan(0，0)； /*從任務0開始分配*/ prin
試題試卷相關推薦
鄂ICP備17016276號-1