數(shù)據(jù)結構綜合練習及參考答案教材

1、數(shù)據(jù)結構（ 01111、 01211）作業(yè)題（一） 一、判斷題 （下列各題，你認為正確的，請在前面的括號內(nèi)打，錯誤的 打。每題 1分，共 10 分） 1、（）2、（）3、（）4、（）5、（） 6、（）7、（）8、（）9、（） 10、（） （ ） 1. 數(shù)據(jù)的存貯結構是數(shù)據(jù)的邏輯結構的存貯映象。 （ ） 2. 用順序表來存儲線性表時，不需要另外開辟空間來保存數(shù)據(jù)元素之 間的相互關系。 （ ） 3. 非線性結構中，至少存在一個元素不止一個直接前趨或不止一個直接后繼 （ ）4. 樹的最大特點是層次結構。 （ ） 5. 隊列的特點是先進先出。 （ ） 6. 圖的最小生成樹是唯一的。 （ ）7. 線性表

2、是廣義表的特殊形式。 （ ） 8. 后序序列和中序序列能唯一確定一棵二叉樹。 （ ） 9. 散列表是一種鏈式存貯結構。 （ ）10. 快速排序并非在任何情況下都比其它排序方法速度快。 二、填空題 （每空 2分，共 20 分） 1 數(shù)據(jù)的存貯結構的四種形式為存貯、 存貯、 存貯和 存貯。 2所有插入和刪除都在表的一端進行的線性表稱為。 3n 個結點的完全二叉樹，其深度 h= 。 4對于順序循環(huán)隊列 QM，下標從 0到 M-1，頭尾指針分別為 F和 R，入隊時， 隊尾指針循環(huán)加 1 可表示為 R= 。 5散列法既是一種查找方法，又是一種方法。 6 n 個頂點的有向完全圖具有條弧。 7n 個元素的順

3、序查找的平均查找長度為。 三、單選題 （本題的每一備選答案中，只有一個是正確的，請把你認為正確的 答案的題號填入題干的括號內(nèi)，多選不給分，每小題 3分，共 15分）。 1若進棧序列為 1，2， 3， 4，則不可能得到的出棧序列是（） （1）3,2,1,4（ 2）3,2,4,1 （3）4,2,3,1（4） 2,3,4,1 2對于下列二叉樹，其后序序列為（） （1）ABDECFG （2）DBEAFCG（3）DEBFGCA （4）GFCEBDA 3對于下列 AOV網(wǎng)，不能出現(xiàn)的拓撲序列為（） （1）1 2 3 4 5 （2）1 2 4 3 5（3）2 4 1 3 5（4）2 1 4 3 5 4深度為

4、 k 的完全二叉樹所含葉結點的個數(shù)最多為（ （1）2k（2） 2k-1（3） k（4） 2k 5衡量查找算法效率的主要標準是（ ） （1） 元素個數(shù) （3） 平均查找長度 四、應用題 （25 分） 1將下列森林轉(zhuǎn)化為二叉樹 （2）所需的存貯量 （4） 算法難易程度 3 分） FG 2對下圖： 4 分） （1）寫出其鄰接矩陣。（2 分） （2）按 Kruskal 算法求其最小生成樹；并寫出相應的邊集數(shù)組。 V1 12 V2 10 V4 V5 11 V3 3 V6 3請畫出后序和中序序列相同的二叉樹的所有形態(tài)。 （3 分） 4散列函數(shù)為 H（k）=k%7，散列表的地址從 0到 6，用線性探查法解決

5、沖突， 建立散列表 ht 。給定關鍵字序列 32，13，49，55，22，38，21 要求：（1）構造散列表（只畫出表，不寫算法） ；（ 5 分） 2）求出平均查找長度。 （2 分） 5用直接選擇排序方法對下列關鍵字進行排序，請寫出每一趟排序的結果。（6分） 68 45 20 90 15 10 50 五、算法設計 （在下列算法的橫線上填上適當?shù)谋磉_式或語句或運算符。每空 3 分，共 30 分） 1在帶頭結點的 head單鏈表的結點 a 之后插入新元素 x struct node node elemtype data; * next; ; void lkinsert (node *head, e

6、lemtype x) node *s, *p; s= new node s-data= x ; p=head-next; while (p!=NULL) if (p=NULL) coutnext=p-next p-next=s 2快速排序 Rp void qksort (int R , int p, int q)/ 按遞增序?qū)?Rq 進行快速排序 int i=p, j=q; R 0 =R i ; /R0 作臨時單元 while ( _ii ) if (ji) R i =R j ; i+; while (ij ) if (ip) qksort(R,p,j); if (iq)qksort(R,i,

7、q) 數(shù)據(jù)結構（ 01111、 01211）作業(yè)題（二） 一、判斷題 （下列各題，你認為正確的， 請在前面的括號內(nèi)打，錯誤的打。 每小題 1分，共 10 分） （ ）1. 數(shù)據(jù)的存貯結構獨立于計算機。 （ ）2. 線性表簡稱為“順序表” 。 （） 3. 對數(shù)據(jù)的任何運算都不能改變數(shù)據(jù)原有的結構特性。 （ ）4. 從循環(huán)單鏈表的任一結點出發(fā)，可以找到表中所有結點。 （ ）5. 棧是一種先進先出的線性表。 （ ） 6. 鏈表的主要缺點是不能隨機訪問。 （ ）7. 二叉樹是樹的特殊形式。 （ ） 8. 圖可以沒有邊，但不能沒有頂點。 （ ） 9. 冒泡排序算法是穩(wěn)定的排序。 （ ）10. 散列法是一

