北京大學(xué)“數(shù)據(jù)結(jié)構(gòu)與算法”教學(xué)設(shè)計(jì)

文章編號(hào)：1672-5913(2008)20-0005-07

摘要：本文介紹了“數(shù)據(jù)結(jié)構(gòu)與算法”課程的教學(xué)理念、教學(xué)設(shè)計(jì)、教學(xué)方法和手段的改革與創(chuàng)新。根據(jù)ACM/IEEE CC2005和教育部計(jì)算機(jī)教指委CCC2006學(xué)科規(guī)范，從問(wèn)題求解出發(fā)，在基礎(chǔ)理論、抽象和設(shè)計(jì)的三個(gè)層次組織課程內(nèi)容體系，特別強(qiáng)調(diào)以知識(shí)與能力培養(yǎng)為導(dǎo)向的教學(xué)目標(biāo)和定位。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；算法；教學(xué)體系

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：B

引言

“數(shù)據(jù)結(jié)構(gòu)與算法”是計(jì)算機(jī)專業(yè)的核心課程之一，本科教學(xué)的重中之重。如圖1所示，本課程上承“計(jì)算概論”(含C語(yǔ)言程序設(shè)計(jì))與“程序設(shè)計(jì)實(shí)習(xí)”(講授C++程序設(shè)計(jì)，并布置綜合實(shí)習(xí))，下啟“算法分析與設(shè)計(jì)”和“計(jì)算復(fù)雜性理論”，同時(shí)是操作系統(tǒng)、軟件工程、數(shù)據(jù)庫(kù)概論、編譯技術(shù)、人工智能、計(jì)算機(jī)圖形學(xué)等專業(yè)課程的必修先行課。很多應(yīng)用軟件都要使用到各種數(shù)據(jù)結(jié)構(gòu)和算法編寫程序進(jìn)行科學(xué)計(jì)算、模擬試驗(yàn)等。

圖1 “數(shù)據(jù)結(jié)構(gòu)與算法”在計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科課程群中的關(guān)鍵地位

本課程以美國(guó)最新ACM/IEEE CC2005課程體系和我國(guó)教育部CCC2006學(xué)科規(guī)范作為理論基礎(chǔ)，制定了先進(jìn)的課程內(nèi)容體系。從問(wèn)題求解出發(fā)，在基礎(chǔ)理論、抽象和設(shè)計(jì)的三個(gè)層次組織課程知識(shí)體系，從邏輯、存儲(chǔ)、運(yùn)算的角度組織數(shù)據(jù)結(jié)構(gòu)與算法，培養(yǎng)學(xué)生獨(dú)立地實(shí)現(xiàn)常用基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型，注重實(shí)踐能力和工程能力的培養(yǎng)，為將來(lái)從事計(jì)算機(jī)學(xué)科的學(xué)習(xí)、開(kāi)發(fā)和研究，或其他學(xué)科應(yīng)用計(jì)算機(jī)進(jìn)行問(wèn)題求解打下堅(jiān)實(shí)的基礎(chǔ)，有利于學(xué)生的未來(lái)發(fā)展。

以創(chuàng)建世界一流大學(xué)為辦學(xué)目標(biāo)，北京大學(xué)加大推進(jìn)高層次創(chuàng)新人才培養(yǎng)的工作。根據(jù)北京大學(xué)的辦學(xué)定位和理念，“數(shù)據(jù)結(jié)構(gòu)與算法”課程定位為理論與實(shí)踐并重的信息學(xué)科的核心主干專業(yè)基礎(chǔ)課程，也是很多非信息類理工專業(yè)學(xué)生的重要基礎(chǔ)課程。面向北京大學(xué)計(jì)算機(jī)類、電子類、非信息類三種不同的大專業(yè)方向，課程組針對(duì)不同基礎(chǔ)、不同能力的學(xué)生進(jìn)行分班教學(xué)。設(shè)置實(shí)驗(yàn)班、A類和B類三種類型，以學(xué)生為本，因材施教，進(jìn)行多元化、個(gè)性化的培養(yǎng)。讓每個(gè)學(xué)生得到最大的收獲。其中，實(shí)驗(yàn)班從學(xué)院優(yōu)秀學(xué)生中選拔，計(jì)算機(jī)和智能專業(yè)的學(xué)生以及部分編程能力強(qiáng)的學(xué)生修“數(shù)據(jù)結(jié)構(gòu)與算法A”和“數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)”，非信息類的理工專業(yè)和電子、微電子基礎(chǔ)較差的學(xué)生修“數(shù)據(jù)結(jié)構(gòu)與算法B”。

課程教學(xué)目標(biāo)可概括為以下三個(gè)方面：

(1) 強(qiáng)調(diào)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法的訓(xùn)練，從問(wèn)題求解的角度，培養(yǎng)學(xué)生運(yùn)用數(shù)據(jù)結(jié)構(gòu)和算法基本理論來(lái)分析和解決問(wèn)題的能力。

