09電子信息2023年《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)題目及要求

09電子信息2024年《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)題目及要求2024年《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)題目及基本要求如下：

設(shè)計(jì)要求：

1)同學(xué)必需認(rèn)真閱讀《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)方案，仔細(xì)主動(dòng)完成課設(shè)

的要求。有問(wèn)題準(zhǔn)時(shí)主動(dòng)通過(guò)各種方式與老師聯(lián)系溝通。

2)同學(xué)要發(fā)揮自主學(xué)習(xí)的力量，充分利用時(shí)間，支配好課設(shè)的時(shí)間計(jì)

劃，并在課設(shè)過(guò)程中不斷檢測(cè)自己的方案完成狀況，準(zhǔn)時(shí)的向老師

匯報(bào)。

3)課程設(shè)計(jì)根據(jù)教學(xué)要求需要兩周時(shí)間完成，兩周中每天（按每周5

天）至少要上3-4小時(shí)的機(jī)來(lái)調(diào)試C/C++語(yǔ)言/JAVA設(shè)計(jì)的程序。

4)以下各題至少需完成2題。

5)設(shè)計(jì)期間，要求嚴(yán)格遵守學(xué)校規(guī)章制度和試驗(yàn)室管理制度。

6)按指定時(shí)間上機(jī)，聽(tīng)從指導(dǎo)老師和試驗(yàn)室其他老師的支配。

7)上機(jī)前，應(yīng)編寫(xiě)相應(yīng)的程序，禁止無(wú)預(yù)備的上機(jī)。

每次上機(jī)，由老師點(diǎn)名，與最終演示以及設(shè)計(jì)報(bào)告一起，構(gòu)成最終成果。第一次上機(jī)，填寫(xiě)老師手中的選題表。非特別狀況，不得中間換題。選題盡可能不要集中在某些題上，最終給分會(huì)結(jié)合題目的難度進(jìn)行平衡。

上交相關(guān)內(nèi)容要求

1．上交源程序：同學(xué)根據(jù)課程設(shè)計(jì)的詳細(xì)要求所開(kāi)發(fā)的全部源程序（應(yīng)當(dāng)放到一個(gè)文件夾中）；

2．上交程序的說(shuō)明文件：（保存在.txt中）在說(shuō)明文檔中應(yīng)當(dāng)寫(xiě)明上交程序所在的名目，上交程序的主程序文件名，假如需要安裝，要有程序的安裝使用說(shuō)明；

3．課程設(shè)計(jì)報(bào)告：（上交紙質(zhì)打印稿，同時(shí)將電子檔保存在word文檔中上交，文件名要求根據(jù)"姓名-學(xué)號(hào)-課程設(shè)計(jì)報(bào)告"起名，如文件名為"張三-001-課程設(shè)計(jì)報(bào)告".doc）根據(jù)課程設(shè)計(jì)的詳細(xì)要求建立的功能模塊，每個(gè)模塊要求根據(jù)如下幾個(gè)內(nèi)容仔細(xì)完成；

其中包括:

a)封面（應(yīng)有標(biāo)題、專(zhuān)業(yè)、班級(jí)、姓名、學(xué)號(hào)和課程設(shè)計(jì)日期）

b)課程設(shè)計(jì)題目

聲明自己選擇的題目

c)按自己選做的題目分章?tīng)?zhēng)論

（居中）標(biāo)題如第**章******

i.問(wèn)題描述

ii.需求分析：以無(wú)歧義的陳述說(shuō)明程序設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)的是程序要做什么？同時(shí)明確規(guī)定：輸入的形式和輸出值的范圍；輸出的形式；程序所能夠達(dá)到的功能；測(cè)試數(shù)據(jù)：包括正確

的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。

iii.概要設(shè)計(jì)：在此說(shuō)明每個(gè)部分的算法設(shè)計(jì)說(shuō)明（可以是描述算法的流程圖），每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明（假如指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫(xiě)出該存儲(chǔ)結(jié)構(gòu)的定義。

iv.具體設(shè)計(jì)：每部分模塊的設(shè)計(jì)，含數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，算法的描述（流程圖或PDL）。各個(gè)算法實(shí)現(xiàn)的源程序，對(duì)每個(gè)題目要有相應(yīng)的源程序（可以是一組源程序，每個(gè)功能模塊采納

