設(shè)計(jì)報(bào)告內(nèi)容要求

1、設(shè)計(jì)報(bào)告內(nèi)容要求1. 課程設(shè)計(jì)題目2. 姓名、學(xué)號(hào)、班級(jí)、日期3. 課程設(shè)計(jì)內(nèi)容描述 :4. 需求 （輸入、輸出、功能、測(cè)試數(shù)據(jù) ）5. 實(shí)現(xiàn)思想、算法描述6. 使用說明7. 調(diào)試說明8. 實(shí)現(xiàn)代碼 （帶注釋 ）1. 一元稀疏多項(xiàng)式計(jì)算器問題描述 設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器?；疽?一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器的基本功能是：（1）輸入并建立多項(xiàng)式；（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列： n，c1，e1，c2，e2，,cn，en，其中 n 是多項(xiàng)式的 項(xiàng)數(shù)， ci， ei，分別是第 i 項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排序；（3）多項(xiàng)式 a和 b相加，建立多項(xiàng)式 a+b；（4）多項(xiàng)式 a和 b

2、相減，建立多項(xiàng)式 a-b；（5）計(jì)算多項(xiàng)式在 x 處的值；（6）計(jì)算器的仿真界面（選做）2. 迷宮問題問題描述以一個(gè) m*n 的長方陣表示迷宮， 0 和 1 分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序， 對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論?；疽螅?）實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的 通路一三元組（ i，j，d）的形式輸出，其中： （i，j）指示迷宮中的一個(gè)坐標(biāo)， d 表示走到下 一坐標(biāo)的方向。（2）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（3）以方陣形式輸出迷宮及其通路（選做）3. 哈夫曼編 /譯碼器問題描述利用

3、哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率， 縮短信息傳輸時(shí)間， 降低傳輸 成本。 但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼； 在接收端將傳來的數(shù) 據(jù)進(jìn)行譯碼 （復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道） ，每端都需要一個(gè)完整的 編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編譯碼系統(tǒng)?；疽?一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：（1）I：初始化（ Initialization ）。從終端讀入字符集大小 n及 n 個(gè)字符和 m 個(gè)權(quán)值，建立哈 夫曼樹，并將它存于文件 hfmtree 中。（2）C：編碼（Coding ）。利用已建好的哈夫曼樹 （如不在內(nèi)存， 則從文件 hf

4、mtree 中讀入）， 對(duì)文件 tobetrans 中的正文進(jìn)行編碼，然后將結(jié)果存入文件 codefile 中。（3）D ：解碼（ Decoding ）。利用已建好的哈夫曼樹將文件codefile 中的代碼進(jìn)行譯碼，結(jié)果存入文件 textfile 中。（4）P：打印代碼文件 （ Print ）。將文件 codefile 以緊湊格式顯示在終端上， 每行 50 個(gè)代碼。 同時(shí)，將此字符形式的編碼文件寫入文件 codeprint 中。（5）T ：打印哈夫曼樹（ Tree printing ）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入 表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 tr

5、eeprint 中。4. 教學(xué)計(jì)劃編制問題問題描述大學(xué)的每個(gè)專業(yè)都要制訂教學(xué)計(jì)劃。 假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限， 每學(xué)年含兩學(xué) 期，每學(xué)期的時(shí)間長度和學(xué)分上限值均相等。 每個(gè)專業(yè)開設(shè)的課程都是確定的， 可以有任意 多門，也可以沒有。 每門課恰好占一個(gè)學(xué)期。 試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序。 基本要求（1）輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(hào)（固定占3 位的字母數(shù)字串）、學(xué)分和直接先修課的課程號(hào)。（2）允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻； 二是是課程盡可能地集中在前幾個(gè)學(xué)期中。（3）若根據(jù)給定的條件問題無解，則報(bào)告適當(dāng)?shù)男畔?/p>

6、；否則，將教學(xué)計(jì)劃輸出到用戶指定 的文件中。計(jì)劃的表格格式自行設(shè)計(jì)。5. 成績分析問題問題描述錄入、保存一個(gè)班級(jí)學(xué)生多門課程的成績，并對(duì)成績進(jìn)行分析。 基本要求（1）通過鍵盤輸入個(gè)學(xué)生的多門課程的成績，建立相應(yīng)的文件input.dat 。（ 2）對(duì)文件 input.dat 中的數(shù)據(jù)進(jìn)行處理，要求具有以下功能：1）按各門課程成績排序，并生成相應(yīng)的文件輸出。2）計(jì)算每人的平均成績，按平均成績排序，并生成文件。3）求出各門課程的平均成績、最高分、最低分、不及格人數(shù)、6069 分人數(shù)、 7079 分人數(shù)、 8089 分人數(shù)、 90 分以上人數(shù)。4）根據(jù)姓名或?qū)W號(hào)查詢某人的各門課成績，重名情況也能處理

