數(shù)據(jù)結(jié)構(gòu)(c語言版)程海英-課后習(xí)題

1.解釋下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、線性結(jié)構(gòu)、算法、抽

象數(shù)據(jù)類型。

2.試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及運(yùn)算3方面的內(nèi)容。

3.選擇題

1）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。

A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的（）。

A.存儲(chǔ)結(jié)構(gòu)B.存儲(chǔ)實(shí)現(xiàn)

C.邏輯結(jié)構(gòu)D.運(yùn)算實(shí)現(xiàn)

3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（

）

O

A.數(shù)據(jù)具有同一特點(diǎn)

B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致

C.每個(gè)數(shù)據(jù)元素都一樣

D.數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等

4）以下說法正確的是（）。

A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位

B.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基木單位

C.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合

D.一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

5）以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)

A.樹B.字符串C.隊(duì)D.棧

4.填空題

1）數(shù)據(jù)結(jié)構(gòu)是

一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的以及它們之

I'可的和運(yùn)算等的學(xué)科。

2）數(shù)據(jù)結(jié)構(gòu)被形式定義為

（D,R）,其中D是________________________________________的有限集合，1^是口上的

___________有限集合。

3）數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的_、數(shù)據(jù)的和

數(shù)據(jù)的這

三個(gè)方面的內(nèi)容。

4)線性結(jié)構(gòu)中元素之間存在_________________關(guān)

系，樹形結(jié)構(gòu)中元素之間存在美

系，圖形結(jié)構(gòu)中元素之間存在關(guān)系。

5)一個(gè)算法的效率可分為效率和效率。

5.試分析下面各算法的時(shí)間復(fù)雜度。

1)x=90;y=100;

while(y>0)if(x>100){x=x-10;y-;Jelsex++;

2)for(i=0;ivn;i++)

forg=0;j<m;j++)a[i][j]=0;

3)for(inti=l;i<=n;i++)

for(intj=l；j<=i；j4-+)s++;

4)i=l;

while(i<二n)i=i*2;

5)i=O,sl=0,s2=0;

while(i++<n){

if(i%2)sl+=i;

elses2+=i；

)

6)x=n;//n>l

y=o；

while(x>=(y+l)*(y+1))y++;

A.q->next=p->next;p-next=q;

B.p?>next二q?>next;q=p;

C.q?>next=p?>next;p,>next二p,>next;

D?p->next=q->next;q->next=p;

4.填空題

1)順序表中訪問任意結(jié)點(diǎn)的時(shí)I'可

復(fù)雜度均為，順序表也稱為隨機(jī)存取的數(shù)

據(jù)結(jié)構(gòu)。

2)順序表中邏輯上相鄰的元素的物理

位置相鄰。單鏈表中邏輯上相鄰的元

素的物理位置___________相鄰。

3)在單鏈表中，

除了第一個(gè)結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由指示。

4)在n個(gè)結(jié)點(diǎn)的單

鏈表中要?jiǎng)h除已知結(jié)點(diǎn)汨，需找到它的，其時(shí)間更雜度

為0

5)

對(duì)于長度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為,

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

6)對(duì)于單鏈表，在表頭插

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

間復(fù)雜度為。

5.已知長度為n的線性表A采用順序存儲(chǔ)，編寫時(shí)間復(fù)雜度為。(n)、空間復(fù)雜度為

0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。

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

7.編寫在順序表和帶頭結(jié)點(diǎn)的單鏈表上，統(tǒng)計(jì)出值為x的元素個(gè)數(shù)的算法，統(tǒng)計(jì)結(jié)果由函數(shù)

值返回。

t編寫在順序表和帶頭結(jié)點(diǎn)的單鏈表上，刪除其值等于x的所有元素的算法。

1.棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)各有什么特點(diǎn)，什么情況下用到棧，什么情況下用到隊(duì)列？

2.設(shè)有編號(hào)為1、2、3、4的4輛車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，試寫出這4輛車開出

車站的所有可能的順序（每輛車可能人站，可能不入站，時(shí)間也可能不相同）。

3.選擇題

1）棧的插入和刪除操作在（）進(jìn)行。

A.棧頂B.棧底

C.任意位置D.指定位子

2）當(dāng)利用大小為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？?，則向這個(gè)棧插

入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行（）語句修改top指針。

A?top++;B.top-;

C?

top=0;D?top=N-l;

