數(shù)據(jù)結(jié)構(gòu)-Pascal

1、數(shù)據(jù)結(jié)構(gòu)-Pascal第一章什么是數(shù)據(jù)結(jié)構(gòu)通常由下列四類基本結(jié)構(gòu):（1） 集合：數(shù)據(jù)元素間的關(guān)系是同屬一個集合。（圖1）（2） 線性結(jié)構(gòu)：數(shù)據(jù)元素間存在一對一的關(guān)系。（圖2）（3） 樹形結(jié)構(gòu)：結(jié)構(gòu)中的元素間的關(guān)系是一對多的關(guān)系。（圖3）（4） 圖（網(wǎng)）狀結(jié)構(gòu)：結(jié)構(gòu)中的元素間的關(guān)系是多對多的關(guān)系。（圖4）1.單鏈表第二章線性表插入新元素:刪除元素循環(huán)鏈表第三章棧出桂校頂棧底入枝特殊的表先進后出1. 某個車站呈狹長形，寬度只能容下一臺車，并 且只有一個出入口。已知某時刻該車站狀態(tài)為 空，從這一時刻開始的出入記錄為：“進，出, 進，進，出，進，進，進，出，出，進，出。 假設(shè)車輛入站的順序為1, 2,

2、 3,，則車 輛出站的順序為（E ）。A. 1, 2, 3, 4, 5B. 1,2, 4, 5, 7C. 1, 3, 5,4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7第四章隊列特殊的表循環(huán)隊列：我們將隊列中從隊頭到隊尾的元素按順時針方向存放在循環(huán)數(shù)組中一段連續(xù)的單元中。當需要將新元素入隊時，可將隊尾游標Q.rear按順時針方向移一位，并在新的隊尾游標指示的單元中存入新元素。岀隊操作也很簡單，只要將隊頭游標 Q.front依順時針方向移一位即可。容易看岀, 用循環(huán)數(shù)組來實現(xiàn)隊列可以在0（1）時間內(nèi)完成 Enqueue和Dequeue運算。執(zhí)行一系列的入隊與岀隊運算

3、，將使整個隊列在循環(huán)數(shù)組中按順時針方向移動。通常，用隊尾游標 元素所在的單元，用隊頭游標 Q.front指向隊頭元素所在單元的前一個單元，maxsize-1 個元素如圖 3所示。Q.rear指向隊尾并且約定只能存放第五章樹和二叉樹樹的概念樹的遞歸定義如下：（1 ）至少有一個結(jié)點（稱為根）（2）其它是互不相交的子樹1. 度樹上任一結(jié)點所擁有的子樹的數(shù)目稱為該結(jié)點的度。入B的度為2, M的度為0。以組成該樹各結(jié)點中最大的度作為該樹的度，如上圖的樹，其度為3;樹中度為零的結(jié)點稱為葉結(jié)點或終端結(jié)點。樹中度不為零的結(jié)點稱為分枝結(jié)點或非終端結(jié)點。除根結(jié)點外的分枝結(jié)點統(tǒng)稱為內(nèi)部結(jié)點。2. 樹的深度一一組成該

4、樹各結(jié)點的最大層次，如上圖，其深度為4 ；3. 森林指若干棵互不相交的樹的集合，如上圖，去掉根結(jié)點A，其原來的二棵子樹 T1、T2、T3的集合T1,T2,T3就為森林；4. 有序樹指樹中同層結(jié)點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。二叉樹二叉樹是結(jié)點的有窮集合，它或者是空集，或者同時滿足下述兩個條件：(1)有且僅有一個稱為根的結(jié)點；(2)其余結(jié)點分為兩個互不相交的集合T1、T2、，T1和T2都是二叉樹，并且分別稱為根的 左子樹和右子樹。(1) 空二叉樹一一(a)；(2) 只有一個根結(jié)點的二叉樹一一(b);(3) 右子樹為空的二叉樹一一(c);(4) 左

5、子樹為空的二叉樹(d);(5) 完全二叉樹一一(e)(1) 完全二叉樹一一只有最下面的兩層結(jié)點度小于2，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置的二叉樹；(2) 滿二叉樹一一除了葉結(jié)點外每一個結(jié)點都有左右子女且葉結(jié)點都處在最底層的二叉樹完全二叉樹滿二叉樹二叉樹性質(zhì)：1、 在二叉樹中，第i層的結(jié)點總數(shù)不超過 2A(i-1);滿二叉樹為2A(i-1)2、深度為h的二叉樹最多有 2h-1個結(jié)點(h=1)，最少有h個結(jié)點；滿二叉樹為 2h-13、具有n個結(jié)點的完全二叉樹的深度為int (log2n) +1練習：1、滿二叉樹的葉結(jié)點個數(shù)為N，則它的結(jié)點總數(shù)為(C )。A. N B. 2 * N

6、C. 2 * N T D. 2 * N + 1 E.2n -12、二叉樹T,已知其前序遍歷序列為1 2 4 3 5 76,中序遍歷序列為4 2 1 5 7 3 6,則其后序遍歷 序列為(B )A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1C. 4 2 7 53 6 1 D. 4 7 2 3 5 6 1E. 4 5 2 6 3 7 15,乙13,則13(頂點的前后3、已知隊列(13, 2, 11, 34, 41, 77,18, 26, 15),第一個進入隊列的元素是 第五個出隊列的元素是(B )。A) 5 B) 41 C) 77 D)E) 186.二叉樹的遍歷運算(遞歸定義)(

7、1)先序遍歷訪問根；按先序遍歷左子樹；按先序遍歷右子樹(2 )中序遍歷按中序遍歷左子樹；訪問根；按中序遍歷右子樹(3)后序遍歷按后序遍歷左子樹；按后序遍歷右子樹；訪問根第六章圖概念圖是由頂點 V的集合和邊E的集合組成的二元組記 G=( V, E)如下圖是一無向圖 順序不限)V=V1,V2,V3,V4,V5E=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)下圖是一有向圖(頂點分先后順序)V=V1,V2,V3,V4E=,vV2,V4,vV1,V3,vV3,V4,vV4,V1完全圖(每一對不同的頂點都有一條邊相連,n個頂點的完全圖共有 n (n-1 ) /2條邊)頂點的度：與頂點關(guān)聯(lián)的邊的數(shù)目，有向圖中等于該頂點的入度與岀度之和。入度一一以該頂點為終點的邊的數(shù)目和出度以該頂點為起點的邊的數(shù)目和度數(shù)為奇數(shù)的頂點叫做奇點，度數(shù)為偶數(shù)的點叫做偶點。定理1圖G中所有頂點的度數(shù)之和等于邊數(shù)的2倍。因為計算頂點的度數(shù)時。每條邊均用到2次。定理2任意一個圖一定有偶數(shù)個奇點。練習：1、假設(shè)我們用d=(a1,a2,a5表示無向圖G的 5個頂點的度數(shù)，下面給出的哪(些)組 d值合 理(BE )。A) 5 ,4,