算法與數(shù)據(jù)結(jié)構(gòu)

前言

《算法與數(shù)據(jù)結(jié)構(gòu)——C語言描述》（高等教育出版社，2002）是著者在二十多年從事“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)實踐和教材建設(shè)的基礎(chǔ)上，為北京大學(xué)理科院系開設(shè)的同名主干基礎(chǔ)課而編寫的一本通用教材，在校內(nèi)外廣泛使用并受到讀者的好評。該書于2004年獲得“北京市高等教育精品教材獎”。為了精益求精，經(jīng)過著者認(rèn)真修訂，2006年出版了第2版，2007年該書又榮獲教育部頒發(fā)的“普通高等教育精品教材獎”。數(shù)據(jù)結(jié)構(gòu)與算法在計算機(jī)專業(yè)教育中的核心地位與重要作用是公認(rèn)的，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的困難也是廣大師生所共知的。多年來，許多老師和同學(xué)都曾向著者反映：十分需要數(shù)據(jù)結(jié)構(gòu)與算法的教學(xué)指導(dǎo)、實習(xí)指導(dǎo)、學(xué)習(xí)輔導(dǎo)和習(xí)題解答之類的書。本書是原書著者應(yīng)廣大讀者需要編寫的與該書配套的一本教學(xué)參考書。根據(jù)著者多年的教學(xué)經(jīng)驗，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的難點(diǎn)在于解題。學(xué)生在解題中經(jīng)常出現(xiàn)的錯誤，通常也是教材中沒有重點(diǎn)解釋的問題。提高學(xué)生的知識水平光靠聽課和看書是不夠的，在學(xué)生解題的過程中，可能會發(fā)現(xiàn)許多教學(xué)中忽視的問題。如果挑選一批對于理解數(shù)據(jù)結(jié)構(gòu)的概念和思想有益的題目讓學(xué)生練習(xí)，可以有助于學(xué)生學(xué)得更活、理解得更深；在習(xí)題解答中標(biāo)明學(xué)生經(jīng)常出現(xiàn)的錯誤，并且適當(dāng)加以解釋，供學(xué)生在自己獨(dú)立思考后參考，更能達(dá)到事半功倍的效果。算法是人類智慧的結(jié)晶。在數(shù)據(jù)結(jié)構(gòu)的習(xí)題中，最難的無疑是算法題。算法題的答案不是唯一的，所以無法給出一個標(biāo)準(zhǔn)答案。編寫習(xí)題解答的重點(diǎn)和難點(diǎn)是算法。設(shè)計算法的關(guān)鍵在于設(shè)計的思路，不同的思路產(chǎn)生出不同的算法。面對一個算法題，學(xué)生最需要的是如何開始分析這個問題和逐步解決這個問題。所以對于每道復(fù)雜的算法題，不應(yīng)該僅僅給出一個程序，而需要首先給出問題的分析、算法的思路，再給出程序和算法分析。對存在多個解法的題目，在給出一個算法的同時，還可以指出各種解法的缺點(diǎn)和改進(jìn)之處。這樣，學(xué)生可以從中體會到算法的真諦，從而真正有利于提高學(xué)生的算法設(shè)計與分析能力。應(yīng)用數(shù)據(jù)結(jié)構(gòu)與算法的知識解決實際問題，并上機(jī)實現(xiàn)，是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的過程中不可缺少的環(huán)節(jié)。為了使上機(jī)實習(xí)取得事半功倍的效果，老師不但要選擇適當(dāng)?shù)膯栴}，提出實習(xí)的具體要求和規(guī)定上機(jī)報告的內(nèi)容和形式；同時更需要給學(xué)生以具體幫助。實習(xí)題與算法題有類似之處，但通常更加復(fù)雜。我們搜集了常見教材上的各種應(yīng)用問題，并給出求解的樣例，其目的就是有助于組織好這一教學(xué)環(huán)節(jié)。

內(nèi)容概要

