《數(shù)據(jù)結構》期末復習題-答案VIP

1.以下與數(shù)據(jù)的存儲結構無關的術語是（C）

C、哈希表

2.一個向量第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是（B）

B、108

3.假設帶頭結點的單向循環(huán)鏈表的頭指針為head,則該鏈表為空的判定條件是（C）

C、head-）next==head

4.若進棧序列為1,2,3,4,5,6,且進棧和出?？梢源┎暹M行，則不可能出現(xiàn)的出棧序列是（D）

D、2,3,5,1,6,4

5.下列關鍵字序列中，構成小根堆的是（A）

A、｛12,21,49,33,81,56,69,41）

6.下列數(shù)據(jù)結構中，不屬于二叉樹的是（A）

A、B樹

7.用順序存儲的方法來存儲一棵二叉樹，存放在一維數(shù)組A[1..N]中,若結點A[i]有右孩子，則其右孩子是（C）。

C、A[2i+l]

8.設樹T的高度為4,其中度為1、2、3、4的結點個數(shù)分別為4、2、1、1,則T中葉子數(shù)為（D）

D、8

9.有數(shù)據(jù)｛53,30,37,12,45,24,96）,從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，則應選擇下

面哪個序列輸入（B）

B、37,24,12,30,53,45,96

10.對下面有向圖給出了四種可能的拓撲序列，其中錯誤的是（C）

C、5,1,6,3,4,2

11.m階B-樹中所有非終端（除根之外）結點中的關鍵字個數(shù)必須大于或等于（B）

B、Lm/2]—1

12.散列文件也稱為（C）

B、索引文件

13.數(shù)據(jù)結構是（D）

D、相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合

14.從邏輯關系來看,數(shù)據(jù)元素的直接前驅為0個或1個的數(shù)據(jù)結構只能是（C）

C、線性結構和樹型結構

15.設p為指向雙向循環(huán)鏈表中某個結點的指針，p所指向的結點的兩個鏈域分別用p-llink和p-rlink表示，則同樣表示

P指針所指向結點的表達式是（D）

D、pfllinkfrlink

16.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間top[i]代表第i個棧（i=1,2）棧頂，棧1的底在v[l],棧2

的底在V[m],則棧滿的條件是（B）

B、top[l]+l=top[2]

17.若一棵二叉樹有11個葉子結點，則該二叉樹中度為2的結點個數(shù)是（A）

A、10

18.樹的先根序列等同于與該樹對應的二叉樹的（A）

A、先序序列

19.下面關于哈希（Hash,雜湊）查找的說法正確的是（C）

C、不存在特別好與壞的哈希函數(shù),要視情況而定

20.下列序列中，（D）是執(zhí)行第一趟快速排序后所得的序列。

D、[68,11,69,23,18][93,73]

21.下列關鍵字序列中，構成小根堆的是（D）

D、（15,28,46,37,84,58,62,41）

22.ISAM文件和VASM文件屬于（C）

C、索引順序文件

23.下面程序段的時間復雜度為（C）

for（i=0；i<m；i++）

for（j=0；j<n；j++）

A[i][j]=i*j;

C、O（m*n）

24.已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點.假設指針s指向另一個單鏈表中某個結點,則在s所指結

點之后插入上述鏈表應執(zhí)行的語句為（A）

A、q->next=s->next；s->next=p；

25.為便于判別有向圖中是否存在回路，可借助于（D）

D、拓撲排序算法

26.若以S和X分別表示進棧和退棧操作，則對初始狀態(tài)為空的棧可以進行的棧操作系列是（D）

D、SSSXXSXX

27.設有一順序棧S,元素si,s2,s3,s4,s5,s6依次進棧，如果6個元素出棧的順序是s2,s3,s4,s6,s5,sl,則棧的容量

至少應該是（B）

B、3

28.假設以數(shù)組A[m]存放循環(huán)隊列的元素.已知隊列的長度為length,指針rear指向隊尾元素的下一個存儲位置,則隊頭元素

所在的存儲位置為（B）。

B、（rear-length+m）%m

29.在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結點s的操作為（D）。

D、rear->next=s;rear=s;

