數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)說(shuō)課講解

1、精品文檔 數(shù)據(jù)結(jié)構(gòu) 第一章 緒論 1、數(shù)據(jù)結(jié)構(gòu)的定義：按照某種邏輯關(guān)系組織起來(lái)的數(shù)據(jù)集、數(shù)據(jù)與數(shù)據(jù)間的邏 輯關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)形式以及定義在數(shù)據(jù)集上的一組操作與操作的 實(shí)現(xiàn)這三個(gè)方面統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)。 2、數(shù)據(jù)主要分為兩大類(lèi)：數(shù)值型數(shù)據(jù)和非數(shù)值類(lèi)型數(shù)據(jù)。數(shù)值型數(shù)據(jù)主要包括 整數(shù)、實(shí)數(shù)和復(fù)數(shù)等；非數(shù)值類(lèi)型數(shù)據(jù)包括字符、字符串、文字、聲音、圖形、 圖像等。 3、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素的集合以及定義在該集合上的數(shù)據(jù)元素之 間的一種或多種特定關(guān)系。 4、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是根據(jù)解決問(wèn)題的功能目標(biāo)而建立的； 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)是根據(jù)解決問(wèn)題的性能要求而建立的。 5、數(shù)據(jù)類(lèi)型是一個(gè)具體相同性

2、質(zhì)的值的集合以及定義在該集合上的一組操作的 總稱。數(shù)據(jù)類(lèi)型定義了數(shù)據(jù)的性質(zhì)、取值范圍以及對(duì)數(shù)據(jù)所能進(jìn)行的一組操作。 6、根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同特性，可將數(shù)據(jù)結(jié)構(gòu)分為：集合、線性機(jī) 構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)。 7、一個(gè)非空的線性結(jié)構(gòu)的邏輯特點(diǎn)： 1.只有一個(gè)數(shù)據(jù)元素沒(méi)有前驅(qū)， 稱其為“第 一個(gè)”元素； 2.只有一個(gè)數(shù)據(jù)元素沒(méi)有后繼，稱其為“最后一個(gè)”元素； 3.除第 一個(gè)元素外，其余數(shù)據(jù)元素有且只有一個(gè)前驅(qū)； 4. 除最后一個(gè)元素外，其余數(shù) 據(jù)元素有且只有一個(gè)后繼。 8、算法是指為解決一個(gè)問(wèn)題而采用的方法和步驟； 9、算法的五個(gè)特性： 1.有窮性：算法必須在有限步驟及有限時(shí)間內(nèi)終止，并計(jì)

3、算出結(jié)果；2.確定性：算法的每一個(gè)操作步驟都有確切的含義， 即無(wú)二義性； 3. 算 法的每一個(gè)操作步驟，都是有效的、可行的； 4.輸入：一個(gè)算法有零個(gè)或多個(gè)輸 入，這些輸入取自于某個(gè)特定對(duì)象的集合； 5.輸出：一個(gè)算法必須有一個(gè)或多個(gè) 輸出。算法的目的是為了求解， 通過(guò)算法所求得的 “解”即是算法的輸出。 注意， 計(jì)算機(jī)算法的輸出不一定就是計(jì)算機(jī)顯示或打印輸出， 一個(gè)算法得到的結(jié)果實(shí)際 就是算法的輸出。 第二章 線性表 10、線性表是一種最基本而且應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)， 其特點(diǎn)是結(jié)構(gòu)中的各數(shù)據(jù) 元素之間存在著一對(duì)一的關(guān)系，是一種最典型的線性結(jié)構(gòu)。 11、線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限