8、種對關鍵字進行比較的查找方法。 二、填空題（每空2分，共 20分） 1、 引 用 、 加工2、 隊列 、隊尾3、 n0=n2+14、F=R 5、n*（n-1） / 26、 AOV 網(wǎng)7、8、 插入 1對數(shù)據(jù)所施加的運算可分為兩類，即型和 型。 2將插入限定在表的一端，而刪除限定在表的另一端進行的線性表稱 為 ； 允許插入的一端稱為 。 3二叉樹的葉結點數(shù) n0與二度結點數(shù) n2 的關系是。 4對于順序循環(huán)隊列 QM，下標從 0到 M1，頭尾指針分別用 F和R表示， 則隊空條件是 。 5 n 個頂點的無向完全圖具有條邊。 6拓撲排序的操作對象是。 7快速排序的最壞情況是初始序列為正序和反序，其時

9、間復雜度 為。 8希爾排序是屬于排序的改進方法。 三、單選題 （本題的每一備選答案中，只有一個是正確的，請把你認為正確的 答案的題號填入題干的括號內(nèi)，多選不給分，每小題 3分，共 15分） 1、（2）2、（ 3）3、（4） 4、（3） 5、（1） 1棧和隊列都是 （1）順序存貯的線性結構 （3）鏈接存貯的線性結構 （2） （4） （） 限制存取點的線性結構 限制存取點的非線性結構 5 2與線性表的鏈接存貯不相符合的特性是（ ） （1）便于插、刪運算（2）存貯空間動態(tài)分配 （3）需要連續(xù)的存貯空間（ 4）只能順序查找 3設二叉樹的根為第一層，則第 i 層上的結點數(shù)最多有 （ ） （1）i（2）

10、i +1（3） i - （4）i -1 4直接選擇排序的時間復雜度為（ ） （1）O（ n） （2）O（n 2n） （3）O（n2 ）（4） O（ 2 n） 5給定下列有向圖，從頂點 V1 出發(fā)，其深度優(yōu)先搜索序列為（） （1）12534（ 2） 12435（3） 14325（4）12345 四、應用題 （25 分） 1畫出下列二叉樹所對應的森林。 （3 分） 2對于下邊有向圖 （1）畫出其鄰接表（ 4 分） 2）寫出三種不同的拓撲序列（ 3 分） 3請畫出先序與中序序列相同的二叉樹的所有形態(tài)。 （3 分） 4給定關鍵字序列 19 ，14，27，68，84，23，1，20，55，12，10，7

11、9 ，散 列函數(shù)為 HK=K% 11散列表的地址從 0到 10，用外鏈法處理沖突，散列地址 為 d 的同義詞均掛在以 htd 為頭指針的單鏈表中。 （1）請畫出其散列表（不寫算法） ；（5 分） （2）求出成功的平均查找長度。 （2 分） 5對下列關鍵字序列進行快速排序， 請寫出第一趟排序結果， 并標識出在第一 趟排序過程中數(shù)據(jù)交換的情況。 （5 分） 35 92 15 19 10 80 100 第一趟排序結果： 五、算法設計 （在下列算法的橫線內(nèi)填上適當?shù)恼Z句或表達式。 每空3分，共30分） 1 直接插入排序 void insertsort(int R ) / 按遞增序?qū)?R1 R n 進行

12、直接插入排序 int i, j; for ( i=2; i =n ; i+ ) R 0 =R i ; / 設定 R0 為監(jiān)視哨 j=i 1； while (R 0 R j ) Rj+1=Rj ; j- - ; R j+1 =R0 ; / 插入第 i 個記錄 2 先序遍歷二叉樹 設二叉樹用二叉鏈表表示， 以 t 為根指針， 二叉鏈表結點的類型為 node；棧 s 的元素類型為指向 node的指針類型 , 棧容量 M足夠大。先序遍歷的非遞歸算法 如下： struct node char data; node* lc,44 *rc; ; void preorder (node* t) node *

13、s M ，*p= ; int top=- 1 ； / 置?？?; do while (p!=NULL) ; s+top = ; if (top!= - ) p=stop- - ； while ( top! = - 1 ) | ( p ! =NULL ); 數(shù)據(jù)結構（ 01111、 01211）作業(yè)題（三） 一、判斷題 （下列各題，你認為正確的， 每題 1 分，共 10分） 1、（）2、（）3、（） 6、（）7、（）8、（） 請在前面的括號內(nèi)打，錯誤的打 4、（）5、（） 9、（） 10、（） ）1. 數(shù)據(jù)是計算機加工處理的對象。 ）2. 數(shù)據(jù)結構的概念包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)在計算機中的存儲方

14、式和 數(shù)據(jù)的運算三個方面。 ）3. 線性表是由 n0 個相同類型元素組成的有限序列。 ）4. 棧是一種后進先出的線性表。 ）5. 從循環(huán)鏈表的某一結點出發(fā)，只能找到它的后繼結點，不能找到它的 前趨結點。 ）6. 單鏈表設置頭結點的目的是為了簡化運算。 ）7. 深度為 h 的二叉樹最多有 2h -1 個結點。 ）8. 圖 G由兩個集合 V（ G）和 E（ G）所組成，其中頂點集 V（G）可以為 空集，而邊集 E（G）不能為空。 ） 9. 散列法是一種對關鍵字進行運算的查找方法和存儲方法。 ）10. 快速排序在任何情況下，都是速度最快的一種排序方法。 、填空題（每空 2分，共 20分） 1、 結構

