北京數據結構培訓 2019-08-20 10:49:21

北京學堂在線為參加計算機考研的學員設置數據結構培訓班，講授的主題從基礎的數據結構，圍繞各類數據結構的設計與實現，揭示其中的規律原理與方法技巧，針對算法設計及其性能分析，使學生了解并掌握主要的套路與手段。

“

數據結構是計算機科學的關鍵內容，也是構建高效算法的必要基礎。其中涉及的知識，在相關專業的課程系統中始終處于核心位置。本課程旨在圍繞各類數據結構的設計與實現，揭示其中的規律原理與方法技巧；同時針對算法設計及其性能分析，使學生了解并掌握主要的套路與手段。講授的主題從基礎的數據結構，一直延伸至新近的研究成果。

”

“

第零章

選課之前；考核方式；OJ系統說明；OJ帳號驗證；關于課程教材與講義；關于討論區；微信平臺；PA討論；PA晉級申請

章緒論(上)

（a）計算；（b）計算模型；（c）大O記號

章緒論(下)

（d）算法分析；（e）迭代與遞歸；（xc）動態規劃；本章測驗

第二章向量(上)

（a）接口與實現；（b）可擴充向量；（c）無序向量；（d1）有序向量：唯一化；（d2）有序向量：二分查找

第二章向量(下)

（d3）有序向量：Fibonacci查找；（d4）有序向量：二分查找（改進）；（d5）有序向量：插值查找；（e）起泡排序；（f）歸并排序；本章測驗

第三章列表

（a）接口與實現；（b）無序列表；（c）有序列表；（d）選擇排序；（e）插入排序；（xd）習題輔導：LightHouse；本章測驗

第四章棧與隊列

（a）棧接口與實現；（c1）棧應用：進制轉換；（c2）棧應用：括號匹配；（c3）棧應用：棧混洗；（c4）棧應用：中綴表達式求值；（c5）棧應用：逆波蘭表達式；（d）隊列接口與實現；本章測驗

第五章二叉樹

（a）樹；（b）樹的表示；（c）二叉樹；（d）二叉樹實現；（e1）先序遍歷；（e2）中序遍歷；（e4）層次遍歷；（e5）重構；本章測驗

第六章圖

（a）概述；（b1）鄰接矩陣；（c）廣度優先搜索；（d）深度優先搜索；本章測驗

查詢PA成績和加分

PA成績；加分

”

“

1、教材

（1）鄧俊輝，數據結構（C++語言版）,第三版,清華大學出版社,2013年9月,ISBN:7-302-33064-6；（2）鄧俊輝，數據結構習題解析（C++語言版）,清華大學出版社,2013年9月,ISBN:7-302-33065-3；（3）注冊本課程的學生，可免費下載電子版勘誤表、樣章、示例代碼包、講義等資料。

2、編程習題平臺

課程中的編程作業，需要在實驗平臺http://dsa.cs.tsinghua.edu.cn/oj/上完成。選修本課的同學，請用與xuetangX賬號相同的郵箱在該平臺上注冊賬號。

3、成績評定

最終成績由以下兩個方面累計而得：（1）課后測驗（共6組）：10%x 6=60%；（2）編程習題（共4組，每組3題）：10%x 4=40%

4、先修知識

盡管“數據結構”是一門綜合性的課程，但這并不意味著你必須精通所有的相關課程。實際上，你只需掌握若干重要的數學概念及方法，以及C/C++語言編程的基本技巧。為確認自己是否適宜選修這門課程，不妨對照以下清單做一清點：C++語言程序設計基礎：類、繼承、重載、重寫、虛方法、模板；離散數學基礎:集合、偏序集、良序、數學歸納法、級數、遞歸、遞推；概率基礎:隨機分布、數學期望、期望值的線性率。

”