數(shù)據(jù)結(jié)構(gòu)綜合練習(xí)及參考答案

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

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

3、正確的，請把你認(rèn)為正確的答案的題號填入題干的括號內(nèi)，多選不給分，每小題3分，共15分）。1若進(jìn)棧序列為1，2，3，4，則不可能得到的出棧序列是（ ）（1）3,2,1,4 （2）3,2,4,1（3）4,2,3,1 （4） 2,3,4,12對于下列二叉樹，其后序序列為（ ）（1）ABDECFG （2）DBEAFCG （3）DEBFGCA （4）GFCEBDA 3對于下列AOV網(wǎng)，不能出現(xiàn)的拓?fù)湫蛄袨椋?）（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深度為k的完全二叉樹所含葉結(jié)點(diǎn)的個數(shù)最多為（ ）（1）2k （2） 2k-1 （3） k

4、 （4） 2k 5衡量查找算法效率的主要標(biāo)準(zhǔn)是（ ）（1） 元素個數(shù) （2） 所需的存貯量 （3） 平均查找長度 （4） 算法難易程度 四、應(yīng)用題（25分）1將下列森林轉(zhuǎn)化為二叉樹。（3分） 2對下圖：（1）寫出其鄰接矩陣。（2分）（2）按Kruskal算法求其最小生成樹；并寫出相應(yīng)的邊集數(shù)組。（4分） 3請畫出后序和中序序列相同的二叉樹的所有形態(tài)。（3分）4散列函數(shù)為H（k）=k%7，散列表的地址從0到6，用線性探查法解決沖突，建立散列表ht。給定關(guān)鍵字序列 32，13，49，55，22，38，21要求：（1）構(gòu)造散列表（只畫出表，不寫算法）；（5分）（2）求出平均查找長度。（2分）5用直接

5、選擇排序方法對下列關(guān)鍵字進(jìn)行排序，請寫出每一趟排序的結(jié)果。（6分）68 45 20 90 15 10 50五、算法設(shè)計(jì)（在下列算法的橫線上填上適當(dāng)?shù)谋磉_(dá)式或語句或運(yùn)算符。每空3分，共30分）1在帶頭結(jié)點(diǎn)的head單鏈表的結(jié)點(diǎn)a之后插入新元素x struct node elemtype data; node *next; ; void lkinsert (node *head, elemtype x) node *s, *p;s= new node ;s->data= x ; p=head->next;while (p!=NULL) &&( p->data!=a

6、 )_p=p->next_;if (p=NULL)cout<<“不存在結(jié)點(diǎn)a”;else _s->next=p->next _;_p->next=s _;2 快速排序void qksort (int R , int p, int q) / 按遞增序?qū)p Rq 進(jìn)行快速排序 int i=p, j=q;R 0 =R i ; /R0作臨時單元 while ( _i<j_ ) while (j>i )&&( R j _>_R 0 ) j- -; if (j>i) R i =R j ; i+;while (i<j )&a

7、mp;& (R i _<_R 0 ) i+; if (i<j) R j =R i ; j- -; ;R i =_R0_; i+; j- -;if (j>p) qksort(R,p,j);if (i<q) qksort(R,i,q) ; 數(shù)據(jù)結(jié)構(gòu)（01111、01211）作業(yè)題（二）1、 判斷題（下列各題，你認(rèn)為正確的，請?jiān)谇懊娴睦ㄌ杻?nèi)打，錯誤的打×。每小題1分，共10分）（ ）1. 數(shù)據(jù)的存貯結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)。（ ）2. 線性表簡稱為“順序表”。（）3. 對數(shù)據(jù)的任何運(yùn)算都不能改變數(shù)據(jù)原有的結(jié)構(gòu)特性。（）4. 從循環(huán)單鏈表的任一結(jié)點(diǎn)出發(fā)，可以找到表中所

