數(shù)據(jù)結(jié)構(gòu)老師給的復習要點

1、第一章1. 怎樣理解“算法+數(shù)據(jù)結(jié)構(gòu)=程序”這個公式？舉例說明。算法是語句序列解決特定問題的固有程序片段。數(shù)據(jù)結(jié)構(gòu)是確定數(shù)據(jù)間的關(guān)系。從具 體問題抽象出一個合適的數(shù)學模型、然后設(shè)計一個解決此數(shù)學模型的算法，最后編寫出程 序。尋求數(shù)學模型的是指就是數(shù)據(jù)結(jié)構(gòu)要完成的工作。參看書p1前兩段的描述。2. 數(shù)據(jù)結(jié)構(gòu)的概念，它包含哪三方面的內(nèi)容？數(shù)據(jù)結(jié)構(gòu)：是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間 餓關(guān)系和操作的學科。參看書p3包含三方面的內(nèi)容：1、數(shù)據(jù)之間的邏輯關(guān)系 2、數(shù)據(jù)在計算機中的存儲方式3、在數(shù)據(jù)上定義的運算的集合。3. 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項的基本概念。舉例說明數(shù)據(jù)元素和

2、數(shù)據(jù)項的聯(lián)系與區(qū)別。數(shù)據(jù)：描述客觀事物的數(shù)字、字符以及所有能直接輸入到計算機中并被計算機程序處 理的符號的集合。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮或處理。數(shù)據(jù)項：數(shù)據(jù)項是具有獨立含義的最小標識單位，是數(shù)據(jù)元的一個具體值，是數(shù) 據(jù)記錄中最基本的、不可分的有名數(shù)據(jù)單位。例 1 : class Aint c123;int i;；class BA a;B b ;b.a是數(shù)據(jù)項，B是數(shù)據(jù)元素例2: 本書的數(shù)目信息為一個數(shù)據(jù)元素，而數(shù)目信息中每一項（如書名、作者名等）為一 個數(shù)據(jù)項4. 從邏輯結(jié)構(gòu)來看，數(shù)據(jù)結(jié)構(gòu)有哪四種基本結(jié)構(gòu)，各自的特點是什么？1、集合（數(shù)據(jù)元素之間同屬于一

3、個集合，再無其他關(guān)系）2、線性結(jié)構(gòu)（數(shù)據(jù)元素之間存在一對一的關(guān)系）3、樹形結(jié)構(gòu)（數(shù)據(jù)元素之間一對多的關(guān)系）4、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)（數(shù)據(jù)元素之間多對多的關(guān)系）5. 從物理結(jié)構(gòu)來看，數(shù)據(jù)結(jié)構(gòu)有哪兩種基本結(jié)構(gòu)，各自的特點是什么？1、順序存儲結(jié)構(gòu)特點：借助元素在存儲器中的相應位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。2、鏈式存儲結(jié)構(gòu)特定：借助元素在存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。6. 算法的5個特征，4個評價標準是什么？ 特征:有窮性、確定性、可行性、輸入、輸出。評價標準：正確性、可讀性、健壯性、效率與低存儲量需求。7. 描述時間復雜度。(1)x=0; y=0; z=0;for (i=1; i<

4、;=n; i+) x+;for( j=1; jv=n; j+) y+;for( k=0; k<=(2*n); k+ )z+;程序片段中語句x=0、x+、y+、z+的時間復雜度和整段程序的時間復雜度。0(1)0(n)0(22)0(23)0(23)第二章線性表1. 描述線性結(jié)構(gòu)的特點。2. 判斷對錯，并解釋說明。線性表中的數(shù)據(jù)元素可以是各種各樣的，但同一線性表中的元素一定具有相同(1) 特性。線性表采用順序存儲表示時，必須占用一片連續(xù)的存儲單元。線性表采用鏈式存儲表示時，不能占用一片連續(xù)的存儲單元。101，每個元素的長度為3,計算出第6個元(2)(3)3. 順序表的第一個元素的存儲地址是 素

5、的存儲地址是多少？L0C ( a6) =LOC(a1)+5*L=101+5*3=1164. 長度為n的順序表中，在第i個元素前插入一個新元素時，需要移動多少個元素？ 插入算法的平均移動次數(shù)是多少，時間復雜度是什么？參看書P2425，需要移動n-i+1個兀素，平均移動次數(shù)為 n/2，時間復雜度是0(n)5. 長度為n的順序表中，將第i個元素刪除時，需要移動多少個元素？刪除算法的 平均移動次數(shù)是多少，時間復雜度是什么？參看書P2425,需要移動n-i個元素，平均移動次數(shù)為(n-1)/2 ,時間復雜度是0(n)6. 線性鏈表的存儲特點是？單鏈表中的結(jié)點由哪兩部分構(gòu)成，畫圖說明。7. 在一個單鏈表中，

