1、第一部分 復(fù)習(xí)提綱數(shù)據(jù)結(jié)構(gòu)與算法分析是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)統(tǒng)設(shè)的一門重要的必修專業(yè)基礎(chǔ)課，它主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)，還研究對(duì)數(shù)據(jù)進(jìn)行的插入、查找、刪除、排序、遍歷等基本運(yùn)算或操作以及這些運(yùn)算在各種存儲(chǔ)結(jié)構(gòu)上具體實(shí)現(xiàn)的算法。下面按照主教材中各章次序給出每章的具體復(fù)習(xí)要求，以便同學(xué)們更好地進(jìn)行復(fù)習(xí)。第1章 緒論內(nèi)容提要1、 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容2、 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型3、 算法的定義和5個(gè)特征。4、 算法設(shè)計(jì)要求5、 算法分析、時(shí)間復(fù)雜度和空間復(fù)雜度。知識(shí)點(diǎn)1、 數(shù)據(jù)的三個(gè)層次：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)2、 數(shù)據(jù)結(jié)構(gòu)的三要素：

2、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及在這種邏輯結(jié)構(gòu)上所定義的操作（運(yùn)算）。3、 抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。4、 時(shí)間復(fù)雜度，最好，最壞，平均時(shí)間復(fù)雜度。常用計(jì)算語(yǔ)句頻度來(lái)估算算法時(shí)間復(fù)雜度。有時(shí)候要求分析語(yǔ)句的執(zhí)行的次數(shù)，有時(shí)候要求給出語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)。5、 空間復(fù)雜度，算法工作所需輔助存儲(chǔ)空間。例如，在遞歸算法中所需的遞歸工作棧等。重點(diǎn)掌握的內(nèi)容：1. 數(shù)據(jù)結(jié)構(gòu)的二元組表示，對(duì)應(yīng)的圖形表示，序偶和邊之間的對(duì)應(yīng)關(guān)系。2. 集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)的特點(diǎn)。3. 抽象數(shù)據(jù)類型的定義和表示方法。4. 普通函數(shù)重載和操作符函數(shù)重載的含義，定義格式和調(diào)用格式。5. 函數(shù)定義中值參數(shù)和引用參數(shù)的說(shuō)

3、明格式及作用，函數(shù)被調(diào)用執(zhí)行時(shí)對(duì)傳送來(lái)的實(shí)際參數(shù)的影響。6. 算法的時(shí)間復(fù)雜度和空間復(fù)雜度的概念，計(jì)算方法，數(shù)量級(jí)表示。7. 一個(gè)簡(jiǎn)單算法的最好、最差和平均這三種情況的時(shí)間復(fù)雜度的計(jì)算。8. 數(shù)據(jù)結(jié)構(gòu)對(duì)算法的影響。對(duì)于本章的其余內(nèi)容均作一般掌握。第2章 線性表內(nèi)容提要1、 線性表是元素間約束力最強(qiáng)的一類數(shù)據(jù)結(jié)構(gòu)。非空線性表第一個(gè)元素?zé)o前驅(qū)之后后繼，最后一個(gè)元素?zé)o后繼只有前驅(qū)，其余每個(gè)元素都有唯一前驅(qū)和唯一后繼。2、 線性表的邏輯結(jié)構(gòu)定義，對(duì)線性表的操作。3、 線性表的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。4、 線性表的操作在兩種存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)。5、 一元多項(xiàng)式的線性表表示方法、稀疏多項(xiàng)式的抽象

4、數(shù)據(jù)類型定義、表示和加法的實(shí)現(xiàn)。知識(shí)點(diǎn)1、 線性表的邏輯結(jié)構(gòu)，指線性表的數(shù)據(jù)元素間存在著線性關(guān)系。在順序存儲(chǔ)結(jié)構(gòu)中，元素存儲(chǔ)的先后位置反映出這種邏輯關(guān)系，而在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，是靠指針來(lái)反映這種邏輯關(guān)系的。2、 順序存儲(chǔ)結(jié)構(gòu)用一維數(shù)據(jù)表示，給定下標(biāo)，可以存取相應(yīng)元素，屬于隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。3、 盡管“只要知道某結(jié)點(diǎn)的指針就可以存取該元素”，但因?yàn)殒湵淼拇嫒《夹枰獜念^指針開始，順鏈進(jìn)行，故鏈表不屬于隨機(jī)存取結(jié)構(gòu)。4、 鏈表是本章學(xué)習(xí)的重點(diǎn)和難點(diǎn)。要理解頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)和元素節(jié)點(diǎn)的差別。為什么要設(shè)置頭結(jié)點(diǎn)。頭結(jié)點(diǎn)是在插入、刪除等操作時(shí)，為了算法的統(tǒng)一而設(shè)立的（若無(wú)頭結(jié)點(diǎn)，則在第一元素前插入