3）假定利用數(shù)組a[N]順序存儲(chǔ)一個(gè)棧，用top表示棧頂元素的下標(biāo)位置，用top==-1表示

?？?，用top==N-I表示棧滿，則該數(shù)組所能存儲(chǔ)的棧的最大長度為（

）

A.N-lB-N

C.N+lD.N+2

4）假定一個(gè)鏈接棧的棧頂指針用top表示，該鏈接棧為空的條件為（>°

A.top!=NULL;B.top==top->next;

C.top==NULL;D.top!=top->next;

5）在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的（）位置。

A.前一個(gè)B.后一個(gè)

C.當(dāng)前D.最后

6）當(dāng)利用大小為N的數(shù)組循環(huán)順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長度為（）

AM-9RM_1

C.ND.N+1

7）從一個(gè)循環(huán)隊(duì)列中刪除元素

時(shí)，首先需要（）。

A.前移隊(duì)首指針B.后移隊(duì)首指針

C.取出隊(duì)首指針?biāo)肝恢蒙系脑谼.取出隊(duì)尾指針?biāo)肝恢蒙系脑?/p>

8）假

定循環(huán)隊(duì)列的隊(duì)首和隊(duì)尾指針分別用f和I?表示，則判斷隊(duì)空的條件為（

）°

A.f+l==rB-r+1==f

C.f==0D-f==r

4.填空題

1)隊(duì)列的插入操作在_____________進(jìn)行，刪除操作在進(jìn)

行。

2)棧乂稱為表，隊(duì)列乂稱為表。

3)在一

個(gè)用一維數(shù)組a[N]表示的順序棧中，該棧所含元素的個(gè)數(shù)最少為個(gè)，

最多為O

4）假定一個(gè)鏈棧的棧頂指針為top,每個(gè)結(jié)點(diǎn)包含值域血ta和指針域next,當(dāng)進(jìn)行出棧

運(yùn)算時(shí)（假定棧非空），需要把棧頂指針top修改為的值。

5）在帶頭結(jié)點(diǎn)的非空循壞鏈隊(duì)中，假定隊(duì)首和隊(duì)尾指針分別為f和r,當(dāng)從中刪除一個(gè)

結(jié)點(diǎn)時(shí)，則需要將f->next賦值為的值。

6）假定front和rear分別為鏈隊(duì)的隊(duì)首和隊(duì)尾指針，則該鏈隊(duì)中只有一個(gè)結(jié)點(diǎn)的條件為

5.假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba'和'abcba'是回文，'abcde'和

<ababab,則不是回文。假設(shè)一字符序列己存入計(jì)算機(jī)，請(qǐng)分析用線性表、棧和隊(duì)列正確輸

出其回文的可能性？

6.假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧，編寫一個(gè)判別表達(dá)

式1p括弧是否正確配對(duì)的函數(shù)correct（exp,tag）；其中：exp為字符串類型的變量（可理

解為每個(gè)字符占用一個(gè)數(shù)組元素），表示被判別的表達(dá)式，tag為布爾型變量。

7.假設(shè)一個(gè)數(shù)組squLmJ存放循環(huán)隊(duì)列的元素。若要使這m個(gè)分量都得到利用，則需另一個(gè)

標(biāo)志tag,以lag為0或1來區(qū)分尾指針和頭指針值相同時(shí)隊(duì)列的狀態(tài)是“空”還是“滿”。

試編寫相應(yīng)的入隊(duì)和出隊(duì)的算法。

B.試寫一個(gè)算法，判別讀入的一個(gè)以“'為結(jié)束符的字符序列是否是“回文”。

1.選擇題

I）以下說法正確的是（）°

A.串是一種特殊的線性表B.串的長度必須大于零

C.串中的元素只能是字母D.空串就是空白串

2）設(shè)有一個(gè)字符串S二“WelcometoShenyang!”，問該串的長度為（

A.18B.19

C.20D.21

3）設(shè)有一個(gè)字符串S二%bcdefghA問該串的最大子串個(gè)數(shù)為（）。

A.8B.36

C.37D.9

4）兩個(gè)字符串相等的條件是（)0

A.兩串的長度相等

B.兩串包含的字符相同

C.兩串的長度相等，并且兩串包含的字符相同

D.兩串的長度相等，并且對(duì)應(yīng)位置上的字符相同

