數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)項(xiàng)目卡.

1、數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)項(xiàng)目卡數(shù)學(xué)與計(jì)算機(jī)科學(xué)系Department of Mathematics and Computer Science實(shí) 訓(xùn) 項(xiàng) 目 卡數(shù)學(xué)與計(jì)算機(jī)科學(xué)系 計(jì)算機(jī)實(shí)驗(yàn)室 計(jì)算機(jī)機(jī)房 分室實(shí)驗(yàn)序號(hào)1實(shí)驗(yàn)名稱數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)基礎(chǔ)實(shí)驗(yàn)類別基礎(chǔ)課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)類型驗(yàn)證性實(shí)驗(yàn)者類別本科計(jì)劃學(xué)時(shí)2實(shí)驗(yàn)要求必做實(shí)驗(yàn)組數(shù)81每組人數(shù)1實(shí) 驗(yàn)內(nèi) 容1、復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)的前導(dǎo)知識(shí)C語言中循環(huán)、數(shù)組、遞歸函數(shù)和鏈表等知識(shí)點(diǎn)的應(yīng)用。2、掌握指針類型、結(jié)構(gòu)體類型等數(shù)據(jù)類型的使用。3、結(jié)合實(shí)際問題，培養(yǎng)學(xué)生算法描述的能力，加強(qiáng)對(duì)算法特性的理解。具體題目：實(shí)驗(yàn)案例1：模擬簡單計(jì)算器的工作。假設(shè)計(jì)算器只能進(jìn)行加減乘除運(yùn)

2、算，運(yùn)算數(shù)和結(jié)果都是整數(shù)，4種運(yùn)算符的優(yōu)先級(jí)相同，按從左到右的順序計(jì)算。實(shí)驗(yàn)案例2：遞增鏈表的插入。給定一個(gè)遞增整數(shù)序列和某個(gè)整數(shù)M，構(gòu)造出次遞增序列對(duì)應(yīng)的鏈表，并創(chuàng)建以M為值的新結(jié)點(diǎn)且插入到鏈表中，使其結(jié)果序列依然保持遞增順序。名 稱型 號(hào)數(shù) 量儀器設(shè)備PC機(jī)VC+6.0聯(lián)想8181低值耐用品名 稱 及 消 耗 額備 注消耗材料實(shí)驗(yàn)室主任: 填卡人: 萬厚沖 填卡日期:2012.9.10實(shí) 訓(xùn) 項(xiàng) 目 卡數(shù)學(xué)與計(jì)算機(jī)科學(xué)系 計(jì)算機(jī)實(shí)驗(yàn)室 計(jì)算機(jī)機(jī)房 分室實(shí)驗(yàn)序號(hào)2實(shí)驗(yàn)名稱單鏈表的插入和刪除實(shí)驗(yàn)類別基礎(chǔ)課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)類型驗(yàn)證性實(shí)驗(yàn)者類別本科計(jì)劃學(xué)時(shí)2實(shí)驗(yàn)要求必做實(shí)驗(yàn)組數(shù)81每組人數(shù)1實(shí)

3、驗(yàn)內(nèi) 容1、掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2、熟練掌握鏈表的基本操作。3、結(jié)合實(shí)際問題，培養(yǎng)學(xué)生算法描述的能力，加強(qiáng)對(duì)算法特性的理解。具體題目：實(shí)驗(yàn)案例：完成對(duì)單鏈表的插入和刪除，單鏈表的數(shù)據(jù)域?yàn)樽址?，插入時(shí)不允許重復(fù)的字符串插入表中；刪除時(shí)是根據(jù)輸入的字符串，先找到相應(yīng)的結(jié)點(diǎn)，后刪除之。（1）輸入的形式和輸入值的范圍：輸入的字符串可以含有空格，以回車鍵結(jié)束。如果直接按回車鍵表示建立鏈表結(jié)束。輸入的字符串最大長度默認(rèn)為10，用戶可以修改頭文件改變此長度。（2）輸出的形式：單鏈表的輸出是每個(gè)字符串占一行。當(dāng)插入重復(fù)的字符串到表中時(shí)，有信息提示，否則輸出插入后的單鏈表：當(dāng)根據(jù)輸入的字符串刪除時(shí)，如果