5、元素或者刪除第一元素時(shí)，鏈表的頭指針總在變化，與在其他位置插入或者刪除元素的步驟是不一樣的，算法寫起來(lái)比較復(fù)雜）。掌握通過(guò)畫出結(jié)點(diǎn)圖來(lái)進(jìn)行鏈表的生成、插入、刪除、遍歷等操作的方法。對(duì)鏈表（不包括循環(huán)鏈表）的任何操作，都要從頭結(jié)點(diǎn)開始，頭結(jié)點(diǎn)的指針具有標(biāo)記作用，故頭指針往往被稱為鏈表的名字，如鏈表la既指出了鏈表的名字叫l(wèi)a也指出了鏈表頭結(jié)點(diǎn)的指針是la5、 鏈表操作中應(yīng)注意不要使鏈表意外斷開。因此若在某元素前插入一個(gè)元素或刪除某元素，必須知道該元素的前驅(qū)結(jié)點(diǎn)的指針。指針操作時(shí)候，先勾連新的指針，再改變舊的指針。6、 從時(shí)間和空間復(fù)雜度的角度綜合分析比較線性表在順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)下的特點(diǎn)。7

6、、 靜態(tài)鏈表，與鏈表進(jìn)行對(duì)比理解。例如，鏈表la在有頭結(jié)點(diǎn)的情況下，第一元素可表示為la-next,而在靜態(tài)鏈表sa中，靜態(tài)鏈表常用下標(biāo)0作“頭結(jié)點(diǎn)”，其第一元素可是sa0.next，相對(duì)p=p-next 有 I = sai.next來(lái)找到第i個(gè)元素的后繼。，對(duì)鏈表用p=null來(lái)判斷是否到尾，而靜態(tài)鏈表用i=-1來(lái)判斷鏈表是否結(jié)束。后續(xù)章節(jié)中樹的雙親表示法，圖的鄰接表表示法、表插入排序、鏈?zhǔn)交鶖?shù)排序、地址排序等都是靜態(tài)鏈表的應(yīng)用。重點(diǎn)掌握的內(nèi)容：1. 線性表的定義及判別和抽象數(shù)據(jù)類型的描述，線性表中每一種操作的功能，對(duì)應(yīng)的函數(shù)名、返回值類型和參數(shù)表中每個(gè)參數(shù)的作用。2. 線性表的順序存儲(chǔ)結(jié)構(gòu)

7、的類型定義，即List類型的定義和每個(gè)域（T *data;int maxSize;int last;）的定義及作用。3. 線性表的每一種運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法，及相應(yīng)的時(shí)間復(fù)雜度。4. 鏈接存儲(chǔ)的概念，線性表的單鏈接和雙鏈接存儲(chǔ)的結(jié)構(gòu)，向單鏈表中一個(gè)結(jié)點(diǎn)之后插入新結(jié)點(diǎn)或從單鏈表中刪除一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針鏈接過(guò)程。5. 單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)，每個(gè)域的定義及作用，即LNode類型的定義及結(jié)構(gòu)。6. 帶表頭附加結(jié)點(diǎn)的鏈表、循環(huán)鏈表、雙向鏈表的結(jié)構(gòu)特點(diǎn)。7. 線性表的每一種運(yùn)算在單鏈表上實(shí)現(xiàn)的算法及相應(yīng)的時(shí)間復(fù)雜度。8. 在順序存儲(chǔ)或鏈接存儲(chǔ)的線性表上實(shí)現(xiàn)指定功能的算法的分析和設(shè)計(jì)。9Jos

