數據結構考試重點.doc

數據結構第一章 緒論1、數據結構的定義：按照某種邏輯關系組織起來的數據集、數據與數據間的邏輯關系在計算機存儲器中的存儲形式以及定義在數據集上的一組操作與操作的實現這三個方面統(tǒng)稱為數據結構。2、數據主要分為兩大類：數值型數據和非數值類型數據。數值型數據主要包括整數、實數和復數等；非數值類型數據包括字符、字符串、文字、聲音、圖形、圖像等。3、數據結構的邏輯結構是指數據元素的集合以及定義在該集合上的數據元素之間的一種或多種特定關系。4、數據結構的邏輯結構是根據解決問題的功能目標而建立的； 數據結構的存儲結構是根據解決問題的性能要求而建立的。5、數據類型是一個具體相同性質的值的集合以及定義在該集合上的一組操作的總稱。數據類型定義了數據的性質、取值范圍以及對數據所能進行的一組操作。6、根據數據元素之間邏輯關系的不同特性，可將數據結構分為：集合、線性機構、樹形結構和圖狀結構。7、一個非空的線性結構的邏輯特點：1.只有一個數據元素沒有前驅，稱其為“第一個”元素；2.只有一個數據元素沒有后繼，稱其為“最后一個”元素；3.除第一個元素外，其余數據元素有且只有一個前驅；4. 除最后一個元素外，其余數據元素有且只有一個后繼。8、算法是指為解決一個問題而采用的方法和步驟；9、算法的五個特性：1.有窮性：算法必須在有限步驟及有限時間內終止，并計算出結果；2.確定性：算法的每一個操作步驟都有確切的含義，即無二義性；3. 算法的每一個操作步驟，都是有效的、可行的；4.輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定對象的集合；5.輸出：一個算法必須有一個或多個輸出。算法的目的是為了求解，通過算法所求得的“解”即是算法的輸出。注意，計算機算法的輸出不一定就是計算機顯示或打印輸出，一個算法得到的結果實際就是算法的輸出。第二章 線性表10、線性表是一種最基本而且應用最廣泛的數據結構，其特點是結構中的各數據元素之間存在著一對一的關系，是一種最典型的線性結構。11、線性表是具有相同特性的數據元素的一個有限序列。12、線性表中的數據元素在位置上是有序的，相鄰的元素之間存在著序偶關系。13、順序表的順序存儲結構是指把線性表中所有數據元素，按照其邏輯順序依次存儲到計算機存儲器中從指定位置開始的一塊連續(xù)的存儲空間中，數據元素間的存儲（物理）位置即表示了它的邏輯位置。14、順序表基本操作的實現：1.初始化操作；2.求長度操作；3.判空操作；4.清空操作；5.取元素操作；6.按值查找操作；7.插入操作；8.刪除操作。15、算法的空間效率是指算法在計算機上運行時所需存儲空間的大小。 算法的空間復雜度用大O記法表示為：S（n）=O（f（n） 隨著問題規(guī)模n的增大，算法運行時所需輔助存儲空間的增長率的數量級為f（n）。若算法運行時所占的存儲空間與問題規(guī)模無關，是個常量，則稱這種算法為原地工作，其空間復雜度用O（1）表示。16、順序表的優(yōu)缺點： 優(yōu)點：a.實現方法簡單，各種高級語言中都有數組，容易實現； b.訪問元素的速度快，因為在順序表中邏輯上相鄰的兩個元素在存儲位置上也必定相鄰，所以只要知道了第一個元素的地址，其他任何一個元素的地址都可通過簡單的計算求得，故可實現隨機存取，即順序表L的第i個元素即為L.basei-1。缺點：a.需占用連續(xù)的存儲區(qū)，存儲要求高，不能利用小塊存儲區(qū)； b.由于在順序表中邏輯上相鄰的兩個元素在存儲位置上也必定相鄰，所以在進行插入和刪除操作時，需要進行大量的元素移動操作，影響了算法效率。17、通常把使用鏈式存儲結構來實現的線性表稱為鏈表。18、線性表的鏈式存儲結構是用一組任意的存儲單元來存放線性表中的數據元素，這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至可以零散分布在內存中的任意位置上。19、鏈表的相關概念：1.首元結點，指鏈表中用于存儲線性表的第一各數據元素的結點；2.頭結點，在鏈表中為了便于進行插入和刪除等操作，為鏈表增設一個輔助結點，稱該輔助結點為鏈表的頭結點。頭結點在鏈表中可有可無；3.頭指針，是指向鏈表中第一個結點的指針，可以唯一地表示一個鏈表；4.空指針，當鏈表中某個結點的指針域為空時，稱該結點的指針域為空指針。20、鏈表的表長是指鏈表中存放數據元素的結點數目。21、鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表。22、單鏈表的建立操作：1.頭插法建立單鏈表：在單鏈表的建立過程中，總是將由讀入元素所生成的結點插入到鏈表的表首端，即插入時始終將新生成結點作為第1個結點插入。2.尾插法建立單鏈表：與頭插法正好相反，在單鏈表的建立過程中，其每次都是將所生成的新結點插入到單鏈表尾端，即在插入時始終是新生成結點作為最后一個結點插入。23、鏈表的優(yōu)缺點：優(yōu)點：a.能充分利用內存中的小塊存儲區(qū)； b.便于進行插入和刪除操作，在進行插入和刪除操作時不需要進行元素的移動，只需修改相應結點的指針域即可。缺點：a.與順序表相比，其實現方法較復雜，特別在對雙鏈表進行操作時不僅要考慮向后指向的“鏈”，還需考慮向前指向的“鏈”； b.無法像順序表那樣實現隨機存取，在鏈表中要找某個結點只能從表頭開始向后尋找； c.在鏈表的每個結點需要附加存儲關系信息（指針域），因此當問題規(guī)模較小且基本一定時，鏈表所需存儲空間比順序表多。第三章 棧與隊列24、棧的定義：棧是一種將插入操作與刪除操作限制在同一段進行的特殊線性表。在這個特殊的線性表中，進行插入與刪除操作的一端稱為棧頂（Top），另一端則稱為棧底（Bottom）。也就是說棧的插入操作與刪除操作均在棧頂端進行，其中，插入操作稱為入棧操作（Push），刪除操作稱為出棧操作（Pop）。不含任何元素的棧稱為空棧。25、棧具有后進先出或者說為先進后出的特性，故棧又稱為后進先出表或先進后出表。26、棧的基本操作：初始化、銷毀、判空、清空、入棧、出棧、取棧頂、求棧長及遍歷。27、經試探可行則行進，不可行則返回重新試探的方法稱為回溯法。28、一個概念、函數等對象用自己來定義自己，則稱該對象為遞歸定義的。在程序設計語言中，一個算法直接或間接調用自己，則稱該算法為遞歸算法。29、遞歸法則：1.基準情形法則。遞歸定義中的基準情形即遞歸出口，它本身不再使用遞歸定義，是遞歸的結束條件；2.不斷推進法則。不斷推進法則是指在遞歸求解過程中，每一次遞歸調用都必須使求解狀況朝接近基準情形的方向推進。30、隊列是一種插入操作限制在一端進行而刪除操作限制在另一端進行的特殊線性表。在這個特殊的線性表中進行插入操作的一端成為隊尾，進行刪除操作的一端稱為隊頭。在隊列尾端進行的插入操作稱為入隊操作，而在隊列頭端進行的刪除操作稱為出隊操作。不含任何元素的隊列稱為空隊。31、隊列具有先進先出或者說后進后出的重要特性，故隊列又稱為先進先出表或后進后出表。第四章 串32、串的定義：串是由零個或多個任意字符組成的有限序列，一般記作：S=“s1s2sisn”（n0）。其中S是串名，用雙引號括起來的字符序列為串值，但引號本身并不屬于串的內容，它的作用是為了避免與變量名或數的常量相混淆。Si（1in）稱為串的元素，它可以是任意字母、數字或者是其他字符，是構成串的基本單位，i是它在整個串中的序號。n為串的長度，表示串中所包含的字符個數。例如，串S1=“abcd”，串的元素為一個字母，其長度為5。而在串S2=“123456”，串的元素為一個數字，其長度為6。33、串的靜態(tài)順序存儲結構利用的是數組的靜態(tài)分配方式，它是為每個定義的字符串分配一個固定長度的連續(xù)存儲區(qū)域，將字符串中的字符順序地存放在存儲區(qū)域的各個單元里。實質上就是將串定義成字符數組，利用串名可以直接訪問串值。用這種表示方式，串的存儲空間在編譯時確定，其大小不能改變。34、串的動態(tài)順序存儲結構仍是為每個定義的字符串分配一個連續(xù)存儲區(qū)域，將字符串中的字符順序地存放在這組存儲區(qū)域中的各個單元里，只是這個存儲區(qū)域不是在操作前分配的固定長度的區(qū)域，而是在操作過程中根據需要動態(tài)分配得到的，即在程序運行時為每個產生的串分配一塊實際串長所需的存儲空間，若分配成功，則返回指向該存儲空間起始地址的指針，作為串的基址。第五章 數組和廣義表35、數組是n個相同數據類型的數據元素a0，a1，an-1構成的占用一塊地址連續(xù)的內存單元的有限序列。數組中任意一個元素可以用該元素在數組中的位置來表示，數組元素的位置通常稱作數組的下標。36、在大多數語言中采用以行序為主序的存儲方式，如C語言、C+語言和Pascal語言；在Fortran等少數語言中采用以列序為主序的存儲方式。37、常見的特殊矩陣：對稱矩陣、三角矩陣和帶狀矩陣。對稱矩陣：在一個n階方陣A中，若元素滿足下述興致：aij=aji（1i，jn），則稱A為n階對稱矩陣。三角矩陣：以主對角線劃分，n階三角矩陣有n階上三角矩陣和n階下三角矩陣兩種。n階上三角矩陣的下三角（不包括主對角線）中的元素均為常數c（或0）。n階下三角矩陣正好相反，它的主對角線上方均為常數c（或0）。帶狀矩陣：帶狀矩陣是指所有非零元素均集中在以對角線為中心的帶狀區(qū)域中的n階方陣。38、常見的稀疏矩陣存儲方法：三元組順序表和十字鏈表。39、三元組順序表：將表示稀疏矩陣非零元素的三元組按行優(yōu)先或列優(yōu)先（一般情況下為行優(yōu)先）的順序排列，并以此存儲在向量中，這種稀疏矩陣的順序存儲結構稱為三元組順序表。40、在廣義表中，每個結點既可以屬于基本數據類型，也可以屬于廣義表類型。41、廣義表的定義是一個遞歸定義，它和線性表之間的不同之處在于：數據元素之間不僅有先后關系，更有元素內部的層次關系。42、廣義表的長度是指表中數據元素的個數，需要注意的是數據元素可能是原子，也可能是子表；廣義表的深度是指表中層次關系的最大深度，即所含括弧的重數，需要注意：“原子”深度為0，“空表”的深度為1。43、廣義表的特性：1.廣義表是一個多層次的結構。表中元素可以是子表，子表的元素還可以是子表；2.廣義表可為其他廣義表所共享。在實際應用中，利用共享特性可以節(jié)約存儲空間來；3.廣義表可以是一個遞歸的表。遞歸表的深度是無窮值，長度則是有限值。44、廣義表的存儲形式：頭尾鏈表和擴展線性鏈表。第六章 樹45、樹形結構是一種典型的非線性結構，在形狀上類似于自然界中倒立的樹，所有元素之間具有明顯的層次關系和分支關系?，F實生活中，操作系統(tǒng)的文件管理、家族的族譜關系和社會機構的組成等都可以用樹形象地表示。46、樹是n（n0）個結點的有限集。若n=0，稱為空樹；否則，在任何一棵非空樹中滿足以下條件：1.有且僅有一個特定的沒有前驅的結點稱為根結點；2.當n1時，其余結點可分為m（m0）個互不相交的有限集合T1，T2，Tm。其中每個集合本身又是一棵樹，稱為根結點的子樹。47、樹的定義具有遞歸性，即樹的定義中還有樹。它刻畫了樹的固有特性：一棵非空子樹由一個根結點及若干子樹構成，而子樹又可以由其根結點和若干棵更小的子樹構成。48、樹的基本術語：1.結點的度和樹的度；2.孩子、雙親和兄弟；3.結點的層次和樹的高度；4.路徑和路徑長度；5.有序樹和無序樹；6.森林。49、樹的高度：空樹的高度為0；在非空樹中，所有結點的最大層次稱為樹的高度（或深度）。50、二叉樹的概念：二叉樹是一種重要的樹形結構，在計算機領域有著十分廣泛的應用。任何一棵樹都可以轉換成一個與之對應的二叉樹，從而對樹的表示與處理便可用二叉樹的表示和相關運算來實現。二叉樹或為空樹，或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。其特點是它是一棵有序樹，每個結點的度最大為2。51、滿二叉樹：在一棵二叉樹中，如果所有分支結點的度均為2，且所有葉子結點在同一層上，則這棵二叉樹稱為滿二叉樹。52、完全二叉樹：對滿二叉樹從樹根為1開始，按照從上到下、每層從左到右的原則對其順序編號。滿二叉樹是完全二叉樹的特例。53、二叉樹的性質：1.在二叉樹的第i層上至少有2i-1個結點（i0）；2.深度為k的二叉樹上至多含2k-1個結點（k1）；3.對任何一棵非空二叉樹，如果它含有n0個葉子結點，n2個度為2的結點，那么：n0= n2+1；4.具有n個結點的完全二叉樹的深度為log2n+1;5.對有n個結點的完全二叉樹編號后，則對任意一個編號為i的結點：a.若i=1，則該結點是二叉樹的根，無雙親；否則，其雙親結點編號為i/2結點;b.若2in，則該結點無左孩子，否則，編號為2i的結點為其左孩子結點；c.若2i+1n，則該結點無右孩子結點，否則，編號為2i+1的結點為其右孩子結點。54、二叉樹的順序存儲結構是用一組地址連續(xù)的存儲單元來存放二叉樹的數據元素。55、二叉樹的鏈式存儲結構：在鏈式存儲結構中，結點之間的邏輯關系是通過指針實現的。由于二叉樹中每個結點最多有兩個孩子結點，所以每個結點結構中，除了數據域data外，還需要設置兩個指針域LChild和RChild，分別指向左孩子和右孩子，這種存儲結構稱為二叉鏈表。56、二叉樹的二叉鏈表和三叉鏈表的特點：1.它們均由root唯一確定，如二叉樹為空，則root=NULL；2.具有n個結點的二叉鏈表，共有2n個指針域，其中具有n+1個空鏈域；3.在三叉鏈表中易于查找某個結點的雙親，而在二叉鏈表中則需要遍歷整棵樹才能查找某結點的雙親。57、二叉樹遍歷是按照一定的路徑訪問二叉樹中的每個結點，而且每個結點僅被訪問一次。58、DLR:先序遍歷；LDR:中序遍歷；LRD:后序遍歷。第七章 圖59、圖是一種比線性表和樹更為復雜的非線性結構。在圖中，數據元