15、 2、線性 、 非線性 3、順序表 4、隊列 5、h 6、有序表 7、排序 8、值 關系 1數(shù)據(jù)元素之間存在的相互關系稱為。 2數(shù)據(jù)結構從邏輯上分為結構和 結構。 3線性表的順序存儲結構稱為。 4所有插入在表的一端進行，而所有刪除在表的另一端進行的線性表稱 為。 5深度為 h 的二叉樹，最少有個結點。 6折半查找要求待查表為表。 7 n 個記錄按其關鍵字大小遞增或遞減的次序排列起來的過程稱為 8存儲數(shù)據(jù)的時侯， 不僅要存儲數(shù)據(jù)元素的，還要存儲元素之間的相 互。 三、選擇題 （本題的每一備選答案中，只有一個是正確的，請把你認為正確的 答案的題號填入題干的括號內(nèi)，多選不給分，每小題 3分，共 15

16、分） 1與線性表的鏈接存儲相符的特性是 1）插入和刪除操作靈活 2）需要連續(xù)存儲空間 （3）便于隨機訪問 2若進隊序列為 1， 2， （1）4，3，2，1 （4）存儲密度大 3， 4，則出隊序列是 （2）1，2，3，4 （3）1，3，2，4（4） 3 ，2，4，1 3已知廣義表 A=（a,b ）,（c,d） ）,則 head（A）等于 （ ） （1）（a,b ） （2）（a,b） （3）a,b（4）a 4n 個結點的二叉樹，若用二叉鏈表作為存貯結構，則非空閑的左、右孩子鏈 域為 （ ） （1）n（2）2n（3）n-1（ 4） n+1 56 個頂點的連通圖的深度優(yōu)先生成樹，其邊數(shù)為（ ） （1）

17、6（2）5（3） 7（ 4） 4 10 四、應用題 （共 25 分） 1已知二叉樹的中序序列為 DBHEIAFJCK，G先序序列為 ABDEHICFJG，K請畫出 該二叉樹。（ 4 分） 2對于給定的 5個實數(shù) W=8，5，13，2，6，試構造 Huffman 樹；并求出該 樹的最小帶權路徑長度。 （ 7 分） 3對于下邊的圖 G （1）畫出其鄰接表（ 4 分） 2）寫出從 V1出發(fā)的深度優(yōu)先搜索序列（ 3 分） 4給定有序表 D=15，17，18， 中查找 18。現(xiàn)要求： （1）試用圖示法表示查找過程； 22，35，51，60，88，93 ，用折半查找法在 D （ 4 分） 2）求出其成功的

18、平均查找長度 ASL。（3 分） 11五、算法設計 （在下列算法的橫線內(nèi)填上適當?shù)恼Z句或表達式 共 30 分） 1直接選擇排序 每空 3 分， 五、算法設計 1. n-2 、 i+1 、 、 k!=i 、 Rk void selectsort (int R ) / 按遞增序?qū)?R 0 Rn-1 進行直接選擇排序 int i, j, k, temp ; for (i=0; i= ; i+) k=i ; for (j= ; jlc 、 coutdata 、 p=p-rc 、 top!=-1 struct node char data; node*lc, *rc; ; void preorder (

19、node *t) node * sm ，*p=t ; int top =- 1 ； do / 置?？?12 while (p!=NULL) s+top = if (top!= - ) p=stop- - ； while ( ) | ( p ! =NULL ); 數(shù)據(jù)結構（ 01111、 01211）作業(yè)題（四） 、判斷題（下列各題， 你認為正確的， 每題 1 分，共 10分） 1、（）2、（）3、（） 6、（）7、（）8、（） 請在前面的括號內(nèi)打，錯誤的打 4、（）5、（） 9、（） 10 、（） ）1. 數(shù)據(jù)的存儲結構是數(shù)據(jù)的邏輯結構的存儲映象，不僅要存儲數(shù)據(jù)元素 的值，還要存儲元素之間的相

20、互關系。 ） 2. 算法是對解題方法和步驟的描述。 ）3. 線性表簡稱為“順序表” 。 ） 4. 隊列是一種先進后出的線性表。 ） 5. 從循環(huán)鏈表的某一結點出發(fā)，既能找到它的后繼結點，又能找到它 的前趨結點。 ）6. 單鏈表設置頭結點的目的是為了把空表與非空表、第一個結點處與非 第一個結點處的運算統(tǒng)一起來。 ）7. 深度為 h的二叉樹最多有 2h-1 個結點。 ）8. 圖 G由兩個集合 V（ G）和 E（G）所組成，其中頂點集 V（G）和邊集 E（G）都可以為空集。 ） 9. 散列法既是一種查找方法，又是一種存儲方法。 ） 10. 對快速排序來說，初始序列為正序和反序，都是最壞情況。 13二

21、、填空題 （每空 2分，共 20 分） 1數(shù)據(jù)元素之間存在的相互關系稱為。 2數(shù)據(jù)結構從邏輯上分為結構和 結構。 3線性表的鏈接存儲結構簡稱為 。 4所有插入和刪除都限定在表的同一端進行的線性表稱為。 5二叉樹的第 i 層上，最多有個結點。 6樹所對應的二叉樹，其根結點的子樹一定為空。 7頂點表示活動、有向邊表示活動間優(yōu)先關系的網(wǎng)稱為。 8折半查找的前提條件是要求待查表為表。 9將 n 個記錄按其關鍵字大小遞增或遞減的次序排列起來的過程稱為。 三、單選題 （本題的每一備選答案中，只有一個是正確的，請把你認為正確的 答案的題號填入題干的括號內(nèi)，多選不給分，每小題 3分，共 15分） 1、（ 1）

22、2、（ 2）3、（1）4、（3）5、（ 3） 1線性表的順序存儲不相符的特性是（ ） （1）插入和刪除操作靈活（ 2）需要連續(xù)存儲空間 （3）便于隨機訪問（ 4）存儲密度大 2若進隊序列為 1，2， 3，則出隊序列是（ ） （1）3，2，1（2）1，2，3（3）1，3，2（4） 3 ，2，1 3已知廣義表 A=（a,b ）,（c,d） ）,則 head（A）等于 （ ） （1）（a,b ）（2）（a,b）（3）a,b（4）a 4n 個結點的二叉樹，若用二叉鏈表作為存貯結構，則非空閑的左、右孩子鏈 域為 （ ） （4）n+1 ） （4）6 DCBGFE，A 請畫出該 （1）n（2）2n（ 3）

23、n-1 5具有 8 個頂點的連通圖的深度優(yōu)先生成樹，其邊數(shù)為（ （1）8（2）9（ 3） 7 四、應用題 （共 25 分） 1已知二叉樹的中序序列為CDBAEG，F(xiàn) 后序序列為 二叉樹。（5 分） 2對于給定的 5個實數(shù) W=8，5，13，2，6，試構造 Huffman 樹；并求出每 個葉子結點的哈夫曼編碼。 （6 分） 14 3對下圖： （1）寫出其鄰接矩陣。（3 分） 2）求出從頂點 V5出發(fā)的廣度優(yōu)先搜索遍歷序列（ 4 分） 4給定無序表 D=18，88，15，93，35，51，60，17，22 ，用二叉排序樹查 找法在 D中查找 51?，F(xiàn)要求： （1）試畫出二叉排序樹，并畫出查找過程；

24、 （3 分） 2）求出其成功的平均查找長度 ASL。（4 分） 15 五、算法設計 (在下列算法的橫線內(nèi)填上適當?shù)恼Z句或表達式或運算符。 每空 3 分，共 30分) 1二分插入排序 void insertsort( int R ) / 按遞增序?qū)?R1 R n 進行二分插入排序 int i, j, left, right, mid; for ( i=2; i = ; i+) R 0 =R i ;/ 設定 R0 為監(jiān)視哨 left=1;right= ； while (left right) ; if(R0=left;j-) R j+1 = ; / 元素后移 Rleft=temp; 2層次遍歷二叉

