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

本文格式為Word版，下載可任意編輯——《數(shù)據(jù)結(jié)構(gòu)課程試驗(yàn)》大綱《數(shù)據(jù)結(jié)構(gòu)課程試驗(yàn)》大綱

一、《數(shù)據(jù)結(jié)構(gòu)課程試驗(yàn)》的地位與作用

“數(shù)據(jù)結(jié)構(gòu)〞是計(jì)算機(jī)專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程，是計(jì)算機(jī)專業(yè)的一門核心的

關(guān)鍵性課程。本課程較系統(tǒng)地介紹了軟件設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)算法，介紹了常用的多種查找和排序技術(shù)，并做了性能分析和比較，內(nèi)容十分豐富。本課程的學(xué)習(xí)將為后續(xù)課程的學(xué)習(xí)以及軟件設(shè)計(jì)水平的提高打下良好的基礎(chǔ)。由于以下原因，使得把握這門課程具有較大的難度：（1）內(nèi)容豐富，學(xué)習(xí)量大，給學(xué)習(xí)帶來困難；

（2）貫穿全書的動(dòng)態(tài)鏈表存儲(chǔ)結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點(diǎn)也是難點(diǎn)；

（3）所用到的技術(shù)多，而在此之前的各門課程中所介紹的專業(yè)性知識(shí)又不多，因而加大了學(xué)習(xí)難度；

（4）隱含在各部分的技術(shù)和方法豐富，也是學(xué)習(xí)的重點(diǎn)和難點(diǎn)。

根據(jù)《數(shù)據(jù)結(jié)構(gòu)課程》課程本身的技術(shù)特性，設(shè)置《數(shù)據(jù)結(jié)構(gòu)課程試驗(yàn)》實(shí)踐環(huán)節(jié)十分重要。通過試驗(yàn)實(shí)踐內(nèi)容的訓(xùn)練，突出構(gòu)造性思維訓(xùn)練的特征,目的是提高學(xué)生組織數(shù)據(jù)及編寫大型程序的能力。試驗(yàn)學(xué)時(shí)為10。

二、《數(shù)據(jù)結(jié)構(gòu)課程試驗(yàn)》的目的和要求

不少學(xué)生在解答習(xí)題特別是算法設(shè)計(jì)題時(shí)，覺得無從下手，做起來特別吃力。試驗(yàn)中的內(nèi)容和教科書的內(nèi)容是密切相關(guān)的，解決題目要求所需的各種技術(shù)大多可從教科書中找到，只不過其出現(xiàn)的形式呈多樣化，因此需要細(xì)心體會(huì)，在反復(fù)實(shí)踐的過程中才能把握。

為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和把握算法設(shè)計(jì)所需的技術(shù)，為整個(gè)專業(yè)學(xué)習(xí)打好基礎(chǔ)，要求運(yùn)用所學(xué)知識(shí)，上機(jī)解決一些典型問題，通過分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、穩(wěn)固把握所用到的一些技術(shù)。數(shù)據(jù)結(jié)構(gòu)中稍微繁雜一些的算法設(shè)計(jì)中可能同時(shí)要用到多種技術(shù)和方法，如算法設(shè)計(jì)的構(gòu)思方法，動(dòng)態(tài)鏈表，算法的編碼，遞歸技術(shù)，與特定問題相關(guān)的技術(shù)等，要求重點(diǎn)把握線性鏈表、二叉樹和樹、圖結(jié)構(gòu)、數(shù)組結(jié)構(gòu)相關(guān)算法的設(shè)計(jì)。在把握基本算法的基礎(chǔ)上，把握分析、解決實(shí)際問題的能力。

三、《數(shù)據(jù)結(jié)構(gòu)課程試驗(yàn)》內(nèi)容

課程試驗(yàn)共10學(xué)時(shí)，要求完成以下五個(gè)題目：

實(shí)習(xí)一約瑟夫環(huán)問題（2學(xué)時(shí)）

用循環(huán)鏈表實(shí)現(xiàn)約瑟夫環(huán)問題，熟悉鏈表結(jié)構(gòu)的使用。實(shí)習(xí)二八皇后問題（2學(xué)時(shí)）