(2) 結(jié)合計(jì)算機(jī)科學(xué)技術(shù)的現(xiàn)代前沿研究課題，設(shè)計(jì)研究啟發(fā)式教學(xué)案例，擴(kuò)展學(xué)生知識(shí)體系，培養(yǎng)主動(dòng)學(xué)習(xí)、研究和創(chuàng)新意識(shí)。

(3) 注重實(shí)踐能力和工程能力的培養(yǎng)，使學(xué)生遵從軟件開(kāi)發(fā)的規(guī)范性，并建立起數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)和問(wèn)題求解的知識(shí)體系。

1課程基本信息

2 課程知識(shí)點(diǎn)的教學(xué)要求和學(xué)時(shí)分配

數(shù)據(jù)結(jié)構(gòu)，就是對(duì)于一批具有某種邏輯關(guān)系的相關(guān)數(shù)據(jù)，按一定的方法存儲(chǔ)組織，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合。數(shù)據(jù)結(jié)構(gòu)具有三個(gè)方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。數(shù)據(jù)結(jié)構(gòu)與算法的知識(shí)體系如圖2所示。

常見(jiàn)邏輯關(guān)系有：線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖結(jié)構(gòu)和文件結(jié)構(gòu)。常見(jiàn)的存儲(chǔ)方法有：順序方法、鏈接方法、索引方法、散列方法。

對(duì)于一種數(shù)據(jù)結(jié)構(gòu)，往往需要定義一些運(yùn)算。排序、檢索是最經(jīng)典的運(yùn)算，為了加快檢索速度往往需要預(yù)先建立索引。內(nèi)存索引主要用BST(二叉搜索樹(shù))，外存索引常用倒排和B+樹(shù)。

算法分析技術(shù)有助于根據(jù)問(wèn)題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)，并對(duì)時(shí)間和空間復(fù)雜性進(jìn)行必要的控制。對(duì)于存儲(chǔ)外存中的文件數(shù)據(jù)的訪問(wèn)速度，對(duì)文件的操作運(yùn)算應(yīng)該盡量減少訪問(wèn)次數(shù)。

抽象數(shù)據(jù)類型(Abstract Data Type，簡(jiǎn)稱ADT)是定義了一組運(yùn)算的數(shù)學(xué)模型，這種抽象的數(shù)據(jù)類型可以在較高級(jí)的算法中直接引用，而不用了解其實(shí)現(xiàn)細(xì)節(jié)，從而很好地支持了邏輯設(shè)計(jì)和物理實(shí)現(xiàn)的分離。

數(shù)據(jù)結(jié)構(gòu)課程的基本知識(shí)模塊是以數(shù)據(jù)的邏輯結(jié)構(gòu)為主線，順序介紹線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖結(jié)構(gòu)和文件結(jié)構(gòu)。在介紹每種數(shù)據(jù)結(jié)構(gòu)時(shí)，再討論其存儲(chǔ)結(jié)構(gòu)以及相關(guān)的算法。

在介紹完基本的數(shù)據(jù)結(jié)構(gòu)及其存儲(chǔ)結(jié)構(gòu)和相關(guān)的算法后，根據(jù)不同的專業(yè)，還將介紹一些擴(kuò)展研究?jī)?nèi)容，涉及到外排序、廣義表、稀疏矩陣、字符樹(shù)、Patricia樹(shù)、后綴樹(shù)、后綴數(shù)組、AVL、紅黑樹(shù)和伸展樹(shù)等高級(jí)數(shù)據(jù)結(jié)構(gòu)，有助于拓寬知識(shí)面，提高解決實(shí)際問(wèn)題的能力。

在實(shí)踐訓(xùn)練環(huán)節(jié)，選取來(lái)自于計(jì)算機(jī)科學(xué)技術(shù)的前沿應(yīng)用課題，例如XML DOM樹(shù)解析器、后綴樹(shù)、搜索引擎等，激發(fā)學(xué)生的學(xué)習(xí)興趣，培養(yǎng)學(xué)生的創(chuàng)新思維能力。

課程以問(wèn)題求解為導(dǎo)向，培養(yǎng)和提高學(xué)生理論、抽象、設(shè)計(jì)的能力。通過(guò)扎實(shí)的經(jīng)典基礎(chǔ)理論訓(xùn)練，幫助學(xué)生靈活地運(yùn)用問(wèn)題抽象、數(shù)據(jù)抽象、算法抽象來(lái)分析問(wèn)題，應(yīng)用數(shù)據(jù)結(jié)構(gòu)和算法來(lái)設(shè)計(jì)和實(shí)現(xiàn)相應(yīng)的程序，完成創(chuàng)新能力和實(shí)踐能力的訓(xùn)練。

以下是學(xué)時(shí)安排，課堂授課48小時(shí)，習(xí)題課6～16小時(shí)。分為基礎(chǔ)模塊、研究模塊和前沿模塊三大部分，可以根據(jù)學(xué)生程度選講。

