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

1、填空題 （結(jié)果由小到大排列）1.一組記錄的關(guān)鍵字為（5， 6， 2，4， 3， 1），利用簡(jiǎn)單選擇排序的方法，經(jīng)過(guò)第1 趟排序后，其關(guān)鍵字序列為1(62435)經(jīng)過(guò)第 2 趟排序后，其關(guān)鍵字序列為12(6435)經(jīng)過(guò)第 3 趟排序后，其關(guān)鍵字序列為123 (465)2.一組記錄的關(guān)鍵字為（5， 6， 2，4， 3， 1），利用直接插入排序的方法，經(jīng)過(guò)第1 趟排序后，其關(guān)鍵字序列為(56)2431經(jīng)過(guò)第 2 趟排序后，其關(guān)鍵字序列為(256)431經(jīng)過(guò)第 3 趟排序后，其關(guān)鍵字序列為(2456)313. 一組記錄的關(guān)鍵字為（ 38，5，19，26，49，97，1，66），利用冒泡排序，經(jīng)過(guò)第 1

2、 趟排序后，其關(guān)鍵字序列為51926384916697經(jīng)過(guò)第 2 趟排序后，其關(guān)鍵字序列為51926381496697經(jīng)過(guò)第 3 趟排序后，其關(guān)鍵字序列為519261384966974. 一組記錄的關(guān)鍵字為（ 265， 301， 751， 129， 937， 863， 742， 694， 76， 438），利用快速排序的方法，經(jīng)過(guò)一次劃分后，其關(guān)鍵字序列為761292657519378637426943014385. 一組記錄的關(guān)鍵字為（ 265， 301， 751， 129， 937， 863， 742， 694， 76， 438），利用歸并排序的方法經(jīng)過(guò)第 1 趟排序后，其關(guān)鍵字序列為26

3、530112975186393769474276438經(jīng)過(guò)第 2 趟排序后，其關(guān)鍵字序列為12926530175169474286393776438經(jīng)過(guò)第 3 趟排序后，其關(guān)鍵字序列為12926530169474275186393776438珊珊的練習(xí)題選擇題1.數(shù)據(jù)結(jié)構(gòu)DS(Data Struct) 可以被形式地定義為 DS=（ D， R），其中D是 的有限集 A 數(shù)據(jù)對(duì)象合，R是D上的數(shù)據(jù)元素有限集合。操作關(guān)系2. 數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)方式，在存儲(chǔ)空間使用的靈活性上，鏈性存儲(chǔ)要比順序儲(chǔ)存要A 低高相同不一定3.計(jì)算機(jī)算法指的是，它具備輸入、輸出和等五個(gè)特性。A計(jì)算方法解決問(wèn)題

4、的有限運(yùn)算序列可行性、確定性和有窮性確定性、有窮性和穩(wěn)定性4.下面程序段執(zhí)行后變量count 的值為（）。int count=0;for(int i=1;i<=10;i+)count= count +i*10;A. 250 B.350 C. 450D. 5505.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種的存儲(chǔ)結(jié)構(gòu)，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種_的存儲(chǔ)結(jié)構(gòu)。A 隨機(jī)存取B索引存取C順序存取D 散列存取6.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址_。A. 必須是連續(xù)的B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的D. 連續(xù)或不連續(xù)都可以7. 在一個(gè)單鏈表中， 已知 q 所指結(jié)點(diǎn)是 p 所指結(jié)點(diǎn)的前

5、驅(qū)結(jié)點(diǎn)， 若在 q 和 p 之間插入 s 結(jié)點(diǎn)，則執(zhí)行 _。A. s->next=p->next;p->next=s;B. p->next=s->next;s->next=p;C. q->next=s;s->next=p;D. p->next=s;s->next=q;8.在一個(gè)單鏈表中，若p 所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p 之后插入 s 所指結(jié)點(diǎn)，則執(zhí)行 _。A. s->next=p; p->next=s;B. s->next=p->next;p->next=s;C. s->next=p->nex

