數據結構與算法分析課程設計

由 故事會 分享時間：2024-05-12 04:15:07 加入收藏我要投稿點贊

在日常的學習、工作、生活中，肯定對各類范文都很熟悉吧。那么我們該如何寫一篇較為完美的范文呢？以下是小編為大家收集的優秀范文，歡迎大家分享閱讀。

數據結構與算法分析課程設計篇一

《數據結構與算法課程設計》任務書

一、課程設計目的

數據結構與算法課程設計是《數據結構與算法》課程教學必不可缺的一個重要環節，它可加深學生對該課程所學內容的進一步的理解與鞏固，是將計算機課程與實際問題相聯接的關鍵步驟。通過課程設計，能夠提高學生分析問題、解決問題，從而運用所學知識解決實際問題的能力，因而必須給予足夠的重視。

2二、課程設計題目

2.1 棋盤覆蓋

【間題描述】

在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態的l型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個l型骨牌不得重疊覆蓋。

【基本要求】

（1）輸入k以及特殊方格所在的行號dr和特殊方格的列號dc。

1（2）要求輸出每一步用什么形態l型骨牌覆蓋，覆蓋后得到的棋盤圖形。（3）如果輸出的結果只是用矩陣表示則為良好，用圖形表示則為優。【測試數據】【實現提示】

使用分治策略，把棋盤劃分成4個小棋盤，然后用一個l型骨牌覆蓋將這4個小棋盤變為都具有特殊方格的棋盤。

2.2 hanoi塔問題（*）

【問題描述】

設a，b，c是三個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊放在一起，各圓盤從小到大編號為1,2,?,n，要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規則：

規則（1）每次只能移動一個圓盤；

規則（2）任何時刻都部允許將較大的圓盤壓在較小的圓盤之上；

規則（3）在滿足移動規則（1）和（2）的前提下，可將圓盤移至a，b，c中任一塔座上。

【基本要求】

（1）設計出hannoi塔游戲，供用戶玩；（2）提供正確的搬運方法。【實現說明】

正確的搬運方法使用遞歸方法實現。【測試數據】

2.3 矩陣連乘問題

【問題描述】

給定n個矩陣{a1,a2,...,an},其中ai和ai?1是可乘的，i＝1,2,?,n-1。考察這n個矩陣的連乘積a1a2,...,an，通過加括號方式，找出矩陣乘積所需的最少計算量的方法。

【基本要求】

輸入每個矩陣的行和列，要求輸出最少計算量的矩陣乘積方法，如(a1(a2(a3a4)))。【實現說明】使用動態規劃方法。

2.4 多邊形游戲（*）

【問題描述】

多邊形游戲是一個單人玩的游戲，開始時有一個由n個頂點構成的多邊形。每個頂點被賦予一個整數值，每條邊被賦予一個運算符“＋”或“*”。所有邊依次用整數從1到n編號。

游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：

選擇一條邊e及由e連接著的2個頂點v1和v2；

用一個新的頂點取代邊e及用e連接著的2個頂點v1和v2，將由頂點v1和v2的整數值通過邊e上的運算得到的結果賦予新頂點。

最后，所有邊都被刪除，游戲結束。游戲的得分就是所剩頂點上的整數值。【基本要求】

設計該游戲供用戶玩；

對于給定的多邊形，給出最高得分計算。【實現說明】使用動態規劃方法。

2.5 0-1背包問題

【問題描述】

給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為c。問應如何選擇裝入背包種的物品，使得裝入背包種物品的總價值最大。

【基本要求】

使用動態規劃、回溯法以及分支界限三種方法實現。【測試數據】【實現提示】

2.6 排序方法

【問題描述】

給定n個元素，要求對這n個元素進行排序。【基本要求】

使用多種排序方法，越多越好；

比較每種排序方法的時間復雜度和空間復雜度。【測試數據】【實現提示】

2.7 哈夫曼編碼譯碼器

【問題描述】

設計一個哈夫曼編碼/譯碼系統，對一個文本文件中的字符進行哈夫曼編碼，生成編碼文件

（壓縮文件，）；反過來，可將一個壓縮文件譯碼還原為一個文本文件(.txt)。

【基本要求】

（1）輸入一個待壓縮的英文文本文件，統計文本文件中各字符的個數作為權值，生成哈夫曼樹；

（2）將文本文件利用哈夫曼樹進行編碼，生成壓縮文件（后綴名cod）（3）輸入一個待解壓的壓縮文件名稱,并利用相應的哈夫曼樹將編碼序列譯碼。【實現說明】

（1）在構造哈夫曼樹時，可以利用不同的線性表存放二叉樹：用順序表、單鏈表、5 循環單鏈表、雙向鏈表、循環雙鏈表；

（2）在構造哈夫曼樹時，可以利用優先隊列存放二叉樹：順序隊列、鏈隊列（可以是單鏈表、雙鏈表等，還可以用靜態結構去實現），可以分別在入隊列或出隊列時實現優先級；

（3）二叉樹本身也可以用靜態數組模擬；（4）使用貪心算法

2.8 迷宮問題（*）

【問題描述】

設計一個迷宮并給出正確走法。如： *** *** *** *** *** *** *** 其中0表示可以走，1表示不能走，每一步只能向上下左右移動。【基本要求】

（1）給出迷宮的正確走法，包括沒有解的情況；（2）要求界面友好。【測試數據】

【實現提示】使用回溯的方法。

2.9 繼續郵資問題

【問題描述】

假設某國家發行了n種不同面值的郵票，并且規定每張信封上最多只允許貼m張郵票。連續郵資問題要求對于給定的n和m的值，給出郵票面值的最佳設計，在1張信封上貼出從郵資1開始，增量為1的最大連續郵資區間。

【基本要求】

輸入任意的m和n都能設計出最佳的方案，并給出連續郵資區間。【實現說明】【測試數據】

2.10 圖的m著色問題

【問題描述】

給定一個地圖，要求給出該地圖的最少著色方案【基本要求】

（1）把地圖以及最少著色的方案顯示出來則為良好。（2）有友好的界面則為優【實現說明】

2.11 猜數字游戲（*）

【問題描述】

孩子想1個由4種顏色組成的序列（4種顏色不一定完全不同）。每種顏色只能是6種顏色之一。方便起見，我們用數字1到6表示6種顏色。

計算機必須根據孩子的回答找出孩子所想的顏色序列。計算機在屏幕上顯示一個序列，孩子用鍵盤回答以下兩個問題：

猜對的顏色中位置不對的有幾個？猜對的顏色中位置對的有幾個？【基本要求】

編程使至多6次問答后猜出序列，如果辦不到，至多10次問答后猜出序列。【實現說明】【測試數據】

如孩子想的是4655 計算機猜想顏色對位置錯的數目顏色和位置都對的數目 1234 1 0 5156 2 1 6165 1 1 5625 1 2 5653 1 2 8 4655 0 4 2.12 大整數計算器

【問題描述】

設計一個計算器實現兩個任意長得整數的加、減、乘、除。【基本要求】

設計一個實現任意長的整數進行四則運算的演示程序，要求輸入任意長的整數進行四則運算，都能得到精確的結果。

【實現說明】

2.13 查找搜索技術

【問題描述】

