填空題：

1. 將時(shí)間復(fù)雜度數(shù)量級(jí)O(n2)、O(nlog2n)、O(2n)、O(1)、O(log2n)和O(n)按由小到大進(jìn)行排序，結(jié)果為：__O(1)，_O(log2n)，_O(n)_，O(nlog2n)，O(n2)，O(2n)___。

2. ?數(shù)據(jù)的邏輯結(jié)構(gòu)可分為_____線性結(jié)構(gòu)___和_____非線性結(jié)構(gòu)___。

3. ?用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為______SXSSXSXX__。

4. ?設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn)，若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下兩條語句：_____py->next=px->next__和_px->next=py_____。

5. ?在雙鏈表結(jié)構(gòu)中，若要求在p 指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針s所指的結(jié)點(diǎn)，則需執(zhí)行下列語句：s->next=p； s->prior= ____p->prior____；p->prior=s；___s->prior->next_____=s；

6. ?已知一個(gè)棧的輸入序列是1,2,3,…,n，其輸出序列是p1,p2,…,pn，若p1=n，則pi的值是___n-i+1__。

7. ?用下標(biāo)0開始的長(zhǎng)度為N的數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，為實(shí)現(xiàn)下標(biāo)變量M加1后在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)，可采用的表達(dá)式是：M=____(M+1)%N____。

8. ?串是一種特殊的線性表，其特殊性：??數(shù)據(jù)元素的類型為字符型??；兩個(gè)串相等的充分必要條件是???它們的長(zhǎng)度相等且對(duì)應(yīng)位置的字符相同。

9. 設(shè)有二維數(shù)組A[0..9, 0..19],其每個(gè)元素占2個(gè)字節(jié)，第一個(gè)元素的存儲(chǔ)地址為100，若按列優(yōu)先順序存儲(chǔ)，則元素A[6, 6]存儲(chǔ)地址為______352__。

10.?設(shè)有一個(gè)10階對(duì)稱矩陣A采用壓縮存儲(chǔ)方式（以行為主序存儲(chǔ)：LOC(a11)=1），則a85的地址為_____33___。

11.?廣義表(a, (a, b), d, e, ((i, j), k))的長(zhǎng)度是?? ???5?，深度是????3???? ?。?

12. ?設(shè)廣義表L=((), ())，則head(L)是??()?? ?；tail(L)是?(())???? ?。?

13. ?有n個(gè)頂點(diǎn)的無向圖最多有_____n*(n-1)/2___條邊。

16. 對(duì)于n個(gè)頂點(diǎn)的連通圖來說，它的生成樹一定有____n-1____條邊。

14. ?在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最小的是?? ?快速排序?? ??，需要內(nèi)存容量最多的是???基數(shù)排序?? ?。?

15. ?對(duì)序列{98,36,-9,0,47,23,1,8,10,7}采用希爾排序，增量為4的第一趟排序結(jié)果是__

__（10，7，-9，0，47，23，1，8，98，36)____。

16. 一個(gè)有2021個(gè)結(jié)點(diǎn)的完全二叉樹的高度為___11_____。

選擇題

1. ?數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象及它們之間的（?關(guān)系?? ）和運(yùn)算的學(xué)科。

A.結(jié)構(gòu) ? ? ? ? ? ?B.關(guān)系 ? ? ? ? ? ?C.運(yùn)算 ? ? ? ? ? ?D.算法

?

2. 可以用（ ?抽象數(shù)據(jù)類型??）定義一個(gè)完整的數(shù)據(jù)結(jié)構(gòu)。

A.數(shù)據(jù)元素 ? ? B.數(shù)據(jù)對(duì)象 ? ? ? ? C.數(shù)據(jù)關(guān)系 ? ? D.抽象數(shù)據(jù)類型

?

3. 抽象數(shù)據(jù)類型的三個(gè)組成部分分別為（數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作?? ?）。

A.數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作 ? ? ? B.數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

C.數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類型 ? ? ? ? D.數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型

?

4.?下列說法正確的是（?一些表面上不相同的數(shù)據(jù)可以具有相同的邏輯結(jié)構(gòu)?? ）。

A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位 ? ? B.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合

C.一些表面上不相同的數(shù)據(jù)可以具有相同的邏輯結(jié)構(gòu) ? ?D.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單

解析：A.數(shù)據(jù)元素是數(shù)據(jù)的基本單位?

