中級(jí)軟件設(shè)計(jì)師下午試題-128

1、中級(jí)軟件設(shè)計(jì)師下午試題-128(總分：100.01，做題時(shí)間：90分鐘)一、試題一(總題數(shù)：1,分?jǐn)?shù)：20.00)1. 說(shuō)明現(xiàn)有n(n v 1000)節(jié)火車車廂，順序編號(hào)為1 , 2, 3，n,按編號(hào)連續(xù)依次從 A方向的鐵軌駛?cè)?，?B方向鐵軌駛岀，一旦車廂進(jìn)入車站(Station)就不能再回到A方向的鐵軌上；一旦車廂駛?cè)隑方向鐵軌就不能 再回到車站，如下圖所示，其中Station為棧結(jié)構(gòu)，初始為空且最多能停放1000節(jié)車廂。下面的C程序判斷能否從B方向駛岀預(yù)先指定的車廂序列，程序中使用了棧類型STACK關(guān)于?；静僮鞯暮瘮?shù)原型說(shuō)明如下。void lnitStack(STACK *s):初始化

2、棧。void Push(STACK *s, int e):將一個(gè)整數(shù)壓入棧，棧中元素?cái)?shù)目增1。void Pop(STACK *s):棧頂元素出棧，棧中元素?cái)?shù)目減1。int Top(STACK s):返回非空棧的棧頂元素值，棧中元素?cái)?shù)目不變。int lsEmpty(STACK s):若是空棧則返回1 ;否則返回0。C程序#include v stdio. h >/*此處為棧類型及其基本操作的定義，省略*/int main() STACK station;int state 1000;int n; /* 車廂數(shù)*/int begin, i, j, maxNo; /*maxNo為A端正待入棧的

3、車廂編號(hào) * /printf(”請(qǐng)輸入車廂數(shù):");Scanf("%d", & n);printf("請(qǐng)輸入需要判斷的車廂編號(hào)序列(以空格分隔):");if (n v 1 =return-1;for (i=0; i v n; i+) /*讀入需要駛出的車廂編號(hào)序列，存入數(shù)組state*/scanf("%d", & statei); /*初始化棧*/maxNo=1;for (i=0; i vn; = /*檢查輸出序列中的每個(gè)車廂號(hào)statei是否能從棧中獲取*/if () /* 當(dāng)棧不為空時(shí)*/if (stat

4、ei=Top (station) /*棧頂車廂號(hào)等于被檢查車廂號(hào)*/printf ("%d", Top(station);Pop (&station); i+;elseif () printf ("error'n");return 1;else begin=;for (j=begin+1; j v =statei; j+) Push (&station, j);else (/* 當(dāng)棧為空時(shí)*/begin=maxNo;for (j=begin; j < =statei; j+) Push (&station, j);m

5、axNo=;printf ("OK");return 0;(分?jǐn)?shù)：20.00 ) 正確答案：()解析：lnitStack(&station) !lsEmpty(station) statei < Top(station) Top(station)j二、試題二(總題數(shù)：1 分?jǐn)?shù)：20.00)說(shuō)明現(xiàn)需在某城市中選擇一個(gè)社區(qū)建一個(gè)大型超市，使該城市的其他社區(qū)到該超市的距離總和最小。用圖模型 表示該城市的地圖，其中頂點(diǎn)表示社區(qū)，邊表示社區(qū)間的路線，邊上的權(quán)重表示該路線的長(zhǎng)度?，F(xiàn)設(shè)計(jì)一個(gè)算法來(lái)找到該大型超市的最佳位置，即在給定圖中選擇一個(gè)頂點(diǎn)，使該頂點(diǎn)到其他各頂點(diǎn)的最

6、短路徑之和最小。算法首先需要求岀每個(gè)頂點(diǎn)到其他任一頂點(diǎn)的最短路徑，即需要計(jì)算任意兩個(gè)頂點(diǎn)之間 的最短路徑；然后對(duì)每個(gè)頂點(diǎn)，計(jì)算其他各頂點(diǎn)到該頂點(diǎn)的最短路徑之和；最后，選擇最短路徑之和最小 的頂點(diǎn)作為建大型超市的最佳位置。(分?jǐn)?shù)：20.00 )(1).本題采用Floyd-Warshall算法求解任意兩個(gè)頂點(diǎn)之間的最短路徑。已知圖G的頂點(diǎn)集合為V=1 ,2,，n，W=w ij nxn為權(quán)重矩陣。設(shè) 為從頂點(diǎn)i到頂點(diǎn)j的一條最短路徑的權(quán)重。當(dāng) k=0時(shí)，不存在f i：i- I中間頂點(diǎn)，因此 。當(dāng)k > 0時(shí)，該最短路徑上所有的中間頂點(diǎn)均屬于集合1，2，k)。若中間頂點(diǎn)包括頂點(diǎn) k，則若中間頂點(diǎn)

