python數(shù)據(jù)結(jié)構(gòu)習(xí)題

第1章數(shù)據(jù)結(jié)構(gòu)導(dǎo)論

一、選擇題

1.算法的時(shí)間復(fù)雜度取決于A。

A.問題的規(guī)模B.變量的多少C.問題的難度D.A和B

2.算法能正確的順利結(jié)束的特性為算法的B。

A.有效性B.有限性C.健壯性D.高效性

3.數(shù)據(jù)的物理結(jié)構(gòu)主要包含N這幾種結(jié)構(gòu)。

A.順序結(jié)構(gòu)和鏈表結(jié)構(gòu)B.線性結(jié)構(gòu)和非線性結(jié)構(gòu)

C.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)D.集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)

4.數(shù)據(jù)在計(jì)算機(jī)內(nèi)存中的表示是指____△__________。

A.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)

C.數(shù)據(jù)的邏輯結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系5.數(shù)

據(jù)結(jié)構(gòu)被形式化定義為二元組（D,S）,其中D是B的有限集合。

A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.數(shù)據(jù)關(guān)系

6.算法效率的度量是D

A.正確度和簡(jiǎn)明度B.數(shù)據(jù)復(fù)雜度和程序復(fù)雜度

C.高的速度和正確度D.時(shí)間復(fù)雜度和空間復(fù)雜度

7.在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，還要存儲(chǔ)___D________。

A.數(shù)據(jù)的存儲(chǔ)方法B.數(shù)據(jù)處理的方法

C.數(shù)據(jù)元素的類型D.數(shù)據(jù)元素之間的關(guān)系

8.以下愈述不正確的是C.

A.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及數(shù)據(jù)相互之間的聯(lián)系

B.數(shù)據(jù)結(jié)構(gòu)主要指數(shù)據(jù)的邏輯結(jié)構(gòu)，與計(jì)算機(jī)的存儲(chǔ)和處理無關(guān)

C.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式，主要包括線形和非線性

D.對(duì)于給定的n個(gè)元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有多種

9.下列程序段違反了算法」____特征。

count=0

whilecount!=3：

print(count)

A.明確性B.有限性

C.有效性D.功能性

10.下列程序的時(shí)間復(fù)雜度為Do

foriinrange(l,n+l)：

j=i

forkinrange(j+l,n+l)：

x=x+l

A.0(i*j)B.0(n(n-l)/2)

C.Og/2)D.0(nz)

二、解答題

1.下列程序段中，函數(shù)mvfun(i.k)的執(zhí)行次數(shù)是n(n+l)/2,該程序的時(shí)間復(fù)雜度為

0G/2)。

forkinrange(l,n+l)：

foriinrange(0,k)：

ifi!=k：

my_fun(i,k)

2.求下列程序段中有數(shù)字標(biāo)號(hào)的各語句的執(zhí)行次數(shù)，然后求出該程序段的時(shí)間復(fù)雜度。

deffun(n):

①i=s=l

②whiles<n：

i=i+l

③s=s+i

④returni

答：

①1次

②(2n)1/2次

③(2n)'1/2-1次

④1次

⑤0(n」/2)

第2章數(shù)組結(jié)構(gòu)

一、選擇題

1.線性表是一個(gè)——A------

A.有限序列，可以為空B.有限序列，不能為空

C.無限序列，可以為空D.無限序列，不能為空

2.下面關(guān)于線性表的敘述中，錯(cuò)誤的是B。

A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元

B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作

C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元

D.線性表采用鏈接存儲(chǔ)，便于進(jìn)行插入和刪除操作

3.某線性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占4個(gè)存儲(chǔ)單元，首地址為100,則第12個(gè)元素

的存儲(chǔ)地址為A。

A.144B.145C.147D.148

4若長度為n的順序存儲(chǔ)結(jié)構(gòu)線性表，刪除第i個(gè)數(shù)據(jù)元素，需要向前移動(dòng)A分

數(shù)據(jù)元素。

A.n-iB.n+iC.n-i-1D.n-i+1

