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

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

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

3、序查找的平均查找長(zhǎng)度為。 三、單選題 （本題的每一備選答案中，只有一個(gè)是正確的，請(qǐng)把你認(rèn)為正確的 答案的題號(hào)填入題干的括號(hào)內(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,1 2對(duì)于下列二叉樹(shù)，其后序序列為（） （1）ABDECFG （2）DBEAFCG（3）DEBFGCA （4）GFCEBDA 3對(duì)于下列 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深度為

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

5、沖突， 建立散列表 ht 。給定關(guān)鍵字序列 32，13，49，55，22，38，21 要求：（1）構(gòu)造散列表（只畫(huà)出表，不寫(xiě)算法） ；（ 5 分） 2）求出平均查找長(zhǎng)度。 （2 分） 5用直接選擇排序方法對(duì)下列關(guān)鍵字進(jìn)行排序，請(qǐng)寫(xiě)出每一趟排序的結(jié)果。（6分） 68 45 20 90 15 10 50 五、算法設(shè)計(jì) （在下列算法的橫線上填上適當(dāng)?shù)谋磉_(dá)式或語(yǔ)句或運(yùn)算符。每空 3 分，共 30 分） 1在帶頭結(jié)點(diǎn)的 head單鏈表的結(jié)點(diǎn) 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 進(jìn)行快速排序 int i=p, j=q; R 0 =R i ; /R0 作臨時(shí)單元 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ù)結(jié)構(gòu)（ 01111、 01211）作業(yè)題（二） 一、判斷題 （下列各題，你認(rèn)為正確的， 請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打，錯(cuò)誤的打。 每小題 1分，共 10 分） （ ）1. 數(shù)據(jù)的存貯結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)。 （ ）2. 線性表簡(jiǎn)稱為“順序表” 。 （） 3. 對(duì)數(shù)據(jù)的任何運(yùn)算都不能改變數(shù)據(jù)原有的結(jié)構(gòu)特性。 （ ）4. 從循環(huán)單鏈表的任一結(jié)點(diǎn)出發(fā)，可以找到表中所有結(jié)點(diǎn)。 （ ）5. 棧是一種先進(jìn)先出的線性表。 （ ） 6. 鏈表的主要缺點(diǎn)是不能隨機(jī)訪問(wèn)。 （ ）7. 二叉樹(shù)是樹(shù)的特殊形式。 （ ） 8. 圖可以沒(méi)有邊，但不能沒(méi)有頂點(diǎn)。 （ ） 9. 冒泡排序算法是穩(wěn)定的排序。 （ ）10. 散列法是一

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

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

10、i +1（3） i - （4）i -1 4直接選擇排序的時(shí)間復(fù)雜度為（ ） （1）O（ n） （2）O（n 2n） （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畫(huà)出下列二叉樹(shù)所對(duì)應(yīng)的森林。 （3 分） 2對(duì)于下邊有向圖 （1）畫(huà)出其鄰接表（ 4 分） 2）寫(xiě)出三種不同的拓?fù)湫蛄校?3 分） 3請(qǐng)畫(huà)出先序與中序序列相同的二叉樹(shù)的所有形態(tài)。 （3 分） 4給定關(guān)鍵字序列 19 ，14，27，68，84，23，1，20，55，12，10，7

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

12、直接插入排序 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 個(gè)記錄 2 先序遍歷二叉樹(shù) 設(shè)二叉樹(shù)用二叉鏈表表示， 以 t 為根指針， 二叉鏈表結(jié)點(diǎn)的類型為 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ù)結(jié)構(gòu)（ 01111、 01211）作業(yè)題（三） 一、判斷題 （下列各題，你認(rèn)為正確的， 每題 1 分，共 10分） 1、（）2、（）3、（） 6、（）7、（）8、（） 請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打，錯(cuò)誤的打 4、（）5、（） 9、（） 10、（） ）1. 數(shù)據(jù)是計(jì)算機(jī)加工處理的對(duì)象。 ）2. 數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方

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

15、 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線性表的順序存儲(chǔ)結(jié)構(gòu)稱為。 4所有插入在表的一端進(jìn)行，而所有刪除在表的另一端進(jìn)行的線性表稱 為。 5深度為 h 的二叉樹(shù)，最少有個(gè)結(jié)點(diǎn)。 6折半查找要求待查表為表。 7 n 個(gè)記錄按其關(guān)鍵字大小遞增或遞減的次序排列起來(lái)的過(guò)程稱為 8存儲(chǔ)數(shù)據(jù)的時(shí)侯， 不僅要存儲(chǔ)數(shù)據(jù)元素的，還要存儲(chǔ)元素之間的相 互。 三、選擇題 （本題的每一備選答案中，只有一個(gè)是正確的，請(qǐng)把你認(rèn)為正確的 答案的題號(hào)填入題干的括號(hào)內(nèi)，多選不給分，每小題 3分，共 15