按照教育部計算機(jī)專業(yè)本科《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱和新頒布的計算機(jī)專業(yè)碩士研究生入學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》考試大綱的要求，本書精心挑選了覆蓋大綱全部要求的500多道習(xí)題，并且提供了所有題目的參考答案。    為了便于閱讀，在每章的開頭概述了本章的主要內(nèi)容，指出了本章的學(xué)習(xí)的重點(diǎn)和難點(diǎn)；為了便于理解，對于較難的算法題和上機(jī)題，書中給出了比較詳細(xì)的分析；對于不同教材可能對答案造成的差異還給出了適當(dāng)?shù)恼f明；對于學(xué)生易犯的錯誤和題目的難易度、重要性等書中均明確給出提示。本書集多功能于一身，具有突出的系統(tǒng)性、完整性和針對性。    本書作者具有近30年從事數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的經(jīng)驗，編寫了多本不同對象和不同語言描述的數(shù)據(jù)結(jié)構(gòu)教材。本書的目的是為各類學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的讀者，特別是希望考研的學(xué)生編寫的一本通用教學(xué)參考書。全書采用作者最新出版的《算法與數(shù)據(jù)結(jié)構(gòu)-c語言描述（第2版）》統(tǒng)一的框架和同樣的語言表示，也包含了該書中全部習(xí)題的答案。該書在2007年榮獲教育部頒發(fā)的“十一五”國家級規(guī)劃教材“普通高等教育精品教材”獎。

書籍目錄

第1章  緒論  1.1 主要內(nèi)容與方法    1.1.1 從問題到程序    1.1.2 抽象數(shù)據(jù)類型    1.1.3 數(shù)據(jù)結(jié)構(gòu)    1.1.4 算法  1.2 簡單題  1.3 問答題  1.4 算法分析題  1.5  應(yīng)用與上機(jī)題第2章  線性表  2.1 主要內(nèi)容與方法    2.1.1 基本概念與抽象數(shù)據(jù)類型    2.1.2 順序表示    2.1.3 鏈接表示    2.1.4 矩陣與廣義表  2.2 簡單題  2.3 問答題    2.4 算法題  2.5 應(yīng)用與上機(jī)題第3章  字符串  3.1 主要內(nèi)容與方法    3.1.1 字符串及其抽象數(shù)據(jù)類型    3.1.2 字符串的表示    3.1.3 模式匹配  3.2 簡單題  3.3 問答題  3.4 算法題  3.5 應(yīng)用與上機(jī)題第4章棧與隊列  4.1 主要內(nèi)容與方法    4.1.1 棧及其抽象數(shù)據(jù)類型    4.1.2 棧的實現(xiàn)    4.1.3 棧與遞歸    4.1.4 隊列及其抽象數(shù)據(jù)類型    4.1.5 隊列的實現(xiàn)  4.2 簡單題  4.3 問答題  4.4 算法題  4.5 應(yīng)用與上機(jī)題第5章  二叉樹、樹與樹林  5.1  主要內(nèi)容與方法    5.1.1 二叉樹及其抽象數(shù)據(jù)類型    5.1.2 二叉樹的周游    5.1.3 二叉樹的實現(xiàn)    5.1.4 二叉樹的應(yīng)用    5.1.5 樹與樹林  5.2 簡單題    5.2.1 是非題    5.2.2 選擇題    5.2.3 填空題  5.3 問答題    5.3.1 基本概念    5.3.2 周游    5.3.3 存儲表示    5.3.4 轉(zhuǎn)換    5.3.5 堆與優(yōu)先隊列    5.3.6 哈夫曼樹    5.3.7 表達(dá)式樹  5.4 算法題  5.5 應(yīng)用與上機(jī)題第6章  集合與字典  6.1 主要內(nèi)容與方法    6.1.1 集合及其抽象數(shù)據(jù)類型    6.1.2 集合的買現(xiàn)    6.1.3 字典及其抽象數(shù)據(jù)類型    6.1.4 字典的順序表示    6.1.5 字典的散列表示  6.2 簡單題  6.3 問答題  6.4 算法題  6.5 應(yīng)用與上機(jī)題第7章  高級字典結(jié)構(gòu)  7.1 主要內(nèi)容與方法    7.1.1 字典與索引    7.1.2 字符樹    7.1.3 二叉排序樹    7.1.4 最佳二叉排序樹    7.1.5 平衡二叉排序樹    7.1.6 索引文件  7.2 簡單題  7.3 問答題    7.3.1 二叉排序樹    7.3.2 最佳二叉排序樹    7.3.3 平衡二叉排序樹    7.3.4 索引文件  7.4 算法題  7.5 應(yīng)用與上機(jī)題第8章  排序  8.1 主要內(nèi)容與方法  8.2 簡單題  8.3 問答題  8.4 算法題  8.5 應(yīng)用與上機(jī)題第9章  圖  9.1 主要內(nèi)容與方法    9.1.1 基本概念及其抽象數(shù)據(jù)類型    9.1.2 圖的周游    9.1.3 存儲表示    9.1.4 最小生成樹    9.1.5 最短路徑    9.1.6 拓?fù)渑判蚺c關(guān)鍵路徑  9.2 簡單題  9.3 問答是亟    9.3.1 基本概念    9.3.2 存儲表示    9.3.3 周游與生成樹    9.3.4 最小生成樹    9.3.5 最短路徑    9.3.6 拓?fù)渑判蚺c關(guān)鍵路徑  9.4 算法題  9.5 應(yīng)用與上機(jī)題第10章  算法分析與設(shè)計  10.1 主要內(nèi)容與方法    10.1.1 算法分析技術(shù)    10.1.2 算法設(shè)計技術(shù)  10.2 簡單題  10.3 算法分析題  10.4 算法設(shè)計題  10.5 應(yīng)用與上機(jī)題參考文獻(xiàn)