4、序列。 12、線性表中的數(shù)據(jù)元素在位置上是有序的，相鄰的元素之間存在著序偶關(guān)系。 13、順序表的順序存儲(chǔ)結(jié)構(gòu)是指把線性表中所有數(shù)據(jù)元素， 按照其邏輯順序依次 存儲(chǔ)到計(jì)算機(jī)存儲(chǔ)器中從指定位置開(kāi)始的一塊連續(xù)的存儲(chǔ)空間中， 數(shù)據(jù)元素間的 存儲(chǔ)(物理)位置即表示了它的邏輯位置。 14、順序表基本操作的實(shí)現(xiàn)： 1.初始化操作； 2.求長(zhǎng)度操作； 3.判空操作； 4.清空 操作； 5.取元素操作； 6.按值查找操作； 7.插入操作； 8.刪除操作。 15、算法的空間效率是指算法在計(jì)算機(jī)上運(yùn)行時(shí)所需存儲(chǔ)空間的大小。 算法的空間復(fù)雜度用大 0記法表示為：S (n) =O (f (n) 隨著問(wèn)題規(guī)模 n 的增大

5、，算法運(yùn)行時(shí)所需輔助存儲(chǔ)空間的增長(zhǎng)率的數(shù)量級(jí)為 f (n) o若算法運(yùn)行時(shí)所占的存儲(chǔ)空間與問(wèn)題規(guī)模無(wú)關(guān)，是個(gè)常量，則稱這種算 法為原地工作，其空間復(fù)雜度用 0(1)表示。 16、順序表的優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)：a.實(shí)現(xiàn)方法簡(jiǎn)單，各種高級(jí)語(yǔ)言中都有數(shù)組，容易實(shí)現(xiàn)； b.訪問(wèn)元素的速度快，因?yàn)樵陧樞虮碇羞壿嬌舷噜彽膬蓚€(gè)元素在存儲(chǔ) 位置上也必定相鄰， 所以只要知道了第一個(gè)元素的地址， 其他任何一個(gè)元素的地 址都可通過(guò)簡(jiǎn)單的計(jì)算求得，故可實(shí)現(xiàn)隨機(jī)存取，即順序表L的第i個(gè)元素即為 L.basei-1o 缺點(diǎn)：a.需占用連續(xù)的存儲(chǔ)區(qū)，存儲(chǔ)要求高，不能利用小塊存儲(chǔ)區(qū)； b.由于在順序表中邏輯上相鄰的兩個(gè)元素在存儲(chǔ)位

6、置上也必定相鄰， 所以在進(jìn)行插入和刪除操作時(shí)，需要進(jìn)行大量的元素移動(dòng)操作，影響了算法效率。 17、通常把使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的線性表稱為鏈表。 18、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來(lái)存放線性表中的數(shù)據(jù)元 素，這組存儲(chǔ)單元既可以是連續(xù)的， 也可以是不連續(xù)的， 甚至可以零散分布在內(nèi) 存中的任意位置上。 19、鏈表的相關(guān)概念： 1.首元結(jié)點(diǎn)，指鏈表中用于存儲(chǔ)線性表的第一各數(shù)據(jù)元素 的結(jié)點(diǎn)； 2.頭結(jié)點(diǎn)，在鏈表中為了便于進(jìn)行插入和刪除等操作，為鏈表增設(shè)一個(gè) 輔助結(jié)點(diǎn)， 稱該輔助結(jié)點(diǎn)為鏈表的頭結(jié)點(diǎn)。 頭結(jié)點(diǎn)在鏈表中可有可無(wú)； 3.頭指針， 是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，可以唯一地表示一個(gè)鏈

7、表； 4.空指針，當(dāng)鏈表 中某個(gè)結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)，稱該結(jié)點(diǎn)的指針域?yàn)榭罩羔槨?20、鏈表的表長(zhǎng)是指鏈表中存放數(shù)據(jù)元素的結(jié)點(diǎn)數(shù)目。 21、鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表。 22、單鏈表的建立操作： 1. 頭插法建立單鏈表：在單鏈表的建立過(guò)程中，總是將由讀入元素所生成的 結(jié)點(diǎn)插入到鏈表的表首端，即插入時(shí)始終將新生成結(jié)點(diǎn)作為第 1 個(gè)結(jié)點(diǎn)插入。 2. 尾插法建立單鏈表：與頭插法正好相反，在單鏈表的建立過(guò)程中，其每次 都是將所生成的新結(jié)點(diǎn)插入到單鏈表尾端， 即在插入時(shí)始終是新生成結(jié)點(diǎn)作為最 后一個(gè)結(jié)點(diǎn)插入。 23、鏈表的優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)：a能充分利用內(nèi)存中的小塊存儲(chǔ)區(qū)； b.便于進(jìn)行插入和刪除操作