6、t;p=s;D. p->next=s;s->next=p;9.在一個(gè)單鏈表中，若刪除p 所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行_。A. p->next= p->next->next ；B. p= p->next;p->next= p->next->next ；C. p->next= p->next;D. p= p->next->next ；10. 鏈表不具備的特點(diǎn)是 _ 。A 可隨機(jī)訪問(wèn)任何一個(gè)元素B 插入、刪除操作不需要移動(dòng)元素C 無(wú)需事先估計(jì)存儲(chǔ)空間大小D 所需存儲(chǔ)空間與線性表長(zhǎng)度成正比11.一個(gè)隊(duì)列的數(shù)據(jù)入列序列是1， 2

7、， 3， 4，則隊(duì)列的出隊(duì)時(shí)輸出序列是_。A4， 3， 2，1B1，2，3， 4C1， 4， 3，2D3，2，4， 112. 一個(gè)隊(duì)列的數(shù)據(jù)入列序列是 1，2，3，4，把隊(duì)列的數(shù)據(jù)出隊(duì)后壓入一個(gè)棧中，當(dāng)隊(duì)列為空時(shí)再把數(shù)據(jù)從棧中彈出，數(shù)據(jù)的出棧序列是 _ 。A 4， 3，2，1B1， 2，3， 4C 1，4，3，2D3，2，4， 113.判斷一個(gè)表達(dá)式中左右括號(hào)是否匹配，采用_ 實(shí)現(xiàn)較為方便。A 線性表的順序存儲(chǔ)B隊(duì)列 C 線性表的鏈?zhǔn)酱鎯?chǔ)D 棧14.棧與一般線性表區(qū)別主要在方面。A 元素個(gè)數(shù) B 元素類(lèi)型C 邏輯結(jié)構(gòu)D 插入、刪除元素的位置15.在一個(gè)鏈隊(duì)中，假設(shè)F 和 R 分別是隊(duì)首和隊(duì)尾指

8、針，則數(shù)據(jù)出隊(duì)的運(yùn)算是。AR=F->next;BR=R->next;CF=F->next;DF=R->next;填空題 （排序結(jié)果由小到大排列）6. 數(shù)據(jù)元素 是數(shù)據(jù)的基本單位，有些情況下它也稱(chēng)為元素、結(jié)點(diǎn)、記錄。7. 數(shù)據(jù)項(xiàng) 是數(shù)據(jù)的不可分割的最小單位。8.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。9.一組記錄的關(guān)鍵字為（5， 6， 2，4， 3，1），利用簡(jiǎn)單選擇排序的方法，經(jīng)過(guò)3 趟排序后，其關(guān)鍵字序列為 1， 2， 3， 4， 6， 510.一組記錄的關(guān)鍵字為（5， 6， 2，4， 3，1），利用直接插入排序的方法，經(jīng)過(guò)3 趟排序后，其關(guān)鍵字序列為 2

9、， 4， 5， 6， 3， 111.一組記錄的關(guān)鍵字為（38，5， 19， 26，49， 97，1， 66），利用冒泡排序的方法，經(jīng)過(guò)3 趟排序后，其關(guān)鍵字序列為5，19， 26，38， 1， 49， 66， 9712. 一組記錄的關(guān)鍵字為（ 265， 301， 751， 129， 937， 863， 742， 694， 76， 438），利用快速排序的方法，經(jīng)過(guò)3 趟排序后，其關(guān)鍵字序列為76， 129， 265， 438， 301， 694， 742， 751，863， 93713. 一組記錄的關(guān)鍵字為（ 265， 301， 751， 129， 937， 863， 742， 694， 76

10、， 438），利用歸并排序的方法，經(jīng)過(guò)3 趟排序后，其關(guān)鍵字序列為129， 265，301， 694， 742， 751， 863， 937，76， 43814.在一個(gè)長(zhǎng)度為n 的順序表中刪除第 i 個(gè)元素，要移動(dòng)N-I個(gè)元素。如果要在第i 個(gè)元素前插入一個(gè)元素，要后移N-I+1個(gè)元素。15.棧操作數(shù)據(jù)的原則是 后進(jìn)先出，隊(duì)列操作數(shù)據(jù)的原則是先進(jìn)先出 。16.在棧中，可進(jìn)行插入和刪除操作的一端稱(chēng)棧頂。17.棧和隊(duì)列都是 _線性 _結(jié)構(gòu)；對(duì)于棧只能在_棧頂 _插入和刪除元素；對(duì)于隊(duì)列只能在_隊(duì)尾 _插入元素和 _隊(duì)頭 _刪除元素。18.計(jì)算機(jī)在運(yùn)行遞歸程序時(shí)，要用到系統(tǒng)提供的棧。19. 表達(dá)式

