數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)解答

1、問答題1.算法和程序的區(qū)別是什么呢？【參考答案】：算法的含義與程序十分相似，但又有區(qū)別。一個程序不一定滿足有窮性。例如，操作系統(tǒng)，只要整個系統(tǒng)不遭破壞，它將永遠不會停止，即使沒有作業(yè)需要處理，它仍處于動態(tài)等待中。因此，操作系統(tǒng)不是一個算法。另一方面，程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的解，而程序則是算法在計算機上的特定的實現(xiàn)。一個算法若用程序設(shè)計語言來描述，則它就是一個程序。算法與數(shù)據(jù)結(jié)構(gòu)是相輔相承的。解決某一特定類型問題的算法可以選定不同的數(shù)據(jù)結(jié)構(gòu)，而且選擇恰當(dāng)與否直接影響算法的效率。反之，一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由各種算法的執(zhí)行來體現(xiàn)。要設(shè)計一個好的算法通

2、常要考慮以下的要求。正確。算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求?？勺x。一個算法應(yīng)當(dāng)思路清晰、層次分明、簡單明了、易讀易懂。健壯。當(dāng)輸入不合法數(shù)據(jù)時，應(yīng)能作適當(dāng)處理，不至引起嚴(yán)重后果。高效。有效使用存儲空間和有較高的時間效率。2. 抽象數(shù)據(jù)類型的定義由哪幾部分組成？ 【參考答案】：數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作三部分。 3. 按數(shù)據(jù)元素之間的邏輯關(guān)系不同，數(shù)據(jù)結(jié)構(gòu)有哪幾類？ 【參考答案】：線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)和集合四類。 4. 你能舉出幾個你熟悉的"序列"的例子來嗎？ 【參考答案】：如："0，1，2，9","A，B，C，Z&quo

3、t;。 5. 簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。6.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎？【參考答案】：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。7. 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點。【參考答案】：線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 一對一的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是多對多的。8. 有下列兩段描述：（1）void pro1( ) (2)void pro2( ) n=2; y=0; While(n%2=0) x=5/y; n=n+2; printf(“%

4、d,%dn,x,y); printf(“%dn”,n); 這兩段描述均不能滿足算法的特征，試問它們違反了算法的那些特征？【參考答案】：（1）是一個死循環(huán)，違反了算法的有窮性特征。（2）出現(xiàn)除零錯誤，違反了算法的可行性特征。9. 分析并寫出下面的各語句組所代表的算法的時間復(fù)雜度。 (1) for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0;【參考答案】：O（m*n）(2) k=0; for( i=1; i<=n; i+) for (j=i ; j<=n; j+) k+; 【參考答案】：O（n2） (3) i=1; while(i<=n

5、) i=i*3;【參考答案】：3 T(n)n即：T(n) log3n =O（log3n）所以：T(n)= O（log3n） (4) k=0; for( i=1; i<=n; i+) for (j=i ; j<=n; j+) for (k=j ; k<=n; k+) x += delta; 【參考答案】：O（n3）(5) for(i=0,j=n-1;i<j;i+,j- -)t=ai; ai= aj; ai=t;【參考答案】：基本語句共執(zhí)行了n/2次，T(n)=O（n）10討論線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系，以及不同存儲結(jié)構(gòu)的比較?！敬鸢浮看鎯Y(jié)構(gòu)分為：順序存儲結(jié)構(gòu)：借助

6、元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯Y(jié)構(gòu)：借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系 數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲（物理）結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器中的實現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關(guān)： 算法設(shè)計 邏輯結(jié)構(gòu) 算法實現(xiàn) 存儲結(jié)構(gòu) 順序表：可以實現(xiàn)隨機存?。篛(1) 插入和刪除時需要移動元素：O(n) 需要預(yù)分配存儲空間; 適用于“不常進行修改操作、表中元素相對穩(wěn)定”的場合。 鏈表：只能進行順序存?。篛(n) 插入和刪除時只需修改指針：O(1) 不需要預(yù)分配存儲空間; 適用于“修改操作頻繁、事先無法估計最大表長”的場合。 應(yīng)用問題的算