8、有結(jié)點(diǎn)。（ ）5. 棧是一種先進(jìn)先出的線性表。（ ）6. 鏈表的主要缺點(diǎn)是不能隨機(jī)訪問。（ ）7. 二叉樹是樹的特殊形式。（ ）8. 圖可以沒有邊，但不能沒有頂點(diǎn)。（ ）9. 冒泡排序算法是穩(wěn)定的排序。（ ）10. 散列法是一種對關(guān)鍵字進(jìn)行比較的查找方法。2、 填空題（每空2分，共20分）1、 引 用 、 加工 2、 隊(duì)列 、 隊(duì)尾 3、 n0=n2+1 4、 F=R 5、 n*(n-1) / 2 6、 AOV 網(wǎng) 7、 8、 插入 1對數(shù)據(jù)所施加的運(yùn)算可分為兩類，即 型和 型。2將插入限定在表的一端，而刪除限定在表的另一端進(jìn)行的線性表稱為 ； 允許插入的一端稱為 。3二叉樹的葉結(jié)點(diǎn)數(shù)n0與二

9、度結(jié)點(diǎn)數(shù)n2的關(guān)系是 。4對于順序循環(huán)隊(duì)列QM，下標(biāo)從0到M1，頭尾指針分別用F和R表示，則隊(duì)空條件是 。5n個頂點(diǎn)的無向完全圖具有 條邊。6拓?fù)渑判虻牟僮鲗ο笫?。7快速排序的最壞情況是初始序列為正序和反序，其時間復(fù)雜度為 。 8希爾排序是屬于 排序的改進(jìn)方法。三、單選題（本題的每一備選答案中，只有一個是正確的，請把你認(rèn)為正確的答案的題號填入題干的括號內(nèi)，多選不給分，每小題3分，共15分） 1、（2） 2、（3） 3、（4） 4、（3） 5、（1） 1棧和隊(duì)列都是（ ）（1）順序存貯的線性結(jié)構(gòu) （2）限制存取點(diǎn)的線性結(jié)構(gòu)（3）鏈接存貯的線性結(jié)構(gòu) （4）限制存取點(diǎn)的非線性結(jié)構(gòu)2與線性表的鏈接存

10、貯不相符合的特性是 （ ）（1）便于插、刪運(yùn)算（2）存貯空間動態(tài)分配（3）需要連續(xù)的存貯空間 （4）只能順序查找3設(shè)二叉樹的根為第一層，則第i層上的結(jié)點(diǎn)數(shù)最多有 （ ）（1）i （2） i +1 （3）i - （4）i -1 4直接選擇排序的時間復(fù)雜度為 （ ）（1）O（n） （2）O(n2n) （3）O(n2 ) （4）O(2 n)5給定下列有向圖，從頂點(diǎn)V1出發(fā)，其深度優(yōu)先搜索序列為（ ）（1）12534 （2）12435 （3） 14325 （4）12345四、應(yīng)用題（25分） 1畫出下列二叉樹所對應(yīng)的森林。（3分） 2對于下邊有向圖 （1）畫出其鄰接表（4分） （2）寫出三種不同的拓?fù)?/p>

11、序列（3分） 3請畫出先序與中序序列相同的二叉樹的所有形態(tài)。（3分）4給定關(guān)鍵字序列19，14，27，68，84，23，1，20，55，12，10，79，散列函數(shù)為HK=K% 11散列表的地址從0到10，用外鏈法處理沖突，散列地址為d的同義詞均掛在以htd為頭指針的單鏈表中。（1）請畫出其散列表（不寫算法）；（5分）（2）求出成功的平均查找長度。（2分）5對下列關(guān)鍵字序列進(jìn)行快速排序，請寫出第一趟排序結(jié)果，并標(biāo)識出在第一趟排序過程中數(shù)據(jù)交換的情況。（5分）35 92 15 19 10 80 100第一趟排序結(jié)果：五、算法設(shè)計(jì)（在下列算法的橫線內(nèi)填上適當(dāng)?shù)恼Z句或表達(dá)式。 每空3分，共30分）1

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