5.若長度為n的順序存儲(chǔ)結(jié)構(gòu)線性表，在第i個(gè)位置插入一個(gè)元素，需要依次向后移

動(dòng)______D個(gè)元素。

A.n-iB.n+iC.n-i-1D.n-i+1

6.一個(gè)順序表所占存儲(chǔ)空間的大小與D無關(guān)。

A.順序表長度B.結(jié)點(diǎn)類型

C.結(jié)點(diǎn)中個(gè)數(shù)據(jù)域的類型D.結(jié)點(diǎn)的存放次序

7.以下以抹不正確的是D。

A.數(shù)據(jù)的邏輯結(jié)構(gòu)包括線性和非線性結(jié)構(gòu)，非線性結(jié)構(gòu)包括樹和圖兩種。

B.數(shù)據(jù)的邏輯結(jié)構(gòu)主要指元素間的關(guān)系，與計(jì)算機(jī)的存儲(chǔ)和處理無關(guān)

C.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式，主要包括順序和鏈?zhǔn)絻煞N

D.對(duì)于給定的n個(gè)元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有順序表和鏈表兩種

8.某線性表采用順序存儲(chǔ)結(jié)構(gòu)，則下列敘述正確的是B。

A.刪除順序表第i個(gè)元素和在第i位置插入一個(gè)元素所需移動(dòng)的元素個(gè)數(shù)一樣

B.刪除順序表第i個(gè)元素和在第i位置插入一個(gè)元素的時(shí)間復(fù)雜度一樣

C.刪除順序表第i個(gè)元素和取第i元素的值的時(shí)間復(fù)雜度一樣

D.在順序表表頭插入和表尾插入的時(shí)間復(fù)雜度一樣

9.對(duì)線性表，在下列情況下應(yīng)當(dāng)采用順序表表示的是A。

A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作

C.表中每個(gè)元素需要的字節(jié)數(shù)比較大D.表中的元素個(gè)數(shù)不變

10.在含有n個(gè)元素的順序表中，算法的時(shí)間復(fù)雜度是0(1)的操作是—A—。

A.訪問第i個(gè)元素(IWiWn)和求第i個(gè)元素的直接前驅(qū)(2WiWn)

B.在第i個(gè)元素后插入一個(gè)新元素

C.刪除第i個(gè)元素(IWiWn)

D.將n個(gè)元素從小到大排序

二、填空題

1.一個(gè)一維數(shù)組(列表)A的長度為500,起始(A[0])地址為2000,每個(gè)元素占4個(gè)字

節(jié)，則A[80]的地址是一2320__。

2.一個(gè)4*6的二維數(shù)組A,每個(gè)元素占4個(gè)字節(jié)，假設(shè)該數(shù)組起始元素A(l,l)的地址是110,

若以行為主存儲(chǔ)，則A(3.5)的地勢(shì)泉174:若以列為主存儲(chǔ)，A(3,5)的地址

是182。

3.以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表簡(jiǎn)稱為順序表,它要求存儲(chǔ)空間必須是

連續(xù)的，并以下標(biāo)來體現(xiàn)元素之間的關(guān)系,在順序表中訪問第i個(gè)

元素的時(shí)間復(fù)雜唐為0(1),因此，順序表也稱為隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。以

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表稱為密表__________。茸存儲(chǔ)空間可以是不容續(xù)

的_______.以指針來體現(xiàn)元素力間的關(guān)系,在鏈表中訪問第i個(gè)元素的時(shí)

間復(fù)雜度為一區(qū)此一鏈表也稱為順序訪問的數(shù)據(jù)結(jié)構(gòu)。

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

1.設(shè)有一個(gè)順序表L,其元素為整型數(shù)據(jù)，編寫一個(gè)要求時(shí)間復(fù)雜度為0(n)、空間復(fù)

雜度為0(1)的算法，將L中所有小于0的整數(shù)放在前半部分，大于0的整數(shù)放在后半部分。

提示：從L的兩端查找，前端找大于0的數(shù)據(jù)，后端找小于0的數(shù)據(jù)，然后將兩位置的數(shù)據(jù)