7、法時間復(fù)雜度的比較 例如，以線性表表示集合進行運算的時間復(fù)雜度為O(n2), 而以有序表表示集合進行運算的時間復(fù)雜度為O(n)11判斷下列概念的正確性(1) 線性表在物理存儲空間中也一定是連續(xù)的。(2) 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。(3) 鏈表的刪除算法很簡單，因為當(dāng)刪去鏈表中某個結(jié)點后，計算機會自動地將后繼的各個單元向前移動。12試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點。答：順序結(jié)構(gòu)存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是統(tǒng)一的，要求內(nèi)存中存儲單元的地址必須是連續(xù)的。優(yōu)點：一般情況下，存儲密度大，存儲空間利用率高。缺點：（1）在做插入和刪除操作時，需移動大量元

8、素；（2）由于難以估計，必須預(yù)先分配較大的空間，往往使存儲空間不能得到充分利用；（3）表的容量難以擴充。鏈?zhǔn)浇Y(jié)構(gòu)存儲時，相鄰數(shù)據(jù)元素可隨意存放，所占空間分為兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。優(yōu)點：插入和刪除元素時很方便，使用靈活。缺點：存儲密度小，存儲空間利用率低。13試寫出一個計算鏈表中結(jié)點個數(shù)的算法，其中指針指向該鏈表的第一個結(jié)點。答：int linklist_num(linklist L,Lnode *p) int n=0;While(p)n+;p=p->next;Return n:14試設(shè)計實現(xiàn)在單鏈表中刪去值相同的多余結(jié)點的算法。 (a)為刪除前，(b

9、)為刪除后。1015181510H(a) 刪除前181510H(b) 刪除后答：void Deletaz(Linklist L) Lnode *p,*q,*r,*s; P=l->next;while (p) q=p;r=q->next;while(r)if(r->data!=p->data)q=r;r=r->next;elses=r->next;q->next=s;free(r);r=s; P=p->next; 15. 設(shè)有兩個單鏈表A、B，其中元素遞增有序，編寫算法將A、B歸并成一個按元素值遞減（允許有相同值）有序的鏈表C，要求用A、B中的原結(jié)

10、點形成，不能重新申請結(jié)點。答：void unit(Linklist A,Linklist B,Linklist C)Lnode *p,*q,*r,*s;P=A->next;q=>next;C=A;r=C;While(p&&q)if(p->dada<=q->dada)r=p;p=p->next;Elses=q;q=q->next;s->next=r->next;r->next=s;r=s;16. 如果輸入序列為1 2 3 4 5 6,試問能否通過棧結(jié)構(gòu)得到以下兩個序列:4 3 5 6 1 2和1 3 5 4 2 6;請說

11、明為什么不能實現(xiàn)或如何才能得到。17. 設(shè)輸入序列為2，3，4，5，6，利用一個棧能得到序列2，5，3，4，6嗎？?？梢杂脝捂湵韺崿F(xiàn)嗎？【答案】1、輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。 得到135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)椋?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結(jié)果135426。2、不能得到序列2，5，3，4，6。?？梢杂脝捂湵韺崿F(xiàn)

12、，這就是鏈棧。由于棧只在棧頂操作，所以鏈棧通常不設(shè)頭結(jié)點。18填空（1）一個字符串相等的充要條件是 和 。（2）串是指 的序列；空串是指 的串；空格串是指 的串。（3）設(shè)s=“IAMATEACHER”,其長度是_。（4）若n為主串長，m為子串長，則串的古典匹配算法最壞的情況下需要比較字符的總次數(shù)為 。 190001”,說明其在樸素模式匹配算法中的匹配過程。答： i=3第一趟匹配 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1(1)0 0 0 1 j=3 i=5 第二趟匹配0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1(2) 0 0 0 1 j=4 20、

