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

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

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

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

3.選擇題

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

A.動態(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)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（）。

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

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

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

）

O

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

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

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

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

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

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

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

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

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

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

A.樹B.字符串C.隊D.棧

4.填空題

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

一門研究非數(shù)值計算的程序設(shè)計問題中計算機(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ù)的這

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

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

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

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

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

5.試分析下面各算法的時間復(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é)點的時I'可

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

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

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

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

素的物理位置___________相鄰。

3)在單鏈表中，

除了第一個結(jié)點外，任一結(jié)點的存儲位置由指示。

4)在n個結(jié)點的單

鏈表中要刪除已知結(jié)點汨，需找到它的，其時間更雜度

為0

5)

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

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

6)對于單鏈表，在表頭插

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

間復(fù)雜度為。

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

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

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

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

值返回。

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

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

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

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

3.選擇題

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

A.棧頂B.棧底

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

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

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

A?top++;B.top-;

C?

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

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

?？眨胻op==N-I表示棧滿，則該數(shù)組所能存儲的棧的最大長度為（

）

A.N-lB-N

C.N+lD.N+2

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

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

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

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

A.前一個B.后一個

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

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

AM-9RM_1

C.ND.N+1

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

時，首先需要（）。

A.前移隊首指針B.后移隊首指針

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

8）假

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

）°

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

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

4.填空題

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

行。

2)棧乂稱為表，隊列乂稱為表。

3)在一

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

最多為O

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

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

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

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

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

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

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

出其回文的可能性？

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

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

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

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

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

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

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

1.選擇題

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

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

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

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

A.18B.19

C.20D.21

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

A.8B.36

C.37D.9

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

A.兩串的長度相等

B.兩串包含的字符相同

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

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

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

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

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

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

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

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

C.空串是零個字符的串

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

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

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

“something”<"Somethig”

C?“BIT”二“BITE"

D.、

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

（B.模式匹配

A.串連接D.串比較

C.求子串>o

9）串的模式匹配是指（

A,判斷兩個串是否相等

B.對兩個串比較大小

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

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

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

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

A."taStr"B."Str”

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

11)若StrIndex(S,T)表示求T在S中的位置的操作,則對于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)字符串按存儲方式可以分為：順序存儲、鏈接存儲和。

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

3)空格串的長度等于。

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

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

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

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

X)假設(shè)有兩個字符串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)下面程序是把兩個串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兩個串太長，溢出！”)；

else{

〃把己連接到

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

rl->vcc|1=r2->vec

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

[i]；

〃修改新串長度

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

)

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

數(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ù)和每種字符的個數(shù)。

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

符。

1.選擇題

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

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

式確定。

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]的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)

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

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

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

則對任一上三角元素arr[i,j]對應(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)稀疏矩陣的壓縮存儲方法是只存儲(

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

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

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

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

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

元組

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

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

7)已知廣義表LS二((a,b,c),(d,c,D),對其運(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.特殊矩陣和稀疏矩陣，哪一種壓縮存儲后失去隨機(jī)存取的功能？為什么？

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

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

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

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

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

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

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

4.選擇題

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

A.0B.1

C.-1D.2

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

（B.葉子結(jié)點

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

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

A.0B.1

C.2D.任意多個

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

A.2B.1

C.0D.-1

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

A,nB-n-1

C.n+1D.2n

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

，占、、、。

B.2i+-

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

A.6B.7

C-5D.8

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

A?nB.n+1

C.2nD.2n-l

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

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

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

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

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

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

5.填空題

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

個，可以有任意多個結(jié)點。

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

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

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

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

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

O

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

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

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

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

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

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

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

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

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

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

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

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

二叉鏈表方式存儲，鏈接時用葉子的「child域存放鏈指針。

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

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

法。

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

右子樹相互交換的算法。

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

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

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

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

3）對于上述實例，比較兩種方案的優(yōu)缺點。

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

1.選擇題

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

數(shù)Z和為（）。

A,sB.s+1

C.s-1D.n

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

之和為（）。

A.sB.s+1

C.s-1D.2s

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

A?nB.e

C.n+eD.2e

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

A.nB,n（n-1）

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

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

A.nB.n（n-1）

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

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

A.nB-1

C,0D.n+1

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

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

A.kB.I

C.k-1D.k+1

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

A.nB.n+1

C.n-1D.2n

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

的大小至少為（）。

A.nB.e

C.2eD.2n

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

中的邊結(jié)點數(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)先遍歷時，通常借助（）來實現(xiàn)算

A.棧B.隊列法。

C.樹D.圖

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

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

C.樹D.圖法。

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

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

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

2.填空題

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

2）在一個有n個頂點的無向完全圖中，包含有條邊，在一個具有n個頂點

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

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

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

5）在一個連通圖中存在著個連通分量。

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

3.已知如圖所示的有向圖，請給出:

①每個頂點的入度和11!度；

②鄰接矩陣；

③鄰接表；

④逆鄰接表；

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

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

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

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

9

b7

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

的鄰接表。

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

的鄰接矩陣。

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

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

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

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

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

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

1.選擇題

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

度為()°

AB?n+1

A?n

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

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

找長度為()0

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

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

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

為()的值向上取整。

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

C.n/2D.

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

度為()的值除以9。

A.20B.18

C.25D.22

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

度為(10

A.3B.4

C5D?6

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

()0

A，11B?log2n

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

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

()0

A-0S)B.O(Iog2n)

C0(1)D.0(n2)

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

()0

AO⑹B.0(log2n)

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

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

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

C.1~2D.0-1

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

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

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

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

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

位置是()。

A.8B.5

C.3D.9

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

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

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

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

2.填空題

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

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

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

時，該查找表必須組織成存儲的

表。

3)在一

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

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

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

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

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

地址。

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

題：

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

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

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

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

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

長度。

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

得到的二叉排序樹。

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

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

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

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

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

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

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

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

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

1.選擇題

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

)0

A.iB.i+1

C.i-1D.1

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

元素之間的交換。

A.nB,n-1

C.n+1D.n/2

)

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

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

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

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

小值元素。

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

C.i