25、樹 設二叉樹用二叉鏈表表示，以 t 為根指針，二叉鏈表結點的類型為 node；隊 列 s 的元素類型為指向 node 的指針類型 , 隊列容量 m 足夠大。層次遍歷二叉樹 的算法如下： struct node char data; node *lc, *rc; ; void preorder (node *t) node * sm ，*p= ; int f=r= 1 ； / 設置隊列頭、尾指針 16 s1= while (flc!=NULL) r+； ； if(p-rc!=NULL) ； sr=p-rc; 17 數(shù)據(jù)結構（ 01111、 01211）作業(yè)題（五） 一、判斷題 （下列各題，你認為

26、正確的，請在前面的括號內(nèi)打，錯誤的打 每題 1 分，共 10 分） （ ） 1. 算法可以用任意的符號來描述。 （ ） 2. 數(shù)據(jù)的邏輯結構可以看作是從具體問題抽象出來的數(shù)學模型。 （ ） 3. 線性表的順序存儲方式是按邏輯次序?qū)⒃卮娣旁谝黄刂愤B續(xù) 的空間中。 （ ） 4. 棧是一種先進后出的線性表。 （ ） 5. 將插入和刪除限定在表的同一端進行的線性表稱為隊列。 （ ） 6. 單鏈表的結點有且僅有一個指針域。 （ ） 7. 二叉樹是樹的特殊形式。 （ ）8. 在有向圖 G中， V2，V1和V1，V2是兩條不同的邊。 （ ） 9. 折半查找方法要求待查表必須是有序表。 （ ） 10. 快

27、速排序在最壞情況下的時間復雜度為 O（ n2）。 二、填空題 （每空 2分，共 20 分） 1數(shù)據(jù)的存貯結構的四種形式為存貯， 存貯， 存貯和 存貯。 2 所有插入和刪除都在表的一端進行的線性表稱為。 3 n 個結點的滿二叉樹 , 其深度 k= 。 4 對于順序循環(huán)隊列 QM，下標從 0到 M-1，頭尾指針分別為 F和 R，出隊 時， 隊首指針循環(huán)加 1 可表示 F= 。 5設二叉樹的葉結點數(shù)為 n0 , 二度結點數(shù)為 n2 , 則兩者之間的關系可表示 為。 6n 個頂點的連通圖的生成樹具有條邊。 7順序查找的平均查找長度為。 三、單選題 （在本題的每一個備選答案中，只有一個是正確的，請把你認

28、為正 確的答案的題號填入題干的括號里，多選不給分，每題 3分，共 15分） 1設輸入序列為 1，2， 3， 4 借助一個棧不可能得到的輸出序列是（ ） （1）1 ，2，3，4 （2）4 ，3，2，1 （3）3 ，4，1，2 （4）1 ，3，4，2 2下列排序算法中，最壞情況下，時間復雜度為 O（n2）的排序算法是（ ） （1） 堆排序 （2） 希爾排序 （3） 歸并排序 （4） 快速排序 18 3在單向循環(huán)鏈表中，若頭指針為 h，那么 p 所指結點為尾結點的條件是（ ） （1） p=NULL （2） p next=NULL （3） p=h（4） p next=h 4與線性表的鏈接存儲不相符的特

