數(shù)據(jù)結(jié)構(gòu)c語言版復(fù)習(xí)資料

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 一、填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 操作對象 以及它們之間的 關(guān)系 和運(yùn)算等的學(xué)科。2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是 數(shù)據(jù)元素 的有限集合，R是D上的 關(guān)系 有限集合。3. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 這三個(gè)方面的內(nèi)容。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。5. 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。6 在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；最后

2、一個(gè)結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。7. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè) 。8. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意多個(gè) 。9數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序 、 鏈?zhǔn)?、 索引 和 散列 。10. 數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。11. 一個(gè)算法的效率可分為 時(shí)間 效率和 空間 效率。12. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與 表

3、長和該元素在表中的位置 有關(guān)。13. 線性表中結(jié)點(diǎn)的集合是 有限 的，結(jié)點(diǎn)間的關(guān)系是 一對一 的。14. 向一個(gè)長度為n的向量的第i個(gè)元素(1in+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng) n-i+1 個(gè)元素。15. 向一個(gè)長度為n的向量中刪除第i個(gè)元素(1in)時(shí)，需向前移動(dòng) n-i 個(gè)元素。16. 在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 O(1) ，因此，順序表也稱為 隨機(jī)存取 的數(shù)據(jù)結(jié)構(gòu)。17. 順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。18在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值 指示。19 在n個(gè)結(jié)點(diǎn)

4、的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為O（n）。20. 向量、棧和隊(duì)列都是 線性 結(jié)構(gòu)，可以在向量的 任何 位置插入和刪除元素；對于棧只能在 棧頂 插入和刪除元素；對于隊(duì)列只能在 隊(duì)尾 插入和 隊(duì)首 刪除元素。21. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 棧頂 。不允許插入和刪除運(yùn)算的一端稱為 棧底 。22. 隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。23. 不包含任何字符（長度為0）的串 稱為空串； 由一個(gè)或多個(gè)空格（僅由空格符）組成的串 稱為空白串。24. 子串的定位運(yùn)算稱為串的模式匹配； 被匹配的主串 稱為

5、目標(biāo)串， 子串 稱為模式。25. 假設(shè)有二維數(shù)組A68，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A的體積（存儲(chǔ)量）為 288 B ；末尾元素A57的第一個(gè)字節(jié)地址為 1282 ；若按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為 (8+4)6+1000=1072 ；若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為 (674)61000）1276 。26 由個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有 5 種形態(tài)。 27. 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個(gè)分支結(jié)點(diǎn)和 26-1 =32 個(gè)葉子。注：滿二叉樹沒有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就

6、是二度結(jié)點(diǎn)數(shù)。28 一棵具有個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為 9 。（ 注：用 log2(n) +1= 8.xx +1=929設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有 350 個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)n/2350 30 設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有 500 個(gè)葉子結(jié)點(diǎn)，有 499 個(gè)度為2的結(jié)點(diǎn)，有 1 個(gè)結(jié)點(diǎn)只有非空左子樹，有 0 個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)n/2500 ，n2=n0-1=499。 另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左子樹。完全二叉樹的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹數(shù)0.31在數(shù)據(jù)的

7、存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是 順序查找（線性查找） 。32. 線性有序表（a1，a2，a3，a256)是從小到大排列的，對一個(gè)給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索 8 次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是 7 。33. 假設(shè)在有序線性表a20上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為 2 ；比較四次查找成功的結(jié)點(diǎn)數(shù)為 8 ；平均查找長度為 3.7 。解：顯然，平均查找長度O（log2n）top0 ST-top=0 ST-topm0 ST-top=m0（ C ）18. 在一個(gè)圖中，所有頂點(diǎn)的

8、度數(shù)之和等于圖的邊數(shù)的 倍。 A1/2 B. 1 C. 2 D. 4 （ B ）19. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。 A1/2 B. 1 C. 2 D. 4 （ B ）20. 有8個(gè)結(jié)點(diǎn)的無向圖最多有 條邊。 A14 B. 28 C. 56 D. 112 （ C ）21. 有8個(gè)結(jié)點(diǎn)的有向完全圖有 條邊。 A14 B. 28 C. 56 D. 112 （ B ）22在表長為的鏈表中進(jìn)行線性查找，它的平均查找長度為. ; . （）; . ; . （）（ A ）23折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則

9、它將依次與表中 比較大小，查找結(jié)果是失敗。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50（ C ）24對22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較 次關(guān)鍵字。A3 B4 C5 D 6（ A ）25. 鏈表適用于 查找A順序 B二分法 C順序，也能二分法 D隨機(jī)四、簡答題1.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？答：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。2. 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對一的，非線性結(jié)構(gòu)反映結(jié)