圖2 “數(shù)據(jù)結(jié)構(gòu)與算法”知識(shí)體系圖

(1) 北京大學(xué)所有理工科學(xué)生需要掌握的數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)模塊，教員必講

1) 數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型、算法度量和評(píng)價(jià)

2) 線性表、棧和隊(duì)列

3) 字符串與模式匹配

4) 樹(shù)(二叉樹(shù)、森林)

5) 圖(有向、無(wú)向、DAG)

6) 內(nèi)排序：插入、分治、快速、堆、基數(shù)

7) 檢索：二分法檢索、散列

8) 索引：內(nèi)存BST索引、外存B+索引樹(shù)

(2) 研究模塊有以下內(nèi)容，教員根據(jù)學(xué)生的程度選講

1) 遞歸到非遞歸的轉(zhuǎn)換機(jī)制和方法

2) 非遞歸深度優(yōu)先周游二叉樹(shù)和穿線二叉樹(shù)

3) 地址排序

4) 各種排序算法的理論和實(shí)驗(yàn)時(shí)間代價(jià)的討論

5) 外排序

(3) 前沿模塊有以下內(nèi)容，實(shí)驗(yàn)班選講

1) 廣義表與內(nèi)存管理技術(shù)

2) 字符樹(shù)與后綴樹(shù)、后綴數(shù)組

3)AVL樹(shù)、伸展樹(shù)、紅黑樹(shù)等有效的動(dòng)態(tài)內(nèi)存索引技術(shù)

4) 倒排索引與搜索引擎技術(shù)

5)B/B+樹(shù)等動(dòng)態(tài)索引組織在數(shù)據(jù)庫(kù)中的應(yīng)用

針對(duì)實(shí)驗(yàn)班和計(jì)算機(jī)類的學(xué)生，可以在習(xí)題課時(shí)間段，介紹一些高級(jí)數(shù)據(jù)結(jié)構(gòu)和學(xué)科前沿等擴(kuò)展內(nèi)容。針對(duì)非計(jì)算機(jī)類的學(xué)生，可以刪減高級(jí)數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，適當(dāng)增加二叉樹(shù)/樹(shù)、圖、排序等課時(shí)。課時(shí)安排如表1所示。

3 教學(xué)目的和要求

“數(shù)據(jù)結(jié)構(gòu)與算法”是一門重要的計(jì)算機(jī)類基礎(chǔ)課程。其主要目的是使學(xué)生較全面地理解數(shù)據(jù)結(jié)構(gòu)的概念、掌握各種數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)現(xiàn)方式，比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)。通過(guò)學(xué)習(xí)，使學(xué)生能夠提高用計(jì)算機(jī)解決實(shí)際問(wèn)題的能力。

(1) 介紹基本數(shù)據(jù)結(jié)構(gòu)和基本算法分析技術(shù)。這一部分將介紹常用基本數(shù)據(jù)結(jié)構(gòu)的ADT及其應(yīng)用，包括線性結(jié)構(gòu)(線性表、串、棧和隊(duì)列)、二叉樹(shù)、樹(shù)、圖等；同時(shí)基于各種數(shù)據(jù)結(jié)構(gòu)所實(shí)施的運(yùn)算討論算法分析的基本技術(shù)，掌握時(shí)間和空間權(quán)衡的原則。

(2) 介紹排序、檢索和索引技術(shù)。這一部分將主要討論插入排序、Shell排序、堆排序、快速排序、歸并排序、基數(shù)排序等常用的各種排序算法及其時(shí)間和空間開(kāi)銷，并介紹文件管理(數(shù)據(jù)在外存中的組織形式)和外排序技術(shù)，以及自組織線性表、散列表、倒排文件、B/B+樹(shù)等常見(jiàn)的檢索和索引技術(shù)，及其各自相應(yīng)的時(shí)間和空間開(kāi)銷。

(3) 通過(guò)本課程的學(xué)習(xí)，學(xué)生將基本掌握數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)分析技術(shù)，提高程序設(shè)計(jì)的質(zhì)量；根據(jù)所求解問(wèn)題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)并對(duì)時(shí)間空間復(fù)雜性進(jìn)行必要的控制。

4 教學(xué)的重點(diǎn)、難點(diǎn)和教學(xué)方案

強(qiáng)調(diào)以知識(shí)與能力培養(yǎng)為導(dǎo)向的教學(xué)目標(biāo)和定位，注意教學(xué)的重點(diǎn)和難點(diǎn)以及教學(xué)突破方法，剖析重要數(shù)據(jù)結(jié)構(gòu)與算法思想方法，研究設(shè)計(jì)教學(xué)案例，注意教學(xué)實(shí)施的細(xì)節(jié)和方案。

(1) 課程的重點(diǎn)

1) 從廣度和深度上把握課程的知識(shí)體系，了解基本數(shù)據(jù)結(jié)構(gòu)和經(jīng)典算法，掌握理論、抽象和設(shè)計(jì)方法。