30.對于哈希函數(shù)H（key）=key%13,被稱為同義詞的關鍵字是（D）

D、25和51

31.采用二叉鏈表存儲的n個結點的二叉樹，共有空指針（A）個.

A、n+1

32.連通網(wǎng)的最小生成樹是其所有生成樹中（D）

D、邊的權值之和最小的生成樹

33.對記錄序列（314,298,508,123,486,145）依次按個位和十位進行兩趟基數(shù)排序之后所得結果為（B）

B、508,314,123,145,486,298

34.任何一個無向連通圖的最小生成樹（C）。

C、一棵或多棵

35.無向圖的鄰接矩陣是一個（C）

C、對稱矩陣

36.設無向圖G—=（V,E）和G，二（『，E，），如G'為G的生成樹，則下列說法中不正確的是（B）.B、G'為G連通分量

37.以vl為起始結點對下圖進行深度優(yōu)先遍歷，正確的遍歷序列是（D）

D、vl,v2,v5,v6,v7,v3,v4

38.下面幾個符號串編碼集合中，不是前綴編碼的是（B）

B、{0,1,00,11}

39.希爾排序的增量序列必須是（B）。

B、遞減的

40.采用起泡排序法對n個關鍵字進行升序排序，若要使排序過程中比較關鍵字的次數(shù)最多，則初始時的序列應滿足條件

（D）

D、關鍵字從大到小排列

41.在下列內部排序中（A）是不穩(wěn)定的。

A、希爾排序

42.分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是(C)。

A、(100,80,90,60,120,110,130)

43.在查找過程中，沖突指的是(C)。

C、不同鍵值對應相同的存儲地址

44.對有14個元素的有序表A[l。。14]作二分查找，查找元素A[4]時的被比較元素依次為(D)。

D、A[7],A[3],A[5],A[4]

45.以vl為起始結點對下圖進行廣度度優(yōu)先遍歷，正確的遍歷序列是(A)

A、vl,v2,v3,v4,v5,v6,v7

二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)

1.數(shù)據(jù)的物理結構包括數(shù)據(jù)元素的存儲和數(shù)據(jù)之間關系的存儲。

2.若一個算法中的語句頻度之和為T(n)=1921n+4nlogn,則算法的時間復雜度為皿n.

3.下面程序段的時間復雜度是_log3n_。

i=l;

while(i〈=n)i=i*3；