7、（3）界面美觀6. 二叉排序樹與平衡二叉樹的實(shí)現(xiàn)問題描述分別采用二叉鏈表和順序表作存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)對(duì)二叉排序樹與平衡二叉樹的操作。 基本要求（1）用二叉鏈表作存儲(chǔ)結(jié)構(gòu)。1）以回車符（ n）為輸入結(jié)束標(biāo)志，輸入數(shù)列L，生成一棵二叉排序樹 T ；2）對(duì)二叉排序樹 T 作中序遍歷，輸出結(jié)果；3）計(jì)算二叉排序樹 T 查找成功的平均查找長度，輸出結(jié)果；4）輸入元素 x，查找二叉排序樹 T ，若存在含 x 的結(jié)點(diǎn)， 則刪除該結(jié)點(diǎn)， 并作中序遍歷（執(zhí) 行操作 2）；否則，輸出信息“無 x ”；5）用數(shù)列 L，生成平衡的二叉排序樹 BT ：當(dāng)插入新元素之后，發(fā)現(xiàn)當(dāng)前的二叉排序樹 BT 不是平衡的二叉排序樹，則立

8、即將它轉(zhuǎn)換成新的平衡的二叉排序樹 BT ；6）計(jì)算平衡的二叉排序樹 BT 的平均查找長度，輸出結(jié)果。（2）用順序表（一維數(shù)組）做存儲(chǔ)結(jié)構(gòu)。1）以回車符（ n ）為輸入結(jié)束標(biāo)志，輸入數(shù)列L，生成一棵二叉排序樹 T；2）對(duì)二叉排序樹 T 作中序遍歷，輸出結(jié)果；3）計(jì)算二叉排序樹 T 查找成功的平均查找長度，輸出結(jié)果；4）輸入元素 x，查找二叉排序樹 T，若存在含 x 的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)，并作中序遍歷（執(zhí) 行操作 2）；否則，輸出信息“無 x ”；7. 圖的基本操作與實(shí)現(xiàn)問題描述 自選存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)對(duì)圖的操作?；疽螅?）自選存儲(chǔ)結(jié)構(gòu)，輸入含 n 個(gè)頂點(diǎn)（用字符表示頂點(diǎn)）和 e 條邊的圖 G；（

9、2）求每個(gè)頂點(diǎn)的度，輸出結(jié)果；（3）指定任意頂點(diǎn) x 為初始頂點(diǎn)，對(duì)圖 G 作 DFS 遍歷，輸出 DFS 頂點(diǎn)序列（提示：使用 一個(gè)棧實(shí)現(xiàn) DFS）；（4）指定任意頂點(diǎn) x 為初始頂點(diǎn)，對(duì)圖 G 作 BFS 遍歷，輸出 BFS 頂點(diǎn)序列（提示：使用 一個(gè)隊(duì)列實(shí)現(xiàn) BFS ）；（5）輸入頂點(diǎn) x ，查找圖 G：若存在含 x 的頂點(diǎn)，則刪除該結(jié)點(diǎn)及與之相關(guān)聯(lián)的邊，并作 DFS 遍歷（執(zhí)行操作 3）；否則，輸出信息“無 x”；（6）判斷圖 G 是否是連通圖，輸出信息“ YES”/“ NO”；（7）如果選用的存儲(chǔ)結(jié)構(gòu)是鄰接矩陣，則用鄰接矩陣的信息生成圖G 的鄰接表，即復(fù)制圖G，然后再執(zhí)行操作 2）；

10、反之亦然。（8）自選圖的其他任意一種操作實(shí)現(xiàn)之。8. 全國交通咨詢模擬問題描述處于不同目的的旅客對(duì)交通工具有不同的要求。例如， 因公出差的旅客希望在旅途中的時(shí)間盡可能地短，出門旅游的旅客則期望旅費(fèi)盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。 編織一個(gè)全國城市間的交通資訊程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢。設(shè)計(jì)要求（1）提供對(duì)城市信息進(jìn)行編輯（如添加或刪除）的功能。（2）城市之間有兩種交通工具：火車和飛機(jī)。提供對(duì)列車時(shí)刻表和飛機(jī)航班進(jìn)行編輯（增 設(shè)或刪除）的功能。（3）提供兩種最優(yōu)決策：最快到達(dá)和最省錢到達(dá)。全程只考慮一種交通工具。（4）旅途中耗費(fèi)的總時(shí)間應(yīng)該包括中轉(zhuǎn)站的等候時(shí)間。（5）咨

11、詢以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行。由用戶輸入起始站、終點(diǎn)站、最優(yōu)決策原則和 交通工具。 輸出信息： 最快需要多長時(shí)間才能到達(dá)或者最少需要多少旅費(fèi)才能到達(dá)， 并詳細(xì) 說明依次于何時(shí)乘坐哪一趟列車或那一次班機(jī)到何地。實(shí)現(xiàn)提示（1）對(duì)全國城市交通圖和列車時(shí)刻表及飛機(jī)航班表進(jìn)行編輯，應(yīng)該提供文件形式輸入和鍵 盤輸入兩種方式。 飛機(jī)航班表的信息應(yīng)包括： 起始站的出發(fā)時(shí)間、 終點(diǎn)站的到達(dá)時(shí)間和票價(jià)； 列車時(shí)刻表則需根據(jù)交通圖給出各個(gè)路段的詳細(xì)信息，例如： 對(duì)從北京到上海的火車， 需給出北京至天津、天津至徐州及徐州至上海各段的出發(fā)時(shí)間、到達(dá)時(shí)間及票價(jià)等信息。（2）以鄰接表座交通圖的存儲(chǔ)結(jié)構(gòu)，表示邊的結(jié)構(gòu)內(nèi)除含