7、不包括頂點(diǎn) k，則 于是得到如下遞歸式：i到頂點(diǎn)j的最短路徑因?yàn)閷?duì)于任意路徑，所有的中間頂點(diǎn)都在集合1，2,，n)內(nèi)，因此矩陣 &出了任意兩個(gè)頂點(diǎn)之間的最短路徑，即對(duì)所有i , j eV,表示頂點(diǎn)i到頂點(diǎn)j的最短路徑,下面是求解該問(wèn)題的偽代碼，請(qǐng)?zhí)畛淦渲械目杖碧?。偽代碼中的主要變量說(shuō)明如下。 W:權(quán)重矩陣。 n :圖的頂點(diǎn)個(gè)數(shù)。 SP：最短路徑權(quán)重之和數(shù)組，SPi表示頂點(diǎn)i到其他各頂點(diǎn)的最短路徑權(quán)重之和，i從1到n min SP ：最小的最短路徑權(quán)重之和。 min v :具有最小的最短路徑權(quán)重之和的頂點(diǎn)。 i :循環(huán)控制變量。 i :循環(huán)控制變量。 k :循環(huán)控制變量。LOCATE -

8、SHOPPINGMALL(W, n)1 D(0)=w2 for3 for i=1 to n4 forj=1 to n5 6 7 else8 9 for i=1 to n10 SPi=011 for j=1 to n12 13 min_SP=SP114 15 for i=2 to n16 if min_SP > SPi17 min_SP=SPi18 min_v=i19 return （分?jǐn)?shù)：10.00 ）正確答案：（）解析：k=1 to nmin_v=1 ；min_v(2).上一題中偽代碼的時(shí)間復(fù)雜度為 (用0符號(hào)表示)。(分?jǐn)?shù)：10.00 )正確答案：()解析：O(n 3 )三、試題三(

9、總題數(shù)：1,分?jǐn)?shù)：20.00)2. 說(shuō)明對(duì)二叉樹(shù)進(jìn)行遍歷是二叉樹(shù)的一個(gè)基本運(yùn)算。遍歷是指按某種策略訪問(wèn)二叉樹(shù)的每個(gè)節(jié)點(diǎn)，且每個(gè)節(jié)點(diǎn)僅 訪問(wèn)一次的過(guò)程。函數(shù)lnOrder()借助棧實(shí)現(xiàn)二叉樹(shù)的非遞歸中序遍歷運(yùn)算。設(shè)二叉樹(shù)采用二叉鏈表存儲(chǔ)，節(jié)點(diǎn)類型定義如下：typedef struct BtNode ElemType data; /*節(jié)點(diǎn)的數(shù)據(jù)域，ElemType的具體定義省略*/struct BtNode *lchild, *rchild;/*節(jié)點(diǎn)的左、右孩子指針域 */ BtNode, *BTree;在函數(shù)lnOrder（）中，用棧暫存二叉樹(shù)中各個(gè)節(jié)點(diǎn)的指針，并將棧表示為不含頭節(jié)點(diǎn)的單向鏈表（