8、ephus問(wèn)題的求解過(guò)程。10順序表和線性鏈表的性能比較及各自使用背景。對(duì)于本章的其余內(nèi)容均作一般掌握。第3章 棧和隊(duì)列內(nèi)容提要1、 從數(shù)據(jù)結(jié)構(gòu)角度講，棧和隊(duì)列都是線性結(jié)構(gòu)。其操作是線性表操作的子集，是操作受限的線性表。但從數(shù)據(jù)類型的角度看，它們是和線性表大不同的重要的抽象數(shù)據(jù)類型。2、 棧的定義和操作。棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表。該端成為棧的頂端。3、 棧的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，及在這兩種結(jié)構(gòu)下實(shí)現(xiàn)棧的操作。4、 棧的應(yīng)用：表達(dá)式求值、過(guò)程調(diào)用、遞歸過(guò)程。5、 隊(duì)列的定義和操作，隊(duì)列的刪除在一端（頭），而插入在另一端（尾）。因此在兩種存儲(chǔ)結(jié)構(gòu)中，一般都對(duì)要隊(duì)頭和隊(duì)尾兩個(gè)指針。6、

9、 鏈隊(duì)列空的條件是首位指針相等。而循環(huán)隊(duì)列滿的條件的判定，有犧牲一個(gè)單元和設(shè)置標(biāo)記兩種方法。知識(shí)點(diǎn)1、 棧和隊(duì)列操作在兩種存儲(chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)。注意因?yàn)闂Ｔ谝欢瞬僮?，通常鏈棧不設(shè)置頭結(jié)點(diǎn)。2、 中綴表達(dá)式轉(zhuǎn)成后綴表達(dá)式，后綴表達(dá)式求值3、 用遞歸解決問(wèn)題：?jiǎn)栴}的定義是遞歸的，數(shù)據(jù)結(jié)構(gòu)是遞歸的，以及問(wèn)題的解法是遞歸的，掌握典型問(wèn)題的算法。4、 對(duì)僅剩一個(gè)元素的鏈隊(duì)列刪除元素時(shí)的處理（令隊(duì)尾指針指向隊(duì)頭），特別是僅設(shè)尾指針的循環(huán)鏈隊(duì)列的各種操作的實(shí)現(xiàn)。5、 循環(huán)隊(duì)列中隊(duì)列空用隊(duì)頭指針等于隊(duì)尾指針來(lái)判斷，隊(duì)列滿則可惜正一個(gè)單元及設(shè)置標(biāo)記方法兩種辦法。這里特別注意入隊(duì)、出隊(duì)和求元素個(gè)數(shù)等操作中的取模運(yùn)算。

10、6、 在后續(xù)章節(jié)中多處有棧和隊(duì)列的應(yīng)用，如二叉樹遍歷的遞歸和非遞歸算法，圖的深度優(yōu)先遍歷等都用到棧，而樹的層次遍歷、圖的廣度優(yōu)先遍歷等則用到隊(duì)列。重點(diǎn)掌握的內(nèi)容：1. 棧的定義和抽象數(shù)據(jù)類型的描述，棧中每一種操作的功能，對(duì)應(yīng)的函數(shù)名、返回值類型和參數(shù)表中每個(gè)參數(shù)的作用。2. 棧的順序存儲(chǔ)結(jié)構(gòu)的類型定義，即Stack類型的定義和每個(gè)域的定義及作用。3棧的每一種運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法，及相應(yīng)的時(shí)間復(fù)雜度。4. 棧的每一種運(yùn)算在鏈接存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法及相應(yīng)的時(shí)間復(fù)雜度。5. 算術(shù)表達(dá)式的中綴表示和后綴表示，以及相互轉(zhuǎn)換的規(guī)則，后綴表達(dá)式求值的方法。6給定n個(gè)棧元素, 出?？赡芑虿豢赡艿男蛄?/p>

