數(shù)據(jù)結(jié)構(gòu)所有練習(xí)和作業(yè)

1、 第一章練習(xí)第一章練習(xí)1. 1.數(shù)據(jù)結(jié)構(gòu)就是研究（數(shù)據(jù)結(jié)構(gòu)就是研究（ D D ）。）。A A數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) B B數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)C C數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)D D數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)在運算數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)在運算上的實現(xiàn)上的實現(xiàn)2. 2.一個算法的好壞取決于該算法的（一個算法的好壞取決于該算法的（ 空間復(fù)雜空間復(fù)雜度）和（度）和（ 時間復(fù)雜度時間復(fù)雜度 ）。）。 3. 3.下面程序的時間復(fù)雜度為（下面程序的時間復(fù)雜度為（ C C ）。）。For(i=0;im;i+)For(i=0;im;i+) For(j=0;jn

2、;j+) For(j=0;jn;j+)Aij=iAij=i* *j; j;A.O(mA.O(m2 2) )B. O(nB. O(n2 2) )C. O(nC. O(n* *m)m) D.O(n+m) D.O(n+m)4. 4.下面程序的時間復(fù)雜度為（下面程序的時間復(fù)雜度為（ O(log3(n) O(log3(n) ）。）。i=1;i=1;while(i=n)while(i=n)i=ii=i* *3; 3;假設(shè)代碼執(zhí)行次數(shù)是k，則i=3k-1因為i=n，i=3k-1=n,k=log3n+1,所以O(shè)(logn)3第二章第二章 練習(xí)練習(xí) 1.1.線性表線性表L=L=（a a1 1，a a2 2 ，a

3、an n，）下列說法正確的是（，）下列說法正確的是（ D D ）。）。 A A每個元素都有一個直接前驅(qū)和一個直接后繼每個元素都有一個直接前驅(qū)和一個直接后繼 B B線性表中至少要有一個元素線性表中至少要有一個元素 C C表中所有元素的排列順序必須是由小到大或由大到小表中所有元素的排列順序必須是由小到大或由大到小 D D除第一個和最后一個元素外，其余每個元素都有且僅有一個除第一個和最后一個元素外，其余每個元素都有且僅有一個直接前驅(qū)和一個直接后繼直接前驅(qū)和一個直接后繼 2.2.線性表采用鏈?zhǔn)酱鎯r，其地址（線性表采用鏈?zhǔn)酱鎯r，其地址（ D D ）。）。 A A必須連續(xù)必須連續(xù)B B部分地址必須連續(xù)

4、部分地址必須連續(xù) C C必須連續(xù)必須連續(xù)D D連續(xù)與否均可連續(xù)與否均可 3 3下面關(guān)于線性表敘述錯誤的是（下面關(guān)于線性表敘述錯誤的是（ B B ）。）。 A A線性表采用順序存儲，必須占用一段地址連續(xù)的單元線性表采用順序存儲，必須占用一段地址連續(xù)的單元 B B線性表采用順序存儲，便于進(jìn)行插入和刪除操作線性表采用順序存儲，便于進(jìn)行插入和刪除操作 C C線性表采用鏈?zhǔn)酱鎯?，不必占用一段地址連續(xù)的單元線性表采用鏈?zhǔn)酱鎯?，不必占用一段地址連續(xù)的單元 D D線性表采用鏈?zhǔn)酱鎯Γ阌谶M(jìn)行插入和刪除操作線性表采用鏈?zhǔn)酱鎯?，便于進(jìn)行插入和刪除操作 4 4若某線性表中最常用的操作是在最后一個元素之后插入一個若某

5、線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后一個元素，則采用（元素和刪除最后一個元素，則采用（ D D ）存儲方式最節(jié)省運算）存儲方式最節(jié)省運算時間。時間。 A A單鏈表單鏈表 B B雙鏈表雙鏈表 C C帶頭結(jié)點的雙循環(huán)鏈表帶頭結(jié)點的雙循環(huán)鏈表 D D容量足夠大的順序表容量足夠大的順序表 第二章作業(yè)第二章作業(yè)2.222.22 試寫一算法試寫一算法, ,對單鏈表實現(xiàn)就地逆置對單鏈表實現(xiàn)就地逆置, ,即利用原表的存儲空間將線性表即利用原表的存儲空間將線性表（a1,a2,a1,a2,an,an）逆置為（）逆置為（an,an-1,an,an-1,a1,a1）提示：提示：將原鏈表中的頭