給定任意的數組，對于給定的數，查找是否在數組中，如果在，則返回給定數在數組的位置，不在則返回不在信息。

【基本要求】

（1）使用多種搜索方法，越多越好，其中二分搜索技術、線性時間選擇是必須的；（2）比較每種排序方法的時間復雜度和空間復雜度。【實現說明】

2.14 tom,jerry和奶酪（*）

【問題描述】

貓tom和鼠jerry同住在一矩陣地窖中。貓要吃鼠，鼠要吃奶酪。地窖中有2種地磚：有洞磚與無洞磚。一個洞足以讓鼠鉆入，但貓不能。

以菜單形式完成以下任務：

隨機地生成一個地窖，并給貓、鼠和奶酪安排一個位置。如： fffffffffffffff fppppppppppppcf fhfffffffffffpf fpppjhppppppppf fpffffffpffffff fpppppppppptppf fffffffffffffff 其中c表示貓，j表示鼠，h表示洞，f表示不能通行（2）鼠先行，貓后行。兩者皆滿足以下規定： 1）必須上、下、左或右移動 2）鼠必須走1步（穿過p或h）3）貓必須走1或2步（穿過p）

（3）當鼠吃到奶酪或貓抓到鼠時，游戲結束。【基本要求】【實現說明】

2.15 布線問題

【問題描述】

印刷電路板將布線區域劃分成n×m個方格陣列，精確的電路布線問題要求確定連接方格a的中點到方格b的中點的最短布線方案。在布線時，電路只能沿著直線或直角布線。為了避免線路相交，已布了線的方格做了封鎖標記，其他線路不允許穿過被封鎖的方格。

【基本要求】（1）解決題目的問題（2）提供友好的界面【實現說明】使用分支限界法。

2.16 魔方工具包（*）

【問題描述】

一個魔方是一個由3×3×3個小立方體組成的立方體。最初立方體的6個面分別涂上不同顏色，我們稱之為“最初魔方”。魔方的每一面上的3×3個小立方體組成它的一層。

魔方所能見到的每一層（6個面）都能旋轉90，180，220或360度。所有層的旋轉軸都垂直于面且通過其中心。旋轉的結果是另一個魔方，它的所有面的顏色都改變了。

現在我們用字符來代替顏色：u=上，d=下，f=前，b=后，l=左，r=右。任何一個序列的旋轉都能表示成{u,r,f,b,l,d}中一些字符組成的字符串，其中每個字符表示它所 11 指定的面順時針旋轉90度。

【基本要求】

（1）編程完成以下3個任務（菜單形式），你可以假設任何輸入的字串長度都<=35。你的算法能處理非法輸入的情況，如：輸入輸出 l l ll ll lll lll llll “”(空串 lllll l llrrrffffrlb lllb hello “error”

（2）判斷輸入的2個字串的旋轉結果是否相同。如輸入一輸入二輸出 ru ur no rrffrrffrrffrrff ffrrffrr yes rrffrrffrrffrrff rrffrrff no（3）求出輸入字符串至少須使用幾次才能將魔方轉回到“最初魔方”（一定大于0）輸入輸出 l 4 12 dd 2 bulb 36 ruf 80 bluff 180 【實現說明】

2.17 圖的建立與輸出

【問題描述】

建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網、無向網，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出圖的鄰接矩陣。

【基本要求】

給出圖的深度優先和廣度優先遍歷算法，并給出遍歷過程的動態演示效果【實現說明】

無

2.18 圖的建立與輸出

【問題描述】

建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網、無向網，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出 13 圖的鄰接矩陣。

【基本要求】

給出圖的深度優先和廣度優先遍歷算法，并給出遍歷過程的動態演示效果。【實現說明】

無

2.19 以隊列實現的仿真技術預測理發館的經營狀況（*）

【問題描述】

理發館一天的工作過程如下：

1)理發館有n把理發椅，可同時為n位顧客進行理發。

2)理發師分三個等級（一級、二級、三級），對應不同的服務收費。3)當顧客進門時，需選擇某級別理發師，只要該級別的理發師有空椅，則可立即坐下理發，否則需排隊等候。

4)一旦該級別的理發師有顧客理發完離去，排在隊頭的顧客便可開始理發。5)若理發館每天連續營業t分鐘，求

（1）一天內顧客在理發館內的平均逗留時間；（2）顧客排隊等候理發的隊列長度平均值；

（3）營業時間到點后仍需完成服務的收尾工作時間；（4）統計每天的營業額；

（5）統計每天不同級別理發師的創收。

【基本要求】

1)模擬理發館一天的工作過程：必須采用事件驅動的離散模型（參考教科書3.5節離散事件模擬p65）；

2)每個顧客到達和下一顧客到達時間的間隔應是隨機的； 3)理發師編號、理發師級別和每天的營業時間由用戶輸入；

4)某顧客挑選某一個級別的理發師而不得時，選第一個隊列排隊等待；

5)每個顧客進門時將生成三個隨機數:(1)durtime:進門顧客理發所需服務時間（簡稱：理發時間）；(2)intertime:下一顧客將到達的時間間隔（簡稱：間隔時間）；(3)select:服務選項。

6)服務收費：應包含服務時間和理發師級別兩個因素。

7)除了輸出統計的數據外，還需要顯示理發館的狀態，可以采用文本方式（橫向顯示每張椅編號、理發師級別。縱向表示等待該理發師理發的排隊長度）。【實現說明】

用戶輸入每位理發師編號、級別號和營業的時間，結合隨機數進行測試。

2.20 防抄襲管理系統（*）

【問題描述】

對于給定的文檔，如word文檔，txt文檔等，找出文檔的相似度。【基本要求】

（1）要求找出給定的兩個文檔的相似度以及標出相似的地方（1:1）；（2）要求找出給定的一個文檔與給定的文件夾的所有文檔的相似度，以及標出相似的地方(1:n)（3）要求找出給定的文件夾下面所有文檔的相似度(n:n)。【實現說明】

給定相似文檔進行測試。

2.21.設計一個停車場管理系統，模擬停車場的運作

設計要求：通過此程序具備以下功能：

1、要求以棧模擬停車場，以隊列模擬車場 15 外的便道，按照從終端讀入的輸入數據序列進行模擬管理；

2、要求處理的數據元素包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻；

3、該系統完成以下功能：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車離去，則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費）；

4、要求棧以順序結構實現，隊列以鏈表實現。

2.22．赫夫曼編碼

設計要求：自己找一篇不少于200個單詞的英文文章，分析該文章中每一個字符的出現概率（包括標點符號，區分大小寫），根據分析結果對文章中每一個字符進行赫夫曼編碼，并將編碼原則儲于一個獨立的文本文件中。最后，根據這個編碼原則，將英文文章轉換為01 串存儲于一個文本文件中，再編寫一個解碼程序，將編碼解碼為原文件。如：英文文章為 aaabbc 則編碼規則為 a-----0 b-----10 c-----11 英文文章將被轉化為 000101011 2.23.并查集：檢查網絡