2) 根據(jù)實(shí)際問(wèn)題，選擇合適的數(shù)據(jù)模型，設(shè)計(jì)合適的算法，運(yùn)用所學(xué)理論知識(shí)實(shí)現(xiàn)問(wèn)題求解。

(2) 課程的難點(diǎn)

1) 算法的數(shù)學(xué)基礎(chǔ)：遞歸、遞推等分析方法，算法的時(shí)間空間度量，數(shù)學(xué)抽象能力的培養(yǎng)。

2) 線性結(jié)構(gòu)部分：棧在遞歸問(wèn)題求解中的應(yīng)用，基于字符串匹配的KMP算法。

3) 樹(shù)形結(jié)構(gòu)部分：基于二叉樹(shù)/樹(shù)周游的靈活應(yīng)用，森林的存儲(chǔ)與遍歷訪問(wèn)方法。

4) 圖結(jié)構(gòu)部分：圖的遍歷方法，Dijstra、Floyd、Prim、Kruskal等典型的圖應(yīng)用算法。

5) 排序部分：內(nèi)排序算法的穩(wěn)定性分析，內(nèi)排序算法的復(fù)雜性分析，置換選擇和選擇樹(shù)外排序，內(nèi)排序方法在各類實(shí)際問(wèn)題中的應(yīng)用。

6) 檢索部分：散列方法，散列在實(shí)際應(yīng)用中的性能分析。

7) 索引部分：磁盤多級(jí)索引結(jié)構(gòu)，倒排文件，B/B+樹(shù)的插入和刪除操作。

8) 高級(jí)數(shù)據(jù)結(jié)構(gòu)部分：Trie和Patricia字符樹(shù)，AVL、伸展樹(shù)、紅黑樹(shù)等平衡樹(shù)的插入刪除操作。

9) 數(shù)據(jù)結(jié)構(gòu)的綜合應(yīng)用：使學(xué)生把數(shù)據(jù)結(jié)構(gòu)和算法理論與編程實(shí)踐相結(jié)合，能夠靈活地應(yīng)用于實(shí)際的工程實(shí)踐。

(3) 教學(xué)實(shí)施方案

針對(duì)上述重點(diǎn)和難點(diǎn)，本課程從理論、抽象和設(shè)計(jì)的三個(gè)層次展開(kāi)數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)，注重?cái)?shù)據(jù)結(jié)構(gòu)基本概念和抽象數(shù)據(jù)類型表述，使得學(xué)生可以在不同的設(shè)計(jì)階段采用不同的抽象數(shù)據(jù)類型作為設(shè)計(jì)的基礎(chǔ)，在適當(dāng)?shù)某橄髮哟紊峡紤]程序的結(jié)構(gòu)和算法。對(duì)每種數(shù)據(jù)結(jié)構(gòu)都從其數(shù)學(xué)特性入手，先介紹其抽象數(shù)據(jù)類型；再討論其不同的存儲(chǔ)方法，與學(xué)生一起討論研究不同存儲(chǔ)實(shí)現(xiàn)下的可能算法；然后結(jié)合算法分析來(lái)討論各種存儲(chǔ)方法和算法的利弊，摒棄那些不適宜的方法。這樣就充分調(diào)動(dòng)了學(xué)生主動(dòng)學(xué)習(xí)的積極性，使學(xué)生學(xué)到了數(shù)據(jù)結(jié)構(gòu)與算法的思維方法。

充分利用先進(jìn)的交互式網(wǎng)絡(luò)多媒體教學(xué)手段。課上講授對(duì)重要知識(shí)點(diǎn)和關(guān)鍵算法都制作了PPT和Flash動(dòng)畫，利用多媒體動(dòng)態(tài)展示執(zhí)行流程，幫助學(xué)生理解數(shù)據(jù)結(jié)構(gòu)原理和算法技術(shù)。必要時(shí)輔以板書，并跟學(xué)生交互討論。

網(wǎng)絡(luò)教學(xué)平臺(tái)http://www.jpk.pku.edu.cn/pkujpk/course/ sjjg/是課堂教學(xué)的延伸。有多媒體演示講稿、全程視頻(“大學(xué)堂”的大學(xué)課程在線上開(kāi)放共享)、可執(zhí)行源程序代碼、經(jīng)典的習(xí)題和上機(jī)題及其參考答案、有詳細(xì)到知識(shí)點(diǎn)的課程導(dǎo)航等豐富的教學(xué)資源。課程的論壇每天都有助教答疑，及時(shí)解決學(xué)生的困惑。

擴(kuò)展的網(wǎng)絡(luò)教學(xué)，幫助學(xué)生加深對(duì)課堂教學(xué)內(nèi)容的理解，擴(kuò)展相關(guān)知識(shí)，提高學(xué)習(xí)興趣和主動(dòng)性。有利于素質(zhì)教育和創(chuàng)新能力的培養(yǎng)，在實(shí)際教學(xué)應(yīng)用中顯著提高了教學(xué)質(zhì)量和教學(xué)效率。