13、 node *lc,44*rc; ;void preorder (node *t) node *s M ，*p=_ ; int top=- 1； /置?？? do while (p!=NULL) ; s+top = ; ; if (top!= -) p=stop- -； ； while ( top! = - 1 ) | ( p ! =NULL ); 數(shù)據(jù)結(jié)構(gòu)（01111、01211）作業(yè)題（三）1、 判斷題（下列各題，你認(rèn)為正確的，請?jiān)谇懊娴睦ㄌ杻?nèi)打，錯誤的打×。 每題1分，共10分）1、（） 2、（） 3、（） 4、（） 5、（）6、（） 7、（） 8、（） 9、（） 10、（）（

14、 ）1. 數(shù)據(jù)是計(jì)算機(jī)加工處理的對象。（ ）2. 數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計(jì)算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個方面。 （ ）3. 線性表是由n0個相同類型元素組成的有限序列。（ ）4. 棧是一種后進(jìn)先出的線性表。（ ）5. 從循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā)，只能找到它的后繼結(jié)點(diǎn)，不能找到它的前趨結(jié)點(diǎn)。（ ）6. 單鏈表設(shè)置頭結(jié)點(diǎn)的目的是為了簡化運(yùn)算。（ ）7. 深度為h的二叉樹最多有2h-1個結(jié)點(diǎn)。（ ）8. 圖G由兩個集合V（G）和E（G）所組成，其中頂點(diǎn)集V（G）可以為空集，而邊集E(G)不能為空。 （ ）9. 散列法是一種對關(guān)鍵字進(jìn)行運(yùn)算的查找方法和存儲方法。 （ ）10. 快速排

15、序在任何情況下，都是速度最快的一種排序方法。2、 填空題（每空2分，共20分）1、 結(jié)構(gòu) 2、 線性 、 非線性 3、 順序表 4、 隊(duì)列 5、 h 6、 有序表 7、 排序 8、 值 關(guān)系 1數(shù)據(jù)元素之間存在的相互關(guān)系稱為 。 2數(shù)據(jù)結(jié)構(gòu)從邏輯上分為 結(jié)構(gòu)和 結(jié)構(gòu)。3線性表的順序存儲結(jié)構(gòu)稱為 。 4所有插入在表的一端進(jìn)行，而所有刪除在表的另一端進(jìn)行的線性表稱為 。5深度為h的二叉樹，最少有 個結(jié)點(diǎn)。6折半查找要求待查表為 表。7n個記錄按其關(guān)鍵字大小遞增或遞減的次序排列起來的過程稱為 8存儲數(shù)據(jù)的時侯，不僅要存儲數(shù)據(jù)元素的 ，還要存儲元素之間的相互 。三、選擇題（本題的每一備選答案中，只有一

16、個是正確的，請把你認(rèn)為正確的答案的題號填入題干的括號內(nèi)，多選不給分，每小題3分，共15分）1與線性表的鏈接存儲相符的特性是 （ ）（1）插入和刪除操作靈活（2）需要連續(xù)存儲空間（3）便于隨機(jī)訪問（4）存儲密度大2若進(jìn)隊(duì)序列為1，2，3，4，則出隊(duì)序列是（ ）（1）4，3，2，1（2）1，2，3，4 （3）1，3，2，4 （4） 3，2，4，13已知廣義表A=（a,b）,(c,d)）,則head(A)等于（ ）（1）（a,b） （2）(a,b) （3）a,b （4）a4n個結(jié)點(diǎn)的二叉樹，若用二叉鏈表作為存貯結(jié)構(gòu)，則非空閑的左、右孩子鏈域?yàn)?（ ）（1）n （2）2n （3）n-1 （4）n+1

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