題目要求：給定一個計算機網絡以及機器間的雙向連線列表，每一條連線允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。請寫出程序判斷：任意指定兩臺計算機，它們之間是否可以進行文件傳輸？輸入要求：輸入若干測試數據組成。對于每一組測試，第1行包含一個整數n（≤10000），即網絡中計算機的總臺數，因而每臺計算機可用1到n之間的一個正整數表示。接下來的幾行輸入格式為i c1 c2或者 c或者c c1c2或者s，其中c1和c2是兩臺計算機的 16 序號，i表示在c1和c2間輸入一條連線，c表示檢查c1和c2間是否可以傳輸文件，s表示該組測試結束。

當n為0時，表示全部測試結束，不要對該數據做任何處理。

輸出要求：對每一組c開頭的測試，檢查c1和c2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。

當讀到s時，檢查整個網絡。若網絡中任意兩機器間都可以傳輸文件，則在一行中輸出“the network is connected.”，否則輸出“there are k components.”,其中k是網絡中連通集的個數。

兩組測試數據之間請輸出一空行分隔。

2.24.教學計劃編制問題（圖的應用）

[問題描述] 大學的每個專業都要制定教學計劃。假設任何專業都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序。[實現提示]

1、輸入參數應包括：學期總數，一學期的學分上限，每門課的課程號（可以是固定占3位的字母數字串）、學分和直接先修課的課程號。

2、應允許用戶指定下列兩種編排策略之一：一是使學生在各學期中的學習負擔盡量均勻；二是使課程盡可能地集中在前幾個學期中。

3、若根據給定的條件問題無解，則報告適當的信息；否則將教學計劃輸出到用戶指定的文件中。計劃的表格格式可以自己設計。

4、可設學期總數不超過12，課程總數不超過100。如果輸入的先修課程號不在該專業開設的課程序列中，則作為錯誤處理。

============================= 17 2.25.藥品銷售統計系統（排序應用）

【問題描述】

設計一系統，實現醫藥公司定期對銷售各藥品的記錄進行統計，可按藥品的編號、單價、銷售量或銷售額做出排名。【實現提示】

在本設計中，首先從數據文件中讀出各藥品的信息記錄，存儲在順序表中。各藥品的信息包括：藥品編號、藥名、藥品單價、銷出數量、銷售額。藥品編號共4位，采用字母和數字混合編號，如：a125，前一位為大寫字母，后三位為數字，按藥品編號進行排序時，可采用基數排序法。對各藥品的單價、銷售量或銷售額進行排序時，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設計中，對單價的排序采用冒泡排序法，對銷售量的排序采用快速排序法，對銷售額的排序采用堆排序法。

藥品信息的元素類型定義： typedef struct node { char num[4];/*藥品編號*/ char name[10];/*藥品名稱*/ float price;/*藥品單價*/ int count;/*銷售數量*/ float sale;/*本藥品銷售額*/ }datatype;存儲藥品信息的順序表的定義： typedef struct { datatype r[maxsize];int length;}sequenlist;

2.26梯運行仿真程序

[問題描述] 辦公大樓有若干層（例如，十層），每層有電梯，同時有步行樓梯；

全樓有若干部（例如，不多于10部）電梯同時供使用，電梯容量為24人，速度每上下一層需5秒，在某一層停下至少15秒。其運行狀態可分：向上、向下、停止，當前乘客數，當前所在層數。它設有一個“按鈕數組”，例如第五層的按鈕按下，意味著有乘客在第5層到達目標層，等等。在樓的每一層，有電梯數，有按鈕表示有人等待向上或向下，由若干人在等待，有若干電梯在本層停下，等等。

在大樓中（包括進出）的總人數不超過500 人，每個人站在電梯前有個目標層，他有一個最大的忍受等待時間，因為他可以選擇電梯或是步行走樓梯，等等。

還有下面若干假設：在每個時間段要進大樓的人數在0～199 之間隨機取值；

用電梯的每個人的目標層在1～10 之間取值；一個人在進電梯或改走樓梯之前的等待時間在180～360 秒范圍內隨機發生；一個人到達目標層后第二次再乘電梯中間的工作時間在400～6600 秒間隨機取值。[基本要求] 編寫一個程序，模擬辦公大樓中全部電梯的工作過程。這個仿真程序可以用來監測系統運行情況，改善大樓管理，它也可以看成是一種游戲程序。

2.27國交通咨詢模擬

[問題描述]

處于不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能的短，出門旅游的游客則期望旅費盡可能省，而老年旅客則要求中轉次數最少。編制一個全國城市間的交通咨詢程序，為旅客提供最優決策的交通咨詢。

[基本要求]

（1）提供對城市信息進行編輯（如：添加或刪除）的功能；

（2）城市之間有兩種交通工具：火車或飛機，提供對全國城市交通圖和列車時刻表及飛機航班表進行編輯的功能。（信息的輸入方式可以是文件輸入和鍵盤輸入兩種方式）

（3）提供兩種最優決策：最快到達和最省錢到達。（選作：旅途中轉次數最少的最優決策）

（4）旅途中耗費的總時間應該包括中轉站的等候時間。

（5）咨詢以用戶和計算機的對話方式進行。

a）由用戶輸入起始站、終點站、最優決策原則和交通工具；

b）輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能到達，并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到何地。

三、課程設計的基本要求

1．問題分析和任務定義。根據設計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？