不同的函數(shù)實(shí)現(xiàn)）。源程序要根據(jù)寫(xiě)程序的規(guī)章來(lái)編寫(xiě)。要結(jié)構(gòu)清楚，重點(diǎn)函數(shù)的重點(diǎn)變量，

重點(diǎn)功能部分要加上清楚的程序解釋。

v.測(cè)試分析：測(cè)試數(shù)據(jù)、測(cè)試過(guò)程、測(cè)試結(jié)果及評(píng)價(jià)

vi.用戶(hù)使用說(shuō)明：說(shuō)明如何使用你的程序，具體列出每一步操作步驟

vii.本章小結(jié)：總結(jié)可以包括:課程設(shè)計(jì)過(guò)程的收獲、遇到問(wèn)題、遇到問(wèn)題解決問(wèn)題過(guò)程的思索、程序調(diào)試力量的思索、對(duì)數(shù)據(jù)結(jié)構(gòu)這門(mén)課程的思索、在課程設(shè)計(jì)過(guò)程中對(duì)《數(shù)據(jù)結(jié)

構(gòu)》課程的熟悉等內(nèi)容

viii.

個(gè)無(wú)向網(wǎng)。頂點(diǎn)和邊均含有相關(guān)信息。

三、停車(chē)場(chǎng)管理問(wèn)題

設(shè)有一個(gè)可以停放n輛汽車(chē)的狹長(zhǎng)停車(chē)場(chǎng)，它只有一個(gè)大門(mén)可以供車(chē)輛進(jìn)出。車(chē)輛按到達(dá)停車(chē)場(chǎng)時(shí)間的早晚依次從停車(chē)場(chǎng)最里面對(duì)大門(mén)口處停放(最先到達(dá)的第一輛車(chē)放在停車(chē)場(chǎng)的最里面)。假如停車(chē)場(chǎng)已放滿(mǎn)n輛車(chē)，則后來(lái)的車(chē)輛只能在停車(chē)場(chǎng)大門(mén)外的便道上等待，一旦停車(chē)場(chǎng)內(nèi)有車(chē)開(kāi)走，則排在便道上的第一輛車(chē)就進(jìn)入停車(chē)場(chǎng)。停車(chē)場(chǎng)內(nèi)如有某輛車(chē)要開(kāi)走，在它之后進(jìn)入停車(chē)場(chǎng)的車(chē)都必需先退出停車(chē)場(chǎng)為它讓路，待其開(kāi)出停車(chē)場(chǎng)后，這些車(chē)輛再依原來(lái)的次序進(jìn)場(chǎng)。每輛車(chē)在離開(kāi)停車(chē)場(chǎng)時(shí)，都應(yīng)依據(jù)它在停車(chē)場(chǎng)內(nèi)停留的時(shí)間長(zhǎng)短交費(fèi)。假如停留在便道上的車(chē)未進(jìn)停車(chē)場(chǎng)就要離去，允許其離去，不收停車(chē)費(fèi)，并且仍舊保持在便道上等待的車(chē)輛的次序。編制一程序模擬該停車(chē)場(chǎng)的管理。

要求程序輸出每輛車(chē)到達(dá)后的停車(chē)位置(停車(chē)場(chǎng)或便道上)，以及某輛車(chē)離開(kāi)停車(chē)場(chǎng)時(shí)應(yīng)交納的費(fèi)用和它在停車(chē)場(chǎng)內(nèi)停留的時(shí)間。

汽車(chē)的模擬輸入信息格式可以是：(到達(dá)／離去，汽車(chē)牌照號(hào)碼，到達(dá)／離去的時(shí)刻)。例如，(…A?，，1，5)表示1號(hào)牌照車(chē)在5這個(gè)時(shí)刻到達(dá)，而(…D?，，5，20)表示5號(hào)牌照車(chē)在20這個(gè)時(shí)刻離去。整個(gè)程序可以在輸入信息為(…E?，0，0)時(shí)結(jié)束。本題可用棧和隊(duì)列來(lái)實(shí)現(xiàn)。

四、全國(guó)交通詢(xún)問(wèn)模擬