11、數(shù)。7. 隊(duì)列的定義和抽象數(shù)據(jù)類型的描述，隊(duì)列中每一種操作的功能，對(duì)應(yīng)的函數(shù)名、返回值類型和參數(shù)表中每個(gè)參數(shù)的作用。8. 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)的類型定義，即Queue類型的定義和每個(gè)域的定義及作用。9. 隊(duì)列的每一種運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法及相應(yīng)的時(shí)間復(fù)雜度。10. 利用棧和隊(duì)列解決簡(jiǎn)單問(wèn)題的算法分析和設(shè)計(jì)。11、遞歸算法，棧與遞歸，掌握遞歸程序的兩個(gè)重要方面，一是遞歸終止的條件，一是遞歸體。遞歸分三種，問(wèn)題的定義是遞歸的，數(shù)據(jù)結(jié)構(gòu)的定義是遞歸的 ，解決問(wèn)題的方法是遞歸的。理解遞歸工作棧的工作過(guò)程。每一層遞歸調(diào)用所需保存的信息構(gòu)成一個(gè)工作記錄，通常它包括三個(gè)方面的內(nèi)容，返回地址、在本次過(guò)程

12、調(diào)用時(shí)，為與形參結(jié)合的實(shí)參創(chuàng)建副本、本層的局部變量值。每進(jìn)入一層遞歸時(shí)，系統(tǒng)就要建立一個(gè)新的工作記錄，把上述項(xiàng)目壓入棧中。每退出一層遞歸，就從遞歸工作棧中退出一個(gè)工作記錄。理解書上P106圖3.12一般掌握的內(nèi)容：1. 后綴表達(dá)式求值的算法，把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法。2. 隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)，以及實(shí)現(xiàn)每一種隊(duì)列運(yùn)算的算法和相應(yīng)的時(shí)間復(fù)雜度。對(duì)于本章的其余內(nèi)容均作一般了解。第4章 數(shù)組、串與廣義表內(nèi)容提要1、 數(shù)組的邏輯結(jié)構(gòu)定義和存儲(chǔ)。2、 特殊矩陣的存儲(chǔ)和運(yùn)算3、 稀疏矩陣的存儲(chǔ)和運(yùn)算4、 廣義表的定義以及存儲(chǔ)5、 廣義表運(yùn)算的遞歸算法6、 串是數(shù)據(jù)元素與字符的線性表，串的定義及操作

13、。7、 串的基本操作，用串的基本操作來(lái)編寫算法串的其他操作。8、 串的存儲(chǔ)結(jié)構(gòu)，因?yàn)榇菙?shù)據(jù)元素為字符的線性表，所以存在“結(jié)點(diǎn)大小”的問(wèn)題，靜態(tài)和動(dòng)態(tài)（塊鏈結(jié)構(gòu)、堆結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。9、 樸素模式匹配算法及改進(jìn)（KMP）算法。知識(shí)點(diǎn)1、 數(shù)組（主要是二維）在以行序優(yōu)先和列序優(yōu)先的存儲(chǔ)中的地址計(jì)算方法2、 特殊矩陣在壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。3、 稀疏矩陣的三元組表存儲(chǔ)結(jié)構(gòu)及矩陣轉(zhuǎn)置的算法。4、 廣義表的head和tail運(yùn)算符5、 給定廣義表畫出其存儲(chǔ)結(jié)構(gòu)6、 通過(guò)廣義表的遞歸模型，掌握如何編寫遞歸算法。7、 用串的基本操作編寫串的其他操作(如index和replace等)和串的模式匹配

14、。8、 了解kmp算法的推導(dǎo)過(guò)程，熟練掌握手工描述求匹配串的next和nextval函數(shù)值9、 盡管樸素的模式匹配的時(shí)間復(fù)雜度是O(m*n),KMP算法的時(shí)間復(fù)雜度是O(m+n).但在一般情況下，前者實(shí)際執(zhí)行時(shí)間近似O(m+n)，因此至今仍被采用。KMP算法僅在主串與模式串存在許多“部分匹配”時(shí)才顯得比前者快得多，其主要優(yōu)點(diǎn)是主串不回溯。重點(diǎn)掌握的內(nèi)容：1. 一維和二維數(shù)組中元素的按下標(biāo)和按地址的訪問(wèn)方式以及相互轉(zhuǎn)換，元素地址和數(shù)組地址的計(jì)算，元素占用存儲(chǔ)空間大小和數(shù)組占用存儲(chǔ)空間大小的計(jì)算。2. 多維數(shù)組的邏輯結(jié)構(gòu)特征。3. 多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及地址計(jì)算公式。4數(shù)組是一種隨機(jī)存取結(jié)構(gòu)的原