10、點(diǎn)間的邏輯關(guān)系是多對多的。3、分析下面各程序段的時(shí)間復(fù)雜度(1.) for (i=0; in; i+)for (j=0; jm; j+)Aij=0;答：O（m*n）1. 項(xiàng)基本原則(2.) x=0;for(i=1; in; i+) for (j=1; j=0是DIJISTRU算法的適應(yīng)范圍）。對無向圖，可看成2個(gè)方向權(quán)值一樣。例子見手寫版。問：DIJISTRU算法能否求圖的最小生成樹？不能。打印最短路徑，時(shí)間O（n2），空間O（n），可以用DIJISTRU算法得到集合的同時(shí)，記錄每個(gè)節(jié)點(diǎn)前面那個(gè)元素，一個(gè)一個(gè)向前找。二部圖：一個(gè)圖是否是二部圖？時(shí)間是O（n）。用等價(jià)類：一個(gè)邊的兩點(diǎn)分屬于不用等

11、價(jià)類（估計(jì)不會(huì)考太深）?；锇橄到y(tǒng)，邊界標(biāo)識（要看）。無用單元收集不考。順序查找時(shí)間（最壞，平均）。有序表查找，二分查找，折半查找（判定樹，樹的高度，平均檢索長度（在成功和不成功時(shí)的不同情況）。靜態(tài)樹表不考，靜態(tài)次優(yōu)不考。索引順序表：概念。動(dòng)態(tài)查找：二叉排序樹：中序遍歷有序，先序無序。給出先（或后）序的次序，寫出此樹（因?yàn)橹行蚴琼樞虻模阎?。他的插入和刪除（刪除不一定考）。給定樹，求平均查找長度。查找長度的量級。平衡二叉樹：一定是二叉排序樹。樹的所有子樹都是平衡二叉樹。反之不成立。若要執(zhí)行4種旋轉(zhuǎn)，至少7個(gè)節(jié)點(diǎn)。M階B樹：關(guān)鍵字個(gè)數(shù)的上下限。N個(gè)關(guān)鍵字構(gòu)成樹的節(jié)點(diǎn)數(shù)目層數(shù)。B樹的概念。鍵樹。哈

12、希表：解決沖突的方法。只有鏈地址法可以解決二次聚集。不是同義詞不會(huì)競爭同一位置。鏈地址法是順序結(jié)構(gòu)和鏈結(jié)構(gòu)的完美結(jié)合。查找長度：1。探測次數(shù)（包括最后一次比較為空的次數(shù)）。 2關(guān)鍵字比較次數(shù)（不包括最后一次為空的）。37內(nèi)部排序：簡單插入排序（穩(wěn)定）；折半（不穩(wěn)定）；希爾（不穩(wěn)定）；冒泡（穩(wěn)定）；快速（不穩(wěn)定）；選擇（不穩(wěn)定）；堆（不穩(wěn)定）；歸并（穩(wěn)定）。要記住她們的時(shí)間復(fù)雜度（最好，平均，最壞）。基數(shù)排序：給定N個(gè)數(shù)，范圍在（0，n2-1），以O(shè)(n)時(shí)間排序。記ni=ai*n+bi，按(ai,bi)先以bi為基數(shù)排序，再以ai 排?；鶖?shù)排序利用關(guān)鍵字本身的值，而其他基于比較。找最大和最小值

13、的時(shí)間3/2n-2。見手寫版。兩兩比較，小的方一個(gè)數(shù)組，大的放一個(gè)數(shù)組，再找。找最大和次大值：可以調(diào)整堆，也可以記下比較第一章一、數(shù)據(jù)結(jié)構(gòu)的四類基本類型：1、集合2、線性結(jié)構(gòu)3、樹形結(jié)構(gòu)4、圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)二、數(shù)據(jù)元素之間的物理結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)三、算法中基本操作重復(fù)的次數(shù)是問題規(guī)模N的某個(gè)函數(shù)F（N）算法的時(shí)間量度記作T（N）O（F（N）它表示隨問題規(guī)模N的增大，算法執(zhí)行的時(shí)間的增長率和F（N）的增長率相同，稱作算法的漸近時(shí)間復(fù)雜度簡稱時(shí)間復(fù)雜度。第二章線性表一、線性表的建立：1、建立一個(gè)線性鏈表：2、插入一個(gè)結(jié)點(diǎn)：在頭部：在中間：在尾部：3、刪除一個(gè)結(jié)點(diǎn)：頭部中間尾部