18、（3分）五、算法設(shè)計(jì)（在下列算法的橫線內(nèi)填上適當(dāng)?shù)恼Z句或表達(dá)式。 每空3分，共30分）1直接選擇排序五、算法設(shè)計(jì)1. n-2 、 i+1 、 < 、 k!=i 、 Rk void selectsort (int R ) / 按遞增序?qū) 0 Rn-1 進(jìn)行直接選擇排序 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 =temp; 2中序遍歷二叉樹 設(shè)二叉樹用二叉鏈表表示，以t為根指針，二叉鏈表

19、結(jié)點(diǎn)的類型為node；棧s的元素類型為指向node的指針類型, 棧容量m足夠大。中序遍歷的非遞歸算法如下：2. p 、 p=p->lc 、 cout<<p->data 、 p=p->rc 、 top!=-1 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!= -) p=stop- -； ； ； while () | ( p ! =NULL );

20、 數(shù)據(jù)結(jié)構(gòu)（01111、01211）作業(yè)題（四）1、 判斷題（下列各題，你認(rèn)為正確的，請?jiān)谇懊娴睦ㄌ杻?nèi)打，錯誤的打×。 每題1分，共10分）1、（） 2、（） 3、（） 4、（） 5、（）6、（） 7、（） 8、（） 9、（） 10、（）（ ）1. 數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映象，不僅要存儲數(shù)據(jù)元素的值，還要存儲元素之間的相互關(guān)系。（ ）2. 算法是對解題方法和步驟的描述。（ ）3. 線性表簡稱為“順序表”。（ ）4. 隊(duì)列是一種先進(jìn)后出的線性表。（ ）5. 從循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā)，既能找到它的后繼結(jié)點(diǎn)，又能找到它的前趨結(jié)點(diǎn)。（ ）6. 單鏈表設(shè)置頭結(jié)點(diǎn)的目的是為了把空表

21、與非空表、第一個結(jié)點(diǎn)處與非第一個結(jié)點(diǎn)處的運(yùn)算統(tǒng)一起來。（ ）7. 深度為h的二叉樹最多有2h-1個結(jié)點(diǎn)。（ ）8. 圖G由兩個集合V（G）和E（G）所組成，其中頂點(diǎn)集V（G）和邊集E(G)都可以為空集。 （ ）9. 散列法既是一種查找方法，又是一種存儲方法。（ ）10. 對快速排序來說，初始序列為正序和反序，都是最壞情況。二、填空題（每空2分，共20分）1數(shù)據(jù)元素之間存在的相互關(guān)系稱為 。 2數(shù)據(jù)結(jié)構(gòu)從邏輯上分為 結(jié)構(gòu)和 結(jié)構(gòu)。 3線性表的鏈接存儲結(jié)構(gòu)簡稱為 。 4所有插入和刪除都限定在表的同一端進(jìn)行的線性表稱為 。5二叉樹的第i層上，最多有 個結(jié)點(diǎn)。6樹所對應(yīng)的二叉樹，其根結(jié)點(diǎn)的 子樹一定為

22、空。7頂點(diǎn)表示活動、有向邊表示活動間優(yōu)先關(guān)系的網(wǎng)稱為 。8折半查找的前提條件是要求待查表為 表。9將n個記錄按其關(guān)鍵字大小遞增或遞減的次序排列起來的過程稱為 。三、單選題（本題的每一備選答案中，只有一個是正確的，請把你認(rèn)為正確的答案的題號填入題干的括號內(nèi)，多選不給分，每小題3分，共15分）1、（1） 2、（2） 3、（1） 4、（3） 5、（3）1線性表的順序存儲不相符的特性是 （ ）（1）插入和刪除操作靈活 （2）需要連續(xù)存儲空間（3）便于隨機(jī)訪問 （4）存儲密度大2若進(jìn)隊(duì)序列為1，2，3，則出隊(duì)序列是（ ）（1）3，2，1 （2）1，2，3 （3）1，3，2 （4） 3，2，13已知廣義表