29、性是（ ） （1）插入和刪除操作靈活 （2）需要連續(xù)的存儲空間 （3）存儲空間動態(tài)分配（4）需另外開辟空間來保存元素間的關系 5對于下邊的二叉樹，其中序序列為（ ） 1)DBEHAFCG 4)ABCDEFGH 四、應用題 （25 分） 1請分別畫出具有三個結點的樹和二叉樹的所有形態(tài)。 （7 分） 2畫出下列二叉樹所對應的中序線索二叉樹。 （5 分） 3寫出上述二叉樹的后序遍歷序列。 （4 分） 19 4假定有以下關鍵字序列，試給出快速排序的第一趟排序結果。 （4 分） 80 15 85 25 65 90 05 95 第一趟排序結果為： 5已知有一帶頭結點的雙向循環(huán)鏈表（結點個數(shù)=3），其頭指針

30、為 head，寫出刪除 最后一個結點的語句序列（引進一個臨時指針 P, 須先找到尾結點）。（5分） 設雙向循環(huán)鏈表的結點類型為： struct bnode datatype data; bnode ; * prior, * next; 3 分， 五、算法設計 （在下列算法的橫線上填上適當?shù)谋磉_式或語句。每空 共 30 分）。 1 將兩個有序的順序表合并成一個有序表 void merge（int R , int A ,int s,int m,int t） / 對兩個升序順序表 Rs Rm和 Rm+1Rt 合并，結果存入升序順 序表 A 中 int i,j,k; i=s;j=m+1;k=s; wh

31、ile(i=m)i+; ; else 復制第一個區(qū)間中剩下元素 復制第二個區(qū)間中剩下元素 Ak=Rj; ;k+; while(i= ) / Ak=Ri;i+;k+; while(j=t) / ;j+;k+; 20 2對有序表 R0 至 Rn-1 進行二分查找，成功時返回記錄在表中的位置，失 敗時返回 0 Struct sqlist keytype key; ; int binsrch(sqlist R ,keytype k) / 在表 R 中查找關鍵字 k int low ,high,mid; low=0; high=n-1; while( ) ; if( ) return mid; else

32、 if( k Rmid.key ) high=mid-1; else low=mid+1; return ; 21 數(shù)據(jù)結構作業(yè)一 三、單選題（本題的第一備選答案中，只有一個是正確的，請把你認為正確的答案的題 號填入題干的括號內(nèi)，多選不給分，每小題 3 分，共 15分）。 1、若進棧序列為 1， 2， 3，4，則不可能得到的出棧序列是（） （1）3，2，1，4 （2）3，2，4，1 （3） 4，2，3，1 （4）2，3，4，1 2、對于下列二叉樹，其后序序列為（） （ 1）ABDECFG （2）DBEAFCG （3）DEBFGCA （4）GFCEBDA 3、對于下列 AOV網(wǎng)，不能出現(xiàn)的拓撲序

33、列為（） 22 4) 21435 1)12345 2) 12435 3) 24135 4)2k （1）2K（2） 2K-1 5衡量查找算法效率的主要標準是（ （1） 元素個數(shù) （2） 所需的存貯量 3）k ） 3請畫出后序和中序序列相同的二叉樹的所有形態(tài)。（ 3 分） （3） 平均查找長度 （4） 算法難易程度 4散列函數(shù)為 H（k）=k%7，散列表的地址從 0 到 6，用線性控查法解決沖突，建立散列 表 ht 。給定關鍵字序列 32， 13，49，55，22，38，21 要求：（ 1）構造散列表（只畫出表，不寫算法）；（5 分） 23 （ 2）求出平均查找長度。（ 2 分） 5用直接選擇排序

34、方法對下列關鍵字進行排序，請寫出每一趟排序的結果。（6 分） 68 45 20 90 15 10 50 五、算法設計（在下列算法的橫線上填上適當?shù)谋磉_形式或語句或運算符。每空3 分，共 30 分） 1 在帶頭結點的 head 單鏈表的結點 a 之后插入新元素 x struct nodeelemtype data; 數(shù)據(jù)結構作業(yè)二 、判斷題（下列各題， 你認為正確的， 請在前面的括號內(nèi)打， 錯誤的打每小題 1 分， 共 10 分） 二、填空題（每空 2 分，共 20分） 1 對數(shù)據(jù)所施加的運算可分為兩類，即 型和 型。 2 將插入限定在表的一端，而刪除限定在表的另一端進行的線性表稱為 ；允許插

35、入的一端稱為 。 3 二叉樹的葉結點數(shù)據(jù) n0與二度結點數(shù)據(jù) n2 的關系是 。 4 對于順序循環(huán)隊列 QM ，下標從 0 到 M-1 ，頭尾指針分別用 F和 R表示，則隊空條 件是 。 5 N 個頂點的無向完全圖具有 條邊。 6 拓撲排序的操作對象是 。 7 快速排序的最壞情況是初始序別為正序和反序， 其時間復雜度為 8 希爾排序是屬于 排序的改進方法。 三、單選題（本題的每一備選答案中，只有一個是正確的，請把你認為正確的答案的題號 填入題干的括號內(nèi)，多選不給分，每小題 3 分，共 15分） 1棧和隊列都是 24 1）順序存貯的線性結構 3）鏈接存貯的線性結構 2）限制存取點的線性結構 4）