5）某串的長度小于一個(gè)常數(shù)，則采用（）存儲(chǔ)方式最節(jié)省空間。

A.鏈?zhǔn)紹.順序

C堆結(jié)構(gòu)D.無法確定

6）以下論述正確的是（>o

A?空串與空格串是相同的

B.“tel”是“Telcptone”白勺子串

C.空串是零個(gè)字符的串

D.空串的長度等于1）0

7）以甲i鰭基野的是C是空格串

A."BEIJING”是"BEIJING”的子串

“something”<"Somethig”

C?“BIT”二“BITE"

D.、

8）設(shè)有兩個(gè)串SI和S2,則StrCompare（SI,S2）運(yùn)算稱做）0

（B.模式匹配

A.串連接D.串比較

C.求子串>o

9）串的模式匹配是指（

A,判斷兩個(gè)串是否相等

B.對(duì)兩個(gè)串比較大小

C?找某字符在主串中第一次出現(xiàn)的位宜

D.找某子串在主串中第一次出現(xiàn)的第一個(gè)字符位置

10)若SubSlring(Sub,S,pos,1en)人示用Sub返向串S的笫pos個(gè)字符起長度為len的子串

的操作，則對(duì)于S="DataStructureSubString(Sub,S,6,3)的結(jié)果為()。

A."taStr"B."Str”

C?“mi”D.以上均不正確

11)若StrIndex(S,T)表示求T在S中的位置的操作,則對(duì)于S="BeijingandNanjing；

T="jing"，StrIndex(S,T)的結(jié)果為()。

A.2B.3C.4D.16

12)S二“moming”，執(zhí)行求子串函數(shù)SubStr(S,2,2)后的結(jié)果為()。

A.“mo”B."or"C."in”D.“ng”

13)SI="Good”,S2="Morning”,執(zhí)行串連接函數(shù)ConcatStr(S1,S2)后的結(jié)果為()。

A.”GoodMoming"B."GoodMorning"

C.”GOODMORNING"D."GOODMORNING”

14)SI二“good”,S2=morning”,執(zhí)行函數(shù)SubStr(S2,4,LenStr(S1))后的結(jié)果為(

)°

A.“good”B.“ning”C.“go"D.“mom”

15)設(shè)串SI二"ABCDEFG”,S2="PQRST”,則ConcatStr(SubStr(Sl,2,LenStr(S2))?

SubStr(S1,LenStr(S2),2)見勺結(jié)果串為()。

A.BCDEFB.BCDEFG

C-BCPQRSTD.BCDEFEF

2.填空題

1)字符串按存儲(chǔ)方式可以分為：順序存儲(chǔ)、鏈接存儲(chǔ)和。

2)在C語言中，以字符表示串值的終結(jié)。

3)空格串的長度等于。

4)在空串和空格串中，長度不為。的是o

5)兩個(gè)串相等是指兩個(gè)串長度相等，且對(duì)應(yīng)位置的o

6)設(shè)S二<kMymathei?'*則LenSlr(s)=。

7)兩個(gè)字符串分別為：$1=叮0<1@丫15”,$2="24網(wǎng)認(rèn)201叫(201^￡1「俗1,S2)的結(jié)果是：

X)假設(shè)有兩個(gè)字符串ST和$2,其中Sl=ltahcdxyzAS2=”g那么如果進(jìn)行了下而的運(yùn)算

StrCat(SubString(Sub,S1,3,2),SubString(Sub,SI,StrLength(S2),3)),其結(jié)果為

3.應(yīng)用題

1)下面程序是把兩個(gè)串rl和己首尾相連的程序，即：rl=rl+r2，試完成程序填空。typedef

struct{

charvecfMAXLEN];〃定義合并后串的最大長度

intlen;//len為串的長度

)Str;

voidConcatStr(Str*rl.Str*r2){〃字符串連接函數(shù)

inti;

pnnlf(<l%s,%s-\rl->vec,r2->vec);

if(rl->len+r2->len>(1))

printf(uH兩個(gè)串太長，溢出！”)；

else{

〃把己連接到

for(i二0:iv⑵；i++)rl

rl->vcc|1=r2->vec

〃添上字符串結(jié)束標(biāo)記

[i]；

〃修改新串長度

r1->vecFr1->len+il=⑷：

)

2)設(shè)x和y兩個(gè)串均采用順序存儲(chǔ)方式,，下面的程序是比較x和y兩個(gè)串是否相等的函