5 課程的實(shí)驗(yàn)設(shè)計(jì)

“紙上得來(lái)終覺(jué)淺，絕知此事要躬行”。“數(shù)據(jù)結(jié)構(gòu)與算法”課程是一門理論和實(shí)際緊密結(jié)合的課程，上機(jī)實(shí)習(xí)題的設(shè)計(jì)、實(shí)習(xí)訓(xùn)練的數(shù)量和質(zhì)量都非常重要。通過(guò)適當(dāng)?shù)膶?shí)習(xí)訓(xùn)練，可以使學(xué)生深刻理解和掌握課程知識(shí)體系中的理論和抽象概念，以及各類設(shè)計(jì)實(shí)現(xiàn)方法，提高在復(fù)雜軟件系統(tǒng)中的實(shí)踐能力。

除教師指定的實(shí)習(xí)題目外，我們鼓勵(lì)優(yōu)秀學(xué)生和本科生科研基金項(xiàng)目學(xué)生自己組隊(duì)選題。以合作學(xué)習(xí)的“文獻(xiàn)調(diào)研—開(kāi)題—項(xiàng)目分析—項(xiàng)目設(shè)計(jì)—成果匯報(bào)—總結(jié)評(píng)價(jià)”模式為主線，以學(xué)生自主探究和開(kāi)發(fā)活動(dòng)為主體，以教師點(diǎn)撥為主導(dǎo)，以培養(yǎng)學(xué)生學(xué)習(xí)的興趣和能力為中心。強(qiáng)化創(chuàng)新意識(shí)和創(chuàng)新能力，相應(yīng)地提高理論聯(lián)系實(shí)際能力、實(shí)踐動(dòng)手能力和科研能力，也能提高學(xué)生的學(xué)習(xí)和研究積極性，優(yōu)化實(shí)踐教學(xué)的效果。

在實(shí)習(xí)課上，同學(xué)們得以實(shí)現(xiàn)理論課上的很多算法，在助教的組織下交流各種不同類型的解題方案，并且進(jìn)行深入的數(shù)據(jù)結(jié)構(gòu)和算法時(shí)間、空間效率討論，達(dá)到理論與實(shí)踐水平共同提高的目的。

(1) 實(shí)習(xí)設(shè)計(jì)思想

著眼于數(shù)據(jù)結(jié)構(gòu)原理和應(yīng)用的結(jié)合點(diǎn)，引導(dǎo)學(xué)生應(yīng)用書本知識(shí)解決實(shí)際問(wèn)題，提高學(xué)生的實(shí)際動(dòng)手能力和團(tuán)隊(duì)合作能力。通過(guò)動(dòng)手實(shí)驗(yàn)，使得課程涉及的數(shù)據(jù)結(jié)構(gòu)理論、存儲(chǔ)技術(shù)、算法技術(shù)“活”起來(lái)，起到深化理解和靈活掌握教學(xué)內(nèi)容的目的。

課程的實(shí)踐訓(xùn)練體系融合了經(jīng)典的理論教學(xué)內(nèi)容與學(xué)科的前沿新技術(shù)和發(fā)展方向，是課程的重要特色。采用ACM/ICPC程序競(jìng)賽題庫(kù)POJ系統(tǒng)進(jìn)行經(jīng)典算法和驗(yàn)證型、小規(guī)模設(shè)計(jì)型實(shí)習(xí)訓(xùn)練，涵蓋圖搜索、枚舉、貪心、遞歸分治、動(dòng)態(tài)規(guī)劃等經(jīng)典算法練習(xí)。從企業(yè)合作項(xiàng)目和學(xué)科前沿研究中提煉大規(guī)模的設(shè)計(jì)和綜合型實(shí)習(xí)題，例如“搜索引擎”、“XML數(shù)據(jù)管理”等，滿足線性表、字符串、二叉樹(shù)/樹(shù)、圖、排序、索引、檢索等數(shù)據(jù)結(jié)構(gòu)綜合訓(xùn)練需求，同時(shí)也豐富了ACM/ICPC程序競(jìng)賽題庫(kù)。作業(yè)題和實(shí)習(xí)題融合當(dāng)前最新理論和技術(shù)，非常有前瞻性，學(xué)生受到創(chuàng)新思維能力和工程能力的訓(xùn)練，使學(xué)生在實(shí)驗(yàn)過(guò)程中進(jìn)一步掌握典型數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及算法的程序?qū)崿F(xiàn)，并訓(xùn)練學(xué)生分析問(wèn)題的能力和編程解決問(wèn)題的能力，培養(yǎng)軟件工程規(guī)范和團(tuán)隊(duì)合作精神。

(2) 實(shí)習(xí)訓(xùn)練目標(biāo)