C.數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

?D.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位

?

5. 某算法的語句執(zhí)行頻度為3n+nlog2n+n2+8，其時(shí)間復(fù)雜度可表示為（?O(n2)??）。

A.O(n2) ? ? ? B.O(nlog2n) ? ? ? ? ?C.O(log2n) ? ? ?D.O(n)

解析：時(shí)間復(fù)雜度主要取決于n的最高次冪數(shù)，即最大影響因子。此題目中n的最高次冪數(shù)為n^2。

?

6. ?以下（ ?由100個(gè)字符組成的序列?）是一個(gè)線性表。

A.由n個(gè)實(shí)數(shù)組成的集合 ? ? ? ? ? ? B.由100個(gè)字符組成的序列

C.所有整數(shù)組成的序列 ? ? ? ? ? ? ? D.鄰接表

解析：線性表的定義為：由n個(gè)數(shù)據(jù)元素組成的有限序列。

A.?不滿足序列。集合中的各元素之間沒有前后驅(qū)關(guān)系。 ?

C.不滿足有限。所有整數(shù)組成的序列的元素個(gè)數(shù)是無窮多個(gè)。 ?

D.鄰接表是屬于存儲(chǔ)結(jié)構(gòu)，但線性表是一種邏輯結(jié)構(gòu)。

?

7. 向順序表中插入一個(gè)新數(shù)據(jù)結(jié)點(diǎn)時(shí)，平均需要移動(dòng)（?n/2?? ）個(gè)結(jié)點(diǎn)。

A. n ? ? ? ? ? ?B. n/2 ? ? ? ? ? C. n+1 ? ? ? ? ? D. (n+1)/2?

?

8. 對(duì)于順序存儲(chǔ)的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（O(1)?O(n)?? ）。

A.O(n) ?O(n) ? ? B. O(n) ?O(1) ? C. O(1) ?O(n) ? D. O(1) ?O(1)

解析：順序存儲(chǔ)可以實(shí)現(xiàn)“隨機(jī)存取”，因此訪問結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)，而插入、刪除結(jié)點(diǎn)由于涉及到大量移動(dòng)元素，故其時(shí)間復(fù)雜度為O(n)。

?

9. ?線性表（a1,a2,…,an）以鏈接方式存儲(chǔ)時(shí)，訪問第i元素的時(shí)間復(fù)雜度為（?O(n)?? ）。

A.O(i) ? ? ? ? ? B.O(1) ? ? ? ? ?C.O(n) ? ? ? ? D.O(i-1)

解析：鏈?zhǔn)酱鎯?chǔ)訪問元素要遍歷

?。阂粋€(gè)算法的時(shí)間復(fù)雜度的定義是問題規(guī)模（即n）的函數(shù)，故不是O（i）

?

10. 單鏈表中增加一個(gè)頭結(jié)點(diǎn)的目的是（?方便運(yùn)算的實(shí)現(xiàn)?? ）。

A.使單鏈表至少有一個(gè)結(jié)點(diǎn) ? ? ? ? ? B.標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置

C.方便運(yùn)算的實(shí)現(xiàn) ? ? ? ? ? ? ? ? ? D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)

解析：頭結(jié)點(diǎn)的存在，使得空鏈表與非空鏈表的處理變得一致，也方便了對(duì)鏈表的開始結(jié)點(diǎn)插入或刪除操作。

?

11. 設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,next），若在p指針?biāo)附Y(jié)點(diǎn)后插入由指針s指向的結(jié)點(diǎn)，則應(yīng)執(zhí)行下面的（ ??s->next=p->next; ?p->next=s;?）操作。

A.p->next=s; ?s->next=p; ? ? ? ? ? ? B. p->next=s; ?s->next=p->next;

C. s->next=p; ?s=p; ? ? ? ? ? ? ? ? ?D. s->next=p->next; ?p->next=s;

?

12. 某鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用(?帶頭結(jié)點(diǎn)的雙循環(huán)鏈表??)最節(jié)省時(shí)間。

A.單鏈表 ? ? ? ? ? ? ? ? B.單循環(huán)鏈表

C.帶尾指針的單循環(huán)鏈表 ? D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

