[it認(rèn)證]09下半年下午真題(參考版)
2025-01-17 22:42本頁面
【正文】 。int Top(STACK s):返回非空棧的棧頂元素值,棧中元素數(shù)目不變。void Push(STACK *s,int e): 將一個整數(shù)壓棧,棧中元素數(shù)目增 1。一旦車廂駛?cè)?B 方向鐵軌就不能再回到車站,如圖 71 所示,其中 Station 為棧結(jié)構(gòu),初始為空且最多能停放 1000 節(jié)車廂。【說明】(代碼不同,其他相同)試題七(共 15 分)閱讀以下說明和C程序,將應(yīng)填入 (n) 處的字句寫在答題紙的對應(yīng)欄內(nèi)。試題五(共 15 分)閱讀下列說明和C++代碼,將應(yīng)填入 (n) 處的字句寫在答題紙的對應(yīng)欄內(nèi)。為獲得最優(yōu)解,應(yīng)該選擇物品 (5) ,獲得的價值為 (6) 。圖 41 中是根據(jù)上述算法構(gòu)造 的搜索樹,其中結(jié)點的編號表示了搜索樹生成的順序,邊上的數(shù)字 1/0 分別表示選擇/不選擇對應(yīng)物品。Y:當(dāng)前已獲得的部分解。cp:當(dāng)前獲得的價值。X:問題的最優(yōu)解。fw:獲得最大價值時背包的重量。w:重量數(shù)組。函數(shù)參數(shù)說明如下:W:背包容量。對應(yīng)于搜索樹中的某個結(jié)點,該函數(shù)值表示確定了部分物品是否選擇之后,對剩下的物品在滿足約束條件的前提下進(jìn)行選擇可 能獲得的最大價值,若該價值小于等于當(dāng)前已經(jīng)得到的最優(yōu)解,則該結(jié)點無需再擴(kuò)展。為了進(jìn)一步提高算法的搜索效率,往往需要設(shè)計一個限界函數(shù),判斷并剪枝那些即使擴(kuò)展了也不能得到最優(yōu)解的結(jié)點。在確定解空間后,回溯法從根結(jié)點開始,按照深度優(yōu)先策略遍歷解空間樹,搜索滿足約束條件的解。【問題 1】(8 分)用回溯法求解此 01 背包問題,請?zhí)畛湎旅鎮(zhèn)未a中(1)～(4)處空缺。試題四(共 15 分)閱讀下列說明,回答問題 1 至問題 2,將解答填入答題紙的對應(yīng)欄內(nèi)?！締栴} 3】(4 分)根據(jù)【說明】中的描述,給出圖 32 中(1)～(4)處對應(yīng)的活動名稱或圖形符號?！締栴} 1】(2 分)根據(jù)【說明】中的描述,給出圖 31 中 A1 和 A2 所對
試題試卷相關(guān)推薦
鄂ICP備17016276號-1