《數(shù)據(jù)結(jié)構(gòu)》教學(xué)日歷

教學(xué)日歷章周次課程內(nèi)容公告綜合作業(yè)思考第一章第一周數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念算法的概念、描述方法以及評(píng)價(jià)標(biāo)準(zhǔn)本周學(xué)習(xí)第一章緒論，請(qǐng)同學(xué)們做好預(yù)習(xí)。預(yù)習(xí)中可思考如下問題：1．你對(duì)數(shù)據(jù)結(jié)構(gòu)的概念是如何理解？2．算法分析的目的是什么？1．物流活動(dòng)中貨車的抽象數(shù)據(jù)類型表示與實(shí)現(xiàn)。1．你對(duì)數(shù)據(jù)結(jié)構(gòu)的概念是如何理解？2．?dāng)?shù)據(jù)邏輯結(jié)構(gòu)包括哪些類型？3．為什么采用抽象數(shù)據(jù)類型描述數(shù)據(jù)結(jié)構(gòu)？4．算法分析的目的是什么？第二章第二周線性表的類型定義線性表的順序表示和實(shí)現(xiàn)本周學(xué)習(xí)內(nèi)容：線性表（類型定義，順序表示和實(shí)現(xiàn)），請(qǐng)同學(xué)們做好預(yù)習(xí)。預(yù)習(xí)時(shí)可思考如下問題：1．線性結(jié)構(gòu)與非線性結(jié)構(gòu)的根本區(qū)別是什么？2．線性表有哪兩種存儲(chǔ)結(jié)構(gòu)，各有哪些優(yōu)缺點(diǎn)？3．在單鏈表中設(shè)置頭結(jié)點(diǎn)有何作用？1．線性結(jié)構(gòu)與非線性結(jié)構(gòu)的根本區(qū)別是什么？1．線性結(jié)構(gòu)與非線性結(jié)構(gòu)的根本區(qū)別是什么？2．線性表有哪兩種存儲(chǔ)結(jié)構(gòu)，各有哪些優(yōu)缺點(diǎn)？3．在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問任一結(jié)點(diǎn)？4．當(dāng)對(duì)一個(gè)線性表經(jīng)常進(jìn)行的是存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用何種存儲(chǔ)結(jié)構(gòu)為宜？當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則應(yīng)采用存儲(chǔ)結(jié)構(gòu)為宜？5．在單鏈表中設(shè)置頭結(jié)點(diǎn)有何作用？第三周線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)本周學(xué)習(xí)內(nèi)容：線性表（鏈?zhǔn)奖硎竞蛯?shí)現(xiàn))，請(qǐng)同學(xué)們做好預(yù)習(xí)。預(yù)習(xí)時(shí)可思考如下問題：1．在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問任一結(jié)點(diǎn)？2．當(dāng)對(duì)一個(gè)線性表經(jīng)常進(jìn)行的是存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用何種存儲(chǔ)結(jié)構(gòu)為宜？當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則應(yīng)采用存儲(chǔ)結(jié)構(gòu)為宜？第四周線性表的其他鏈?zhǔn)奖硎揪€性表的應(yīng)用舉例本周學(xué)習(xí)內(nèi)容：線性表（其他鏈?zhǔn)奖硎炯皯?yīng)用舉例），請(qǐng)同學(xué)們做好預(yù)習(xí)。第三章第五周棧的概念、存儲(chǔ)結(jié)構(gòu)及其基本操作隊(duì)列的概念、存儲(chǔ)結(jié)構(gòu)及其基本操作棧與隊(duì)列的應(yīng)用舉例本周學(xué)習(xí)內(nèi)容：棧和隊(duì)列（鏈隊(duì)列、循環(huán)隊(duì)列、應(yīng)用舉例）。請(qǐng)同學(xué)們提前預(yù)習(xí)，并思考如下問題：1．隊(duì)列是具有什么特性的線性表？2．分析棧與遞歸的關(guān)系。1．利用兩個(gè)棧模擬一個(gè)隊(duì)列的入隊(duì)、出隊(duì)、判斷隊(duì)空等運(yùn)算。1．棧是具有什么特性的線性表？2．隊(duì)列是具有什么特性的線性表？3．分析棧與遞歸的關(guān)系。4．為什么要循環(huán)隊(duì)列？在循環(huán)隊(duì)列中隊(duì)列空、滿的評(píng)定標(biāo)準(zhǔn)是什么？第四章第六周樹二叉樹本周學(xué)習(xí)內(nèi)容：樹和二叉樹（樹的定義和基本術(shù)語，二叉樹，遍歷二叉樹和線索二叉樹）。同學(xué)們預(yù)習(xí)時(shí)可參考如下問題：1．樹型結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)2．樹和二叉樹的主要差別表現(xiàn)在哪些方面？3．二叉樹具有那些重要特性？1．有一份電文中共使用5個(gè)字符：a、b、c、d、e，它們的出現(xiàn)頻率依次為4、7、5、2、9，試畫出對(duì)應(yīng)的赫夫曼樹（請(qǐng)按左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造），并求出每個(gè)字符的赫夫曼編碼。1．樹型結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)2．樹和二叉樹的主要差別表現(xiàn)在哪些方面？3．二叉樹具有那些重要特性？4．二叉樹有哪些遍歷策略？如何利用算法實(shí)現(xiàn)？5．已知某二叉樹的后序遍歷序列和中序遍歷序列，如何求解出其前序遍歷序列。6．已知一棵二叉樹的中序序列為cbedahgijf，后序序列為cedbhjigfa，畫出該二叉樹的先序線索二叉樹。第七周線索二叉樹本周學(xué)習(xí)內(nèi)容：樹和二叉樹（遍歷二叉樹和線索二叉樹，樹和森林）。同學(xué)們預(yù)習(xí)時(shí)可參考如下問題：1．二叉樹有哪些遍歷策略？如何利用算法實(shí)現(xiàn)？2．已知某二叉樹的后序遍歷序列和中序遍歷序列，如何求解出其前序遍歷序列。第八周樹和森林赫夫曼樹及其應(yīng)用本周學(xué)習(xí)內(nèi)容：樹和二叉樹（赫夫曼樹及其應(yīng)用）。請(qǐng)同學(xué)們提前預(yù)習(xí)。第五章第九周圖的數(shù)學(xué)結(jié)構(gòu)圖的計(jì)算機(jī)表示本周學(xué)習(xí)內(nèi)容：圖（圖的定義和術(shù)語，圖的存儲(chǔ)結(jié)構(gòu)）。請(qǐng)同學(xué)們提前預(yù)習(xí)，并思考如下問題：1．圖是一種相對(duì)于線性表、樹更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其復(fù)雜性體現(xiàn)在何處？2．在解決圖的具體應(yīng)用問題時(shí)，圖的存儲(chǔ)表示（鄰接矩陣、鄰接表）的選取標(biāo)準(zhǔn)是什么？1．編寫一個(gè)實(shí)現(xiàn)連通圖G的深度優(yōu)先搜索遍歷的非遞歸程序。1．圖是一種相對(duì)于線性表、樹更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其復(fù)雜性體現(xiàn)在何處？2．在解決圖的具體應(yīng)用問題時(shí)，圖的存儲(chǔ)表示（鄰接矩陣、鄰接表）的選取標(biāo)準(zhǔn)是什么？3．論述圖的深度優(yōu)先搜索遍歷的策略4．編寫一個(gè)實(shí)現(xiàn)連通圖G的深度優(yōu)先搜索遍歷的非遞歸程序。5．論述圖的廣度優(yōu)先搜索遍歷的策略6．論述Prim算法的基本思想。第十周圖的遍歷本周學(xué)習(xí)內(nèi)容：圖（圖的遍歷，最小生成樹）。同學(xué)們預(yù)習(xí)時(shí)可參考如下問題：1．論述圖的深度優(yōu)先搜索遍歷的策略。2．論述圖的廣度優(yōu)先搜索遍歷的策略。第十一周圖的應(yīng)用本周學(xué)習(xí)內(nèi)容：圖的應(yīng)用，請(qǐng)同學(xué)們做好預(yù)習(xí)。第六章第十二周基本概念靜態(tài)查找表本周學(xué)習(xí)內(nèi)容：查找（靜態(tài)查找表）。請(qǐng)同學(xué)們做好預(yù)習(xí)。1．假設(shè)有序表的長(zhǎng)度為20，分析斐波那契查找過程并以判定樹的形式表示整個(gè)查找過程。1．何謂查找表？針對(duì)具體應(yīng)用問題，查找表應(yīng)采用怎樣的存儲(chǔ)結(jié)構(gòu)？2．如何評(píng)價(jià)折半查找算法的性能？為什么折半查找只適用于有序表，且限于順序存儲(chǔ)結(jié)構(gòu)？3．二叉查找樹結(jié)構(gòu)是實(shí)現(xiàn)動(dòng)態(tài)查找的最佳選擇，為什么？4．為什么引入B-樹？第十三周二叉查找樹B-樹散列表查找本周學(xué)習(xí)內(nèi)容：查找（動(dòng)態(tài)查找表——二叉排序樹、B-樹）。同學(xué)們預(yù)習(xí)時(shí)可參考如下問題：1．二叉查找樹結(jié)構(gòu)是實(shí)現(xiàn)動(dòng)態(tài)查找的最佳選擇，為什么？2．為什么引入B-樹？第七章第十四周概述插入排序交換排序本周學(xué)習(xí)內(nèi)容：內(nèi)部排序（插入排序、交換排序）。請(qǐng)同學(xué)們認(rèn)真做好預(yù)習(xí)。1．采用單鏈表作存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)采用選擇排序方法進(jìn)行升序排序的算法。1．從時(shí)間復(fù)雜度的角度對(duì)排序方法進(jìn)行歸類。2．在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)有哪些？3．空間復(fù)雜度最佳的排序方法有哪些？4．從算法的簡(jiǎn)單性角度對(duì)排序方法進(jìn)行歸類第十五周選擇排序歸并排序各種內(nèi)部排序方法的比較討論外部排序本周學(xué)習(xí)內(nèi)容：內(nèi)部排序（歸并排序，外部排序簡(jiǎn)介）。同學(xué)們預(yù)習(xí)時(shí)可參考如下問題：1．從算法的簡(jiǎn)單性角度對(duì)排序方法進(jìn)行歸類。2．采用單鏈表作存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)采用選擇排序方法進(jìn)行升序排序的算。第八章第十六周文件概述順序文件直接文件索引文件索引順序文件倒排文件本周學(xué)習(xí)第八章文件。本章重點(diǎn)與難點(diǎn)為：1.重點(diǎn)為順序文件的操作和索引順序文件的結(jié)構(gòu)。2.難點(diǎn)是散列文件的設(shè)計(jì)模型——桶散列。請(qǐng)同學(xué)們認(rèn)真預(yù)習(xí)。1．圖書館的圖書流通