山東大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)教學(xué)大綱

課

程名

租數(shù)據(jù)結(jié)構(gòu)

文

名

租

英

程

編DataStructures

專

課

實(shí)驗(yàn)課性質(zhì)：非獨(dú)立設(shè)課

人

課sd03031191

負(fù)責(zé)

程

人開(kāi)放實(shí)驗(yàn)題目數(shù)：個(gè)

大

主

綱

撰8

審核

郭

綱

人

琳

華

鳳

王

學(xué)時(shí)、學(xué)分

課程總學(xué)時(shí):104實(shí)驗(yàn)學(xué)時(shí)：32

課程總學(xué)分:5實(shí)驗(yàn)學(xué)分：1

二、適用專業(yè)及年級(jí)

軟件學(xué)院軟件工程系二年級(jí)

三、實(shí)驗(yàn)教學(xué)目的與基本要求

實(shí)驗(yàn)?zāi)康?/p>

掌握數(shù)據(jù)結(jié)構(gòu)基本的算法原理和實(shí)現(xiàn)方法，在項(xiàng)目實(shí)踐開(kāi)發(fā)過(guò)程中，逐步培養(yǎng)綜合開(kāi)發(fā)能力、科研

鉆研能力和創(chuàng)新能力。

基本要求

1、采用良好的編程風(fēng)格；關(guān)鍵操作要有注釋。

2、程序能夠運(yùn)行，顯示運(yùn)行結(jié)果。

四、主要儀器設(shè)備

硬件環(huán)境：P4CPU2.0以上PC機(jī)，512M以上內(nèi)存。

軟件環(huán)境：Windows7,VisualC++6.0以上

五、實(shí)驗(yàn)課程內(nèi)容和學(xué)時(shí)分配

實(shí)指已

驗(yàn)學(xué)實(shí)實(shí)每導(dǎo)開(kāi)

序題時(shí)驗(yàn)驗(yàn)組教/

實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)要求

號(hào)目分屬類人師未

名配性型數(shù)開(kāi)

稱

1遞1、輸出n個(gè)整數(shù)的全排列。4專驗(yàn)采用良好的編已

歸業(yè)證開(kāi)

練2、輸出n個(gè)整數(shù)的所有子集。類性程風(fēng)格；關(guān)鍵操

習(xí)作要有注釋；程

序能夠運(yùn)行，顯

示運(yùn)行結(jié)果。

驗(yàn)

2排4專已

1、創(chuàng)建排序類。證采用良好的編

序業(yè)開(kāi)

性

算2、提供操作:選擇排序、冒泡排序、類程風(fēng)格；關(guān)鍵操

法插入排序、基數(shù)排序、快速排序、作要有注釋；程

歸并排序。序能夠運(yùn)行，顯

3、能夠顯示各種排序算法的中間示運(yùn)行結(jié)果。

過(guò)程。

驗(yàn)

34專已

線1創(chuàng)建線性表類。線性表的存儲(chǔ)結(jié)證采用良好的編

業(yè)開(kāi)

性

性構(gòu)使用鏈表。類程風(fēng)格；關(guān)鍵操

表2提供操作:自表首插入元素、刪作要有注釋；程

操除指定元素、搜索表中是否有指序能夠運(yùn)行，顯

作定元素、輸出鏈表。示運(yùn)行結(jié)果。

3接收鍵盤錄入的一系列整數(shù)（例

10,25,8,33,60）作為節(jié)點(diǎn)的元素

值，創(chuàng)建鏈表。輸出鏈表內(nèi)容。

4輸入一個(gè)整數(shù)（例33）,在鏈表

中進(jìn)行搜索，輸出其在鏈表中的

位置。如果不存在輸出0o

5使用鏈表遍歷器實(shí)現(xiàn)鏈表的反

序輸出。

6創(chuàng)建兩個(gè)有序鏈表，使用鏈表遍

歷器實(shí)現(xiàn)鏈表的合并。

4矩1創(chuàng)建三對(duì)角矩陣類，采用按列映4專驗(yàn)采用良好的編已

業(yè)證開(kāi)

陣射方式,提供store和retrieve方類性程風(fēng)格；關(guān)鍵操

和法。作要有注釋；程

散2創(chuàng)建下三角矩陣類，采用按列映序能夠運(yùn)行，顯

列射方式,提供store和retrieve方示運(yùn)行結(jié)果。

表法。

3創(chuàng)建稀疏矩陣類，采用行主順序

把稀疏矩陣映射到一維數(shù)組中，

實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置和兩個(gè)稀疏