36、限制存取點的非線性結構 1 畫出下列二叉樹所對應的森林。 （3 分） 2 對于下邊有向圖 25 1） 畫出其鄰接表（ 4 分） 3 分） （5 分） （ 2） 寫出三種不同的拓撲序列（ 第一趟排序過程中數(shù)據(jù)交換的情況。 35 92 15 19 10 80 100 第一趟排序結果： 五、算法設計（在下列算法的橫線內(nèi)填上適當?shù)恼Z句或表達式。每空 3 分，共 30 分） 1 直接插入排序 void insertsort（int R ） /按遞增序?qū)?R1Rn 進行直接插入排序 int i, j; for （i=2; i=; i+） R 0=Ri;/設定 R0 為監(jiān)視哨 j=; while （R 0

37、R j ） ; j- -； R j+1=;/插入第 i 個記錄 2 先序遍歷二叉樹 設二叉樹用二叉鏈表表示，以 t 為根指針，二叉鏈表結點的類型為 mode；棧 s的元素 26 類型為指向 node 的指針類型，棧容量 M 足夠大。先序遍歷的非遞歸算法如下： struct node char data; node *lc ， *rc; ; void preorder (node *t) node *sM, *p=; int top= - 1;/置?？眨?do while (p!=NULL) ; s+top=; if (top!= - 1) p=stop- -; while ( top! = -

38、 1) | | (p ! =NULL); 數(shù)據(jù)結構作業(yè)三 、判斷題 （下列各題， 你認為正確的， 請在前面的括號內(nèi)打， 錯誤的打。 每題 1 分， 共 10 分） ）1、數(shù)據(jù)是計算機加工處理的對象。 ）2、數(shù)據(jù)結構的概念包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運 算三個方面。 ）3、線性表是由 n0 個相同類型元素組成的有限序列。 ）4、棧是一種后進先出的線性表。 ）5、從循環(huán)鏈表的某一結點出發(fā)，只能找到它的后繼結點，不能找到它的前趨結點。 ）6、單鏈表設置頭結點的目的是為了簡化運算。 ）7、深度為 h的二叉樹最多有 2h-1 個結點。 ）8、圖 G 由兩個集合 V（G）和 E（G

39、）所組成，其中頂點集 V （G）可以為空集， 而邊集 E（G ）不能為空。 ）9、散列法是一種對關鍵字進行運算的查找方法和存儲方法。 ） 10 、快速排序在任何情況下，都是速度最快的一種排序方法。 、填空題（每空 2 分，共 20分） 1、數(shù)據(jù)無素之間存在的相互關系稱為 。 27 2、數(shù)據(jù)結構從邏輯上分為 結構和 結構。 3、線性表的順序存儲結構稱為 。 4、所有 插入在表 的一端 進行， 而所有刪 除在表 的另一 端進行 的線性表 稱為 5、深度為 h 的二叉樹，最少有 個結點。 6、折半查找要待查表為 表。 7、n 個記錄按其關鍵字大小遞增或遞減的次序排列起來的過程稱為 。 8、存儲數(shù)據(jù)的

40、時候，不僅要存儲數(shù)據(jù)元素的 ，還要存儲元素之間的相互 三、選擇題（本題的每一備選答案中，只有一個是正確的，請把你認為正確的答案的題號 填入題干的括號內(nèi)，多選不給分，每小題3 分，共 15分） 1與線性表的鏈接存儲相符的特性是（） （ 1）插入和刪除操作靈活（2）需要連續(xù)存儲空間 （ 3）便于隨機訪問（4）存儲密度大 2若進隊序列為 1， 2， 3，4，則出隊序列是（） （1）4，3，2，1 （2）1，2，3，4 （ 3）1，3，2，4 （4）3，2，4，1 3已知廣義表 A= （a，b），*c，d），則 head（A ）等于（） （ 1）（a， b） （2）（a，b）（3） a， b（4）a

41、4結點的二叉樹，若用二叉鏈表作為存貯結構，則非空閑的左、右孩子鏈域為（） （ 1）n（2）2n（ 3）n-1 5個頂點的連通圖的深度優(yōu)先生成樹，其邊數(shù)為（ （1）6（ 2）5（3）7 四、應用題（共 25 分） 1已知二叉樹的中序序列為DBHEIAFJCKG 二叉樹。（4 分） （4） n+1 ） （4）4 ，先序序列為 ABDEHICFJGK ，請畫出該 2于給定的 5 個實數(shù) W=8 ，5，13，2，6 ，試構造 Huffman 樹；并求出該樹的最小帶 權路徑長度。 （ 7 分） 3對于下邊的圖 G （1） 畫出其鄰接表（ 4 分）。 4給定有序表 D=15 ，17，18，22，35，51