6、結(jié)點和第一個元素結(jié)將原鏈表中的頭結(jié)點和第一個元素結(jié)點斷開（令其指針域為空），先構(gòu)成一個點斷開（令其指針域為空），先構(gòu)成一個空表，然后將原鏈表中各結(jié)點從第一個結(jié)空表，然后將原鏈表中各結(jié)點從第一個結(jié)點起依次插入這個新表的頭部。點起依次插入這個新表的頭部。2.112.11設(shè)順序表設(shè)順序表VaVa中的數(shù)據(jù)元素遞增有序（非中的數(shù)據(jù)元素遞增有序（非遞減有序）。試寫一算法，遞減有序）。試寫一算法，將將x x插入到順序表的適當(dāng)位置上，以保持該表插入到順序表的適當(dāng)位置上，以保持該表的有序性。的有序性。補(bǔ)充作業(yè)：補(bǔ)充作業(yè)：寫出按寫出按正位序正位序建立一個單鏈表的算法。建立一個單鏈表的算法。for (i = 1;

7、i data); / 輸入元素值p-next = NULL; if (head-next = NULL) /如果鏈表只有頭結(jié)點 head-next = p; q = p;else /如果頭結(jié)點next不為空 q-next = p; q = p;第三章練習(xí)1.假定一個順序循環(huán)隊列存儲于長度為假定一個順序循環(huán)隊列存儲于長度為n的一維數(shù)組中，的一維數(shù)組中，其隊頭和隊尾指針分別用其隊頭和隊尾指針分別用front和和rear表示，則判斷隊滿的表示，則判斷隊滿的條件是（條件是（ D）*A（rear+1）%n=frontBfront+1=rearCrear=（front-1）%nDrear=（front+1

8、）%n2.假定一個順序循環(huán)隊列的隊頭和隊尾指針分別用假定一個順序循環(huán)隊列的隊頭和隊尾指針分別用front和和rear表示，則判隊空的條件是（表示，則判隊空的條件是（D）。）。Afront+1= =rearBfront= =rear+1Cfront= =0Dfront= =rear練習(xí)3.三個元素按照三個元素按照A,B,C的順序入棧，下列哪一個是不合的順序入棧，下列哪一個是不合法的出棧序列？（法的出棧序列？（B ） A. ABC B. CAB C. ACB D. BAC 4.堆棧的邏輯特點是（堆棧的邏輯特點是（ 先進(jìn)后出先進(jìn)后出 ），隊列的邏輯特點），隊列的邏輯特點是（先進(jìn)先出是（先進(jìn)先出 ）。