15、因。5特殊矩陣和稀疏矩陣的概念。6特殊矩陣（包括對(duì)角矩陣）和壓縮存儲(chǔ)的下標(biāo)變換方法及所需存儲(chǔ)空間。7. 稀疏矩陣的定義和三元組線性表表示。8. 稀疏矩陣的轉(zhuǎn)置運(yùn)算及在三元組表存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。9. 廣義表的定義和表示，廣義表長(zhǎng)度和深度的計(jì)算。10廣義表上的求表頭、表尾運(yùn)算。11. 廣義表的鏈接存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)類型的定義，分別求廣義表長(zhǎng)度和深度的遞歸算法，它們對(duì)應(yīng)的時(shí)間復(fù)雜度。12. 串的模式匹配。樸素模式匹配的算法。kmp算法的推導(dǎo)過(guò)程，手工描述求匹配串的next和nextval函數(shù)值.第二部分 部分復(fù)習(xí)題第1章 緒論課本P371.2;1.3;1.7;1.8;1.13;1.14補(bǔ)充題目：第2章

16、線性表還有很多算法的題目，請(qǐng)見(jiàn)文件線性鏈表.PDF 第3章 棧和隊(duì)列棧的概念、算法練習(xí)題 P131 3.1 (1) (2) 3.3 3.4棧的類定義-與線性表不同的運(yùn)算（方法），Push 與 Insert ; Pop 與 Remove ; getTop 與getData; 順序棧：我們課本上順序棧采用順序表作為其存儲(chǔ)結(jié)構(gòu)，在順序棧的聲明中用一維數(shù)組作為棧的存儲(chǔ)空間，存放棧元素的數(shù)組的頭指針是*elements，該數(shù)組的最大允許存放元素個(gè)數(shù)為maxSize，當(dāng)前棧頂位置由數(shù)組下標(biāo)指針top指示，如果棧為空，top = -1 ; 棧不為空時(shí)，elements0 表示棧中的第一個(gè)元素?；谶@種存儲(chǔ)結(jié)

17、構(gòu)，如何實(shí)現(xiàn)棧的類定義中定義的那些運(yùn)算，特別是，Push ； Pop ；getTop鏈?zhǔn)綏?，采用鏈?zhǔn)綏１硎疽粋€(gè)棧，便于結(jié)點(diǎn)的插入和刪除，特別在程序中需要同時(shí)使用多個(gè)棧的情況下，用鏈接表示不僅能夠提高效率，還可以達(dá)到共享存儲(chǔ)空間的目的。鏈?zhǔn)綏５臈ｍ斣阪湵淼谋眍^。新結(jié)點(diǎn)的插入和棧頂結(jié)點(diǎn)的刪除都是在鏈表的第一個(gè)元素即棧頂進(jìn)行的，所以采用不帶頭結(jié)點(diǎn)的單鏈表來(lái)表示即可。鏈?zhǔn)綏５念惗x，采用了單鏈表中關(guān)于單鏈表結(jié)點(diǎn)的struct定義方法來(lái)定義結(jié)點(diǎn)。在鏈?zhǔn)綏５念惗x中，用棧頂指針top表示單鏈表的頭指針?；阪?zhǔn)綏５拇鎯?chǔ)結(jié)構(gòu)定義，如何實(shí)現(xiàn)棧的類定義中的那些運(yùn)算，特別是，Push ； Pop ；getTop棧

18、的應(yīng)用，括號(hào)匹配的算法描述，P95,改進(jìn)這個(gè)算法，利用3個(gè)棧來(lái)解決課后習(xí)題3.13棧的應(yīng)用，表達(dá)式的計(jì)算，表達(dá)式的中綴、前綴、后綴表示是通用定義，對(duì)照書上P100的算法，能夠?qū)⒔o出的中綴表達(dá)式轉(zhuǎn)換成相應(yīng)的后綴表達(dá)式。課后習(xí)題 P134 3.4 (1),(2),(3),(4)應(yīng)用后綴表示計(jì)算表達(dá)式的值，能夠參照書上算法程序3.9 (P97-P98) 來(lái)畫出某個(gè)后綴表達(dá)式求解過(guò)程中棧的內(nèi)容的變化。棧與遞歸，掌握遞歸程序的兩個(gè)重要方面，一是遞歸終止的條件，一是遞歸體。遞歸分三種，問(wèn)題的定義是遞歸的，數(shù)據(jù)結(jié)構(gòu)的定義是遞歸的 ，解決問(wèn)題的方法是遞歸的。理解遞歸工作棧的工作過(guò)程。每一層遞歸調(diào)用所需保存的信