處于對(duì)不同目的的旅客對(duì)交通工具有不同的要求。例如，因公出差的旅客盼望在旅途中的時(shí)間盡可能短，出門(mén)旅游的游客則盼望旅費(fèi)盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個(gè)全國(guó)城市間的交通詢(xún)問(wèn)程序，為旅客供應(yīng)兩種或三種最優(yōu)決策的交通詢(xún)問(wèn)。

（1）供應(yīng)對(duì)城市信息進(jìn)行編輯（如：添加或刪除）的功能。

（2）城市之間有兩種交通工具：火車(chē)和飛機(jī)。供應(yīng)對(duì)列車(chē)時(shí)刻表和飛機(jī)航班進(jìn)行編輯（增設(shè)或刪除）的功能。

（3）供應(yīng)兩種最優(yōu)決策：最快到達(dá)或最省錢(qián)到達(dá)。全程只考慮一種交通工具。

（4）旅途中耗費(fèi)的總時(shí)間應(yīng)當(dāng)包括中轉(zhuǎn)站的等候時(shí)間。

（5）詢(xún)問(wèn)以用戶(hù)和計(jì)算機(jī)的對(duì)話(huà)方式進(jìn)行。由用戶(hù)輸入起始站、終點(diǎn)站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長(zhǎng)時(shí)間才能到達(dá)或者最少需要多少旅費(fèi)才能到達(dá)，并具體說(shuō)明依次于何時(shí)乘坐哪一趟列車(chē)或哪一次班機(jī)到何地。

（1）對(duì)全國(guó)城市交通圖和班車(chē)時(shí)刻表及飛機(jī)航班表的編輯，應(yīng)當(dāng)供應(yīng)文件形式輸入和鍵盤(pán)輸入兩種方式。飛機(jī)航班表的信息應(yīng)包括：起始站的動(dòng)身時(shí)間、終點(diǎn)站的到達(dá)時(shí)間和票價(jià)；列車(chē)時(shí)刻表則需依據(jù)交通圖給出各個(gè)路段的具體信息，例如：對(duì)于從北京到上海的火車(chē)，需給出北京至天津、天津至徐州及徐州至各段的動(dòng)身時(shí)間、到達(dá)時(shí)間和票價(jià)信息。

（2）以鄰接表作交通圖的存儲(chǔ)結(jié)構(gòu)，表示邊的結(jié)點(diǎn)內(nèi)除含有鄰接點(diǎn)的信息外，包括交通工具、路程中消耗的時(shí)間和花費(fèi)以及動(dòng)身和到達(dá)的時(shí)間等多項(xiàng)屬性。

五、壓縮器/解壓器

為了節(jié)約存儲(chǔ)空間，經(jīng)常需要把文本文件采納壓縮編碼的方式儲(chǔ)存。例如：一個(gè)包含1000個(gè)x的字符串和2000個(gè)y的字符串的文本文件在不壓縮時(shí)占用的空間為3002字節(jié)（每個(gè)x或每個(gè)y占用一個(gè)字節(jié)，兩個(gè)字節(jié)用來(lái)表示串的結(jié)尾）。同樣是這個(gè)文件，采納游程長(zhǎng)度編碼（run-lengthcoding），可以存儲(chǔ)為字符串1000x2000y，僅為10個(gè)字母，占用12個(gè)字節(jié)。若采納二進(jìn)制表示游程長(zhǎng)度（1000和2000）可以進(jìn)一步節(jié)省空間。假如每個(gè)游程長(zhǎng)度占用2個(gè)字節(jié)，則可以表示的最大游程長(zhǎng)度為2*pow(16)，這樣，上例中的字符串只需要用8個(gè)字節(jié)來(lái)存儲(chǔ)。當(dāng)要讀取編碼文件時(shí)，需要對(duì)其進(jìn)行解碼。由壓縮器（pressor）對(duì)文件進(jìn)行編碼，由解壓器（depressor）進(jìn)行解碼。

①（1）長(zhǎng)度-游程編碼的壓縮/解壓；+（2）LZW壓縮/解壓（散列）；

②（1）長(zhǎng)度-游程編碼的壓縮/解壓；+（3）霍夫曼編碼壓縮/解壓(霍夫曼樹(shù))