16、分） 1與線性表的鏈接存儲(chǔ)相符的特性是 1）插入和刪除操作靈活 2）需要連續(xù)存儲(chǔ)空間 （3）便于隨機(jī)訪問(wèn) 2若進(jìn)隊(duì)序列為 1， 2， （1）4，3，2，1 （4）存儲(chǔ)密度大 3， 4，則出隊(duì)序列是 （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 個(gè)結(jié)點(diǎn)的二叉樹(shù)，若用二叉鏈表作為存貯結(jié)構(gòu)，則非空閑的左、右孩子鏈 域?yàn)?（ ） （1）n（2）2n（3）n-1（ 4） n+1 56 個(gè)頂點(diǎn)的連通圖的深度優(yōu)先生成樹(shù)，其邊數(shù)為（ ） （1）

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

18、平均查找長(zhǎng)度 ASL。（3 分） 11五、算法設(shè)計(jì) （在下列算法的橫線內(nèi)填上適當(dāng)?shù)恼Z(yǔ)句或表達(dá)式 共 30 分） 1直接選擇排序 每空 3 分， 五、算法設(shè)計(jì) 1. n-2 、 i+1 、 、 k!=i 、 Rk void selectsort (int R ) / 按遞增序?qū)?R 0 Rn-1 進(jìn)行直接選擇排序 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ù)結(jié)構(gòu)（ 01111、 01211）作業(yè)題（四） 、判斷題（下列各題， 你認(rèn)為正確的， 每題 1 分，共 10分） 1、（）2、（）3、（） 6、（）7、（）8、（） 請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打，錯(cuò)誤的打 4、（）5、（） 9、（） 10 、（） ）1. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映象，不僅要存儲(chǔ)數(shù)據(jù)元素 的值，還要存儲(chǔ)元素之間的相

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

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

22、2、（ 2）3、（1）4、（3）5、（ 3） 1線性表的順序存儲(chǔ)不相符的特性是（ ） （1）插入和刪除操作靈活（ 2）需要連續(xù)存儲(chǔ)空間 （3）便于隨機(jī)訪問(wèn)（ 4）存儲(chǔ)密度大 2若進(jìn)隊(duì)序列為 1，2， 3，則出隊(duì)序列是（ ） （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 個(gè)結(jié)點(diǎn)的二叉樹(shù)，若用二叉鏈表作為存貯結(jié)構(gòu)，則非空閑的左、右孩子鏈 域?yàn)?（ ） （4）n+1 ） （4）6 DCBGFE，A 請(qǐng)畫(huà)出該 （1）n（2）2n（ 3）

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

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

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

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

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

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

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

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

31、ile(i=m)i+; ; else 復(fù)制第一個(gè)區(qū)間中剩下元素 復(fù)制第二個(gè)區(qū)間中剩下元素 Ak=Rj; ;k+; while(i= ) / Ak=Ri;i+;k+; while(j=t) / ;j+;k+; 20 2對(duì)有序表 R0 至 Rn-1 進(jìn)行二分查找，成功時(shí)返回記錄在表中的位置，失 敗時(shí)返回 0 Struct sqlist keytype key; ; int binsrch(sqlist R ,keytype k) / 在表 R 中查找關(guān)鍵字 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ù)結(jié)構(gòu)作業(yè)一 三、單選題（本題的第一備選答案中，只有一個(gè)是正確的，請(qǐng)把你認(rèn)為正確的答案的題 號(hào)填入題干的括號(hào)內(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，1 2、對(duì)于下列二叉樹(shù)，其后序序列為（） （ 1）ABDECFG （2）DBEAFCG （3）DEBFGCA （4）GFCEBDA 3、對(duì)于下列 AOV網(wǎng)，不能出現(xiàn)的拓?fù)湫?/p>

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

34、方法對(duì)下列關(guān)鍵字進(jìn)行排序，請(qǐng)寫(xiě)出每一趟排序的結(jié)果。（6 分） 68 45 20 90 15 10 50 五、算法設(shè)計(jì)（在下列算法的橫線上填上適當(dāng)?shù)谋磉_(dá)形式或語(yǔ)句或運(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)為正確的， 請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打， 錯(cuò)誤的打每小題 1 分， 共 10 分） 二、填空題（每空 2 分，共 20分） 1 對(duì)數(shù)據(jù)所施加的運(yùn)算可分為兩類，即 型和 型。 2 將插入限定在表的一端，而刪除限定在表的另一端進(jìn)行的線性表稱為 ；允許插

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

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