12、有鄰接點(diǎn)的信息外，還應(yīng)包括交 通工具、路程中耗費(fèi)的時(shí)間和花費(fèi)以及出發(fā)和到達(dá)的時(shí)間等多種屬性。（3）增加旅途中轉(zhuǎn)次數(shù)最少的最優(yōu)決策。9. 內(nèi)部排序算法的性能分析問題描述設(shè)計(jì)一個(gè)測(cè)試程序， 比較幾種內(nèi)部排序算法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)以取得直觀感 受?；疽螅?）對(duì)冒泡排序、直接排序、簡(jiǎn)單選擇排序、快速排序、希爾排序、堆排序算法進(jìn)行比較。（2）待排序表的表長不小于 100，表中數(shù)據(jù)隨機(jī)產(chǎn)生，至少用 5 組不同數(shù)據(jù)作比較，比較 指標(biāo)：關(guān)鍵字參加比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換記為3 次移動(dòng)）。（3）輸出比較結(jié)果。選做內(nèi)容（1）對(duì)不同表長進(jìn)行比較。（2）驗(yàn)證各算法的穩(wěn)定性。（3）輸出界面的優(yōu)

13、化。10. 背包問題的求解問題描述 假設(shè)有一個(gè)能裝入總體積為 T 的背包和 n 件體積分別為 w1， w2 ， wn 的物品，能 否從 n 件物品中挑選若干件恰好裝滿背包， 即使 w1+w2+ +wn=T ，要求找出所有滿足上述 條件的解。例如：當(dāng) T=10 ，各件物品的體積 1,8,4,3,5,2 時(shí)，可找到下列 4 組解：（1,4,3,2） （1,4,5）（8,2）（3,5,2）實(shí)現(xiàn)提示 可利用回溯法的涉及思想來解決背包問題。 首先， 將物品排成一列， 然后順序選取物品 裝入背包， 假設(shè)一選取了前 i 件物品之后背包還沒有裝滿， 則繼續(xù)選取第 i+1 件物品， 若該 件物品“太大”不能裝入

14、，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的 物品中找不到合適的物品以填滿背包，則說明“剛剛”裝入背包的那件物品“不適合” ，應(yīng) 將它取出“棄之一邊” ，繼續(xù)再從“它之后”的物品中選取，如此重復(fù)，直至求得滿足條件 的解，或者無解。由于回溯求解的規(guī)則是“后進(jìn)先出”因此自然要用到棧。11. 簡(jiǎn)單個(gè)人圖書管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)問題描述學(xué)生在自己的學(xué)習(xí)和生活中會(huì)擁有很多的書籍， 對(duì)購買的書籍進(jìn)行分類和統(tǒng)計(jì)是一種良 好的習(xí)慣。 這樣可以便于對(duì)這些知識(shí)資料的整理和查詢使用。 如果用文件來存儲(chǔ)相關(guān)書籍的 各種信息，包括分類、購買日期、價(jià)格、簡(jiǎn)介等，輔之以程序來使用這些文件對(duì)里面的書籍 信息進(jìn)行統(tǒng)

15、計(jì)和查詢的工作將使這種書籍管理工作變得輕松而有趣。 簡(jiǎn)單個(gè)人書籍管理系統(tǒng) 的開發(fā)就是為了解決這個(gè)實(shí)際問題的。這個(gè)系統(tǒng)具備如下的功能：（1）存儲(chǔ)書籍各種相關(guān)信息。（2）提供查找功能，按照多種關(guān)鍵字查找需要的書籍，查找成功后可以修改記錄的相 關(guān)項(xiàng)。（ 3）提供排序功能， 按照多種關(guān)鍵字對(duì)所有的書籍進(jìn)行排序， 例如按照價(jià)格進(jìn)行排序。（ 4）其他輔助的維護(hù)工作。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)由于書籍的冊(cè)數(shù)較多， 而且要在程序不再運(yùn)行的時(shí)候仍然要保持里面的數(shù)據(jù)， 所以采用 文件的形式放到外存儲(chǔ)器中，需要操作時(shí)，從文件中調(diào)入內(nèi)存來進(jìn)行查找和排序的工作。12. 簡(jiǎn)易電子表格的設(shè)計(jì)問題描述設(shè)計(jì)一個(gè)支持基本計(jì)算統(tǒng)計(jì)功能和其他一些

16、表格管理/ 處理功能的計(jì)算機(jī)軟件，使用戶可在該軟件的支持下， 用互交方式進(jìn)行表格建立、 數(shù)據(jù)輸入、 數(shù)據(jù)編輯及其他一些表格操作。 基本要求 （1）建立表格：建立空白表格，同時(shí)在屏幕上顯示，使其處于可輸入數(shù)據(jù)狀態(tài)。 （2）輸入數(shù)據(jù)與編輯數(shù)據(jù)：通過鍵盤將數(shù)據(jù)輸入到顯示在屏幕上的電子表格上，同時(shí)要支 持基本的數(shù)據(jù)輸入編輯。（3）基本統(tǒng)計(jì)計(jì)算：統(tǒng)計(jì)計(jì)算的種類包括：合計(jì)、求平均、求最大/小統(tǒng)計(jì)計(jì)算方式；表格按行 /列統(tǒng)計(jì)計(jì)算；表格按塊統(tǒng)計(jì)計(jì)算。（4）排序：使任一行 /列中的數(shù)據(jù)按大?。ㄉ蚪担┡帕校瑢?duì)字符串型數(shù)據(jù)，還要可選大小 寫敏感。（ 5）表格保存：使電子表格存儲(chǔ)在磁盤上（磁盤文件），并可隨時(shí)讀入，