9、二者的共同點是只允許在它們的）。二者的共同點是只允許在它們的（ 端點端點 ）處插入和刪除數(shù)據(jù)元素。）處插入和刪除數(shù)據(jù)元素。5. 設(shè)輸入元素的順序為設(shè)輸入元素的順序為1,2,3,4,5，要在棧的輸出端得到，要在棧的輸出端得到43521，則應(yīng)進(jìn)行棧的基本運算表示應(yīng)為：，則應(yīng)進(jìn)行棧的基本運算表示應(yīng)為：Push（S,1）,Push(S,2),Push(S,3),Push(S,4),Pop(S,4),(Pop(S,3),Push(S,5),Pop(S,5)，Pop(S,2)，Pop(S,1)。練習(xí)6. 隊列的插入操作是在隊列的（隊尾隊列的插入操作是在隊列的（隊尾 ）進(jìn)行，）進(jìn)行，刪除操作是在隊列的（刪除

10、操作是在隊列的（ 隊頭隊頭 ）進(jìn)行。）進(jìn)行。7堆棧的邏輯特點是（堆棧的邏輯特點是（ 先進(jìn)后出先進(jìn)后出 ），隊列），隊列的邏輯特點是（先進(jìn)先出的邏輯特點是（先進(jìn)先出 ）。）。第三章作業(yè)3.1 設(shè)將整數(shù)設(shè)將整數(shù)1、2、3、4依次進(jìn)棧，但只要出棧時棧依次進(jìn)棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答非空，則可將出棧操作按任何次序夾入其中，請回答下面問題：下面問題： （1）若入棧次序為）若入棧次序為push(1)，pop()，push(2），），push(3)，pop()，pop( )，push(4)，pop( )，則出棧，則出棧的數(shù)字序列為什么？的數(shù)字序列為什么？ （2）請分析）

11、請分析1、2、3、4的的24種排列中，哪些序列種排列中，哪些序列可以通過相應(yīng)的入出棧得到?？梢酝ㄟ^相應(yīng)的入出棧得到。 4、3、1、2可能嗎？可能嗎？3.12 寫出以下程序段的輸出結(jié)果（隊列中的元素寫出以下程序段的輸出結(jié)果（隊列中的元素 類型類型QElemType 為為char）。）。Void main( ) Queue Q; InitQueue(Q); Char x=e, y=c; EnQueue(Q, h); EnQueue(Q, r); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, a); Wh

12、ile ( !QueueEmpty(Q) ) DeQueue(Q, y); Printf(y); Printf(x);第四章 習(xí) 題1.空串是（零個字符的串），其長度等于（ 0 ）。2.空格串是（一個或多個空格組成的串），其長度等于（ 串中空格字符的個數(shù) ）。3.空串與空格串的區(qū)別在于：（ “” ）。4.兩個字符串相等的充分必要條件是（字符串長度相同且對應(yīng)位置字符相同）。長度相等，并且各個對應(yīng)位置上的字符都相等。5.寫出模式串p=“abaabcac”的next函數(shù)值序列為（01122312）。第五章 作 業(yè)5.1 假設(shè)有二維數(shù)組A 68，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的

13、起始存儲位置（基地址）為1000，計算：（1）數(shù)組A的體積（即存儲量）；（2）數(shù)組A的最后一個元素a57的第一個字節(jié)的地址；（3）按行存儲時，元素a14的第一個字節(jié)的地址；（4）按列存儲時，元素a47的第一個字節(jié)的地址。第五章 作 業(yè)5.10 求下列廣義表操作的結(jié)果：（1）GetHead( (p, h, w) );（4） GetTail( (a ,b) ,(c ,d) );（5） GetHead ( GetTail ( (a,b),(c,d) ) )。5.12 畫出下列廣義表的存儲結(jié)構(gòu)圖，并求它的長度。（1）( ( ( ) ) , a , ( ( b , c ) , ( ) , d ) , (

14、 ( ( e ) ) ) )（2）( ( ( ( a ) , b ) ) , ( ( ( ) , d ) , ( e , f ) ) ) 性質(zhì)性質(zhì) 1 ： 在二叉樹的第在二叉樹的第 i 層上至多有層上至多有2i-1 個結(jié)點。個結(jié)點。 (i1)二叉樹中第二叉樹中第5層上的結(jié)點個數(shù)最多為層上的結(jié)點個數(shù)最多為_C_A.8 B.15C.16 D.32第六章練習(xí)第六章練習(xí) 性質(zhì)性質(zhì) 2 ： 深度為深度為 k 的二叉樹上至多含的二叉樹上至多含 2k-1 個結(jié)點（個結(jié)點（k1）。）。深度為深度為5的二叉樹至多有（的二叉樹至多有（ C ）結(jié)點。）結(jié)點。A64 B32 C31 D63 性質(zhì)性質(zhì) 3 ： 對任何一

15、棵二叉樹，若它含有n0 個葉子結(jié)點、n2 個度為 2 的結(jié)點，則必存在關(guān)系式：n0 = n2+1。1、一棵二叉樹有、一棵二叉樹有67個結(jié)點個結(jié)點,這些結(jié)點的度要么是這些結(jié)點的度要么是0，要么是要么是2。這棵二叉樹中度數(shù)為。這棵二叉樹中度數(shù)為2的結(jié)點有的結(jié)點有 33 個。個。1.將一棵有將一棵有100個結(jié)點的完全二叉樹從上到下，從個結(jié)點的完全二叉樹從上到下，從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點的編號為左到右依次對結(jié)點進(jìn)行編號，根結(jié)點的編號為1，則編號為則編號為49的結(jié)點的左孩子的編號為的結(jié)點的左孩子的編號為_A_。*左孩子2n，右孩子2n+1A.98 B.99 C.50 D.48練練 習(xí)習(xí)1. 假

16、設(shè)一棵二叉樹的層序序列是假設(shè)一棵二叉樹的層序序列是ABCDEFGHIJ和中序序列是和中序序列是DBGEHJACIF,請畫出該樹。請畫出該樹。練練 習(xí)習(xí)1、一個哈夫曼、一個哈夫曼(Huffman)樹有樹有19個結(jié)點，則其個結(jié)點，則其葉結(jié)點的個數(shù)是葉結(jié)點的個數(shù)是 10 。哈弗曼樹。哈弗曼樹2n-1個節(jié)個節(jié)點，則有點，則有n個葉子節(jié)點。個葉子節(jié)點。2、一棵深度為、一棵深度為6的滿二叉樹有的滿二叉樹有 31 個分支結(jié)個分支結(jié)點和點和 32 個葉子。個葉子。2n- 1個節(jié)點，個節(jié)點，2n-1個個葉子葉子3、設(shè)二叉樹結(jié)點的先序序列為、設(shè)二叉樹結(jié)點的先序序列為ABDECFGH，中序序列為中序序列為DEBAF

17、CHG,則二叉樹的后序序列則二叉樹的后序序列是是EDBHFGCA 。 作 業(yè)1、已知一棵二叉樹的中序序列和后序序列分已知一棵二叉樹的中序序列和后序序列分別為：別為： DBGEACHF和和DGEBHFCA，則該二，則該二叉樹的前序序列是什么？試畫出這棵二叉樹。叉樹的前序序列是什么？試畫出這棵二叉樹。2.給定權(quán)值集合給定權(quán)值集合15,03,14,02,06,09,16,17，構(gòu)造，構(gòu)造相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。 第七章第七章 練練 習(xí)習(xí)無向完全圖具有（無向完全圖具有（ 1/2n(n-1) ）條邊。）條邊。有向完全圖具有有向完全圖具有 （ n(n

18、-1) ）條邊。）條邊。圖的遍歷方式有（深度優(yōu)先搜索圖的遍歷方式有（深度優(yōu)先搜索 ）和（）和（ 廣廣度優(yōu)先搜索度優(yōu)先搜索 ）兩種。）兩種。 0 1 04.從鄰接矩陣從鄰接矩陣A= 1 0 1 可以看出，該圖共有（可以看出，該圖共有（ ） 0 1 0頂點。如果是無向圖，則共有（）條邊。頂點。如果是無向圖，則共有（）條邊。 練練 習(xí)習(xí)1.寫出有向圖寫出有向圖2的頂點的頂點V和弧和弧E的鄰接矩陣，鄰接表和的鄰接矩陣，鄰接表和逆鄰接表逆鄰接表。 練練 習(xí)習(xí)1.從頂點從頂點a出發(fā)寫出深度優(yōu)先搜索順序和廣度優(yōu)先搜出發(fā)寫出深度優(yōu)先搜索順序和廣度優(yōu)先搜索順序。索順序。abcdegf 練練 習(xí)習(xí)1.對于圖所示的無向帶權(quán)圖，根據(jù)普里姆算法思想，對于圖所示的無向帶權(quán)圖，根據(jù)普里姆算法思想，畫出構(gòu)造該無向帶權(quán)圖最小生成樹的過程。畫出構(gòu)造該無向帶權(quán)圖最小生