2．邏輯設計。對問題描述中涉及的操作對象定義相應的數據類型，并按照以數據結構為中心的原則劃分模塊，定義主程序模塊和各抽象數據類型。邏輯設計的結果應寫出每個抽象數據類型的定義(包括數據結構的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調用關系圖。

3．詳細設計。定義相應的存儲結構并寫出各函數的偽碼算法。在這個過程中，要綜合考慮系統功能，使得系統結構清晰、合理、簡單和易于調試，抽象數據類型的實現盡可能做到數據封裝，基本操作的規格說明盡可能明確具體。詳細設計的結果是對數據結構和基本操作作出進一步的求精，20 寫出數據存儲結構的類型定義，寫出函數形式的算法框架。

4．程序編碼。把詳細設計的結果進一步求精為程序設計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚。

5．程序調試與測試。采用自底向上，分模塊進行，即先調試低層函數。能夠熟練掌握調試工具的各種功能，設計測試數據確定疑點，通過修改程序來證實它或繞過它。調試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結果。

6．結果分析。程序運行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。算法的時間、空間復雜性分析。

7．編寫課程設計報告并提交相關內容

設計最終需提交的內容包括：

a）課程設計報告（1份，a4紙打印，同時包括一份電子版）報告要求版面清晰，格式規范，否則重新編寫。報告內容要求包括：

（1）問題的概述、分析及研究意義；（2）數據結構的邏輯設計和物理存儲設計；（3）重要算法的設計、流程描述或偽代碼描述；

（4）數據結構的時空復雜性分析以及重要算法的復雜性分析；

（5）程序最終實現結果（包括重點結果界面的抓取，能過說明問題的重要實驗結果數據的打印或其可視化結果等）。

（6）參考文獻（如果需要）。

（7）附錄部分附上關鍵數據結構的定義及關鍵算法的源代碼。

b）完整的程序系統（電子方式提交）

能夠對輸入產生相應的輸出，同時盡量的完成可視化演示。

該部分包括源代碼和可執行文件兩個部分（提交的時候需清楚的注明個人姓名，班級）。

c）源程序文檔（電子方式提交）

源程序代碼要求結構清晰、可讀性好。應對源程序中的類說明（如果采用面向對象方法設計），函數說明，接口說明，關鍵變量說明等進行注釋；源程序要進行適當的縮進編排。

d）答辯報告（編寫power point答辯報告，電子方式提交）要求突出重點，思路清晰。同時就此報告準備答辯。

e）所有以電子方式提交的文件全部存在一個目錄中，并對其進行壓縮（用winrar或winzip均 21 可），壓縮后的文件按規定格式進行命名，命名格式為：學號+（）。8．每位同學只能選擇一個題目并完成

四、評分標準

1、基本功能：

50分。

通過功能的實現情況、界面的完成情況、軟件的實現情況進行評分。

2、設計報告及使用說明書： 20分按照報告的要求進行評分。

3、回答問題：

4、平時考勤：

5、核分標準：

15分 15分 100分

（90~100為優、80~89為良、70~79為中、60~69為及格、，60以下為不及格）

五、參考書目

嚴蔚敏.《數據結構》（c語言版）.清華大學出版社劉玉龍．《數據結構與算法》.電子工業出版社.嚴蔚敏等《數據結構題集》（c語言版）.清華大學出版社

徐孝凱.數據結構實用教程（c/c++描述）.北京:清華大學出版社.陳慧南.數據結構（使用c++語言描述）.南京:東南大學出版社.殷人昆, 陶永雷, 謝若陽等.數據結構（用面向對象方法與c++描述）.北京:清華大學出版社.22

數據結構與算法分析課程設計篇二

《數據結構與算法》課程設計教學大綱（data structures & algorithms）

一、基本信息

課程編號：e1132107 課程類別：學科基礎課必修課適用層次：本科

適用專業：計算機科學與技術、網絡工程、軟件工程等開課學期：3 學分：2學分學時：2周考核方式：考查

二、教學目的

數據結構與算法課程設計不僅是數據結構與算法課程的實踐教學環節，而且是一門綜合性實驗項目。通過這個實驗，培養學生綜合運用數據結構基本知識和程序設計基本知識，解決實際問題，提高程序設計的能力和團隊協作精神。

本課程設計的目的就是要達到理論與實際應用相結合，使同學們能夠根據數據對象的特性，學會數據組織的方法，能把現實世界中的實際問題在計算機內部表示出來，并培養基本的、良好的程序設計技能。

1．學生通過實踐掌握線性表、樹、圖等數據結構的存儲結構及算法實現； 2．培養學生利用數據結構知識解決實際問題的能力;3．使學生初步具備查閱資料、分析設計、上機實現和書寫科技報告的能力。

三、基本要求

1.指導教師要在選題、設計、上機實現等諸環節上投入精力，加強指導、討論和答疑的力度。尤其在選題上，要充分考慮學生目前所具有的知識水平、掌握的開發工具、以及綜合設計能力的現狀，使題目取材合理、大小適中、難易適度，使學生在完成設計工作后，能有所收獲。2.參加課程設計的學生要珍惜機會、勤奮工作、勇于創新、勇于探索、勇于實踐，虛心向指導教師請教，向同學學習，獨立完成設計任務。

3.學生需保質、保量、保時間進度地提交規范的課程設計報告，審查由指導教師負責。

四、教學內容

1.主要內容：應用所掌握的線性表、樹、圖等數據結構知識解決實際問題。2.軟件開發工具：c/c++、java。

3.課程設計題目：指導教師擬定（參考題目見附錄1）

4.具體步驟：指導教師擬定設計題目，學生研究具體問題、進行需求分析、選擇合適的數據結構、設計算法、編寫并調試代碼、書寫文檔材料、提交設計報告，最后，由指導教師驗收并評定成績。

5.設計內容及時間安排：第1-3天，選定題目，明確題目要求、確定數據結構、設計算法，并分析算法復雜度；第4-8天，編寫程序、調試程序、測試程序；第9-10天，撰寫設計報告，準備答辯（上機演示，回答教師提問）。6.設計報告書寫要求：按照軟件開發規范的要求書寫設計報告（參見附錄三報告書寫格式）；要求報告層次結構清晰、圖表完整、語言通順、字跡工整。7.驗收要求：1）運行所設計的程序；2）回答有關問題；3）提交課程設計報告（打印或手寫在實習報告冊上）；4）提交軟盤（源程序）。（鼓勵學生創新。對內容有創新者，成績評定將適當提高）。

五、考核方法

學習成績的評定方式：考查。

課程設計成績評定 =平時出勤（20%）+設計報告（40%）+答辯（40%）通過設計答辯方式，并結合學生的動手能力，獨立分析解決問題的能力和創新精神，總結報告和答辯水平以及學習態度綜合考評。成績分為優、良、中、及格和不及格五等。

六、教材與參考資料 1.建議教材：

[1] 數據結構(c++)版，王紅梅、胡明、王濤編著，清華大學出版社，2005.7 [2] 自編教材

2.建議參考書目：

[1] 許卓群，楊冬青，唐世渭，張銘.數據結構與算法.高等教育出版社，2004.7 [2] 嚴蔚敏, 陳文博.數據結構及應用算法教程.清華大學出版社, 2001.2 [3] 朱晉蜀.數據結構(第一版).成都: 電子科技大學出版社, 2000.1 [4] clifford r著.張銘，劉曉丹譯.數據結構與算法分析.電子工業出版社，1998.8 [5] 殷人昆等.數據結構（用面向對象方法與c++描述）.清華大學出版社，1999.7 [6] ford w., topp structures with c++.清華大學出版社（影印版），1997.3

附錄一

參考題目（可分若干組，每個學生選擇其中一個題目）

1．商廈家電庫存管理 2.排序算法的時間比較

3．使用哈希表技術判斷兩個源程序的相似性 4．以隊列實現的仿真技術預測理發館的經營狀況 5.某公園導游圖

6．用樹型結構的搜索算法模擬因特網域名的查詢 7．管道鋪設施工的最佳方案選擇 8．表達式分析與求值程序 9．安排教學計劃

10.設計huffman 編碼器與解碼器 11．在國際象棋盤上馬遍歷問題 12．八皇后問題 13．民航售票系統 14．模擬旅館管理系統中的床位分配和加收 15．銀行業務活動的模擬

16．文字統計系統—文字研究助手 17．修道士野人問題 18．考試問題

19．計算機輔助考核系統 20．學籍管理系統

注：學生可以自選題目或選擇指導老師擬定的題目。

附錄二

開發步驟

1.分析題目的要求、目的； 2.選擇適當的數據結構；

3.抽象數據類型的設計； 4.抽象數據類型的實現； 5.編寫代碼、上機調試； 6.總結驗收、評價。

附錄三報告書寫格式

1．問題描述

題目內容、基本要求 2．需求分析

軟件的基本功能、輸入/輸出形式、測試數據要求 3．概要設計

所需的adt及作用、主程序流程及模塊調用關系 4．詳細設計

實現概要設計的數據類型、每個操作的偽碼算法、主程序和其它模塊的偽碼算法、函數調用關系圖 5．編碼與調試分析

編碼與調試過程中遇到的問題及解決的辦法，還存在哪些沒有解決的問題？ 6．使用說明

簡要說明程序運行操作步驟 7．測試結果

8．課程設計心得體會

數據結構與算法分析課程設計篇三

《數據結構》教學大綱

一、課程基本信息

課程名稱：數據結構

總學時：64(理論課內學時48，上機課內學時16)課程設計：24 課程類型：必修課

考試形式：半開卷考試講課對象：計算機本科

建議教材：《數據結構》(c語言版)陳明編著清華大學出版社

課程簡介：數據結構課程介紹如何組織各種數據在計算機中的存儲、傳遞和轉換。內容包括：數組、鏈接表、棧和隊列、串、樹與森林、圖、排序、查找、索引與散列結構等。課程以結構化程序設計語言c語言作為算法的描述工具，強化數據結構基本知識和結構化程序設計基本能力的雙基訓練。為后續計算機專業課程的學習打下堅實的基礎。

二、課程的教學目標

“數據結構”是計算機相關專業的一門重要專業基礎課，是計算機學科的公認主干課。課程內容由數據結構和算法分析初步兩部分組成。

數據結構是針對處理大量非數值性程序問題而形成的一門學科，內涵豐富、應用范圍廣。它既有完整的學科體系和學科深度，又有較強的實踐性。通過課程的學習，應使學生理解和掌握各種數據結構(物理結構和邏輯結構)的概念及其有關的算法；熟悉并了解目前常用數據結構在計算機諸多領域中的基本應用。

算法分析強調最基本的算法設計技術和分析方法。要求學生從算法和數據結構的相互依存關系中把握應用算法設計的藝術和技能。

經過上機實習和課程設計的訓練，使學生能夠編制、調試具有一定難度的中型程序；以培養良好的軟件工程習慣和面向對象的軟件思維方法。

“數據結構”的前序課是《離散數學》、《c語言程序設計與算法初步》。

三、理論教學內容的基本要求及學時分配

1、序論(2學時)學習目標：熟悉各類文件的特點，構造方法以及如何實現檢索，插入和刪除等操作。

重點與難點：本章無。

知識點：數據、數據元素、數據結構、數據類型、抽象數據類型、算法及其設計原則、時間復雜度、空間復雜度。

2、線性表(4學時)

學習目標：

(1)了解線性表的邏輯結構特性是數據元素之間存在著線性關系，在計算機中表示這種關系的兩類不同的存儲結構是順序存儲結構和鏈式存儲結構。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表；

(2)熟練掌握這兩類存儲結構的描述方法以及線性表的基本操作在這兩種存儲結構上的實現；

(3)能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲結構的不同特點及其適用場合；

(4)結合線性表類型的定義增強對抽象數據類型的理解。

重點與難點：鏈表是本章的重點和難點。扎實的指針操作和內存動態分配的編程技術是學好本章的基本要求，分清鏈表中指針 p 和結點 *p 之間的對應關系，區分鏈表中的頭結點、頭指針和首元結點的不同所指以及循環鏈表、雙向鏈表的特點等。

知識點：線性表、順序表、鏈表、有序表。

3、棧和隊列(4學時)

學習目標：

(1)掌握棧和隊列這兩種抽象數據類型的特點，并能在相應的應用問題中正確選用它們；

(2)熟練掌握棧類型的兩種實現方法；

(3)熟練掌握循環隊列和鏈隊列的基本操作實現算法；(4)理解遞歸算法執行過程中棧的狀態變化過程。

重點與難點：棧和隊列是在程序設計中被廣泛使用的兩種線性數據結構，因此本章的學習重點在于掌握這兩種結構的特點，以便能在應用問題中正確使用。

知識點：順序棧、鏈棧、循環隊列、鏈隊列。

4、串(2學時)

學習目標：(1)理解串類型定義中各基本操作的特點，并能正確利用它們進行串的其它操作；

(2)理解串類型的各種存儲表示方法；(3)理解串匹配的各種算法。

重點和難點：相對于其它各個知識點而言，本章非整個課程的重點，鑒于串已是多數高級語言中已經實現的數據類型，因此本章重點僅在于了解串類型定義中各基本操作的定義以及串的實現方法，并學會利用這些基本操作來實現串的其它操作。本章的難點是理解實現串匹配的kmp算法的思想。

知識點：串的類型定義、串的存儲表示、串匹配、kmp算法。

5、數組和廣義表(4學時)

學習目標：

(1)理解數組類型的特點及其在高級編程語言中的存儲表示和實現方法，并掌握數組在“以行為主”的存儲表示中的地址計算方法；

(2)掌握特殊矩陣的存儲壓縮表示方法；

(3)理解稀疏矩陣的兩類存儲壓縮方法的特點及其適用范圍，領會以三元組表示稀疏矩陣時進行矩陣運算所采用的處理方法。

重點和難點：本章重點是學習數組類型的定義及其存儲表示。

知識點：數組的類型定義、數組的存儲表示、特殊矩陣的壓縮存儲表示方法、隨機稀疏矩陣的壓縮存儲表示方法。

6、樹和二叉樹(8學時)

學習目標：

(1)領會樹和二叉樹的類型定義，理解樹和二叉樹的結構差別；(2)熟記二叉樹的主要特性，并掌握它們的證明方法；

(3)熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現二叉樹的其它操作；

(4)理解二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法；

(5)熟練掌握二叉樹和樹的各種存儲結構及其建立的算法；(6)學會編寫實現樹的各種操作的算法；

(7)了解最優樹的特性，掌握建立最優樹和赫夫曼編碼的方法。

重點和難點：二叉樹和樹的遍歷及其應用是本章的學習重點，而編寫實現二叉樹和樹的各種操作的遞歸算法也恰是本章的難點所在。

知識點：樹的類型定義、二叉樹的類型定義、二叉樹的存儲表示、二叉樹的遍歷以及其它操作的實現、線索二叉樹、樹和森林的存儲表示、樹和森林的遍歷以及其它操作的實現、最優樹和赫夫曼編碼。

7、圖(8學時)

學習目標：

(1)領會圖的類型定義；

(2)熟悉圖的各種存儲結構及其構造算法，了解各種存儲結構的特點及其選用原則；

(3)熟練掌握圖的兩種遍歷算法；(4)理解各種圖的應用問題的算法。

重點和難點：圖的應用極為廣泛，而且圖的各種應用問題的算法都比較經典，因此本章重點在于理解各種圖的算法及其應用場合。

知識點：圖的類型定義、圖的存儲表示、圖的深度優先搜索遍歷和圖的廣度優先搜索遍歷、無向網的最小生成樹、最短路徑、拓撲排序、關鍵路徑。

8、查找(6學時)

學習目標：

(1)理解“查找表”的結構特點以及各種表示方法的適用性；(2)熟練掌握以順序表或有序表表示靜態查找表時的查找方法；

(3)熟悉靜態查找樹的構造方法和查找算法，理解靜態查找樹和折半查找的關系；

(4)熟練掌握二叉查找樹的構造和查找方法；(5)理解二叉平衡樹的構造過程；

(6)熟練掌握哈希表的構造方法，深刻理解哈希表與其它結構的表的實質性的差別；

(7)掌握描述查找過程的判定樹的構造方法，以及按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。

重點和難點：本章重點在于理解查找表的結構特點及其各種表示方法的特點和適用場合。

知識點：順序表、有序表、索引順序表、靜態查找樹、二叉查找樹、二叉平衡樹、哈希表。

9、內部排序(6學時)

學習目標：

(1)理解排序的定義和各種排序方法的特點，并能加以靈活應用。排序方法有不同的分類方法，基于“關鍵字間的比較”進行排序的方法可以按排序過程所依據的不同原則分為插入排序、交換排序、選擇排序、歸并排序和計數排序等五類；

(2)掌握各種排序方法的時間復雜度的分析方法。能從“關鍵字間的比較次數”分析排序算法的平均情況和最壞情況的時間性能。按平均時間復雜度劃分，內部排序可分為三類：o(n2)的簡單排序方法，o(n*logn)的高效排序方法和o(d*n)的基數排序方法；

(3)理解排序方法“穩定”或“不穩定”的含義，弄清楚在什么情況下要求應用的排序方法必須是穩定的。

重點和難點：希爾排序、快速排序、堆排序和歸并排序等高效方法是本章的學習重點和難點。

知識點：排序、直接插入排序、折半插入排序、表插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序、堆排序、2-路歸并排序、基數排序、排序方法的綜合比較。

10、文件(4學時)

學習目標：熟悉各類文件的特點，構造方法以及如何實現檢索，插入和刪除等操作。

重點和難點：本章重點在于了解各種文件的結構特點及其適用場合。知識點：順序文件、索引文件、b-樹、b+樹、索引順序文件、vsam文件、散列文件、多關鍵字文件。

四、實驗教學內容的基本要求及學時分配

1、線性表(1學時)實驗一順序表的應用實驗二鏈表的應用

要求：理解線性表的定義及其運算；理解順序表和鏈表的定義，組織形式，結構特征和類型說明；掌握在這兩種表上實現的插入，刪除和按值查找的算法；了解循環鏈表，雙(循環)鏈表的結構特點和在其上施加的插入，刪除等操作。

2、棧(0.5學時)實驗三棧的應用

要求：理解棧的定義，特征及在其上所定義的基本運算；掌握在兩種存儲結構上對棧所施加的基本運算的實現。

3、隊列(0.5學時)實驗四隊列的應用

要求：理解隊列的定義，特征及在其上所定義的基本運算；掌握在兩種存儲結構上對隊列所施加的基本運算的實現。

4、串(0.5學時)實驗五串的應用

要求：了解串的定義；理解和領會串的存儲方式；掌握常用的串運算。

5、數組和廣義表(0.5學時)實驗六稀疏矩陣的應用

要求：理解多維數組的結構特點和在內存中的兩種順序存儲方式；理解并掌握矩陣和特殊矩陣元素在存儲區中地址的計算；領會稀疏矩陣的壓縮方式和簡單運算；了解廣義表的定義和基本運算。

6、樹與二叉樹(4學時)實驗七樹與二叉樹的應用

要求：理解樹的定義，術語；領會并掌握樹的各種存儲結構；熟練掌握森林與二叉樹間的相互轉換；領會樹和森林的遍歷；了解樹的簡單應用。深刻理解二叉樹的定義，性質及其存儲方法；熟練掌握二叉樹的二叉鏈表存儲方式，結點結構和類型定義；理解并掌握二叉樹的三種遍歷算法；掌握二叉樹的線索化方法；靈活運用二叉樹的遍歷方法解決相關的應用問題。

7、圖(3學時)實驗八圖的應用

要求：理解圖的基本概念及術語；掌握圖的兩種存儲結構(鄰接矩陣和鄰接表)的表示方法；熟練掌握圖的兩種遍歷(深度優先搜索遍歷和廣度優先搜索遍歷)的算法思想，步驟，并能列出在兩種存儲結構上按上述兩種遍歷算法得到的序列；理解最小生成樹的概念，能按prim算法構造最小生成樹；領會并掌握拓撲排序，關鍵路徑，最短路徑的算法思想。

8、查找(3學時)實驗九順序查找實驗十折半查找實驗十一哈希表的應用實驗十二二叉排序樹的綜合練習要求：了解查找的基本思想及查找成功和不成功的概念；掌握在順序表，有序表，索引表，散列表等上的查找方法和算法，并能求出相應的平均查找長度；理解并掌握二叉排序樹，平衡二叉樹b-樹的各種算法。

9、排序(3學時)實驗十三插入排序實驗十四選擇排序實驗十五排序綜合練習

要求：領會排序的基本思想和基本概念；理解并掌握插入排序，冒泡排序，快速排序，直接選擇排序，堆排序，歸并排序和基數排序的基本思想，步驟，算法及時空效率分析；了解外排序的定義和基本方法。

五、大綱說明

1、課堂講述的論題只是核心或有特色的知識內容，還有相當數量的篇章內容留給學生自學，所確定的自學部分內容亦屬考查范圍。

2、“數據結構”課注重上機訓練，所有作業都必須配有規范的文檔。上機訓練由平時的上機訓練和小學期的實訓課程設計兩部分組成。

3、課內學時安排說明：前8周每周4學時全為理論課，從第9周開始理論和上機為1：1，也即2學時理論，2學時上機訓練。

4、本課強調能力的培養，期末采用半開卷考試(允許同學攜帶一頁a4紙的總結資料)。本課成績由平時作業、上機成績(30%)和期末考試(70%)合成得到，有獨到見解的作業予以適當加分。

5、主要參考書：

[1]《數據結構與算法教程》鄒永林周蓓唐曉陽楊劍勇編著機械工業出版社

[2]《數據結構(c語言版)》(含cd)嚴蔚敏吳為民編著清華大學出版社

[3]《數據結構習題集(c語言版)》嚴蔚敏編著清華大學出版社

[4]《數據結構習題解析與實訓》張世和編著清華大學出版社

數據結構與算法分析課程設計篇四

教學大綱

數據結構與算法（data structures）

計算機技術已成為現代化發展的重要支柱和標志，并逐步滲透到人類生活的各個領域。隨著計算機硬件的發展，對計算機軟件的發展也提出了越來越高的要求。由于軟件的核心是算法，而算法實際上是對加工數據過程的描述，所以研究數據結構對提高編程能力和設計高性能的算法是至關重要的。

非數值計算問題的數學模型不再是傳統的數學方程問題，而是諸如表、樹、圖之類的數據結構。因此，簡單地說，數據結構是一門研究非數值計算的程序設計問題的學科，主要研究數據的邏輯結構、存儲結構和算法。

一、教學目的與要求---了解數據的邏輯結構和物理結構；

教學要求在每章教學內容給出，大體上為三個層次：了解、掌握和熟練掌握。他們的含義大致為：了解是正確理解概念，掌握是學會所學知識，熟練掌握就是運用所學知識解決實際問題。

教學目的為：了解算法對于程序設計的重要性；學習掌握基本數據結構的描述與實現方法，熟練掌握典型數據結構及其應用算法的設計。了解算法分析方法。

二、教學重點與難點--數據結構中基本概念和術語，算法描述和分析方法。

1、鏈表插入、刪除運算的算法。算法時間復雜度

2、后綴表達式的算法，數制的換算

利用本章的基本知識設計相關的應用問題

3、循環隊列的特點及判斷溢出的條件

利用隊列的特點設計相關的應用問題

4、串的模式匹配運算算法

5、二叉樹遍歷算法的設計

利用二叉樹遍歷算法，解決簡單應用問題哈夫曼樹的算法

6、圖的遍歷

最小生成樹

最短路徑

7、二叉排序樹查找

平衡樹二叉樹

8、堆排序

快速排序歸并排序

三、教學方法與手段-充分利用多媒體教學工具，配合黑板上的教學內容較難部分的算法實現過程演義

四、教學內容、目標與學時分配

教學內容教學目標課時分配

1、緒論

數據結構的內容

邏輯結構與存儲結構

算法和算法分析

2、線性表

線性表的定義與運算

線性表的順序存儲

線性表的鏈式存儲

3、棧

棧的定義與運算

棧存儲和實現

棧的應用舉例

4、隊列

隊列的定義與基本運算

隊列的存儲與實現

隊列的應用舉例

5、串

串的定義與基本運算

串的表示與實現

串的基本運算

6、樹和二叉樹

樹的定義和術語

二叉樹樹的基本概念和術語遍歷二叉數和線索二叉樹

二叉樹的轉換

二叉樹的應用

哈夫曼樹及其應用

7、圖

圖的定義和術語

圖的存儲結構

圖的遍歷算法

圖的連通性

8、查找

查找的基本概念與靜態查找動態查找

哈希表

了解

掌握

熟練掌握順序表存儲地址的計算

掌握單鏈表的結構特點和基本運算

掌握雙鏈表的結構特點和基本運算

掌握棧的定義與運算

掌握棧的存儲與實現

熟練掌握棧的各種實際應用

掌握隊列的定義與基本運算

熟練掌握隊列的存儲與實現

掌握循環隊列的特征和基本運算

了解串的邏輯結構

掌握串的存儲結構

熟練掌握串的基本運算

了解

了解二叉樹

熟練掌握二叉樹定義和存儲結構

了解二叉樹的遍歷算法

掌握

掌握哈夫曼的建立及編碼

了解

熟練掌握

了解

熟練掌握

了解哈希表與哈希方法

4學時

1學時

2學時

8學時

2學時

4學時

8學時

2學時

4學時

6學時

2學時

6學時

2學時

12學時

2學時

8學時

2學時

8學時

4學時

2學時

9、排序

12學時插入排序

熟練掌握基本思想

3學時快速排序

了解各種內部排序方法和特點

3學時選擇排序

掌握

2學時各種排序方法比較

掌握

2學時

實驗內容實驗目標課時分配算法編程實驗：

1、用指針方式編寫程序復習c（c++）語言指針、結構體等的用法

2、對單鏈表進行遍歷

鏈表的描述與操作實現

3、棧及其操作

描述方法及操作

4、編寫串子系統1 串的特點及順序定長存儲、操作、查找

5、編寫串子系統 2 串的特點及順序定長存儲、操作、查找

6、編寫樹子系統1 二叉樹的特點及存儲方式、創建、顯示、遍歷等

7、編寫樹子系統2 二叉樹的特點及存儲方式、創建、顯示、遍歷等

8、圖子系統

圖的鄰接矩陣的存儲、遍歷、廣度/深度優先搜索

9、查找子系統

理解查找基本算法、平均查找長度、靜態、動態查找等

五、考試范圍與題型

1、考試范圍與分數比例

1)緒論

