數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書20xx-資料下載頁

　　

【正文】 果數(shù)據(jù)要保存到文件中。測試數(shù)據(jù)：分別選擇男生多于女生、女生多于男生、男女生相等的三組測試數(shù)據(jù) 提高要求：計算出任意一位男生(編號為X)和任意一位女生(編號為Y), 在第K曲配對跳舞的情況。4．文學(xué)研究助手（*）問題描述：文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標(biāo)的文字統(tǒng)計系統(tǒng)，稱為“文學(xué)研究助手”。基本要求：英文小說存于一個文本文件中，待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設(shè)計, 結(jié)果保存到文件中。提高要求：模式匹配選取KMP算法測試數(shù)據(jù)：以你的C/C++/JAVA源程序模擬英文小說，相應(yīng)語言的保留字集作為待統(tǒng)計的詞匯集。5．哈希表的設(shè)計與實現(xiàn)（*）問題描述：針對某個單位電話號碼簿，設(shè)計一個哈希表，并完成相應(yīng)的建表和查表程序。基本要求：設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、住址。從鍵盤輸入各記錄，以用戶名為關(guān)鍵字建立哈希表，哈希函數(shù)用除留取余數(shù)法構(gòu)造，采用線性探測法解決沖突。可以插入、查找、刪除并顯示給定用戶名的記錄，并計算查找長度, 哈希表保存到文件中。測試數(shù)據(jù)：取某個單位電話號碼簿中的30個記錄。提高要求：將電話號碼薄以文件形式保存到盤上，能夠按用戶名和電話號碼兩種形式建立哈希表并實現(xiàn)插入、查找、刪除表中元素的功能。6．管道鋪設(shè)施工的最佳方案（*）問題描述:需要在某個城市的n個小區(qū)鋪設(shè)管道，則在這n個小區(qū)之間鋪設(shè)n1條管道即可，假設(shè)任意兩個居民區(qū)之間都可以架設(shè)管道，但由于地理環(huán)境的不同，所需經(jīng)費不同，選擇最優(yōu)的施工方案使總投資盡可能的少。基本要求：輸入表示小區(qū)間關(guān)系的圖及每條管道的權(quán)值，選擇出n1條管道, 使總投資最小。圖的信息輸入一次后, 保存到文件中, 選擇的n1條管道輸出到顯示器的同時, 也保存于文件中。測試用例：任意選擇一個圖，模擬小區(qū)間可能鋪設(shè)的管道及費用。提高要求：顯示原始圖及選擇n1條管道后的圖。7．安排教學(xué)計劃（**）問題描述：大學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩個學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排上必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課程恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序。基本要求：輸入?yún)?shù)包括學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課程的課程號、學(xué)分和直接先修課的課程號；允許兩種策略，一是使學(xué)生在各學(xué)期的學(xué)習(xí)負(fù)擔(dān)盡量均勻，二是使課程盡量集中在前幾個學(xué)期；若根據(jù)給定的條件問題無解，則報告適當(dāng)?shù)男畔ⅲ駝t將教學(xué)計劃輸出到用戶指定的文件中。教學(xué)計劃的表格格式自行設(shè)定, 可以從鍵盤讀取數(shù)據(jù)也可以從文件讀取數(shù)據(jù), 結(jié)果保存到文件中。測試數(shù)據(jù)：學(xué)期總數(shù)為6，學(xué)分上限為10，該專業(yè)共開設(shè)12門。以08級某專業(yè)必修課與選修課為例，選擇12門課程及相應(yīng)學(xué)分，制定一個表明各門課程先后約束關(guān)系的有向圖。提高要求：產(chǎn)生多種不同的方案，并使方案之間的差異盡可能地大。8．停車場管理程序(**)問題描述：設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。基本要求：每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費，單位時間的停車費用由用戶從鍵盤輸入）。測試數(shù)據(jù)：設(shè)輸入數(shù)據(jù)為：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。其中，‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入結(jié)束。提高要求：設(shè)停車場有南、北兩個門，每個門都可以進(jìn)、出車輛。9．計算表達(dá)式的值(**)問題描述：對于給定的一個表達(dá)式，表達(dá)式中可以包括常數(shù)、算術(shù)運行符（“+”、“”、“*”、“/”）和括號，編寫程序計算表達(dá)式的值。基本要求：從鍵盤輸入一個正確的中綴表達(dá)式，將中綴表達(dá)式轉(zhuǎn)換為對應(yīng)的后綴表達(dá)式，計算后綴表達(dá)式的值。測試數(shù)據(jù)：任意選取一個符合題目要求的表達(dá)式。提高要求：（1）對于表達(dá)式中的簡單錯誤，能夠給出提示；（2）表達(dá)式中可以包括單個字母表示的變量。10．設(shè)計Huffman 編碼器與解碼器（***）問題描述：利用哈夫曼編碼進(jìn)行信息通訊可以大大提高信道的利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼；在接受端將傳來的數(shù)據(jù)進(jìn)行譯碼。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個哈夫曼碼的編/譯碼系統(tǒng)。基本要求：根據(jù)某字符文件統(tǒng)計字符出現(xiàn)頻度，構(gòu)造Huffman 樹，編制Huffman編碼，并將給定字符文件編碼，生成編碼文件；再將給定編碼文件解碼，生成字符文件。（要求按二進(jìn)制位表示編碼）測試數(shù)據(jù)：英文文件。提高要求：用二進(jìn)制表示編碼，生成二進(jìn)制的編碼文件。11．銀行業(yè)務(wù)模擬（***）問題描述：設(shè)銀行有四個服務(wù)窗口，一個等待隊列, 每個窗口均可以辦理存款、取款、掛失、還貸業(yè)務(wù)，每種業(yè)務(wù)所需的服務(wù)時間不同，客戶到達(dá)銀行后，先到打號機上打號，號票上包括到達(dá)時間、編號和需要辦理的業(yè)務(wù)，然后在銀行內(nèi)等候, 當(dāng)任一服務(wù)窗口空閑時,處理等候客戶中排在最前面的客戶的業(yè)務(wù)。寫一個上述銀行業(yè)務(wù)的模擬系統(tǒng),通過模擬方法求出客戶在銀行內(nèi)逗留的平均時間和每個窗口辦理的客戶數(shù)及辦理的每種業(yè)務(wù)數(shù)。基本要求：每個客戶到達(dá)銀行的時間和需要辦理的業(yè)務(wù)隨機產(chǎn)生，輸出一天客戶在銀行的平均逗留時間和每個窗口每天辦理的客戶數(shù)和每種業(yè)務(wù)數(shù)。測試數(shù)據(jù)：營業(yè)時間為8小時，其他模擬量自行設(shè)定。12．程序源代碼的相似性（***）問題描述：對于兩個C++語言的源程序代碼，用哈希表的方法分別統(tǒng)計兩個程序中使用C++語言關(guān)鍵字的情況，并最終按定量的計算結(jié)果，得出兩份程序的相似性。基本要求：建立C++語言關(guān)鍵字的哈希表，統(tǒng)計在每個源程序中C++關(guān)鍵字出現(xiàn)的頻度, 得到兩個向量X1和X2，通過計算向量X1和X2的相對距離來判斷兩個源程序的相似性。例如: 關(guān)鍵字 Void Int For Char if else while do break class 程序1關(guān)鍵字頻度 4 3 0 4 3 0 7 0 0 2 程序2關(guān)鍵字頻度 4 2 0 5 4 0 5 2 0 1 X1=[4,3,0,4,3,0,7,0,0,2] X2=[4,2,0,5,4,0,5,2,0,1] 設(shè)s是向量X1和X2的相對距離，s=sqrt(∑(xi1xi2)2)，當(dāng)X1=X2時，s=0, 反映出可能是同一個程序；s值越大，則兩個程序的差別可能也越大。測試數(shù)據(jù): 選擇若干組編譯和運行都無誤的C++程序，程序之間有相近的和差別大的，用上述方法求s, 對比兩個程序的相似性。提高要求：建立源代碼用戶標(biāo)識符表，比較兩個源代碼用戶標(biāo)識符出現(xiàn)的頻度，綜合關(guān)鍵字頻度和用戶標(biāo)識符頻度判斷兩個程序的相似性。13．小型文本編輯器問題描述：設(shè)計一個行編輯程序，使其具有通常行編輯器(如Vi、Edlin)應(yīng)具備的基本功能。基本要求：編輯器應(yīng)具備對文本文件的查找、插人、刪除、修改、字符串替換、統(tǒng)計字?jǐn)?shù)，統(tǒng)計行數(shù)等功能，對于超過一屏的長文件，應(yīng)能夠分頁顯示，查找功能用字符串匹配算法實現(xiàn)。設(shè)計用戶接口命令，實現(xiàn)對文本的編輯。具體的編輯命令，可參考數(shù)據(jù)結(jié)構(gòu)算法網(wǎng)絡(luò)教學(xué)平臺上提供的edlin、Vi的命令集。測試數(shù)據(jù)：任一文本文件。提高要求：“* ”、“? ”等通配符；、粘貼等功能；提示：可以考慮用雙向鏈表實現(xiàn)，每一結(jié)點表示一行字符，注意每行字符不能超過255。14．小型英漢詞典問題描述：設(shè)計一個英漢詞典，支持Member(查找)、Insert(插入)、Delete(刪除)操作。基本要求：實現(xiàn)字典的常用方法有：有序線性表（Memeber用二分檢索實現(xiàn)）、AVL樹（二叉搜索樹）、Patricia Trie、散列表等，任選一種方法實現(xiàn)字典的操作，查找單詞、插入單詞（插入時，先查找，找不到插入，找到提示用戶）、刪除單詞（刪除時，先查找，找到刪除，找不到提示用戶）。測試數(shù)據(jù)：任一英文單詞。提高要求：選用兩種以上的方法實現(xiàn)字典的操作，并比較不同實現(xiàn)算法的時間復(fù)雜度和空間復(fù)雜度。提示：字典可以自己建立，但必須按字母a~z建立26個文件，建議從網(wǎng)上下載，文件類型為txt。備注：*號，表示題目的難度系數(shù)；對應(yīng)的評定成績等級為及格（無*號）、中等（*號）、良好（**號）、優(yōu)秀（***號），學(xué)生完成題目的基本要求，即可得到程序設(shè)計部分的相應(yīng)等級成績，完成題目提高要求，成績可以向上浮動，如果沒有完成基本要求，成績向下浮動，直至不及格。++完成，不能用C或MFC。“*”號多的題目。