矩陣的加法操作。

4使用散列表設(shè)計(jì)實(shí)現(xiàn)一個(gè)字典，

假設(shè)關(guān)鍵字為整數(shù)且D為961,在

字典中插入隨機(jī)產(chǎn)生的500個(gè)不

同的整數(shù)，實(shí)現(xiàn)字典的建立和搜

索操作。分別使用線性開(kāi)型尋址

和鏈表散列解決溢出。

專驗(yàn)

5堆1、計(jì)算數(shù)學(xué)表達(dá)式的值。4采用良好的編已

業(yè)證開(kāi)

棧輸入數(shù)學(xué)表達(dá)式，輸出表達(dá)式的類性程風(fēng)格；關(guān)鍵操

和計(jì)算結(jié)果。數(shù)學(xué)表達(dá)式由單個(gè)數(shù)作要有注釋；程

隊(duì)字和運(yùn)算符序能夠運(yùn)行，顯

列"（、”）構(gòu)成,例如2+3*（4+5）示運(yùn)行結(jié)果。

的-6/4o假定表達(dá)式輸入格式合

應(yīng)法。

用2、以一個(gè)m*n的長(zhǎng)方陣表示迷

宮，0和1分別表示迷宮中的通路

通路，或得出沒(méi)有通路的結(jié)論。

迷宮根據(jù)一個(gè)迷宮數(shù)據(jù)文件建

立。迷宮數(shù)據(jù)文件由一個(gè)包含0、

1的矩陣組成。迷宮的通路可以使

用通路上各點(diǎn)的坐標(biāo)序列進(jìn)行展

示（使用圖形展示最佳）。

3、設(shè)計(jì)電路布線最短路徑和障

礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定

的迷宮，求出一條從入口到出口

的通路，或得出沒(méi)有通路的結(jié)論。

迷宮根據(jù)一個(gè)迷宮數(shù)據(jù)文件建

立。迷宮數(shù)據(jù)文件由一個(gè)包含0、

1的矩陣組成。迷宮的通路可以使

用通路上各點(diǎn)的坐標(biāo)序列進(jìn)行展

示（使用圖形展示最佳）。

專驗(yàn)

6二1創(chuàng)建二叉樹(shù)類。二叉樹(shù)的存儲(chǔ)結(jié)4采用良好的編已

業(yè)證開(kāi)

叉構(gòu)使用鏈表。類性程風(fēng)格；關(guān)鍵操

樹(shù)2提供操作:前序遍歷、中序遍歷、作要有注釋；程

操后序遍歷、層次遍歷、計(jì)算二叉序能夠運(yùn)行，顯

作樹(shù)結(jié)點(diǎn)數(shù)目、計(jì)算二叉樹(shù)高度。示運(yùn)行結(jié)果。

3對(duì)建立好的二叉樹(shù)，執(zhí)行上述各

操作。

4接收鍵盤錄入的二叉樹(shù)前序序

列和中序序列（各元素各不相同）

輸出該二叉樹(shù)的后序序列。

驗(yàn)

74專已

堆1創(chuàng)建最大堆類。最大堆的存儲(chǔ)結(jié)證采用良好的編

業(yè)開(kāi)

性

和構(gòu)使用鏈表。類程風(fēng)格；關(guān)鍵操

搜2提供操作:堆的插入、堆的刪除。作要有注釋；程

索堆的初始化。Huffman樹(shù)的構(gòu)造。序能夠運(yùn)行，顯

樹(shù)二叉搜索樹(shù)的構(gòu)造。示運(yùn)行結(jié)果。

3接收鍵盤錄入的一系列整數(shù)，輸

出其對(duì)應(yīng)的最大堆、Huffman編碼

以及二叉搜索樹(shù)。

堆排序

驗(yàn)

84專已

圖1創(chuàng)建圖類。圖的存儲(chǔ)結(jié)構(gòu)使用鄰證采用良好的編

業(yè)開(kāi)

性

的接矩陣或鏈表。類程風(fēng)格；關(guān)鍵操

操2提供操作:遍歷、BFS、DFS作要有注釋；程

作3對(duì)建立好的圖，執(zhí)行上述各操序能夠運(yùn)行，顯

作。示運(yùn)行結(jié)果。

4輸出生成樹(shù)。

5輸出最小生成樹(shù)。

六、考核方式

程序結(jié)果演示和實(shí)驗(yàn)報(bào)告.

七、實(shí)驗(yàn)教科書(shū)、參考書(shū)

（一）教科書(shū)