19、息構(gòu)成一個(gè)工作記錄，通常它包括三個(gè)方面的內(nèi)容，1、返回地址 2、在本次過(guò)程調(diào)用時(shí)，為與形參結(jié)合的實(shí)參創(chuàng)建副本 3、本層的局部變量值。每進(jìn)入一層遞歸時(shí)，系統(tǒng)就要建立一個(gè)新的工作記錄，把上述項(xiàng)目壓入棧中。每退出一層遞歸，就從遞歸工作棧中退出一個(gè)工作記錄。理解書上P106圖3.12遞歸算法的練習(xí)題書上p132，3.14 3.15 3.16 3.19 3.21 任選一。隊(duì)列隊(duì)列的概念用普通的數(shù)組存儲(chǔ)表示隊(duì)列的時(shí)候，會(huì)有什么弊端。循環(huán)隊(duì)列表示隊(duì)列空和滿的方法有哪些。書上P116定義的循環(huán)隊(duì)列的類定義中，實(shí)現(xiàn)判斷隊(duì)空隊(duì)滿的算法、實(shí)現(xiàn)入隊(duì)、出隊(duì)的算法。書上P133 題目3.22 3.23 3.24鏈?zhǔn)疥?duì)列的

20、類定義與單鏈表類定義比較。結(jié)點(diǎn)的定義是一樣的，鏈表的定義有不同，鏈?zhǔn)疥?duì)列的定義中，有一個(gè)隊(duì)頭指針和一個(gè)隊(duì)尾指針。如何實(shí)現(xiàn)鏈?zhǔn)疥?duì)列的入隊(duì)和出隊(duì)。書上P134 題目3.25隊(duì)列應(yīng)用，楊輝三角形 的算法 P121 優(yōu)先級(jí)隊(duì)列的定義用數(shù)組最為優(yōu)先級(jí)隊(duì)列的存儲(chǔ)表示，優(yōu)先級(jí)隊(duì)列入隊(duì)、出隊(duì)的算法書上P134 題目3.29書上P134 題目3.28第3章 棧和隊(duì)列.PDF第4章 數(shù)組、串與廣義表第三部分 部分模擬試題一、單項(xiàng)選擇題 （1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（B）A）有向圖 B）隊(duì)列 C）線索二叉樹 D）B樹（2）在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，則執(zhí)行如

21、下（D）語(yǔ)句序列。A）p=q; p-next=q; B）p-next=q; q-next=p;C）p-next=q-next; p=q; D）q-next=p-next; p-next=q;（3）（A）不是隊(duì)列的基本運(yùn)算。A）在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B）從隊(duì)頭刪除一個(gè)元素C）判斷一個(gè)隊(duì)列是否為空 D）讀取隊(duì)頭元素的值（4）字符A、B、C依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成（B）個(gè)不同的字符串。A）14 B）5 C）6 D）8（5）若順序存儲(chǔ)的循環(huán)隊(duì)列的QueueMaxSize=n，則該隊(duì)列最多可存儲(chǔ)（）個(gè)元素。A）n B）n-1 C）n+1 D）不確定（6）下

22、述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？（）A）存儲(chǔ)密度大 B）插入和刪除運(yùn)算方便 C）獲取符合某種條件的元素方便 D）查找運(yùn)算速度快（7）設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在600(10)，A33存放位置在678(10)，每個(gè)元素占一個(gè)空間，問(wèn)A23(10)存放在什么位置？（腳注(10)表示用10進(jìn)制表示，m3）（）。A）658 B）648 C）633 D）653（8）對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（）方面的內(nèi)容。A）健壯性和可讀性 B）并行性 C）正確性 D）時(shí)空復(fù)雜度（9）在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（）。A）p-next=HL-next; HL-n