在8×8的棋盤上放置彼此不受攻擊的8個(gè)皇后，熟悉遞歸與回溯程序設(shè)計(jì)方法。實(shí)習(xí)三二叉樹基本操作（2學(xué)時(shí)）

創(chuàng)立、遍歷、顯示二叉樹，通過二叉樹的基本操作，把握樹結(jié)構(gòu)的處理方法。實(shí)習(xí)四哈夫曼編碼與譯碼

針對(duì)字符集A及其各字符的頻率值（可統(tǒng)計(jì)獲得）給出其中給字符哈夫曼編碼，并

針對(duì)一段文本（定義在A上）進(jìn)行編碼和譯碼，實(shí)現(xiàn)一個(gè)哈夫曼編碼/譯碼系統(tǒng)。

實(shí)習(xí)五最小生成樹問題（2學(xué)時(shí)）

在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法。

四、《數(shù)據(jù)結(jié)構(gòu)課程試驗(yàn)》考核方式

采用上機(jī)狀況、程序質(zhì)量、實(shí)習(xí)報(bào)告相結(jié)合的形式，總分值為100分。

1．上機(jī)狀況（30%）

包括出勤狀況、調(diào)試表現(xiàn)、是否上網(wǎng)、玩游戲。2．程序質(zhì)量（50%）3．實(shí)習(xí)報(bào)告（20%）

《數(shù)據(jù)結(jié)構(gòu)課程試驗(yàn)》指導(dǎo)書

實(shí)習(xí)一線性表

本次實(shí)習(xí)的主要目的在于熟悉線性表的基本運(yùn)算在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)，其中以熟悉各種鏈表的操作為側(cè)重點(diǎn)。通過本次實(shí)習(xí)還可幫助讀者復(fù)習(xí)高級(jí)語言的使用方法。

1、城市鏈表[問題描述]

將若干城市的信息，存入一個(gè)帶頭結(jié)點(diǎn)的單鏈表。結(jié)點(diǎn)中的城市信息包括：城市名，城市的位置坐標(biāo)。要求能夠利用城市名和位置坐標(biāo)進(jìn)行有關(guān)查找、插入、刪除、更新等操作。[基本要求]

（1）給定一個(gè)城市名，返回其位置坐標(biāo)；

（2）給定一個(gè)位置坐標(biāo)P和一個(gè)距離D，返回所有與P的距離小于等于D的城市。[測(cè)試數(shù)據(jù)]

由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)。

2、約瑟夫環(huán)[問題描述]約瑟夫（Joeph）問題的一種描述是：編號(hào)為1,2,?,n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)中止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。[基本要求]

利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，依照出列的順序印出各人的編號(hào)。[測(cè)試數(shù)據(jù)]

m的初值為20；密碼：3，1，7，2，4，8，4（正確的結(jié)果應(yīng)為6，1，4，7，2，3，5）。[實(shí)現(xiàn)提醒]

程序運(yùn)行后首先要求用戶指定初始報(bào)數(shù)上限值，然后讀取各人的密碼。設(shè)n≤30。[選作內(nèi)容]

向上述程序中添加在順序結(jié)構(gòu)上實(shí)現(xiàn)的部分。

3、線性表的逆置[問題描述]

分別以不同存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置。線性表的就地逆置就是在原表的存儲(chǔ)空間內(nèi)將線性表（a1,a2,a3,?,an）逆置為（an，an-1，?，a2，a1）。[基本要求]

用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置，并將結(jié)果輸出。[測(cè)試數(shù)據(jù)]

由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)，如空表。

[實(shí)現(xiàn)提醒]

設(shè)三個(gè)連續(xù)的指針，分別指向當(dāng)前結(jié)點(diǎn)、當(dāng)前結(jié)點(diǎn)的前趨、當(dāng)前結(jié)點(diǎn)的后繼。[選作內(nèi)容]

利用單鏈表作為存儲(chǔ)結(jié)構(gòu)。首先先建立線性表的帶頭結(jié)點(diǎn)的單鏈表表示形式，之后在不借助輔助結(jié)點(diǎn)空間的狀況下實(shí)現(xiàn)單鏈表的逆置，并將結(jié)果輸出。