11、a*(b+c)-d 的后綴表達(dá)式是 abc+*d-20. 若 a=1， b=2， c=3， d=4，則后綴式 db/cc*a-b*+ 的運(yùn)算結(jié)果為 _ 1821.設(shè)將整數(shù)1，2，3，4 進(jìn)棧，若入、出棧次序?yàn)镻ush, Pop,Push,Push, Pop, Pop,Push, Pop,則出棧的數(shù)字序列為 1324 ；若想得到出棧序列 1432 則具體操作為： Push，Pop，Push，Push，Push，Pop， Pop， Pop22. 在采用少用一個(gè)存儲(chǔ)空間的具有 n 個(gè)單元的循環(huán)隊(duì)列中， 隊(duì)滿時(shí)共有 n-1 個(gè)元素。 對(duì)于下圖所示的循環(huán)隊(duì)列，隊(duì)滿的條件是 front=(rear+1)%

12、MAXSIZE ；隊(duì)空的條件是 rear=front23.一棵有 n 個(gè)結(jié)點(diǎn)的滿二叉樹(shù)有_0_個(gè)度為 1的結(jié)點(diǎn)、有 _(n-1)/2_個(gè)分支 （非 終端）結(jié)點(diǎn)和 _(n+1)/2_ 個(gè)葉子，該滿二叉樹(shù)的深度為 _log 2(n+1)_ 。24.寫(xiě)出下圖二叉樹(shù)的先序遍歷結(jié)果ABDCEFJ中序遍歷結(jié)果 DBAECJF、后序遍歷結(jié)果DBEJFCAABCDEFJ第九周：排序練習(xí)插入排序：初始數(shù)據(jù)： 30205040601. 302. 20 303. 20 30 504. 20 30 40 505.20 30 40 5060選擇排序：初始數(shù)據(jù)： 30 20 50 40 601. 20 30 50 40

13、602. 20 30 50 40 603.203040 50 604.20304050 60第十二周：查找練習(xí)1、已知散列表地址區(qū)間為010，哈希函數(shù)為H(k)=k ll ，給定關(guān)鍵字序列（16， 13，20， 18，23， 15，31， 45， 56）。分別采用線性探測(cè)法和鏈接法，將以上關(guān)鍵字依次存儲(chǔ)到哈希表中。請(qǐng)描述出散列地址的計(jì)算過(guò)程及最后得到的散列表。012345678910231345151656182031線性探測(cè)法：H(k)=k : ll第一趟K=16H(16)=5第二趟 :K=13H(13)=2第三趟 :K=20H(20)=9第四趟 :K=18H(18)=7第五趟 :K=23H

14、(23)=1第五趟 :K=15H(15)=4第六趟 :K=31H(31)=9由于與20發(fā)生沖突， H(31)=(31+1)/11. 即 H(31)=10第七趟 :K=45H(45)=1由于與23發(fā)生沖突， H(45)=(45+1)/11. 即 H(45)=2但又與13發(fā)生沖突， H(45)=(45+2)/11. 即 H(45)=3第八趟 :K=56H(56)=1由于與23發(fā)生沖突， H(45)=(45+1)/11. 即 H(45)=2但又與13發(fā)生沖突， H(45)=(45+2)/11. 即 H(45)=3但又與45發(fā)生沖突， H(45)=(45+3)/11. 即 H(45)=4但又與15發(fā)生