配合“數(shù)據(jù)結(jié)構(gòu)與算法”進(jìn)行問(wèn)題求解能力訓(xùn)練，注重實(shí)踐能力和工程能力的培養(yǎng)，使學(xué)生遵從軟件開(kāi)發(fā)的規(guī)范性。以項(xiàng)目驅(qū)動(dòng)，從軟件工程的角度對(duì)學(xué)生系統(tǒng)地進(jìn)行需求分析、數(shù)學(xué)建模、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)、程序?qū)崿F(xiàn)測(cè)試調(diào)試、文檔編寫訓(xùn)練。不僅要求進(jìn)行簡(jiǎn)單的實(shí)現(xiàn)，更要求進(jìn)行工程實(shí)現(xiàn)的設(shè)計(jì)。學(xué)生不僅能完成自己承擔(dān)的開(kāi)發(fā)任務(wù)，還能從系統(tǒng)級(jí)認(rèn)識(shí)整個(gè)項(xiàng)目，積累重大項(xiàng)目的組合、合作協(xié)調(diào)經(jīng)驗(yàn)，培養(yǎng)項(xiàng)目組織和管理能力，能夠創(chuàng)造性地解決工程中遇到的問(wèn)題。

通過(guò)典型案例教學(xué)，引導(dǎo)學(xué)生深入思考，激發(fā)創(chuàng)新思想火花，充分調(diào)動(dòng)學(xué)生學(xué)習(xí)的主動(dòng)性，實(shí)現(xiàn)教與學(xué)的互動(dòng)。學(xué)生從案例中進(jìn)行研究型學(xué)習(xí)，并在學(xué)習(xí)過(guò)程中主動(dòng)運(yùn)用所學(xué)知識(shí)來(lái)分析問(wèn)題、解決問(wèn)題，根據(jù)問(wèn)題的需求來(lái)主動(dòng)獲取新知識(shí)，從而強(qiáng)化創(chuàng)新意識(shí)和創(chuàng)新能力，相應(yīng)地提高理論聯(lián)系實(shí)際能力、實(shí)踐動(dòng)手能力和科研能力。

(3) 實(shí)習(xí)訓(xùn)練過(guò)程

本教學(xué)小組的教員結(jié)合自己的科研背景，在本課程體系的框架下，針對(duì)不同層次、不同需求的學(xué)生進(jìn)行有針對(duì)性的案例教學(xué)，并從企業(yè)合作和科研項(xiàng)目中提煉工業(yè)級(jí)的綜合實(shí)習(xí)訓(xùn)練題目。

注重培養(yǎng)學(xué)生自主學(xué)習(xí)能力和創(chuàng)新意識(shí)，提供開(kāi)放的學(xué)習(xí)環(huán)境，實(shí)施啟發(fā)式教學(xué)，擴(kuò)展學(xué)生知識(shí)體系。設(shè)計(jì)啟發(fā)式教學(xué)案例、課下思考題、課堂討論題，引導(dǎo)學(xué)生靈活應(yīng)用基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型、存儲(chǔ)方法、經(jīng)典算法設(shè)計(jì)新型數(shù)據(jù)結(jié)構(gòu)來(lái)解決問(wèn)題，鼓勵(lì)優(yōu)化方案的提出、分析和驗(yàn)證。

鼓勵(lì)優(yōu)秀學(xué)生和本科生科研基金項(xiàng)目學(xué)生自己組隊(duì)、選題代替期末的綜合合作實(shí)習(xí)。學(xué)生自己設(shè)計(jì)過(guò)音樂(lè)搜索引擎、基于后綴樹(shù)的網(wǎng)頁(yè)聚類、網(wǎng)頁(yè)商品實(shí)體抽取器、Web用戶意見(jiàn)情感分析等很多富有創(chuàng)意的綜合題。以合作學(xué)習(xí)的“文獻(xiàn)調(diào)研—開(kāi)題—項(xiàng)目分析—項(xiàng)目設(shè)計(jì)—成果匯報(bào)—總結(jié)評(píng)價(jià)”模式為主線，以學(xué)生自主探究和開(kāi)發(fā)活動(dòng)為主體，以教師點(diǎn)撥為主導(dǎo)，以培養(yǎng)學(xué)生的學(xué)習(xí)興趣和能力為中心，來(lái)優(yōu)化實(shí)踐教學(xué)的效果。

在這種創(chuàng)新科學(xué)素養(yǎng)培養(yǎng)中，引導(dǎo)學(xué)生閱讀文獻(xiàn)、選擇課題進(jìn)行研究型學(xué)習(xí)，并在研究性學(xué)習(xí)過(guò)程中主動(dòng)運(yùn)用所學(xué)知識(shí)來(lái)分析問(wèn)題、解決問(wèn)題，根據(jù)問(wèn)題的需求來(lái)主動(dòng)獲取新知識(shí)。從而強(qiáng)化創(chuàng)新意識(shí)和創(chuàng)新能力，相應(yīng)地提高理論聯(lián)系實(shí)際能力、實(shí)踐動(dòng)手能力和科研能力，也提高了學(xué)生的學(xué)習(xí)和研究積極性。