解析：首先總在末位操作，所以使用循環(huán)鏈表。又因?yàn)橐獔?zhí)行刪除操作：刪除尾結(jié)點(diǎn)需要找到倒數(shù)第二個(gè)結(jié)點(diǎn)，但單向鏈表無法得到前一個(gè)結(jié)點(diǎn)，即倒數(shù)第二個(gè)結(jié)點(diǎn)。而雙循環(huán)鏈表，可向回訪問。

?

13. 對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（?head->next==NULL??）。

A. head==NULL ? ? ? ? ? B. head->next==NULL

C. head->next==head ? ? ? D. head!=NULL

?

14. 下面關(guān)于串的的敘述中，不正確的是（ ?空串是由空格構(gòu)成的串??）。

A. 串是字符的有限序列 ? ? ? ? B. 模式匹配是串的一種重要運(yùn)算

C. 空串是由空格構(gòu)成的串 ? ? ? D. 串既可以順序存儲(chǔ)，也可以鏈?zhǔn)酱鎯?chǔ)

解析：空串表示所含字符數(shù)為0的串?？崭翊硎局缓崭竦拇?/p>

?

15. 已知廣義表LS＝((a, b, c), (d, e, f))，運(yùn)用head和tail函數(shù)取出LS中原子e的運(yùn)算是（?head(tail(head(tail(LS))))?? ）。

A. head(tail(LS)) ? ? ? ? ? ? ? ? ? ?B. tail(head(LS))

C. head(tail(head(tail(LS))))?? ? ? ? ? ?D. head(tail(tail(head(LS))))

解析：

若廣義表Ls非空(n≥1)，則a?l?是LS的表頭，其余元素組成的表(?a?2?，a3,…，a?n?)稱為L(zhǎng)s的表尾。

任何一個(gè)非空廣義表的表頭是表中第一個(gè)元素，它可以是原子，也可以是子表，而其表尾必定是子表。?

tail(LS)=((d,e,f))?

head(tail(LS))=(d,e,f) ? ? ? ?[！有兩層括號(hào)，所以=（d,e,f),不=d]

tail(head(tail(LS) )) = (e,f) ? ? ?[表尾必定是子表]

head(tail( head(tail(LS) ))) = e?

?

?

16. 下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（?{11,10,001,101,0001}??）。

A. {0,10,110,1111} ? ? ? ? ? ? ? ? ? B. {11,10,001,101,0001}

C. {00,010,0110,1000} ? ? ? ? ? ? ? ?D. {b,c,aa,ac,aba,abb,abc}

解析：前綴編碼,在一個(gè)字符集中,任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴。

? ? B中10是101的前綴，所以不是前綴編碼。

?

17. 若已知一個(gè)棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3,…,pn，若pn是n，則pi是（?n-i+1?）。

A. i ? ? ? ? ? ? ? ? B. n-i ? ? ? ? ? ?C. n-i+1 ? ? ? ?D. 不確定

?

解析：由棧的先進(jìn)后出原則?

P1——Pi——Pn?

1--—n-i+1—-n

?

18. 若已知一個(gè)棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3,…,pn，若p1是3，則p2是（ ?不可能是1??）。

A.一定是2 ? ? ? ? ? B.一定是1 ? ? ? C. 不可能是1 ?D. 以上都不對(duì)

解析：若第一個(gè)輸出的是3，說明前面的1,2都有入棧且沒有出棧，要想讓1出棧，則必須2先出棧（p2=2,p3=1)。

?

19. 假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素，其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（?(rear-front+m)%m?? ）。

A. (rear-front+m)%m ? ? ? ? ? ?B. rear-front+1

C. (front-rear+m)%m ? ? ? ? ? ?D. (rear-front)%m

?

20. 用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)（?隊(duì)頭、隊(duì)尾指針都可能要修改?? ）。

A. 僅修改隊(duì)頭指針 ? ? ? ? ? ? B. 僅修改隊(duì)尾指針?

C. 隊(duì)頭、隊(duì)尾指針都要修改 ? ? D. 隊(duì)頭、隊(duì)尾指針都可能要修改

?

21. ?空串與空格串的區(qū)別在于（ ??兩串包含的字符不相同?）。

A. 沒有區(qū)別 ? ? ? ? ? ? ? ? ? ?B. 兩串的長(zhǎng)度不相等

C. 兩串的長(zhǎng)度相等 ? ? ? ? ? ? ?D. 兩串包含的字符不相同

解析：空串表示所含字符數(shù)為0的串?？崭翊硎局缓崭竦拇?/p>

