大連理工數(shù)據(jù)結(jié)構(gòu)考試考點.

1、鍵入文檔標題鍵入文檔副標題 年黃薇Microsoft選取日期第一章一名詞解釋數(shù)據(jù)：是對客觀事物的客觀表示，在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素：構(gòu)成數(shù)據(jù)的基本單位。數(shù)據(jù)項：數(shù)據(jù)不可分割的最小單位。數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。二數(shù)據(jù)結(jié)構(gòu)的三個方面：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運算（操作）三抽象數(shù)據(jù)類型的定義是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)類型可用（D，S，P）三元組表示。其中：D 是數(shù)據(jù)對象； S 是 D 上的關(guān)系集； P 是對 D

2、的基本操作集。四算法的概念特性原則概念：解決某一特定問題的具體步驟的描述，是指令的有限序列。五大特性：有窮性，確定性，可行性，有零個或多個輸入，有一個或多個輸出。四大原則：正確性，可讀性，健壯性，高效率和低存儲量需求。五算法的時間復(fù)雜度 對足夠大的n，有以下順序 常見數(shù)量級第二章1、順序線性表與鏈式線性表的區(qū)別對線性表的操作主要有查找，插入和刪除三大類?；跁r間上的比較查找時，數(shù)組是可以隨機存取的，因此查找時間復(fù)雜度為O(1)，對于鏈表，每次查找都必須從鏈表的首結(jié)點開始，時間復(fù)雜度為O(n)，因此查找速率上，數(shù)組是優(yōu)于線性表的。插入和刪除時，數(shù)組必須首先采用順序查找的方式定位相應(yīng)的數(shù)據(jù)元素，接

3、下來還需要移動大量的數(shù)據(jù)元素，而鏈表在插入和刪除時，僅需要先定位數(shù)據(jù)元素，然后通過簡單的指針修改即可完成。這方面鏈表是優(yōu)于數(shù)組的。基于空間上的比較數(shù)組的存儲空間是預(yù)先靜態(tài)分配的，雖然在實現(xiàn)過程中可以動態(tài)拓展，但是如果線性表的長度變化范圍較大，空間在使用過程中會存在大量的閑置空間。鏈表的內(nèi)存主要被分配為兩部分，一部分存儲數(shù)據(jù)元素，另一部分則存儲指針域，因此在線性表數(shù)據(jù)元素結(jié)構(gòu)簡單，且長度變化不大時，可以考慮使用數(shù)組。2、鏈表的操作（插入、刪除）1 線性表操作ListInsert(&L, i, e)在單鏈表中的實現(xiàn)：O(ListLength(L)有序?qū)?lt;ai-1, ai>改變?yōu)?/p>

4、<ai-1, e>和<e, ai>因此，在單鏈表中第i 個結(jié)點之前進行插入的基本操作為:找到線性表中第i-1個結(jié)點，然后修改其指向后繼的指針。2 線性表的操作ListDelete (&L, i, &e)在鏈表中的實現(xiàn):O(ListLength(L)有序?qū)?lt;ai-1, ai>和<ai, ai+1>改變?yōu)?lt;ai-1, ai+1>在單鏈表中刪除第i 個結(jié)點的基本操作為:找到線性表中第i-1個結(jié)點p，修改其指向后繼的指針。3、鏈式結(jié)構(gòu)實現(xiàn)一元多項式一般情況下的一元稀疏多項式可寫成Pn(x) = p1xe1 + p2xe2 +

5、+ pmxem其中：pi 是指數(shù)為ei的項的非零系數(shù)，且 0 e1< e2 <<em = n可用下列線性表表示：（p1, e1）, (p2, e2), , (pm,em) ）例如:P999(x) = 7x3 - 2x12 - 8x999可用線性表( (7, 3), (-2, 12), (-8, 999) )表示第四章1、棧和隊列的特點通常稱，棧和隊列是限定只能在表的“端點”進行插入和刪除操作的線性表棧：插入和刪除操作均在“棧頂”進行隊列：插入和刪除操作分別在“隊頭”和“隊尾”進行2、棧的典型應(yīng)用例一、數(shù)制轉(zhuǎn)換例二、括號匹配的檢驗算法的設(shè)計思想：1）凡出現(xiàn)左括弧，則進棧；2）凡

