數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)計(jì)劃書級(jí)

指導(dǎo)教師分配情況:

一、教學(xué)目的與要求:數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)的目的是使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性,合理的組織數(shù)據(jù)并能綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)與算法基本知識(shí)和程序設(shè)計(jì)基本知識(shí)解決實(shí)際問(wèn)題,二、主要階段、內(nèi)容、時(shí)間及地點(diǎn)安排(以天為單位計(jì):

容,學(xué)生選擇題目,明確問(wèn)題描述和要求,查閱資料。(1

各班長(zhǎng)或?qū)W習(xí)委員將本班的選題表交給輔導(dǎo)教師,一人一題,每道題的選擇人數(shù)

人,第一天課程設(shè)計(jì)結(jié)束后,每名學(xué)生都要確定題目。

階段:明確題目要求、確定數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)算法,編寫程序、調(diào)試程序、測(cè)

第三周,完成剩余任務(wù)的編碼與調(diào)試,準(zhǔn)備足夠的測(cè)試數(shù)據(jù),對(duì)軟件進(jìn)行測(cè)試與

階段:完成設(shè)計(jì)任務(wù),準(zhǔn)備驗(yàn)收、答辯(1

階段:答辯(上機(jī)演示,回答教師提問(wèn)(1

階段:撰寫課程設(shè)計(jì)報(bào)告(2

計(jì)算機(jī)科學(xué)與技術(shù):

大節(jié)、下午(驗(yàn)收第三周上午、下午上午、下午下午(驗(yàn)收第三周上午、下午上午下午上午(驗(yàn)收

三、課程設(shè)計(jì)題目及具體要求:

績(jī)(高等數(shù)學(xué)、英語(yǔ)、物理,設(shè)計(jì)一個(gè)簡(jiǎn)單的成績(jī)管理程序。

建立成績(jī)表,能夠插入、刪除、修改學(xué)生的成績(jī)記錄;

按任一單科成績(jī)排序;

計(jì)算每名學(xué)生的平均成績(jī);

統(tǒng)計(jì)任一單科成績(jī)不及格的學(xué)生人數(shù),

根據(jù)平均成績(jī)將成績(jī)表按由高到低的次序排列,統(tǒng)計(jì)每名學(xué)生在考試中獲得的名次,分?jǐn)?shù)相同的為同一名次,按名次輸出成績(jī)表。

成績(jī)表保存在文件中,

測(cè)試數(shù)據(jù):學(xué)生可以根據(jù)自己班級(jí)的考試成績(jī)單,任意截取一部分做為測(cè)試數(shù)據(jù)提高要求:成績(jī)表用鏈?zhǔn)浇Y(jié)構(gòu)表示,實(shí)現(xiàn)上述全部要求。

用順序結(jié)構(gòu)表示成績(jī)單,完成任務(wù)(1~(6,成績(jī)?yōu)榧案?

用鏈表表示成績(jī)單,完成任務(wù)(1~(6,且軟件容錯(cuò)能力強(qiáng),成績(jī)?yōu)橹械?/p>

輸入并建立多項(xiàng)式;

兩個(gè)多項(xiàng)式相加,輸出結(jié)果多項(xiàng)式;

兩個(gè)多項(xiàng)式相減,輸出結(jié)果多項(xiàng)式。測(cè)試數(shù)據(jù):可任意選取兩個(gè)一元多項(xiàng)式,可以是一般的多項(xiàng)式,也可以是稀疏多提高要求:可以根據(jù)輸入變量的值,計(jì)算出多項(xiàng)式的結(jié)果,且算法的效率高。

用鏈表表示多項(xiàng)式,完成任務(wù)(1~(4,成績(jī)?yōu)榧案?/p>

的要求,同時(shí)能夠輸入變量的值,計(jì)算出多項(xiàng)式的結(jié)果,成績(jī)中等,

別編號(hào)坐在舞池兩邊的椅子上,每曲開始時(shí),

本曲沒成功配對(duì)者坐著等待下一曲找舞伴,設(shè)計(jì)一個(gè)程序模擬舞伴配對(duì)過(guò)程?；疽?輸入男、女學(xué)生的姓名、性別,由程序自動(dòng)為男女生編號(hào),可以順序編號(hào),也可以隨機(jī)編號(hào),輸出每曲配對(duì)情況(包括男、女生的姓名、性別和編號(hào)。原提高要求:計(jì)算出任意一位男生(編號(hào)為

用隊(duì)列表示男、女學(xué)生,能夠從文件中讀取數(shù)據(jù),文件中至少包括三組測(cè)試到文件中。完成上述任務(wù),成績(jī)?yōu)榧案瘛?/p>

在完成考核要求(1

支舞曲的配對(duì)情況,能夠處理異4.文學(xué)研究助手(*置。試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng),稱為“文學(xué)研究助手”?；疽?英文小說(shuō)存于一個(gè)文本文件中,待統(tǒng)計(jì)的詞匯集合要一次輸入完畢,鍵盤輸入,程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào),格式自行

提高要求:包含是否區(qū)別大、小寫兩種匹配模式,且讓用戶選擇。

源程序模擬英文小說(shuō),相應(yīng)語(yǔ)言的保留字集作為

用線性結(jié)構(gòu)表示文本文件和待統(tǒng)計(jì)的單詞,動(dòng)態(tài)分配內(nèi)存,完成基本要求的

在完成基本要求的基礎(chǔ)上,完成提高要求,且用戶界面友好,能夠處理異常,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)度,哈希表保存到文件中,并能從文件中讀取數(shù)據(jù)。

將電話號(hào)碼薄以文件形式保存到盤上,能夠按用戶名和電話號(hào)碼兩種形式建

對(duì)于相同的哈希函數(shù),采用兩種或兩種以上的處理沖突的方法,如線性探測(cè)法和拉鏈法,比較不同的處理沖突的方法平均查找長(zhǎng)度的變化。測(cè)試時(shí),采用同一組測(cè)試數(shù)據(jù),分別用不同的方法處理沖突,記錄并輸出各自的平均查找長(zhǎng)度。

能夠從鍵盤和文件輸入原始數(shù)據(jù),能夠把變化的哈希表重新寫回到文件中,同時(shí)完成其它的基本要求,成績(jī)?yōu)橹械取?/p>

達(dá)到提高要求中的(1

或(2,或者同時(shí)達(dá)到(1

6.管道鋪設(shè)施工的最佳方案(*

個(gè)小區(qū)鋪設(shè)管道,則在這

假設(shè)任意兩個(gè)居民區(qū)之間都可以架設(shè)管道,但由于地理環(huán)境的不同,所需經(jīng)費(fèi)不基本要求:輸入表示小區(qū)間關(guān)系的圖及每條管道的權(quán)值,選擇出

總投資最小。圖的信息輸入一次后,

保存到文件中,

測(cè)試用例:任意選擇一個(gè)圖,模擬小區(qū)間可能鋪設(shè)的管道及費(fèi)用。

注意,本題要求能夠從鍵盤和文件中讀取原始圖的數(shù)據(jù),且選擇出的最佳方案也要保存到文件中,如果不能達(dá)到這個(gè)要求,成績(jī)?yōu)椴患案?。完成基本要?成績(jī)

達(dá)到提高要求中的(1

或(2,或者同時(shí)達(dá)到(1

實(shí)現(xiàn)圖形用戶界面,實(shí)現(xiàn)友好的圖形用戶界面,成績(jī)?yōu)榱己?.安排教學(xué)計(jì)劃(**年限,每學(xué)年含兩個(gè)學(xué)期,每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的些先修課程是確定的,可以有任意多門,也可以沒有。每門課程恰好占一個(gè)學(xué)期。試基本要求:輸入?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ì)劃表(如每個(gè)學(xué)期所開設(shè)的課程的課程號(hào)及學(xué)分,同時(shí)將教學(xué)計(jì)劃輸出到用戶指定的文件中。教學(xué)計(jì)劃的表格格式自行設(shè)定,

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

必修課與選修課為例,選擇

門課程及相應(yīng)學(xué)分,制定一個(gè)表明各門課程先后約束提高要求:產(chǎn)生多種不同的方案,并使方案之間的差異盡可能地大。

達(dá)到基本要求,成績(jī)?yōu)榱己?如果不能把結(jié)果保存到文件中,成績(jī)?yōu)椴患案瘛?/p>

在達(dá)到基本要求的基礎(chǔ)上,產(chǎn)生

種以上的解決方案,且用戶界面友好,成績(jī)8.計(jì)算表達(dá)式的值(**問(wèn)題描述:對(duì)于給定的一個(gè)表達(dá)式,表達(dá)式中可以包括常數(shù)、算術(shù)運(yùn)行符(“+”、“-”、“*”、“/”和括號(hào),編寫程序計(jì)算表達(dá)式的值?；疽?從鍵盤輸入一個(gè)正確的中綴表達(dá)式,將中綴表達(dá)式轉(zhuǎn)換為對(duì)應(yīng)的后綴

對(duì)于表達(dá)式中的簡(jiǎn)單錯(cuò)誤,能夠給出提示;

不僅提示錯(cuò)誤,也能給出錯(cuò)誤信息

表達(dá)式中的數(shù)據(jù)可以是整數(shù)或小數(shù),達(dá)到基本要求,成績(jī)?yōu)榱己谩Ｈ绻麅H能處理個(gè)位數(shù),成績(jī)?yōu)榧案?如果僅能處理整數(shù),成績(jī)?yōu)橹械取?/p>

在達(dá)到基本要求的基礎(chǔ)之上,如果達(dá)到提高要求的

問(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è)哈夫曼碼基本要求:根據(jù)某字符文件統(tǒng)計(jì)字符出現(xiàn)頻度,構(gòu)造

編碼,并將給定字符文件編碼,生成編碼文件;再將給定編碼文件解碼,生成字符文

編碼,產(chǎn)生兩種以上的編碼方案,對(duì)同一組測(cè)試數(shù)據(jù),用不同的編碼方案編碼,從文件長(zhǎng)度、算法復(fù)雜度等方面進(jìn)行比較。

對(duì)原文件編碼后,保存到新建文件中,將原文件與新文件比較,如果新文件長(zhǎng)度大于原文件,則編碼失敗,成績(jī)不及格。如果達(dá)到題目的基本要求,成績(jī)?yōu)榱己谩?/p>

達(dá)到提高要求,成績(jī)可以為優(yōu)秀。10.銀行業(yè)務(wù)模擬(**問(wèn)題描述:設(shè)銀行有四個(gè)服務(wù)窗口,一個(gè)等待隊(duì)列,

取款、掛失、還貸業(yè)務(wù),每種業(yè)務(wù)所需的服務(wù)時(shí)間不同,客戶到達(dá)銀行后,先到打號(hào)機(jī)上打號(hào),號(hào)票上包括到達(dá)時(shí)間、編號(hào)和需要辦理的業(yè)務(wù),然后在銀行內(nèi)等候,

基本要求:每個(gè)客戶到達(dá)銀行的時(shí)間和需要辦理的業(yè)務(wù)隨機(jī)產(chǎn)生,輸出一天客戶提高要求:設(shè)計(jì)圖形用戶界面,模擬中國(guó)銀行真實(shí)的打號(hào)機(jī)操作界面,當(dāng)用戶選

數(shù)據(jù)結(jié)構(gòu)選擇合理,達(dá)到題目的基本要求,成績(jī)?yōu)榱己谩?/p>

達(dá)到提高要求,用戶界面友好,能夠處理異常,成績(jī)可以為優(yōu)秀11.程序源代碼的相似性(***

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)

i1-x

反映出可能是同一個(gè)程序;s

值越大,則兩個(gè)程序的差別可能也越大,分析計(jì)算結(jié)果,

提高要求:建立源代碼用戶標(biāo)識(shí)符表,比較兩個(gè)源代碼用戶標(biāo)識(shí)符出現(xiàn)的頻度,考核要求:從源代碼中分解單詞,判斷是否為關(guān)鍵字要采用效率高的方法,設(shè)計(jì)的哈希函數(shù)盡量產(chǎn)生較少的沖突,任選處理沖突的方法,選擇的測(cè)試數(shù)據(jù)要盡量包含多種情況,能夠處理異常,達(dá)到這些要求成績(jī)?yōu)閮?yōu)秀,否則成績(jī)向下浮動(dòng)。鼓勵(lì)按關(guān)鍵字和用戶標(biāo)識(shí)符判斷相似性,鼓勵(lì)設(shè)計(jì)圖形用戶界面。12.小型文本編輯器(***問(wèn)題描述:設(shè)計(jì)一個(gè)行編輯程序,使其具有通常行編輯器(如

換、統(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ì)文本的編輯。具體的編輯命令,

edlin、Vi

”等通配符;

支持多文檔同時(shí)編輯;

界面可以是菜單形式,完成基本要求,成績(jī)可為優(yōu)秀,如果只實(shí)現(xiàn)了基本要求

設(shè)計(jì)界面,但其中的功能實(shí)現(xiàn)不能用類庫(kù)中的類。提示:可以考慮用雙向鏈表實(shí)現(xiàn),每一結(jié)點(diǎn)表示一行字符,注意每行字符不能超

13.小型英漢詞典(***問(wèn)題描述:設(shè)計(jì)一個(gè)英漢詞典,支持

基本要求:實(shí)現(xiàn)字典的常用方法有:有序線性表(用二分檢索實(shí)現(xiàn)、A

Tree、散列表等,任選一種方法實(shí)現(xiàn)字典的操作,查找單詞、插入單詞(插入時(shí),先查找,找不到插入,找到提示用戶、刪除單詞(刪除時(shí),先查找,找到刪除,找不到提示用戶。字典是按字母順序排列的,不能用順序查找,插入或刪提高要求:選用兩種以上的方法實(shí)現(xiàn)字典的操作,要比較不同實(shí)現(xiàn)算法的時(shí)間復(fù)

如果采用線性結(jié)構(gòu)且無(wú)序,成績(jī)?yōu)椴患案瘛?/p>

選擇合適的數(shù)據(jù)結(jié)構(gòu),達(dá)到了基本要求,成績(jī)?yōu)閮?yōu)秀。

提示:字典可以自己建立,但必須按字母

個(gè)文件,建議從網(wǎng)上下載,

問(wèn)題描述:對(duì)中國(guó)地圖進(jìn)行著色,兩個(gè)共同邊界的省份染不同的顏色,當(dāng)可以選

種不同的顏色的情況下,由程序自動(dòng)進(jìn)行處理,給出具體的染色方

建立以省為節(jié)點(diǎn),以是否相鄰為邊的一個(gè)無(wú)向圖;

從顏色模板中選取一個(gè)顏色賦值給每個(gè)節(jié)點(diǎn);

相鄰節(jié)點(diǎn)顏色不能相同;測(cè)試數(shù)據(jù):學(xué)生可以自己選取顏色模板做為測(cè)試數(shù)據(jù);分別需要測(cè)試

種顏色染色時(shí),給出不同的染色方案,計(jì)算染色的效率。

可以不實(shí)際畫圖,用數(shù)字或文字表示顏色,給出著色方案,達(dá)到基本要求,成

問(wèn)題描述:從任一省會(huì)出發(fā),走遍所有省會(huì),給出某種評(píng)價(jià)指標(biāo),然后根據(jù)該指標(biāo)

建立以省會(huì)為節(jié)點(diǎn),以是否相鄰為邊的一個(gè)無(wú)向賦權(quán)圖;

只能選擇陸路和水路交通;

每條邊的權(quán)重為兩地之間的距離,以公里為單位;測(cè)試數(shù)據(jù):學(xué)生可以自己選取評(píng)價(jià)指標(biāo),如費(fèi)用最少、時(shí)間最短等等。提高要求:不同的出發(fā)點(diǎn)結(jié)果是否一致,并討論多目標(biāo)模型。

不要求畫圖,用數(shù)字或文字表示省會(huì),給出漫游路線,達(dá)到基本要求,成績(jī)可

為附加題,有能力完成的學(xué)生可以選擇。

為例解析其格式:

1,文件的頭兩行構(gòu)成文件的頭部,其中第一行說(shuō)明文件有多少個(gè)頂點(diǎn)

個(gè)頂點(diǎn);第二行表示文件有多少個(gè)面(比如比如

文件頭部緊接的下面就是文件的頂點(diǎn)部分,按照頭部說(shuō)明,應(yīng)該有

x、y、z

21、表排序并維護(hù)面表的索引的一致性（***）

lengthY。

的內(nèi)存）(***