14、二、線性鏈表原代碼如下： include typedefstruct node int data; struct node *next;NODE1、建立一個(gè)線性鏈表：create_list( )NODE *head,*p; int i,j,k; scanf(“%d”,&i); /鏈表的結(jié)點(diǎn)個(gè)數(shù) head=NULL; for(j=i;i!=0;i-) scanf(“%d”,&k); if(head=NULL) head-data=k; p=head;p-next-data=k;p=p-next;p-next=NULL;return(head); 2、插入一個(gè)結(jié)點(diǎn)： 在頭部插入一個(gè)結(jié)點(diǎn)p ： in

15、sert(NODE*head) NODE *p ; scanf(“%d”,&p-data)； /要插入的結(jié)點(diǎn) p-next=head; head=p; 在p與q之間插入結(jié)點(diǎn)k：insert(NODE * head) NODE *p,*q,*k; scanf(“%d”,&k-data)； /要插入的結(jié)點(diǎn) k-next=q; p-next=k; 在尾部插入一個(gè)結(jié)點(diǎn)q ： insert(NODE *head) NODE *p,*q; scanf(“%d”,&q-data)； /要插入的結(jié)點(diǎn) for(p=head;p-next!=NULL;p=p-next); /到鏈表的最后一個(gè)結(jié)點(diǎn) p-next=q

16、; q-next=NULL; 3、刪除一個(gè)結(jié)點(diǎn)：在頭部刪除一個(gè)結(jié)點(diǎn)p: delete(NODE*head)NODE *p;p=head; head=head-next;free(p); 在p與q之間刪除結(jié)點(diǎn)k： delete(NODE*head) NODE *p,*q,*k; p-next=q; free(k); 在尾部刪除一個(gè)結(jié)點(diǎn)p: delete(NODE*head) NODE *p,*q; for(q=p=head;p-next!=NULL;q=p,p=p-next); /到鏈表的最后一個(gè)結(jié)點(diǎn) q-next=NULL; free(p);雙向鏈表的操作與單向差不多。第三章棧和隊(duì)列一、棧是一

17、種先進(jìn)后出的線性表進(jìn)棧相當(dāng)于在線性鏈表的頭部插一個(gè)結(jié)點(diǎn)，出棧相當(dāng)于在線性鏈表的頭部刪除一個(gè)結(jié)點(diǎn)二、隊(duì)列是一種和棧相反的線性表，它是先進(jìn)先出線性表進(jìn)隊(duì)相當(dāng)于是在線性表的尾部加一結(jié)點(diǎn)，出隊(duì)相當(dāng)于在線性鏈表的頭部刪除一個(gè)結(jié)點(diǎn)三、判斷循環(huán)隊(duì)列的空滿可以用以下兩種方法：一是另設(shè)一個(gè)標(biāo)志位區(qū)別隊(duì)列是空是滿二是少用一個(gè)元素空間，約定頭指針在隊(duì)列尾指針的下一位置上作為隊(duì)滿第四章串一、串的機(jī)內(nèi)表示：定長順序存儲(chǔ)表示和堆分配存儲(chǔ)表示，兩者的思想和區(qū)別二、定長順序存儲(chǔ)表示思想是類似于線性表的順序存儲(chǔ)結(jié)構(gòu)，用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列。三、堆分配存儲(chǔ)表示思想是仍以一組地址連續(xù)的存儲(chǔ)單元存放串值字符序列，

18、但它們的存儲(chǔ)空間是程序執(zhí)行過程中動(dòng)態(tài)分配而得。四、兩者區(qū)別是：定長順序存儲(chǔ)是每個(gè)定義的串變量是分配一個(gè)固定的長度而堆分配存儲(chǔ)是程序執(zhí)行過程中動(dòng)態(tài)分配而得。 串的模式匹配算法：P79第五章：數(shù)組和廣義表一、疏矩陣的存儲(chǔ)方法1、三元組順序表： 壓縮存儲(chǔ)的概念就是只存儲(chǔ)稀疏矩陣的非零元。所以一個(gè)三元組（i,j, aij）就可以唯一確定了矩陣的一個(gè)非零元。其中i 表示該非零元在稀疏矩陣中的第幾行，j 表示非零元在稀疏矩陣中的第幾列，aij表示非零元在稀疏矩陣中的值?？焖俎D(zhuǎn)置的好處缺點(diǎn)原因二、十字鏈表：在鏈表中，每個(gè)非零元可以用一個(gè)含有五個(gè)域的結(jié)點(diǎn)表示，其是I,j,e三個(gè)域分別表示該非零元所在行、列、和