23、A=（a,b）,(c,d)）,則head(A)等于 （ ）（1）（a,b） （2）(a,b) （3）a,b （4）a4n個結(jié)點(diǎn)的二叉樹，若用二叉鏈表作為存貯結(jié)構(gòu)，則非空閑的左、右孩子鏈域?yàn)?（ ）（1）n （2）2n （3）n-1 （4）n+1 5具有8個頂點(diǎn)的連通圖的深度優(yōu)先生成樹，其邊數(shù)為（ ）（1）8 （2）9 （3） 7 （4）6四、應(yīng)用題（共25分）1已知二叉樹的中序序列為CDBAEGF，后序序列為DCBGFEA，請畫出該二叉樹。（5分）2對于給定的5個實(shí)數(shù)W=8，5，13，2，6，試構(gòu)造Huffman樹；并求出每個葉子結(jié)點(diǎn)的哈夫曼編碼。（6分）3對下圖：（1）寫出其鄰接矩陣。（3分

24、）（2）求出從頂點(diǎn)V5出發(fā)的廣度優(yōu)先搜索遍歷序列（4分）4給定無序表D=18，88，15，93，35，51，60，17，22，用二叉排序樹查找法在D中查找51?，F(xiàn)要求：（1）試畫出二叉排序樹，并畫出查找過程；（3分）（2）求出其成功的平均查找長度ASL。（4分）五、算法設(shè)計(jì)（在下列算法的橫線內(nèi)填上適當(dāng)?shù)恼Z句或表達(dá)式或運(yùn)算符。 每空3分，共30分）1二分插入排序 void insertsort( int R )/ 按遞增序?qū)1R n 進(jìn)行二分插入排序 int i, j, left, right, mid; for ( i=2; i <= ; i+) R 0 =R i ; / 設(shè)定R0為監(jiān)

25、視哨 left=1;right= ； while (left right) ;if(R0<Rmid) right=mid-1 ;else left=mid+1; for(j=i-1;j>=left;j-)R j+1 = ; / 元素后移 Rleft=temp; 2層次遍歷二叉樹 設(shè)二叉樹用二叉鏈表表示，以t為根指針，二叉鏈表結(jié)點(diǎn)的類型為node；隊(duì)列s的元素類型為指向node的指針類型, 隊(duì)列容量m足夠大。層次遍歷二叉樹的算法如下：struct node char data; node *lc,*rc; ;void preorder (node *t) node *sm ，*p=

26、; int f=r= 1；/設(shè)置隊(duì)列頭、尾指針s1= ; while (f<=r) p=sf+ ; ; if (p->lc!=NULL) r+； ； if(p->rc!=NULL) ； sr=p->rc; 數(shù)據(jù)結(jié)構(gòu)（01111、01211）作業(yè)題（五）一、判斷題（下列各題，你認(rèn)為正確的，請?jiān)谇懊娴睦ㄌ杻?nèi)打，錯誤的打× 每題1 分，共10分）（ ）1. 算法可以用任意的符號來描述。 （ ）2. 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。 （ ）3. 線性表的順序存儲方式是按邏輯次序?qū)⒃卮娣旁谝黄刂愤B續(xù)的空間中。（ ）4. 棧是一種先進(jìn)后出的線性表

27、。 （ ）5. 將插入和刪除限定在表的同一端進(jìn)行的線性表稱為隊(duì)列。（ ）6. 單鏈表的結(jié)點(diǎn)有且僅有一個指針域。（ ）7. 二叉樹是樹的特殊形式。（ ）8. 在有向圖G中，<V2，V1>和<V1，V2>是兩條不同的邊。 （ ）9. 折半查找方法要求待查表必須是有序表。（ ）10. 快速排序在最壞情況下的時間復(fù)雜度為O（n2）。二、填空題（每空2分，共20分）1數(shù)據(jù)的存貯結(jié)構(gòu)的四種形式為 存貯， 存貯， 存貯和 存貯。2 所有插入和刪除都在表的一端進(jìn)行的線性表稱為 。3 n個結(jié)點(diǎn)的滿二叉樹,其深度k= 。4 對于順序循環(huán)隊(duì)列QM，下標(biāo)從0到M-1，頭尾指針分別為F和R，出隊(duì)