8、，在進(jìn)行插入和刪除操作時(shí)不需要進(jìn)行元 素的移動(dòng)，只需修改相應(yīng)結(jié)點(diǎn)的指針域即可。 缺點(diǎn)：a.與順序表相比，其實(shí)現(xiàn)方法較復(fù)雜，特別在對(duì)雙鏈表進(jìn)行操作時(shí)不 僅要考慮向后指向的“鏈”，還需考慮向前指向的“鏈” ； b. 無(wú)法像順序表那樣實(shí)現(xiàn)隨機(jī)存取， 在鏈表中要找某個(gè)結(jié)點(diǎn)只能從表 頭開(kāi)始向后尋找； c. 在鏈表的每個(gè)結(jié)點(diǎn)需要附加存儲(chǔ)關(guān)系信息（指針域），因此當(dāng)問(wèn)題 規(guī)模較小且基本一定時(shí)，鏈表所需存儲(chǔ)空間比順序表多。 第三章 棧與隊(duì)列 24、棧的定義：棧是一種將插入操作與刪除操作限制在同一段進(jìn)行的特殊線性表。 在這個(gè)特殊的線性表中，進(jìn)行插入與刪除操作的一端稱為棧頂 （Top），另一端則 稱為棧底（Bott

9、om）。也就是說(shuō)棧的插入操作與刪除操作均在棧頂端進(jìn)行，其中, 插入操作稱為入棧操作（Push），刪除操作稱為出棧操作（Pop）。不含任何元素 的棧稱為空棧。 25、棧具有后進(jìn)先出或者說(shuō)為先進(jìn)后出的特性， 故棧又稱為后進(jìn)先出表或先進(jìn)后 出表。 26、棧的基本操作：初始化、銷(xiāo)毀、判空、清空、入棧、出棧、取棧頂、求棧長(zhǎng) 及遍歷。 27、經(jīng)試探可行則行進(jìn)，不可行則返回重新試探的方法稱為回溯法。 28、一個(gè)概念、函數(shù)等對(duì)象用自己來(lái)定義自己，則稱該對(duì)象為遞歸定義的。在程 序設(shè)計(jì)語(yǔ)言中，一個(gè)算法直接或間接調(diào)用自己，則稱該算法為遞歸算法。 29、遞歸法則： 1.基準(zhǔn)情形法則。遞歸定義中的基準(zhǔn)情形即遞歸出口，它

10、本身不 再使用遞歸定義，是遞歸的結(jié)束條件； 2.不斷推進(jìn)法則。不斷推進(jìn)法則是指在遞 歸求解過(guò)程中，每一次遞歸調(diào)用都必須使求解狀況朝接近基準(zhǔn)情形的方向推進(jìn)。 30、隊(duì)列是一種插入操作限制在一端進(jìn)行而刪除操作限制在另一端進(jìn)行的特殊線 性表。在這個(gè)特殊的線性表中進(jìn)行插入操作的一端成為隊(duì)尾， 進(jìn)行刪除操作的一 端稱為隊(duì)頭。 在隊(duì)列尾端進(jìn)行的插入操作稱為入隊(duì)操作， 而在隊(duì)列頭端進(jìn)行的刪 除操作稱為出隊(duì)操作。不含任何元素的隊(duì)列稱為空隊(duì)。 31、隊(duì)列具有先進(jìn)先出或者說(shuō)后進(jìn)后出的重要特性， 故隊(duì)列又稱為先進(jìn)先出表或 后進(jìn)后出表。 第四章 串 32、串的定義：串是由零個(gè)或多個(gè)任意字符組成的有限序列，一般記作：S

11、= “s1s2sisn” (n 0)。其中S是串名，用雙引號(hào)括起來(lái)的字符序列為串值， 但引號(hào)本身并不屬于串的內(nèi)容，它的作用是為了避免與變量名或數(shù)的常量相混 淆。Si (K i n)稱為串的元素，它可以是任意字母、數(shù)字或者是其他字符， 是構(gòu)成串的基本單位， i 是它在整個(gè)串中的序號(hào)。 n 為串的長(zhǎng)度，表示串中所包 含的字符個(gè)數(shù)。例如，串 S 1 = “ abcd” ，串的元素為一個(gè)字母，其長(zhǎng)度為 5。而在 串S2= “ 123456”，串的元素為一個(gè)數(shù)字，其長(zhǎng)度為 6。 33、串的靜態(tài)順序存儲(chǔ)結(jié)構(gòu)利用的是數(shù)組的靜態(tài)分配方式， 它是為每個(gè)定義的字 符串分配一個(gè)固定長(zhǎng)度的連續(xù)存儲(chǔ)區(qū)域， 將字符串中的