1.SartajSahni.DataStructures,Algorithms,andApplicationsinC++.北京，機(jī)械工業(yè)出版社,

1999.3.

（二）參考書(shū)

1.殷人昆編著.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）（第2版）.清華大學(xué)出版社

2.張銘王騰蛟趙海燕編著.數(shù)據(jù)結(jié)構(gòu)與算法.高等教育出版社

附件三：實(shí)驗(yàn)教學(xué)大綱部分格式編寫說(shuō)明

《XXXX》課程實(shí)驗(yàn)教學(xué)大綱

一、實(shí)驗(yàn)課程名稱：中文名：按教務(wù)處綜合教務(wù)管理系統(tǒng)中規(guī)定的名稱

英文名：把實(shí)驗(yàn)課程名稱譯成英語(yǔ)

二、課程編號(hào)：按教務(wù)處綜合教務(wù)管理系統(tǒng)中規(guī)定的課程編號(hào)

三、大綱主撰人、審核人：大綱主撰人與審核人不能為同一人

四、實(shí)驗(yàn)課性質(zhì)：分獨(dú)立設(shè)課和非獨(dú)立設(shè)課兩種（獨(dú)立設(shè)課課程總學(xué)時(shí)與實(shí)驗(yàn)總

學(xué)時(shí)完全一致，并有單獨(dú)的學(xué)分和考試成績(jī)）

五、開(kāi)放實(shí)驗(yàn)題目數(shù)：各學(xué)院、實(shí)驗(yàn)中心按照上報(bào)實(shí)驗(yàn)室與設(shè)備管理處開(kāi)放實(shí)驗(yàn)題目如實(shí)填

報(bào)

六'學(xué)時(shí)學(xué)分：

（1）課程總學(xué)時(shí)：；課程總學(xué)分：；實(shí)驗(yàn)課總學(xué)時(shí)：；實(shí)驗(yàn)總學(xué)分：

（2）適應(yīng)兩個(gè)以上專業(yè)但學(xué)時(shí)數(shù)不一樣的可依次分別填寫

（3）為適應(yīng)實(shí)驗(yàn)室開(kāi)放和學(xué)生自選實(shí)驗(yàn)和開(kāi)設(shè)綜合性、設(shè)計(jì)性實(shí)驗(yàn)，可列出一定的選做

實(shí)驗(yàn)課時(shí)和實(shí)驗(yàn)內(nèi)容，若安排的實(shí)驗(yàn)教學(xué)計(jì)劃課時(shí)超出教學(xué)計(jì)劃規(guī)定的課時(shí)，可將超出的課

時(shí)列為選修、選做課時(shí)（內(nèi)容）。

七、適用專業(yè)：按本科生院2012年本科教學(xué)計(jì)劃中規(guī)定的專業(yè)名稱（或方向）填寫，學(xué)院內(nèi)

同一課程適應(yīng)不同專業(yè)要求只編寫一門實(shí)驗(yàn)大綱，按實(shí)驗(yàn)學(xué)時(shí)最多的專業(yè)編寫，適應(yīng)兩個(gè)以

上專業(yè)（或方向）的依次填寫全部專業(yè)名稱（或方向），并注明不同專業(yè)的實(shí)驗(yàn)內(nèi)容的課時(shí)。

八、實(shí)驗(yàn)教學(xué)目的和基本要求

指本門實(shí)驗(yàn)課總的目的和要求，通過(guò)實(shí)驗(yàn)培養(yǎng)學(xué)生總體上了解或掌握什么方法或技能，

達(dá)到什么目的；對(duì)學(xué)生有什么具體要求（比如：理解實(shí)驗(yàn)原理及實(shí)驗(yàn)方案，掌握正確操作規(guī)

程；掌握各種儀器的使用，了解其性能參數(shù)、適應(yīng)范圍及注意事項(xiàng)等）。

九、主要儀器設(shè)備：指應(yīng)配備的主要設(shè)備名稱和臺(tái)件數(shù)

設(shè)備名稱應(yīng)填寫主要儀器設(shè)備的名稱，并與實(shí)驗(yàn)設(shè)備帳卡名稱一致

十、實(shí)驗(yàn)課程內(nèi)容和學(xué)時(shí)分配

序?qū)嶒?yàn)題目學(xué)時(shí)實(shí)驗(yàn)實(shí)驗(yàn)每組實(shí)驗(yàn)指導(dǎo)己開(kāi)/

實(shí)驗(yàn)內(nèi)容

號(hào)名稱分配屬性類型人數(shù)要求教師未開(kāi)

1