交換。

L=11,2,3,4,5,6,7,8,9,10,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]

n=len(L)

print("原順序表：\n{}format(L))

J=0

k=0

foriinrange(n)：

ifL[i]<0：

k=L[i]

L[i]=L[j]

L[j]=k

J+=1

else：

continue

print("排序后順序表:\n{}°.format(L))

2.在一個(gè)有序列表中查找元素x,當(dāng)被查元素x小于列表中某個(gè)元素時(shí)就可停止。請(qǐng)

編寫一個(gè)函數(shù)實(shí)現(xiàn)上述查找，并分析此查找在最好情況、最壞情況以及平均情況下的性能。

deffound(L,x)：

print("查找元素”)

foriinL：

ifx>iorx==i：

print("元素x大于或等于｛｝，程序繼續(xù)”.format(i))

continue

else：

print("元素x小于｛｝,程序停止".format(i))

break

if___name__=="main_":

x=eval(input("請(qǐng)輸入要查找的元素x："))

L=[l,2,3,4,5,6,7,8,9]

found(L,x)

3.已知一個(gè)n*n的二維數(shù)組a已經(jīng)以行為主存放在一個(gè)大小為n2的一維數(shù)組b中，編

寫一個(gè)函數(shù)計(jì)算此二維數(shù)組的主對(duì)角線元素之和。count(b,n)

defcount(b,n)：

x=0

i=0

whileTrue：

x+=b[i]

i+=n+1

ifi>len(b)：

break

print("主對(duì)角線元素之和為:％d"%x)

if___name__=="main_":

a=[[1,2,3],[4,5,6],[7,8,9]]

b=[]

n=len(a)

print("二維數(shù)組A為：")

foriinrange(n)：

forjinrange(n)：

b.append(a[i][j])

print(,r%dn%a[i][j],end='\tr)

print()

print("存放在一維數(shù)組b中為：M)

print(b)

count(b,n)

4.有一值為整型、長度為n的順序表(列表)，寫一個(gè)函數(shù)，計(jì)算該順序表所有元素的

平均值，并輸出所有大于平均值的元素。

defAverage(L,n)：

nsum=0

foriinrange(n)：

nsum+=L[i]

average=nsum/n

print(,r平均數(shù)為:%dH%average)

print("所有大于平均值的元素為：")

foriinL：

ifi>average：

print(i,end=，')

else：

continue

if___name__=="__main_":

L=[1,354,56,57,2,8,9,46,767,678]

n=len(L)

Average(L,n)

第3章鏈表

一、選擇題

1.以下關(guān)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的敘述中，C是不正確的。

A.結(jié)點(diǎn)除自身信息外還包括指針域，因此空間利用率小于順序存儲(chǔ)結(jié)構(gòu)

B.邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接

C.可以通過計(jì)算直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址

D.插入、刪除運(yùn)算操作方便，不必移動(dòng)結(jié)點(diǎn)

2.在下列存儲(chǔ)結(jié)構(gòu)中，最適合實(shí)現(xiàn)在線性表中進(jìn)行隨機(jī)訪問的是

A.數(shù)組B.雙向鏈表C.單向鏈表D.循環(huán)鏈表

3.與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是

A.可以由最后一個(gè)結(jié)點(diǎn)找到頭結(jié)點(diǎn)B.可隨機(jī)訪問

C.插入、刪除操作更加簡(jiǎn)單D.訪問前驅(qū)結(jié)點(diǎn)更加方便

4如果對(duì)線性表的運(yùn)算只有2種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素,

則最好使用」_。

A.順序表B.單鏈表C.雙向鏈表D.具有表尾指針的循環(huán)單鏈表

5.在表頭指針為head且表長大于1的單向循環(huán)鏈表中，指針p指向表中的某個(gè)結(jié)點(diǎn)，若

p.next.next==head,則D_____。

A.p指向頭結(jié)點(diǎn)B.p指向尾結(jié)點(diǎn)

C.p所指結(jié)點(diǎn)的直接后繼是頭結(jié)點(diǎn)D.p所指結(jié)點(diǎn)的直接后繼是尾結(jié)點(diǎn)

6.帶表頭附加結(jié)點(diǎn)的單鏈表head為空的判斷條件昌B0

A.head==None#不帶頭結(jié)點(diǎn)的空鏈表

head.next==None

head.next==head

head!=None

7.一個(gè)單鏈表中，若要在指針s所指結(jié)點(diǎn)的后面插入一個(gè)由指針P所指向的結(jié)點(diǎn)，則執(zhí)行

.next=pp.next=s.next；

p.next=s.next

.next=p.nextp.next=

p.next=s.nexts.next=p

8.對(duì)線性表，在下列情況下應(yīng)當(dāng)采用鏈表表示的是B。

A.經(jīng)常需要隨機(jī)地存取元素

B.經(jīng)常需要進(jìn)行插入和刪除操作

C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間

D.表中的元素個(gè)數(shù)不變

9.如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及前驅(qū)，則采用A存儲(chǔ)方式最節(jié)省時(shí)間。

A.順序表B.雙鏈表C.單循環(huán)鏈表D.單鏈表

10.從一個(gè)具n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平

均比較1)個(gè)結(jié)點(diǎn).

A.nB.n/2C.(nT)/2D.(n+l)/2

11.在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)刪除x的后繼的語句是B.

A.p=p.nextB.p.next=p.next,next

C.p.next=pD.p=p.next,next

12.循環(huán)鏈表的主要優(yōu)點(diǎn)是D。

A.不再需要頭指針了

B.已知某個(gè)結(jié)點(diǎn)的位置后，能很容易找到它的直接前驅(qū)結(jié)點(diǎn)

C.在進(jìn)行刪除操作后，能保證鏈表不斷開

D.從表中任一結(jié)點(diǎn)出發(fā)都能遍歷整個(gè)鏈表

二、填空題

1.一個(gè)單鏈表結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)都包含有兩個(gè)域，稱為—數(shù)據(jù)—域和--指毋—域。

2.已知一個(gè)雙向鏈表(指針域名為next和prior)中間局部如下圖所示，

現(xiàn)要求將P所指的結(jié)點(diǎn)插入到x和y結(jié)點(diǎn)之間(即p所指結(jié)點(diǎn)后面)，其操作步驟為:

----p.next=q.next-----；-------p.prior-q--------------；

----":rtext—p---------;------—p---------------------;

2.已知L是不帶頭結(jié)點(diǎn)的單鏈表，閱讀下列函數(shù)，回答問題。

deffun(L)：#L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針

if(L!=None&&L.next!=None)：#語句1

q二L

L=L.next

p=L

while(p.next!=None)：#語句5

p=p.next

p.next=q

q.next二None

returnL；

(1)說明該函數(shù)執(zhí)行的條件，即語句1的功能

Len(L)>1

(2)說明語句5(即while循環(huán))的功能

查找尾結(jié)點(diǎn)

(3)若鏈表L的初始狀態(tài)如下圖，畫出執(zhí)行上述函數(shù)后的鏈表L的示意圖。

a2|用a311fla4|Ta5||八|

木A

Pq

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

1.編寫一個(gè)函數(shù)，實(shí)現(xiàn)從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回。

deffun(L)：

ifL.next=None：

return0

Max=L.next,data

p=L.next,next

whilep!=None：

ifp.data>max：

max=p.data

p=p.next

returnmax

2.編寫一個(gè)函數(shù)，實(shí)現(xiàn)單鏈表中刪除一個(gè)最小值節(jié)點(diǎn)的算法(假設(shè)該鏈表中每個(gè)節(jié)點(diǎn)的值

不重復(fù))。

deffunl(L)：

ifL.next=None：

returnNone

ptr=L.next

p=L.next,next

whilep!=None：

ifp.data<ptr.data：

ptr=p

p=p.next

P=L

Whilep.next!=ptr：

p=p.next

P.next=p.next,next#p.next=ptr.next

3.假設(shè)有一個(gè)循環(huán)鏈表的長度大于1,且表中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表

某個(gè)結(jié)點(diǎn)的指針，編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。

deffun（s）：

p=s.next

Whilep.next,next!=s：

p=p.next

p.next=s

第4章棧+第5章隊(duì)列

一、選擇題

1.有5個(gè)元素a,b,c,d,e依次進(jìn)棧，允許任何時(shí)候出棧，則可能的出棧序列是C。

A.baecdB.dceabC.abedcD.aebcd

2,下列有關(guān)遞歸的敘述，不正確的是B。

A.在計(jì)算機(jī)系統(tǒng)內(nèi)，執(zhí)行遞歸函數(shù)是通過自動(dòng)使用棧來實(shí)現(xiàn)的。

B.在時(shí)間和空間效率方面，遞歸算法比非遞歸算法好。

C.遞歸函數(shù)的求解過程分為遞推（進(jìn)棧）和回推（出棧）兩個(gè)階段。

D.在遞歸函數(shù)中必須有終止遞歸的條件。

3.棧和隊(duì)列均屬于哪一種邏輯結(jié)構(gòu)A

A.線性結(jié)構(gòu)B.順序結(jié)構(gòu)C.非線性結(jié)構(gòu)D.鏈表結(jié)構(gòu)

4.設(shè)輸入元素為1、2、3、P和A,輸入次序?yàn)?23PA,元素經(jīng)過棧后得到各種輸出序列，

則可以作為高級(jí)語言變量名的序列有—B—種。

A.4B.5C.6D.7

5.一個(gè)隊(duì)列的入隊(duì)序列為a,b,c,d,則該隊(duì)列的輸出序列是3__o

A.dcbaB.abedC.adebD.cbda

6.在一個(gè)鏈?zhǔn)疥?duì)列中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算是

B。

A.f.next=s；f=s；B.r.next=s；r=s;

C.s.next=s；r=s；D.s.next=f；f=s；

7.如果5個(gè)元素出棧的順序是1、2、3、4、5,則進(jìn)棧的順序可能是C。

A.3、5、4、1,2B.1、4、5、3、2

C.5、4、1、3、2D.2、4、3、1、5

8.已知一個(gè)棧的進(jìn)棧序列為1,2,3,4?,,n,其出棧輸出序列是pl,p2,p3,…，pn。若

pl=3,則D2的值D。

A.一定是2B.一定是1C.可能是1D.可能是2

9.以1,2,3,…，n的順序進(jìn)隊(duì)列，則可能的出隊(duì)序列有A種。

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

D.10.在計(jì)算遞歸函數(shù)時(shí)，如不用遞歸過程,應(yīng)

借助于B這種數(shù)據(jù)結(jié)構(gòu)。

A.線性表B.棧C.隊(duì)列D.雙向隊(duì)列

二、填空題

1.棧和隊(duì)列是一種特殊的線性表，其特殊性體現(xiàn)在易運(yùn)算受限線性表0設(shè)現(xiàn)有元素

el,e2,e3,e4,e5和e6依次進(jìn)棧，若出棧的序列是e2,e4,e3,e6,e5,el,則棧S的容量至少

是_3。_______

2.順序循環(huán)隊(duì)列中，設(shè)隊(duì)頭指針為front,隊(duì)尾指針為rear,隊(duì)中最多可有MAX個(gè)元素，

采用少用一個(gè)存儲(chǔ)單元的方法區(qū)分隊(duì)滿與隊(duì)空問題，則元素入隊(duì)列時(shí)隊(duì)尾指針的變化為

rear二(rear+1)%MAX:元素出隊(duì)列時(shí)隊(duì)頭指針的變化為front二(front+l)%MAX:隊(duì)列中

的元素個(gè)數(shù)為(rear-front+MAX)%MAXo隊(duì)滿的判別條件為為(rear+l)%W\X==

frnnt:隊(duì)空的判別條件為「rent二二八

3.一個(gè)中綴表達(dá)式a+b*(a+c)-c/d的前綴表達(dá)式為-+a*b+ac/cd,后綴表達(dá)式為

H)ac+*+cd/-0一個(gè)后綴表達(dá)式21+42-*3+的值為9。