17、供繼續(xù)處理。（6）數(shù)據(jù)復(fù)制：將表格中任一塊數(shù)據(jù)，復(fù)制到另一塊中。復(fù)制到目標(biāo)塊時(shí)，對(duì)目標(biāo)塊中原 內(nèi)容，可選擇下列幾種處理方式：代替、相加、相減、按條件替換。（7）公式支持： 單元格內(nèi)可輸入公式 （表達(dá)式），使對(duì)應(yīng)單元格的最終內(nèi)容為公式的計(jì)算結(jié) 果，公式最基本的形式是算術(shù)計(jì)算公式，公式中可以按名引用其他單元格。13. 停車場(chǎng)模擬管理程序的設(shè)計(jì)與實(shí)現(xiàn)問題描述設(shè)停車場(chǎng)只有一個(gè)可停放幾輛汽車的狹長通道， 且只有一個(gè)大門可供汽車進(jìn)出。 汽車在 停車場(chǎng)內(nèi)按車輛到達(dá)的先后順序依次排列， 若車場(chǎng)內(nèi)已停滿幾輛汽車， 則后來的汽車只能在 門外的便道上等候， 一旦停車場(chǎng)內(nèi)有車開走， 則排在便道上的第一輛車即可進(jìn)入；

18、當(dāng)停車場(chǎng) 內(nèi)某輛車要離開時(shí)， 由于停車場(chǎng)是狹長的通道， 在它之后開入的車輛必須先退出車場(chǎng)為它讓 路，待該車輛開出大門， 為它讓路的車輛再按原次序進(jìn)入車場(chǎng)。 在這里假設(shè)汽車不能從便道 上開走，試設(shè)計(jì)這樣一個(gè)停車廠模擬管理程序。 為了以下描述的方便， 停車廠的停車場(chǎng)用 “停 車位”進(jìn)行敘述，停車廠的便道用“便道”進(jìn)行敘述。14. 農(nóng)夫過河問題的求解問題描述一個(gè)農(nóng)夫帶著一只狼、 一只羊和一棵白菜， 身處河的南岸。 他要把這些東西全部運(yùn)到北 岸。他面前只有一條小船，船只能容下他和一件物品，另外只有農(nóng)夫才能撐船。如果農(nóng)夫在 場(chǎng)，則狼不能吃羊，羊不能吃白菜，否則狼會(huì)吃羊，羊會(huì)吃白菜，所以農(nóng)夫不能留下羊和白

19、 菜自己離開， 也不能留下狼和羊自己離開， 則狼不吃白菜。 請(qǐng)求出農(nóng)夫?qū)⑺械臇|西運(yùn)過河 的方案。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)求解這個(gè)問題的簡(jiǎn)單方法是步步進(jìn)行試探，每步搜索所有可能的選擇，對(duì)前一 步合適的選擇再考慮下一步的各種方案。要模擬農(nóng)夫過河問題，首先需要對(duì)問題中每個(gè)角色的位置進(jìn)行描述。一個(gè)很方便的辦 法是用 4 位二進(jìn)制數(shù)順序分別表示農(nóng)夫、 狼、 白菜和羊的位置。 用 0 表示農(nóng)夫或者某東西在 河的南岸， 1 表示在河的北岸。 例如整數(shù) 5（其二制表示為 0101）表示農(nóng)夫和白菜在河的南岸， 而狼和羊在北岸?，F(xiàn)在問題變成： 從初的狀態(tài)二進(jìn)制 0000（ 全部在河的南岸 ）出發(fā)，尋找一種全部由安全狀 態(tài)

20、構(gòu)成的狀態(tài)序列，它以二進(jìn)制1111（全部到達(dá)河的北岸）為最終目標(biāo)，并且在序列中的每一個(gè)狀態(tài)都可以從前一狀態(tài)到達(dá)。為避免瞎費(fèi)功夫，要求在序列中不出現(xiàn)重復(fù)的狀態(tài)。實(shí)現(xiàn)上述求解的搜索過程可以采用兩種不同的策略：一種廣度優(yōu)先搜索，另一種深度 優(yōu)先搜索。這里介紹在廣度優(yōu)先搜索方法中采用的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。廣度優(yōu)先就是在搜索過程中總是首先搜索下面一步的所有可能狀態(tài)，再進(jìn)一步考慮更 后面的各種情況。 要實(shí)現(xiàn)廣度優(yōu)先搜索， 可以使用隊(duì)列。 把下一步所有可能的狀態(tài)都列舉出 來，放在隊(duì)列中，再順序取出來分別進(jìn)行處理，處理過程中把再下一步的狀態(tài)放在隊(duì)列 里， 由于隊(duì)列的操作遵循先進(jìn)先出的原則， 在這個(gè)處理過程中， 只有

21、在前一步的所有情 況都處理完后， 才能開始后面一步各種情況的處理。 這樣， 具體算法中就需要用一個(gè)整數(shù)隊(duì) 列 moveTo ，它的每個(gè)元素表示個(gè)可以安全到達(dá)的中間狀態(tài)。另外還需要一個(gè)數(shù)據(jù)結(jié)構(gòu)記 錄已被訪問過的各個(gè)狀態(tài)， 以及己被發(fā)現(xiàn)的能夠到達(dá)當(dāng)前這個(gè)狀態(tài)的路徑。 由于在這個(gè)問題 的解決過程中需要列舉的所有狀態(tài) （二進(jìn)制 0000 到 1111）一共 16 種，所以可以構(gòu)造一個(gè)包含 16 個(gè)元素的整數(shù)順序表來實(shí)現(xiàn)。 順序表的第 i 個(gè)元素記錄狀態(tài) i 是否已被訪問過， 若已被訪 問過則在這個(gè)順序表元素中記入前驅(qū)狀態(tài)值，把這個(gè)順序表叫做route。 route 的每個(gè)分量初始值為 -1。 rout

