個(gè)人資料整理 僅限學(xué)習(xí)使用計(jì)算機(jī)科學(xué)與工程學(xué)院集中性實(shí)踐教案計(jì)劃書<2018—2018 學(xué)年第 二學(xué)期）課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)軟件工程、網(wǎng)絡(luò)工程班 級(jí)：計(jì)算機(jī)科學(xué)與技術(shù) 091-6軟件工程091-4網(wǎng)絡(luò)工程091-4課程負(fù)責(zé)人：李錫祚、王玲芬、李威指導(dǎo)教師分配情況：專業(yè) 指導(dǎo)教師計(jì)算機(jī)科學(xué)與技術(shù) 李威、包書哲、鄭海旭、商周、張恒博、李靈華、王巍、云健、劉爽、李笑牛、軟件工程 魏曉鳴、焉德軍、王玲芬、宋海玉、趙丹丹、趙晶瑩、王存睿、孫世昶網(wǎng)絡(luò)工程 李錫祚、劉向東、盧桂艷、姜楠個(gè)人資料整理 僅限學(xué)習(xí)使用教案起止周：第 1至3教案周一、 教案目的與要求：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)的目的是使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性，合理的組織數(shù)據(jù)并能綜合二、 主要階段、內(nèi)容、時(shí)間及地點(diǎn)安排 <以天為單位計(jì)）：階段與內(nèi)容第1階段：指導(dǎo)教師布置設(shè)計(jì)任務(wù)并解讀有關(guān)題目的設(shè)計(jì)指標(biāo)和任務(wù)的具體內(nèi)容，學(xué)生選擇題目第2階段：明確題目要求、確定數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)算法，編寫程序、調(diào)試程序、測(cè)試程序<11天）；第3階段：完成設(shè)計(jì)任務(wù)，撰寫課程設(shè)計(jì)報(bào)告，準(zhǔn)備驗(yàn)收、答辯<2天）；第4階段：驗(yàn)收、答辯<上機(jī)演示，回答教師提問(wèn)）<1天）。地點(diǎn)與時(shí)間地點(diǎn)：計(jì)算機(jī)科與技術(shù) 091-6綜合樓1機(jī)房、3機(jī)房、嵌入式機(jī)房<第一周）計(jì)算機(jī)科與技術(shù)091-6綜合樓嵌入式機(jī)房，二教網(wǎng)絡(luò)基礎(chǔ)實(shí)驗(yàn)室、網(wǎng)絡(luò)測(cè)試實(shí)驗(yàn)室 <第二、三周）軟件工程091-4多媒體機(jī)房<二）網(wǎng)絡(luò)工程091-4多媒體機(jī)房<一）時(shí)間：計(jì)算機(jī)科學(xué)與技術(shù)：課程設(shè)計(jì)上機(jī)時(shí)間表周第一周 上第二周 上第三周 上周第一周 上第二周 上第三周 上課程設(shè)計(jì)上機(jī)時(shí)間表個(gè)人資料整理 僅限學(xué)習(xí)使用周第一周 上第二周 上第三周 上三、課程設(shè)計(jì)題目及具體要求：成績(jī)管理問(wèn)題描述：給出 n個(gè)學(xué)生的考試成績(jī)表，成績(jī)表包括學(xué)生的學(xué)號(hào)、姓名、考試成績(jī) <高等數(shù)學(xué)、英語(yǔ)、物理），基本要求：<1）建立成績(jī)表，能夠插入、刪除、修改學(xué)生的成績(jī)記錄；<2）按任一單科成績(jī)排序；(3> 計(jì)算每名學(xué)生的平均成績(jī)；(4> 統(tǒng)計(jì)任一單科成績(jī)不及格的學(xué)生人數(shù) , 輸出不及格人數(shù)及不及格的學(xué)生名單(5> 根據(jù)平均成績(jī)將成績(jī)表按由高到低的次序排列，統(tǒng)計(jì)每名學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為同一名(6> 成績(jī)表保存在文件中 , 可以從文件讀取數(shù)據(jù)。測(cè)試數(shù)據(jù)：學(xué)生可以根據(jù)自己班級(jí)的考試成績(jī)單，任意截取一部分做為測(cè)試數(shù)據(jù)提高要求：成績(jī)表用鏈?zhǔn)浇Y(jié)構(gòu)表示，實(shí)現(xiàn)上述全部要求。一元多項(xiàng)式簡(jiǎn)單計(jì)算問(wèn)題描述：設(shè)計(jì)一個(gè)簡(jiǎn)單一元多項(xiàng)式計(jì)算器?；疽螅?1>輸入并建立多項(xiàng)式；(2>輸出多項(xiàng)式；(3>兩個(gè)多項(xiàng)式相加，輸出結(jié)果多項(xiàng)式；個(gè)人資料整理 僅限學(xué)習(xí)使用(4> 兩個(gè)多項(xiàng)式相減，輸出結(jié)果多項(xiàng)式。測(cè)試數(shù)據(jù)：可任意選取兩個(gè)一元多項(xiàng)式，可以是一般的多項(xiàng)式，也可以是稀疏多項(xiàng)式。提高要求：可以根據(jù)輸入變量的值，計(jì)算出多項(xiàng)式的結(jié)果，且算法的效率高。舞伴問(wèn)題問(wèn)題描述：一班有 m個(gè)女生、n個(gè)男生(m不等于n>, 舉辦一場(chǎng)舞會(huì) . 男女生分別編號(hào)坐在舞池兩邊的椅子上基本要求：輸入男、女學(xué)生的姓名、性別，由程序自動(dòng)為男女生編號(hào)，可以順序編號(hào)，也可以隨機(jī)編號(hào)，輸出測(cè)試數(shù)據(jù)：分別選擇男生多于女生、女生多于男生、男女生相等的三組測(cè)試數(shù)據(jù)提高要求：計(jì)算出任意一位男生 (編號(hào)為X>和任意一位女生 (編號(hào)為Y>,在第K曲配對(duì)跳舞的情況。文學(xué)研究助手<*）問(wèn)題描述：文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文基本要求：英文小說(shuō)存于一個(gè)文本文件中，待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次測(cè)試數(shù)據(jù)：以你的C/C++/JAVA源程序模擬英文小說(shuō)，相應(yīng)語(yǔ)言的保留字集作為待統(tǒng)計(jì)的詞匯集。哈希表的設(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ù)據(jù)。測(cè)試數(shù)據(jù)：取某個(gè)單位電話號(hào)碼簿中的 30個(gè)記錄。提高要求：將電話號(hào)碼薄以文件形式保存到盤上，能夠按用戶名和電話號(hào)碼兩種形式建立哈希表并實(shí)現(xiàn)插入、注意事項(xiàng)：不能用類庫(kù)中的類完成題目管道鋪設(shè)施工的最佳方案<*）問(wèn)題描述:需要在某個(gè)城市的 n個(gè)小區(qū)鋪設(shè)管道，則在這 n個(gè)小區(qū)之間鋪設(shè) n-1條管道即可，假設(shè)任意兩個(gè)居民基本要求：輸入表示小區(qū)間關(guān)系的圖及每條管道的權(quán)值，選擇出 n-1條管道,使總投資最小。圖的信息輸入一次測(cè)試用例：任意選擇一個(gè)圖，模擬小區(qū)間可能鋪設(shè)的管道及費(fèi)用。提高要求：顯示原始圖及選擇 n-1條管道后的圖。安排教案計(jì)劃<**）問(wèn)題描述：大學(xué)的每個(gè)專業(yè)都要制定教案計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩個(gè)學(xué)期，每的，可以有任意多門，也可以沒(méi)有。每門課程恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教案計(jì)劃編制程序?；疽螅狠斎?yún)?shù)包括學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課程的課程號(hào)、學(xué)分和直接先修課的課程號(hào)；允計(jì)劃輸出到用戶指定的文件中。教案計(jì)劃的表格格式自行設(shè)定

,

可以從鍵盤讀取數(shù)據(jù)也可以從文件讀取數(shù)據(jù)

,

結(jié)果測(cè)試數(shù)據(jù)：學(xué)期總數(shù)為

6，學(xué)分上限為

10，該專業(yè)共開設(shè)

12門。以

08級(jí)某專業(yè)必修課與選修課為例，選擇

1提高要求：產(chǎn)生多種不同的方案，并使方案之間的差異盡可能地大。計(jì)算表達(dá)式的值(**>問(wèn)題描述：對(duì)于給定的一個(gè)表達(dá)式，表達(dá)式中可以包括常數(shù)、算術(shù)運(yùn)行符 <“+”、“-”、“*”、“/”）和括基本要求：從鍵盤輸入一個(gè)正確的中綴表達(dá)式，將中綴表達(dá)式轉(zhuǎn)換為對(duì)應(yīng)的后綴表達(dá)式，計(jì)算后綴表達(dá)式的值測(cè)試數(shù)據(jù)：任意選取一個(gè)符合題目要求的表達(dá)式。個(gè)人資料整理 僅限學(xué)習(xí)使用提高要求：<1）對(duì)于表達(dá)式中的簡(jiǎn)單錯(cuò)誤，能夠給出提示；<2）不僅提示錯(cuò)誤，也能給出錯(cuò)誤信息<3）表達(dá)式中可以包括單個(gè)字母表示的變量<4）能夠處理多種操作符<5）實(shí)現(xiàn)包含簡(jiǎn)單運(yùn)算的計(jì)算器<6）實(shí)現(xiàn)一個(gè)包含簡(jiǎn)單運(yùn)算和函數(shù)運(yùn)算的計(jì)算器設(shè)計(jì)Huffman編碼器與解碼器<**）問(wèn)題描述：利用哈夫曼編碼進(jìn)行信息通訊可以大大提高信道的利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個(gè)哈夫曼碼的編 /譯碼系統(tǒng)。基本要求：根據(jù)某字符文件統(tǒng)計(jì)字符出現(xiàn)頻度，構(gòu)造 Huffman樹，編制 Huffman編碼，并將給定字符文件編碼測(cè)試數(shù)據(jù)：英文文件。銀行業(yè)務(wù)模擬<**）問(wèn)題描述：設(shè)銀行有四個(gè)服務(wù)窗口，一個(gè)等待隊(duì)列 , 每個(gè)窗口均可以辦理存款、取款、掛失、還貸業(yè)務(wù)，每種時(shí),處理等候客戶中排在最前面的客戶的業(yè)務(wù)。寫一個(gè)上述銀行業(yè)務(wù)的模擬系統(tǒng) ,通過(guò)模擬方法求出客戶在銀行內(nèi)逗基本要求：每個(gè)客戶到達(dá)銀行的時(shí)間和需要辦理的業(yè)務(wù)隨機(jī)產(chǎn)生，輸出一天客戶在銀行的平均逗留時(shí)間和每個(gè)測(cè)試數(shù)據(jù)：營(yíng)業(yè)時(shí)間為 8小時(shí)，其他模擬量自行設(shè)定。11. 判斷給出的代數(shù)系統(tǒng)是否是群 <**）問(wèn)題描述：給出含有 n個(gè)元素的代數(shù)系統(tǒng)的運(yùn)算表，設(shè)計(jì)一個(gè)簡(jiǎn)單的程序，判斷給出的代數(shù)系統(tǒng)是否是群。基本要求：給出一個(gè)代數(shù)系統(tǒng) <G,*>，其中：G={1，2，，n}，*運(yùn)算由運(yùn)算表矩陣給出，要判斷：<1）<G,*>是否為半群；<2）<G，*>是否為含幺半群；<3）<G，*>是否為群；(4>原始數(shù)據(jù)和結(jié)果數(shù)據(jù)要保存到文件中。實(shí)驗(yàn)原理：對(duì)于代數(shù)系統(tǒng) <G，*>，若*運(yùn)算是可結(jié)合的，則 <G，*>是半群。顯然，這一點(diǎn)與上一個(gè)實(shí)驗(yàn)中判斷*>是群。測(cè)試數(shù)據(jù)：學(xué)生可以選取 n個(gè)自然數(shù)或 n個(gè)字母做為測(cè)試數(shù)據(jù)提高要求：構(gòu)造以運(yùn)算表形式判斷給出的代數(shù)系統(tǒng)是否是群的通用算法并實(shí)現(xiàn)之。真值表的設(shè)計(jì)與實(shí)現(xiàn)<**）問(wèn)題描述：對(duì)給出的任意一個(gè)合式公式 <不超過(guò)四個(gè)命題變?cè)?，?C語(yǔ)言的程序編程表示出來(lái)，并且能夠計(jì)算基本要求：<1）已知命題 p和q的真值，求出它們的合取、析取、蘊(yùn)涵和等價(jià)的真值；<2）表示出合式公式；<3）給出任意一個(gè)合式公式 <不超過(guò)四個(gè)命題變?cè)O(shè)計(jì)程序把它表示出來(lái)，并且能夠計(jì)算它在各組真值個(gè)人資料整理 僅限學(xué)習(xí)使用提高要求：構(gòu)造任意合式公式的真值表程序源代碼的相似性<***）問(wèn) 題描 述 ： 對(duì) 于

兩 個(gè)

C++

語(yǔ) 言 的 源 程 序

代 碼 ， 用 哈 希 表 的 方 法 分

別 統(tǒng)基本要求：建立

C++語(yǔ)言關(guān)鍵字的哈希表，統(tǒng)計(jì)在每個(gè)源程序中

C++關(guān)鍵字出現(xiàn)的頻度

,

得到兩個(gè)向量

X1和

X2例

如關(guān)鍵字VoidIntForCharifelsewhiledo breakclass程

序

1

關(guān)

鍵

字

頻

度

43

0程 序

2

關(guān) 鍵

字 頻 度

4

2

0X1=[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(

∑(xi1-xi2>2>，當(dāng)

X1=X2時(shí)，s=0,反映出可能是同一個(gè)程序；

s值越大測(cè) 試

數(shù)

據(jù)

:

選 擇

若 干 組

編 譯

和 運(yùn)

行 都 無(wú)

誤 的

C++

程

序

，提高要求：建立源代碼用戶標(biāo)識(shí)符表，比較兩個(gè)源代碼用戶標(biāo)識(shí)符出現(xiàn)的頻度，綜合關(guān)鍵字頻度和用戶標(biāo)識(shí)符頻小型文本編輯器<***）問(wèn)題描述：設(shè)計(jì)一個(gè)行編輯程序，使其具有通常行編輯器 (如Vi、Edlin>應(yīng)具備的基本功能。基本要求：編輯器應(yīng)具備對(duì)文本文件的查找、插人、刪除、修改、字符串替換、統(tǒng)計(jì)字?jǐn)?shù)，統(tǒng)計(jì)行數(shù)等功能，法網(wǎng)絡(luò)教案平臺(tái)上提供的 edlin、Vi的命令集。測(cè)試數(shù)據(jù)：任一文本文件。提高要求：１ .可以支持“*”、“?”等通配符；２.支持復(fù)制、粘貼等功能支持多文檔同時(shí)編輯；提示：可以考慮用雙向鏈表實(shí)現(xiàn)，每一結(jié)點(diǎn)表示一行字符，注意每行字符不能超過(guò) 255。小型英漢詞典<***）問(wèn)題描述：設(shè)計(jì)一個(gè)英漢詞典，支持 Member的查找、插入、刪除操作。基 本 要 求 ： 實(shí) 現(xiàn) 字 典Tree、散列表等，任選一種方法實(shí)現(xiàn)字典的操作，查找單詞、插入單詞 <插入時(shí)，先查找，找不到插入，找到提示用測(cè)試數(shù)據(jù)：任一英文單詞。提高要求：選用兩種以上的方法實(shí)現(xiàn)字典的操作，并比較不同實(shí)現(xiàn)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。提示：字典可以自己建立，但必須按字母 a~z建立26個(gè)文件，建議從網(wǎng)上下載，文件類型為 txt。關(guān)系的計(jì)算與判斷問(wèn)題<***）問(wèn)題描述：設(shè)計(jì)一個(gè)程序，求出給定集合上所有不同的等價(jià)關(guān)系和偏序關(guān)系，并且判斷給定集合上的關(guān)系是否基本要求：(1>輸入集合的元素首先求出給定集合上所有不同的劃分，(2> 求給定集合上所有不同的等價(jià)關(guān)系；個(gè)人資料整理 僅限學(xué)習(xí)使用(3>求給定集合上所有不同的偏序關(guān)系；(4>判斷給定集合上的關(guān)系是否為等價(jià)和偏序關(guān)系；(5>原始數(shù)據(jù)和結(jié)果數(shù)據(jù)要保存到文件中。測(cè)試數(shù)據(jù)：分別選擇自然數(shù)和字母作為集合中元素，用這兩種數(shù)據(jù)測(cè)試提高要求：設(shè)計(jì)求給定集合上關(guān)系的自反閉包、對(duì)稱閉包，以及用 Warshall 算法求傳遞閉包的程序。Hash函數(shù)的構(gòu)造<***）問(wèn)題描述：類Hénon系統(tǒng)方程為：其中參數(shù)xn [-0.95,1.2], a=1.4,b=0.3,w [0.2,1.3] 范圍時(shí)，系統(tǒng)是混沌的，設(shè)計(jì)基于上述混沌系統(tǒng)的 Hash函數(shù)構(gòu)基本要求：<1）設(shè)計(jì)構(gòu)造 Hash函數(shù)的算法；<2）編程實(shí)現(xiàn)；<3）驗(yàn)證其性質(zhì)。提高要求：構(gòu)造基于 Lorenz系統(tǒng)的Hash函數(shù)加密系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)<***）基于Lorenz系統(tǒng)的密碼算法的設(shè)計(jì)與實(shí)現(xiàn)問(wèn)題描述：設(shè)計(jì)用基于類Hénon系統(tǒng)生成的混沌序列加密文件并用程序?qū)崿F(xiàn)基本要求：<1）求出混沌序列；<2）編程實(shí)現(xiàn)；<3）原始數(shù)據(jù)和結(jié)果數(shù)據(jù)要保存到文件中。提高要求：構(gòu)造基于 Lorenz系統(tǒng)的加密程序地圖著色<***）問(wèn)題描述：對(duì)中國(guó)地圖進(jìn)行著色，兩個(gè)共同邊界的省份染不同的顏色，當(dāng)可以選擇 7、6、5、4種不同的顏色的基本要求：<1）建立以省為節(jié)點(diǎn)，以是否相鄰為邊的一個(gè)無(wú)向圖；<2）從顏色模板中選取一個(gè)顏色賦值給每個(gè)節(jié)點(diǎn)；(3> 相鄰節(jié)點(diǎn)顏色不能相同；測(cè)試數(shù)據(jù)：學(xué)生可以自己選取顏色模板做為測(cè)試數(shù)據(jù)；分別需要測(cè)試 7、6、5、4種不同的顏色。提高要求：當(dāng)用 4種顏色染色時(shí)，給出不同的染色方案，計(jì)算染色的效率。漫游中國(guó)<***）問(wèn)題描述：從任一省會(huì)出發(fā)，走遍所有省會(huì)，給出某種評(píng)價(jià)指標(biāo)，然后根據(jù)該指標(biāo)由計(jì)算機(jī)選擇最優(yōu)的漫游路基本要求：<1）建立以省會(huì)為節(jié)點(diǎn)，以是否相鄰為邊的一個(gè)無(wú)向賦權(quán)圖；個(gè)人資料整理 僅限學(xué)習(xí)使用<2）只能選擇陸路和水路交通；(3> 每條邊的權(quán)重為兩地之間的距離，以公里為單位；測(cè)試數(shù)據(jù)：學(xué)生可以自己選取評(píng)價(jià)指標(biāo)，如費(fèi)用最少、時(shí)間最短等等。提高要求：不同的出發(fā)點(diǎn)結(jié)果是否一致，并討論多目標(biāo)模型。21~23為附加題，有能力完成的學(xué)生可以選擇。這里以big_porsche.ply 為例解讀其格式：1、文件的頭部：參看圖1，文件的頭兩行構(gòu)成文件的頭部，其中第一行說(shuō)明文件有多少個(gè)頂點(diǎn) <比如big_porsche.ply 共有“eleme2、文件的體：2.1 點(diǎn)表部分文件頭部緊接的下面就是文件的頂點(diǎn)部分，按照頭部說(shuō)明，應(yīng)該有 5247行頂點(diǎn)數(shù)據(jù)，圖 2中只是顯示了 10行。圖2紅色方框內(nèi)是10行頂點(diǎn)數(shù)據(jù)2.2 面表部分緊接這頂點(diǎn)數(shù)據(jù)的是

10474

行面表。每個(gè)行表示一個(gè)面，如果這個(gè)行的第一個(gè)值是

3，表示此面為三角形，后號(hào)頂點(diǎn)<即

2.1

中點(diǎn)表的第二個(gè)頂點(diǎn)）、第三個(gè)頂點(diǎn)為

2號(hào)頂點(diǎn)<即

2.1

點(diǎn)表中的第三個(gè)頂點(diǎn)）。個(gè)人資料整理 僅限學(xué)習(xí)使用圖3紅色方框內(nèi)是9行面表數(shù)據(jù)3、繪制結(jié)果由這樣一個(gè)文件就能繪制出一個(gè)三維的車的模型，如下圖所示：1）首先對(duì)整個(gè)點(diǎn)表數(shù)據(jù)按照X坐標(biāo)從小到大排序。2）定義一個(gè)值lengthX，從上到下的切分X值段，每段的長(zhǎng)度為lengthX。3）在每個(gè)lengthX行數(shù)據(jù)內(nèi)，按Y值進(jìn)行排序。4）在每個(gè)lengthX內(nèi)再切分出lengthY。5）在lengthY內(nèi)按Z值排序。兩點(diǎn)需要注意的：⑴整個(gè)排序的過(guò)程中每個(gè)點(diǎn)<即點(diǎn)表的一行數(shù)據(jù)）是一個(gè)整體。⑵點(diǎn)的編號(hào)改變，請(qǐng)同時(shí)維護(hù)面表的一致性<即維護(hù)面表和點(diǎn)表初始時(shí)的對(duì)應(yīng)關(guān)系）。22、對(duì)大的點(diǎn)表序列排序，請(qǐng)?jiān)O(shè)計(jì)基于外存的排序算法<即即使對(duì)大的文件排序，占用的內(nèi)存也非常小，比如對(duì)1G23、完成對(duì)ply文件的壓縮(***>定義點(diǎn)表中兩個(gè)頂點(diǎn)<x1,y1,z1）和(x2,y2,z2>之間的距離定義為：對(duì)ply 文件