遼寧省高等教育自學考試軟體技術專業（應用本科）
一、課程性質與設定目的
（一）課程性質、特點和設定目的
《演算法與資料結構（實踐）》課程是與《演算法與資料結構》課程所對應的一門實踐課。通過本課程的學習，使應考者能夠全面理解演算法與資料結構在實際應用中的地位和作用，熟練掌握演算法設計與分析中的基本概念和基本設計與分析方法，熟練掌握運用資料結構進行程式設計的基本方法和基本技能，培養將原理應用於實際的能力，提高軟體設計、演算法應用、程式設計及除錯的綜合素質，為今後的應用軟體程式設計打下堅實的基礎。
（二）本課程的基本要求
通過本課程的學習，達到如下目標:
1. 掌握線性結構、樹形結構和圖形結構等基本資料結構及演算法的應用；
2. 掌握分治技術、貪心技術、回溯和分支限界等經典演算法設計技術及應用；
3. 熟練掌握搜尋演算法和排序演算法的應用；
4. 具備應用演算法與資料結構開發簡單應用軟體的能力。
二、課程內容與考核要求
第一部分實驗
實驗1 順序表的應用
（一）實驗內容
1. 建立和銷毀順序表儲存結構。
2. 實現順序表的基本操作，如插入、刪除、查詢和遍歷等。
3. 順序表的簡單應用，如分數統計、有序表的查詢與合併、字典比較等。
（二）考核知識點及考核要求
1. 建立和銷毀順序表儲存結構，要求達到「熟練掌握」層次。
2. 實現順序表的基本操作，要求達到「熟練掌握」層次。
3. 順序表的簡單應用，要求達到「基本掌握」層次。
實驗2 鍊錶的應用
（一）實驗內容
1. 建立和銷毀鍊錶儲存結構。
2. 實現鍊錶的基本操作，如插入、刪除、查詢和遍歷等。
3. 鍊錶的簡單應用，如約瑟夫環、集合求並、一元多項式相加等。
（二）考核知識點及考核要求
1. 建立和銷毀鍊錶儲存結構，要求達到「熟練掌握」層次。
2. 實現鍊錶的基本操作，要求達到「熟練掌握」層次。
3. 鍊錶的簡單應用，要求達到「基本掌握」層次。
實驗3 棧和佇列的應用
（一）實驗內容
1. 建立和銷毀棧和佇列的儲存結構。
2. 實現棧和佇列的基本操作，如入棧、出棧、入隊、出隊、取棧頂和隊頭元素等。
3. 棧和佇列的簡單應用，如停車場管理、配對問題、算術表示式求值、迷宮問題等。
（二）考核知識點及考核要求
1. 建立和銷毀棧和佇列的儲存結構，要求達到「熟練掌握」層次。
2. 實現棧和佇列的基本操作，要求達到「熟練掌握」層次。
3. 棧和佇列的簡單應用，要求達到「基本掌握」層次。
實驗4 樹和二叉樹的應用
（一）實驗內容
1. 建立和銷毀二叉樹的儲存結構。
2. 實現二叉樹的基本操作，如查詢和遍歷等。
3. 二叉樹的簡單應用，如線索二叉樹、哈夫曼樹和表示式樹等。
4. 樹轉化為二叉樹的儲存結構的建立和銷毀。
5. 樹與森林的遍歷演算法。
6. 樹的簡單應用，如網際網路查詢等。
（二）考核知識點及考核要求
1. 建立和銷毀二叉樹的儲存結構，要求達到「熟練掌握」層次。
2. 實現二叉樹的基本操作，要求達到「熟練掌握」層次。
3. 二叉樹的簡單應用，要求達到「熟練掌握」層次。
4. 樹轉化為二叉樹的儲存結構的建立和銷毀，要求達到「基本掌握」層次。
5. 樹與森林的遍歷演算法，要求達到「基本掌握」層次。
6. 樹的簡單應用，要求達到「基本掌握」層次。
實驗5 圖的應用
（一）實驗內容
1. 圖的鄰接表和鄰接矩陣儲存結構的建立和銷毀。
2．實現圖的基本操作，如查詢和遍歷等。
3．圖的應用，如最小生成樹、單源最短路徑、拓撲排序等。
（二）考核知識點及考核要求
1. 圖的鄰接表和鄰接矩陣儲存結構的建立和銷毀，要求達到「熟練掌握」層次。
2．實現圖的基本操作，要求達到「熟練掌握」層次。
3．圖的應用，要求達到「基本掌握」層次。
實驗6 雜湊表的應用
（一）實驗內容
1. 雜湊表儲存結構的建立和銷毀。
2．實現雜湊表的基本操作，如插入、刪除和查詢等。
3．解決雜湊衝突方法的應用，如開放位址法和鏈位址法等。
（二）考核知識點及考核要求
1. 雜湊表儲存結構的建立和銷毀，要求達到「熟練掌握」層次。
2．實現雜湊表的基本操作，要求達到「熟練掌握」層次。
3．解決雜湊衝突方法的應用，要求達到「基本掌握」層次。
實驗7 排序的應用
（一）實驗內容
1．插入排序的應用，如直接插入排序、有序表排序等。
2．交換排序的應用，如氣泡排序、快速排序等。
3．選擇排序的應用，如直接選擇排序、堆排序等。
4．歸併排序的應用，如二路歸併排序等。
（二）考核知識點及考核要求
1．插入排序的應用，要求達到「熟練掌握」層次。
2．交換排序的應用，要求達到「熟練掌握」層次。
3．選擇排序的應用，要求達到「熟練掌握」層次。
4．歸併排序的應用，要求達到「熟練掌握」層次。
實驗8 典型演算法的應用
（一）實驗內容
1．分治演算法的應用，如靜態二分查詢、順序統計和二叉排序樹等。
2．貪心演算法的應用，如會議日程安排、0/1揹包問題等。
3．動態規劃演算法的應用，如最長公共子串行、關鍵路徑等。
4．回溯與分支限界演算法的應用，如迷宮問題、旅行售貨員問題等。
（二）考核知識點及考核要求
1．分治演算法的應用，要求達到「基本掌握」層次。
2．貪心演算法的應用，要求達到「基本掌握」層次。
3．動態規劃演算法的應用，要求達到「基本掌握」層次。
4．回溯與分支限界演算法的應用，要求達到「基本掌握」層次。
第二部分綜合應用
（一）課題內容
根據現實問題，運用演算法與資料結構技術，開發乙個比較複雜的應用系統，並經歷以下幾個階段：
1．設計抽象資料型別。
2．設計資料結構模型。
3．設計系統功能模組。
4．設計問題的主演算法。
5．實現抽象資料型別。
6．程式設計和除錯。
7．書寫程式文件。
（二）考核知識點及考核要求
1．設計抽象資料型別，要求達到「基本掌握」層次。
2．設計資料結構模型，要求達到「熟練掌握」層次。
3．設計系統功能模組，要求達到「基本掌握」層次。
4．設計問題的主演算法，要求達到「熟練掌握」層次。
5．實現抽象資料型別，要求達到「熟練掌握」層次。
6．程式設計和除錯，要求達到「基本掌握」層次。
7．書寫程式文件，要求達到「基本掌握」層次。
三、有關說明與實施要求
（一）關於「考核要求」 中三個「能力層次」的說明
考核知識點與考核要求用「初步掌握」、「基本掌握」、和「熟練掌握」三個能力層次加以區分，具體解釋如下：
初步掌握：要求能夠運用本課程中規定的部分知識點，採用簡單的方法和技能，分析和解決一般的應用問題。
基本掌握：要求能夠運用本課程中規定的多個知識點，採用一般的方法和技能，分析和解決典型的應用問題。
熟練掌握：要求能夠靈活運用本課程中規定的多個知識點，盡可能採用多種方法和技能，分析和解決較複雜的應用問題。
（二）自學參考教材
《資料結構題集》（c語言版）嚴蔚敏、吳偉民編著
清華大學出版社 2023年2月
《資料結構及應用演算法教程》嚴蔚敏、陳文博編著
清華大學出版社 2023年2月
（三）自學方法指導
1．認真閱讀與鑽研大綱與教材。應考者應根據本大綱規定的考核目標，認真學習教材，全面系統地掌握教材所闡述的基本原理、基本方法和基本技能。
2．系統學習和重點深入相結合。應考者應在全面系統學習教材的基礎上，對重點內容進行深入的學習和練習，學會基本方法，以便更好地把握本課程的全部內容。
3. 實驗和實訓相結合。實驗著重於消化各個單元內容，而實訓則著重於提高專項技能和綜合應用能力。
4. 本課程的學習，都是在上機環境下完成的，所以必須保證必要的學習時間。自學者應根據本課程的特點和自身的實際情況，合理安排自學時間。
5. 本課程要提交實驗報告和綜合應用大作業，並附加源程式。
（四）課程學分
本課程是一門實踐課程,總計3學分,其中實驗1學分，綜合應用2學分。
（五）對社會助學的要求
1.社會助學者應明確本課程的性質與設定要求，根據本大綱規定的課程內容
和考核目標，把握指定教材的基本內容，對應考者進行切實有效的訓練和輔導，引導他們掌握正確的學習方法，防止自學中的各種偏向，體現社會助學的正確導向。
2.要正確處理基本原理、基本概念和基本知識同應用能力的關係，努力引導應考者將基礎理論知識轉化為認識、分析和解決實際問題的能力。
3.要正確處理重點和一般的關係。社會助學者應根據這門課程和考試命題的特點，指導應考者全面系統地學習教材，掌握全部課程內容和考核目標。
4.注意安排上機實踐內容，做好單元練習和綜合應用練習的學時比例分配。
5．社會助學者要有專業的實習指導教師。
（六）關於課程考試的若干規定
1.本課程考試分為平時成績和上機考試兩部分，其中平時成績佔30%，上機考試成績佔70%。
2.平時成績以提交的實驗報告和二個綜合應用作業為依據，由實習指導教師評定。
3.本課程的上機命題考試，應根據本大綱規定的課程內容和考核目標，來確定考試範圍和考核要求，不要任意擴大或縮小考試範圍，提高或降低考核要求。
4. 本課程的上機命題考試內容分為兩部分，簡單應用題和綜合應用題。其中簡單應用題佔30%，綜合應用題佔70%。考試中，應有適當的口試。
5.要合理安排上機命題考試試卷的難度結構。試題的難度分為較易和較難兩種。簡單應用題試題的難度為較易，綜合應用題試題的難度為較難。具體題型樣式可參見本大綱附錄。
6.本課程上機考試時間為180分鐘，試題量應以中等水平的自學應考者在規定時間內答完全部試題為度。
（七）題型舉例
《演算法與資料結構（實踐）》上機試題
一、簡單應用題
應用迴圈佇列編寫乙個列印二項式係數表（即楊輝三角形）的演算法。
二、綜合應用題
設有一組關鍵字
採用雜湊函式 h（key）=key mod 13,並採用開放位址的線性探測再雜湊方法解決衝突，試程式設計實現在0—18的雜湊位址空間中對該關鍵字序列構造雜湊表（要求有計算過程），並求出在等概率情況下，查詢成功時的平均查詢長度。
演算法與資料結構
演算法 是按部就班地解決某個問題的方法，是對特定問題求解步驟的一種描述。偽碼語言是一種包括高階程式語言的3種基本控制結構 順序 選擇和迴圈 和自然語言成分的 物件導向 的語言。演算法的特徵 1 可行性 一是演算法中的每個步驟必須是能實現的 二是演算法執行的結果要能達到預期的目的。2 確定性 演算法的...
資料結構與演算法
課程設計報告 目錄一 問題描述1 二 資料結構1 三 演算法設計思想及流程圖1 四 源程式2 五 測試情況6 參考文獻6 一 問題描述 計算表示式的值 問題描述 對於給定的乙個表示式，表示式中可以包括常數 算術執行符和括號，編寫程式計算表示式的值。基本要求 從鍵盤輸入乙個正確的中綴表示式，將中綴表示...
資料結構與演算法信
美國uiuc大學博士生梅俏竹 資料結構是美國所有一流計算機系的本科核心課程之一，上承計算引論與初級程式設計，下啟高階演算法和計算理論，向來是計算機本科教學的重中之重。我在北大上過的諸多本科基礎課中，無論從課程內容和老師教學下的功夫來看，張銘老師的 資料結構與演算法 課程都是首屈一指的。可以說，將北大...