19、非元零的值，向 右域right用以鏈接同一行下個(gè)非零元，用down用以鏈接同列中下一個(gè)非零元，同一行非零元可以通過right域鏈成一個(gè)鏈表，同一列可以通過 down域鏈成一個(gè)鏈表，每個(gè)非零元既是某行鏈表中的結(jié)點(diǎn)，又是某個(gè)列鏈表的結(jié)點(diǎn)整個(gè)矩陣就成了一個(gè)十字交叉的鏈表故稱十字鏈表，可以用兩個(gè)分別存儲(chǔ)行鏈 表的頭指針的列鏈表的頭指針的一維數(shù)組表示之：矩陣： 0 0 1 01312 0 0 4 0 3 5 03353232122441、廣義表的存儲(chǔ)結(jié)構(gòu)廣義表LS=（a1,a2,a3an）表頭是第一個(gè)元素a1，其余元素組成的表（a2,a3,an）是LS的表尾第六章 樹和二叉樹一、二叉的性質(zhì)：1、在二叉樹

20、的第I層上至多有2I-1個(gè)結(jié)點(diǎn)（I1） 2、深度為K的二叉樹至多有2K1個(gè)結(jié)點(diǎn) 3、對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)不N0，度為2的結(jié)點(diǎn)數(shù)為N 2則N0N21 4、具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度為LLOG2N1二、滿二叉樹的定義：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為三、完全二叉樹定義：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度k的滿二叉樹中編號從1到n的結(jié)點(diǎn)一一對應(yīng)時(shí)稱之為完全二叉樹四、二叉樹的存儲(chǔ)結(jié)構(gòu)：一、順序存儲(chǔ)結(jié)構(gòu)二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)五、遍歷二叉樹：1、前序：是先訪問根結(jié)點(diǎn)，先序遍歷左子樹，先序遍歷右子樹2、中序：中序遍歷左子樹，訪問根結(jié)點(diǎn)，中序遍歷右子樹3、后序

21、：后序遍歷左子樹，后序遍歷右子樹，訪問根結(jié)點(diǎn)例：見書p129頁六、建立一棵二叉樹：p131七、線索二叉樹：穿線方法：先按先、中或后序把二叉樹遍歷，八、樹的存儲(chǔ)結(jié)構(gòu)：一、雙親表示法：就是用一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親的結(jié)點(diǎn)在數(shù)組中位置。特點(diǎn)：找雙親容易，找孩子難（見p135 圖6.13）二、孩子兄弟表示法（又稱二叉樹和二叉鏈表表示法）鏈表結(jié)構(gòu)中的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。操作容易，破壞了樹的層次（見p137 圖6.15）九、森林的遍歷：1、先根（序）遍歷：先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹2、后根（序）遍歷：先依次

22、后根遍歷每棵子樹，然后訪問根結(jié)點(diǎn)十、森林和二叉樹的轉(zhuǎn)換：十一、最優(yōu)二叉樹（赫夫曼樹）是一類帶權(quán)路徑長度最短的樹建立構(gòu)造Huffman樹的方法Huffman算法構(gòu)造Huffman樹步驟1、根據(jù)給定的n個(gè)權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹，令起權(quán)值為wj2、在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點(diǎn)權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和3、在森林中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入森林中4、重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹第七章 圖一、圖的定義和術(shù)語：1、圖(Graph)圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E)

23、其中：V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)?、有向圖有向圖G是由兩個(gè)集合V(G)和E(G)組成的其中：V(G)是頂點(diǎn)的非空有限集E(G)是有向邊（也稱?。┑挠邢藜?，弧是頂點(diǎn)的有序?qū)?，記為，v,w是頂點(diǎn)，v為弧尾，w為弧頭3、無向圖無向圖G是由兩個(gè)集合V(G)和E(G)組成的其中：V(G)是頂點(diǎn)的非空有限集E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)?，記為（v,w）或（w,v），并且（v,w）=(w,v)4、有向完備圖n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)5、無向完備圖n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/26、權(quán)與圖的邊或弧相關(guān)的數(shù)叫7、網(wǎng)帶權(quán)的圖叫8、