要求選用二種壓縮/解壓策略實(shí)現(xiàn)壓縮/解壓器。輸入的為本文文件（.txt），輸出的為一種自定義的文件（.nz）?？紤]當(dāng)構(gòu)成文本的字符集合為{a,b,c,……,z,0,1,2,…9}時(shí)，請(qǐng)用實(shí)例測(cè)試你的壓縮/解壓器。你的壓縮器會(huì)不會(huì)消失抖動(dòng)？（壓縮后的文本比原來(lái)的還要大）。擴(kuò)充構(gòu)成文本的字符集合以便使它適應(yīng)更一般的狀況。

LZW：由Lempel、Ziv和Welch這三位科學(xué)家所開(kāi)發(fā)的技術(shù)。該方法把文本的字符串映射為編碼，首先，為該文本中全部可能消失的字母分別安排一個(gè)代碼。例如：要壓縮的對(duì)象是aaabbbbbbbaabaaba，由a和b組成。為a安排代碼0,為b安排代碼1。字符串和編碼的關(guān)系被存儲(chǔ)在字典中。

其相應(yīng)的代碼。若輸入文件的下一個(gè)字符為c，則為pc安排下一個(gè)代碼，并插

入字典，這種策略稱(chēng)為L(zhǎng)ZW規(guī)章。相反，在解壓時(shí)，編碼表由壓縮文件重新構(gòu)造，LZW原則使這種重建成為可能。

如上例子，壓縮時(shí)，文件中第一個(gè)在字典中消失的最長(zhǎng)前綴是a,輸出其編碼0,然后為字符串a(chǎn)a安排代碼2，并插入到字典中。余下的字符串在字典中消失的最長(zhǎng)前綴是aa,輸出aa的對(duì)應(yīng)代碼2，同時(shí)為字符串a(chǎn)ab安排代碼3并將其插入到字典中。依次類(lèi)推，由此，輸出0214537

解壓時(shí)，要輸入代碼，然后用代碼所表示的文原來(lái)替換這些代碼。代碼到文本的映射可按下面的方法重建：首先把安排給單一字母的代碼插入到字典中。象前面一樣，字典的入口為key-code對(duì)。然而此時(shí)是依據(jù)給定的代碼（key）去查找相應(yīng)的入口（而不是依據(jù)文本Code）。壓縮文件中的第一個(gè)代碼對(duì)應(yīng)于單一的字母，因此可以由該字母代替。對(duì)于壓縮文件中的其他代碼p,要考慮兩種狀況：1）在字典中；2）不在字典中。

在1）狀況下，找到p對(duì)應(yīng)的文本text(p)輸出。并且，依據(jù)壓縮原理可知，若在壓縮文件中代碼q寫(xiě)在p之前且text(q)是與q對(duì)應(yīng)的文本，則壓縮器會(huì)為文本text(q)（其后緊跟fc(p)，text(p)的第一個(gè)字符）安排一新代碼。因此在字典中插入序偶（下一個(gè)代碼，text(q)fc(p)）。

狀況2）時(shí)，只有在當(dāng)前文本段形如text(q)text(q)fc(q)且text(p)=text(q)fc(q)時(shí)才會(huì)發(fā)生。相應(yīng)的壓縮文件段是qp。在壓縮過(guò)程中，為text(q)fc(q)安排的代碼為p。在解壓過(guò)程中，在用text(q)代替q后，又遇到代碼p。然而，此時(shí)字典中沒(méi)有與p對(duì)應(yīng)的文本。由于這種狀況只在解壓文本段為text(p)text(q)fc(q)時(shí)才發(fā)生，因此可以對(duì)p解碼。當(dāng)遇到一個(gè)沒(méi)有定義代碼文本對(duì)的代碼p時(shí)，p對(duì)應(yīng)的文本為text(q)fc(q)，其中q為p前面的代碼。

如上例子：首先，初始化字典，在其中插入(0,a),(1,b)。壓縮的第一個(gè)代碼為0,則用a代替之。下一個(gè)代碼2未定義，由于前一個(gè)代碼為0，且text(0)=a,fc(0)=a,則

text(2)=text(0)fc(0)=aa。因此用aa代替2,并把(2,aa)插入字典中。下個(gè)代碼1由b來(lái)替換，并把(3,text(2)fc(1))=(3,aab)插入字典中。依次類(lèi)推，得解壓結(jié)果。