4、沒有找到相應(yīng)的結(jié)點(diǎn)，有信息提示，否則輸出刪除后的單鏈表。（3）程序所能達(dá)到的功能：能夠根據(jù)要求正確的實(shí)現(xiàn)插入和刪除功能。名 稱型 號(hào)數(shù) 量儀器設(shè)備PC機(jī)VC+6.0聯(lián)想8181低值耐用品名 稱 及 消 耗 額備 注消耗材料實(shí)驗(yàn)室主任: 填卡人: 萬厚沖 填卡日期: 2012.9.10實(shí) 訓(xùn) 項(xiàng) 目 卡數(shù)學(xué)與計(jì)算機(jī)科學(xué)系 計(jì)算機(jī)實(shí)驗(yàn)室 計(jì)算機(jī)機(jī)房 分室實(shí)驗(yàn)序號(hào)3實(shí)驗(yàn)名稱棧和隊(duì)列實(shí)驗(yàn)類別基礎(chǔ)課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)類型驗(yàn)證性實(shí)驗(yàn)者類別本科計(jì)劃學(xué)時(shí)2實(shí)驗(yàn)要求必做實(shí)驗(yàn)組數(shù)81每組人數(shù)1實(shí) 驗(yàn)內(nèi) 容1、熟練掌握堆棧的基本操作。2、熟練掌握隊(duì)列的基本操作。3、結(jié)合實(shí)際問題，培養(yǎng)學(xué)生算法描述的能力，加強(qiáng)對(duì)算法特

5、性的理解。具體題目：實(shí)驗(yàn)案例1：數(shù)制轉(zhuǎn)換。本實(shí)驗(yàn)采用順序表作為棧的的存儲(chǔ)結(jié)構(gòu)，完成對(duì)數(shù)制的轉(zhuǎn)換。（1）輸入的形式和輸入值的范圍：輸入任意一個(gè)非負(fù)十進(jìn)制整數(shù)，范圍在-3276832767之間。（2）輸出的形式：輸入與之等值的八進(jìn)制數(shù)。（3）程序所能達(dá)到的功能：能夠根據(jù)要求正確的實(shí)現(xiàn)十進(jìn)制整數(shù)與八進(jìn)制整數(shù)之間的轉(zhuǎn)換，并由此加深對(duì)棧后進(jìn)先出特點(diǎn)的認(rèn)識(shí)與理解。實(shí)驗(yàn)案例2：銀行業(yè)務(wù)隊(duì)列簡單模擬。設(shè)某銀行有A、B兩個(gè)業(yè)務(wù)窗口，且處理業(yè)務(wù)的速度不一樣，其中A窗口處理速度是B窗口的2倍即當(dāng)A窗口每處理完2個(gè)顧客時(shí)，B窗口處理完1個(gè)顧客。給定到達(dá)銀行的顧客序列，請(qǐng)按業(yè)務(wù)完成的順序輸出顧客序列。假定不考慮顧客先后

6、達(dá)到的時(shí)間間隔，并且當(dāng)不同窗口同時(shí)處理完2個(gè)顧客時(shí)，A窗口顧客優(yōu)先輸出。名 稱型 號(hào)數(shù) 量儀器設(shè)備PC機(jī)VC+6.0聯(lián)想8181低值耐用品名 稱 及 消 耗 額備 注消耗材料實(shí)驗(yàn)室主任: 填卡人: 萬厚沖 填卡日期: 2012.9.10實(shí) 訓(xùn) 項(xiàng) 目 卡數(shù)學(xué)與計(jì)算機(jī)科學(xué)系 計(jì)算機(jī)實(shí)驗(yàn)室 計(jì)算機(jī)機(jī)房 分室實(shí)驗(yàn)序號(hào)4實(shí)驗(yàn)名稱二叉樹的操作實(shí)驗(yàn)類別基礎(chǔ)課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)類型驗(yàn)證性實(shí)驗(yàn)者類別本科計(jì)劃學(xué)時(shí)2實(shí)驗(yàn)要求必做實(shí)驗(yàn)組數(shù)81每組人數(shù)1實(shí) 驗(yàn)內(nèi) 容1、熟練掌握二叉樹的存儲(chǔ)結(jié)構(gòu)。2、熟練掌握二叉樹的遍歷及其應(yīng)用。3、結(jié)合實(shí)際問題，培養(yǎng)學(xué)生算法描述的能力，加強(qiáng)對(duì)算法特性的理解。具體題目：實(shí)驗(yàn)案例1：還原