?

22. 在線索二叉樹中，某結(jié)點(diǎn)*p沒有右孩子的充要條件是（?p->rtag==1??）。

A. p->rchild==NULL ? ? ? ? ? ? ? ?B. p->rchild!=NULL

C. p->rtag==1 ? ? ? ? ? ? ? ? ? ? ?D. p->rtag==0

解析：p->rchild線索化后已經(jīng)指向結(jié)點(diǎn)，所以判斷p->rchild沒用.AB錯(cuò)誤

? ??

?

23.?若一棵二叉樹有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)有（?11??）個(gè)。

? ?解析：N0=N2+1?

A. 9 ? ? ? ? ? ? ?B. 11 ? ? ? ? ? ? ?C. 15 ? ? ? ? ? ? D. 不確定

?

24. 有關(guān)二叉樹下列說法正確的是（ ?一棵二叉樹的度可以小于2??）

A. 二叉樹的度為2 ? ? ? ? ? ? ? ? ? B. 一棵二叉樹的度可以小于2

C. 二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 ? D. 二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2

?

25. 具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有（?5???）條邊才可能是一個(gè)連通圖。

A. 5 ? ? ? ? ? ? ?B. 6 ? ? ? ? ? ? ?C. 7 ? ? ? ? ? ? ?D. 8

?

26.?圖的深度優(yōu)先遍歷算法類似于二叉樹的（先序遍歷?? ?）算法。

A.?先序遍歷?? ??B. 中序遍歷??? ? ? C. 后序遍歷??? ?D. 層次遍歷

?

27. 下列關(guān)于最小生成樹的說法中，正確的是（ ?僅I???）。

I. 最小生成樹的代價(jià)唯一。

II. 權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹中。

Ⅲ. 用Prim算法從不同頂點(diǎn)開始構(gòu)造的所有最小生成樹一定相同。

Ⅳ. 使用Prim算法和Kruskal算法得到的最小生成樹總不相同。

A.?僅I??? ? ? ? ? B. 僅II ? ? ? ? ? C. 僅I 、III ? ? ? ?D. 僅II 、Ⅳ

解析：Ⅰ.最小生成樹不唯一，但最小生成樹的代價(jià)唯一（易錯(cuò)）

? ? ?Ⅱ.如果加入權(quán)值最小的邊構(gòu)成環(huán)，則權(quán)值最小的邊不存在于最小生成樹中

? ? ?Ⅲ.設(shè)N個(gè)結(jié)點(diǎn)構(gòu)成環(huán)，N-1條邊權(quán)值相等，則從不同的頂點(diǎn)開始Prim算法會(huì)得到N- 1種不同的最小生成樹

Ⅳ.當(dāng)最小生成樹唯一時(shí)（各邊的權(quán)值不同），普里姆算法和克魯斯卡爾算法得到的最小生成樹相同

28. 有一個(gè)有序表為{1, 3, 9，12，32，41，45，62，75，77，82，95，100}， 當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，（ ?4??）次比較后查找成功。

A.1 ? ? ? ? ? ? B.2 ? ? ? ? ? C.4 ? ? ? ? ?D.8

?

29. 對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（?以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列?）。

A.以順序方式存儲(chǔ). ? ? ? ? ? ?B.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列

C.以鏈接方式存儲(chǔ) ? ? ? ? ? ? D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列

解析：二分查找通過左右端數(shù)據(jù)相加除以2求出中點(diǎn)位置mid，然后將要查找的數(shù)值與中點(diǎn)位置比較，小于中點(diǎn)，右端點(diǎn)變?yōu)閙id-1，否則左端點(diǎn)變?yōu)閙id+1。所以要求線性表是順序存儲(chǔ)結(jié)構(gòu)且要有序。

?

30. 設(shè)一維數(shù)組中有n個(gè)元素，則讀取第i個(gè)元素的平均時(shí)間復(fù)雜度可表示為（?O(1)???? ）。

A.O(n2) ? ? ? B.O(nlog2n) ? ? ? ? ?C.O(1) ? ? ? ? D.O(n)

解析：數(shù)組是讀取數(shù)組下標(biāo)（沒有循環(huán)），數(shù)組下標(biāo)為常數(shù)，所以為O(1)

?

?

判斷題

1.（ ?×??） 算法原地工作的含義是不需要任何額外的輔助空間。