4.下列函數(shù)的功能是求n2+(n~~l)2+(n~~2)2+..+1的木口c

defsum(n)：

ifn=0：

return0

else：

returnsum(n-l)+n*n

5.下列算法的功能判斷輸入的字符串是否是回文。

deffunc()：

creatstack(S)#初始化構(gòu)造一個(gè)空棧S

creatqueue(Q)#初始化構(gòu)造一個(gè)空隊(duì)列Q

str二input("輸入一個(gè)字符串：”)

forchinstr：

push(ch)

enqueue(ch)

whilenotisempty(S)：

a=pop()

b二dequeue()

ifa!=b：

return0

return1

三、解答題

1.用一維數(shù)組a[7]順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列，隊(duì)首和隊(duì)尾指針分別用front和rear表示，

當(dāng)前隊(duì)列中已有5個(gè)元素：22,30,16,36,58,其中22是隊(duì)首，front值為5,請(qǐng)畫出

對(duì)應(yīng)的存儲(chǔ)狀態(tài)圖，當(dāng)連續(xù)做兩次出隊(duì)運(yùn)算后，再做兩次入隊(duì)運(yùn)算，讓元素80,55依次進(jìn)

隊(duì)，請(qǐng)?jiān)佼嫵鰧?duì)應(yīng)的存儲(chǔ)狀態(tài)圖。