12% 2)線性表

17% 3)棧

7% 4)隊列

6% 5)串

4% 6)樹和二叉樹

14% 7)圖

15% 8)查找

4% 9)排序

21%

2、考試題型與分數比例

1)名詞解釋

18% 2)判斷對錯

16% 3)填空

16% 4)單項選擇

18% 5)應用

32%

六、教材與參考資料

1、教材：實用數據結構基礎（譚浩強）中國鐵道出版社

2、參考資料：數據結構（嚴蔚敏）清華大學出版社

數據結構實用教程（徐孝凱）清華大學出版社

（撰寫人：

，審核人： 2學時 2學時 2學時 2學時 2學時 2學時 2學時 2學時 2學時）

數據結構與算法分析課程設計篇五

數據結構與算法課程設計題目

1．成績管理

問題描述：給出n個學生的考試成績表，成績表包括學生的學號、姓名、考試成績（高等數

學、英語、物理），設計一個簡單的成績管理程序。

基本要求：

（1）建立成績表，能夠插入、刪除、修改學生的成績記錄；（2）按任一單科成績排序；(3)計算每名學生的平均成績；

(4)統計任一單科成績不及格的學生人數, 輸出不及格人數及不及格的學生名單(5)根據平均成績將成績表按由高到低的次序排列，統計每名學生在考試中獲得的名次，分數相同的為同一名次，按名次輸出成績表。