28、時， 隊(duì)首指針循環(huán)加1可表示F= 。5設(shè)二叉樹的葉結(jié)點(diǎn)數(shù)為n0 ,二度結(jié)點(diǎn)數(shù)為n2 ,則兩者之間的關(guān)系可表示為 。6n個頂點(diǎn)的連通圖的生成樹具有 條邊。7順序查找的平均查找長度為 。三、單選題（在本題的每一個備選答案中，只有一個是正確的，請把你認(rèn)為正確的答案的題號填入題干的括號里，多選不給分，每題3分，共15分）1設(shè)輸入序列為1，2，3，4 借助一個棧不可能得到的輸出序列是（ ）(1)1，2，3，4(2)4，3，2，1(3)3，4，1，2(4)1，3，4，22下列排序算法中，最壞情況下，時間復(fù)雜度為O（n2）的排序算法是（ ）(1) 堆排序 (2) 希爾排序(3) 歸并排序(4) 快速排序3在

29、單向循環(huán)鏈表中，若頭指針為h，那么p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是（ ）（1） p=NULL （2） pnext=NULL （3） p=h （4） pnext=h4與線性表的鏈接存儲不相符的特性是 （ ）（1）插入和刪除操作靈活（2）需要連續(xù)的存儲空間（3）存儲空間動態(tài)分配（4）需另外開辟空間來保存元素間的關(guān)系5對于下邊的二叉樹，其中序序列為 （ ）（1）DBEHAFCG （2）DBHEAFCG （3）ABDEHCFG （4）ABCDEFGH 四、應(yīng)用題（25分） 1請分別畫出具有三個結(jié)點(diǎn)的樹和二叉樹的所有形態(tài)。（7分）2畫出下列二叉樹所對應(yīng)的中序線索二叉樹。（5分）3寫出上述二叉樹的后序遍歷序列。

30、（4分）4假定有以下關(guān)鍵字序列，試給出快速排序的第一趟排序結(jié)果。（4分） 80 15 85 25 65 90 05 95 第一趟排序結(jié)果為： 5已知有一帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表（結(jié)點(diǎn)個數(shù)>=3），其頭指針為head，寫出刪除最后一個結(jié)點(diǎn)的語句序列（引進(jìn)一個臨時指針P, 須先找到尾結(jié)點(diǎn)）。（5分） 設(shè)雙向循環(huán)鏈表的結(jié)點(diǎn)類型為： struct bnode datatype data; bnode *prior,*next; ;五、算法設(shè)計(jì)（在下列算法的橫線上填上適當(dāng)?shù)谋磉_(dá)式或語句。每空3分，共30分）。1 將兩個有序的順序表合并成一個有序表 void merge(int R , int A ,

31、int s,int m,int t)/對兩個升序順序表RsRm和Rm+1Rt合并，結(jié)果存入升序順序表A中 int i,j,k; i=s;j=m+1;k=s; while(i<=m)&&(j<= ) if(Ri<=Rj) Ak=Ri;i+; ; else Ak=Rj; ;k+; while(i<= ) /復(fù)制第一個區(qū)間中剩下元素 Ak=Ri;i+;k+; while(j<=t) /復(fù)制第二個區(qū)間中剩下元素 ;j+;k+; 2對有序表R0至Rn-1進(jìn)行二分查找，成功時返回記錄在表中的位置，失敗時返回0Struct sqlist keytype key;