42、，60，88，93 ，用折半查找法在 D 中查找 18?，F(xiàn)要求： （1） 試用圖示法表示查找過程； （4 分） （2） 求出其成功的平均查找長度 ASL 。（ 3 分） 28 五、算法設計(在下列算法的橫線內(nèi)填上適當?shù)恼Z句或表達式。每空 3 分，共 30 分) 1直接選擇排序 void selectsort (int R ) /按遞增序?qū)?R0Rn-1 進行直接選擇排序 int i，j， k， temp; for (i=0; i= ; i+ k=i; for (j=; j=n-1; j+) if (R j R k ) k=j; if ( ) temp=R i ; R i = ; R k =te

43、mp; 2中序遍歷二叉樹 設二叉樹用二叉鏈表表示，以 t 為根指針，二叉鏈表結點的類型為node；棧 s 的元素 類型為指向 node的指針類型，棧容量 m 足夠大。中序遍歷的非遞歸算法如下： struct node char data; node *lc, *rc ; void preorder (node *t) node *sm , *p=t; int top = - 1;/置棧空 do while (p!=NULL) s+top =; if (top!= - 1) p=stop - -; while () | | (P! =NULL); 數(shù)據(jù)結構作業(yè)四 29 一、判斷題（下列各題，你認

44、為正確的，請在前面的括號內(nèi)打，錯誤的打。每題 1 分， 共 10 分） （ ） 1. 數(shù)據(jù)的存儲結構是數(shù)據(jù)的邏輯結構的存儲映象，不僅要存儲數(shù)據(jù)元素的值，還 要存儲元素之間的相互關系。 （ ）2. 算法是對解題方法和步驟的描述。 （ ）3. 線性表簡稱為“順序表“。 （ ）4. 隊列是一種先進后出的線性表。 （ ） 5. 從循環(huán)鏈表的某一結點出發(fā)，既能找到它的后繼結點。又能找到它的前趨結點。 （ ） 6. 單鏈表設置頭結點的目的是為了把空表與非空表、第一個結點處于非第一個結 點處的運算統(tǒng)一起來。 （ ）7. 深度為 h的二叉樹最多有 2h-1 個結點。 （ ）8.圖G由兩個集合 V（G）和 E（

45、G）所組成，其中頂點集 V （G）和邊集 E（G） 都可以為空集。 （ ） 9. 散列法既是一種查找方法，又是一種存儲方法。 （ ）10. 對于快速排序來說，初始序列為正序和反序，都是最壞情況。 二、填空題（每空 2 分，共 20分） 1、數(shù)據(jù)無素之間存在的相互關系稱為 。 2、數(shù)據(jù)結構從邏輯上分為 結構和 結構。 3、線性表的順序存儲結構稱為 。 4、所有插入和刪除都限定在表的同一端進行的線性表稱為 。 5、二叉樹的第 i 層上，最多有 個結點。 6、樹所對應的二叉樹，其根結點的 子樹一定為空。 7 、 頂點表示活動、有向邊表示活動間優(yōu)先關系的網(wǎng)稱為 。 8、 折半查找的前提條件是要求待查表

46、為 表。 9、將 n 個記錄按其關鍵字大小遞增或遞減的次序排列起來的過程稱為 。 三、擇題（本題的每一備選答案中，只有一個是正確的，請把你認為正確的答案的題號填 入題干的括號內(nèi)，多選不給分，每小題3 分，共 15分） 1線性表的鏈接存儲不相符的特性是（） （ 1）插入和刪除操作靈活（2）需要連續(xù)存儲空間 （ 3）便于隨機訪問（4）存儲密度大 2若進隊序列為 1， 2， 3，則出隊序列是（） （1）3，2，1 （ 2）1，2，3 （3）1，3，2 （4）3，2， 1 3已知廣義表 A= （ a， b）， c， d），則 head（A ）等于（） （ 1）（a， b） （2）（a，b）（3） a，

47、 b（4）a 4 n 個結點的二叉樹，若用二叉鏈表作為存貯結構，則非空閑的左、右孩子鏈域為（） （ 1）n（2）2n（ 3）n-1（4） n+1 5具有 8 個頂點的連通圖的深度優(yōu)先生成樹，其邊數(shù)為（） （1）8（ 2）9（3）7（4）6 四、應用題（共 25 分） 30 1已知二叉樹的中序序列為CDBAEGF, 先序序列為 DCBGFEA, 請畫出該二叉樹。 （5 分） 2對于給定的 5 個實數(shù) W=8 ，5，13，2，6 ，試構造 Huffman 樹；并求出每個葉子結 點的哈夫曼編碼。 （6 分） 3對于圖： （1）寫出其鄰接矩陣。 （4 分）。 4給定元序表 D=18 ，88，15，93

48、，35， 51，60，17， 22 ，用二叉排序樹查找法在 D 中查找 51?，F(xiàn)要求： （1）試畫出二叉排序，并畫出查找過程； （ 3分） （2）求出其成功的平均查找長度 ASL 。（ 4 分） 五、算法設計（在下列算法的橫線內(nèi)填上適當?shù)恼Z句或表達式。每空 3 分，共 30 分） 1二分插入排序 void insertsort（ int R ） /按遞增序?qū)?R1Rn 進行二分插入排序 int i，j，left ， right ， mid; for （i=2; i=; i+） R 0 =R i ;/設定 R0為監(jiān)視哨 left=1; right=; while （leftright） ; if

49、（R0=left; j-） Rj+1=;/ 元素后移 Rleft=temp; 2遍歷二叉樹 設二叉樹用二叉鏈表表示，以 t 為根指針，二叉鏈表結點的類型為node；隊列 s 的元 素類型為指向 node的指針類型，隊列容量 m 足夠大。層次遍歷二叉樹的算法如下： struct node 31 char data; node *lc, *rc ; void preorder (node *t) node *sm , *p=; int f=r=1;/ 設置隊列頭尾指針 s1=; while (flc!=NULL） r+; ; if （p-rc!=NULL） ; sr=p-rc; 數(shù)據(jù)結構作業(yè)五 一

50、、判斷題 （下列各題， 你認為正確的， 請在前面的括號內(nèi)打， 錯誤的打。 每題 1 分， 共 10 分） （ ） 1算法可以用任意的符號來描述。 （ ） 2數(shù)據(jù)的邏輯結構可以看作是從具體問題抽象出來的數(shù)學模型。 （ ） 3線性表的順序存儲方式是按邏輯次序?qū)⒃卮娣旁谝黄刂愤B續(xù)的空間中。 （ ） 4棧是一種先進后出的線性表。 （ ） 5將插入和刪除限定在表的同一端進行的線性表稱為隊列。 （ ） 6單鏈表的結點有僅有一個指針域。 （ ） 7二叉樹是樹的特殊形式。 （ ）8在有向圖 G 中，是兩條不同的邊。 （ ） 9折半查找方法要求待查表必須是有序表。 （ ） 10快速排序在最球情況下的時間復雜

