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

1、精品文檔 數(shù)據(jù)結(jié)構(gòu) 第一章 緒論 1、數(shù)據(jù)結(jié)構(gòu)的定義：按照某種邏輯關(guān)系組織起來的數(shù)據(jù)集、數(shù)據(jù)與數(shù)據(jù)間的邏 輯關(guān)系在計算機存儲器中的存儲形式以及定義在數(shù)據(jù)集上的一組操作與操作的 實現(xiàn)這三個方面統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)。 2、數(shù)據(jù)主要分為兩大類：數(shù)值型數(shù)據(jù)和非數(shù)值類型數(shù)據(jù)。數(shù)值型數(shù)據(jù)主要包括 整數(shù)、實數(shù)和復數(shù)等；非數(shù)值類型數(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ù)解決問題的功能目標而建立的； 數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)是根據(jù)解決問題的性能要求而建立的。 5、數(shù)據(jù)類型是一個具體相同性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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