32、 int binsrch(sqlist R ,keytype k) /在表R中查找關(guān)鍵字k int low ,high,mid; low=0; high=n-1; while( ) ; if( ) return mid; else if( kRmid.key ) high=mid-1; else low=mid+1; return ; 數(shù)據(jù)結(jié)構(gòu)作業(yè)一三、單選題（本題的第一備選答案中，只有一個是正確的，請把你認(rèn)為正確的答案的題號填入題干的括號內(nèi)，多選不給分，每小題3分，共15分）。1、若進(jìn)棧序列為1，2，3，4，則不可能得到的出棧序列是（ ） （1）3，2，1，4 （2）3，2，4，1 （3）4

33、，2，3，1 （4）2，3，4，12、對于下列二叉樹，其后序序列為（ ）（1）ABDECFG （2）DBEAFCG （3）DEBFGCA （4）GFCEBDA3、對于下列AOV網(wǎng)，不能出現(xiàn)的拓?fù)湫蛄袨椋?） （1）12345 （2）12435 （3）24135 （4）214354深度為k的完全二叉樹所含葉結(jié)點(diǎn)的個數(shù)最多為（ ）（1）2K （2）2K-1 （3）k （4）2k5衡量查找算法效率的主要標(biāo)準(zhǔn)是（ ） (1)元素個數(shù) (2)所需的存貯量 (3)平均查找長度 (4)算法難易程度3請畫出后序和中序序列相同的二叉樹的所有形態(tài)。（3分）4散列函數(shù)為H（k）=k%7，散列表的地址從0到6，用線性

34、控查法解決沖突，建立散列表ht。給定關(guān)鍵字序列32，13，49，55，22，38，21要求：（1）構(gòu)造散列表（只畫出表，不寫算法）；（5分） （2）求出平均查找長度。（2分）5用直接選擇排序方法對下列關(guān)鍵字進(jìn)行排序，請寫出每一趟排序的結(jié)果。（6分）68 45 20 90 15 10 50五、算法設(shè)計(jì)（在下列算法的橫線上填上適當(dāng)?shù)谋磉_(dá)形式或語句或運(yùn)算符。每空3分，共30分）1 在帶頭結(jié)點(diǎn)的head單鏈表的結(jié)點(diǎn)a之后插入新元素x struct nodeelemtype data;數(shù)據(jù)結(jié)構(gòu)作業(yè)二一、判斷題（下列各題，你認(rèn)為正確的，請?jiān)谇懊娴睦ㄌ杻?nèi)打，錯誤的打×每小題1分，共10分）二、填空

35、題（每空2分，共20分）1 對數(shù)據(jù)所施加的運(yùn)算可分為兩類，即_型和_型。2 將插入限定在表的一端，而刪除限定在表的另一端進(jìn)行的線性表稱為_；允許插入的一端稱為_。3 二叉樹的葉結(jié)點(diǎn)數(shù)據(jù)n0與二度結(jié)點(diǎn)數(shù)據(jù)n2的關(guān)系是_。4 對于順序循環(huán)隊(duì)列QM，下標(biāo)從0到M-1，頭尾指針分別用F和R表示，則隊(duì)空條件是_。5 N個頂點(diǎn)的無向完全圖具有_條邊。6 拓?fù)渑判虻牟僮鲗ο笫莀。7 快速排序的最壞情況是初始序別為正序和反序，其時間復(fù)雜度為_。8 希爾排序是屬于_排序的改進(jìn)方法。三、單選題（本題的每一備選答案中，只有一個是正確的，請把你認(rèn)為正確的答案的題號填入題干的括號內(nèi)，多選不給分，每小題3分，共15分）1