(4) 實(shí)習(xí)訓(xùn)練效果

經(jīng)過(guò)多年的建設(shè)，形成了精巧而具前瞻性的實(shí)習(xí)題庫(kù)。

北大99級(jí)本科生，現(xiàn)就讀于UIUC的梅俏竹博士在推薦信中寫道：“記得當(dāng)年數(shù)據(jù)結(jié)構(gòu)的大實(shí)習(xí)作業(yè)是設(shè)計(jì)并實(shí)現(xiàn)一個(gè)簡(jiǎn)單的搜索引擎。而當(dāng)時(shí)只不過(guò)是2000年，現(xiàn)在搜索引擎的巨頭Google遠(yuǎn)未上市，百度則剛剛成立，微軟和雅虎甚至還沒(méi)開(kāi)始研發(fā)自己的搜索引擎。北大的本科生課程實(shí)習(xí)就能有這樣的前瞻性的問(wèn)題絕對(duì)是值得稱道的。”“歸結(jié)起來(lái)，大家都認(rèn)為張銘老師的‘?dāng)?shù)據(jù)結(jié)構(gòu)與算法課程’內(nèi)容細(xì)致實(shí)用，講授深入淺出，課程實(shí)習(xí)精巧而具前瞻性，對(duì)培養(yǎng)學(xué)生分析和解決問(wèn)題，創(chuàng)造性思考，和團(tuán)隊(duì)合作的能力都有很好的作用。”

課程的實(shí)習(xí)訓(xùn)練為學(xué)生學(xué)習(xí)后續(xù)課程，將來(lái)進(jìn)行科學(xué)研究、工作創(chuàng)業(yè)等，打下了厚實(shí)的基礎(chǔ)。實(shí)習(xí)課程受到學(xué)生尤其是畢業(yè)生的廣泛好評(píng)。

6 課程考核

(1)“數(shù)據(jù)結(jié)構(gòu)與算法”課程的考核

主要包括如下幾個(gè)部分：

1) 平時(shí)(書面作業(yè)、課堂測(cè)試)，占學(xué)期總成績(jī)的20%

2) 上機(jī)實(shí)習(xí)(+實(shí)習(xí)報(bào)告)，占學(xué)期總成績(jī)的15%

3) 期中考試，占學(xué)期總成績(jī)的20%

4) 期末考試，占學(xué)期總成績(jī)的40%

5) 考勤和態(tài)度，占學(xué)期總成績(jī)的5%

期中期末采用閉卷考試，共占60%。習(xí)題作業(yè)和上機(jī)，考察動(dòng)手解決實(shí)際問(wèn)題的實(shí)踐能力，占35%。另外，對(duì)課程的參與度、學(xué)習(xí)態(tài)度、對(duì)他人的幫助等過(guò)程性評(píng)價(jià)也作為考核的內(nèi)容。

(2)“數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)”課程的考核

主要包括如下幾個(gè)部分：

1) 平時(shí)(考勤+開(kāi)卷隨堂測(cè)試+課堂表現(xiàn))，占學(xué)期總成績(jī)的15%

2) ACM/ICPC作業(yè)(北京大學(xué)POJ結(jié)果+源程序+實(shí)習(xí)報(bào)告)20%

3) 綜合上機(jī)題(源程序＋實(shí)習(xí)報(bào)告)40%

4) 期末考試，占學(xué)期總成績(jī)的20%

5) 考勤和態(tài)度，占學(xué)期總成績(jī)的5%

注重綜合能力的考評(píng)，平時(shí)表現(xiàn)突出、上機(jī)能力較強(qiáng)的可以得到獎(jiǎng)勵(lì)加分。平時(shí)作業(yè)、上機(jī)實(shí)習(xí)題、考試嚴(yán)禁抄襲，平時(shí)作業(yè)要附加“誠(chéng)實(shí)代碼”，考試要在“誠(chéng)實(shí)考試宣言”之后簽名。對(duì)平時(shí)作業(yè)作弊抄襲者提出警告并得負(fù)分(相當(dāng)于在總期評(píng)成績(jī)中給予懲罰)，嚴(yán)重者期評(píng)成績(jī)記0分，并上報(bào)學(xué)校教務(wù)處處理。

7 結(jié)束語(yǔ)

北京大學(xué)信息學(xué)院“數(shù)據(jù)結(jié)構(gòu)與算法”課程以ACM/IEEE CC2005和教育部CCC2006教學(xué)規(guī)范為指導(dǎo)，從問(wèn)題求解著手，貫穿數(shù)據(jù)結(jié)構(gòu)理論、抽象和設(shè)計(jì)的三個(gè)形態(tài)，課程組教師編寫了先進(jìn)的“十五”、“十一五”國(guó)家級(jí)系列規(guī)劃教材。