霍夫曼編碼：依據(jù)不同符號(hào)在文本中消失的不同的頻率來(lái)進(jìn)行壓縮編碼。假設(shè)文本是由a,u,x,z組成的字符串，若這個(gè)字符串的長(zhǎng)度為1000，每個(gè)字符用一個(gè)字節(jié)來(lái)存儲(chǔ)，共需1000個(gè)字節(jié)（即8000位）的空間。假如每個(gè)字符用2位二進(jìn)制來(lái)編碼（00=a,01=x,10=u,11=z），則用2000位二進(jìn)制即可以表示1000個(gè)字符。此外，還需要肯定的空間來(lái)存放編碼表，可以采納如下格式來(lái)存儲(chǔ)：符號(hào)個(gè)數(shù)：代碼1，符號(hào)1，代碼2，符號(hào)2，……

符號(hào)個(gè)數(shù)及每個(gè)符號(hào)分別用8位二進(jìn)制來(lái)表示，每個(gè)代碼需要占用位二進(jìn)制。因此，上例中，代碼表需占用5*8+4*2=48位，壓縮比為8000/2048=3.9。利用這種編碼方法，字符串a(chǎn)axuaxz的壓縮碼為二進(jìn)制串00000110000111，每個(gè)字符的編碼具有相同的位數(shù)（兩位）。從左到右依次從位串中取出兩位，通過(guò)查編碼表邊可以獲得原字符串，這是解壓縮過(guò)程。

我們利用霍夫曼編碼來(lái)實(shí)現(xiàn)壓縮，必需：

1）必需獲得不同字符的頻率。

2）建立具有最小加權(quán)外部路徑的二叉數(shù)（即霍夫曼樹(shù)），樹(shù)的外部結(jié)點(diǎn)用字符串中

的字符表示，外部結(jié)點(diǎn)的權(quán)重（weight）即為該字符消失的頻率。

3）遍歷從根到外部結(jié)點(diǎn)的路徑得到每個(gè)字符的編碼。

4）使用字符的編碼來(lái)代替字符串中的字符。

為了便利解碼，需要保存字符代碼映射表或每個(gè)字符的

頻率表（在保存信息為頻率表的狀況下，解碼需要重構(gòu)霍夫曼數(shù)以獲得相應(yīng)的編碼表）。

構(gòu)造霍夫曼樹(shù)：首先從僅含一個(gè)外部結(jié)點(diǎn)的二叉樹(shù)集合開(kāi)頭，每個(gè)外部結(jié)點(diǎn)代表字符串的一個(gè)不同的字符，其權(quán)重等于該字符的頻率。此后不斷的從集合中選擇兩棵具有最小權(quán)重的二叉樹(shù)，并把它們合并成一棵新的二叉樹(shù)，合并方法是把這兩棵二叉樹(shù)分別作為左右子樹(shù)，然后增加一個(gè)新的根結(jié)點(diǎn)。新二叉樹(shù)的權(quán)重為兩棵子樹(shù)的權(quán)重之和。這個(gè)過(guò)程始終可以持續(xù)到僅剩下一棵樹(shù)為止。。

編碼：構(gòu)造完畢霍夫曼樹(shù)后，可以對(duì)從根開(kāi)頭到外部結(jié)點(diǎn)（葉子）的路徑進(jìn)行編碼，方法是向左孩子移動(dòng)時(shí)取0，向右孩子移動(dòng)時(shí)取1。

對(duì)于策略2）我們用這種方法修改它：每當(dāng)壓縮/解壓1024*x個(gè)字節(jié)后，重新初始化代碼表。取文本長(zhǎng)度為100K到200K之間，x=10，20，30，40和50。測(cè)試修改后的程序，請(qǐng)給出你的結(jié)論：采納那種x值比較好？

對(duì)于霍夫曼編碼：當(dāng)文本中的字符消失的頻率差別很大時(shí)，我們可以通過(guò)使用變長(zhǎng)的編碼來(lái)降低每個(gè)位串的長(zhǎng)度。但是，怎樣對(duì)使用變長(zhǎng)編碼的位串解碼呢？我們可以發(fā)覺(jué)：在得到的霍夫曼編碼中，沒(méi)有任何一個(gè)代碼是另一個(gè)代碼的前綴。因此與編碼向匹配的實(shí)際的字符是唯一的。請(qǐng)用實(shí)現(xiàn)這樣的變長(zhǎng)策略，并驗(yàn)證它。