36、棧和隊(duì)列都是 （ ） （1）順序存貯的線性結(jié)構(gòu) （2）限制存取點(diǎn)的線性結(jié)構(gòu) （3）鏈接存貯的線性結(jié)構(gòu) （4）限制存取點(diǎn)的非線性結(jié)構(gòu)四、應(yīng)用題（25分）1 畫出下列二叉樹所對應(yīng)的森林。（3分）2 對于下邊有向圖（1） 畫出其鄰接表（4分）（2） 寫出三種不同的拓?fù)湫蛄校?分）第一趟排序過程中數(shù)據(jù)交換的情況。（5分）35 92 15 19 10 80 100第一趟排序結(jié)果：五、算法設(shè)計(jì)（在下列算法的橫線內(nèi)填上適當(dāng)?shù)恼Z句或表達(dá)式。每空3分，共30分）1 直接插入排序void insertsort(int R )/按遞增序?qū)1Rn進(jìn)行直接插入排序 int i, j; for (i=2; i<=

37、_; i+) R 0=Ri; /設(shè)定R0為監(jiān)視哨 j=_; while (R 0 _R j ) _; j- -； R j+1=_; /插入第i個記錄 2 先序遍歷二叉樹設(shè)二叉樹用二叉鏈表表示，以t為根指針，二叉鏈表結(jié)點(diǎn)的類型為mode；棧s的元素類型為指向node的指針類型，棧容量M足夠大。先序遍歷的非遞歸算法如下：struct node char data; node *lc，*rc; ;void preorder (node *t)node *sM, *p=_; int top= - 1; /置?？?； dowhile (p!=NULL) _ ; s+top=_; _; if (top!=

38、- 1) p=stop- -; _ ; while ( top! = - 1) | | (p ! =NULL); 數(shù)據(jù)結(jié)構(gòu)作業(yè)三一、 判斷題（下列各題，你認(rèn)為正確的，請?jiān)谇懊娴睦ㄌ杻?nèi)打，錯誤的打×。每題1分，共10分） （ ）1、數(shù)據(jù)是計(jì)算機(jī)加工處理的對象。 （ ）2、數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計(jì)算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個方面。 （ ）3、線性表是由n0個相同類型元素組成的有限序列。 （ ）4、棧是一種后進(jìn)先出的線性表。 （ ）5、從循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā)，只能找到它的后繼結(jié)點(diǎn)，不能找到它的前趨結(jié)點(diǎn)。 （ ）6、單鏈表設(shè)置頭結(jié)點(diǎn)的目的是為了簡化運(yùn)算。 （ ）7、深

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

40、次序排列起來的過程稱為_。8、 存儲數(shù)據(jù)的時候，不僅要存儲數(shù)據(jù)元素的_，還要存儲元素之間的相互_。三、 選擇題（本題的每一備選答案中，只有一個是正確的，請把你認(rèn)為正確的答案的題號填入題干的括號內(nèi)，多選不給分，每小題3分，共15分）1與線性表的鏈接存儲相符的特性是（ ） （1）插入和刪除操作靈活（2）需要連續(xù)存儲空間 （3）便于隨機(jī)訪問（4）存儲密度大2若進(jìn)隊(duì)序列為1，2，3，4，則出隊(duì)序列是（ ） （1）4，3，2，1 （2）1，2，3，4 （3）1，3，2，4 （4）3，2，4，13已知廣義表A=（a，b），*c，d），則head（A）等于（ ） （1）（a，b） （2）（a，b） （3）a，b （4）a4結(jié)點(diǎn)的二叉樹，若用二叉鏈表作為存貯結(jié)構(gòu)，則非空閑的左、右孩子鏈域?yàn)椋?）（1）n （2）2n （3）n-1 （4）n+15個頂點(diǎn)的連通圖的深度優(yōu)先生成樹，其邊數(shù)為（ ） （1）6 （2）5 （3）7 （4）4四、 應(yīng)用題（共25分）1已知二叉樹的中序序列為DBHEIAFJCKG，先序序列為ABDEHICFJGK，請畫出該二叉樹。（4分）2于給定的5個實(shí)數(shù)W=8，5，13，2，6，試構(gòu)造Huffman樹；并求出該樹的最小帶權(quán)路徑長度。（7分）3對于下邊的圖G（1） 畫出其鄰接表（4分）。（2） 寫出從V1出發(fā)的深度優(yōu)先搜索序列（3分）。4給定有序表D