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

1、數(shù)據(jù)結(jié)構(gòu)第一章 緒論1、數(shù)據(jù)結(jié)構(gòu)的定義：按照某種邏輯關系組織起來的數(shù)據(jù)集、數(shù)據(jù)與數(shù)據(jù)間的邏 輯關系在計算機存儲器中的存儲形式以及定義在數(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ù)元素之 間的一種或多種特定關系。4、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是根據(jù)解決問題的功能目標而建立的； 數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)是根據(jù)解決問題的性能要求而建立的。5、數(shù)據(jù)類型是一個具體相同性質(zhì)的值的集合以及定義在

2、該集合上的一組操作的 總稱。數(shù)據(jù)類型定義了數(shù)據(jù)的性質(zhì)、取值范圍以及對數(shù)據(jù)所能進行的一組操作。6、根據(jù)數(shù)據(jù)元素之間邏輯關系的不同特性，可將數(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)終止，并計 算出結(jié)果； 2.確定性：算法的

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

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

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

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

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

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

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

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

12、數(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ù)元素 a0 , al,，an-1構(gòu)成的占用一塊 地址連續(xù)的內(nèi)存單元的有限序列。 數(shù)組中任意一個元

13、素可以用該元素在數(shù)組中的 位置來表示，數(shù)組元素的位置通常稱作數(shù)組的下標。36、 在大多數(shù)語言中采用以行序為主序的存儲方式，如C 語言、 C+ 語言和 Pascal 語言；在 Fortran 等少數(shù)語言中采用以列序為主序的存儲方式。37、常見的特殊矩陣：對稱矩陣、三角矩陣和帶狀矩陣。對稱矩陣：在一個n階方陣A中，若元素滿足下述興致：aij=aji （1 <i, j <n）,則稱A為n階對稱矩陣。三角矩陣：以主對角線劃分， n 階三角矩陣有 n 階上三角矩陣和 n 階下三角 矩陣兩種。n階上三角矩陣的下三角（不包括主對角線）中的元素均為常數(shù)c （或 0）。n階下三角矩陣正好相反，它的主

14、對角線上方均為常數(shù) c （或0）。帶狀矩陣：帶狀矩陣是指所有非零元素均集中在以對角線為中心的帶狀區(qū)域 中的 n 階方陣。38、常見的稀疏矩陣存儲方法：三元組順序表和十字鏈表。39 、三元組順序表：將表示稀疏矩陣非零元素的三元組按行優(yōu)先或列優(yōu)先（一 般情況下為行優(yōu)先） 的順序排列， 并以此存儲在向量中， 這種稀疏矩陣的順序存 儲結(jié)構(gòu)稱為三元組順序表。40、在廣義表中，每個結(jié)點既可以屬于基本數(shù)據(jù)類型，也可以屬于廣義表類型。41 、廣義表的定義是一個遞歸定義，它和線性表之間的不同之處在于：數(shù)據(jù)元 素之間不僅有先后關系，更有元素內(nèi)部的層次關系。42、廣義表的長度是指表中數(shù)據(jù)元素的個數(shù)，需要注意的是數(shù)據(jù)

15、元素可能是原 子，也可能是子表；廣義表的深度是指表中層次關系的最大深度， 即所含括弧的重數(shù)， 需要注意：“原 子”深度為 0 ，“空表”的深度為 1 。43 、廣義表的特性： 1.廣義表是一個多層次的結(jié)構(gòu)。表中元素可以是子表，子表 的元素還可以是子表； 2.廣義表可為其他廣義表所共享。在實際應用中，利用共 享特性可以節(jié)約存儲空間來； 3.廣義表可以是一個遞歸的表。遞歸表的深度是無 窮值，長度則是有限值。44 、廣義表的存儲形式：頭尾鏈表和擴展線性鏈表。第六章 樹45 、樹形結(jié)構(gòu)是一種典型的非線性結(jié)構(gòu)，在形狀上類似于自然界中倒立的樹， 所有元素之間具有明顯的層次關系和分支關系。 現(xiàn)實生活中， 操