章節(jié)摘錄

插圖：11.什么是存儲密度？【答】存儲數(shù)據(jù)結(jié)構(gòu)時，實際數(shù)據(jù)所占的空間與結(jié)構(gòu)所占總空間之比叫做存儲密度。12.解釋下列與文件相關(guān)的概念。（1）文件（2）記錄（3）關(guān)鍵碼（4）頁塊【答】文件是一種線性結(jié)構(gòu)，它一般放在外存儲器（簡稱外存）上，由許多記錄組成。記錄是數(shù)據(jù)項的集合，是文件中可以存取的邏輯單位。能夠唯一地標(biāo)識記錄的一個（或一組）字段叫做關(guān)鍵碼。一個頁塊（簡稱塊）是磁帶或磁盤上的一條物理記錄，通常可以存放多條邏輯記錄。內(nèi)存中設(shè)置的緩沖區(qū)應(yīng)該是頁塊大小的倍數(shù)。每次訪問外存儲器，就是把一個頁塊讀入緩沖區(qū)或者把部分緩沖區(qū)內(nèi)容寫到一個頁塊。分頁塊存儲的方法是一種有利于減少訪問外存儲器的次數(shù)而又便于管理的方法。13.什么是順序文件？它有什么特點(diǎn)？【答】如果文件記錄的邏輯次序是按關(guān)鍵碼遞增（或遞減）次序定義的，并且在外存儲器上是按同樣的次序排列的，則這種文件叫做順序文件。由于順序文件中記錄的物理次序與邏輯次序是一致的，所以適宜順序存取（即存取一條記錄之后，接著將存取其后繼記錄）和成批處理。川頁序文件特別適用于磁帶存儲器，也適用于磁盤存儲器。順序文件的隨機(jī)存?。窗措S機(jī)給出的關(guān)鍵碼存取一條記錄）效率很低。14.什么是索引（順序）文件？它有什么特點(diǎn)？【答】索引表是由索引組成的表，每個索引項是一條記錄的關(guān)鍵碼和指向該記錄的指針組成的二元組。如果文件中每條記錄對應(yīng)一個索引項，則將這樣的索引稱為密集索引；如果不是每條記錄都對應(yīng)一個索引項，例如，讓文件中每個頁塊對應(yīng)一個索引項，則這樣的索引稱為稀疏索引。

編輯推薦

《算法與數(shù)據(jù)結(jié)構(gòu):學(xué)習(xí)指導(dǎo)與習(xí)題解析(第2版)》：普通高等教育“十一五”國家級規(guī)劃教材配套參考書

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    算法與數(shù)據(jù)結(jié)構(gòu) PDF格式下載

---