23、ext=p B）p-next=HL; HL=pC）p-next=HL; p=HL D）HL=p; p-next=HL（10）對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）A）經(jīng)常需要隨機(jī)地存取元素 B）經(jīng)常需要進(jìn)行插入和刪除操作C）表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D）表中元素的個(gè)數(shù)不變（11）一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是（）。A）2 3 1B）3 2 1C）3 1 2 D）1 2 3（12）若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為（）參數(shù)。A）值 B）函數(shù) C）指針 D）引用（13）在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有

24、相同的（）。A）行號(hào) B）列號(hào) C）元素值 D）非零元素個(gè)數(shù)（14）以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（）A）有向圖 B）棧 C）二叉樹 D）B樹（15）若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。A）單鏈表B）雙鏈表C）帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D）單循環(huán)鏈表（16）（）不是隊(duì)列的基本運(yùn)算。A）在隊(duì)列第i個(gè)元素之后插入一個(gè)元素 B）從隊(duì)頭刪除一個(gè)元素C）判斷一個(gè)隊(duì)列是否為空 D）讀取隊(duì)頭元素的值（17）字符A、B、C、D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個(gè)不同的字符串？A）15 B）14 C）16 D）21（1

25、8）隊(duì)列的特點(diǎn)是（）。A）先進(jìn)后出B）先進(jìn)先出C）任意位置進(jìn)出D）前面都不正確（18）限定在一端加入和刪除元素的線性表稱為（）。A）雙向鏈表B）單向鏈表C）棧D）隊(duì)列（19）從L=(apple,pear),(orange,banana)中，取出banana元素的表達(dá)式為（）。A）head(tail(L)B）head(head(tail(L)C）tail(head(tail(L)D）head(tail(head(tail(L)（20）設(shè)D=A,B,C,D，R=,，則數(shù)據(jù)結(jié)構(gòu)(D,R)是（）。A）樹B）圖B）線性表D）前面都正確（21）在算法的時(shí)間復(fù)雜度中，n表示問(wèn)題規(guī)模，f(n)表示基本操作重復(fù)

26、執(zhí)行的次數(shù)，則隨問(wèn)題的規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率同（）相同。A）f(n)B）nC）O(n)D）前面都不正確二、已知一個(gè)65稀疏矩陣如下所示，試：（1）寫出它的三元組線性表；（2）給出三元組線性表的順序存儲(chǔ)表示。解答（1） (0,4,1),(2,1,-1),(3,4,-2),(4,0,5),(5,2,7)（2）三元組線性表的順序存儲(chǔ)表示如下所示：smArray如下行列值04121-134-2405527Rows= 6；Cols = 5;Terms = 5三、設(shè)有數(shù)組A-1:3,0:6,-2:3，按行為主序存放在2000開始的連續(xù)空間中，如元素的長(zhǎng)度是5，試計(jì)算出A1,1,1的存儲(chǔ)位置。解

27、答：A1,1,1的存儲(chǔ)位置=2000+(1-(-1)*(6-0+1)*(3-(-2)+1)+(1-0)*(3-(-2)+1)+(1-(-2)*5=2465。四、試寫出表達(dá)式(a+b/c)*(d-e*f)的后綴表示。解答：abc/+def*-*五、假設(shè)把n個(gè)元素的序列（a1,a2,an）滿足條件akaj(ij)，試問(wèn)，當(dāng)ai與aj相互交換后，該序列中逆序元素的個(gè)數(shù)一定不會(huì)增加，這句話對(duì)不對(duì)？如果對(duì)，請(qǐng)說(shuō)明為什么？如果不對(duì)，請(qǐng)舉一例說(shuō)明。解答：不對(duì)，例如序列3、3、4、2、l的“逆序元素”個(gè)數(shù)是2，2和1是“逆序元素”；但是將第二個(gè)3和2交換后，成為3、2、4、3、l，此時(shí)“逆序元素”個(gè)數(shù)是3，2、3和1是“逆序元素”。然而交換后一定減少的是“逆序?qū)Α钡膫€(gè)數(shù)，例如上例中3、3、4、2、l的逆序?qū)Φ膫€(gè)數(shù)是 7，交換第二個(gè) 3和2后，3、2、4、3