計(jì)算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料

計(jì)算機(jī)科學(xué)與技術(shù)《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料1

一、填空題

1.若規(guī)定二叉樹根結(jié)點(diǎn)的層次為1,則第4層上最多有個(gè)結(jié)點(diǎn)。

2.具有N個(gè)結(jié)點(diǎn)的無向完全圖共有條邊。

3.樹轉(zhuǎn)換為二叉樹;其根結(jié)點(diǎn)的子樹一定為空。

4.對(duì)一棵二叉排序樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)o

5.已知二維數(shù)組a[10][8]采用行優(yōu)先存儲(chǔ)方式，每個(gè)元素占2個(gè)存儲(chǔ)單元，第一個(gè)元素的

存儲(chǔ)地址是1012,則元素a[4][5]的存儲(chǔ)地址為()0

6.快速排序在平均情況下的時(shí)間復(fù)雜度為,在最壞情況下的時(shí)間復(fù)雜度為o

7.畫出具有3個(gè)結(jié)點(diǎn)的二叉樹的所有形態(tài)：o

8.對(duì)于一個(gè)單鏈接存儲(chǔ)的線性表，假定表頭指針指向鏈表的第一個(gè)結(jié)點(diǎn)，則在表頭插入結(jié)點(diǎn)

的時(shí)間復(fù)雜度為，在表尾插入結(jié)點(diǎn)的時(shí)間復(fù)雜度為o

9.數(shù)據(jù)結(jié)構(gòu)課程是研究數(shù)據(jù)的、、等三個(gè)方面的內(nèi)容。

10.已知完全二叉樹的第8層有8個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是o

二、應(yīng)用題

1.已知二叉樹的中序遍歷序列和后序遍歷序列分別為CBEDAFIGH和CEDBIFHGA,試構(gòu)造該二

叉樹。

2.若一個(gè)圖的邊集為{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)},從頂點(diǎn)A開始分別

對(duì)該圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索，要求頂點(diǎn)值小的鄰接點(diǎn)被優(yōu)先訪問，則寫出得到

的深度優(yōu)先搜索和廣度優(yōu)先搜索的頂點(diǎn)序列。

3.下圖所示是一個(gè)無向帶權(quán)圖，請(qǐng)按Prim算法求最小生成樹。

4.給定數(shù)據(jù)元素系列為{47,23,2,15,98,57,22,6,12},請(qǐng)寫出直接選擇排序各趟的

結(jié)果。

5.已知散列函數(shù)H(k)=kmod12,鍵值序列為(25,37,52,43,84,99,120,15,26,11,70,82),

采用拉鏈法處理沖突，試構(gòu)造開散列表，并計(jì)算查找成功的平均查找長度。

答案

一、填空題

1.8

2.N(N+l)/2

3.右子樹

4.有序序列

5.1050.

6.O(log2n),O(log2n)

7.

8.0(1),0(n)

9.操作對(duì)象、關(guān)系、操作

10.68

二、應(yīng)用題

1.二叉樹的構(gòu)造過程如圖:

2.深度優(yōu)先搜索得到的頂點(diǎn)序列:A,B,D,E,F,C

廣度優(yōu)先搜索得到的頂點(diǎn)序列：A,B,C,D,F,E

3.解答：按Prim算法求最小生成樹的過程如下:

4.解答:

初始:47,23,2,15,98,57,22,6,12.

第一趟:2,[23,47,15,98,57,22,6,12]

弟人人?一—.趟主業(yè):2,6,[47,15,98,57,22,23,12]

第三趟:2,6,12,[15,98,57,22,23,47]

第四趟:2,6,12,15,[98,57,22,23,47]

第五趟:2,6,12,15,22,[57,98,23,47]

第六趟:2,6,12,15,22,23,【98,57,47]

第七趟:2,6,12,15,22,23,47,[57,98]

第八趟:2,6,12,15,22,23,47,57,[98]

最后所得：2,6,12,15,22,23,47,57,98

5.解答:H(25)=l,H(37)=l,H(52)=4,H(43)=7,H(84)=0,H(99)=3,H(120)=0,H(15)=3,

H(26)=2,H(ll)=ll,H(70)=10,H(82)=10o構(gòu)造的開散列表如下:

0

1

2

3

4

5

6

7

8

9

10

11

計(jì)算機(jī)科學(xué)與技術(shù)《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料2

一、應(yīng)用題

1.對(duì)給定的一組權(quán)值W=(5,2,9,11,8,3,7),試構(gòu)造相應(yīng)的哈夫曼樹，并計(jì)算它的

帶權(quán)路徑長度。

2.若一個(gè)圖的邊集為{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)},從頂點(diǎn)A開始分別

對(duì)該圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索，要求頂點(diǎn)值小的鄰接點(diǎn)被優(yōu)先訪問，則寫出得到

的深度優(yōu)先搜索和廣度優(yōu)先搜索的頂點(diǎn)序列。

3.已知一組元素為(46,25,78,62,12,37,70,29),試畫出按元素排列次序插入生成的一棵二

叉排序樹。

4.給定數(shù)據(jù)元素系列為{47,23,2,15,98,57,22,6,12},請(qǐng)寫出直接選擇排序各趟的