22、e 的一個(gè)元素具有非負(fù)值表示這個(gè)狀態(tài)已訪問過，或是正被考慮。最后可以 利用 route 順序表元素的值建立起正確的狀態(tài)路徑。 于是得到農(nóng)夫過河問題的廣度優(yōu)先算法。在具體應(yīng)用時(shí)，采用鏈隊(duì)和順序隊(duì)均可，為敘述的方便，不妨設(shè)為使用順序隊(duì)。15. 電話號(hào)碼查詢系統(tǒng)問題描述設(shè)計(jì)散列表實(shí)現(xiàn)電話號(hào)碼查找系統(tǒng)。基本要求 （1）設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、地址；（2）從鍵盤輸入各記錄，分別以電話號(hào)碼和用戶名為關(guān)鍵字建立散列表；（3）采用一定的方法解決沖突； （4）查找并顯示給定電話號(hào)碼的記錄；（5）查找并顯示給定用戶名的記錄。整個(gè)系統(tǒng)必須滿足系統(tǒng)功能要求； 設(shè)計(jì)不同的散列函數(shù)， 比較沖突率； 在散

23、列函數(shù)確定 的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。16. 跳表（ Skip List ）的實(shí)現(xiàn)與分析基本要求 構(gòu)造并實(shí)現(xiàn)跳表（ Skip List ）的 ADT ADT中應(yīng)包括初始化、查找、插入、刪除等基本 操作。 分析各基本操作的時(shí)間復(fù)雜性。 針對(duì)一個(gè)實(shí)例實(shí)現(xiàn) Skip List 的動(dòng)態(tài)演示 （ 圖形演示 ） 。17. B- 樹的實(shí)現(xiàn)及分析基本要求 實(shí)現(xiàn)在 B- 樹上的查找，并分析其時(shí)間復(fù)雜性。 實(shí)現(xiàn) B-樹的ADT ，包括其上的基本操作：結(jié)點(diǎn)的加入和刪除。 要求B-樹結(jié)構(gòu)中的 M=3 或5，實(shí)現(xiàn)其中的一種即可。 實(shí)現(xiàn)基本操作的 動(dòng)態(tài)演示 （ 圖形演示 ） 。18

24、. AVL 樹的實(shí)現(xiàn)及分析?；疽?編寫 AVL 樹判別程序，并判別一個(gè)二叉搜索樹是否為 AVL 樹。二叉搜索樹用其先序 遍歷結(jié)果表示，如： 5，2，1，3， 7，8。 實(shí)現(xiàn) AVL 樹的 ADT ，包括其上的基本操作：結(jié)點(diǎn)的加入和刪除； 實(shí)現(xiàn)基本操作的動(dòng)態(tài)演示 （ 圖形演示 ） 。19. 長整數(shù)的代數(shù)計(jì)算問題描述 應(yīng)用線性數(shù)據(jù)結(jié)構(gòu)解決長整數(shù)的計(jì)算問題。設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)完成長整數(shù)的表示和存 儲(chǔ)，并編寫算法來實(shí)現(xiàn)兩長整數(shù)的加、減、乘、除等基本代數(shù)運(yùn)算。基本要求 長整數(shù)長度在一百位以上。 實(shí)現(xiàn)兩長整數(shù)在取余操作下的加、 減、乘、除操作， 即實(shí)現(xiàn)算法來求解 a+b mod n, a-b mod n,