13、已知一個二叉樹的先序和中序序列，能否唯一確定一棵二叉樹？并舉例。若給定先序遍歷序列和后序遍歷序列，能否唯一確定，說明理由（或舉例說明）?！緟⒖即鸢浮浚呵耙粋€可以唯一確定一個二叉樹，前序abdghcefi 中序 gdhbaecif若只知道前序和后序序列是不能確定唯一的二叉樹的，如圖中為二棵不同的二叉樹，其先序和后序的序列相同，分別為：ba和ab：21、假定用于通信的電文由8個字母A，B，C，D，E，F(xiàn)，G，H組成，各字母在電文中出現(xiàn)的概率為5，25，3，7，10，12，30，8，試為這8個字線設(shè)計哈夫曼編碼。【參考答案】：954157818927124325473010022、對于圖6.23中的

14、樹回答下列問題： （1）哪些結(jié)點是樹葉？（2）哪個結(jié)點樹根？（3）哪個結(jié)點是C雙親結(jié)點？ （4）哪個結(jié)點是C孩子結(jié)點？（5）哪些結(jié)點是F祖先結(jié)點？（6）哪些結(jié)點是B子孫結(jié)點？（7）這棵樹的高度是多少? （8）結(jié)點J的深度是多少？23、請分別畫出有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。24、已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，能否確定唯一的二叉樹？它的前序序列是什么？25、選擇題1）一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足下面 條件？A所有結(jié)點均無左孩子B所有結(jié)點均無右孩子C只有一個葉子結(jié)點D是任意一棵二叉樹2）設(shè)n、m為一棵

15、二叉樹上的兩個結(jié)點，在中序遍歷時，n在m前面的條件是（ ）。An在m右方Bn是m祖先 Cn在m左方 Dn是m子孫3）在一棵非空二叉樹的中序遍歷中，根結(jié)點的右邊_. A只有右子樹上的所有結(jié)點 B只有右子樹上的部分結(jié)點 C只有左子樹上的所有結(jié)點 D只有左子樹上的部分結(jié)點26、判斷題 （1）完全二叉樹一定存在度為1的結(jié)點。 （2）對一棵二叉樹進行層次遍歷時，應(yīng)借助于一個棧。 （3）若已知二叉樹的先序遍歷序列和后序遍歷序列，可確定唯一的一棵二叉樹。27. 圖遍歷不唯一的因素有哪些？答：遍歷的方法不同；開始遍歷的頂點不同；存儲結(jié)構(gòu)不同。28. 證明：具有n個頂點和多于n-1條邊的無向連通圖G一定不是樹。

16、答：具有n個頂點n-1條邊的無向連通圖是自由樹，即沒有確定根結(jié)點的樹，每個結(jié)點均可當(dāng)根。（根結(jié)點不唯一）29 設(shè)一個有向圖為G=(V,E),其中V= v1, v2, v3, v4,E=< v2, v1>,< v2, v3>,< v4, v1>,< v1, v4>,< v4, v2>,請畫出該有向圖,并求出每個頂點的入度和出度,畫出相應(yīng)的鄰接矩陣、鄰接鏈表答：有向圖：頂點 入度 出度V1 2 1V2 1 2V3 1 0V4 1 2鄰接距陣：鄰接鏈表：30. 圖的連通分量和最小生成樹的區(qū)別是什么？答：圖的連通分量是圖的極大連通子圖，不一定包含圖中所有頂點；而最小生成樹是連通網(wǎng)的帶權(quán)路徑長度最小的生成樹，它包含了圖中所有頂點和n-1條邊。31. 根據(jù)圖7.26：（1）假設(shè)指定從v1出發(fā)，用普里姆方法畫出最小生成樹的過程。 （2）用克魯斯卡爾方法畫出最小生成樹的過程。答：（1）假設(shè)指定從v1出發(fā)，用普里姆方法畫出最小生成樹的過程：（2）用克魯斯卡爾方法畫出最小生成樹的過程：33. 寫出圖7.28的三種可能的拓樸排序結(jié)果。答:5,2,1,3,4,6,7,85,2,4,3,1,7,6,87,5,2,1,3,4,6,833若二叉排序樹中的一個結(jié)點存在兩個孩子，那么它的中序后繼結(jié)點是否有左孩子？它的中序前驅(qū)結(jié)點是否有右孩