51、度為0（n2）。 二、填空題（每空 2 分，共 20分） 1數(shù)據(jù)的存貯結構的四種形式為 存貯,存貯,存貯和 存貯。 2所有插入和刪除都在表的一端進行的線性表稱為 。 3 n個結點的滿二叉樹，其深度 k= 。 4對于順序循環(huán)隊列 QM ，下標從 0 到 M-1 ，頭尾指針分別為 F 和 R，出隊時，隊道 指針循不加 1 可表示 F= 。 32 5設二叉樹的葉結點數(shù)為 n0，二度結點數(shù)為 n2，則兩者之間的關系可表示為 6n 個頂點的連通圖的生成樹具有 條邊。 7順序查找的平均查找長度為 。 三、擇題（本題的每一備選答案中，只有一個是正確的，請把你認為正確的答案的題號填 入題干的括號內(nèi)，多選不給分

52、，每小題 3 分，共 15分） 1設輸入序列為 1， 2， 3，4，借助一個棧不可能得到的輸出序序列是（） （1）1，2，3，4 （2）4，3，2，1 （3）3，4，1，2 （4）1，3，4， 2 2下列排序算法中，最壞情況下，時間復雜度為0（ n2）的排序算法是（） （ 1）堆排序（2）希爾排序（3）歸并排序（4）快速排序 3在單向循環(huán)鏈表中，若頭指針為h，那么 p 所指結點為尾結點的條件是（ ） （ 1） p=NULL（2）pnext=NULL（3） p=h（ 4） p next=h 4與線性表的鏈接存儲不相符的特性是（） （ 1）插入和刪除操作靈活（2）需要連續(xù)的存儲空間 （ 3）存儲空

53、間動態(tài)分配（4）需另外開辟空間來保存元素間的關系 5對于下邊的二叉樹 ,其中序序列為（） 四、 1)DBEHAFCG 4)ABCDEFGH 應用題（ 25 分） 2)DBHEAFCG 3)ABDEHCFG 1請分別畫出具有三個結點的樹和二叉樹的所有形態(tài)。（7 分） 2畫出下列二叉樹所對應的中序線索二叉樹。（ 5 分） 33 34 、判斷題 1、（） 6、（） 數(shù)據(jù)結構作業(yè)題一參考答案 2、（） 7、（） 3、（） 8、（） 4、（） 9、（） 5、（） 10、（） 二、填空題 1、順序 鏈接 索引 2、 散列 35 3、log2n +1 4、(R+1) % M 5、存儲 6、n*(n-1) 7

54、、(n+1) / 2 三、單選題 1、（ 3）2、（ 3） 3、（1）4、（2）5、（ 3） 四、應用題 1、解：森林轉(zhuǎn)換成的二叉樹如下： 2、解： （1）鄰接矩陣如下： 0 12 5 12 0 8 10 8 0 3 5 0 6 10 6 0 11 3 11 0 （2） 用 Kruskal 算法求得的最小生成樹如下： 36 邊集數(shù)組如下： 3 1 4 2 2 6 4 5 3 5 3 5 6 8 10 fromvex endvex weight 1 2 3 4 5 3、解：中序和后序相同的所有二叉樹形態(tài)如下： 4、解：線性探查的散列表如下： 0 1 2 3 4 5 6 49 55 22 38 3

55、2 21 13 平均查找長度 ASL=(1+1+1+3+2+1+6)/7=15/7=2.14 5、解：直接選擇排序的每 一趟排序結果如下： 初始狀態(tài)： 68 45 20 90 15 10 50 第一趟排序結果： 10 45 20 90 15 68 50 第二趟排序結果： 10 15 20 90 45 68 50 第三趟排序結果： 10 15 20 90 45 68 50 37 第五趟排序結果： 第六趟排序結果： 10 15 20 45 50 68 90 10 15 20 45 50 68 90 五、算法設計 1、 new node 、 x p=p-next 、 s-next=p-next 、

56、p-next=s 2、i 、 R0 、 qksort(R,i,q) 2、 隊列 、 隊尾 4、 F=R 6、 AOV 網(wǎng) 8、 插入 4、（3） 5、（ 1） 2、解： （1） 鄰接表為 38 數(shù)據(jù)結構作業(yè)題二參考答案 、判斷題 1、（） 2、（） 3、（） 4、（ ） 5、（） 6、（ ） 7、（） 8、（） 9、（） 10、（） 二、填空題 1、引 用 、 加工 3、n0=n2+1 5、n*（n-1） / 2 2 7、 O（ n2） 三、單選題 1、（ 2） 2、（3） 3、（4） 四、 應用題 1、解：二叉樹所對應的森林如下： 2)三種不同的拓撲序列如下： V1 V2 V3 V5 V4 V1 V3 V5 V2 V4 V1 V3 V2 V5 V4 3、解：先序和中序相同的二叉樹的所有形態(tài)如下： 4、解： (1)外鏈法的散列表為 2) 平均查找長度 ASL= (1*9+2*2+3*1 )/