6、出現(xiàn)右括弧，首先檢查棧是否空若?？?，則表明該“右括弧”多余，出錯否則和棧頂元素比較，若相匹配，則“左括弧出?！?，否則表明括號不匹配。3）表達式檢驗結(jié)束時，若?？眨瑒t表明表達式中匹配正確，否則表明“左括弧”有余，出錯。例三、行編輯程序問題思路：棧作為輸入緩沖區(qū)，每當從終端了接受一個字符之后先做如下判別：1：若是退格符#，從棧頂刪去一個元素，即出棧Pop；2：若是退行符，輸入緩沖區(qū)中的內(nèi)容回退一行字符。3：若不是#或，即為有效字符，將該字符入棧，即Push；例四、迷宮求解求迷宮路徑算法的基本思想是：若當前位置“可通”，則納入路徑，繼續(xù)前進; 若當前位置“不可通”，則后退，換方向繼續(xù)探索; 若四周“

7、均無通路”，則將當前位置從路徑中刪除出去。設(shè)定當前位置的初值為入口位置； do若當前位置可通，則將當前位置插入棧頂；若該位置是出口位置，則算法結(jié)束；否則切換當前位置的東鄰方塊為新的當前位置；否則 while (棧不空）；若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當前位置為: 沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則刪去棧頂位置；/ 從路徑中刪去該通道塊若棧不空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至?？眨蝗魲？眨瑒t表明迷宮沒有通路。3、棧和遞歸當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，需先完成三項任務(wù)：將所

8、有參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；為被調(diào)用函數(shù)的局部變量分配存儲區(qū)；將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項任務(wù)：保存被調(diào)函數(shù)的計算結(jié)果；釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)；依照被調(diào)函數(shù)保存的返回地址，將控制轉(zhuǎn)移到調(diào)用函數(shù)。多個函數(shù)嵌套調(diào)用的規(guī)則是：后調(diào)用先返回！此時的內(nèi)存管理實行“棧式管理”第五章1、數(shù)組及廣義表的概念數(shù)組特性：1. 可以將二維數(shù)組看成是一個定長的線性表，其中每一個數(shù)據(jù)元素也是一個定長的線性表。2. N維數(shù)組也可以看成是一個定長的線性表3. 當數(shù)組維數(shù)n=1，則數(shù)組退化為一個定長的線性表。廣義表是線性表的擴展（表中有表的線性表），也稱為列表（l

