數(shù)據(jù)結構與算法 實驗教學大綱

數(shù)據(jù)結構與算法實驗教學大綱一、課程性質與基本要求數(shù)據(jù)結構與算法是計算機類專業(yè)的一門重要基礎課程，是一門理論與工程實踐緊密結合的綜合性課程，它是研究非數(shù)值計算程序設計問題中計算機的操作對象、對象間關系以及常用算法實現(xiàn)原理的課程。通過課程學習和實驗，加深學生對數(shù)據(jù)結構和算法理論知識的理解，學會如何分析數(shù)據(jù)結構的特征，為不同的應用場景選擇設計合適的邏輯結構、存儲結構以及相應的算法。在實驗過程中要求學生編寫符合軟件工程規(guī)范的程序，以培養(yǎng)其數(shù)據(jù)抽象能力和算法設計能力，為后續(xù)課程學習和實際工作打下堅實的基礎。二、課程目標本實驗教材主要涉及如何合理地組織數(shù)據(jù)、有效地存儲和處理數(shù)據(jù)，正確地設計算法以及對算法的分析和評價。通過實驗，使學生深刻理解數(shù)據(jù)的邏輯結構和物理結構的基本概念以及有關算法，提高程序設計與實現(xiàn)能力。實驗目標如下：目標1：理解數(shù)據(jù)的物理結構和邏輯結構，具有對抽象數(shù)據(jù)類型的理解能力。目標2：掌握常用的數(shù)據(jù)結構和算法，能根據(jù)實際問題構建合適的數(shù)據(jù)模型，選擇或構思合適的算法。目標3：能根據(jù)構思的數(shù)據(jù)模型和算法編寫具有良好風格的實際可運行程序，并對算法的復雜度進行分析。三、實驗環(huán)節(jié)教學安排序號實驗項目名稱實驗目的實驗內(nèi)容學時1順序表的建立及操作1.掌握線性表的順序存儲結構。2.掌握順序表基本操作的算法實現(xiàn)。3.了解順序表的應用。任務1：按表格的方式打印顯示序順序表L中的所有信息。任務2：寫一個函數(shù)刪除順序表L中某一元素。任務3：在有序的順序表中加入元素后，使表仍然有序。任務4：將線性表中L的數(shù)據(jù)保存到一個磁盤文件中。22鏈表的建立及操作1.掌握線性表的鏈式存儲結構的表示和實現(xiàn)方法。2.掌握鏈表基本操作的算法實現(xiàn)。任務1：在單鏈表L中的第i個學生后面插入一個新學生stu。任務2：統(tǒng)計單鏈表L中高等數(shù)學大于x并且大學英語大于x的學生人數(shù)。任務3：在任務2的基礎上，將單鏈表L中高等數(shù)學成績和大學英語成績在min_score到max_score之間的學生組織成一個新的單鏈表L2。任務4（選做題）：編程實現(xiàn)在帶頭結點的雙向循環(huán)鏈表中插入和刪除元素。23棧的建立及操作1．掌握棧的存儲結構的表示和實現(xiàn)方法。2．掌握棧的入棧和出棧等基本操作的算法實現(xiàn)。任務1：兩棧共享空間，設計兩棧共享空間的數(shù)據(jù)結構，然后完成初始化算法、入棧、出棧等算法。任務2：五子棋游戲中悔棋操作，設計一個悔棋的數(shù)據(jù)結構并設計相關算法。任務3（選做題）：象棋游戲中的悔棋操作，設計一個悔棋的數(shù)據(jù)結構和相關算法。任務4（選做題）：表達式求值，實現(xiàn)算術表達式的求值問題，假設表達式中只含加、減、乘、除四種運算符。24隊列的建立及操作1．掌握隊列存儲結構的表示和實現(xiàn)方法。2．掌握隊列的入隊和出隊等基本操作的算法實現(xiàn)。任務1：使用隊列打印楊輝三角，寫一個函數(shù)打印楊輝三角前n行。任務2：設計一個銀行排隊叫號系統(tǒng)，能模擬顧客到達取號、銀行工作人員準備接待下一位顧客，系統(tǒng)檢測隊列長度、顧客預計等待時間等。任務3：寫一個模擬程序實現(xiàn)鍵盤輸入循環(huán)緩沖區(qū)。假設有兩個進程同時存在于一個應用程序中，其中一個進程在屏幕上連續(xù)顯示字符‘A’，與此同時，程序不斷檢測鍵盤是否有輸入，如果有輸入就讀入用戶輸入的字符并保存到緩沖區(qū)中。在用戶輸入時，鍵入的字符并不立即回顯在屏幕上。當用戶鍵入一個逗號“，”時表示第一個進程結束，第二個進程從緩沖區(qū)中讀取那些已鍵入的字符并顯示在屏幕上。第二個進程結束后，程序又進入第一個進程，重新顯示字符“A”，同時用戶又可以繼續(xù)鍵入字符，直到用戶輸入一個分號“；”鍵，才結束第一個進程，同時也結束整個進程。25二叉樹的建立及操作1．理解二叉樹的類型定義與性質。2.掌握二叉樹的二叉鏈表存儲結構的表示和實現(xiàn)方法。3．掌握二叉樹遍歷操作的算法實現(xiàn)。任務1：設計一個函數(shù)，根據(jù)二叉樹的先序遍歷序列和中序遍歷序列建立二叉樹。例如已知先序遍歷序列ABCDEFGH和中序遍歷序列BDCEAFHG，建立該二叉樹。任務2：實現(xiàn)二叉樹中序遍歷的非遞歸操作，設計一個函數(shù)，用非遞歸方法實現(xiàn)對任務1建立的二叉樹進行中序遍歷。任務3：給定兩棵二叉樹，判斷兩棵二叉樹是否相等。任務4（選做題）：編程求從二叉樹根結點到指定結點p之間的路徑。26圖的建立及操作1．掌握圖的相關概念。2．掌握用鄰接矩陣和鄰接表的方法描述圖的存儲結構。3．掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷的方法及其實現(xiàn)方法。4．掌握最小生成樹算法。5.掌握最短路徑算法。任務1：用鄰接表作為圖的存儲結構建立一個無向圖。任務2：在任務1建立的無向圖鄰接表的基礎上，對圖進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列，并分析算法的時間復雜度。任務3（選做題）：用鄰接矩陣作為圖的存儲結構建立一個連通網(wǎng)，并構造該網(wǎng)的最小生成樹。任務4（選做題）：校園導航系統(tǒng)。用無向圖表示你所在學校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求實現(xiàn)如下功能：（1）查詢各景點的相關信息。（2）查詢圖中任意兩個景點間的最短路徑。（3）查詢圖中任意兩個景點間的所有路徑。27查找1.理解基于不同查找結構的查找技術。2.掌握順序查找算法。3.掌握二分查找算法。4.掌握索引查找算法。任務1：二分查找（非遞歸算法），用二分查找的非遞歸算法實現(xiàn)范例2。任務2：二叉排序樹，編程實現(xiàn)如下功能。（1）按照輸入的n個關鍵字序列順序建立二叉排序樹，二叉排序樹采用二叉鏈表的存儲結構。（2）先輸入待查找記錄的關鍵字值key，然后在二叉排序樹上查找該記錄，如果在二叉排序樹中存在該記錄，則顯示“找到”的信息，否則顯示“找不到”的信息。（3）輸入待插入記錄的關鍵字值key，然后在二叉排序樹上查找該記錄，如果查找失敗，則在二叉排序樹中插入該記錄對應的結點，并輸出插入操作后的二叉排序樹（以某種遍歷序列表示）。（4）輸入待刪除記錄的關鍵字值key，然后在二叉排序樹上查找該記錄，如果查找成功，則在二叉排序樹中刪除該記錄對應的結點，并輸出刪除操作后的二叉排序樹（以某種遍歷序列表示）。假設二叉排序樹中元素的關鍵字值類型為int。任務3：分塊查找（選做），編程實現(xiàn)如下功能。（1）建立索引查找表。（2）利用索引查找確定給定記錄在索引查找表中的塊號和在塊中的位置。28排序1.掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法。2.理解排序的定義和各種排序方法的特點，并能加以靈活應用。3.了解各種方法的排序過程及其時間復雜度的分析方法。任務1：建立順序表，輸入n個學生的姓名和成績，將該順序表作為待排序序列，利用直接選擇排序對待排序序列按成績從高到低進行排序，并輸出排序后的結果，并分析算法的時間和空間復雜度。任務2：建立順序表，輸入n個學生的姓名和成績，將該順序表作為待排序序列，利用希爾排序對待排序序列按成績從高到低進行排序，并輸出排序后的結果，并分析算法的時間和空間復雜度。任務3：建立順序表，輸入n個學生的姓名和成績，將該順序表作為待排序序列，利用2路歸并排序對待排序序列按成績從高到低進行排序，并輸出排序后的結果，并分析算法的時間和空間復雜度。29貪心算法1.理解貪心算法中貪心選擇性質。2.對于給定的問題，識別是否適合用貪心算法求解。3.理解貪心算法的局限性，在某些時候貪心算法只能提供近似解。任務1：用貪心策略求解最優(yōu)裝載問題。有n個集裝箱1、2、…、n需要裝上輪船，集裝箱i的重量wi，輪船裝載重量限制為C，每個集裝箱的重量小于C（wi≤C）,無體積限制，問如何裝使得輪船上的集裝箱個數(shù)最多。任務2：用貪心策略解決最小延遲調(diào)度問題。給定等待服務的客戶集合A={1,2,…,n}，各客戶的服務時間T=(t1,t2,…,tn)，其中客戶i的服務時間為ti（ti>0），各客戶的期望完成時刻D=(d1,d2,…,dn)，其中客戶i期望的服務完成時刻為di（di>0）。一個調(diào)度f：A->N，f(i)為客戶i的開始時刻。如果對客戶i的服務在di之前結束，那么客戶i的服務沒有延遲，如果在di之后結束，那么這個服務就被延遲了，延遲的時間等于該服務的實際完成時刻f(i)+ti減去預期結束時刻di。一個調(diào)度f的最大延遲是所有客戶延遲時長的最大值max{f(i)+ti-di}。要求找出一個調(diào)度使得最大延遲達到最小。210回溯法1.理解回溯法的基本原理。2.掌握如何定義問題的狀態(tài)空間樹以及如何在樹中進行深度優(yōu)先搜索來尋找可行解或最優(yōu)解。3.理解剪枝策略。任務1：利用回溯算法求解0-1背包問題。給定n種物品和一個背包。第i種物品重量為wi，其價值為vi，其中i=1,2,3,…,n。背包的容量為c。問如何選擇放入背包的物品，使得放入背包的物品的總價值最大。任務2：利用回溯算法求解旅行售貨員問題。某售貨員要到n個城市去推銷商品，已知各城市之間的路程(或旅行所需的費用)。要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到駐地的路線，使總的路程(或總旅費)最小。211動態(tài)規(guī)劃算法1.理解動態(tài)規(guī)劃算法中的最優(yōu)子結構和重疊子問題性質。2.理解動態(tài)規(guī)劃的核心概念，即通過將復雜問題分解為更小的、相互關聯(lián)的子問題來求解，并存儲這些子問題的結果以避免重復計算。3.掌握動態(tài)規(guī)劃算法的實際應用方法。任務1：最大子數(shù)組問題，給定一個數(shù)組X[1..n]，對于任意一對數(shù)組下標為l、r（l≤r）的非空子數(shù)組，其和記為：S求S(l,r)的最大值。任務2：求最長公共子序列，X的子序列是將序列X中零個或多個元素去掉后所得的序列。給定序列X和序列Y，求X和Y的最長公共子序列。2四、實驗評分標準實驗項目基本評分標準如下。實驗評分標準100~90分89~80分79~70分69~60分59~0分能夠對給定的實際問題抽象正確的數(shù)據(jù)模型；可以分析、選擇、設計、優(yōu)化存儲結構；針對問題正確設計滿足時間、空間約束條件的算法；算法實現(xiàn)正確，實驗報告撰寫規(guī)范；能夠對實驗結果進行分析。能夠對給定的實際問題抽象正確的數(shù)據(jù)模型；可以分析、選擇、設計合適的存儲結構；可針對問題設計滿足時間、空間約束條件的算法；算法實現(xiàn)正確，實驗報告撰寫規(guī)范；能夠對給定的實際問題抽象數(shù)據(jù)模型；可分析、選擇合適的存儲結構；算法設計合理，滿足題目約束條件；算法實現(xiàn)正確，實驗報告撰寫較規(guī)范。能夠對給定的實際問題抽象數(shù)據(jù)模型；算法設計基本滿足題目約束條件；算法實現(xiàn)基本正確，實驗報告撰寫基本滿足規(guī)范。沒有完成實驗任務，實驗報告撰寫存在較大的缺陷。五、課程思政在教學過程中，可從科技強國、科學素養(yǎng)、工匠精神、職業(yè)道德等方面融入思政內(nèi)容。介紹數(shù)據(jù)結構與算法在重大項目中的應用，如云計算、大數(shù)據(jù)分析等領域的創(chuàng)新應用，強調(diào)算法創(chuàng)新對