25、a b mod n, a b mod n 。 輸入輸出均在文件中。 分析算法的時(shí)空復(fù)雜性。實(shí)現(xiàn)提示 需將長整數(shù)的加法轉(zhuǎn)化為多個(gè)一般整數(shù)加法的組合。20. 公交線路上優(yōu)化路徑的查詢問題描述最短路徑問題是圖論中的一個(gè)經(jīng)典問題，其中的 Dijkstra 算法一直被認(rèn)為是圖論中的好 算法，但有的時(shí)候需要適當(dāng)?shù)恼{(diào)整 Dijkstra 算法才能完成多種不同的優(yōu)化路徑的查詢。對(duì)于某城市的公交線路，乘坐公交的顧客希望在這樣的線路上實(shí)現(xiàn)各種優(yōu)化路徑的查 詢。設(shè)該城市的公交線路的輸入格式為：線路編號(hào)：起始站名 （ 該站坐標(biāo) ）；經(jīng)過的站點(diǎn) 1名 （該站坐標(biāo) ）；經(jīng)過的站點(diǎn) 2名（該站坐 標(biāo)）；經(jīng)過的站點(diǎn) n名 （

26、該站坐標(biāo) ）；終點(diǎn)站名 （該站坐標(biāo) ）。該線路的乘坐價(jià)錢。該線路 平均經(jīng)過多少時(shí)間來一輛。車速。例如：63：A（32,45）；B（76,45）；C（76,90）； N（100,100） 。1元。 5分鐘。 1/每分鐘。假定線路的乘坐價(jià)錢與乘坐站數(shù)無關(guān)，假定不考慮公交線路在路上的交通堵塞。 對(duì)這樣的公交線路， 需要在其上進(jìn)行的優(yōu)化路徑查詢包括： 任何兩個(gè)站點(diǎn)之間最便宜的 路徑；任何兩個(gè)站點(diǎn)之間最省時(shí)間的路徑等等?；疽?根據(jù)上述公交線路的輸入格式，定義并建立合適的圖模型。 針對(duì)上述公交線路，能查詢獲得任何兩個(gè)站點(diǎn)之間最便宜的路徑，即輸入站名S， T后，可以輸出從 S到T的最便宜的路徑，輸出格式

27、為：線路 x：站名 S，站名 M1 ；換乘線路 x： 站名M1 ，站名 M2 ；換乘線路 x：站名MK ，站名 T。共花費(fèi) x元。 針對(duì)上述公交線路，能查詢獲得任何兩個(gè)站點(diǎn)之間最省時(shí)間的路徑（不考慮在中間站等 下一輛線路的等待時(shí)間），即輸入站名S， T后，可以輸出從 S到 T的考慮在中間站等下一輛線路的等待時(shí)間的最省時(shí)間的路徑， 輸出格式為： 線路x：站名S，站名 M1 ；換乘線路 x： 站名M1 ，站名 M2 ；換乘線路 x：站名MK ，站名 T。共花費(fèi) x時(shí)間。 針對(duì)上述公交線路，能查詢獲得任何兩個(gè)站點(diǎn)之間最省時(shí)間的路徑（要考慮在中間站等 下一輛線路的等待時(shí)間），即輸入站名S， T后，可以

28、輸出從 S到 T的考慮在中間站等下一輛線路的等待時(shí)間的最省時(shí)間的路徑， 輸出格式為： 線路x：站名S，站名 M1 ；換乘線路 x： 站名M1 ，站名 M2 ；換乘線路 x：站名MK ，站名 T。共花費(fèi) x時(shí)間。（4）實(shí)現(xiàn)提示 需深入考慮，應(yīng)根據(jù)不同的應(yīng)用目標(biāo)，即不同的優(yōu)化查詢來建立合適的圖模型。21. 文檔集合上的查詢問題描述 設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)完成在一個(gè)文檔集合的存儲(chǔ)，并構(gòu)造算法實(shí)現(xiàn)其內(nèi)容的查詢。該設(shè) 計(jì)包括三個(gè)部分：（一）應(yīng)用數(shù)據(jù)結(jié)構(gòu)完成文檔集合的內(nèi)容 （ 基于單詞的 ）存儲(chǔ)，并為下一步的查詢建立 索引。（二 ） 就單個(gè)單詞的查詢請(qǐng)求，設(shè)計(jì)算法進(jìn)行查詢。（三）對(duì)多個(gè)單詞通過 AND和OR構(gòu)造的復(fù)

29、雜查詢進(jìn)行處理 （ 此處可只做兩個(gè)單詞的情 況 ） 。具體情形如下面的例子：ExampleDoc1: I like the class on data structures and algorithms.Doc2: I hate the class on data structures and algorithms.Doc3: Interesting statistical data may result from this survey.Here are the answers to some queries:Query 1: dataDoc1, Doc2, Doc3Query2: data

30、 AND structuresDoc1, Doc2Query 3: like OR surveyDoc1, Doc3文檔集合上的查詢實(shí)例基本要求 文檔集合中的文檔數(shù)不能少于 20 個(gè)。 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)以及查找算法的構(gòu)造應(yīng)考慮如何最大程度的提高查詢效率。 查詢效率的提高應(yīng)是綜合多種查詢的，而不是只針對(duì)一種查詢的優(yōu)化。 給出查詢效率的模擬實(shí)驗(yàn)數(shù)據(jù)。實(shí)現(xiàn)提示AND 和OR 查詢可轉(zhuǎn)變?yōu)閱蝹€(gè)單詞查詢結(jié)果的組合。22. 應(yīng)用堆實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列并實(shí)現(xiàn)作業(yè)的優(yōu)先調(diào)度問題描述優(yōu)先隊(duì)列 priority queue是一種可以用于很多場(chǎng)合的數(shù)據(jù)結(jié)構(gòu)， 應(yīng)用堆結(jié)構(gòu)設(shè)計(jì)并實(shí) 現(xiàn)一個(gè)優(yōu)先隊(duì)列。應(yīng)用該優(yōu)先隊(duì)列實(shí)現(xiàn)作業(yè)的優(yōu)

31、先調(diào)度：一個(gè)作業(yè) ti =（ si ，ei），si為作業(yè)的開始時(shí)間 （進(jìn)入時(shí)間） ，ei為作業(yè)的結(jié)束時(shí)間 （離 開時(shí)間）。作業(yè)調(diào)度的基本任務(wù)是從當(dāng)前在系統(tǒng)中的作業(yè)中選取一個(gè)來執(zhí)行，如果沒 有作業(yè)則執(zhí)行 nop操作。本題目要求的作業(yè)調(diào)度是基于優(yōu)先級(jí)的調(diào)度，每次選取優(yōu)先 級(jí)最高的作業(yè)來調(diào)度，優(yōu)先級(jí)用優(yōu)先數(shù)（每個(gè)作業(yè)一個(gè)優(yōu)先數(shù)pi）表征，優(yōu)先數(shù)越小，優(yōu)先級(jí)越高。作業(yè) t i進(jìn)入系統(tǒng)時(shí)，即 si時(shí)刻，系統(tǒng)給該作業(yè)指定其初始優(yōu)先數(shù) pi = ei - si， 從而使越短的作業(yè)優(yōu)先級(jí)越高。該優(yōu)先數(shù)在作業(yè)等待調(diào)度執(zhí)行的過程中會(huì)不斷減小， 調(diào)整公式為： pi = pi - w i，其中的 wi為作業(yè) t i的