數(shù)，試完成程序填空。

#defineMAXLEN100

typedefstruct{

charvec|MAXLEN];

intlen;

}Str;

intsame(Str*x,*y){

inti=0,tag=l;

if(x->lcn(1)y->lcn)

return0;

else(

while(i<x->len￡2)lag){if(x->vec[il(3)y->vec[il)

⑸；

returntag;

)

}

3)編寫算法，求串S中所含不同字符的總數(shù)和每種字符的個(gè)數(shù)。

4)有兩個(gè)串SI和S2,設(shè)計(jì)一個(gè)算法，求一個(gè)串T,使其中的字符是S1和S2中的公共字

符。

1.選擇題

1)對(duì)于C語言的二維數(shù)組DataType

arr[m][n],每個(gè)數(shù)據(jù)元素占k個(gè)存儲(chǔ)單元，二維數(shù)組中任意元素arr[i,j]的存儲(chǔ)位置可由()

式確定。

A.Loc[i,j]=arr[m,n]+[(n+l)*i+j]*kB.Loc[i,j]=Loc[0,0]+[(m+n)*i+j]*k

C?Loc[i,j]=Loc[0,0]+[(n+l)*i+j]*kD.Loc[i,j]=[(n+l)*i+j]*k

2)數(shù)組air[0..5,0..6]的每個(gè)元素占五個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)

存單元中,則元素arrl5,5J的地址是()。

A.1175B.1180C.1205D.1210

3)A[N,N]是對(duì)稱矩陣，將下三角(含對(duì)角線)以行序存儲(chǔ)到一維數(shù)組arr[N(N+l)⑵中、

則對(duì)任一上三角元素arr[i,j]對(duì)應(yīng)air[k]的下標(biāo)k是()。

A.i*(i-l)/2+jB.j*(j-l)/2+iC.i*(j-l)/2+lD.j*(i-l)/2+l

4)稀疏矩陣的壓縮存儲(chǔ)方法是只存儲(chǔ)(

A.非零元素B.三元組(i,j,a?)C.砌D.i,j

5)對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是()。

A.便于輸入和輸111B.降低運(yùn)算的時(shí)[可復(fù)雜度

C.節(jié)省存儲(chǔ)空間D.便于進(jìn)行矩陣運(yùn)算

6)有一個(gè)100*90的稀疏矩陣，非零元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三

元組

表示該矩陣時(shí)，所需的字節(jié)數(shù)是(

A.18000B.60C.33D.66

7)已知廣義表LS二((a,b,c),(d,c,D),對(duì)其運(yùn)用Head和Tai】運(yùn)算，取出其中原子e的

運(yùn)算是()。

A.Hcad(Tail(LS))B?Head(Tail(Head(Tail(LS))))

C.Head(Tail(Tail(Head(LS))))D.Tail(Head(LS))

8)廣義表(3,b,c,d))的表頭是()，表尾是()0

A.aB.()C?(a,b,c,d)D.(b)

9)設(shè)廣義表L二((a.b,c)),則L的長度和度分別為()0

A.1和2B.1和3C.1和1D.2和3

2.數(shù)組、廣義表與線性表之間有什么用的關(guān)系？

3.特殊矩陣和稀疏矩陣，哪一種壓縮存儲(chǔ)后失去隨機(jī)存取的功能？為什么？

4.畫出廣義表((((a),b)),(((),d),(e,f)))的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)圖示。

5.設(shè)二維數(shù)組L.n]含有m*n個(gè)整數(shù)。

(1)寫出算法：判斷a中所有元素是否互不相同？輸出相關(guān)信息(yes/no)：

(2)試分析算法的時(shí)間復(fù)雜度。

1.分析樹結(jié)構(gòu)的特征，并舉例說明其實(shí)際的應(yīng)用。

2.試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。

3.一棵度為2的樹與一棵二叉樹有何區(qū)別？

4.選擇題

1）樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（）。

A.0B.1

C.-1D.2

2）在一棵樹中,）沒有前驅(qū)結(jié)點(diǎn)。

（B.葉子結(jié)點(diǎn)

A.樹枝結(jié)點(diǎn)D.空結(jié)點(diǎn)

3）在一棵樹中，每個(gè)結(jié)點(diǎn)最多有個(gè)前驅(qū)結(jié)點(diǎn)。

A.0B.1

C.2D.任意多個(gè)