4、長(zhǎng)整數(shù)運(yùn)算[問題描述]

設(shè)計(jì)一個(gè)程序?qū)崿F(xiàn)兩個(gè)任意長(zhǎng)的整數(shù)求和運(yùn)算。[基本要求]

利用雙項(xiàng)循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整型變量。任何整型變量的范圍是-（215-1）~（215-1）。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開。[測(cè)試數(shù)據(jù)]

（1）0；0；應(yīng)輸出“0〞。

（2）-2345,6789；-7654,3211；應(yīng)輸出“-1,0000,0000〞。

（3）-9999,9999；1,0000,0000,0000；應(yīng)輸出“9999,0000,0001〞。（4）1,0001,000；-1,0001,0001；應(yīng)輸出“0〞。（5）1,0001,0001；-1,0001,0000；應(yīng)輸出“1〞。

[實(shí)現(xiàn)提醒]

（1）每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為215-1=32767，才能保證兩數(shù)相加不會(huì)溢出。但若這樣存，即相當(dāng)于按32768進(jìn)制數(shù)存，在十進(jìn)制數(shù)與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不便利。故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制數(shù)的4位，即不超過9999的非負(fù)整數(shù)，整個(gè)鏈表視為萬進(jìn)制數(shù)。（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)點(diǎn)數(shù)目。相加過程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。[選作內(nèi)容]

修改上述程序，使它在整型量范圍是-（2n-1）~（2n-1）的計(jì)算機(jī)上都能有效地運(yùn)行。其中，n是由程序讀入的參量。輸入數(shù)據(jù)的分組方法可以另行規(guī)定。

實(shí)習(xí)二棧、隊(duì)列與遞歸算法設(shè)計(jì)

僅僅認(rèn)識(shí)到棧和隊(duì)列是兩種特別的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)習(xí)的目的在于使讀者深入了解棧和隊(duì)列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它們；同時(shí)還將穩(wěn)定這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較繁雜問題的遞歸算法設(shè)計(jì)。

1、數(shù)制轉(zhuǎn)換問題[問題描述]

將十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題，其解決方案好多，其中最簡(jiǎn)單方法基于以下原理：即除d取余法。例如：（1348）10=（2504）8

NNdiv8Nmod8134816841682102125202從中我們可以看出，最先產(chǎn)生的余數(shù)4是轉(zhuǎn)換結(jié)果的最低位，這正好符合棧的特性即后進(jìn)先出的特性。所以可以用順序棧來模擬這個(gè)過程。[基本要求]

對(duì)于鍵盤輸入的任意一個(gè)非負(fù)的十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。由于上述的計(jì)算過程是從低位到高位順序產(chǎn)生的八進(jìn)制數(shù)的各個(gè)數(shù)位，而打印輸出，一般來說應(yīng)從高位到地位進(jìn)行，恰好和計(jì)算過程相反。因此可以先將計(jì)算過程中得到的八進(jìn)制數(shù)的各位進(jìn)棧，待相對(duì)應(yīng)的八進(jìn)制數(shù)的各位均產(chǎn)生以后，再使其按順序出棧，并打印輸出。即得到了與輸入的十進(jìn)制數(shù)相對(duì)應(yīng)的八進(jìn)制數(shù)。[測(cè)試數(shù)據(jù)]

由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)。

2、回文判斷[問題描述]

試寫一個(gè)算法，判斷依次讀入的一個(gè)以@為終止符的字母序列，是否為形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a(chǎn)+b&b+a’是屬該模式的字符序列，而‘１+３&３－１’則不是。[實(shí)現(xiàn)提醒]

首先，序列1進(jìn)棧，然后序列1出棧并與序列2比較。[測(cè)試數(shù)據(jù)]

由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)，如序列1和序列2均為空串。

3、商品貨架管理[問題描述]

商品貨架可以看成一個(gè)棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。上貨時(shí)，需要倒貨架，以保證生產(chǎn)日期較近的商品在較下的位置。[基本要求]

針對(duì)一種特定商品，實(shí)現(xiàn)上述管理過程。[實(shí)現(xiàn)提醒]

用棧模擬貨架和周轉(zhuǎn)空間。[測(cè)試數(shù)據(jù)]