32、等待時(shí)間： wi = 當(dāng)前時(shí)間 -si。一旦作業(yè) 被調(diào)度，該作業(yè)就一直執(zhí)行，不能被搶占，只有當(dāng)前執(zhí)行作業(yè)指向完成時(shí)，才產(chǎn)生下 一輪調(diào)度。所以可以在每次調(diào)度前動(dòng)態(tài)調(diào)整各作業(yè)的優(yōu)先數(shù)。編程實(shí)現(xiàn)這樣一個(gè)作業(yè)調(diào)度系統(tǒng)?；疽?給出優(yōu)先隊(duì)列的 ADT 描述，包括隊(duì)列的邏輯結(jié)構(gòu)及其上基本操作。 以堆結(jié)構(gòu)為輔助結(jié)構(gòu)實(shí)現(xiàn)優(yōu)先隊(duì)列的存儲(chǔ)表示并實(shí)現(xiàn)其上的基本操作。 作業(yè)集合中的各作業(yè)隨機(jī)生成，根據(jù)作業(yè)的s 屬性和 e屬性動(dòng)態(tài)調(diào)整作業(yè)隊(duì)列，不斷加入作業(yè)，作業(yè)結(jié)束刪除作業(yè)。 要對(duì)作業(yè)調(diào)度的結(jié)果給出清晰的輸出信息，包括：何時(shí)作業(yè)進(jìn)入，何時(shí)調(diào)度哪 個(gè)作業(yè)，何時(shí)離開，每個(gè)作業(yè)等待多長時(shí)間，優(yōu)先數(shù)的動(dòng)態(tài)變化情況等。23.

33、LZW壓縮算法及應(yīng)用基本要求 在一個(gè)文本文件上實(shí)現(xiàn) LZW 壓縮和解壓縮，其中每個(gè)字符就是該文本的8位 ASCII 碼。 在實(shí)現(xiàn) LZW 過程中需要仔細(xì)考慮如何在編譯表中找到匹配或找不到匹配， 需要注意匹配 算法的時(shí)間、空間開銷。 （選做 ）應(yīng)用 LZW 算法實(shí)現(xiàn) 256色灰度 BMP 圖像文件的壓縮和解壓縮。24. 應(yīng)用等價(jià)類生成隨機(jī)迷宮并尋找迷宮路徑問題描述 ：使用等價(jià)類來構(gòu)造一個(gè) N N的從左上角到右下角只有一條路徑的隨機(jī)迷宮， 然后在這一 迷宮上 尋找迷宮路徑 。該設(shè)計(jì)共包含如下四個(gè)部分： 等價(jià)類數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和實(shí)現(xiàn) 構(gòu)建隨機(jī)迷宮 尋找迷宮路徑 將迷宮和路徑用圖形方式畫出 用圖形方式將

34、上述算法獲得的隨機(jī)迷宮及其上的最短路徑畫出。 用線段來表示迷宮中的 墻，用在每個(gè)方格中心的點(diǎn)來表示路徑。25. 約瑟夫環(huán) （ 學(xué)號(hào)： 問題描述： 編號(hào)為 1，2 n 的 n 個(gè)人按順時(shí)針方向圍坐一圈， 每人持有一個(gè)密碼 （正整數(shù)） 。 一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m，從第一個(gè)人開始按順時(shí)針方向自 1 開始順序報(bào)數(shù)，報(bào)到 m時(shí)停止報(bào)數(shù)， 報(bào) m的人出列， 將他的密碼作為新的 m值，從他的順時(shí)針方向上的 下一個(gè)開始重新從 1 報(bào)數(shù)， 如此下去， 直至所有人全部出列為止， 以單循環(huán)鏈表為存儲(chǔ)結(jié)構(gòu) 設(shè)計(jì)一個(gè)程序以求出出列各人的編號(hào)的序列。26. 最小生成樹問題 （ 學(xué)號(hào)： 問題描述 ：給定一個(gè)

35、地區(qū)的 n 個(gè)城市間的距離網(wǎng)（要求至少 6個(gè)城市， 10 條邊），用 Prim 算法和 Kruskal 算法建立最小生成樹，并計(jì)算得到的最小生成樹的代價(jià)。（分別使用 Prim 算法和 Kruskal 算法）27. 交通咨詢模擬 （ 學(xué)號(hào)： 問題描述 ：建立一個(gè)模擬的交通網(wǎng)絡(luò) （用有向網(wǎng)來表示）， 編程實(shí)現(xiàn)從某個(gè)城市出發(fā)到另一 個(gè)城市所需的最短時(shí)間及路徑。28. 哈夫曼編碼譯碼器 （ 學(xué)號(hào)： 問題描述 ：打開一篇英文文章，統(tǒng)計(jì)該文章中每個(gè)字符出現(xiàn)的次數(shù)，然后以它們作為權(quán)值， 對(duì)每一個(gè)字符進(jìn)行編碼，編碼完成后再對(duì)其編碼進(jìn)行譯碼。29. 紙牌游戲 （ 學(xué)號(hào) ： 問題描述 ：編號(hào)為 1-52 張牌，正

