南開大學《數(shù)據(jù)結(jié)構(gòu)與算法》本科課程教學大綱

南開大學本科課程教學大綱開課學院：（公章）課程名稱數(shù)據(jù)結(jié)構(gòu)與算法英文名稱DataStructuresandAlgorithms課程編號1030310170030312學分數(shù)3總學時62講授學時32實驗、上機、習題等學時30授課語言（單選）■漢語□英語□雙語□其他：成績類型（單選）■百分制□等級制（通過/不通過）課程負責人王愷職稱副教授課程組成員趙宏，李敏，王剛，劉哲理授課專業(yè)理工科非計算機專業(yè)課程類型（可多選）■A□B□C□D□E所需先導(dǎo)課程計算機基礎(chǔ)（理）教材作者名稱出版社出版時間趙宏，王愷數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用上海交通大學出版社2012參考書目作者名稱出版社出版時間趙端陽,左伍衡算法分析與設(shè)計—以大學生程序設(shè)計競賽為例清華大學出版社2012嚴蔚敏,吳偉民數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學出版社2007張銘,王騰蛟,趙海燕數(shù)據(jù)結(jié)構(gòu)與算法高等教育出版社2008SartajSahni著汪詩林，孫曉東等譯數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用——C++描述機械工業(yè)出版社2009教學目標詳細說明學生學習課程后在知識、技能、態(tài)度等方面達到的狀態(tài)，陳述應(yīng)力求明確、具體，并可以觀察和測量，600字以內(nèi)一、知識方面掌握線性表、棧、隊列、樹、圖等數(shù)據(jù)結(jié)構(gòu)的基本概念、原理及相關(guān)算法；理解直接插入排序、希爾排序、簡單選擇排序、冒泡排序、快速排序等常用排序算法的基本原理；理解順序查找、二分查找、分塊查找、二叉排序樹查找、哈希查找等常用查找算法的基本原理；掌握標準模板庫中vector、string、set、multiset、map、multimap、deque、list、stack、queue、priority_queue等常用容器的使用方法。二、技能方面能夠應(yīng)用線性表、棧、隊列、樹、圖等數(shù)據(jù)結(jié)構(gòu)將實際問題模型化，并通過選擇或設(shè)計相關(guān)算法來解決實際問題；能夠應(yīng)用標準模板庫中的容器快速編寫C++程序，通過計算機運行程序完成實際問題的求解。三、思維方面具備較好的計算思維能力，能夠在學習和工作中自覺運用計算的思維方式更好地解決專業(yè)問題。課程在學生培養(yǎng)中的地位和作用課程開設(shè)的必要性及其在教學計劃中對學生培養(yǎng)的作用，400字以內(nèi)一、課程開設(shè)的必要性在解決生活或工作中的一些問題時，通常需要綜合運用多種思維方式。在科學思維的譜系中，真正具備了系統(tǒng)和完善的表達體系的思維模式只有三個，分別是邏輯思維、實證思維和計算思維。大學教育中開設(shè)數(shù)學、物理和計算機等公共基礎(chǔ)課程的主要目的就是對學生這三種思維方式的培養(yǎng)。作為計算機公共基礎(chǔ)系列課程之一，本課程對理工類學生計算思維能力的培養(yǎng)有著非常重要的作用和意義。二、在教學計劃中對學生培養(yǎng)的作用本課程是公共計算機基礎(chǔ)教學部針對理工類非計算機專業(yè)學生開設(shè)的一門校公共必修課。雖然本課程的教學內(nèi)容與學生的專業(yè)課程無直接聯(lián)系，但通過本課程的學習，有助于培養(yǎng)學生的計算思維、使學生自覺運用計算的思維方式解決日常生活和專業(yè)學習中遇到的實際問題，從而進一步促進學生的專業(yè)課程學習、提高學生的專業(yè)創(chuàng)新能力。主要教學手段和方法為完成教學目標而采用的主要教學方法和手段，以及方法和手段的改革情況，600字以內(nèi)一、主要教學方法和手段（1）案例教學以數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)、算法設(shè)計為主線，通過大量實例講解如何借助數(shù)據(jù)結(jié)構(gòu)來描述實際問題、如何設(shè)計算法來解決實際問題，以培養(yǎng)學生的計算思維為教學目的。（2）教師課堂講授和學生自主學習相結(jié)合通過課程教學網(wǎng)站為學生提供用于自主學習的教學資源，方便學生在課外靈活安排時間鞏固教師課堂講授內(nèi)容及進行拓展學習。（3）理論和實踐相結(jié)合本課程包括講授課和上機課，在講授課上注重講解基本理論知識，在上機課上注重提高學生的實踐能力。（4）充分發(fā)揮學生主觀能動布置大作業(yè)，鼓勵學生根據(jù)課上教師講授內(nèi)容及課外拓展學習內(nèi)容自己去選擇要解決的問題、設(shè)計解決問題的算法、撰寫算法設(shè)計報告、編寫程序?qū)崿F(xiàn)問題求解、制作講稿并講解。通過發(fā)揮學生的主觀能動，激發(fā)學生對課程的興趣，增強學生對課程內(nèi)容的理解。二、方法和手段的改革情況（1）構(gòu)建課程教學網(wǎng)站，并逐步豐富用于學生自主學習的課程資源。（2）以大作業(yè)的形式激發(fā)學生的主觀能動，鍛煉學生自覺運用計算的思維方式解決實際問題的能力、培養(yǎng)學生的寫作能力和講述能力。考核方式明確說明考試、平時成績（討論、作業(yè)、測驗、出勤等）、實驗實踐所占總成績比重，以及考試的形式（閉卷、開卷），400字以內(nèi)本課程采用“大作業(yè)+平時成績+期末考核”的評價方式：各部分的比例分別為20%，30%和50%。其中，大作業(yè)：學生自主選題，分析問題、選取數(shù)據(jù)結(jié)構(gòu)、設(shè)計算法、編程實現(xiàn)、撰寫報告、制作講稿、講解并回答教師提出的問題。平時成績：由任課老師評定，主要參考作業(yè)提交數(shù)量、質(zhì)量、是否及時，以及理論課、上機課的出勤情況，平時上機測試等情況。期末考核：采用機考、閉卷形式。課程學習要求和建議對學生學習該課程的相關(guān)要求及學習建議，800字以內(nèi)1、正確認識本課程在本科教學計劃中的地位和作用，明確本課程的學習目的。2、積極發(fā)揮主觀能動，從被動學習轉(zhuǎn)為主動學習，一方面充分利用課堂時間進行課程內(nèi)容的學習和實踐，另一方面安排一定的課外時間進行自主學習。3、不要局限于課堂上學習的內(nèi)容，應(yīng)拓展知識面，在學習基本知識的同時也要考慮如何借助本課程學習的知識更好地去解決專業(yè)學習和研究中遇到的問題。4、多動手實踐，一方面能夠鞏固課上所學內(nèi)容，另一方面能夠認識到學習過程中的一些潛在問題。課程內(nèi)容及學時分配列出課程主要章節(jié)的標題，在每個標題下寫出主要內(nèi)容的細目及學時數(shù)。各教學環(huán)節(jié)（習題、實驗、課堂討論、寫作、社會調(diào)查、測驗、考試）的內(nèi)容和時數(shù)。實驗課程要詳細列出每個實驗的名稱、內(nèi)容、學時數(shù)、實驗性質(zhì)（驗證性、綜合性、設(shè)計性）、實驗類別（選做、必做）和實驗的分組情況等。實踐教學課程要寫出相應(yīng)的時間、地點、方式、教學內(nèi)容等。第1部分概論教師講授內(nèi)容：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，算法與算法分析基礎(chǔ)學生自學內(nèi)容：算法設(shè)計基本方法與策略基礎(chǔ)要求：理解數(shù)據(jù)結(jié)構(gòu)和算法的基本概念，掌握算法的時間復(fù)雜度和空間復(fù)雜度分析方法，了解基本的算法設(shè)計策略。學時：講授2學時。第2部分線性表及基于線性表的問題求解教師講授內(nèi)容：線性表及其抽象數(shù)據(jù)類型，線性表的順序存儲結(jié)構(gòu)及實現(xiàn)，線性表的鏈式存儲結(jié)構(gòu)及實現(xiàn)，vector容器、list容器和deque容器。學生自學內(nèi)容：string容器、set容器、multiset容器、map容器、multimap容器、應(yīng)用實例（教材第2.4節(jié)）。上機實習1順序表的操作（2學時）（1）對于最多由100名學生的姓名和成績信息（如王洪，90）構(gòu)成的線性表，采用順序存儲結(jié)構(gòu)并完成下面的問題。①統(tǒng)計成績大于等于95分的人數(shù)，并輸出這些學生的姓名。②刪除成績小于20分的信息。③以60分為分界線，將表中所有小于60的信息放在表的前半部分，大于60的元素放在表的后半部分。（2）有兩個順序表S1和S2，假設(shè)他們的元素值從左到右遞增排列，且沒有重復(fù)值。設(shè)計一個Merge函數(shù)，該函數(shù)的功能是將這兩個表合并成一個元素值仍由小到大排列的順序表S。（3）用順序表解決選旅長的問題（有10個驢友需要選出一個負責人——旅長。大家制定了選旅長的規(guī)則：所有人圍成一圈，從1到10為每個人進行編號，并設(shè)定一個數(shù)字N。然后，從編號為1的驢友開始按照編號順序循環(huán)報數(shù)，數(shù)到N的驢友出圈，重復(fù)此過程，最后剩下那個驢友就是旅長。）上機實習2線性鏈表的操作（2學時）（1）對于最多由100名學生的姓名和成績信息（王洪，90）構(gòu)成的線性表建立單向鏈表，并完成下面的問題：①統(tǒng)計成績大于等于95分的人數(shù)，并輸出這些學生的姓名。②刪除成績小于20分的信息。③以60分為分界線，將表中所有小于60的信息放在表的前半部分，大于60的元素放在表的后半部分。（2）有兩個帶表頭結(jié)點的存放整數(shù)的單向鏈表Link1和Link2，假設(shè)他們的元素值從左到右遞增排列，且沒有重復(fù)值。設(shè)計一個Merge函數(shù)，該函數(shù)的功能是將這兩個單向鏈表合并成一個元素值仍由小到大排列的單向鏈表Link。（3）設(shè)計算法并測試。將單向鏈表中關(guān)鍵字的值重復(fù)的結(jié)點刪除，使得鏈表中各結(jié)點的值均不相同。要求：理解線性表的基本概念和抽象數(shù)據(jù)類型；掌握線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)；能夠應(yīng)用線性表解決實際問題；了解線性表的C++實現(xiàn)方法；了解循環(huán)鏈表和雙向鏈表。學時：講授4學時，上機4學時。第3部分棧和隊列及基于棧和隊列的問題求解教師講授內(nèi)容：棧及其抽象數(shù)據(jù)類型，棧的表示及實現(xiàn)，隊列及抽象數(shù)據(jù)類型，隊列的表示及實現(xiàn)，stack容器、queue容器和priority_queue容器。學生自學內(nèi)容：應(yīng)用實例（教材第3.5節(jié)）。要求：理解棧和隊列的基本概念和抽象數(shù)據(jù)類型；掌握棧和隊列的順序表示、鏈式表示及其C++實現(xiàn)方法，能夠應(yīng)用棧和隊列解決實際問題。上機實習1棧的操作（2學時）（1）用棧實現(xiàn)【例3-1】中將十進制數(shù)轉(zhuǎn)換為其他各種進制（如二進制、八進制、十六進制）數(shù)的問題。（2）請利用已有的基本操作，實現(xiàn)棧元素的正序輸出，并編寫主函數(shù)就進行測試。主函數(shù)要求先建立一順序棧S，若干個元素依次入棧，然后執(zhí)行“Print(S);”語句，在屏幕上按輸入的順序輸出棧中的元素。例如，將1、3、5、7、9、11、13、15等元素依次入棧，輸出結(jié)果仍然是1、3、5、7、9、11、13、15。（3）用棧的特性來解決一個生活中的實際問題。例如，把一個字符串倒序輸出。上機實習2隊列的操作（2學時）（1）使用隊列實現(xiàn)【例3-2】中的在屏幕上顯示楊輝三角的問題。（2）編寫程序?qū)崿F(xiàn)利用一個隊列中的元素創(chuàng)建一個棧的算法，將隊列的頭作為棧頂，隊列的尾作為棧底，創(chuàng)建棧后隊列保持不變。學時：講授4學時，上機4學時。第4部分樹和二叉樹及基于樹和二叉樹的問題求解教師講授內(nèi)容：樹的基本概念，二叉樹及其基本性質(zhì)，二叉樹的抽象數(shù)據(jù)類型和表示方式，二叉樹順序表示的實現(xiàn)，二叉樹的遍歷及常用操作，二叉樹遍歷的遞歸實現(xiàn)。學生自學內(nèi)容：二叉樹鏈式存儲、二叉樹遍歷及常用操作的C++實現(xiàn)，哈夫曼樹和哈夫曼碼，樹的表示法，樹、森林與二叉樹的轉(zhuǎn)換。要求：掌握樹的定義、表示形式和基本術(shù)語；掌握二叉樹的定義和基本性質(zhì)；掌握二叉樹的順序表示和鏈式表示方法；二叉樹順序表示的C++實現(xiàn)，掌握二叉樹的遍歷和常用操作及二叉樹遞歸遍歷算法的C++實現(xiàn)；了解哈夫曼樹和哈夫曼碼的基本概念、哈夫曼樹的構(gòu)造方法及哈夫曼碼的編解碼方法；了解樹的雙親表示法、孩子表示法、孩子雙親表示法、孩子兄弟表示法；了解樹、森林轉(zhuǎn)換為二叉樹的方法，及二叉樹轉(zhuǎn)換為樹、森林的方法；了解二叉樹鏈式存儲、二叉樹遍歷及常用操作的C++實現(xiàn)；了解二叉樹和樹的應(yīng)用；能夠應(yīng)用二叉樹和樹解決實際問題。上機實習1二叉樹的操作（2學時）（1）構(gòu)建一棵鏈式表示的二叉樹，其中每一結(jié)點保存一個整數(shù)，且任一結(jié)點中的整數(shù)值大于其左子樹各結(jié)點中的整數(shù)值、小于其右子樹各結(jié)點中的整數(shù)值。假設(shè)將值為43、56、37、28、17、39、22、70的各結(jié)點依次插入到二叉樹中，插入完畢后采用中序遍歷方式輸出二叉樹中每一結(jié)點的整數(shù)值。（2）構(gòu)建一棵鏈式表示的二叉樹，其中每一結(jié)點保存一名學生信息（包括學號、姓名和成績），且任一結(jié)點中學生的學號大于其左子樹各結(jié)點中學生的學號、小于其右子樹各結(jié)點中學生的學號。假設(shè)將以下六名學生信息依次插入到二叉樹中：("1102030","李剛",65)、("1102035","王濤",92)、("1102041","吳明",73)、("1102023","馬洪",85)、("1102033","趙冰",90)、("1102045","陳立",88)，插入完畢后分別在二叉樹中查找學號為1102033和1102037的結(jié)點，若查找成功則將結(jié)點中保存的學生信息輸出，否則輸出“查找失敗！”。上機實習2哈夫曼樹和哈夫曼碼（2學時）（1）假設(shè)要編碼的字符集為{A,B,C,D,E,F}，各字符的出現(xiàn)次數(shù)為{20,5,13,8,23,3}，構(gòu)造一棵哈夫曼樹。（2）利用第1題中構(gòu)造的哈夫曼樹，得到字符串“FACE”的哈夫曼編碼，再將編碼結(jié)果輸入到哈夫曼樹中，得到解碼結(jié)果“FACE”。學時：講授4學時，上機4學時。第5部分圖及基于圖的問題求解教師講授內(nèi)容：圖的基本概念及特性，圖的抽象數(shù)據(jù)類型和表示方式，圖的遍歷。學生自學內(nèi)容：圖的C++實現(xiàn)，最小生成樹和最短路徑。要求：掌握圖的基本概念和應(yīng)用；掌握圖的鄰接矩陣表示法、鄰接壓縮表表示法和鄰接鏈表表示法；掌握圖的廣度優(yōu)先遍歷和深度優(yōu)先遍歷方法；掌握最小生成樹和最短路徑的計算方法；能夠應(yīng)用圖解決實際問題；了解圖的C++實現(xiàn)方法。上機實習圖的操作（4學時）（1）實現(xiàn)【例5-1】，城市之間修建高速公路的工程造價如圖5-4（a）所示。（2）實現(xiàn)【例5-2】，從一個地方到另一個地方的里程數(shù)如圖5-4（b）所示。（3）構(gòu)建一個人際關(guān)系網(wǎng)：假設(shè)有李剛、王濤、吳明、馬洪、趙冰、陳立6個人，其中(李剛,王濤)、(李剛,馬洪)、（李剛,趙冰）、（王濤,趙冰）、（吳明,馬洪）、（馬洪,陳立）是朋友關(guān)系。請編程實現(xiàn)該人際關(guān)系網(wǎng)，并按關(guān)系遠近輸出與吳明有直接或間接關(guān)系的人（如馬洪是吳明的朋友；陳立、李剛是馬洪的朋友，即吳明的朋友的朋友；王濤、趙冰是李剛的朋友，即吳明的朋友的朋友的朋友）。學時：講授4學時，上機4學時。第6部分排序算法教師講授內(nèi)容：排序算法及常見排序算法比較，插入排序，選擇排序（堆排序不講），交換排序（快速排序只講原理、不講實現(xiàn)）。學生自學內(nèi)容：堆排序、快速排序的C++實現(xiàn)、歸并排序、箱排序和基數(shù)排序的C++實現(xiàn)。要求：掌握各種排序算法的適用情況；理解直接插入排序、希爾排序、簡單選擇排序和冒泡排序的基本原理，并掌握其C++實現(xiàn)方法；理解快速排序的基本原理，并了解其C++實現(xiàn)方法；了解堆排序、歸并排序、箱排序和基數(shù)排序的基本原理其C++實現(xiàn)方法。上機實習插入排序、選擇排序和交換排序（3學時）假設(shè)有以下6名學生的信息（包括學號、姓名和成績）：("1102030","李剛",65)、("1102035","王濤",92)、("1102041","吳明",73)、("1102023","馬洪",85)、("1102033","趙冰",90)、("1102045","陳立",88)。分別用冒泡排序算法、希爾排序算法和快速排序算法，按學號從低到高對學生信息進行排序并將排序結(jié)果輸出。學時：講授3學時，上機3學時。第7部分查找算法教師講授內(nèi)容：查找算法及常見查找算法比較，靜態(tài)查找及其實現(xiàn)，動態(tài)查找（只講原理、不講實現(xiàn)）。學生自學內(nèi)容：動態(tài)查找的C++實現(xiàn)，哈希查找及其C++實現(xiàn)。要求：掌握各種查找算法的適用情況；理解順序查找、折半查找和分塊查找的基本原理，并掌握其C++實現(xiàn)方法；掌握二叉排序樹的生成和查找方法，并了解其C++實現(xiàn)方法；掌握哈希表、哈希函數(shù)和沖突的處理方法，了解哈希查找的C++實現(xiàn)方法。上機實習1靜態(tài)查找（1學時）假設(shè)有以下6名學生的信息（包括學號、姓名和成績）：("1102023","馬洪",85)、("1102030","李剛",65)、("1102033","趙冰",90)、("1102035","王濤",92)、("1102041","吳明",73)、("1102045","陳立",88)。分別用順序查找算法和折半查找算法，按學號對學生信息進行查找。上機實習2動態(tài)查找和哈希查找（2學時）假設(shè)有以下6名學生的信息（包括學號、姓名和成績）：("1102030","李剛",65)、("1102035","王濤",92)、("1102041","吳明",73)、("1102023","馬洪",85)、("1102033","趙冰",90)、("1102045","陳立",88)。分別用二叉排序樹查找算法按姓名對學生信息進行查找和哈希算法、用哈希算法，按學號對學生信息進行查找。學時：講授3學時，上機3學時。第8部分經(jīng)典實例教師講授內(nèi)容：分治策略，貪心策略，動態(tài)規(guī)劃策略，回溯策略，分支限界策略。學生自學內(nèi)容：使用各種算法設(shè)計策略解決實際問題的應(yīng)用實例。要求：掌握分治策略、貪心策略、動態(tài)規(guī)劃策略、回溯策略和分支限界策略的基本思想、算法設(shè)計步驟及程序模式；能夠使用這些策略設(shè)計問題求解算法；了解應(yīng)用算法設(shè)計策略求解實際問題的C++實現(xiàn)方法。上機實習《數(shù)據(jù)結(jié)構(gòu)與算法》課程大作業(yè)（8學時）3~7人一組，上機課上每組學生派一名代表按PPT講稿講解所求解的問題和具體求解算法（講解時間在4~6分鐘），講解后教師或其他學生向該組中的每名學生問1~3個問題，根據(jù)回答情況給每名學生打不同的分數(shù)。評分標準如下：評分項評分內(nèi)容分值選題（5分）選題難易程度5文檔（10分）是否按時提交（第12周及之前提交給滿分，每晚一周扣1分，最晚不得超過第14周）3問題描述是否清楚2求解算法描述是否清楚3文檔（包括Word文檔和PPT講稿）是否規(guī)范2講解（5分）講解是否清楚2回答問題是否正確3學時：講授8學時，上機8學時。課程簡要介紹簡要介紹課程的目標、主要授課內(nèi)容、授課對象以及在學生培養(yǎng)中的作用，200—500字本課程以數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)、算法設(shè)計為主線，通過大量實例講解如何借助數(shù)據(jù)結(jié)構(gòu)來描述實際問題、如何設(shè)計算法來解決實際問題，以培養(yǎng)學生的計算思維為教學目標。主要授課內(nèi)容包括：各種數(shù)據(jù)結(jié)構(gòu)的基本概念、原理；標準模板庫的使用方法，借助標準模板庫快速解決實際問題；常用排序和查找算法；應(yīng)用問題的經(jīng)典求解方法。本課程是針對理工類非計算機專業(yè)學生開設(shè)的一門校公共必修課。雖然本課程的教學內(nèi)容與學生的專業(yè)課程無直接聯(lián)系，但通過本課程的學習，有助于培養(yǎng)學生的計算思維、使學生自覺運用計算的思維方式解決日常生活和專業(yè)學習中遇到的實際問題，從而進一步促進學生的專業(yè)課程學習、提高學生的專業(yè)創(chuàng)新能力。英文課程簡要介紹課程介紹的英文翻譯版Thiscourseprovidesthefundamentalknowledgeofdatastructureandplacesemphasisonalgorithmdesign.Throughalotofexamplestoexplainhowtousethedatastructuretodescribethepracticalproblems,howtodesignalgorithmstosolvepracticalproblems.Themainobjectiveofthiscourseistoteachco