結(jié)果。

5.設(shè)散列表的長度m=13；散列函數(shù)為H(K)=Kmodm,給定的關(guān)鍵碼序列為19,14,23,01,

68,20,84,27,55,11,試畫出用線性探查法解決沖突時(shí)所構(gòu)造的散列表。

二、算法設(shè)計(jì)題

1.設(shè)計(jì)一個(gè)算法，在順序線性表L中刪除第i個(gè)元素，并返回其值。

答案

一、應(yīng)用題

1.構(gòu)造的哈夫曼樹如圖:

樹的帶權(quán)路徑長度為：WPL=2X4+3X4+5X3+7X3+8X3+9X2+11X2=120

2.深度優(yōu)先搜索得到的頂點(diǎn)序列：A,B,D,E,F,C

廣度優(yōu)先搜索得到的頂點(diǎn)序列：A,B,C,D,F,E

4.解答:

初始:47,23,2,15,98,57,22,6,12.

第一趟：2,[23,47,15,98,57,22,6,12]

第二趟：2,6,[47,15,98,57,22,23,12]

第三趟：2,6,12,[15,98,57,22,23,47]

第四趟:2,6,12,15,[98,57,22,23,47]

第五趟：2,6,12,15,22,[57,98,23,47]

第六趟：2,6,12,15,22,23,【98,57,47]

第七趟:2,6,12,15,22,23,47,【57,98]

第八趟:2,6,12,15,22,23,47,57,[98]

最后所得：2,6,12,15,22,23,47,57,98

5.解答：

設(shè)散列表的長度m=13；散列函數(shù)為H(K)=Kmodm,給定的關(guān)鍵碼序列為

19,14,23,01,68,20,84,27,55,11,則有

H(19)=6,成功;H(14)=l,成功;H(23)=10,成功;

H(01)=l,沖突,=2,成功;H(68)=3,成功;H(20)=7,成功;

H(84)=6,沖突,沖突，=8,成功;

H(27)=1,沖突,=2,沖突，=3,沖突，=4,成功;

H(55)=3,沖突,=4,沖突，=5,成功;H(ll)=ll,成功。

0123456789101112

14016827551920842311

⑴(2)(1)(4)(3)(1)(1)(3)(1)⑴

二、算法設(shè)計(jì)題

1?【解答】

StatusListDelete_Sq(SqList&L,inti,ElemType&e)

(

if(i<l|i>L.length)teturnERROR;

p=&L.elem[i-l];

e=*p;

q=L.elem+L.length-1;

for(++p;p<=q;++p)*(p+l)=*p;

一L.length;

returnOK;

計(jì)算機(jī)科學(xué)與技術(shù)《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料3

一、應(yīng)用題

1.對(duì)于下列二叉樹，請(qǐng)寫出:

(1)前、中、后序遍歷次序;

(2)中序線索二叉樹；

2.若一個(gè)圖的邊集為{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)},從頂點(diǎn)A開始分別

對(duì)該圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索，要求頂點(diǎn)值小的鄰接點(diǎn)被優(yōu)先訪問，則寫出得到

的深度優(yōu)先搜索和廣度優(yōu)先搜索的頂點(diǎn)序列。

3.給定葉子結(jié)點(diǎn)的權(quán)值{1,4,6,2,9},請(qǐng)構(gòu)造哈夫曼樹，并給出葉子結(jié)點(diǎn)的哈夫曼編碼。

4.已知一組記錄為(46,74,53,14,26,38,86,65,27,34),給出采用快速排序法進(jìn)行排序時(shí)每

一趟的排序結(jié)果。

5.設(shè)散列表的長度m=13；散列函數(shù)為H(K)=Kmodm,給定的關(guān)鍵碼序列為

19,14,23,01,68,20,84,27,55,11,試畫出用線性探查法解決沖突時(shí)所構(gòu)造的散列表。

二、算法設(shè)計(jì)題

1、設(shè)計(jì)一個(gè)算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。

答案

一、應(yīng)用題

1.(1)前序遍歷次序：ABDGCEFH

中序遍歷次序：DGBAECHF

后序遍歷次序：GDBEHFCA

(2)中序線索二叉樹

2.深度優(yōu)先搜索得到的頂點(diǎn)序列：A,B,D,E,F,C

廣度優(yōu)先搜索得到的頂點(diǎn)序列：A,B,C,D,F,E

3.解答：

各符號(hào)的哈夫曼編碼為:1:000；2：0001；4：001；6：01；9：1

4.解答:

初始：[46745314263886652734]

第一趟：[3414263827]46[86655374]

第二趟：[271426]343846[746553]86

第三趟：[2614]27343846[5365]7486

第四趟：14262734384653657486

5.解答：

設(shè)散列表的長度m=13；散列函數(shù)為H(K)=Kmodm,給定的關(guān)鍵碼序列為

19,14,23,01,68,20,84,27,55,11,則有

H(19)=6,成功;H(14)=l,成功;H(23)=10,成功;

H(01)=l,沖突，=2,成功；H(68)=3,成功；H(20)=7,成功;

H(84)=6,