24、子圖如果圖G(V,E)和圖G(V,E),滿足：v則稱G為G的子圖9、頂點(diǎn)的度1、無向圖中，頂點(diǎn)的度為與每個(gè)頂點(diǎn)相連的邊數(shù)2、有向圖中，頂點(diǎn)的度分成入度與出度入度：以該頂點(diǎn)為頭的弧的數(shù)目出度：以該頂點(diǎn)為尾的弧的數(shù)目10、路徑路徑是頂點(diǎn)的序列V=Vi0,Vi1,Vin，滿足(Vij-1,Vij)E 或 E,(1 V2-V4 - V8 -V5 -V3-V6-V72、廣度優(yōu)先遍歷(BFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次訪問V0的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖 中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未

25、被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為 止數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料12010-01-06 10:43一、名詞解釋：1. 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)的組織形式，也可看成是包含數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)表，說明數(shù)據(jù)之間存在著一定的相互關(guān)系或約束。2. 邏輯結(jié)構(gòu)我們把只表現(xiàn)元素之間邏輯關(guān)系，而不涉及它們在計(jì)算機(jī)中的表示，只是理論的、反映在紙面上的東西，這種抽象的數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。3. 物理結(jié)構(gòu)抽象的數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的表示，也就是映射在存儲(chǔ)空間上的、具體的數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)表示，也就是映射在存儲(chǔ)空間上的、具體的數(shù)據(jù)結(jié)構(gòu)。二、問答題：1. 簡述“軟件工程”的工程化的思想。答：軟件工程就是應(yīng)用一些科

26、學(xué)理論和工程上的技術(shù)來指導(dǎo)軟件開發(fā)。軟件工程將研制軟件的全過程分為六個(gè)階段：問題說明，需求分析，系統(tǒng)設(shè)計(jì)，編寫程序，測試工作，運(yùn)行與維護(hù)。軟件工程的基本原則是：劃分軟件生命期，運(yùn)行計(jì)劃評審，編制軟件文檔。2. 說明對程序進(jìn)行評價(jià)時(shí)，“時(shí)間”與“空間”之間的關(guān)系。答：時(shí)間性和空間性是程序的效率問題。時(shí)間效率決定于：源程序轉(zhuǎn)換為目標(biāo)程序的時(shí)間和目標(biāo)程序執(zhí)行的時(shí)間。時(shí)間效率與編譯質(zhì)量有關(guān)，與算法的簡化程度有關(guān)，還與用戶對語言的熟練程度有關(guān)，其中，算法的效率起主要作用?？臻g效率一般指程序花費(fèi)的內(nèi)存空間的問題。對于同等復(fù)雜程度的程序：一般時(shí)間效率越高的程序，占用的內(nèi)存就越大，空間效率就越低；一般時(shí)間效率

27、越低的程序，占用的內(nèi)存就越小，空間效率就越高。兩者具有一定的矛盾性。但是隨著內(nèi)存容量的不斷增大，往往會(huì)犧牲空間性來提高時(shí)間性。3. 依照“軟件工程”的思想，敘述軟件生命周期的不同階段及各階段的主要工作內(nèi)容。答：在軟件工程中，把從軟件的計(jì)劃開始，經(jīng)歷問題的說明（定義），需求分析，設(shè)計(jì)代碼，測試與維護(hù)，直到軟件報(bào)廢為止的整個(gè)期間，稱為軟件的生命周期。在軟件生命周期中，除了最后的運(yùn)行與維護(hù)屬于運(yùn)行期，其它都稱為開發(fā)期。1） 問題說明：對研究的問題進(jìn)行完整而且適當(dāng)?shù)恼f明。2） 需求分析：根據(jù)問題說明，確定軟件必須具有的功能。不是具體解決問題，而是明確必須“做什么”。3） 系統(tǒng)設(shè)計(jì)：將反映用戶要求的邏輯模型轉(zhuǎn)換為一個(gè)具體的設(shè)計(jì)方案，使用偽碼來描述算法。4） 編寫程序：將偽碼轉(zhuǎn)換為高級語言的形式。5） 測試工作：檢查程序和系統(tǒng)的其他部分是否滿足設(shè)計(jì)要求。6） 運(yùn)行與維護(hù)：將驗(yàn)收后的軟件交付用戶使用，通過實(shí)際運(yùn)行環(huán)境的檢驗(yàn)，對不適應(yīng)的部分進(jìn)行修改和擴(kuò)充。4. 拓?fù)渑判蛑惺褂昧四切?shù)據(jù)結(jié)構(gòu)共使用了數(shù)組，鏈表，圖和堆棧四種數(shù)據(jù)結(jié)構(gòu)。三、求二叉樹的葉節(jié)點(diǎn)的個(gè)數(shù)： algorithm countleaf( Tree *t, int count ) if( t != null ) if( t-lchild = null & t-rchild = null ) count+; co