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

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