15、沖突， H(45)=(45+4)/11. 即 H(45)=5但又與16發(fā)生沖突， H(45)=(45+5)/11. 即 H(45)=6鏈接法：012345562133 4515166718892030102、考慮散列表的查找方法，試完成以下兩題 已知哈希函數(shù)為H(k)=k ll ，線性探測(cè)法解決沖突，散列表狀態(tài)如下：012345678910231345151656182031請(qǐng)描述出關(guān)鍵字45 和 5 的查找過(guò)程及結(jié)果。查找 45:H(K)=K%11K=45H(45)=1由于 23不等于 45,即 H(45)=(45+1)/11=2由于 13不等于 45，即 H(45)=(45+2)/11=3

16、由于 H(45)=3 時(shí)，查找成功 .比較次數(shù)為 3查找 5K=5K(5)=5由于 16 不等于 5，即 H(5)=(5+1)/11=6由于 56 不等于 5，即 H(5)=(5+1)/11=7由于 18 不等于 5，即 H(5)=(5+1)/11=8由于 H(8) 為空，所以關(guān)鍵字5 一定不在哈希表中 . 已知哈希函數(shù)為 H(k)=k ll ，線性探測(cè)法解決沖突，散列表狀態(tài)如下：0123456789103323134515165618192031請(qǐng)描述出關(guān)鍵字50 的查找過(guò)程及結(jié)果。H(K)=K%11K=50H(50)=6由于 56 不等于 50，即 H(50)=(50+1)/11=7.由于

17、 18 不等于 50，即 H(50)=(50+2)/11=8由于 19 不等于 50，即 H(50)=(50+3)/11=9由于 20 不等于 50，即 H(50)=(50+4)/11=10由于 31 不等于 50，即 H(50)=(50+5)/11=0由于 33 不等于 50，即 H(50)=(50+6)/11=1由于 23 不等于 50，即 H(50)=(50+7)/11=2由于 13 不等于 50，即 H(50)=(50+8)/11=3由于 45 不等于 50，即 H(50)=(50+9)/11=4由于 15 不等于 50，即 H(50)=(50+10)/11=5由于 16 不等于 50

18、，即 H(50)=(50+11)/11=6由于游歷一遍后，亦沒(méi)有查找關(guān)鍵字50，即查找失敗.第十三周：數(shù)的遍歷1、分別寫(xiě)出下面二叉樹(shù)的層次、先序、中序、后序遍歷的次序。ABCDEHFG層次：ABCDEFGH先序 :ABDFGCEH中序 :BFDGAEHC后序 :FGDBHECA2、畫(huà)出上面二叉樹(shù)的二叉鏈的鏈?zhǔn)浇Y(jié)構(gòu)ROOTAC BDEFGH3、給出一顆二叉樹(shù)的后序遍歷和中序遍歷的次序，后序遍歷為：BDECA中序編列為： BADCE畫(huà)出這顆樹(shù)。ABCED第十四周：二叉樹(shù)1、 畫(huà)出創(chuàng)建下列數(shù)據(jù)到二叉排序樹(shù)的過(guò)程，并中序遍歷這棵二叉排序樹(shù)。3620508030202656362050103080265

19、6中序遍歷： 10202630365650802、 把下列數(shù)據(jù)生成一棵完全二叉樹(shù)，并判斷這棵樹(shù)是不是堆。如果不是就調(diào)整為最大堆結(jié)構(gòu)。90806030205060709080603020506070化成大堆90806070205060“303、 下面是一棵最小堆結(jié)構(gòu)的樹(shù)，列出輸出排序次序的過(guò)程（即每次輸出根結(jié)點(diǎn)后，刪除根）。103020603626過(guò)程：103020603626輸出 1026302060362030266036輸出 203630266026303660輸出 2626363060603630303660輸出 3030366060363660輸出 3660輸出 60第十五周圖的存儲(chǔ)結(jié)

20、構(gòu)三、練習(xí)題1.畫(huà)出下面無(wú)向圖的鄰接矩陣和鄰接表（參考課件）。ADBCEABCDEA01111B10000C10000D10001E10010ABCDEBACADAEAD或vexdat firstaradjvexnext0A1234 1B02C03D04E03這個(gè)是后插式，還有前插式。2. 畫(huà)出下面有向圖的鄰接矩陣和鄰接表。ADBCEABCDEA01101B00000C00000D10001E00000ABCEBDAEE 或vexdatfirstaradjvexnext0A124 1B2C3D044E第3題：struct EdgeNodeintadjvex;EdgeNode*next;stru