(6)成績表保存在文件中, 可以從文件讀取數據。

測試數據：學生可以根據自己班級的考試成績單，任意截取一部分做為測試數據 2．一元多項式簡單計算

問題描述：設計一個簡單一元多項式計算器。基本要求：(1)輸入并建立多項式；(2)輸出多項式；

(3)兩個多項式相加，輸出結果多項式；(4)兩個多項式相減，輸出結果多項式。

提高要求：可以根據輸入變量的值，計算出多項式的結果，且算法的效率高。測試數據：可任意選取兩個一元多項式，可以是一般的多項式，也可以是稀疏多項式。3．舞伴問題

問題描述：一班有m個女生、n個男生(m不等于n), 舉辦一場舞會.男女生分別編號坐在舞池兩邊的椅子上，每曲開始時, 依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴，設計一個程序模擬舞伴配對過程。

基本要求：輸入男、女學生的姓名、性別，由程序自動為男女生編號，可以順序編號，也可以隨機編號，輸出每曲配對情況（包括男、女生的姓名、性別和編號）。原始數據和結果數據要保存到文件中。

測試數據：分別選擇男生多于女生、女生多于男生、男女生相等的三組測試數據提高要求：計算出任意一位男生(編號為x)和任意一位女生(編號為y), 在第k曲配對跳舞的情況。