? ? ? ? ? ? ? ??解析：算法原地工作的含義是指不需要任何額外的輔助（！不是輔助空間），算法所需要的輔助空間不隨著問題的規(guī)模而變化，是一個(gè)確定的值。

2.（ ?√??） 數(shù)據(jù)的定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，其實(shí)現(xiàn)要基于某種存儲(chǔ)結(jié)構(gòu)。

3.（ ?×??） 鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。

解析：還方便了對(duì)鏈表的開始結(jié)點(diǎn)插入或刪除操作。

4.（ ?√??） 線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)之間的存儲(chǔ)空間可以是不連續(xù)的。

5.（ ?×?? ） 若輸入序列為1,2,3,4,5,6，則通過一個(gè)?？梢暂敵鲂蛄?,5,4,6,2,3。

? ? ? ? ? ? ?解析：棧是先進(jìn)后出，由1546可知：SXSSSSXXSX（1進(jìn)棧，1出棧，2進(jìn)棧，3進(jìn)棧，

4進(jìn)棧，5進(jìn)棧，5出棧，6進(jìn)棧，6出棧）。若之后2要想出棧，則必須3先出棧。

6.?（ ?×??） 通常使用隊(duì)列來處理函數(shù)或過程的調(diào)用。

解析：用堆棧來處理函數(shù)調(diào)用，函數(shù)調(diào)用過程中把參數(shù)壓入堆棧保存,執(zhí)行完畢后彈出??堆棧釋放。

7.（ ?√?? ） 兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。

8.（ ?√?? ） 兩個(gè)棧共用靜態(tài)存儲(chǔ)空間，棧頂相對(duì)使用就可以避免空間溢出問題。

9.（ ?√?? ） 隊(duì)列是插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出結(jié)構(gòu)。

10.（ ?√??） 如果表示圖的鄰接矩陣是對(duì)稱矩陣，則該圖一定是無向圖。

11.（ ?√?）?在圖的深度優(yōu)先遍歷中一般要采用棧來暫存剛訪問過的頂點(diǎn)。

12.（ ?×??） 在表示某工程的AOE網(wǎng)中，加速其關(guān)鍵路徑上的任意關(guān)鍵活動(dòng)均可縮短整個(gè)工程的完成時(shí)間。

解析：存在多個(gè)關(guān)鍵路徑（存在并行的關(guān)鍵活動(dòng)）時(shí)，縮短關(guān)鍵活動(dòng)需使所有關(guān)鍵路徑都縮短。

13.（ ?√?） 在有向圖中，各頂點(diǎn)的入度之和等于各頂點(diǎn)的出度之和。

14.（ ?×?）?連通分量是無向圖中的極小連通子圖。

解析：連通分量，是指無向圖的極大連通子圖

15.?（ ?×??） 對(duì)n個(gè)頂點(diǎn)的連通圖G來說，如果其中的某個(gè)子圖有n個(gè)頂點(diǎn)、n-1條邊，則該子圖一定是G的生成樹。

16.（ ?√??） 無論是有向圖還是無向圖，其鄰接矩陣表示都是唯一的。

?

?

?

?

解答題

1. 設(shè)二叉樹BT的存儲(chǔ)結(jié)構(gòu)如下：

1 ? ? 2 ? ? 3 ? ?4 ? ? 5 ? ? 6 ? ?7 ? ? 8 ? ? 9 ? 10

其中BT為樹根結(jié)點(diǎn)的指針，其值為6，Lchild和Rchild分別為結(jié)點(diǎn)的左、右孩子指針域，data為結(jié)點(diǎn)的數(shù)據(jù)域。試完成下列各題：

（l）畫出二叉樹BT的邏輯結(jié)構(gòu)；答案

（2）寫出按前序、中序、后序遍

歷該二叉樹所得到的結(jié)點(diǎn)序列；

（3）畫出二叉樹的后序線索二叉樹。

?

?

?

?

?

?

?

?

2．設(shè)一棵二叉樹的先序遍歷序列：ABDFCEGH，中序遍歷序列：BFDAGEHC。

（1）畫出這棵二叉樹；

（2）畫出這棵二叉樹的后序線索二叉樹；

（3）將這棵二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹（或森林）。

答案：

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