21、ct VertexNodecharvexdata;EdgeNode*firstarc;VertexNode G5;第十六周：復(fù)習(xí)一、單項(xiàng)選擇題(從下列各題四個(gè)備選答案中選出一個(gè)正確答案,將其代號(hào)(A,B,C,D) 寫(xiě)在下表中 ,答題寫(xiě)在其它地方無(wú)效；每小題1 分題號(hào)1234567891011答案1.數(shù)據(jù)的不可分割的基本單位是_D_。A. 元素B. 結(jié)點(diǎn)C.數(shù)據(jù)類(lèi)型D.數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的標(biāo)識(shí)單位，是數(shù)據(jù)不可分割的最小單位；數(shù)據(jù)元素是數(shù)據(jù)的操作基本單位。數(shù)據(jù)元素也又可稱(chēng)為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。7.與中綴表達(dá)式a+b*c-d 等價(jià)的后綴表達(dá)式是_abc*+d- _。運(yùn)算符優(yōu)先級(jí)：0：(

22、#1：+-2：*/利用棧結(jié)構(gòu)存放運(yùn)算符轉(zhuǎn)換規(guī)則：操作數(shù)直接存放在后綴表達(dá)式中運(yùn)算符按照以下規(guī)則入棧/ 出棧：先預(yù)存“”至棧底a) “（”強(qiáng)制入棧b) 遇到“）”開(kāi)始出棧，直到遇見(jiàn)棧頂元素為“ （”為止c) 如果中綴表達(dá)式中掃描的當(dāng)前運(yùn)算符優(yōu)先級(jí)高于棧頂運(yùn)算符優(yōu)先級(jí)則當(dāng)前運(yùn)算符入棧，否則要棧頂運(yùn)算符先出棧再進(jìn)行比較。8.折半查找有序表(6,15,30,37,65,68,70,72,89,99), 若查找元素37,需依次與表中元素 _D _進(jìn)行比較 ,。A.65,15,37B.68,30,37C.65,15,30D.65,15,30,37數(shù)組 A：0123456789615303765687072

23、8999low=0,high=9 (0+9)/2=4 37<A 4 low=0,high=4-1=3; (0+3)/2=1 37>A 1 low=1+1=2,high=3 (2+3)/2=2 37>A 2 low=2+1=3,high=3 (3+3)/2=3 37=A 3。9.對(duì)長(zhǎng)度為10 的表作選擇 (簡(jiǎn)單選擇 )排序 ,共需比較 _A _次關(guān)鍵字。A.45B.90C.55D.11010.對(duì) n 個(gè)元素的表作快速排序,在最壞情況下 ,算法的時(shí)間復(fù)雜度為 _C_。A.O(log 2 n)B.O(nlog 2 n)C.O(n 2)D.O(2 n )11.對(duì)長(zhǎng)度為10 的表作 2

24、_路歸并排序 ,共需移動(dòng) _C_次 (個(gè) )記錄。A.20B.45C.40D.30一道關(guān)于數(shù)據(jù)結(jié)構(gòu)歸并排序移動(dòng)記錄次數(shù)的題目12345678910111213141&2 ;3&4 ; 5&6 ; 7&8 ; 9&10 ; 兩兩歸并 ,共移動(dòng) 10 次 ,比較 5 次 1,2&3,4 ; 5,6&7,8 ; 9,10 兩兩歸并 ,共移動(dòng) 10 次 ,比較 3 次 1,2,3,4&5,6,7,8 ; 9,10, 兩兩歸并 ,共移動(dòng) 10 次 ,比較 4 次 1,2,3,4,5,6,7,8 & 9,10, 兩兩歸并 ,共移動(dòng) 1

25、0 次,比較 8 次正序共移動(dòng)10*4=40, 比較 5+3+4+8=20 次二、填空 (每空 1 分 ,共 11 分)1.一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映象 )稱(chēng)為 _存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)_?。2.線性表中 _元素的個(gè)數(shù) _ 稱(chēng)為表的長(zhǎng)度。3.棧中元素的進(jìn)出原則為_(kāi)后進(jìn)先出或先進(jìn)后出_ 。4.設(shè)數(shù)組 A1.10,1.8 的基地址為 2000,每個(gè)元素占2個(gè)存儲(chǔ)單元 ,若以行序?yàn)橹餍蝽樞虼鎯?chǔ),則元素 A4,5 的存儲(chǔ)地址為 _2056_；若以列序?yàn)橹餍蝽樞虼鎯?chǔ),則元素 A4,5 的存儲(chǔ)地址為 _2086 _。1、 11、21、 31、 41、 51、 61、 71、 82、 12、22、 32、