4．文學研究助手（*）

問題描述：文學研究人員需要統計某篇英文小說中某些形容詞的出現次數和位置。試寫一個實現這一目標的文字統計系統，稱為“文學研究助手”。基本要求：英文小說存于一個文本文件中，待統計的詞匯集合要一次輸入完畢，即統計工作必須在程序的一次運行之后就全部完成。程序的輸出結果是每個詞的出現次數和出現位置所在行的行號，格式自行設計, 結果保存到文件中。

提高要求：模式匹配選取kmp算法

測試數據：以你的c/c++/java源程序模擬英文小說，相應語言的保留字集作為待統計的詞匯集。

5．哈希表的設計與實現（*）

問題描述：針對某個單位電話號碼簿，設計一個哈希表，并完成相應的建表和查表程序。基本要求：設每個記錄有下列數據項：電話號碼、用戶名、住址。從鍵盤輸入各記錄，以用戶名為關鍵字建立哈希表，哈希函數用除留取余數法構造，采用線性探測法解決沖突。可以插入、查找、刪除并顯示給定用戶名的記錄，并計算查找長度, 哈希表保存到文件中。

測試數據：取某個單位電話號碼簿中的30個記錄。

提高要求：將電話號碼薄以文件形式保存到盤上，能夠按用戶名和電話號碼兩種形式建立哈希表并實現插入、查找、刪除表中元素的功能。