2.用一個(gè)帶頭結(jié)點(diǎn)的循環(huán)鏈表來表示循環(huán)隊(duì)列，且該隊(duì)列只設(shè)尾指針。編寫初始化、入隊(duì)、出

隊(duì)操作算法。

classQnode：

def__init_(self,data,next=None)：

self.data=data

self.next=None

rear=Qnode()

rear.next=rear

defenqueue(item)：

globalrear

newQueue=Qnode()

newQueue.data=item

newQueue.next=rear,next

rear,next=newQueue

rear=newQueue

defdequeue(item)：

globalrear

ifrear,next=rear：

print("隊(duì)列已空！”)

else：

item=rear.next,data

rear,next=rear.next,next

returnitem

第5章樹形結(jié)構(gòu)

一、選擇題

1.按照二叉樹定義，具有3個(gè)結(jié)點(diǎn)的二叉樹共有C種形態(tài)。

(A)3(B)4(C)5(D)6

2.具有五層結(jié)點(diǎn)的完全二叉樹至少有D個(gè)結(jié)點(diǎn)。

(A)9(B)15(C)31(D)16

3.以下有關(guān)二叉樹的說法正確的是

(A)二叉樹的度為2(B)一棵二叉樹的度可以小于2

(C)至少有一個(gè)結(jié)點(diǎn)的度為2(D)任一結(jié)點(diǎn)的度均為2

4.已知二叉樹的后序遍歷是dabec,中序遍歷是debac,則其前序遍歷是--D----。

(A)acbed(B)decab(C)deabc(D)cedba

5將一棵有1000個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為

1,則編號(hào)為49的結(jié)點(diǎn)的右孩子編號(hào)為B。

(A)98(B)99(C)50(D)沒有右孩子

6對(duì)具有100個(gè)結(jié)點(diǎn)的二叉樹，若有二叉鏈表存儲(chǔ)，則其指針域共有D為空。

說明：n=n0+nl+n2

指針域?yàn)榭盏膫€(gè)數(shù)：2*n0+nl=nO+nl+n2+1=101