26、 42、 52、 62、 72、 83、 13、23、 33、 43、 53、 63、 73、 84、 14、24、 34、 44、 54、 64、 74、 85、 15、25、 35、 45、 55、 65、 75、 86、 16、26、 36、 46、 56、 66、 76、 87、 17、27、 37、 47、 57、 67、 77、 88、 18、28、 38、 48、 58、 68、 78、 89、 19、99、 39、 49、 59、 69、 79、 810、 110、 210、 310、 410、 510、 610、 710、 85.一棵深度為6 的滿二叉樹(shù)有_31_個(gè)非終端結(jié)點(diǎn)

27、（分支結(jié)點(diǎn)）。滿二叉樹(shù)的性質(zhì)：性質(zhì)1：滿二叉樹(shù)中第 i 層上有2i-1 個(gè)結(jié)點(diǎn)數(shù)（即葉子結(jié)點(diǎn)）性質(zhì) 2：深度為 h 的滿二叉樹(shù)有2h-1 個(gè)結(jié)點(diǎn)數(shù)所以：整棵滿二叉樹(shù)的結(jié)點(diǎn)數(shù)-葉子結(jié)點(diǎn)數(shù) =分支結(jié)點(diǎn)數(shù)26-1 - 2(6-1) = 316.若一棵二叉樹(shù)中有8 個(gè)度為 2 的結(jié)點(diǎn) ,則它有 _9_個(gè)葉子。一般二叉樹(shù)的性質(zhì)：葉子結(jié)點(diǎn)數(shù)= 雙分支結(jié)點(diǎn)數(shù) - 17.順序查找n 個(gè)元素的順序表,當(dāng)使用監(jiān)視哨時(shí),若查找成功 ,比較關(guān)鍵字的次數(shù)至少為次；若查找失敗,比較關(guān)鍵字的次數(shù)為_(kāi)n+1 _次。三、回答下列問(wèn)題(每小題 5 分 ,共 10 分)1.線性表的存儲(chǔ)結(jié)構(gòu),在什么情況下采用順序結(jié)構(gòu)? 為什么 ?_

28、1_次 ,最多為 _n_2.二叉樹(shù)有哪幾種基本形態(tài)?（五種基本形態(tài)） 畫(huà)圖說(shuō)明之?？諛?shù)僅有根結(jié)點(diǎn)的二叉樹(shù)右子樹(shù)為空的二叉樹(shù)3 畫(huà)出下面無(wú)向圖的鄰接矩陣和鄰接表（參考課件）左子樹(shù)為空的二叉樹(shù) 左右子樹(shù)均非空的二叉樹(shù)，列出該圖有 A 為起點(diǎn)的廣度優(yōu)先遍歷和深度優(yōu)先遍歷結(jié)果A108D1112B9CE鄰接矩陣ABCDEA0811109B80000C110000D1000012E9001200082C0113D084124E09312廣度優(yōu)先遍歷： ABCDE 或 AEDCB深度優(yōu)先遍歷： ABCDE 或 AEDCB4 列出該圖的廣度優(yōu)先遍歷和深度優(yōu)先遍歷結(jié)果(起點(diǎn)為 A)AD