六、編寫(xiě)一個(gè)五子棋的嬉戲程序(沒(méi)學(xué)可視化編程，可能比較難，但實(shí)際比較簡(jiǎn)潔)。

實(shí)現(xiàn)人與機(jī)對(duì)下的功能。要求：

1、要有棋盤(pán)；

2、設(shè)計(jì)輸、贏推斷規(guī)章函數(shù)；

3、給出下棋過(guò)程

七、簡(jiǎn)潔的職工管理系統(tǒng)

1.問(wèn)題描述

對(duì)單位的職工進(jìn)行管理，包括插入、刪除、查找、排序等功能。

2.要求

職工對(duì)象包括姓名、性別、誕生年月、工作年月、學(xué)歷、職務(wù)、住址、電話(huà)等信息。

（1）新增一名職工：將新增職工對(duì)象按姓名以字典方式職工管理文件中。（2）刪除一名職工：從職工管理文件中刪除一名職工對(duì)象。

（3）查詢(xún)：從職工管理文件中查詢(xún)符合某些條件的職工。

（4）修改：檢索某個(gè)職工對(duì)象，對(duì)其某些屬性進(jìn)行修改。

（5）排序：按某種需要對(duì)職工對(duì)象文件進(jìn)行排序。

3.實(shí)現(xiàn)提示

職工對(duì)象數(shù)不必許多，便于一次讀入內(nèi)存，全部操作不經(jīng)過(guò)內(nèi)外存交換。（1）由鍵盤(pán)輸入職工對(duì)象，以文件方式保存。程序執(zhí)行時(shí)先將文件讀入內(nèi)存。（2）對(duì)職工對(duì)象中的"姓名"按字典挨次進(jìn)行排序。

（3）對(duì)排序后的職工對(duì)象進(jìn)行增、刪、查詢(xún)、修改、排序等操作。

4.選做內(nèi)容

將職工對(duì)象按散列法存儲(chǔ)，并設(shè)計(jì)解決沖突的方法。在此基礎(chǔ)上實(shí)現(xiàn)增、刪、查詢(xún)、修改、排序等操作。

八、全國(guó)鐵路運(yùn)輸網(wǎng)最佳經(jīng)由問(wèn)題

1.問(wèn)題描述

該題目采納我國(guó)鐵路運(yùn)輸網(wǎng)的數(shù)據(jù)進(jìn)行編程和運(yùn)行驗(yàn)證。圖如下(具體可參見(jiàn)http://.zgtlky./kyzn/ShowArticle.asp?ArticleID=168)，可不要這么具體，只要全國(guó)的主干線(xiàn)就可以了。

鐵路運(yùn)輸網(wǎng)絡(luò)中由鐵路線(xiàn)和火車(chē)站的兩個(gè)主要概念，譬如：1號(hào)鐵路線(xiàn)表示京廣線(xiàn)，2號(hào)鐵路線(xiàn)表示京滬線(xiàn)等。

鐵路線(xiàn)對(duì)象包括鐵路線(xiàn)編號(hào),鐵路線(xiàn)名稱(chēng)，起始站編號(hào),終點(diǎn)站編號(hào),該鐵路線(xiàn)長(zhǎng)度，通行標(biāo)志(00B客貨運(yùn)禁行,01B貨運(yùn)通行專(zhuān)線(xiàn)，10B客運(yùn)通行專(zhuān)線(xiàn)，11B客貨運(yùn)通行)。

火車(chē)站對(duì)象包括所屬鐵路線(xiàn)編號(hào)，車(chē)站代碼，車(chē)站名，車(chē)站簡(jiǎn)稱(chēng)，離該鐵路線(xiàn)起點(diǎn)站路程及終點(diǎn)站路程。

2.要求

（1）查詢(xún)某站所屬的鐵路線(xiàn)

（2）要求具備新增鐵路線(xiàn)的管理功能

（3）要求具備新增車(chē)站的管理功能

（4）針對(duì)客運(yùn)，貨運(yùn)狀況能計(jì)算任何一個(gè)起始車(chē)站到任何一個(gè)終點(diǎn)站之間的最短路徑。并且要求能夠顯示出該最短路徑的各個(gè)火車(chē)站的經(jīng)由挨次

3.實(shí)現(xiàn)提示

該題的解題思路可以參考第六大題。

九、教學(xué)方案編制問(wèn)題

高校的每個(gè)專(zhuān)業(yè)都要制定教學(xué)方案。假設(shè)任何專(zhuān)業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等，每個(gè)專(zhuān)業(yè)開(kāi)設(shè)的課程都是確定的，而且課程在開(kāi)設(shè)時(shí)間的支配必需滿(mǎn)意先修關(guān)系。每門(mén)課程有哪些先修

課程是確定的，可以有任意多門(mén)，也可以沒(méi)有。每門(mén)課恰好占一個(gè)學(xué)期。試在這

樣的前提下設(shè)計(jì)一個(gè)教學(xué)方案編制程序。

（1）輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門(mén)課的課程號(hào)(固定占3位的字母數(shù)字串)、學(xué)分和直接先修課的課程號(hào)。

（2）允許用戶(hù)指定下列兩種編排策略之一：一是使同學(xué)在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量勻稱(chēng)；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。

（3）若依據(jù)給定的條件問(wèn)題無(wú)解，則報(bào)告適當(dāng)?shù)男畔?；否則將教學(xué)方案輸出到用戶(hù)指定的文件中。方案的表格格式自行設(shè)計(jì)。