10、簡(jiǎn)稱鏈棧），其節(jié)點(diǎn)類型定義如下：typedef struct StNode /*鏈棧的節(jié)點(diǎn)類型 */BTree elem; /* 棧中的元素是指向二叉鏈表節(jié)點(diǎn)的指針*/struct StNode *link; StNode;假設(shè)從棧頂?shù)綏５椎脑貫閑 n，e n -1 ,，e 1，則不含頭節(jié)點(diǎn)的鏈棧示意圖如下圖所示。C程序int InOrder (BTree root) /*實(shí)現(xiàn)二叉樹(shù)的非遞歸中序遍歷*/BTree ptr; /*ptr用于指向二叉樹(shù)中的節(jié)點(diǎn)*/StNode *q; /*q暫存鏈棧中新創(chuàng)建或待刪除的節(jié)點(diǎn)指針*/StNode *stacktop=NULL; /*初始化空棧的棧頂指

11、針 stacktop */ptr=root; /*ptr指向二叉樹(shù)的根節(jié)點(diǎn)*/while (| stacktop != NULL)while (ptr !=NULL)q=(StNode *)malloc(sizeof(StNode);if (q=NULL)return -1;qielem=ptr;stacktop=q; /*stacktop 指向新的棧頂 */ptr=; /*進(jìn)入左子樹(shù)*/q=stacktop; /*棧頂元素岀棧*/visit（q）; /*visit是訪問(wèn)節(jié)點(diǎn)的函數(shù)，其具體定義省略*/ptr=; /* 進(jìn)入右子樹(shù)*/free（q）; /*釋放原棧頂元素的節(jié)點(diǎn)空間*/return

12、 0; /*InOrder*/（分?jǐn)?shù)：20.00 ）為Vi,價(jià)格為p i ,其中i=1 , 2,，n，套餐中每項(xiàng)食物至多出現(xiàn)一次。客人常需要一個(gè)算法來(lái)求解 總價(jià)格不超過(guò)M的營(yíng)養(yǎng)價(jià)值最大的套餐。（分?jǐn)?shù)：20.01）（1）.下面是用動(dòng)態(tài)規(guī)劃策略求解該問(wèn)題的偽代碼，請(qǐng)?zhí)畛淦渲械臋M線處。偽代碼中的主要變量說(shuō)明如下。 n：總食物項(xiàng)數(shù)。v：營(yíng)養(yǎng)價(jià)值組，下標(biāo)為1n，對(duì)應(yīng)第1項(xiàng)第n項(xiàng)食物的營(yíng)養(yǎng)價(jià)值。P：價(jià)格數(shù)組，下標(biāo)為1n，對(duì)應(yīng)第1項(xiàng)第n項(xiàng)食物的價(jià)格。M總標(biāo)準(zhǔn)，即套餐的價(jià)格不超過(guò)x：解向量（數(shù)組），下標(biāo)為1 n，其元素值為0或1，其中元素值為0表示對(duì)應(yīng)的食物不出現(xiàn)在套餐中，元 素值為1表示對(duì)應(yīng)的食物岀現(xiàn)在套餐

13、中。nv： n+1行M+1列的二維數(shù)組，其中行和列的下標(biāo)均從0開(kāi)始，nvij表示由前i項(xiàng)食物組合且價(jià)格不超過(guò)j套餐的最大營(yíng)養(yǎng)價(jià)值。問(wèn)題最終要求套餐的最大營(yíng)養(yǎng)價(jià)值為nvnM。偽代碼如下：MaxNutrientValue （n, v, p, M, x）1 for i = 0 t0 n2 nvi 0 = 03 for j = 1 t0 M4 nv0 j = 05 for i = 1 to n6 for j = 1 to M7 if j v pi / 若食物mi不能加入到套餐中8 nvi j = nvi-1 j9 else if10 nvi j = nvi-1 j11 else12 nvi j = n

14、vi-1 j-pi + vi13 j=M14 for i=n downt0 115 if16 xi=017 else18 xi=119 20 return x and nvn M（分?jǐn)?shù)：6.67 ） 正確答案：（）解析：nvi-1j> =nvi-1j-pi+vinvij=nvi-1jj=j-pi（2）.現(xiàn)有5項(xiàng)食物，每項(xiàng)食物的營(yíng)養(yǎng)價(jià)值和價(jià)格如下表所示。食物營(yíng)養(yǎng)價(jià)值及價(jià)格編碼營(yíng)養(yǎng)價(jià)值價(jià)格m 120050m 218030m 322545m 420025m 5505若要求總價(jià)格不超過(guò)100元的營(yíng)養(yǎng)價(jià)值最大的套餐，則套餐應(yīng)包含的食物有 （用食物項(xiàng)的編碼表示），對(duì)應(yīng)的最大營(yíng)養(yǎng)價(jià)值為。（分?jǐn)?shù)：6.6

15、7 ）正確答案：（）解析：O（nXM）五、試題五（總題數(shù)：1分?jǐn)?shù)：20.00）3. 說(shuō)明已知集合A和B的元素分別用不含頭節(jié)點(diǎn)的單鏈表存儲(chǔ)，函數(shù)Difference。 用于求解集合A與B的差集,并將結(jié)果保存在集合 A的單鏈表中。例如，若集合A=5, 10, 20, 15, 25, 30，集合B=5, 15 , 35, 25, 如下圖（a）所示，運(yùn)算完成后的結(jié)果如下圖（b）所示。鏈表節(jié)點(diǎn)的結(jié)構(gòu)類型定義如下：typedef struct Node ElemType elem;struct Node *next; NodeType;C程序void Difference (NodeType *LA, NodeType *LB) NodeType *pa, *pb, *pre, *q;pre=NUL