29、BCE廣度優(yōu)先遍歷:ABCED 或 AECBD深度優(yōu)先遍歷:ABCED或AECBD四、試畫(huà)出下列存儲(chǔ)結(jié)構(gòu)圖(每小題4分,共 20 分)1.數(shù)組 A1.2,0.2的以列序?yàn)橹餍虻捻樞虼鎯?chǔ)結(jié)構(gòu)。A1 、 0，A2 、 0 ，A1 、1，A2 、1，A1 、2，A2 、22.依次將元素A,C,D,B插入一個(gè)初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫(huà)出所有插入完成之后的鏈?zhǔn)綏！ｍ斨羔楤DCA五、求解下列問(wèn)題(每小題 6 分 ,共 24 分)2.試按表 ( 10,8,9,12,20,5,6,15,19,25 ) 中元素的排列次序 , 將所有元素插入一棵初始為空的二叉排序樹(shù)中 , 使之仍是一棵二叉排序樹(shù)。(1) 試畫(huà)

30、出插入完成之后的二叉排序樹(shù)；1012859202561519(2) 若查找元素 17,它將依次與二叉排序樹(shù)中哪些元素比較大小?10， 12， 20， 15， 19(3) 假設(shè)每個(gè)元素的查找概率相等（ 1*1 + 2*2 + 3*3 + 3*4 + 1*5） /10,試計(jì)算該樹(shù)的平均查找長(zhǎng)度ASL 。(4) 對(duì)該樹(shù)進(jìn)行中序遍歷 ,試寫(xiě)出中序遍歷序列。5689101215192025六、程序填空(在算法中有下劃線的位置填空,使之成為完整、正確的算法 )算法說(shuō)明 :已知 Rn 是 n 個(gè)記錄的遞增有序數(shù)組,用折半查找法查找關(guān)鍵字為k 的記錄 ,若查找失敗 ,則返回 -1；否則返回該記錄的序號(hào)值。in

31、tBinFindList(int Rn, int k)int low= 0 , high=n-1;while( low<=high)int mid= (low+high) / 2;if(k=L.listmid) returnmid ;else if( k<L.listmid ) high=mid-1;else low= mid+1 ;return -1;七、算法設(shè)計(jì)(算法中必須有注釋)1.設(shè)n 個(gè)元素的線性表順序存儲(chǔ)在一維數(shù)組stmaxlen 的前n 個(gè)位置上,試將新元素e 插入表中第i-1個(gè)和第i 個(gè)元素之間,寫(xiě)出算法(可用文字或流程圖描述)。/ 向最大長(zhǎng)度為MAXSIZEint

32、Insert(int st,int n,int/數(shù)組空間是否已滿if(n = MAXSIZE)、有效長(zhǎng)度為i, inte)n 的數(shù)組st下標(biāo)i 處插入新元素ecout<<" 空間滿 "<<endl;return(-1);/檢查插入位置的有效性if(i < 1 | i > L->length)cout<<" 位置錯(cuò) "<<endl;return(0);/向后移動(dòng)數(shù)組元素，空出i 位置/從下標(biāo) length-1 開(kāi)始到 i 結(jié)束，按照從后向前的順序依次向后移動(dòng)元素 for(int j = n-

33、1; j >= i; j -)stj+1 = stj;/插入新元素sti = e ;return (1); /插入成功2.設(shè) Head 為帶表頭結(jié)點(diǎn)的單鏈表的頭指針,試寫(xiě)出算法 :若為非空表 ,則輸出首結(jié)點(diǎn)和尾結(jié)點(diǎn)的值(data 值 )；否則輸出 :” Empty list ！”。void print(Node *Head)Node *t = Head->next;/ 帶空表頭結(jié)點(diǎn) ,第一個(gè)有效結(jié)點(diǎn)應(yīng)為鏈表的第二個(gè)結(jié)點(diǎn) t if(t=NULL) /空表cout<<"Empty list ！ "<<endl; return;elsecout