12、字符順序地存放在存儲(chǔ)區(qū) 域的各個(gè)單元里。實(shí)質(zhì)上就是將串定義成字符數(shù)組， 利用串名可以直接訪問(wèn)串值。 用這種表示方式，串的存儲(chǔ)空間在編譯時(shí)確定，其大小不能改變。 34、串的動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)仍是為每個(gè)定義的字符串分配一個(gè)連續(xù)存儲(chǔ)區(qū)域，將 字符串中的字符順序地存放在這組存儲(chǔ)區(qū)域中的各個(gè)單元里， 只是這個(gè)存儲(chǔ)區(qū)域 不是在操作前分配的固定長(zhǎng)度的區(qū)域， 而是在操作過(guò)程中根據(jù)需要?jiǎng)討B(tài)分配得到 的，即在程序運(yùn)行時(shí)為每個(gè)產(chǎn)生的串分配一塊實(shí)際串長(zhǎng)所需的存儲(chǔ)空間， 若分配 成功，則返回指向該存儲(chǔ)空間起始地址的指針，作為串的基址。 第五章 數(shù)組和廣義表 35、 數(shù)組是n個(gè)相同數(shù)據(jù)類(lèi)型的數(shù)據(jù)元素 aO, al,，an-

13、1構(gòu)成的占用一塊地 址連續(xù)的內(nèi)存單元的有限序列。 數(shù)組中任意一個(gè)元素可以用該元素在數(shù)組中的位 置來(lái)表示,數(shù)組元素的位置通常稱作數(shù)組的下標(biāo)。 36、 在大多數(shù)語(yǔ)言中米用以行序?yàn)橹餍虻拇鎯?chǔ)方式，如C語(yǔ)言、C+語(yǔ)言和Pascal 語(yǔ)言；在 Fortran 等少數(shù)語(yǔ)言中采用以列序?yàn)橹餍虻拇鎯?chǔ)方式。 37、常見(jiàn)的特殊矩陣：對(duì)稱矩陣、三角矩陣和帶狀矩陣。 對(duì)稱矩陣：在一個(gè)n階方陣A中，若元素滿足下述興致：aij=aji （K i , j 1時(shí)，其余結(jié)點(diǎn)可分為 m （m0）個(gè)互不相交的有限集合T1 , T2,，Tm。 其中每個(gè)集合本身又是一棵樹(shù)，稱為根結(jié)點(diǎn)的子樹(shù)。 47、樹(shù)的定義具有遞歸性，即樹(shù)的定義中還有

14、樹(shù)。它刻畫(huà)了樹(shù)的固有特性：一棵 非空子樹(shù)由一個(gè)根結(jié)點(diǎn)及若干子樹(shù)構(gòu)成， 而子樹(shù)又可以由其根結(jié)點(diǎn)和若干棵更小 的子樹(shù)構(gòu)成。 48、樹(shù)的基本術(shù)語(yǔ)： 1.結(jié)點(diǎn)的度和樹(shù)的度； 2.孩子、雙親和兄弟； 3.結(jié)點(diǎn)的層次 和樹(shù)的高度； 4.路徑和路徑長(zhǎng)度； 5.有序樹(shù)和無(wú)序樹(shù)； 6.森林。 49、樹(shù)的高度：空樹(shù)的高度為 0；在非空樹(shù)中，所有結(jié)點(diǎn)的最大層次稱為樹(shù)的高 度（或深度）。 50、二叉樹(shù)的概念： 二叉樹(shù)是一種重要的樹(shù)形結(jié)構(gòu)， 在計(jì)算機(jī)領(lǐng)域有著十分廣泛 的應(yīng)用。任何一棵樹(shù)都可以轉(zhuǎn)換成一個(gè)與之對(duì)應(yīng)的二叉樹(shù)， 從而對(duì)樹(shù)的表示與處 理便可用二叉樹(shù)的表示和相關(guān)運(yùn)算來(lái)實(shí)現(xiàn)。 二叉樹(shù)或?yàn)榭諛?shù)， 或是由一個(gè)根結(jié)點(diǎn)加上兩

15、棵分別稱為左子樹(shù)和右子樹(shù)的、 互不 相交的二叉樹(shù)組成。其特點(diǎn)是它是一棵有序樹(shù)，每個(gè)結(jié)點(diǎn)的度最大為 2。 51、 滿二叉樹(shù)：在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)的度均為2，且所有葉子結(jié) 點(diǎn)在同一層上，則這棵二叉樹(shù)稱為滿二叉樹(shù)。 52、完全二叉樹(shù)：對(duì)滿二叉樹(shù)從樹(shù)根為 1 開(kāi)始，按照從上到下、每層從左到右的 原則對(duì)其順序編號(hào)。滿二叉樹(shù)是完全二叉樹(shù)的特例。 53、二叉樹(shù)的性質(zhì)： 1.在二叉樹(shù)的第 i 層上至少有 2i-1 個(gè)結(jié)點(diǎn)（ i0）； 2.深度為 k 的二叉樹(shù)上至多含2k-1個(gè)結(jié)點(diǎn)（k 1）; 3.對(duì)任何一棵非空二叉樹(shù)，如果它含有 no個(gè)葉子結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，那么：n0= n2+1 ； 4.