3．將關(guān)鍵字序列(7、8、30、11、18、9、14)散列存儲(chǔ)到散列表中，散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開始的一個(gè)一維數(shù)組，散列函數(shù)為：H(key)=(key×3)% 7，處理沖突采用線性探測(cè)法，要求裝載因子為0.7。

（1）請(qǐng)畫出所構(gòu)造的散列表。

（2）分別計(jì)算等概率情況下，

查找成功和查找不成功的

平均查找長(zhǎng)度。

答案：

?

?

?

?

?

?

?

?

?

4．?給定帶權(quán)無向圖G。（P280，圖8.24）?? ? ? ? ? ?

? 答案:

（1）畫出該圖的鄰接表存儲(chǔ)結(jié)構(gòu)。

（2）根據(jù)該圖的鄰接表存儲(chǔ)結(jié)構(gòu)，從頂點(diǎn)3發(fā)，調(diào)用DFS和BFS算法遍歷該圖，給出相應(yīng)的遍歷序列。

（3）給出

采用Kruskal

算法構(gòu)造最小

生成樹的過程。

?

?

?

?

?

5．一棵二叉樹的先序、中序、后序序列如下，其中一部分未標(biāo)出，請(qǐng)構(gòu)造出該二叉樹。

先序序列：A?B?C D E?F?G H I?J?K??（可填入字母：A,B,F,J）

中序序列：C B?E?D?F A?H?J K I G ???(可填入字母：D,E,H)

后序序列：C?E F D B?K?J I H?G?A ???(可填入字母：C,G,K)

答案：

（填序列）

1 先判斷各序列剩余的可填入字母

2 由后序知A為根節(jié)點(diǎn)（若先序中第一個(gè)字母為A,也可判定A為根節(jié)點(diǎn)）

（由于節(jié)點(diǎn)數(shù)大于2個(gè)，則B是A的左孩子結(jié)點(diǎn)）

3 由2可將中序劃分成A的左右側(cè)（二叉樹的左右子樹與中序的左右字母相同→中序H位置確定）

4?在中序，C在B的左側(cè)→則C必在A的左子樹→在后序，B在中間位置→后序C位置確定

5?（（中序知，F(xiàn)在左子樹上）且（后序知，E在F之前））→先序F位置確定→先序只剩J，則先序J位置確定

6?（（先序中，DEF緊挨）且（后序中，EFD緊挨）且（中序中只剩D,E字母））→中序D,E位置確定

7?由完整先序序列知，GHIJK在右子樹上，且G為A的右孩子結(jié)點(diǎn)→后序G位置確定→后序K位置確定

（構(gòu)造二叉樹）

A為根節(jié)點(diǎn)，B,C,D,E,F為左子樹 G,H,I,J,K為右子樹

A,B,G的位置由上述中2，7步確定

?（左子樹）

在中序，CB緊挨→C為B的左孩子

在后序，DB緊挨且C在最左→D為B的右孩子

在中序，EDF緊挨→E,F為D的左右孩子

?（右子樹）

（（在先序，GH緊挨）且（在中序，HJKI在G的左側(cè)））→H為G的左子樹

（（在先序，HI緊挨）且（在后序，IH緊挨））→I為H的右子樹

（（在先序，IJ緊挨）且（在中序，JK在G的左側(cè)））→J為I的左子樹

（（在先序，JK緊挨）且（在后序，KJ緊挨））→K為J的右子樹

?

?

?

6．假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07、0.19、

0.02、0.06、0.32、0.03、0.21和0.10。（P240）

（1）試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼，求出WPL；

（2）試設(shè)計(jì)另一種由二進(jìn)制表示的等長(zhǎng)編碼方案，并求出該編碼的平均長(zhǎng)度。

?

?

?

?

?

?

?

?

?

?

?

?

?

?

??

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

7．對(duì)于有向無環(huán)圖：

（1）敘述求拓?fù)溆行蛐蛄械牟襟E。

（2）對(duì)于圖G（P303），寫出它的3個(gè)不同的拓?fù)湫蛄小?/p>

答案：

（1）1 從有向圖中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)（即入度為0的頂點(diǎn)）并且輸出它。

?????2 從圖中刪去該頂點(diǎn)，并且刪去從該頂點(diǎn)發(fā)出的全部有向邊

????3 重復(fù)上述兩步，直到剩余的圖中不再存在沒有前驅(qū)的頂點(diǎn)為止

??（2）由（1）可知，拓?fù)湫蛄锌蔀椋?/p>