16、作系統(tǒng)的文件管 理、家族的族譜關系和社會機構(gòu)的組成等都可以用樹形象地表示。46、 樹是n (n >0)個結(jié)點的有限集。若 n=0，稱為空樹；否則，在任何一棵 非空樹中滿足以下條件： 1.有且僅有一個特定的沒有前驅(qū)的結(jié)點稱為根結(jié)點； 2. 當n>1時，其余結(jié)點可分為m (m>0 )個互不相交的有限集合T1 , T2 ,， Tm。其中每個集合本身又是一棵樹，稱為根結(jié)點的子樹。47、樹的定義具有遞歸性，即樹的定義中還有樹。它刻畫了樹的固有特性：一棵非空子樹由一個根結(jié)點及若干子樹構(gòu)成， 而子樹又可以由其根結(jié)點和若干棵更 小的子樹構(gòu)成。48、樹的基本術語： 1.結(jié)點的度和樹的度； 2.

17、孩子、雙親和兄弟； 3.結(jié)點的層次 和樹的高度； 4.路徑和路徑長度； 5.有序樹和無序樹； 6.森林。49、樹的高度：空樹的高度為 0；在非空樹中，所有結(jié)點的最大層次稱為樹的高 度(或深度)。50、二叉樹的概念：二叉樹是一種重要的樹形結(jié)構(gòu)，在計算機領域有著十分廣 泛的應用。 任何一棵樹都可以轉(zhuǎn)換成一個與之對應的二叉樹， 從而對樹的表示與 處理便可用二叉樹的表示和相關運算來實現(xiàn)。二叉樹或為空樹， 或是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、 互不 相交的二叉樹組成。其特點是它是一棵有序樹，每個結(jié)點的度最大為 2。51 、滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點的度均為 2，且所有葉子結(jié)

18、 點在同一層上，則這棵二叉樹稱為滿二叉樹。52 、完全二叉樹：對滿二叉樹從樹根為 1 開始，按照從上到下、每層從左到右 的原則對其順序編號。滿二叉樹是完全二叉樹的特例。53、二叉樹的性質(zhì)：1.在二叉樹的第i層上至少有2i-1個結(jié)點（i>0 ）; 2深度為k的二叉樹上至多含2k-1個結(jié)點（k >1）; 3.對任何一棵非空二叉樹，如果它含 有no個葉子結(jié)點，n2個度為2的結(jié)點，那么：no= n2+1 ; 4.具有n個結(jié)點的完 全二叉樹的深度為 log 2n+1;5. 對有 n 個結(jié)點的完全二叉樹編號后，則對任意一 個編號為i的結(jié)點：a.若i=1，則該結(jié)點是二叉樹的根，無雙親；否則，其雙

19、親 結(jié)點編號為i/2結(jié)點;b.若2i>n ,貝U該結(jié)點無左孩子，否則，編號為2i的結(jié)點為 其左孩子結(jié)點；c.若2i+1>n，則該結(jié)點無右孩子結(jié)點，否則，編號為2i+1的結(jié)點為其右孩子結(jié)點。54、二叉樹的順序存儲結(jié)構(gòu)是用一組地址連續(xù)的存儲單元來存放二叉樹的數(shù)據(jù)55、二叉樹的鏈式存儲結(jié)構(gòu)：在鏈式存儲結(jié)構(gòu)中，結(jié)點之間的邏輯關系是通過 指針實現(xiàn)的。由于二叉樹中每個結(jié)點最多有兩個孩子結(jié)點， 所以每個結(jié)點結(jié)構(gòu)中， 除了數(shù)據(jù)域 data 外，還需要設置兩個指針域 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、圖是一種比線性表和樹更為復雜的非線性結(jié)構(gòu)。在圖中，數(shù)據(jù)元