軟件設(shè)計師考試歷年試題(編輯修改稿)
2025-04-22 04:23 本頁面
【文章內(nèi)容簡介】 ：當前獲得的價值；k：當前考慮的物品編號；Y：當前已獲得的部分解。BKNAP( W,n,w,v,fw,fp,X )1 cw ← cp ← 02 （1）3 fp ← 14 while true5 while k ≤ n and cw + w[k] ≤ W do6 （2） 7 cp ← cp + v[k]8 Y[k] ← 19 k ← k + 110 if k n then11 if fp cp then12 fp ← cp13 fw ← cw14 k ← n15 X ← Y16 else Y(k) ← 017 while BOUND(cp,cw,k,W) ≤ fp do18 while k ≠ 0 and Y(k) ≠ 1 do19 （3） 20 if k = 0 then return21 Y[k] ← 022 cw ← cw w[k]23 cp ← cp v[k]24 （4） 【問題 2】（7 分）考慮表 41 的實例，假設(shè)有 3 個物品，背包容量為 22。圖 41 中是根據(jù)上述算法構(gòu)造 的搜索樹，其中結(jié)點的編號表示了搜索樹生成的順序，邊上的數(shù)字 1/0 分別表示選擇/不選擇對應(yīng)物品。除了根結(jié)點之外，每個左孩子結(jié)點旁邊的上下兩個數(shù)字分別表示當前背包的重量和已獲得的價值，右孩子結(jié)點旁邊的數(shù)字表示擴展了該結(jié)點后最多可能獲得的價值。 為獲得最優(yōu)解，應(yīng)該選擇物品 （5） ，獲得的價值為 （6） 。試題五（共 15 分）閱讀下列說明和C++代碼，將應(yīng)填入 （n） 處的字句寫在答題紙的對應(yīng)欄內(nèi)?！菊f明】 現(xiàn)欲構(gòu)造一文件/目錄樹，采用組合（Composite）設(shè)計模式來設(shè)計，得到的類圖如 51所示：【C++代碼】include listinclude iostreaminclude stringusing namespace std。class AbstractFile protected :string name。 // 文件或目錄名稱public:void printName(){cout name。} // 打印文件或目錄名稱virtual void addChild(AbstractFile *file)=0。 // 給一個目錄增加子目錄或文件 virtual void removeChild(AbstractFile *file)=0。 // 刪除一個目錄的子目錄或文件 virtual listAbstractFile* *getChildren()=0。 // 獲得一個目錄的子目錄或文件}。class File : public AbstractFile {public :File(string name) { （1） = name。 }void addChild(AbstractFile *file) { return 。 }void removeChild(AbstractFile *file) { return 。 } （2） getChildren() { return （3） 。 }}。class Folder :public AbstractFile {private :list AbstractFile* childList。 // 存儲子目錄或文件public :Folder(string name) { （4） = name。 }void addChild(AbstractFile *file) { (file)。 } void removeChild(AbstractFile *file) { (file)。} listAbstractFile* *getChildren() { return （5） 。 }
電大資料相關(guān)推薦
鄂ICP備17016276號-1