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