4）在一棵二叉鏈表中，空指針域等于非空指針域數(shù)加

A.2B.1

C.0D.-1

5）在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)樹等于（

A,nB-n-1

C.n+1D.2n

6）在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹的第i層上，最多具有（）個(gè)結(jié)

，占、、、。

B.2i+-

7）在一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹中，該樹的深度為（

A.6B.7

C-5D.8

8）利用n個(gè)值造成的哈夫曼樹中共有（）個(gè)結(jié)點(diǎn)。

A?nB.n+1

C.2nD.2n-l

9）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（

A.唯一的B.有多種，但根結(jié)點(diǎn)都沒有左孩子

c.有多種D.有多種，但根結(jié)點(diǎn)都沒有右孩子

10）引入二叉線索樹的目的是（

A.為了能方便的找到雙親B.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度

C,使二叉樹的遍歷結(jié)果唯一D.為了能在二叉樹中方便的進(jìn)行插入與刪除

5.填空題

1）在一棵樹中，結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有并且只有一

個(gè)，可以有任意多個(gè)結(jié)點(diǎn)。

2）對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為。

3）一棵深度為5的完全二叉樹中的結(jié)點(diǎn)數(shù)最少為個(gè)，最多為

4）一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是______________o

5）利用二叉鏈表存儲(chǔ)一般樹，則根結(jié)點(diǎn)的右指針是_____________。

6）用4個(gè)權(quán)值｛3,2,4,1｝構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長度是

O

6.IE］出和下列已知序列對(duì)應(yīng)的二叉樹。

1）二叉樹的先序訪問序列為：GFKDAIEBCHJ

2）二叉樹的中序訪問序列為：DIAEKFCJHBG

7.畫出和下列已知序列對(duì)應(yīng)的二叉樹。

1）二叉樹的后序訪問序列為：CFEGDBJLKIHA

2）二叉樹的中序訪問序列為：CBEFDGAJIKLH

8.畫出和下列已知序列對(duì)應(yīng)的二叉樹。

1）二叉樹的層次訪問序列為：ABCDEFGHIJ

2）二叉樹的中序訪問序列為：DBGEHJACIF

9.給定一棵用二叉鏈表表示的二叉樹，其根指針為root。試寫出求二叉樹結(jié)點(diǎn)的數(shù)目的算法

（遞歸算法或非遞歸算法）。

10.設(shè)計(jì)一個(gè)算法，要求該算法把二叉樹的葉子按從左至右的順序鏈成一個(gè)單鏈表。二叉樹按

二叉鏈表方式存儲(chǔ)，鏈接時(shí)用葉子的「child域存放鏈指針。

II-給定一棵用二叉鏈表表示的二叉樹，其根指針為W01。試寫出求二叉樹的深度的算法。

12.給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出求二叉樹各結(jié)點(diǎn)的層數(shù)的算

法。

13.給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出將二叉樹中所有結(jié)點(diǎn)的左、

右子樹相互交換的算法。

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

0.02,0.06,0.32,0.03,0.21,0.10。

1）試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。

2）使用0?7的二進(jìn)制表示的等長編碼方案。

3）對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。

13.畫出和下列二叉樹相應(yīng)的森林。

1.選擇題

1）在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s,則所有頂點(diǎn)的入度

數(shù)Z和為（）。

A,sB.s+1

C.s-1D.n

2）在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s,則所有頂點(diǎn)的度數(shù)

之和為（）。

A.sB.s+1

C.s-1D.2s

3）在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，若具有e條邊，則所有頂點(diǎn)的度數(shù)之和為（）。

A?nB.e

C.n+eD.2e

4）在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，所含的邊數(shù)為（）。

A.nB,n（n-1）

C.n（n-1）/2D.n（n+1）/2

5）在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，所含的邊數(shù)為（）。

A.nB.n（n-1）

C.n（n-1）/2D.n（n+1）/2

6）對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向連通圖，它包含的連通分量的個(gè)數(shù)為（）。

A.nB-1

C,0D.n+1

7）若一個(gè)圖中包含有k個(gè)連通分量，若按照深度優(yōu)先搜索的方法訪問所有頂點(diǎn)，則必須

調(diào)用（）次深度優(yōu)先搜索遍歷的算法。

A.kB.I

C.k-1D.k+1

8）若要把n個(gè)頂點(diǎn)連接為一個(gè)連通圖，則至少需要（）條邊。