37、R j ） ; j- -； R j+1=;/插入第 i 個(gè)記錄 2 先序遍歷二叉樹(shù) 設(shè)二叉樹(shù)用二叉鏈表表示，以 t 為根指針，二叉鏈表結(jié)點(diǎn)的類型為 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ù)結(jié)構(gòu)作業(yè)三 、判斷題 （下列各題， 你認(rèn)為正確的， 請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打， 錯(cuò)誤的打。 每題 1 分， 共 10 分） ）1、數(shù)據(jù)是計(jì)算機(jī)加工處理的對(duì)象。 ）2、數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn) 算三個(gè)方面。 ）3、線性表是由 n0 個(gè)相同類型元素組成的有限序列。 ）4、棧是一種后進(jìn)先出的線性表。 ）5、從循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā)，只能找到它的后繼結(jié)點(diǎn)，不能找到它的前趨結(jié)點(diǎn)。 ）6、單鏈表設(shè)置頭結(jié)點(diǎn)的目的是為了簡(jiǎn)化運(yùn)算。 ）7、深度為 h的二叉樹(shù)最多有 2h-1 個(gè)結(jié)點(diǎn)。 ）8、圖 G 由兩個(gè)集合 V（G）和 E（G

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

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

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

42、，60，88，93 ，用折半查找法在 D 中查找 18?，F(xiàn)要求： （1） 試用圖示法表示查找過(guò)程； （4 分） （2） 求出其成功的平均查找長(zhǎng)度 ASL 。（ 3 分） 28 五、算法設(shè)計(jì)(在下列算法的橫線內(nèi)填上適當(dāng)?shù)恼Z(yǔ)句或表達(dá)式。每空 3 分，共 30 分) 1直接選擇排序 void selectsort (int R ) /按遞增序?qū)?R0Rn-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 =te

43、mp; 2中序遍歷二叉樹(shù) 設(shè)二叉樹(shù)用二叉鏈表表示，以 t 為根指針，二叉鏈表結(jié)點(diǎn)的類型為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ù)結(jié)構(gòu)作業(yè)四 29 一、判斷題（下列各題，你認(rèn)

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

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

46、為 表。 9、將 n 個(gè)記錄按其關(guān)鍵字大小遞增或遞減的次序排列起來(lái)的過(guò)程稱為 。 三、擇題（本題的每一備選答案中，只有一個(gè)是正確的，請(qǐng)把你認(rèn)為正確的答案的題號(hào)填 入題干的括號(hào)內(nèi)，多選不給分，每小題3 分，共 15分） 1線性表的鏈接存儲(chǔ)不相符的特性是（） （ 1）插入和刪除操作靈活（2）需要連續(xù)存儲(chǔ)空間 （ 3）便于隨機(jī)訪問(wèn)（4）存儲(chǔ)密度大 2若進(jìn)隊(duì)序列為 1， 2， 3，則出隊(duì)序列是（） （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 個(gè)結(jié)點(diǎn)的二叉樹(shù)，若用二叉鏈表作為存貯結(jié)構(gòu)，則非空閑的左、右孩子鏈域?yàn)椋ǎ?（ 1）n（2）2n（ 3）n-1（4） n+1 5具有 8 個(gè)頂點(diǎn)的連通圖的深度優(yōu)先生成樹(shù)，其邊數(shù)為（） （1）8（ 2）9（3）7（4）6 四、應(yīng)用題（共 25 分） 30 1已知二叉樹(shù)的中序序列為CDBAEGF, 先序序列為 DCBGFEA, 請(qǐng)畫(huà)出該二叉樹(shù)。 （5 分） 2對(duì)于給定的 5 個(gè)實(shí)數(shù) W=8 ，5，13，2，6 ，試構(gòu)造 Huffman 樹(shù)；并求出每個(gè)葉子結(jié) 點(diǎn)的哈夫曼編碼。 （6 分） 3對(duì)于圖： （1）寫(xiě)出其鄰接矩陣。 （4 分）。 4給定元序表 D=18 ，88，15，93

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

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

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

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

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

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

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

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

56、p-next=s 2、i 、 R0 、 qksort(R,i,q) 2、 隊(duì)列 、 隊(duì)尾 4、 F=R 6、 AOV 網(wǎng) 8、 插入 4、（3） 5、（ 1） 2、解： （1） 鄰接表為 38 數(shù)據(jù)結(jié)構(gòu)作業(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） 四、 應(yīng)用題 1、解：二叉樹(shù)所對(duì)應(yīng)的森林如下： 2)三種不同的拓?fù)湫蛄腥缦拢?V1 V2 V3 V5 V4 V1 V3 V5 V2 V4 V1 V3 V2 V5 V4 3、解：先序和中序相同的二叉樹(shù)的所有形態(tài)如下： 4、解： (1)外鏈法的散列表為 2) 平均查找長(zhǎng)度 ASL= (1*9+2*2+3*1 )/