課程具有幾個(gè)比較明顯的特點(diǎn)：http://www.jpk.pku. edu.cn/pkujpk/course/sjjg/網(wǎng)絡(luò)教學(xué)資源極為豐富，有全程錄像、豐富的教學(xué)課件；http://www.jpk.pku.edu.cn/pkujpk/ course/sjjg/frame/index.html教學(xué)平臺(tái)相當(dāng)完善，細(xì)化到知識(shí)點(diǎn)的課程導(dǎo)航；實(shí)踐平臺(tái)十分先進(jìn)，采用ACM/ICPC (ACM程序競(jìng)賽)在線提交評(píng)測(cè)系統(tǒng)http://acm.pku.edu.cn/ JudgeOnline(POJ)，該系統(tǒng)由北京大學(xué)李文新教授主持開(kāi)發(fā)，有2200多道覆蓋各知識(shí)領(lǐng)域的在線評(píng)測(cè)經(jīng)典算法實(shí)習(xí)題，本課程還采用該系統(tǒng)進(jìn)行算法能力測(cè)試。本課程還設(shè)計(jì)了數(shù)十道數(shù)據(jù)結(jié)構(gòu)綜合大項(xiàng)目實(shí)習(xí)題。

強(qiáng)化課程的實(shí)踐環(huán)節(jié)，以學(xué)生為本、分層設(shè)計(jì)的培養(yǎng)方案，讓每個(gè)學(xué)生得到最大的收獲。課程組得到了學(xué)院教學(xué)督導(dǎo)組的高度評(píng)價(jià)，得到同事們的認(rèn)可，受到北大學(xué)生的廣泛好評(píng)。國(guó)內(nèi)有南開(kāi)大學(xué)、蘭州大學(xué)等30多所名校采用本課程組的教材，課程網(wǎng)站、課程視頻等網(wǎng)絡(luò)教學(xué)資源被很多高校和IT網(wǎng)站鏈接。

在校內(nèi)，北京大學(xué)校長(zhǎng)助理、副教務(wù)長(zhǎng)李曉明教授認(rèn)為“張銘所主持的數(shù)據(jù)結(jié)構(gòu)與算法和相應(yīng)的實(shí)習(xí)課是北大信息學(xué)院學(xué)生公認(rèn)的精品課程”。

在國(guó)內(nèi)，教育部計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)教學(xué)指導(dǎo)分委員會(huì)委員，2006年國(guó)家精品課程“數(shù)據(jù)結(jié)構(gòu)與算法”主持人廖明宏教授認(rèn)為“北京大學(xué)信息科學(xué)技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程在國(guó)內(nèi)同類課程中處于領(lǐng)先地位”。

值得一提的是，北京大學(xué)信息科學(xué)技術(shù)學(xué)院“數(shù)據(jù)結(jié)構(gòu)與算法”課程得到了許多來(lái)自世界著名大學(xué)的認(rèn)可和高度贊賞：ACM Fellow(院士)、美國(guó)卡內(nèi)基·梅隆(CMU)大學(xué)張暉教授認(rèn)為“課程建設(shè)得非常完善而先進(jìn)。毫不遜色于美國(guó)的CMU、Berkeley等一流大學(xué)的相應(yīng)課程，甚至在深度、廣度上擴(kuò)展得更多。”斯坦福大學(xué)計(jì)算機(jī)系博士生徐穎表示：“我自豪地發(fā)現(xiàn)，北大的本科教育，特別是張老師的數(shù)據(jù)與算法結(jié)構(gòu)課，完全可以媲美美國(guó)最好的計(jì)算機(jī)系的相應(yīng)課程?！?/p>

在長(zhǎng)期教學(xué)實(shí)踐過(guò)程中，北京大學(xué)信息科學(xué)技術(shù)學(xué)院“數(shù)據(jù)結(jié)構(gòu)與算法”課程在國(guó)內(nèi)外都獲得了廣泛好評(píng)，2008年被評(píng)選為“北京市精品課程”。

課程建設(shè)小組成員將再接再厲，多與國(guó)內(nèi)外同行交流，更多地與IT企業(yè)界合作，保持課程理論和技術(shù)的先進(jìn)性，進(jìn)一步擴(kuò)大課程的影響力和受益面。

參考文獻(xiàn)

[1] 教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)．高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)發(fā)展戰(zhàn)略研究報(bào)告暨專業(yè)規(guī)范(試行)[M]. 北京：高等教育出版社，2006.

[2] CC2005. The Overview Report of Computing Curricula 2005[EB/OL].

[3] http://www.computer.org/portal/cms_docs_ieeecs/ieeecs/education/cc2001/CC2005-March06Final.pdf

[4] 蔣宗禮．“編譯原理”教學(xué)設(shè)計(jì)[J]．計(jì)算機(jī)教育，2008，(3).

[5] 張銘，王騰蛟，趙海燕．?dāng)?shù)據(jù)結(jié)構(gòu)與算法[M]．北京：高等教育出版社，2008.——普通高等教育“十一五”國(guó)家級(jí)規(guī)劃教材。