6、q所指結(jié)點是P所指結(jié)點的直接前驅(qū)結(jié)點，若在q與P之間插入一個s所指的結(jié)點，寫出執(zhí)行的兩條語句(提示：先鏈接、后斷開)。s->next=p; q->next=s;或者 s->next=q->next; q->next=s;8. 在單鏈表中，w所指結(jié)點是s所指結(jié)點的直接前驅(qū)結(jié)點刪除s結(jié)點，寫出執(zhí)行的兩條語句。w->n ext=s->n ext;free(s)9. 畫圖說明單循環(huán)鏈表為空的狀態(tài)，并寫出循環(huán)鏈表判斷是否為空的語句。參看書P35圖2.12 ( b) 判空語句 H->next=H10. 雙向鏈表中，要在指針 q指向的結(jié)點后插入新結(jié)點t，寫出執(zhí)

7、行的四條語句。t->p rior=q ; t->n ext=q->n ext ; q->n ext=t ; t->n ext->p rior=s11. 雙向鏈表中，要刪除指針q的后繼結(jié)點，寫出執(zhí)行的兩條語句。T=q->next ; q->next=t->next ; free(t);或者 t=q->next;q->next-q->next->next;free(t)第三章棧和隊列1. 判斷對錯（1）棧和隊列是操作受限的線性表。（2）棧的插入操作只需要在表尾端進行，隊列的插入操作只需要在表頭進行。FRONT相關(guān)。（3）

8、棧的操作只和棧頂指針 TOP相關(guān)，隊列的操作只和隊頭指針2. 棧的特點是？隊列的特點是？（先進先出、先進后出中選擇） 棧的特點是先進后出（FILO）隊列的特點是先進先出（FIFO）3. 用文字描述算法。（參照我寫的（1）的算法描述完成）（1）順序存儲的棧插入操作 算法描述：（2）順序棧的刪除操作 算法描述：第一步，判斷棧是否為空，如果?？眨荒苓M行刪除操作；第二步，棧不空的時候，棧頂指針TOP減1，向下移動一位;第三步，將要刪除的棧頂元素用新變量保存；（3）鏈式存儲的隊列的插入操作 算法描述：第一步，禾U用指針創(chuàng)建新結(jié)點，新節(jié)點的數(shù)據(jù)域值為要入隊列的元素，新結(jié)點的指 針域復制為NULL ；第二

9、步，將鏈隊列的尾節(jié)點鏈接上新結(jié)點；第三步，修改鏈隊列的尾指針的指向，讓它指向新結(jié)點；（4）鏈棧的刪除操作 算法描述：第一步，禾U用指針創(chuàng)建新結(jié)點，新節(jié)點的數(shù)據(jù)域值為要入棧的元素，新結(jié)點的指針 域復制為NULL ；第二步，新結(jié)點的指針域指向鏈棧的頭結(jié)點；第三步，修改鏈棧的頭指針TOP的指向，讓它指向新結(jié)點；4.假設(shè)棧為S,寫出判斷語句typ edef struct sqstackint datamax;int top;sqstack ;s->t op= =0 s->t op = =maxsqstack *s ；（1）順序棧為空的條件判斷語句（2）順序棧為滿的條件判斷語句5. 假設(shè)隊列

