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

1、數(shù)據(jù)結(jié)構(gòu)第一章 緒論1、數(shù)據(jù)結(jié)構(gòu)的定義：按照某種邏輯關(guān)系組織起來的數(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ù)主要分為兩大類：數(shù)值型數(shù)據(jù)和非數(shù)值類型數(shù)據(jù)。數(shù)值型數(shù)據(jù)主要包括 整數(shù)、實(shí)數(shù)和復(fù)數(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ù)解決問題的功能目標(biāo)而建立的； 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)是根據(jù)解決問題的性能要求而建立的。5、數(shù)據(jù)類型是一個(gè)具體相同性質(zhì)的值的集合以及定義在

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

3、每一個(gè)操作步驟都有確切的含義，即無二義性；3.算法的每一個(gè)操作步驟，都是有效的、可行的； 4.輸入：一個(gè)算法有零個(gè)或多個(gè) 輸入，這些輸入取自于某個(gè)特定對(duì)象的集合； 5. 輸出：一個(gè)算法必須有一個(gè)或多 個(gè)輸出。算法的目的是為了求解，通過算法所求得的“解”即是算法的輸出。注 意，計(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è)有限序列。12 、線性表中的數(shù)據(jù)元素在位置上是有

4、序的，相鄰的元素之間存在著序偶關(guān)系。13 、順序表的順序存儲(chǔ)結(jié)構(gòu)是指把線性表中所有數(shù)據(jù)元素，按照其邏輯順序依 次存儲(chǔ)到計(jì)算機(jī)存儲(chǔ)器中從指定位置開始的一塊連續(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ù)雜度用大 O 記法表示為： S（n）=O （f（n） 隨著問題規(guī)模 n 的增大，算法運(yùn)行時(shí)所需輔助存儲(chǔ)空間的增長(zhǎng)率的數(shù)量級(jí)為

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

6、要進(jìn)行大量的元素移動(dòng)操作， 影響了算法效率。17、通常把使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來實(shí)現(xiàn)的線性表稱為鏈表。18、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來存放線性表中的數(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)在鏈表中可有可無； 3.頭指針， 是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，可以唯一地表示一個(gè)鏈表； 4. 空指針，當(dāng)鏈表 中某個(gè)結(jié)點(diǎn)的指針域?yàn)榭?/p>

7、時(shí)，稱該結(jié)點(diǎn)的指針域?yàn)榭罩羔槨?0 、鏈表的表長(zhǎng)是指鏈表中存放數(shù)據(jù)元素的結(jié)點(diǎn)數(shù)目。21 、鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表。22 、單鏈表的建立操作：1. 頭插法建立單鏈表：在單鏈表的建立過程中，總是將由讀入元素所生成的 結(jié)點(diǎn)插入到鏈表的表首端，即插入時(shí)始終將新生成結(jié)點(diǎn)作為第 1 個(gè)結(jié)點(diǎn)插入。2. 尾插法建立單鏈表：與頭插法正好相反，在單鏈表的建立過程中，其每次 都是將所生成的新結(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)行插入和刪除操作，在進(jìn)行插入和刪除操作時(shí)不需要進(jìn)行元 素的移動(dòng)，只需修

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

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

10、推進(jìn)法則是指在遞 歸求解過程中，每一次遞歸調(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)先出或者說后進(jìn)后出的重要特性，故隊(duì)列又稱為先進(jìn)先出表 或后進(jìn)后出表。第四章 串32 、串的定義：串是由零個(gè)或多個(gè)任意字符組成的有限序列，一般記作：S=“s1s2sisn” (n X)。其中S是串名，用雙引號(hào)括起來的字符

11、序列為串值， 但引號(hào)本身并不屬于串的內(nèi)容，它的作用是為了避免與變量名或數(shù)的常量相混 淆。Si (1 <i<n)稱為串的元素，它可以是任意字母、數(shù)字或者是其他字符，是 構(gòu)成串的基本單位， i 是它在整個(gè)串中的序號(hào)。 n 為串的長(zhǎng)度，表示串中所包含 的字符個(gè)數(shù)。例如，串 S1= “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ū)域， 將字符串中的字符順序地存放在存儲(chǔ) 區(qū)域的各個(gè)單元里。 實(shí)質(zhì)上就是將串定義成字符

12、數(shù)組， 利用串名可以直接訪問串 值。用這種表示方式，串的存儲(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ū)域， 而是在操作過程中根據(jù)需要?jiǎng)討B(tài)分配得 到的，即在程序運(yùn)行時(shí)為每個(gè)產(chǎn)生的串分配一塊實(shí)際串長(zhǎng)所需的存儲(chǔ)空間， 若分 配成功，則返回指向該存儲(chǔ)空間起始地址的指針，作為串的基址。第五章 數(shù)組和廣義表35、 數(shù)組是n個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素 a0 , al,，an-1構(gòu)成的占用一塊 地址連續(xù)的內(nèi)存單元的有限序列。 數(shù)組中任意一個(gè)元

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

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

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

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

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

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

19、親 結(jié)點(diǎn)編號(hào)為i/2結(jié)點(diǎn);b.若2i>n ,貝U該結(jié)點(diǎn)無左孩子，否則，編號(hào)為2i的結(jié)點(diǎn)為 其左孩子結(jié)點(diǎn)；c.若2i+1>n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。54、二叉樹的順序存儲(chǔ)結(jié)構(gòu)是用一組地址連續(xù)的存儲(chǔ)單元來存放二叉樹的數(shù)據(jù)55、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)之間的邏輯關(guān)系是通過 指針實(shí)現(xiàn)的。由于二叉樹中每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)， 所以每個(gè)結(jié)點(diǎn)結(jié)構(gòu)中， 除了數(shù)據(jù)域 data 外，還需要設(shè)置兩個(gè)指針域 LChild 和 RChild ，分別指向左孩 子和右孩子，這種存儲(chǔ)結(jié)構(gòu)稱為二叉鏈表。56、 二叉樹的二叉鏈表和三叉鏈表的特點(diǎn)：1.它們均由 root 唯一確定，如二叉 樹為空，則 root=NULL ； 2.具有 n 個(gè)結(jié)點(diǎn)的二叉鏈表，共有 2n 個(gè)指針域，其 中具有 n+1 個(gè)空鏈域； 3.在三叉鏈表中易于查找某個(gè)結(jié)點(diǎn)的雙親，而在二叉鏈 表中則需要遍歷整棵樹才能查找某結(jié)點(diǎn)的雙親。57、二叉樹遍歷是按照一定的路徑訪問二叉樹中的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅 被訪問一次。58、DLR:先序遍歷；LDR:中序遍歷；LRD:后序遍歷。第七章 圖59、圖是一種比線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。在圖中，數(shù)據(jù)元