學(xué)期總數(shù)：6；學(xué)分上限：10；該專(zhuān)業(yè)共開(kāi)設(shè)12門(mén)課，課程號(hào)從C01到C12，

可設(shè)學(xué)期總數(shù)不超過(guò)12，課程總數(shù)不超過(guò)100。假如輸入的先修課程號(hào)不在該專(zhuān)業(yè)開(kāi)設(shè)的課程序列中，則作為錯(cuò)誤處理。應(yīng)建立內(nèi)部課程序號(hào)與課程號(hào)之間的對(duì)應(yīng)關(guān)系。

十、哈夫曼編/譯碼器

利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼編/譯碼系統(tǒng)。

一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：

（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmTree中。

（2）E：編碼（Encoding）。利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件htmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。

（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。

（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼寫(xiě)入文件CodePrint中。

（5）T：印哈夫曼樹(shù)（TreePrinting）。將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件TreePrint中。

（1）數(shù)據(jù)一：已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能消失8種字符，其概率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此設(shè)計(jì)哈夫曼編碼。利用此數(shù)據(jù)對(duì)程序進(jìn)行調(diào)試。

（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù)，并實(shí)現(xiàn)以

（1）文件CodeFile的基類(lèi)型可以設(shè)為子界型bit=0..1。

（2）用戶(hù)界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示運(yùn)行Quit。請(qǐng)用戶(hù)鍵入一個(gè)先把功能符，些功能執(zhí)行完畢后再經(jīng)菜單，直至某次用戶(hù)先把了“E”為止。

（3）在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行I、D或C命令之后，哈夫曼樹(shù)已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不肯定執(zhí)行I命令，由于文件hfmTree可能早已建好。

十一、哈希表設(shè)計(jì)

針對(duì)自己的班集體中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，完成相應(yīng)的建表和查表程序。

假設(shè)人名為中國(guó)姓名的漢語(yǔ)拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長(zhǎng)度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)照，用鏈表法處理沖突。

讀取熟識(shí)的30個(gè)人的姓名。

十二.文章編輯

功能：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。

靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共N行；要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中消失的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。

存儲(chǔ)結(jié)構(gòu)使用線(xiàn)性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；

輸入數(shù)據(jù)的形式和范圍：可以輸入大寫(xiě)、小寫(xiě)的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。

輸出形式：（1）分行輸出用戶(hù)輸入的各行字符；（2）分4行輸出"全部字母數(shù)"、"數(shù)字個(gè)數(shù)"、"空格個(gè)數(shù)"、"文章總字?jǐn)?shù)"（3）輸出刪除某一字符串后的文章；

十三.最小生成樹(shù)問(wèn)題