10、為Q,寫出判斷語句typ edef struct SqQueueint dataMAX;int front;Front和隊尾指針 Rear*/Q->rear= =Q->fro nt(Q->rea r+1)%MAX= =Q->fro ntint rear; /*定義隊頭指針；SqQueue *Q(1) 循環(huán)隊列為空的條件判斷語句(2) 循環(huán)隊列為滿的條件判斷語句6. 總結(jié)說明，線性表的順序存儲與鏈式存儲的區(qū)別? 參看書P27第一段第六章樹和二叉樹1. 一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)，它含有雙親結(jié)點(4)個，單分支結(jié)點(2)個，葉子結(jié)點(3)個。e

11、只有左孩子f,二叉樹根為a； a有左孩子b,右孩子e； b有左孩子c,右孩子d； f只有右孩子g2. 判斷對錯K' , K''的長度(1) 在樹中，如果從結(jié)點 K出發(fā)，存在兩條分別到達 相等的路徑，則結(jié)點 K' , K''互為兄弟。，還可能是堂兄結(jié)點, 由完全二(2) 完全二叉樹的某結(jié)點若無左孩子，則必是葉結(jié)點。叉樹的性質(zhì)決定(3) 一棵完全二叉樹按層次遍歷的序列為ABCDEFGH I,則在 后序遍歷中結(jié)點B的直接后繼是F。由于是完全二叉樹，所以樹中第一層是A，第二層從左向右是 B和C,第三層是D、E、F、G,第四層從左向右是 H和I。畫出二叉樹

12、，進行后序遍歷，后序遍歷序列 為 HIDEBFGCA。二叉樹的后序遍歷序列中，任意一個結(jié)點均處在其子樹結(jié)點的后(4)面。后序遍歷算法決定的，左、右、根(5)由二叉樹結(jié)點的先根序列和后根序列可以唯一地確定一棵二叉樹。(6)結(jié)構(gòu)。(7)個結(jié)點都有不唯一，因為只有在中序遍歷中才能劃分左右子樹樹存儲時采用雙親表示法時，求某個結(jié)點的孩子時需要遍歷整個一棵有n ( n1)個結(jié)點的d叉樹，右用多重鏈表表示，樹中每 d個鏈域，則在樹的nd個鏈域中，有n ( d-1) +1個是空鏈域，只有n-1個是非空鏈域。根據(jù)樹的特性：一對多，每個結(jié)點都有且僅有一個雙親結(jié)點，除了根結(jié)點外。因此,n個結(jié)點的樹中有n-1個結(jié)點都

13、有且僅有一個雙親，這個關(guān)系表示在鏈式存儲里就一定 會占用它雙親的一個指針域，所以樹中一定有n-1個非空指針域，多叉樹也適用。(8)在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加2。解：二叉鏈表中有n個結(jié)點時，一定存在2n個指針域，n+1個空鏈域，則非空鏈域為n-1個，所以，空鏈域=非空鏈域+2（9）樹的后根遍歷序列等同于該樹對應的二叉樹的中序遍歷。P138筆記（10）樹利用孩子兄弟表示法轉(zhuǎn)換后的二叉樹中根結(jié)點一定不存在右子樹。 看書P137頁最后一句話，參看書，參3. 二叉樹根結(jié)點的層次為1,所有含有（4 ）°要想得出最小高度，必須是完全二叉樹才能保證， 結(jié)點的完全二叉樹的高

14、度是？參看二叉樹性質(zhì)4. 設(shè)一棵二叉樹結(jié)點的先根序列為則二叉樹中葉子結(jié)點是（E F H ）。參看書P154例題5. 樹的存儲結(jié)構(gòu)有幾種？分別是？二叉樹的存儲結(jié)構(gòu)有幾種，分別是？ 樹的存儲結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法二叉樹的存儲結(jié)構(gòu)有兩：順序存儲、鏈式存儲（又叫二叉鏈表的表示法） 在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（2）06. 若二叉樹有7個度為2的結(jié)點，試問有？個終端結(jié)點。由二叉樹的性質(zhì)3得出，n0=n2+1，所以度為1的終端結(jié)點有7+1=8個7. 一棵有124個葉結(jié)點的完全二叉樹，最多有？個結(jié)點。首先，由二叉樹的性質(zhì) 3得出，度為2的結(jié)點個數(shù)為124

15、-1=123個； 又根據(jù)二叉樹的定義可以得出這樣的結(jié)論：完全二叉樹的前n-1層8. 一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是？500解：設(shè)分支總數(shù)變量為b，則n=b+1 ,得出分支數(shù)為1000°分支數(shù)是偶數(shù)，所以不 存在度為1的結(jié)點，只有度為2的結(jié)點和葉子結(jié)點。根據(jù)性質(zhì)3, n0=n2+1,所以1001 =n0+n2= 2*n0+1 o n0=500。9. w=4,5,6,7,8，如何構(gòu)建哈夫曼樹？第9章查找查找表的概念？這是四種經(jīng)典數(shù)據(jù)結(jié)構(gòu)中的哪一種？靜態(tài)查找和動態(tài)查找有什么聯(lián)系和區(qū)別？查找表中的關(guān)鍵字是數(shù)據(jù)元素還是數(shù)據(jù)項，有什么特點？ASL表示什么？寫出計算的公式，

16、并解釋公式中每個變量的含義。描述順序查找的算法思想（用漢字描述，不是代碼） 描述折半查找的算法思想。給定由以下元素組成的關(guān)鍵字序列（55, 46, 89, 13, 24, 67, 23, 15）,將他15個結(jié)點的二叉樹中，最小高度是因此這個題目考核的是有 即可得出15個4，ABDECFGH ，中根序列為 DEBAFCHG ，1.2.3.4.5.6.7.們存儲在數(shù)組的第1位至第8位，現(xiàn)在要查找關(guān)鍵字為15和100的元素。描述查找過程。8. 畫出包含8個元素的查找表對應的折半判定樹。樹的深度為？9. 根據(jù)給定的序列（21,54,43,76,87,65,32），生成一棵二叉排序樹，并分析該二叉排序 樹的平均查找長度 ASL;同時根據(jù)該序列，生成一棵平衡二叉樹 ，并分析該平衡二叉樹 的平均查找長度ASL 0第10章排序1.比較分析9種排序方法的時間復雜度和穩(wěn)定性。排序方法平均時間最壞情況輔助空間穩(wěn)定性