7、二叉樹。給定一棵二叉樹的先序遍歷序列和中序遍歷序列，要求計(jì)算該二叉樹的高度。（1）輸入說明：輸入第1行給出正整數(shù)N（N50），為樹中結(jié)點(diǎn)總數(shù)。隨后2行先后給出先序和中序遍歷序列，均為長度為N的不包含重復(fù)英文字母（區(qū)分大小寫）的字符串。（2）輸出說明：輸出為一個(gè)整數(shù)，即該二叉樹的高度。實(shí)驗(yàn)案例2：完成對(duì)二叉樹的建立、先序、中序、后序及按層次遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作。（1）輸入的形式和輸入值的范圍：二叉樹中結(jié)點(diǎn)的值默認(rèn)為字符類型，以先序形式輸入并創(chuàng)建二叉樹，空指針以“#”字符代替，字符連續(xù)輸入，以按回車鍵表示結(jié)束。（2）輸出的形式：二叉樹的輸出是每個(gè)字符占一列，輸出完成后換行。（3）

8、程序所能達(dá)到的功能：能夠根據(jù)要求正確的實(shí)現(xiàn)二叉樹的所有要求的操作。名 稱型 號(hào)數(shù) 量儀器設(shè)備PC機(jī)VC+6.0聯(lián)想8181低值耐用品名 稱 及 消 耗 額備 注消耗材料實(shí)驗(yàn)室主任: 填卡人: 萬厚沖 填卡日期: 2012.9.10實(shí) 訓(xùn) 項(xiàng) 目 卡數(shù)學(xué)與計(jì)算機(jī)科學(xué)系 計(jì)算機(jī)實(shí)驗(yàn)室 計(jì)算機(jī)機(jī)房 分室實(shí)驗(yàn)序號(hào)5實(shí)驗(yàn)名稱哥尼斯堡的“七橋問題”實(shí)驗(yàn)類別基礎(chǔ)課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)類型驗(yàn)證性實(shí)驗(yàn)者類別本科計(jì)劃學(xué)時(shí)2實(shí)驗(yàn)要求必做實(shí)驗(yàn)組數(shù)81每組人數(shù)1實(shí) 驗(yàn)內(nèi) 容1、熟練掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)。2、熟練掌握?qǐng)D的連通性判斷方法。3、結(jié)合實(shí)際問題，培養(yǎng)學(xué)生算法描述的能力，加強(qiáng)對(duì)算法特性的理解。具體題目：實(shí)驗(yàn)案例：18世紀(jì)

9、時(shí)，歐洲有一個(gè)風(fēng)景秀麗的小城哥尼斯堡(今俄羅斯加里寧格勒)，那里的普萊格爾河上有七座橋。將河中的兩個(gè)島和河岸連結(jié)，城中的居民經(jīng)常沿河過橋散步，于是提出了一個(gè)問題：一個(gè)人怎樣才能一次走遍七座橋，每座橋只走過一次，最后回到出發(fā)點(diǎn)？（1）輸入說明：輸入第1行給出兩個(gè)正整數(shù)N（1N1000）和邊數(shù)M，隨后的M行對(duì)應(yīng)M條邊，每行給出一對(duì)正整數(shù)，分別是該條邊連通的兩個(gè)結(jié)點(diǎn)的編號(hào)（結(jié)點(diǎn)從1到N編號(hào)）。（2）輸出說明：若歐拉回路存在則輸出1，否則輸出0。名 稱型 號(hào)數(shù) 量儀器設(shè)備PC機(jī)VC+6.0聯(lián)想8181低值耐用品名 稱 及 消 耗 額備 注消耗材料實(shí)驗(yàn)室主任: 填卡人: 萬厚沖 填卡日期: 2012.9

10、.10實(shí) 訓(xùn) 項(xiàng) 目 卡數(shù)學(xué)與計(jì)算機(jī)科學(xué)系 計(jì)算機(jī)實(shí)驗(yàn)室 計(jì)算機(jī)機(jī)房分室實(shí)驗(yàn)序號(hào)6實(shí)驗(yàn)名稱旅游規(guī)劃實(shí)驗(yàn)類別基礎(chǔ)課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)類型驗(yàn)證性實(shí)驗(yàn)者類別本科計(jì)劃學(xué)時(shí)2實(shí)驗(yàn)要求必做實(shí)驗(yàn)組數(shù)81每組人數(shù)1實(shí) 驗(yàn)內(nèi) 容熟練掌握迪杰斯特拉算法的應(yīng)用。具體題目：實(shí)驗(yàn)案例：根據(jù)一張自駕旅游路線圖，可以知道城市間的高速公路長度以及該公路要收取的過路費(fèi)。現(xiàn)在編寫一個(gè)程序，找出一條出發(fā)地和目的地之間的最短路徑。如果有若干條路徑都是最短的，那么需要輸出過路費(fèi)最少的一條路徑。（1）輸入說明：輸入第1行給出4個(gè)正整數(shù)N,M,S,D，其中N（2N500）是城市的個(gè)數(shù)，順便假設(shè)城市的編號(hào)為0（N-1）；M是高速公路的條數(shù)；