9、ists）。例如：X=(a, (b, c, (d)現(xiàn)實世界中的許多數(shù)據(jù)的結(jié)構(gòu)可以用廣義表來定義，例如數(shù)組。廣義表是遞歸定義的線性結(jié)構(gòu)，廣義表一般記作LS = ( a1, a2, ×××, an )，n是它的長度。2、矩陣的壓縮存儲特殊矩陣的壓縮存儲方法:一、對稱矩陣為每對對稱元素分配一個存儲空間二、對角矩陣只存儲其對角線上的元素。稀疏矩陣的壓縮存儲方法:一、 三元組順序表三元組順序表又稱有序的雙下標法。它的特點是：非零元在表中按行序有序存儲，每個非零元存儲的是行號、列號和元素值三項數(shù)據(jù)。二、 行邏輯聯(lián)接的順序表三元組順序表便于進行按行序處理的矩陣運算。然而，若需快

10、速存取某一行中的非零元，則需從頭開始進行查找。修改前述的稀疏矩陣的結(jié)構(gòu)定義，增加一個數(shù)據(jù)項rpos-各行第一個非零元的位置三、十字鏈表利用行邏輯鏈接的順序表表示稀疏矩陣，便于查找同一行中的非零元，但是不便于查找同一列中的非零元。十字鏈表：每一個非零元均有指向分別指向同一行和同一列中下一個非零元的指針，形成行、列兩個鏈表 - 十字鏈表。3、廣義表層次劃分廣義表是一個多層次的線性結(jié)構(gòu)1廣義表是遞歸定義的線性結(jié)構(gòu)， LS = ( a1, a2, ×××, an )其中：ai或為原子或為廣義表例如: A = ( ) - 空表 F = (d, (e) D = (a,(b,c

11、), F) C = (A, D, F) B = (a, B) = (a, (a, (a, ××× , ) ) )2 任何一個非空廣義表 LS = ( a1, a2, , an)均可分解為：表頭 Head(LS) = a1 和表尾 Tail(LS) = ( a2, , an) 兩部分。例如: D = ( E, F ) = (a, (b, c)，F(xiàn) )Head(D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) =

12、 ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )第六章1、樹及二叉樹的概念樹：非線性數(shù)據(jù)結(jié)構(gòu)，是n個結(jié)點的有限集。數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹；否則: (1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root； (2) 當n>1時，其余結(jié)點可分為m (m>0)個互不相交的有限集T1, T2, , Tm，其中每一個子集本身又是一棵符合本定義的樹，稱為根root的子樹。二叉樹：或為空樹，或是由一個根結(jié)點加上兩棵分別稱為左子樹

13、和右子樹的、互不交的二叉樹組成。2、二叉樹的重要特性性質(zhì) 1 ：在二叉樹的第 i 層上至多有2i-1 個結(jié)點。 (i1)性質(zhì) 2 ：深度為 k 的二叉樹上至多含 2 k-1 個結(jié)點（k1）。性質(zhì) 3 ：對任何一棵二叉樹，若它含有n0 個葉子結(jié)點、n2 個度為 2 的結(jié)點，則必存在關(guān)系式：n0 = n2+1。性質(zhì) 4 ：具有 n 個結(jié)點的完全二叉樹的深度為ë log2nû +1 。性質(zhì)5 ：若對含n 個結(jié)點的完全二叉樹從上到下且從左至右進行1至n的編號，則對于完全二叉樹中任意一個編號為i的結(jié)點：(1) 若i=1，則該結(jié)點是二叉樹的根，無雙親，否則，編號為ëi/2&#

14、251;的結(jié)點為其雙親結(jié)點；(2) 若2i>n，則該結(jié)點無左孩子，否則，編號為2i 的結(jié)點為其左孩子結(jié)點；(3) 若2i+1>n，則該結(jié)點無右孩子結(jié)點，否則，編號為2i+1 的結(jié)點為其右孩子結(jié)點。3、二叉樹的遍歷方式二、遍歷算法對“二叉樹”而言，可以有四種搜索路徑：先（根）序遍歷-波蘭式中（根）序遍歷-中綴表示后（根）序遍歷-逆波蘭式層序遍歷先序遍歷：A B C D E F中序遍歷：B C A D F E后序遍歷：C B F E D A層序遍歷：A B D C E F4、按給定的表達式建相應(yīng)二叉樹習(xí)題一：已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCH

15、KIJD，畫出此二叉樹。5、森林和二叉樹的對應(yīng)及轉(zhuǎn)換設(shè)森林 F = ( T1, T2, , Tn ); T1 = (root，t11, t12, , t1m);二叉樹 B =( LBT, Node(root), RBT );由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若F = ，則B = ；否則，由ROOT( T1 )對應(yīng)得到Node(root)；由(t11, t12, , t1m )對應(yīng)得到LBT；由(T2, T3, Tn)對應(yīng)得到RBT。由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：若B = ，則F = ；否則，由Node(root)對應(yīng)得到ROOT( T1)；由LBT對應(yīng)得到( t11, t12, ，t1m)；由

16、RBT對應(yīng)得到(T2, T3, , Tn)。由此，樹的各種操作均可對應(yīng)二叉樹的操作來完成。應(yīng)當注意的是，和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋鹤笫呛⒆樱沂切值堋?、構(gòu)造哈夫曼樹及編碼1 最優(yōu)二叉樹（哈夫曼樹）樹中結(jié)點的路徑長度定義為：從根結(jié)點到該結(jié)點的路徑上經(jīng)過的分支數(shù)目。樹的路徑長度定義為：樹中每個結(jié)點的路徑長度之和。樹的帶權(quán)路徑長度定義為：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和 WPL(T) = Swklk(對所有葉子結(jié)點)。帶權(quán)路徑長度最小的二叉樹稱為最優(yōu)二叉樹，簡稱為最優(yōu)樹或哈夫曼樹。2 如何構(gòu)造最優(yōu)樹赫夫曼算法(兩兩合并方法) ：(1)根據(jù)給定的n 個權(quán)值w1, w2, , w

17、n，構(gòu)造n 棵獨立的二叉樹的集合F = T1, T2, , Tn，其中每棵二叉樹中均只含一個帶權(quán)值為wi的根結(jié)點，其左、右子樹為空樹；(2)在F 中選取其根結(jié)點的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和；(3)從F中刪去這兩棵樹，同時加入剛生成的新樹；(4)重復(fù)(2)和(3)兩步，直至F 中只含一棵樹為止。(5)對樹中的分支進行編碼標注：如果某分支指向左子樹，則其編碼為0，否則為1；(6)產(chǎn)生所有葉子結(jié)點的編碼：每個葉子結(jié)點的編碼為：從根結(jié)點到該葉子結(jié)點的路徑上所有分支的編碼的串聯(lián)（二進制編碼）。第七章1、圖的概

18、念圖的結(jié)構(gòu)定義:圖是由一個頂點集V 和一個弧集VR構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。 Graph = (V , VR )其中，VR<v,w> | v,wV 且P(v,w)<v,w>表示從v 到w 的一條弧，并稱v 為弧尾，w 為弧頭。謂詞 P(v,w) 定義了弧<v,w>的意義或信息。由于“弧”是有方向的，因此稱由頂點集和弧集構(gòu)成的圖為有向圖。2、圖的存儲及遍歷一、圖的數(shù)組(鄰接矩陣)存儲表示有向圖的鄰接矩陣一般為非對稱矩陣無向圖的鄰接矩陣一定是對稱矩陣二、圖的（逆）鄰接表存儲表示三、 有向圖的十字鏈表存儲表示四、無向圖的鄰接多重表存儲表示typedefstructEbox

19、/VisitIf mark; / 訪問標記，用于遍歷intivex, jvex; /該邊依附的兩個頂點的位置structEBox*ilink, *jlink; /指向下一條依附于ivex/ jvex的邊InfoType*info; / 該邊信息指針EBox;3、圖的最小生成樹算法，兩種算法的比較該問題等價于： 構(gòu)造網(wǎng)的一棵最小（代價）生成樹，即：在 e 條帶權(quán)的邊中選取 n-1 條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法一：（普里姆算法） 算法二：（克魯斯卡爾算法） 普里姆（Prim）算法的基本思想: 取圖G=(V, E)中任意一個頂點 v 作為生成樹的根（U=v)，之后往生成樹上添加新的

20、頂點 w。在添加的頂點 w （wÎV-U）和已經(jīng)在生成樹上的頂點v （vÎU） 之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點 v 和 w 之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點，直至生成樹上含有 n-1 個頂點為止?？唆斔箍枺↘ruskal）算法的基本思想：考慮問題的出發(fā)點: 為使生成樹上邊的權(quán)值之和達到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小，但不能出現(xiàn)回路。具體做法:首先構(gòu)造一個只含 n 個頂點的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇不使森林中產(chǎn)生回路的邊加入到森林中去，直至該森林變成一棵樹為止，這棵樹便是連通網(wǎng)的最小生成樹。4、圖中兩點最短路徑（源點到任意頂點）迪杰斯特拉算法： 設(shè)置輔助數(shù)組Dist，其中每個分量Distk 表示當前所求得的從源點