(A)50(B)99(C)100(D)101

7.設(shè)二叉樹的深度為h,且只有度為1和0的結(jié)點(diǎn)，則此二叉樹的結(jié)點(diǎn)總數(shù)為(：。

(A)2h(B)2h-l(C)h(D)h+1

&對(duì)一棵滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h,則D。

(A)n=h+m(B)h+m=2n(C)m=h-1(D)n=2h-l

9.某二叉樹的先序序列和后序序列正好相反，則下列說法錯(cuò)誤的是A

(A)二叉樹不存在

(B)若二叉樹不為空，則二叉樹的深度等于結(jié)點(diǎn)數(shù)

(0若二叉樹不為空，則任一結(jié)點(diǎn)不能同時(shí)擁有左孩子和右孩子

(D)若二叉樹不為空，則任一結(jié)點(diǎn)的度均為1

1Q對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編號(hào)，同一

結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用U歷實(shí)現(xiàn)編號(hào)。

(A)先序(B)中序(C)后序(D)層序

11.一個(gè)具有具25個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為C。

(A)10(B)ll(O1T1025(D)10^1024

12.設(shè)n,m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是。

(A)n在m右方⑻n是m祖先

(C)n在m左方(D)n是m子孫

13.實(shí)現(xiàn)對(duì)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是二叉樹采用

U儲(chǔ)結(jié)構(gòu)。

(A)二叉鏈表(B)廣義表(C)三叉鏈表(D)順序

14.一棵樹可轉(zhuǎn)換成為與其對(duì)應(yīng)的二叉樹，則下面敘怵正確的是A。

(A)樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷相同

(B)樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷相同

(C)樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷相同

(D)以上都不對(duì)

二、填空題

1對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵完全二叉樹時(shí)具有最小高度:當(dāng)它為單

分支二叉樹苗.具有最大高度。

2在二叉樹的第i(i2l)層上至多有第(i-1)個(gè)結(jié)點(diǎn),深度為k(k^l)的完全二

叉樹至多2'k-1個(gè)結(jié)點(diǎn),最少2.(kT)個(gè)結(jié)點(diǎn)；

3.如果二叉樹的終端結(jié)點(diǎn)數(shù)為期，度為2的結(jié)點(diǎn)數(shù)為絲，則n()=n2+l。

4已知一棵二叉樹的中序序列是cbedahgijf,后序序列是cedbhjigfa,則該二叉樹的先序

序列是.abcdefghii,該二叉樹的深度為5。

5若一棵二叉樹的中序遍歷結(jié)果為ABC,則該二叉樹有5種不同的形態(tài)。

6在順序存儲(chǔ)的二叉樹中，下標(biāo)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是lo")i=

log⑵i。

7.已知完全二叉樹的第7層有8個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)為36個(gè)?？偨Y(jié)點(diǎn)數(shù)為7j_工。

&在對(duì)二叉樹進(jìn)行非遞歸中序遍歷過程中，需要用棧來暫存所訪問結(jié)點(diǎn)的地址:進(jìn)行層

序遍歷過程中，需要用隊(duì)列來暫存所訪問結(jié)點(diǎn)的地址;

a高度為h,唐為k的樹中至少有h+k-1個(gè)結(jié)點(diǎn),至多有klT個(gè)結(jié)點(diǎn)。

1Q一維數(shù)組存放完全二叉樹：ABCDEFGHI,則后序遍歷該二叉樹的序列為HIDEBEGCA。

三、應(yīng)用題

1.應(yīng)用題：說明分別滿足下列條件的二叉樹各是什么？

(D先序遍歷和中序遍歷相同；右斜二叉樹、空樹，只有一個(gè)跟節(jié)點(diǎn)的二叉樹

(2)中序遍歷和后序遍歷相同；左斜二叉樹、空樹，只有一個(gè)跟節(jié)點(diǎn)的二叉樹

⑶先序遍歷和后序遍歷相同；空樹，只有一個(gè)跟節(jié)點(diǎn)的二叉樹

2.已知一棵二叉樹的中序序列是cbedahgijf,后序序列是cedbhjigfa,畫出這棵二叉

樹的邏輯結(jié)構(gòu)圖。

3.一棵二叉樹的先序、中序、后序序列如下，其中一部分未標(biāo)出，試構(gòu)造出該二叉樹。

先序序列：ABCDEFGHIJK

中序序列：CBEDFAHJKIG

后序序列：CEFDBLJIHGA

4.有n個(gè)結(jié)點(diǎn)的二叉樹，已知葉子結(jié)點(diǎn)個(gè)數(shù)為n，回答下列問題：

0

(1)寫出求度為1的結(jié)點(diǎn)的個(gè)數(shù)n的計(jì)算公式；nl=n+l-2n0

1

⑵若此樹是深度為k的完全二叉樹，寫出n為最小的公式；n(min)=27k-l)

⑶若二叉樹中僅有度為0和度為2的結(jié)點(diǎn)，寫出求該二叉樹結(jié)點(diǎn)個(gè)數(shù)n的公式；n=2n0-l

5.按列表為［32,25,16,35,34,20,40］中的數(shù)據(jù)創(chuàng)建一棵二叉查找樹，畫出此二叉查找

樹，并寫出此二叉查找樹的先序、中序、后序遍歷序歹％

先序:32251620353440

中序:16202532343540

后序:20162534403532

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

1.編寫求二叉樹BT中結(jié)點(diǎn)總數(shù)的算法。

defnodecount(BT)：

ifBT==None：

return0

else：

n=nodecount(BT.left)+nodecount(BT.right)+1

returnn

2.編寫求二叉樹BT中葉子結(jié)點(diǎn)數(shù)的算法。

defleavecount(BT)：

ifBT==None：

return0

elifBT.left==NoneandBT.right==None：

return1

else：

m=leavecount(BT.left)+leavecount(BT.right)

returnm

3.若已知兩棵二叉樹BT1和BT2皆為空，或者皆不為空且BT1的左、右子樹和BT2的

左、右子樹分別相似，則稱二叉樹BT1和BT2相似。編寫算法，判別給定的兩棵二叉樹是否

相似。

defBTreeSim(BTl,BT2)：

ifBT1==NoneandBT2==None：

return1

elifBT1==NoneorBT2==None：

return0

else：

m=BTreeSim(BTl.left,BT2.left)

n=BTreeSim(BTl.right,BT2.right)

returnm,n

4.編寫算法，求二叉樹中以元素值為x的結(jié)點(diǎn)為根的子樹的深度。

defgetDepth(BT,x)：

ifBT==None：

return0

elifBT.data==x：

returnbtreedepth(BT)

elifBT.left!=Null：

returngetDepth(BT.left,x)

elifBT.right!=Null：

returngetDepth(BT.right,x)

else：

return0

defbtreedepth(ptr)：#求二叉樹的高度

ifptr==None：

return0

else：

m=btreedepth(ptr.left)

n=btreedepth(ptr.right)

ifm>n：

returnm+1

else：

returnn+1

第6章圖形結(jié)構(gòu)

一、選擇題

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

A.nB.n(n-1)C.n(n-l)/2D.n(n+l)/2

2.在一個(gè)有向圖中，所有頂點(diǎn)的度之和與圖的邊數(shù)之比為。

A.1：1B.2：1C.1：2D.不確定

3.一個(gè)具有n個(gè)頂點(diǎn)的無向圖，要確保是一個(gè)連通圖，至少需要A條邊。

A.n-lB.nC.n+1D.n/2

4.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的C倍。

A.4B.2C.1D.1/2

5.對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為kl,出度為k2,則對(duì)應(yīng)鄰接表中該頂點(diǎn)在表結(jié)點(diǎn)中

出現(xiàn)的結(jié)點(diǎn)數(shù)為一C。

A.klB.k2C.kl-k2D.kl+k2

6.在無向圖G的鄰接矩陣A中，若等于1,則等于_Bo

A.無窮大B.1C.0D.無法確定

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

大小至少為___A-

A.nB.2nC.eD.2e

8.G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有B個(gè)頂點(diǎn)。n(n-l)/2=28

n=8+l=9

A.16B.9C.8D.7

9.在一個(gè)有向圖的鄰接表中，每個(gè)頂點(diǎn)單鏈表中結(jié)點(diǎn)的個(gè)數(shù)等于該頂點(diǎn)的_人o

A.出邊數(shù)B.入邊數(shù)C.度數(shù)D.度數(shù)減1

10.對(duì)某個(gè)無向圖的鄰接矩