《數(shù)據(jù)結(jié)構(gòu)與算法》教學(xué)大綱.doc

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)雙語教學(xué)大綱課程編號：12000042英文名稱：Data Structures and Algorithms Design學(xué)分：4 學(xué)時(shí)：64（其中理論學(xué)時(shí)：52 上機(jī)輔導(dǎo)：12）適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)；軟件工程專業(yè)。一、 目的與任務(wù)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的一門綜合性基礎(chǔ)課程，主要使學(xué)生了解數(shù)據(jù)抽象的目的和意義，學(xué)會分析研究計(jì)算機(jī)加工的數(shù)據(jù)對象的特征，選擇合適的數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)以及相應(yīng)的算法。初步學(xué)會各種算法時(shí)間和空間開銷的分析方法同時(shí)學(xué)習(xí)本課程也是進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程。因此，要求學(xué)生能用算法語言書寫結(jié)構(gòu)清晰正確的算法。并通過上機(jī)實(shí)驗(yàn)，使學(xué)生受到嚴(yán)格的基本技術(shù)訓(xùn)練，以便為今后的工作實(shí)踐打好堅(jiān)實(shí)基礎(chǔ)。該課程是在離散數(shù)學(xué)、程序設(shè)計(jì)之后，在集合論、圖論等理論基礎(chǔ)上，以算法語言為工具，通過數(shù)據(jù)抽象的方法，研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法。它是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫、和面向?qū)ο蟪绦蛟O(shè)計(jì)等課程的重要基礎(chǔ)。本課程通過雙語教學(xué)的方式，使學(xué)生在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的同時(shí)，加強(qiáng)英語的聽、讀、寫、說的能力。二、 教學(xué)內(nèi)容及學(xué)時(shí)分配（理論教學(xué)52學(xué)時(shí)+上機(jī)輔導(dǎo)12學(xué)時(shí)）第一章 緒論（理論教學(xué)1學(xué)時(shí)+0上機(jī)輔導(dǎo)學(xué)時(shí)）Chapter 1 Preface什么是數(shù)據(jù)結(jié)構(gòu)，基本概念和術(shù)語，數(shù)據(jù)抽象和面向?qū)ο蟪绦蛟O(shè)計(jì)。 Definitions of data structure, Basic concepts and terminology, Data abstraction and OOP.第二章 算法分析（理論教學(xué)1學(xué)時(shí)+0上機(jī)輔導(dǎo)學(xué)時(shí)）Chapter 2 Algorithm Analysis程序、算法的定義，算法的時(shí)間特性，算法分析的方法和目的。Definition of program and algorithm, Time complexities, Methods and goals of algorithm analysis第三章 線性表、堆棧和隊(duì)列（理論教學(xué)7學(xué)時(shí)+4上機(jī)輔導(dǎo)學(xué)時(shí)）Chapter 3 Lists, Stacks, and Queues抽象數(shù)據(jù)類型；線性表的ADT， 線性表的順序存儲結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)與庫函數(shù)；線性表的應(yīng)用；靜態(tài)鏈表；堆棧的順序存儲結(jié)構(gòu)，堆棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)；棧的應(yīng)用；棧在后綴、中綴表達(dá)式的應(yīng)用；循環(huán)隊(duì)列，隊(duì)列應(yīng)用。Definition of ADT, List ADT，Array implementation of lists, Linked Lists, Data structure and library of function, Applictions of lists, Cursor implementation of linked lists, Stack ADT, Array implementation of lists, Linked lists implementation of stack, Applictions of stacks, Postfix and infix evaluation, Circular queue, Applictions of queue實(shí)驗(yàn)：一元多項(xiàng)式程序，股票交易撮合，表達(dá)式中綴向后綴的轉(zhuǎn)換，飛機(jī)場調(diào)度。LAB: 1.Polynomial evaluation, 2. Stock trading, 3. Infix to Postfix Conversion, 4. Schedule of airport第四章： 矩陣和廣義表（理論教學(xué)3學(xué)時(shí)+2上機(jī)輔導(dǎo)學(xué)時(shí)）Chapter 4 Matrix And Generic List矩陣的壓縮存儲，矩陣運(yùn)算實(shí)現(xiàn)。廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，廣義表的遞歸算法，廣義表的應(yīng)用。Compression of matrix, Operations on compressed matrix, Linked implementation of generic lists, Recursive functions of generic lists, Applications of generic list.實(shí)驗(yàn)：矩陣乘法實(shí)現(xiàn)；廣義表的建立及基本操作。LAB: 1. Multiplication of compressed matrix, 2. Basic operation of generic list第五章 樹（理論教學(xué)8學(xué)時(shí)+2上機(jī)輔導(dǎo)學(xué)時(shí)）Chapter 5 Trees樹的定義，樹的兄弟表示法，樹的遍歷，樹的應(yīng)用；二叉樹的定義和基本特性，遍歷二叉樹，二叉樹的遞歸操作，線索二叉樹；二叉排序樹，平衡二叉樹，Splay樹，B-樹，二叉樹應(yīng)用。Definition of tree ADT, FirstChild-NextSibling Representation, Tree traversals, Applications of trees, Definitions and properties of binary trees, Traversal of trees, Recursive functions of trees, Threaded binary trees, Binary search trees, AVL trees, Splay trees, B-trees, Application of binary trees.實(shí)驗(yàn)：樹的建立及運(yùn)算，平衡二叉排序樹，博弈。LAB: Basic operation of trees, AVL tress, Game trees.第六章 優(yōu)先級隊(duì)列（理論教學(xué)2學(xué)時(shí)+0上機(jī)輔導(dǎo)學(xué)時(shí)）Chapter 6 Priority Queues堆的定義和特性，堆的運(yùn)算，堆的應(yīng)用, d-Heaps。Definitions and properties of heaps, Operations of heaps, Applications of heaps, d-Heaps.第七章 排序（理論教學(xué)6學(xué)時(shí)+2上機(jī)輔導(dǎo)學(xué)時(shí)）Chapter 7 Sorting插入排序，排序效率分析，希爾排序，堆排序，合并排序，快速排序，大型數(shù)據(jù)的排序，桶排序和基數(shù)排序。Insertion sort, A lower bound for simple sorting algorithms, Shellsort, Heapsort, Mergesort, Quicksort, Sorting large structures, Bucket sort and radix sort, 實(shí)驗(yàn)：快速排序，堆排序。LAB：Quicksort, Heapsort.第八章 哈希表（理論教學(xué)3學(xué)時(shí)+0上機(jī)輔導(dǎo)學(xué)時(shí)）Chapter 8 Hashing哈希表的基本概念，哈希函數(shù)設(shè)計(jì)，沖突解決方法, 哈希表的查找、插入、刪除、重建運(yùn)算。Basic concepts of hash tables, Hash functions designing, Collision solving methods, Basic operations of hash tables, Rehashing. 第九章 等價(jià)類（理論教學(xué)3學(xué)時(shí)+0上機(jī)輔導(dǎo)學(xué)時(shí)）Chapter 9 The Disjoint Set ADT等價(jià)關(guān)系的基本概念，動(dòng)態(tài)等價(jià)問題，等價(jià)關(guān)系基本操作的實(shí)現(xiàn)，提高效率的方法。Basic concepts of Equivalence Relations, Dynamic equivalence problem, Basic operations of equivalence class, smart algorithm.第十章 圖（理論教學(xué)12學(xué)時(shí)+2上機(jī)輔導(dǎo)學(xué)時(shí)）Chapter 10 Graph Algorithms圖的定義和術(shù)語，圖的存儲結(jié)構(gòu)，拓?fù)渑判?，AOV網(wǎng)，最短路徑，AOE網(wǎng)，關(guān)鍵路徑，網(wǎng)絡(luò)流量分配，最小生成樹，深度優(yōu)先搜索，廣度優(yōu)先搜索，歐拉圖，圖的連通性，人工智能中的問題求解。Definintions and terminology of graph, Representation of Graphs, AOV network, Topological sort, Shortest path algorithms, AOE network, Critical Path, Network flow problems, Minimum spanning tree, Applications of Depth-First Search, Biconnectivity, Breadth-first search, Euler Circuits, Problem solving in AI.實(shí)驗(yàn)：最短路徑，關(guān)鍵路徑LAB: Shortest path problem, Critical Path Problem*第十一章 算法設(shè)計(jì)（理論教學(xué)6學(xué)時(shí)+0上機(jī)輔導(dǎo)學(xué)時(shí)）Chapter 11 Algorthm Design Techniques貪婪算法，分治法，動(dòng)態(tài)法，回溯法Greedy Algorithms, Divide and Conquer, Dynamic Programming, Backtracking Algorithms說明：其中的*部分的章節(jié)和內(nèi)容為可選內(nèi)容。如果不講授可選部分的內(nèi)容，6學(xué)時(shí)可以如下分配：五一假期4學(xué)時(shí)，期末復(fù)習(xí)2學(xué)時(shí)。三、 考核與成績評定采用日常性考核（作業(yè)、實(shí)驗(yàn)）和期末終結(jié)性考核相結(jié)合的方式。作業(yè)、實(shí)驗(yàn)成績占40%，期末為閉卷筆試考試，成績占60%。四、 大綱說明本課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、軟件工程專業(yè)本科生的核心課程。本課程的先修課程包括：離散數(shù)學(xué)、高級程序設(shè)計(jì)語言（C/C+）。本課程的后繼課程主要包括：軟件基礎(chǔ)實(shí)習(xí)、操