4.循環(huán)隊列用數(shù)組A[0oom-11存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列的元素個數(shù)是

(rear-front+m)%m

5.主要是使插入和刪除等操作統(tǒng)一

6.(n-1)12。

7.在單鏈表中設置頭結點的作用是深度優(yōu)先.

8.線性表L=(al,a2,…，an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是

相同值關鍵字.

9.已知一無向圖G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法

從頂點a開始遍歷圖，得到的序列為abecd,則采用的是前移遍歷方法。

10.如果排序過程不改變時間復雜度之間的相對次序,則稱該排序方法是穩(wěn)定的。

11.從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需一個位置。

12.當問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數(shù)量級被稱為算法的100

13.若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個數(shù)即為頂點vi的sxssxxssxssxxx.

14.一棵含999個結點的完全二叉樹的深度為120

15.假設S和X分別表示進棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX,貝岫“a*b+c/d”

得到“ab*cd/+”的操作序列為。

16.o如圖所示的有向無環(huán)圖可以排出L—〉next?>next==L

17.邊種不同的拓撲序列。

18.從空樹起，依次插入關鍵字11,27,35,48,52,66和73構造所得的二叉排序樹，在等概率查找的假設下，查找成功時

的平均查找長度為384.

19.帶頭結點的雙循環(huán)鏈表L中只有一個元素結點的條件是隊列。

20.求最小生成樹的克魯斯卡爾（Kruskal）算法耗用的時間與圖中邊稠密、邊稀疏的數(shù)目正相關。

21.已知一棵完全二叉樹中共有768結點，則該樹中共有5個葉子結點。

22.實現(xiàn)圖的廣度優(yōu)先搜索，除了一個標志數(shù)組標志已訪問的圖的結點外，還需要8、64存放被訪問的結點以實現(xiàn)遍歷.

23.Prim（普里姆）算法適用于求上匚_的網(wǎng)的最小生成樹；kruskal（克魯斯卡爾）算法適用于求上L的網(wǎng)的最小生成樹。

24.對長度為20的有序表進行二分查找的判定樹的高度為n—1。

25.設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為n,有個葉子結點.

26.高度為h的完全二叉樹中最少有棧個結點,最多有個結點。

27.設連通圖G中有n個頂點e條邊.則對應的最小生成樹上有3條邊.

28.構造n個結點的強連通圖，至少有0（I?）條弧。

29.表達式求值是（42,13,94,55,05,46,17）應用的一個典型例子。

30.設棧S和隊列Q的初始狀態(tài)為空，元素eLe2,e3,e4,e5,e6依次通過棧S,一個元素出棧后即進入隊列Q,若6個元素出

隊的序列是e2,e4,e3,e6,e5,el,則棧的容量至少應該是。

31.快速排序算法在最差的情況下其時間復雜度是o

32.對序列｛55,46,13,05,94,17,42）進行基數(shù)排序，第一趟排序后的結果是。

三、應用題（本大題共5小題，每小題6分，共30分）

1.已知二叉樹的先序遍歷序列ABCDEFGH,中序遍歷序列為CBEDFAGH,畫出二叉樹。

答案：二叉樹形態(tài)

2.如圖請給出鄰接表、鄰接矩陣及逆鄰接表。

（1）鄰接表：（注意邊表中鄰接點域的值是頂點的序號，這里頂點的序號是頂點的下標值一1）

vertexfirstedgenext

（2）逆鄰接表:

(3)

0101

0010

1000

0010

3.由字符集｛s,t,a,e,1｝及其在電文中出現(xiàn)的頻度構建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100,

請根據(jù)該哈夫曼樹進行譯碼，寫出原來的電文。

答案:原來的電文為：eatst

4.請畫出下圖所示的樹所對應的二叉樹，并寫出對應二叉樹的先序遍歷和中序遍歷。

答案:

先序遍歷為：12345687中序遍歷為：34867521

5.設散列表為HT[13],散列函數(shù)為H(key)=key%13。用閉散列法解決沖突，對下列關鍵碼序列12,23,45,57,

20,03,78,31,15,36造表。采用線性探查法尋找下一個空位，畫出相應的散列表，并計算等概率下搜索成功的平均搜

索長度。

答案：

使用散列函數(shù)H(key)=keymod13,有

H(12)=12,H(23)=10,H(45)=6,H(57)=5,

H(20)=7,H(03)=3,H(78)=0,H(31)=5,

H(15)=2,H(36)=10o

利用線性探查法造表：

0123456789101112

78150357452031233612

(1)(1)(1)(1)(1)(1)(4)(1)(2)(1)

搜索成功的平均搜索長度為

114

ASLsucc=----(1+1+1+1+1+1+4+1+2+1)=-----

1010

6.已知帶權圖G如圖所示，畫出圖G的一棵最小生成樹.

7.假設用于通信的電文由字符集｛a,b,c,d,e,f,g,h｝中的字母構成，這8個字母在電文中出現(xiàn)的概率分別為｛0。07,

0.19,0.02,0o06,0.32,0.03,0.21,0.10),請為這8個字母設計哈夫曼編碼。

1.00

0

O-4X0.60

^0^28?0.32

0.210.19o

V17'X11

少@Qo.05

0.100.070.06（/Al

??

哈夫曼編內樹0.030.02

哈夫曼編碼為：a：1001b：01c：10111d：1010e:llf：10110g:00h：1000

注意：答案不唯一

8.試用權集合｛12,4,5,6,1,2｝構造哈夫曼樹，并計算哈夫曼樹的帶權路徑長度。

h

300CD

WPL=12*1+(4+5+6)*3+(1+2)*4=12+，45+12=69

9.畫出與如圖所示森林對應的二叉樹。

吟

））??

答:

10.已知一個散列表如下圖所示:

0123456789101112

其散列函數(shù)為h(key尸key%13,處理沖突的方法為雙重散列法，探查序列為:

hi=(h(key)+1*hl(key))%m1=0,1,…，m-1

其中：hl(key)=key%ll+l

回答下列問題:

(1)對表中關鍵字35,20,33和48進行查找時，所需進行的比較次數(shù)各為多少？

(2)該散列表在等概率查找時查找成功的平均查找長度為多少？

答:

(1)對關鍵字35、20、33和48進行查找的比較次數(shù)為3、2、1、1；

…3+2+1+1+29

(2)平均查找長度ASL=--------------=-

55

11.請畫出與下列二叉樹對應的森林。

答:

12.對于給定結點的關鍵字集合K={5,7,3,1,9,6,4,8,2,10),

(1)試構造一棵二叉排序樹;

(2)求等概率情況下的平均查找長度ASL.

答:

5

(2)ASL=(1*1+2*2+3*4+4*3)/10=2.9

13.給出下圖對應的鄰接矩陣,并給出A,B,C三個頂點的出度與入度

答案：鄰接矩陣為：

ABCDEF

AFO00100

B101000

C000111

D000000

E110100

FLO10010

其中頂點A的入度為2,出度為1；

其中頂點B的入度為2,出度為2;

其中頂點C的入度為1,出度為3；

14.已知圖5.32如下所示，求從頂點a到其余各頂點的最短路徑。（給出求解過程）

5

答:

終點最短路徑求解過程

b6(a,b)5(a,c,b)

C3(a,c)

doo6(a,c,d)6(a,c,d)

eoo7(a,c,e)7(a,c,e)7(a,c,e)

fooooco9(a,c,d,f)9(a,c,d,f)

vjcbdef

S{a,c}{a,c,b}{a,c,d}{a,c,e}{a,c,d,f)

15.閱讀下列算法，并回答問題：

(1)假設串由合法的英文字母和空格組成，并以'\0作結束符。設串s="LJLIIIJamLJaLJLJLJstudent”(口表示空格符)，寫出f30

(s)的返回值；

(2)簡述算法f30的功能.

intf30(char*s)

答案：

(1)4

(2)算法功能：統(tǒng)計單詞的個數(shù)。

16.閱讀下列函數(shù)，并回答問題：

(1)假設隊列q中的元素為(a,b,c,d,e),其中“a”為隊頭元素。寫出執(zhí)行函數(shù)調用Conv(&q)后的隊列q；

(2)簡述算法Conv的功能。

答案：

(1)e,d,c,b,a

(2)將隊列里的值反轉

17.閱讀下列函數(shù)，并回答問題：

已知整形數(shù)組L[1。.8]中的元素依次為(19,18,15,17,16,13,12,10),閱讀下列函數(shù)，并寫出執(zhí)行函數(shù)調用sort(L,

8)時，對L進行的頭兩趟(pass分別為0和1)處理結果。

答案:

(1)第一趟(pass=0)1915181617121310

(2)第二趟(pass=1)1915161812171013

18.已知帶頭結點的單鏈表中的關鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設散列表的

長度為m,散列函數(shù)為Hash(key尸key%m。鏈表的結點結構為：.請在空缺處填入適當內容，使其成為一個完整算法。

keynext

答案：

(1)NULL(2)p—>next=H[j]p=q

19.下列函數(shù)的功能是,對以帶頭結點的單鏈表作為存儲結構的兩個遞增有序表(表中不存在值相同的數(shù)據(jù)元素)進行如下操

作：將所有在Lb表中存在而La表中不存在的結點插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填

入合適內容，使其成為一個完整的算法。

答案：

(1)pre-〉next=pb(2)pre->next=pa(3)pre-〉next=pb

20.閱讀算法f30,并回答問題：下列算法為有向圖拓撲排序，請在空缺處填入合適的內容，使其成為一個完整的算法。

答案：

(l)top=-1(2)top=graph[j].count(3)graph[k].count==0

21.閱讀算法131,并回答問題：下列算法功能為在數(shù)組a的前n(n>=l)個元素中找出第k(l〈=k<=n)小的值.這里假設數(shù)組

a中各元素的值都不相同。請在空缺處填入合適的內容，使其成為一個完整的算法。

答案：

(1)(i==k)return;(2)i+l(3)i—1

22.閱讀算法f33,并回答問題:下列算法功能為奇偶交換排序，思路如下：第一趟對所有奇數(shù)的i,將aLi]和a[i+l]進行

比較,第二趟對所有偶數(shù)的i,將a[i]和a[i+l]進行比較,每次比較時若a[i]〉a[i+1],將二者交換；以后重復上述二

趟過程，直至整個數(shù)組有序。請在空缺處填入合適的內容，使其成為一個完整的算法。

答案：

(l)a[i]=t(2)(i=2；i<=n;i+=2)(3)flag

四、算法設計題(本大題共2小題，每小題10分，共20分)

1.已知單鏈表的結點類型為Lnode,包含next和data成員。編寫算法，實現(xiàn)帶頭結點單鏈表的逆置算法。

參考答案:

voidinvent(Lnode*head)

(

Lnode*p,*q；

if(!head—〉next)returnERROR；

p=head—〉next；q=p->next;p->next=NULL;

while(q)

{p=q;q=q-)next；p->next=head->next;head—>next=p;}

)

2.編寫一個函數(shù)，要求借助一個棧把一個數(shù)組中的數(shù)據(jù)元素逆置。

其中，棧類型為SeqStack,可以直接使用InitStack(SeqStack**)、

Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函數(shù)。

參考答案：

voidInverse(ElemTypearr[],intn)

(

SeqStack*s；

inti;

InitStack(&s);

for(i=0；i〈n；i++)〃數(shù)組元素依次入棧

Push(s,arr[i])；

for(i=0;i<n;i++)〃棧中元素依次出棧，存入數(shù)組，是數(shù)組逆序

Pop(s,&arr[i])；

}

3.二叉樹采用鏈接存儲結構，結點類型為Btree,包括left、right和data三個成員，試設計一個算法計算一棵給定二叉樹的度

為2的結點的個數(shù)。

參考答案：

inttwochild(Btree*b)

{intnuml,num2;

if(b==NULL)return0；

else

{numl=twochild1(b一〉left)；

num2=twochildl(b—>right)；

if(b—>left!=NULL&&b—〉right!=NULL)return(numl+num2+l)；

elsereturn(numl+num2);

}

4.假設以帶雙親指針的二叉鏈表作為二叉樹的存儲結構，其結點結構的類型說明如下所示：

typedefcharDataType；

typedefstructnode{

DataTypedata;

structnode*lchild,^rchild；//左右孩子指針

structnode*parent；〃指向雙親的指針

}BinTNode;

typedefBinTNode*BinTree;

若px為指向非空二叉樹中某個結點的指針，可借助該結構求得px所指結點在二叉樹的中序序列中的后繼.

(1)就后繼的不同情況，簡要敘述實現(xiàn)求后繼操作的方法；

參考答案：

(1)分兩種情況討論

①當*px的右子樹不為空時，則從*px的右孩子開始，沿其左孩子往下查找，直到找到一個沒有左孩子的節(jié)點為止，則該

結點為*px在中序序列中的后繼；

②當*px的右孩子為空時，則沿*px的雙親指針鏈向上查找，直至找到其左子樹中包含*px的最年輕祖先，則該祖先結

點為*px在中序序列中的后繼.

(2)編寫算法求px所指結點的中序序列后繼,并在算法語句中加注注釋.

(2)BinTreef34(BinTreepx)

|

BinTreeq=px->rchild；

if(q!=NULL){〃沿左孩子往下查找

px=q；

while(px-)lchild!=NULL)

px=px->lchild；

}

else{〃沿雙親指針鏈向上查找

while(px!=NULL&&px—>rchild==q){

q=px；

px=px——>parent;

}

}

returnpx;〃返回所找到的中序序列后繼結點的指針

〃或者無后繼結點時返回空指針

5.已有鄰接表表示的有向圖，請編程判斷從第u頂點至第v頂點是否有簡單路徑，若有則印出該路徑上的頂點。

參考答案：

voidAllSPdfs(AdjListg,vertypeu,vertypev)

{〃求有向圖g中頂點u到頂點v的所有簡單路徑，初始調用形式：AllSPdfs(