36、面向上，從第 2 張開始，以 2為基數(shù)，是 2 的倍數(shù)的牌翻 一次，直到最后一張牌；然后，從第 3 張開始，以 3 為基數(shù)，是 3 的倍數(shù)的牌翻一次，直到 最后一張牌；然后從第 4 張開始，以 4 為基數(shù)，是 4 的倍數(shù)的牌翻一次， 直到最后一張 牌；. 再依次 5的倍數(shù)的牌翻一次， 6的，7的 直到 以 52為基數(shù)的 翻過，輸出：這時(shí)正 面向上的牌有哪些？30. 排序算法 （ 學(xué)號(hào)： 問題描述 ：在教材中，各種內(nèi)排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階， 或大概執(zhí)行時(shí)間。 試通過隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)， 以取得直觀感 受?；疽?：設(shè)待排序表的表長不小于

37、1000；其中的數(shù)據(jù)使用隨機(jī)數(shù)，對(duì)表中數(shù)據(jù)使用各種 常的內(nèi)排序方法進(jìn)行排序； 至少使用 5 組不同的輸入數(shù)據(jù)作比較， 比較的指標(biāo)為每種算法中 關(guān)鍵字參與的比較、 移動(dòng)次數(shù) （關(guān)鍵字交換計(jì)為 3 次移動(dòng)）。最后要求對(duì)結(jié)果作出簡(jiǎn)單分析， 包括對(duì)各組數(shù)據(jù)得出結(jié)果波動(dòng)大小的解釋。31. 拓?fù)渑判騿栴} （ 學(xué)號(hào)：?jiǎn)栴}描述 ：任意給定一個(gè) AOV網(wǎng)絡(luò)，編寫程序檢測(cè)其是否存在有向回路？31. 文章編輯 （ 學(xué)號(hào)： 問題描述 ：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁文章， 每行最多不超過 80 個(gè)字符，共 N行；要求（ 1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇 文章總字?jǐn)?shù)； （ 2

38、）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（ 3）刪除某一子串，并將后面的字符前移。存儲(chǔ)結(jié)構(gòu)使用線性表； 輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。輸出形式：（ 1）分行輸出用戶輸入的各行字符；（2）分 4 行輸出 全部字母數(shù) 、數(shù)字個(gè)數(shù)、 空格個(gè)數(shù) 、 文章總字?jǐn)?shù) （ 3）輸出刪除某一字符串后的文章；32. 訂票系統(tǒng) （ 學(xué)號(hào)：此系統(tǒng)可以實(shí)現(xiàn)如下功能 ：錄入： 可以錄入航班情況 （數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中， 數(shù)據(jù)結(jié)構(gòu)、 具體數(shù)據(jù)自定） 查詢：可以查詢某個(gè)航線的情況（如，輸入航班號(hào)，查詢起降時(shí)間，起飛抵達(dá)城市，航 班票價(jià)，票價(jià)折扣，確定航班是否滿倉）；

39、可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況； 訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已 經(jīng)無票，可以提供相關(guān)可選擇航班；退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件； 客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。 修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件問題描述 ： 根據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；33. 集合運(yùn)算 （ 學(xué)號(hào)：?jiǎn)栴}描述 ：編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序。34. 馬踏棋盤 問題描述 設(shè)計(jì)一個(gè)國際象棋的馬踏遍棋盤的演示程序 設(shè)計(jì)要求 輸入：設(shè)計(jì)程序按要求輸入馬的初始位置（相應(yīng)的坐標(biāo)）

40、 輸出：程序的設(shè)計(jì)完成后應(yīng)給出馬從初始位置走遍棋盤的過程，并按照求出的行走路線的順序，將數(shù)字 1,2，。，64 依次填入一個(gè) 8*8 的方陣并輸出。 數(shù)據(jù)結(jié)構(gòu)使用的數(shù)據(jù)結(jié)構(gòu)是棧。 利用順序棧來實(shí)現(xiàn)。 此問題是指將馬隨機(jī)放在國際象棋的 8*8 棋盤的 某個(gè)方格中，按規(guī)則馬走日字進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍 64 個(gè)方格。從用 戶給出的初始位置開始判斷，按順時(shí)針順序每次產(chǎn)生一個(gè)路點(diǎn)，驗(yàn)證是新路點(diǎn)，則入棧，重 復(fù)進(jìn)行。如果一個(gè)路點(diǎn)的可擴(kuò)展路點(diǎn)為0。進(jìn)行回溯。35. 八皇后問題 （ 學(xué)號(hào)：?jiǎn)栴}描述 ：設(shè)在初始狀態(tài)下在國際象棋棋盤上無任何棋子（皇后） ，然后順序在第 1 行，第2 行，第 8 行上放置棋子。在每一行中有 8 個(gè)可選擇位置，但在任一時(shí)刻，棋盤的合 法布局都必須滿足三個(gè)限制條件， 即任何兩個(gè)棋子不得放在同一行、 或同一列， 或同一斜線 上。編寫一個(gè)算法，求解并輸出此問題的所有合法布局。算法思想 ：從第一行起逐行放置， 依次對(duì) 1到 8