〈數(shù)據(jù)結(jié)構(gòu)〉上機實驗指導(dǎo)-資料下載頁
2025-06-29 09:18本頁面
【正文】 常用的應(yīng)用方法。 實驗學(xué)時：建議2~4學(xué)時實驗內(nèi)容內(nèi)容1： 圖的搜索問題【問題描述】設(shè)計一個程序，演示在連通的無向圖上訪問全部結(jié)點的操作?！净疽蟆浚?）以鄰接表作為存儲結(jié)構(gòu)，并圖進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索。（2）以用戶指定的結(jié)點為起點，分別輸出每種搜索方式下的結(jié)點訪問序列和相應(yīng)生成樹的邊集?！緦崿F(xiàn)提示】（1）圖的每個結(jié)點用一個編號表示（如1~n）。通過輸入圖的全部邊來輸入一個圖，每個邊是一個數(shù)對。（2）數(shù)據(jù)結(jié)構(gòu)描述見教材。（3）可設(shè)計以下三個函數(shù)過程：void createadjlist( amp。T)；//建立圖的鄰接表void desttraverse(T)；//圖的深度優(yōu)先搜索void besttraverse(T)；//圖的廣度優(yōu)先搜索【選做內(nèi)容】借助棧，用非遞歸算法實現(xiàn)深度優(yōu)先搜索。內(nèi)容2： 教學(xué)計劃編制問題【問題描述】教學(xué)計劃中各課程之間必須滿足先修關(guān)系。每門課程的先修課程是確定的，可以有任意多門，也可以沒有。試在這樣的前提下設(shè)計一個教學(xué)計劃編制的程序?！净疽蟆浚?）輸入數(shù)據(jù)包括：學(xué)期總數(shù)、一學(xué)期的學(xué)分上限、課程號、課程學(xué)分和直接先修課程的課程號。（2）編排策略：使每學(xué)期的總學(xué)分?jǐn)?shù)盡量均勻?！緦崿F(xiàn)提示】可設(shè)學(xué)期總數(shù)不超過12，課程總數(shù)不超過100?！具x做內(nèi)容】產(chǎn)生多種不同的方案，并使方案之間的差異盡可能大。 實驗五 查找實驗?zāi)康?．熟練掌握順序表和有序表的查找方法及算法實現(xiàn)。2．熟悉常用查找算法的編寫。3．理解靜態(tài)查找和折半查找的關(guān)系。4．熟練掌握二叉排序樹的構(gòu)造和查找方法。5．通過上機操作,理解如何科學(xué)地組織信息存儲,并選擇高效的查找算法。實驗學(xué)時：建議2學(xué)時實驗內(nèi)容內(nèi)容1： 基本查找算法【問題描述】設(shè)計一個程序，演示折半查找和二叉排序樹查找過程?！净疽蟆浚?）建立一棵二叉排序樹，采用二叉鏈表存儲結(jié)構(gòu)，并進(jìn)行查找。（2）給出一組有序數(shù)，對其進(jìn)行折半查找?！緦崿F(xiàn)提示】（1）可設(shè)計以下三個功能函數(shù)：status insertbst(bitree amp。bt,elemtype e)。//,插入e 并返回truesearchebst(bitree bt,keytype key)。//在根指針bt所指二叉樹中遞歸地查找關(guān)鍵字等于key的數(shù)據(jù)元素,若查找成功,則返回指向該數(shù)據(jù)元素結(jié)點的指針,否則返回空指針。int Search_Bin(SSTable ST，keytype key)；//折半查找算法（2）可設(shè)計遞歸算法?！具x做內(nèi)容】設(shè)計非遞歸算法。內(nèi)容2： 哈希表設(shè)計【問題描述】針對某集體中的“人名”設(shè)計一個哈希表，完成相應(yīng)的建表和查表程序?！净疽蟆浚?）人名用漢語拼音，待填入哈希表的人名共30個。（2）哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法處理沖突?！緦崿F(xiàn)提示】（1） 數(shù)據(jù)結(jié)構(gòu)設(shè)計人名用指向字符的指針表示，因而哈希表可設(shè)計成線性結(jié)構(gòu)（即指針組）。（2） 設(shè)計以下的功能函數(shù)：status create_hash(H)。// 哈希表的建表操作int search_hash (H ,name)。// 哈希表的查表操作【選做內(nèi)容】（1） 用鏈地址法處理沖突。（2） 通過分析給定人名的特點，設(shè)計出具有不（或較少）沖突的哈希函數(shù)。 實驗六 排序?qū)嶒災(zāi)康?．深刻理解排序的定義和各種排序方法的特點。2．了解各種方法的排序過程及其依據(jù)的原則。3．熟練掌握各種排序方法的時間復(fù)雜度的分析方法。4．了解排序的過程及適用場合。5．了解排序效果與采用算法的關(guān)系。6．通過上機,加深對排序算法的理解.實驗學(xué)時：建議2學(xué)時實驗內(nèi)容：內(nèi)部排序算法比較【問題描述】設(shè)計一個程序，通過隨機數(shù)據(jù)比較常用排序算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)?！净疽蟆浚?）對以下排序算法進(jìn)行比較：起泡排序、簡單選擇排序、直接插入排序、快速排序。（2）用隨機數(shù)進(jìn)行排序；至少用5組不同數(shù)據(jù)進(jìn)行比較。（3）最后進(jìn)行簡單分析?！緦崿F(xiàn)提示】在算法的適當(dāng)位置插入對關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)的統(tǒng)計操作?！具x做內(nèi)容】對不同表長作試驗，觀察兩指標(biāo)的變化情況。20
試題試卷相關(guān)推薦
鄂ICP備17016276號-1