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

2、棧。void Push(STACK *s, int e):將一個整數(shù)壓入棧，棧中元素數(shù)目增1。void Pop(STACK *s):棧頂元素出棧，棧中元素數(shù)目減1。int Top(STACK s):返回非空棧的棧頂元素值，棧中元素數(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、車廂編號 * /printf(”請輸入車廂數(shù):");Scanf("%d", & n);printf("請輸入需要判斷的車廂編號序列(以空格分隔):");if (n v 1 =return-1;for (i=0; i v n; i+) /*讀入需要駛出的車廂編號序列，存入數(shù)組state*/scanf("%d", & statei); /*初始化棧*/maxNo=1;for (i=0; i vn; = /*檢查輸出序列中的每個車廂號statei是否能從棧中獲取*/if () /* 當(dāng)棧不為空時*/if (stat

4、ei=Top (station) /*棧頂車廂號等于被檢查車廂號*/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)棧為空時*/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)說明現(xiàn)需在某城市中選擇一個社區(qū)建一個大型超市，使該城市的其他社區(qū)到該超市的距離總和最小。用圖模型 表示該城市的地圖，其中頂點表示社區(qū)，邊表示社區(qū)間的路線，邊上的權(quán)重表示該路線的長度?，F(xiàn)設(shè)計一個算法來找到該大型超市的最佳位置，即在給定圖中選擇一個頂點，使該頂點到其他各頂點的最

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

7、不包括頂點 k，則 于是得到如下遞歸式：i到頂點j的最短路徑因為對于任意路徑，所有的中間頂點都在集合1，2,，n)內(nèi)，因此矩陣 &出了任意兩個頂點之間的最短路徑，即對所有i , j eV,表示頂點i到頂點j的最短路徑,下面是求解該問題的偽代碼，請?zhí)畛淦渲械目杖碧?。偽代碼中的主要變量說明如下。 W:權(quán)重矩陣。 n :圖的頂點個數(shù)。 SP：最短路徑權(quán)重之和數(shù)組，SPi表示頂點i到其他各頂點的最短路徑權(quán)重之和，i從1到n min SP ：最小的最短路徑權(quán)重之和。 min v :具有最小的最短路徑權(quá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).上一題中偽代碼的時間復(fù)雜度為 (用0符號表示)。(分?jǐn)?shù)：10.00 )正確答案：()解析：O(n 3 )三、試題三(

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

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

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

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

13、中。nv： n+1行M+1列的二維數(shù)組，其中行和列的下標(biāo)均從0開始，nvij表示由前i項食物組合且價格不超過j套餐的最大營養(yǎng)價值。問題最終要求套餐的最大營養(yǎng)價值為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項食物，每項食物的營養(yǎng)價值和價格如下表所示。食物營養(yǎng)價值及價格編碼營養(yǎng)價值價格m 120050m 218030m 322545m 420025m 5505若要求總價格不超過100元的營養(yǎng)價值最大的套餐，則套餐應(yīng)包含的食物有 （用食物項的編碼表示），對應(yīng)的最大營養(yǎng)價值為。（分?jǐn)?shù)：6.6

15、7 ）正確答案：（）解析：O（nXM）五、試題五（總題數(shù)：1分?jǐn)?shù)：20.00）3. 說明已知集合A和B的元素分別用不含頭節(jié)點的單鏈表存儲，函數(shù)Difference。 用于求解集合A與B的差集,并將結(jié)果保存在集合 A的單鏈表中。例如，若集合A=5, 10, 20, 15, 25, 30，集合B=5, 15 , 35, 25, 如下圖（a）所示，運算完成后的結(jié)果如下圖（b）所示。鏈表節(jié)點的結(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