???041253 ?041523 ?045123 ?450123 ?401253 ?405123 ?401523

?

?

?

?

?

?

8.假設(shè)一棵二叉排序樹的關(guān)鍵字為單個(gè)字母，其后序遍歷序列為 ACDBFIJHGE.

（1）畫出該二叉排序樹；?? ? ? ?答案:

（2）求在等概率下的查找成功的平均查找長(zhǎng)度。

（3）求在等概率下的查找不成功的平均查找長(zhǎng)度。

?

?

?

?

?

?

?

?

算法設(shè)計(jì)

1．已知順序表L的所有元素按其值非遞增有序排列，設(shè)計(jì)算法刪除表中值相同的多余元素。

typedef ?struct?

? ? ?{???ElemType data[MaxSize];?? ? /* 存放順序表元素*/ ?

????? ? ?int length; ? ? ? ? ? ? ? ???/* 存放順序表的長(zhǎng)度*/ ?

? ? ?} SqList; ? ? ? ? ? ? ? ? ??? ?/* 順序表的類型定義*/ ?

?

?

?

?

?

?

?

?

? ?

?

?

?

?

?

?

?

?

?

?

?

?

2.?已知單鏈表L中各元素的值互異，設(shè)計(jì)算法判斷單鏈表L是否按結(jié)點(diǎn)值遞增有序排列。

?

3. 設(shè)ha=(a1,a2,…,an)和hb=(b1,b2,…,bn)是兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表，請(qǐng)完成下列算法，實(shí)現(xiàn)將這兩個(gè)表合并成一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表hc的功能。

void Merge(LinkList *ha, LinkList *hb, LinkList *&hc)

{??LinkList *p=ha->next;

hc=ha;

while (???p->next!=ha?? ?) ? ? /* 找到ha的尾結(jié)點(diǎn)p */

??? ??p=p->next?? ?

? ? ??p->next=ha-next?? ??? ? ? ? ? /* 將結(jié)點(diǎn)p的next指向hb的開始結(jié)點(diǎn) */

while (?? ? ?p->next!=hb???? ?) ? ? /* 找到hb的尾結(jié)點(diǎn)p */

?p=p->next;

? ??p->next=hc?? ??? ? ? ? ? /* 構(gòu)成循環(huán)單鏈表 */

free(hb); ? ? ? ? ? ? ? /* 釋放hb單鏈表的頭結(jié)點(diǎn) */

}文章來源地址http://www.zghlxwxcb.cn/news/detail-824811.html

?

?

?

?

?

4．已知線索二叉樹中的結(jié)點(diǎn)類型TBTNode的聲明如下：

typedef struct node

{ ???ElemType ?data; ? ? ? /*數(shù)據(jù)域*/

???int ?ltag, rtag; ? ? ? ? /*左、右線索標(biāo)志域*/

???struct node ?*lchild; ? /*左孩子鏈域或指向前驅(qū)的線索*/

???struct node ?*rchild; ? /*右孩子鏈域或指向后繼的線索*/

} TBTNode;

完成下面的算法，實(shí)現(xiàn)在中序線索二叉樹中找結(jié)點(diǎn)p的中序前驅(qū)，返回前驅(qū)結(jié)點(diǎn)的指針。

TBTNode?*?1Inprior(TBTNode *p) /*中序線索二叉樹中查找結(jié)點(diǎn)p的直接前驅(qū)*/

{ ??? ??TBTNode?*pre?;?? ?

? ?if(p->ltag==1) ?pre=p->lchild; ? ?

? ?else ? ? ? ? ? ? ? ? ? ? ? ??

? ?{ ??? ??pre=p->lchild;???? ??

? ? ? ?while (pre->rtag==0) ? ? ?

? ? ? ? ? ???pre=pre->rchild;?????

? ?}

? ?return pre;

}

?

?

?

5．設(shè)計(jì)在二叉排序樹t中查找特定元素(值為x)的算法SearchBST(t, x)。

typedef struct node

{ ?KeyType ? key;

InfoType ? data;

Struct node ?*lchild,*rchild;

}BSTNode;

BSTNode ?*searchBST(BSTNode ?*t, KeyType x)

{

if(t==NULL || t->key==x)

??return t;

if(k<t->key)

return ?searchBST(t->lchild,?x);

else

return ?searchBST(t->rchild,?x);

}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)期末考試題庫的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！