11、S是出發(fā)地的城市編號(hào)；D是目的地的城市編號(hào)。隨后M行，每行給出一條高速公路的信息，分別是：城市1、城市2、高速公路長度、收費(fèi)額，中間以空格分隔，數(shù)字均為整數(shù)且不超過500.輸入保證解的存在。（2）輸出說明：在一行中輸出路徑長度和收費(fèi)總額，數(shù)字間以空格分隔，輸出結(jié)尾不能有多余空格。名 稱型 號(hào)數(shù) 量儀器設(shè)備PC機(jī)VC+6.0聯(lián)想8181低值耐用品名 稱 及 消 耗 額備 注消耗材料實(shí)驗(yàn)室主任: 填卡人: 萬厚沖 填卡日期: 2012.9.10實(shí) 訓(xùn) 項(xiàng) 目 卡數(shù)學(xué)與計(jì)算機(jī)科學(xué)系 計(jì)算機(jī)實(shí)驗(yàn)室 計(jì)算機(jī)機(jī)房 分室實(shí)驗(yàn)序號(hào)7實(shí)驗(yàn)名稱整型關(guān)鍵字的散列映射實(shí)驗(yàn)類別基礎(chǔ)課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)類型驗(yàn)證性實(shí)驗(yàn)者類

12、別本科計(jì)劃學(xué)時(shí)2實(shí)驗(yàn)要求必做實(shí)驗(yàn)組數(shù)81每組人數(shù)1實(shí) 驗(yàn)內(nèi) 容（1）熟練掌握除留余數(shù)法散列映射。（2）熟練掌握用線性探測(cè)解決沖突的機(jī)制。實(shí)驗(yàn)案例：給定一系列整型關(guān)鍵字和素?cái)?shù)P，用除留余數(shù)法定義的散列函數(shù)H（key）=Key % P 將關(guān)鍵字映射到長度為P的散列表中。用線性探測(cè)法解決沖突。（1）輸入說明：輸入第1行首先給出兩個(gè)正整數(shù)N（N1000）和P（N的最小素?cái)?shù)），分別為待插入的關(guān)鍵字總數(shù)以及散列表的長度。第2行給出N個(gè)整型關(guān)鍵字。數(shù)字間以空格分隔。（2）輸出說明：在一行內(nèi)輸出每個(gè)整型關(guān)鍵字在散列表中的位置。數(shù)字間以空格分隔，但行末尾不得有多余空格。名 稱型 號(hào)數(shù) 量儀器設(shè)備PC機(jī)VC+6.

13、0聯(lián)想8181低值耐用品名 稱 及 消 耗 額備 注實(shí)驗(yàn)室主任: 填卡人: 萬厚沖 填卡日期: 2012.9.10實(shí) 訓(xùn) 項(xiàng) 目 卡數(shù)學(xué)與計(jì)算機(jī)科學(xué)系 計(jì)算機(jī)實(shí)驗(yàn)室 計(jì)算機(jī)機(jī)房 分室實(shí)驗(yàn)序號(hào)8實(shí)驗(yàn)名稱模擬Excel排序?qū)嶒?yàn)類別基礎(chǔ)課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)類型驗(yàn)證性實(shí)驗(yàn)者類別本科計(jì)劃學(xué)時(shí)2實(shí)驗(yàn)要求必做實(shí)驗(yàn)組數(shù)81每組人數(shù)1實(shí) 驗(yàn)內(nèi) 容熟練掌握快速排序的庫函數(shù)調(diào)用。實(shí)驗(yàn)案例：Excel可以對(duì)一組記錄按任意指定列排序?，F(xiàn)編寫程序?qū)崿F(xiàn)類似功能。（1）輸入說明：輸入第1行包含兩個(gè)正整數(shù)N（N105）和C，其中N是記錄的條數(shù)，C是指定排序的列號(hào)。之后有N行，每行包含一條學(xué)生記錄。每條學(xué)生記錄由學(xué)號(hào)（6位數(shù)字，保證沒有重復(fù)學(xué)號(hào)）、姓名（不超過8位且不包含空格的字符串）、成績（0,100