34、<<" 首結(jié)點(diǎn)數(shù)據(jù)為："<<t->data<<endl;while(t->next != NULL)/ 查找尾結(jié)點(diǎn)t = t->next;cout<<" 尾結(jié)點(diǎn)數(shù)據(jù)為："<<t->data<<endl;1、自己獨(dú)立實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的代碼（當(dāng)堂課完成并上傳）操作有：初始化、表頭插入、按值查找、按位置刪除、輸出具體要求：完成下面代碼中紅色 字的內(nèi)容/ 數(shù)據(jù)類(lèi)型定義及函數(shù)聲明/ 數(shù)據(jù)元素 ElemType 類(lèi)型為 inttypedefintElemType;

35、/ 結(jié)點(diǎn)數(shù)據(jù)類(lèi)型struct NodeElemTypedata;/ data代表數(shù)據(jù)元素Node*Next;/指向下一結(jié)點(diǎn)的指針;/ 單鏈表數(shù)據(jù)類(lèi)型struct ChainListintnLength; / 代表結(jié)點(diǎn)的個(gè)數(shù)Node*head;/ 指向單鏈表的頭結(jié)點(diǎn);/ 初始化線性表為空表void init_ChainList( ChainList &L);/ 表頭插入法voidInsert_ChainList(ChainList&L, ElemTypex );/ 按值查找，返回找到的位置intLocation_ChainList(ChainList &L, ElemTy

36、pex);/ 按位置 i 刪除voidDelete_ChainList(ChainList&L,inti);/ 輸出線性表的所有元素void print(ChainList &L);各種操作實(shí)現(xiàn)代碼如下：測(cè)試代碼詳見(jiàn)附件中項(xiàng)目文件/ 初始化線性表為空表，即表長(zhǎng)為0，表頭指針為空void init_ChainList( ChainList &L)L.nLength = 0;L.head = NULL;/ 表頭插入法，將元素 x 插入到表頭位置voidInsert_ChainList(ChainList&L, ElemTypex )/申請(qǐng)并初始化新結(jié)點(diǎn)t（ data

37、、 next 的初始化）Node *t ;t = new Node;t->data = x;t->Next = L.head;/ 原表頭結(jié)點(diǎn)head 作為新結(jié)點(diǎn)t 的后繼/更新表頭指針指向和表長(zhǎng)L.head = t;/ 表頭指針指向新結(jié)點(diǎn)tL.nLength+ ; / 表長(zhǎng)增 1/ 按值查找，返回找到的位置/x存在則返回所在具體位置；x 不存在返回0；表空返回1intLocation_ChainList(ChainList &L, ElemTypex)if(L.nLength = 0)/ 表空cout<<" 線性表是空表："<<e

38、ndl;return-1;/ 查找結(jié)點(diǎn) x Node *p; p = L.head;int j = 1;while(p&&p->data != x)/ p 存在且 p 指向的結(jié)點(diǎn)數(shù)據(jù)域的值不為xp = p->Next;j+;/ 分情況返回結(jié)果if(p = NULL)/元素 x 不存在cout<<" 沒(méi)找到 "<<endl;return0;else/ 元素 x 存在returnj ;/ 刪除第 i 位置的元素voidDelete_ChainList(ChainList&L,inti)/*位置 i 的有效性判斷if(

39、i<=0| i>L.nLength )/ i 的位置非法 cout<<" 刪除元素的位置有錯(cuò)："<<endl;return;Node *t;/*當(dāng) i=1 的時(shí)候特殊處理if(i=1)t = L.head;L.head = L.head->Next;/ 表頭指針指向原表頭的后繼結(jié)點(diǎn)delete t;L.nLength-; /表長(zhǎng)減 1return;/*查找位置i 的前驅(qū)位置jt = L.head;int j = 1;while(j< i-1&&t)t = t->Next;/ t 指向下一個(gè)結(jié)點(diǎn)j+; /t 指向 i 結(jié)點(diǎn)的前驅(qū)位置j/*刪除 i 位置上的結(jié)點(diǎn)tNode *p;p = t;/p指向待刪除結(jié)點(diǎn)的前驅(qū)t = p->Next;/ t 指向待刪除結(jié)點(diǎn)p->Next = t->Next;/ 將 t 的后繼連在p 的后面，即令t 的后繼成為p 的后繼delete t;L.nLength-;/ 輸出線性表的所有元素void print(ChainList &L)Node *t = L.head;