A.nB.n+1

C.n-1D.2n

9）在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接表中，保存頂點(diǎn)單鏈表的表頭指針向量

的大小至少為（）。

A.nB.e

C.2eD.2n

10）對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為kl,出度為kZ則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表

中的邊結(jié)點(diǎn)數(shù)為（）°

A.klB.kl-k2

C.k2D.kl+k2

H）深度優(yōu)先遍歷類似于二叉樹的

A.先序遍歷B.中序遍歷

C.后序遍歷D.層次遍歷

12）廣度優(yōu)先遍歷類似于二叉樹的（）。

A.先序遍歷R中序遍歷

C.后序遍歷D.層次遍歷

13）用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常借助（）來實(shí)現(xiàn)算

A.棧B.隊(duì)列法。

C.樹D.圖

14）用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常借助（

A.棧B.隊(duì)列）來實(shí)現(xiàn)算

C.樹D.圖法。

15）下面（）方法可以判斷出一個(gè)有向圖是否有環(huán)。

A?深度優(yōu)先遍歷B.拓?fù)渑判?/p>

C.求最短路徑D.求關(guān)鍵路徑

2.填空題

1）在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的倍。

2）在一個(gè)有n個(gè)頂點(diǎn)的無向完全圖中，包含有條邊，在一個(gè)具有n個(gè)頂點(diǎn)

的有向完全圖中'包含有條邊。

3）在一個(gè)有n個(gè)頂點(diǎn)的元向圖中，要連通所有頂點(diǎn)則至少需要條邊。

4）表示圖的兩種存儲(chǔ)結(jié)構(gòu)為和°

5）在一個(gè)連通圖中存在著個(gè)連通分量。

6）圖中的一條路徑長度為k,該路徑所含的頂點(diǎn)數(shù)為______________c

3.已知如圖所示的有向圖，請(qǐng)給出:

①每個(gè)頂點(diǎn)的入度和11!度；

②鄰接矩陣；

③鄰接表；

④逆鄰接表；

⑤強(qiáng)連通分量。

4.請(qǐng)對(duì)如圖所示的無向網(wǎng):

①寫出鄰接矩陣，并按普里姆算法求其最小生成樹：

②寫出鄰接表，并按克魯斯卡爾算法求其最小生成樹。

9

b7

5.編寫算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖

的鄰接表。

6.編寫算法，由依次輸入的頂點(diǎn)數(shù)目、邊的數(shù)目、各頂點(diǎn)的信息和各條邊的信息建立有向圖

的鄰接矩陣。

7.試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：DeleteArc(G,v,w),即刪除一條邊的操作。&試

在鄰接表存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：DeleteArc(G,v,w),即刪除一條邊的操作。

9.試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基木操作：InserlVex(Gv),即新增一個(gè)新頂點(diǎn)的操作。

10.試在鄰接表存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：InsertVex(G,v),即新增一個(gè)新頂點(diǎn)的操作。

II.采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)判別無向圖中任意給定的兩個(gè)頂點(diǎn)之間是否存在一

條長度為k的簡單路徑的算法。

1.選擇題

1)若查找每個(gè)元素的概率相等，則在長度為n的順序表上查找任一個(gè)元素的平均查找長

度為()°

AB?n+1

A?n

C.(n-1)/2D.(n+1)/2

2)對(duì)長度為n的單鏈有序表，若查找每個(gè)元素的概率相等，則查找任一個(gè)元素的平均查

找長度為()0

A.n/2B.(n+l)/2

C.(n-l)/2D-n/4

3)對(duì)于長度為n的順序存儲(chǔ)的有序表，若采用折半查找，則對(duì)所有元素的最長查找長度

為()的值向上取整。

A.log?(n+1)B?log2n

C.n/2D.

4)對(duì)于長度為9的順序存儲(chǔ)的有序表，若采用折半查找，在等概率情況下的平均查找反

度為()的值除以9。

A.20B.18

C.25D.22

5)對(duì)于長度為18的順廳存儲(chǔ)的有序表，若采用折半查找，則查找第15個(gè)元素的查找長

度為(10

A.3B.4

C5D?6

6).在一棵深度為h的具有n個(gè)元素的二叉排序樹中，查找所有元素的最長查找長度為

()0

A，11B?log2n

C.(h+l)/2D.h