設(shè)計(jì)要求：利用第八題的全國(guó)鐵路運(yùn)輸網(wǎng)，在n個(gè)城市之間建設(shè)石油管道網(wǎng)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法。存儲(chǔ)結(jié)構(gòu)采納多種。求解算法多種。

十四.敢死隊(duì)問(wèn)題

有M個(gè)敢死隊(duì)員要炸掉敵人的一碉堡，誰(shuí)都不想去，排長(zhǎng)打算用輪回?cái)?shù)數(shù)的方法來(lái)打算哪個(gè)戰(zhàn)士去執(zhí)行任務(wù)。假如前一個(gè)戰(zhàn)士沒(méi)完成任務(wù)，則要再派一個(gè)戰(zhàn)士上去?，F(xiàn)給每個(gè)戰(zhàn)士編一個(gè)號(hào)，大家圍坐成一圈，任憑從某一個(gè)戰(zhàn)士開(kāi)頭計(jì)數(shù)，當(dāng)數(shù)到5時(shí)，對(duì)應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù)，且此戰(zhàn)士不再參與下一輪計(jì)數(shù)。假如此戰(zhàn)士沒(méi)完成任務(wù)，再?gòu)南乱粋€(gè)戰(zhàn)士開(kāi)頭數(shù)數(shù)，被數(shù)到第5時(shí)，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類(lèi)推，直到任務(wù)完成為止。

排長(zhǎng)是不情愿去的，假設(shè)排長(zhǎng)為1號(hào)，請(qǐng)你設(shè)計(jì)一程序，求出從第幾號(hào)戰(zhàn)士開(kāi)頭計(jì)數(shù)才能讓排長(zhǎng)最終一個(gè)留下來(lái)而不去執(zhí)行任務(wù)。

要求：至少采納兩種不同的數(shù)據(jù)結(jié)構(gòu)的方法實(shí)現(xiàn)。假如采納三種以上的方法者，可加分。

十五.猴子吃桃子問(wèn)題

有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再多吃一個(gè)，到了第10天就只余下一個(gè)桃子。用多種方法實(shí)現(xiàn)求出原來(lái)這群猴子共摘了多少個(gè)桃子。

要求：

1)采納數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解

2)采納鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解

3)采納遞歸實(shí)現(xiàn)上述求解

4)假如采納4種方法者,適當(dāng)加分

十六.數(shù)制轉(zhuǎn)換問(wèn)題(全班只能有2人及以下的人選擇做此題，超過(guò)2人則不計(jì)成果)

任意給定一個(gè)M進(jìn)制的數(shù)x，請(qǐng)實(shí)現(xiàn)如下要求

1)求出此數(shù)x的10進(jìn)制值（用MD表示）

2)實(shí)現(xiàn)對(duì)x向任意的一個(gè)非M進(jìn)制的數(shù)的轉(zhuǎn)換。

3)至少用兩種或兩種以上的方法實(shí)現(xiàn)上述要求（用棧解決，用數(shù)組解決，其它方法解決）。

十七.排序綜合

利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。

要求：

1)至少采納三種方法實(shí)現(xiàn)上述問(wèn)題求解（提示，可采納的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。

2)統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法。

3)假如采納4種或4種以上的方法者，可適當(dāng)加分。

十八.模擬旅館管理系統(tǒng)的一個(gè)功能——床位的安排與回收

⒈問(wèn)題描述：

某旅館有n個(gè)等級(jí)的房間，第i等級(jí)有個(gè)房間，每個(gè)等級(jí)有個(gè)床位

（1≤I≤n）。試模擬旅館管理系統(tǒng)中床位安排和回收的功能，設(shè)計(jì)能為單個(gè)旅客安排床位，在其離店便回收床位（供下次安排）的算法。

⒉基本要求

（1）輸入數(shù)據(jù)

對(duì)房間信息進(jìn)行初始化，包括房間的類(lèi)別、數(shù)量以及房間和床位的計(jì)費(fèi)標(biāo)準(zhǔn)；

安排時(shí)，輸入旅客姓名、年齡、性別、到達(dá)日期和所需房間等級(jí)；

回收時(shí)，輸入房間等級(jí)、房間號(hào)和床位號(hào)。

（2）輸出數(shù)據(jù)

安排勝利時(shí)打印旅客