16、具有n個(gè)結(jié)點(diǎn)的完全二叉 樹(shù)的深度為Iog2n+1；5.對(duì)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)編號(hào)后，則對(duì)任意一個(gè)編號(hào)為 i的結(jié)點(diǎn)：a.若i=1，則該結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親；否則，其雙親結(jié)點(diǎn)編號(hào)為 i/2結(jié)點(diǎn);b.若2in，則該結(jié)點(diǎn)無(wú)左孩子，否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié) 點(diǎn)；c.若2i+1n,則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩 子結(jié)點(diǎn)。 54、二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)是用一組地址連續(xù)的存儲(chǔ)單元來(lái)存放二叉樹(shù)的數(shù)據(jù)元 素。 55、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中， 結(jié)點(diǎn)之間的邏輯關(guān)系是通過(guò)指 針實(shí)現(xiàn)的。由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，所以每個(gè)結(jié)點(diǎn)結(jié)構(gòu)中， 除了數(shù)據(jù)域dat

17、a外，還需要設(shè)置兩個(gè)指針域 LChild和RChild，分別指向左孩子 和右孩子，這種存儲(chǔ)結(jié)構(gòu)稱為二叉鏈表。 56、 二叉樹(shù)的二叉鏈表和三叉鏈表的特點(diǎn)：1.它們均由root唯一確定，如二叉樹(shù) 為空，則 root=NULL ； 2.具有 n 個(gè)結(jié)點(diǎn)的二叉鏈表，共有 2n 個(gè)指針域，其中具 有 n+1 個(gè)空鏈域； 3.在三叉鏈表中易于查找某個(gè)結(jié)點(diǎn)的雙親，而在二叉鏈表中則 需要遍歷整棵樹(shù)才能查找某結(jié)點(diǎn)的雙親。 57、 二叉樹(shù)遍歷是按照一定的路徑訪問(wèn)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被 訪問(wèn)一次。 58、DLR:先序遍歷；LDR:中序遍歷；LRD:后序遍歷。 第七章 圖 59、 圖是一種比線性表和樹(shù)更

18、為復(fù)雜的非線性結(jié)構(gòu)。在圖中， 數(shù)據(jù)元素間的關(guān)系 是多對(duì)多的，任何兩個(gè)元素間都可能存在關(guān)系，元素之間的關(guān)系是任意的。 60、在圖中，通常將數(shù)據(jù)元素稱為頂點(diǎn)，而將數(shù)據(jù)元素之間的關(guān)系稱為邊。 61、圖的相關(guān)術(shù)語(yǔ)： 無(wú)向圖和有向圖； 完全圖； 稀疏圖、 稠密圖、 子圖；權(quán)和網(wǎng)； 頂點(diǎn)的度、 入度和出度； 路徑、路徑長(zhǎng)度、 回路、簡(jiǎn)單路徑和簡(jiǎn)單回路； 連通圖、 連通分量；強(qiáng)連通圖、強(qiáng)連通分量；生成樹(shù)和生成森林。 62、圖的鄰接矩陣存儲(chǔ)方法又稱為數(shù)組表示法， 其方法是用一個(gè)一維數(shù)組來(lái)存儲(chǔ) 圖中頂點(diǎn)的信息，用一個(gè)二維數(shù)組來(lái)存儲(chǔ)圖中頂點(diǎn)之間的領(lǐng)接關(guān)系的信息。 63、圖的遍歷操作是指從圖中的某個(gè)頂點(diǎn)出發(fā)， 按照某種方法對(duì)圖中的所有頂點(diǎn) 進(jìn)行訪問(wèn)，使每個(gè)頂點(diǎn)都被訪問(wèn)且僅被訪問(wèn)一次。 第八章 查找 64、為了取得某一條數(shù)據(jù)， 必須掃描某一范圍的數(shù)據(jù)， 這個(gè)掃描的過(guò)程就是查找。 65、關(guān)鍵字是數(shù)