7)從具有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，在平均情況下的時(shí)間復(fù)雜度大致為

()0

A-0S)B.O(Iog2n)

C0(1)D.0(n2)

8)從具有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素口寸，在最壞情況下的口寸間復(fù)雜度大致為

()0

AO⑹B.0(log2n)

C.°(1)D-0(n2)

9)在一棵平衡二叉排序樹中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是()。

A.?1~1B.-2-2

C.1~2D.0-1

10)在散列查找中，平均查找長度主要與()有關(guān)。

A.散列表長度B.散列元素的個(gè)數(shù)

C.裝填因子D.處理沖突方法

11)設(shè)散列表長為14,散列函數(shù)是H(key)=key%ll,表中已有數(shù)據(jù)的關(guān)鍵字為15,38,

61,84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的元素加到表中，用二次探測法解決沖突，則放入的

位置是()。

A.8B.5

C.3D.9

12)采用線性探測法處理沖突，可能要探測多個(gè)位置，在查找成功的情況下，所探測的

這些位置上的關(guān)鍵字()。

A.不一定都是同義詞B.一定都是同義詞

C.一定都不是同義詞D.都相同

2.填空題

1)采用順序查找法對(duì)長度為n的順序表或單鏈表進(jìn)行查找一個(gè)元素時(shí)，其平均查找長度

為，時(shí)間復(fù)雜性為o

2)以折半查找法進(jìn)行查找

時(shí)，該查找表必須組織成存儲(chǔ)的

表。

3)在一

棵二叉排序樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定________________________該結(jié)

點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定該結(jié)點(diǎn)的值。

4)折半查找有序表(4,6,12,20,28,38,50,7(),88,100)，若查找表中元素20,

將依次與表中元素比較大小。

5)______________________________________散列法存儲(chǔ)的基本思想是由決定數(shù)據(jù)的存儲(chǔ)

地址。

3.假定對(duì)有序表:(3,4,5,7,24,30,42,54,63,72,87,95)進(jìn)行折半查找，試回答下列問

題：

①畫出描述折半查找過程的判定樹；

②若查找元素54,需依次與哪些元素比較？

③若查找元素90,需依次與哪些元素比較？

④假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長度。

4.畫出對(duì)長度為10的有序表進(jìn)行折半查找的判定樹，并求其等概率時(shí)查找成功的平均查找

長度。

5.在一一棵空的二叉排序樹中依次插入關(guān)鍵字序列為12,7,17,11,16,2,13,9,21,4,請(qǐng)畫出所

得到的二叉排序樹。

6.選取散列函數(shù)H(key)=(3*key)%11,用線性探測法處理沖突，對(duì)下列關(guān)鍵字序列構(gòu)

造一個(gè)散列地址室間為0?10,表長為11的散列表，［22,41,53,08,46,30,01,31,66｝。

7.設(shè)計(jì)一個(gè)折半查找的算法，已知11個(gè)元素的有序表為(05,13,19,21,37,56,64,75,80,88,

92)查找關(guān)鍵字為key的數(shù)據(jù)元素。

也設(shè)計(jì)一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲(chǔ)結(jié)

構(gòu)，且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。

9.已知散列表的裝填因子小于1,散列函數(shù)H(key)為關(guān)鍵字(標(biāo)識(shí)符)的第一個(gè)字母在字母表中

的序號(hào)，處理沖突的方法為線性探測法。試設(shè)計(jì)一個(gè)按笫一個(gè)字母的順序輸出散列表中所

有關(guān)鍵字的算法。

1.選擇題

1)若對(duì)n個(gè)元素進(jìn)行直接插入排序，則進(jìn)行第i趟排序過程前，有序表中的元索個(gè)數(shù)為

)0

A.iB.i+1

C.i-1D.1

2)在對(duì)n個(gè)元素進(jìn)行冒泡排序的過程中，笫一趟排序至多需要進(jìn)行鄰)對(duì)相

元素之間的交換。

A.nB,n-1

C.n+1D.n/2

)

3)在對(duì)n個(gè)元素進(jìn)行直接插入排序的過程中，算法的空間復(fù)雜度為。

A.0(1)B.O(log2n)

C.O(n2)D.O(nlog2n)個(gè)元素中選

4)在對(duì)n個(gè)元素進(jìn)行直接選擇排序的過程中，第i趟需要從(擇出最

小值元素。

A.n-i+1B.n-i

C.i