6．管道鋪設施工的最佳方案（*）

問題描述:需要在某個城市的n個小區鋪設管道，則在這n個小區之間鋪設n-1條管道即可，假設任意兩個居民區之間都可以架設管道，但由于地理環境的不同，所需經費不同，選擇最優的施工方案使總投資盡可能的少。

基本要求：輸入表示小區間關系的圖及每條管道的權值，選擇出n-1條管道, 使總投資最小。圖的信息輸入一次后, 保存到文件中, 選擇的n-1條管道輸出到顯示器的同時, 也保存于文件中。

測試用例：任意選擇一個圖，模擬小區間可能鋪設的管道及費用。提高要求：顯示原始圖及選擇n-1條管道后的圖。

7．安排教學計劃（**）

問題描述：大學的每個專業都要制定教學計劃。假設任何專業都有固定的學習年限，每學年含兩個學期，每學期的時間長度和學分上限值均相等。每個專業開設的課程都是確定的，而且課程在開設時間的安排上必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課程恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序。

基本要求：輸入參數包括學期總數，一學期的學分上限，每門課程的課程號、學分和直接先修課的課程號；允許兩種策略，一是使學生在各學期的學習負擔盡量均勻，二是使課程盡量集中在前幾個學期；若根據給定的條件問題無解，則報告適當的信息，否則將教學計劃輸出到用戶指定的文件中。教學計劃的表格格式自行設定, 可以從鍵盤讀取數據也可以從文件讀取數據, 結果保存到文件中。

測試數據：學期總數為6，學分上限為10，該專業共開設12門。以08級某專業必修課與選修課為例，選擇12門課程及相應學分，制定一個表明各門課程先后約束關系的有向圖。

提高要求：產生多種不同的方案，并使方案之間的差異盡可能地大。8．停車場管理程序(**)問題描述：設停車場內只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。

基本要求：每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數據進行操作后的輸出數據為：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車離去；則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費，單位時間的停車費用由用戶從鍵盤輸入）。

測試數據：設輸入數據為：（‘a’，1，5），（‘a’，2，10），（‘d’，1，15），（‘a’，3，20），（‘a’，4，25），（‘a’，5，30），（‘d’，2，35），（‘d’，4，40），（‘e’，0，0）。其中，‘a’表示到達；‘d’表示離去，‘e’表示輸入結束。

提高要求：設停車場有南、北兩個門，每個門都可以進、出車輛。9．計算表達式的值(**)問題描述：對于給定的一個表達式，表達式中可以包括常數、算術運行符（“+”、“-”、“*”、“/”）和括號，編寫程序計算表達式的值。

基本要求：從鍵盤輸入一個正確的中綴表達式，將中綴表達式轉換為對應的后綴表達式，計算后綴表達式的值。

測試數據：任意選取一個符合題目要求的表達式。提高要求：（1）對于表達式中的簡單錯誤，能夠給出提示；

（2）表達式中可以包括單個字母表示的變量。

10．設計huffman 編碼器與解碼器（***）

問題描述：利用哈夫曼編碼進行信息通訊可以大大提高信道的利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳輸數據預先編碼；在接受端將傳來的數據進行譯碼。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統。試為這樣的信息收發站編寫一個哈夫曼碼的編/譯碼系統。

基本要求：根據某字符文件統計字符出現頻度，構造huffman 樹，編制huffman編碼，并將給定字符文件編碼，生成編碼文件；再將給定編碼文件解碼，生成字符文件。（要求按二進制位表示編碼）測試數據：英文文件。

提高要求：用二進制表示編碼，生成二進制的編碼文件。11．銀行業務模擬（***）

問題描述：設銀行有四個服務窗口，一個等待隊列, 每個窗口均可以辦理存款、取款、掛失、還貸業務，每種業務所需的服務時間不同，客戶到達銀行后，先到打號機上打號，號票上包括到達時間、編號和需要辦理的業務，然后在銀行內等候, 當任一服務窗口空閑時,處理等候客戶中排在最前面的客戶的業務。寫一個上述銀行業務的模擬系統,通過模擬方法求出客戶在銀行內逗留的平均時間和每個窗口辦理的客戶數及辦理的每種業務數。

基本要求：每個客戶到達銀行的時間和需要辦理的業務隨機產生，輸出一天客戶在銀行的平均逗留時間和每個窗口每天辦理的客戶數和每種業務數。

測試數據：營業時間為8小時，其他模擬量自行設定。12．程序源代碼的相似性（***）

問題描述：對于兩個c++語言的源程序代碼，用哈希表的方法分別統計兩個程序中使用c++語言關鍵字的情況，并最終按定量的計算結果，得出兩份程序的相似性。

基本要求：建立c++語言關鍵字的哈希表，統計在每個源程序中c++關鍵字出現的頻度, 得到兩個向量x1和x2，通過計算向量x1和x2的相對距離來判斷兩個源程序的相似性。

例如: 關鍵字 void int for char if else while do break class 程序1關鍵字頻度 4 3 0 4 3 0 7 0 0 2 程序2關鍵字頻度 4 2 0 5 4 0 5 2 0 1 x1=[4,3,0,4,3,0,7,0,0,2] x2=[4,2,0,5,4,0,5,2,0,1] 設s是向量x1和x2的相對距離，s=sqrt(∑(xi1-xi2)2)，當x1=x2時，s=0, 反映出可能是同一個程序；s值越大，則兩個程序的差別可能也越大。

測試數據: 選擇若干組編譯和運行都無誤的c++程序，程序之間有相近的和差別大的，用上述方法求s, 對比兩個程序的相似性。

提高要求：建立源代碼用戶標識符表，比較兩個源代碼用戶標識符出現的頻度，綜合關鍵字頻度和用戶標識符頻度判斷兩個程序的相似性。

13．小型文本編輯器

問題描述：設計一個行編輯程序，使其具有通常行編輯器(如vi、edlin)應具備的基本功能。

基本要求：編輯器應具備對文本文件的查找、插人、刪除、修改、字符串替換、統計字數，統計行數等功能，對于超過一屏的長文件，應能夠分頁顯示，查找功能用字符串匹配算法實現。設計用戶接口命令，實現對文本的編輯。具體的編輯命令，可參考數據結構算法網絡教學平臺上提供的edlin、vi的命令集。

測試數據：任一文本文件。

提高要求：１.可以支持“* ”、“? ”等通配符；

２.支持復制、粘貼等功能

3.支持多文檔同時編輯；

提示：可以考慮用雙向鏈表實現，每一結點表示一行字符，注意每行字符不能超過255。14．小型英漢詞典

問題描述：設計一個英漢詞典，支持member(查找)、insert(插入)、delete(刪除)操作。

基本要求：實現字典的常用方法有：有序線性表（memeber用二分檢索實現）、avl樹（二叉搜索樹）、patricia trie、散列表等，任選一種方法實現字典的操作，查找單詞、插入單詞（插入時，先查找，找不到插入，找到提示用戶）、刪除單詞（刪除時，先查找，找到刪除，找不到提示用戶）。