數(shù)據(jù)結構期末試卷2

數(shù)據(jù)結構期末試卷A

一、判斷題：（共10分，每題1分）

1、深度為h的非空二叉樹的第i層最多有2iT個結點。（）

2、在完全二叉樹中，若某結點無左孩子，則它必是葉結點。（）

3、一組權值，可以唯一構造出一棵赫夫曼樹。（）

4、在n個結點的無向圖中，若邊數(shù)多于n-1,則該圖必是連通圖。（）

5、對于有向圖，頂點的度分為入度和出度，入度是以該頂點為終點的入邊數(shù)目；出度

是以該頂點為起點的出邊數(shù)目，該頂點的度等于其入度和出度之和。（）

6、無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣是不對稱的。（）

7、折半查找只適用于有序表，包括有序的順序表和有序的鏈表。（）

8、一個好的哈希函數(shù)應使函數(shù)值均勻的分布在存儲空間的有效地址范圍內(nèi)，以盡可能

減少沖突。（）

9、在初始數(shù)據(jù)為逆序時，冒泡排序所執(zhí)行的比較次數(shù)最多。（）

10、希爾排序在效率上較直接插入排序有較大的改進。但是不穩(wěn)定的。（）

二、填空題：（共20分，每空2分）

1、在樹結構里，有且僅有一個結點沒有前驅，稱為根。非根結點有且僅有一個，,

且存在一條從根到該結點的。

2、三個結點的二叉樹，最多有種形狀。

3、任何?棵二叉樹，若nO,n2分別是度為0,2的結點的個數(shù)，則nO和n2的關系為

4、設有10個值，構成赫夫曼樹，則該赫夫曼樹共有個結點。

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

6、一個連通圖的生成樹是該圖的連通子圖。若這個連通圖有n個頂點，則它

的生成樹有條邊。

7、如果從一無向圖的任意頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖

一定是O

8、將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關鍵字有序的序列叫o

三、選擇題：（共20分，每題2分）

1、設X是一棵樹，X，是對應于X的二叉樹，則X的后根次序遍歷和X，的一次序遍歷相

同

A.先序B.中序

C.后序D.都不是

2、設有100個元素，用折半查找法進行查找時，在查找成功的情況下，最大比較次數(shù)是

A.100B.50

C.99D.7

3、設散列表長m=14,散列函數(shù)H(K)=K%11,已知表中已有4個結點：r(15)=4;r(38)=5;

r(61)=6;r(84)=7,其他地址為空，如用二次探測再散列處理沖突，關鍵字為49的結點地址

是。

A.8B.3

C.5D.9

4、在含有n個項點有e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為。

A.eB.2e

C.n'-eD.n-2e

5、圖的深度優(yōu)先遍歷類似于樹的。

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

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

6、下面關于圖的存儲的敘述中，哪一個是正確的。

A.用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結點個數(shù)有關，而與邊數(shù)無關

B.用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關,而與結點個數(shù)無關

C.用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結點個數(shù)有關，而與邊數(shù)無關

D.用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關，而與結點個數(shù)無關

7、從堆中刪除一個元素的時間復雜度為._。

A、0(1)B、0(n)

C、0(log2n)D、0(nlog2n)

8、用某種排序方法對關鍵字序列(23,72,21,47,15,27,59,35,20)進行排序時，

前三趟的結果情況如下：

23,21,47,15,27,59,35,20,72

21,23,15,27,47,35,20,59,72

21,15,23,27,35,20,47,59,72

則所采用的排序方法是一

A.選擇排序B.起泡排序

C.歸并排序D.快速排序

9、將一棵有40個結點的完全二叉樹從上到下，從左到右依次對結點進行編號，根結點的編

號為1,則編號為15的結點的左孩子的編號為。

A.30B.31

C.16D.32

10、如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是

A.有向完全圖B.連通圖

C.強連通圖D.有向無環(huán)圖

四、應用題：(共28分，每題4分)

1、將下圖轉換為二叉樹，對轉換后的二叉樹進行先序、中序、后序遍歷序列。

2、什么是赫夫曼(Huffman)樹？有一組數(shù)值14、21、32、15、28,畫出赫夫曼樹，并計

算其WPLo

3、設一個有向圖為G=(V,E),其中V={vl,v2,v3,v4},E={<v2,v1>,<v2,v3>,<v4,v1>,<v1,v4>,

<v4,v2>},畫出該有向圖，畫出相應鄰接表，寫出從頂點vl出發(fā)進行深度優(yōu)先和廣度優(yōu)先

搜索得到的頂點序列。

4、用序列(46,88,45,39,70,58,101,10,66,34)建立一個平衡的二叉排序樹，畫

出該樹。

5、已知一組鍵值序列為(41,66,73,52,40,37,65,43),試采用快速排序法對該組序

列作升序排序，并給出每一趟的排序結果。

6、已知一組關鍵字為(26,36,41,38,44,15,68,12,06,51,25),用線性探查法

解決沖突構造這組關鍵字的哈希表。表長取13,哈希函數(shù)H(key)=keyMOD13。

7、已知一棵三階的B-樹如下圖所示，假定依次插入關鍵字50,83請畫出插入個結點后樹

的情況：

五、程序題(共22分)

1、完成下列程序，并說出該算法所完成的功能。(8分)

voidweizhisort(structnoder[n],intn)

{intlow,high,mid,j,i；

fbr(i=2;i<=n;i++)

{r[O]=r[i];

low=;

high=；

while(low<=high)

{mid=(low+high)/2;

if(r[O].key<r[mid].key)

elselow=mid+l;}

for(j=i-l；j>=l;j-)

rU+l]=rU]；

r[high+l]=r[O];

))

其中數(shù)據(jù)類型定義為：

structnode

{intkey;

Infbtypeotherinfb;

2、完成程序，并說出程序的功能（8分）

Bitreptr*bstsearch(Bitreptr*t,Keytypek)

{while(t!=null)

{if(t->key==k);

ifift->key>k);

else

returnnull;

}

其中，類型定義

typedefstructBitnode{

Keytypekey;

StructBitnode*lchild,*rchild;

}Bitreptr;

3.完成程序，說明其功能(6分)

#defineNULL0;

typedefstructBitnode{

chardata;

StnictBitnode*Ichild,*rchild;

}Bitreptr;

voidinorder_notrecursive(Bitreptrbt,Status(Visit)(TelemTypee)))

{InitStack(S);

P=T;

while(P||!StackEmpty(s))

{if(P){Push(S,P);；

else{

Pop(S,P);

if(!Visit(P->data))returnError;

{returnOK;

)

數(shù)據(jù)結構期末試卷B

一、判斷題：（共10分，每題1分）

1、滿二叉樹也是完全二叉樹。（）

2、二叉樹可以用0W度W2的有序樹來表示。（）

3、在只有度為0和度為k的結點的k叉樹中，設度為0的結點有n0個，度為k的結

點有nk個，則有nO=nk+l。（）

4、帶權連通圖中某一頂點到圖中另一頂點的最短路徑不一定唯一。（）

5、在n個結點的無向圖中，若邊數(shù)少于nT,則該圖必是非連通圖。（）

6、樹的帶權路徑長度最小的二叉樹中必定沒有度為1的結點。（）

7、哈希表的查找無需進行關鍵字的比較。（）

8、折半查找方法可以用于按值有序的線性鏈表的查找。（）

9、對一個堆按層次遍歷，不一定能得到一個有序序列。（）

10、由于希爾排序的最后一趟與直接插入排序過程相同，因此前者一定比后者花費的

時間多。（）

二、填空題：（共20分，每空2分）

1、度數(shù)為o的結點，即沒有子樹的結點叫作結點。同一個結點的兒子結點之

間互稱為結點。

2、在具有n個結點的二叉鏈表中，有個空鏈域。

3、一個無向圖采用鄰接矩陣存儲方法，其鄰接矩陣一定是一個。

4、給定序列{100,86,48,73,35,39,42,57,66,21},按堆結構的定義，則它是一個

堆。

5、在進行直接插入排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列關；而在進行

直接選擇排序時,其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列關。

6、結點關鍵字轉換為該結點存儲單元地址的函數(shù)H稱為或叫。

7、對n個關鍵字的序列進行快速排序，平均情況下的空間復雜度為一。

三、選擇題：（共20分，每題2分）

1、將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點進行編號，根結點的

編號為1,則編號為49的結點的左孩子的編號為。

A.98B.99

C.50D.48

2、堆的形狀是一棵—_O

A.二叉排序樹B.滿二叉樹

C.完全二叉樹D.平衡二叉樹

3、對于哈希函數(shù)H（key）=keyMOD13,被稱為同義詞的關鍵字是

A.35和41B.23和39

C.15和44D.25和51

4、指出在順序表｛2、5、7、10、14、15、18、23、35>41、52｝中，用二分法查找12,需

做多少次比較。

A、2B、3

C、4I)、5

5、假設一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除與某個頂點vi相關的邊時

間復雜度是：

A.0(n)B.0(e)

C.0(n+e)D.0(n*e)

6、從二叉排序樹中查找一個元素時，其時間復雜度大致為。

A、0(n)B、0(1)

2

C、0(log2n)D、0(n)

7、由權值分別為3,8,6,2,5的葉子結點生成一棵赫夫曼樹，它的帶權路徑長度為。

A、24B、48

C、72D、53

8、設有字符序列｛Q、II、C、Y、P、A、M、S、R、D、F、X),一趟排序的結果為｛F、H、C、D、

P、A、M、Q、R、S、Y、X｝,則是下列哪個排序算法。

A、起泡排序B、初始步長為4的shell的排序

C、二路歸并排序D、以第一個元素為分界元素的快速排序

9、一個無向連通圖的生成樹是含有該連通圖的全部頂點的

A.極小連通子圖B.極小子圖

C.極大連通子圖1).極大子圖

10、圖的廣度優(yōu)先遍歷類似于二叉樹的。

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

C.后序遍歷1).層次遍歷

四、應用題：(共28分，每題4分)

1、如圖所示的二叉樹完成中序遍歷、后序遍歷、先序遍歷，并畫出中序線索化的二叉樹。

2、請給出下圖的鄰接矩陣和鄰接表，寫出從頂點a出發(fā)對此圖進行深度優(yōu)先和廣度優(yōu)先進

行遍歷的頂點序列。

4、已知-一表為(49,66,73,52,40,37,65,43),使按表中元素的次序依次插入?棵初

始為空的二叉排序樹，畫出表中元素構成的二叉排序樹。

5、已知一棵三階的B-樹如下圖所示，假定依次刪除關鍵字46,24,8,15請畫出每次刪除

結點后樹的情況：

6、已知一組關鍵字為(19,14,23,01,68,20,84,27,55,6,10,79),則按哈希

函數(shù)H(key)=keyMOD13和線性探測法解決沖突構造這組關鍵字的哈希表。

7、判斷下面的序列是否是堆？如果不是，則把它調整為堆：

(5,56,20,23,40,38,29,61,35,76,28,100)

五、程序題(共22分)

1、閱讀下列算法，并回答下列問題：(4分)

完善程序，并回答該算法完成什么功能？算法中r[n+l]的作用是什么？

voidsort(elemtyper[],intn)

{intk,i；

fbr(k=n-l;k>=l;k--)

if(r[k]>r[k+l])

{r[n+l]=r[k];

fbr(i=k+l;r[i]<r[n+l];i++)

r[i-l]=r[i];

________________；)

}}

2、完成下列程序，并說出該算法所完成的功能。(8分)

voidweizhisort(structnoder[n],intn)

{intlow,high,mid,j,i;

for(i=2;i<=n;i++)

{r[0]=r[i];

low=;

high=；

while(low<=high)

mid=(low+high)/2;

if(r[O].key<r[mid].key)

elselow=mid+l;}

fbr0=i-l;j>=l;j-)

r[j+l]=rU]；

r[high+l]=r[O];

}}

其中數(shù)據(jù)類型定義為：

structnode

{intkey;

Infbtypeotherinfb;

}

3、說出下面算法完成的功能。(2分)

voiddelete(inta[n],inti)

{if(i<0)||(i>=n)printf(44errorv);

else

{for(j=i-l；j<n;j++)

a[j]=a[j+l];

n=n-l;}

}

4、完善程序，說明其功能(8分)

#defineNULL0;

typedefstructBitnode{

chardata;

StructBitnode*lchild,*rchild;

|Bitreptr;

voidinorder_notrecursive(Bitreptrbt,Status(Visit)(TelemTypee)))

{InitStack(S);

P=T;

while(P||!StackEmpty(s))

{if(P){Push(S,P);

else(

if(!Visit(P->data))returnError;

}

}returnOK;

}

題庫

一、判斷題：

1、線性表的邏輯順序與物理順序總是一致的。（）

2、線性表的順序存儲表示優(yōu)于鏈式存儲表示。（）

3、線性表若采用鏈式存儲表示時所有結點之間的存儲單元地址可連續(xù)可不連續(xù)。（）

4、二維數(shù)組是其數(shù)組元素為線性表的線性表。（）

5、每種數(shù)據(jù)結構都應具備三種基本運算：插入、刪除和搜索。（）

6、數(shù)據(jù)結構概念包括數(shù)據(jù)之間的邏輯結構，數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個

方面。（）

7、線性表中的每個結點最多只有一個前驅和一個后繼。（）

8、線性的數(shù)據(jù)結構可以順序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)結構只能鏈接存儲。

（）

9、棧和隊列邏輯上都是線性表。（）

10、單鏈表從任何一個結點出發(fā)，都能訪問到所有結點（）

11、刪除二叉排序樹中一個結點，再重新插入上去，一定能得到原來的二叉排序樹。（）

12、快速排序是排序算法中最快的一種。（）

13、多維數(shù)組是向量的推廣。（）

14、一般樹和二叉樹的結點數(shù)目都可以為0。（）

15、直接選擇排序是一種不穩(wěn)定的排序方法。（）

16、98、對一個堆按層次遍歷，不一定能得到一個有序序列。（）

17、在只有度為0和度為k的結點的k叉樹中，設度為0的結點有n0個，度為k的結點有

nk個，則有n0=nk+l。（）

18、折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。（）

19、堆棧在數(shù)據(jù)中的存儲原則是先進先出。（）

20、隊列在數(shù)據(jù)中的存儲原則是后進先出。（）

21、用相鄰矩陣表示圖所用的存儲空間大小與圖的邊數(shù)成正比。（）

22、哈夫曼樹一定是滿二叉樹。（）

23、程序是用計算機語言表述的算法。（）

24、線性表的順序存儲結構是通過數(shù)據(jù)元素的存儲地址直接反映數(shù)據(jù)元素的邏輯關系。

（）

25、用一組地址連續(xù)的存儲單元存放的元素一定構成線性表。（）

26、堆棧、隊列和數(shù)組的邏輯結構都是線性表結構。（）

27、給定一組權值，可以唯一構造出一棵哈夫曼樹。（）

28、只有在初始數(shù)據(jù)為逆序時，冒泡排序所執(zhí)行的比較次數(shù)最多。（）

29、希爾排序在較率上較直接接入排序有較大的改進。但是不穩(wěn)定的。（）

30、在平均情況下，快速排序法最快，堆積排序法最節(jié)省空間。（）

31、快速排序法是一種穩(wěn)定性排序法。（）

32、算法一定要有輸入和輸出。（）

33、算法分析的目的旨在分析算法的效率以求改進算法。（）

34、非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接后繼元素。（）

35、數(shù)據(jù)的存儲結構不僅有順序存儲結構和鏈式存儲結構，還有索引結構與散列結構。

（）

36、若頻繁地對線性表進行插入和刪除操作，該線性表采用順序存儲結構更合適。（）

37、若線性表采用順序存儲結構，每個數(shù)據(jù)元素占用4個存儲單元，第12個數(shù)據(jù)元素的存

儲地址為144,則第1個數(shù)據(jù)元素的存儲地址是101o（）

38、若長度為n的線性表采用順序存儲結構，刪除表的第i個元素之前需要移動表中n-i+1

個元素。（）

39、符號p->next出現(xiàn)在表達式中表示p所指的那個結點的內(nèi)容。（）

40、要將指針p移到它所指的結點的下一個結點是執(zhí)行語句p-p->next。（）

41、若某堆棧的輸入序列為1,2,3,4,則4,3,1,2不可能是堆棧的輸出序列之一。（）

42、線性鏈表中各個鏈結點之間的地址不一定要連續(xù)。（）

43、程序就是算法，但算法不一定是程序。（）

44、線性表只能采用順序存儲結構或者鏈式存儲結構。（）

45、線性表的鏈式存儲結構是通過指針來間接反映數(shù)據(jù)元素之間邏輯關系的。（）

46、除插入和刪除操作外，數(shù)組的主要操作還有存取、修改、檢索和排序等.（）

47、稀疏矩陣中0元素的分布有規(guī)律，因此可以采用三元組方法進行壓縮存儲。（）

48、不管堆棧采用何種存儲結構，只要堆棧不空，可以任意刪除一個元素。（）

49、確定串T在串S中首次出現(xiàn)的位置的操作稱為串的模式匹配。（）

50、深度為h的非空二叉樹的第i層最多有2i-l個結點。（）

51、滿二叉樹也是完全二叉樹。（）

52、已知一棵二叉樹的前序序列和后序序列可以唯一地構造出該二叉樹。（）

53、非空二叉排序樹的任意一棵子樹也是二叉排序樹。（）

54、對一棵二叉排序樹進行前序遍歷一定可以得到一個按值有序的序列。（）

55、一個廣義表的深度是指該廣義表展開后所含括號的層數(shù)。（）

56、散列表的查找效率主要取決于所選擇的散列函數(shù)與處理沖突的方法。（）

57、序列初始為逆序時，冒泡排序法所進行的元素之間的比較次數(shù)最多。（）

58、已知指針P指向鍵表L中的某結點，執(zhí)行語句P=P-＞next不會刪除該鏈表中的結點。

（）

59、在鏈隊列中，即使不設置尾指針也能進行入隊操作。（）

60、如果一個串中的所有字符均在另一串中出現(xiàn)，則說前者是后者的子串。（）

61＞設與一棵樹T所對應的二叉樹為BT,則與T中的葉子結點所對應的BT中的結點也一定

是葉子結點。（）

62、若圖G的最小生成樹不唯、則G的邊數(shù)一定多于n-1,并且權值最小的邊有多條（其

中n為G的頂點數(shù)）。（）

63、給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。（）

64、由于希爾排序的最后一趟與直接插入排序過程相同，因此前者一定比后者花費的時間多。

（）

65、程序越短，程序運行的時間就越少。（）

66、采用循環(huán)鏈表作為存儲結構的隊列就是循環(huán)隊列。（）

67、堆棧是一種插入和刪除操作在表的一端進行的線性表。（）

68、一個任意串是其自身的子串。（）

69、哈夫曼樹一定是完全二叉樹。（）

70、帶權連通圖中某一頂點到圖中另一定點的最短路徑不一定唯一。（）

71、折半查找方法可以用于按值有序的線性鏈表的查找。（）

72、稀疏矩陣壓縮存儲后，必會失效掉隨機存取功能。（）

73＞由一棵二叉樹的前序序列和后序序列可以唯?確定它。（）

74、在n個結點的元向圖中，若邊數(shù)在于nT,則該圖必是連通圖。（）

75、在完全二叉樹中，若某結點元左孩子，則它必是葉結點。（）

76、若一個有向圖的鄰接矩陣中，對角線以下元素均為0,則該圖的拓撲有序序列必定存在。

（）

77、樹的帶權路徑長度最小的二叉樹中必定沒有度為1的結點。（）

78、二叉樹可以用0〈度＜2的有序樹來表示。（）

79、一組權值，可以唯一構造出一棵哈夫曼樹。（）

80、101,88,46,70,34,39,45,58,66,10）是堆；（）

81、將一棵樹轉換成二叉樹后，根結點沒有左子樹；（）

82、用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷；（）

83、在非空線性鏈表中山p所指的結點后面插入一個山q所指的結點的過程是依次執(zhí)行語句：

q->next=p->next;p->next=q?（）

84、非空雙向循環(huán)鏈表中由q所指的結點后面插入一個由p指的結點的動作依次為：

p->prior=q,p->next=q->next,q->next=p,q->prior->next—p（>（）

85、刪除非空鏈式存儲結構的堆棧（設棧頂指針為top）的一個元素的過程是依次執(zhí)

行：p=top,top=p->next,free（p）。（）

86、哈希的查找無需進行關鍵字的比較。（）

87、一個好的哈希函數(shù)應使函數(shù)值均勻的分布在存儲空間的有效地址范圍內(nèi)，以盡可能減少

沖突。（）

88、排序是計算機程序設計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素（或記錄）的任

意序列，重新排列成一個按關鍵字有序的序列。（）

89、隊列是一種可以在表頭和表尾都能進行插入和刪除操作的線性表。（）

90、在索引順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不與表的個數(shù)有

關，而與每一塊中的元素個數(shù)有關。（）

91、對于有向圖，頂點的度分為入度和出度，入度是以該頂點為終點的入邊數(shù)目；出度是以

該頂點為起點的出邊數(shù)目，該頂點的度等于其入度和出度之和。（）

92、無向圖的鄰接矩陣是對稱的有向圖的鄰接矩陣是不對稱的。（）

93、具有n個頂點的連通圖的生成樹具有n-1條邊（）

二、填空題：

1、《數(shù)據(jù)結構》課程討論的主要內(nèi)容是數(shù)據(jù)的邏輯結構、存儲結構和。

2、數(shù)據(jù)結構算法中，通常用時間復雜度和兩種方法衡量其效率。

3、一個算法一該具有,,,和—這五種特性。

4、若頻繁地對線性表進行插入與刪除操作，該線性表應采用存儲結構。

5、在非空線性表中除第一個元素外，集合中每個數(shù)據(jù)元素只有一個；除最后一個元

素之外，集合中每個數(shù)據(jù)元素均只有一個o

6、線性表中的每個結點最多有前驅和后繼。

7、鏈表從任何一個結點出發(fā)，都能訪問到所有結點。

8、鏈式存儲結構中的結點包含域，域。

9、在雙向鏈表中，每個結點含有兩個指針域，一個指向結點，另一個指向

結點。

10、某帶頭結點的單鏈表的頭指針head,判定該單鏈表非空的條件o

11、在雙向鏈表中，每個結點含有兩個指針域，一個指向結點，另一個指向

結點。

12、已知指針p指向單鏈表中某個結點，則語句p->next=p->next->next的作用_刪除p的

后繼結點一

13、已知在結點個數(shù)大于1的單鏈表中，指針p指向某個結點，則下列程序段結束時，指針

q指向*p的結點。

q=p;

while(q->next!=p)

q=q->next;

14、若要在單鏈表結點*P后插入一結點*S,執(zhí)行的語句o

15、線性表的鏈式存儲結構地址空間可以，而向量存儲必須是地址空間

16、棧結構允許進行刪除操作的一端為。

17、在棧的順序實現(xiàn)中，棧頂指針top,棧為空條件?

18、對于單鏈表形式的隊列，其空隊列的F指針和R指針都等于。

19、若數(shù)組s[0..n-l]為兩個棧si和s2的共用存儲空間，僅當s[0..n-l]全滿時，各棧才不能

進行棧操作，則為這兩個棧分配空間的最佳方案是：si和s2的棧頂指針的初值分別為

20、允許在線性表的一端插入,另一端進行刪除操作的線性表稱為o插入的一端為

，刪除的一端為。

21、設數(shù)組A[m]為循環(huán)隊列Q的存儲空間，fbnt為頭指針，rear為尾指針，判定Q為空隊

列的條件。

22、對于順序存儲的隊列，存儲空間大小為n,頭指針為F,尾指針為R。若在邏輯上看一

個環(huán)，則隊列中元素的個數(shù)為。

23、已知循環(huán)隊列的存儲空間為數(shù)組data[21],且頭指針和尾指針分別為8和3,則該隊列

的當前長度o

24、一個串的任意個連續(xù)的字符組成的子序列稱為該串的,包含該子串的串稱為

25、求串T在主串S中首次出現(xiàn)的位置的操作是o

26、在初始為空的隊列中插入元素A,B,C,D以后，緊接著作了兩次刪除操作，此時的隊尾元

素是.

27、在長度為n的循環(huán)隊列中，刪除其節(jié)點為x的時間復雜度為o

28、已知廣義表L為空，其深度為?

29、已知一順序存儲的線性表，每個結點占用k個單元，若第個結點的地址為DA1,則

第i個結點的地址為。

30、設一行優(yōu)先順序存儲的數(shù)組A[5][6],A[0][0]的地址為1100,且每個元素占2個存儲單

元，則A[2][3]的地址為?

31、設有二維數(shù)組A[9][19],其每個元素占兩個字節(jié)，第一個元素的存儲地址為100,若按

行優(yōu)先順序存儲，則元素A[6,6]的存儲地址為,按列優(yōu)順序存儲，元素A[6,6]

的存儲地址為。

32、在進行直接插入排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列關；而在進行直接

選擇排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列關。

33、假設以行為優(yōu)先存儲的三維數(shù)組A[5][6][7],A[0皿皿]的地址為1100,每個元素占兩個

存儲單元，則A[4][3][2]的地址為。

34、設二維數(shù)組A[m][n]按列優(yōu)先存儲，每個元素占1個存儲單元，元素Aoo的存儲地址

loc(Aoo),則Ay的存儲地址loc(Ajj)=。

35、稀疏矩陣一般采用方法進行壓縮存儲。

36、稀疏矩陣可用進行壓縮存儲，存儲時需存儲非零元的、、

________O

37、若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0,

則稱為。

38、若一個n階矩陣A中的元素滿足：AfAj,(O<=I,j<=n-l)則稱A為矩陣；

若主對角線上方(或下方)的所有元素均為零時，稱該矩陣為。

39、對于上三角形和下三角形矩陣，分別以按行存儲和按列存儲原則進行壓縮存儲到數(shù)組

M[k]中，若矩陣中非0元素為A.,則k對應為和?

40、設有一上三角形矩陣A[5][5]按行壓縮存儲到數(shù)組B中，B[0]的地址為100,每個元素

占2個單元，則A[3][2]地址為。

41、廣義表(A,(a,b),d,e,((i,j),k))，則廣義表的長度為,深度為。

42己知廣義表人=(值,1>,<：),((1,6,。),則運算1162&1162(1佃口(人))))=。

43、已知廣義表Is=(a,(b,c,d),e),運用head和tail函數(shù)取出1s中的原子b的運算是。

44、在樹結構里，有且僅有一個結點沒有前驅，稱為根。非根結點有且僅有一個,

且存在一條從根到該結點的。

45、度數(shù)為0的結點，即沒有子樹的結點叫作結點或結點。同一個結

點的兒子結點之間互稱為結點。

46、假定一棵樹的廣義表為A(B(e),C(F(h,i,j),g),D),則該樹的度為,樹的深度為

,終端結點為,單分支結點為，雙分支結點個數(shù)為，三分支結點

為，C結點的雙親結點是,孩子結點是。

48、完全二叉樹、滿二叉樹、線索二叉樹和二叉排序樹這四個名詞術語中，與數(shù)據(jù)的存儲結

構有關系的是?

47、有三個結點的二叉樹，最多有種形狀。

48、每一趟排序時從排好序的元素中挑出一個值最小的元素與這些未排小序的元素的第一個

元素交換位置，這種排序方法成為排序法。

49、高度為k的二叉樹具有的結點數(shù)目，最少為，最多為。

50、對任何一棵二叉樹，若n0,nl,n2分別是度為0,1,2的結點的個數(shù)，則n0=。

51、在含100個結點的完全二叉樹，葉子結點的個數(shù)為。

52、將一個數(shù)據(jù)元素(或記錄)的任意序列，重新排列成一個按關鍵字有序的序列叫。

53、若一棵滿二叉樹含有121個結點，則該樹的深度為。

54、一個具有767個結點的完全二叉樹，其葉子結點個數(shù)為。

55、深度為90的滿二叉樹，第11層有個結點。

56、有100個結點的完全二叉樹，深度為?

57、設一棵二叉樹中度為2的結點10個，則該樹的葉子個數(shù)為。

58、若待散列的序列為(18,25,63,50,42,32,9),散列函數(shù)為H(key尸keyMOD9,與18發(fā)生沖

突的元素有個。

59、含有3個2度結點和4個葉結點的二叉樹可含個1度結點。

60、一棵具有5層滿二叉樹中節(jié)點總數(shù)為。

61、一棵含有16個結點的完全二叉樹，對他按層編號，對于編號為7的結點，他的雙親結

點及左右結點編號為、、。

62、深度為k(設根的層數(shù)為1)的完全二叉樹至少有個結點，至多有個結點。

63、若要對某二叉排序樹進行遍歷，保證輸出所有結點的值序列按增序排列，應對該二叉排

序樹采用遍歷法。

64、在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24,需要

進行次元素之間的比較。

65、設有10個值，構成哈夫曼樹，則該哈夫曼樹共有個結點。

66、從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的。

67、關鍵字自身作為哈希函數(shù)，即H(k)=k,也可自身加上一個常數(shù)作為哈希函數(shù)，即

H(k)=k+C這種構造哈希函數(shù)的方式叫。

68、對于一個圖G,若邊集合E(G)為無向邊的集合，則稱該圖為o

69、對于一個圖G,若邊集合E(G)為有向邊的集合，則稱該圖為o

70、對于有向圖，頂點的度分為入度和出度，以該頂點為終點的邊數(shù)目叫:以該頂

點為起點的邊數(shù)目叫。

71、一個無向圖采用鄰接矩陣存儲方法，其鄰接矩陣一定是一個o

72、有一個n個頂點的有向完全圖的弧數(shù)。

73、在無向圖中，若從頂點A到頂點B存在,則稱A與B之間是連通的。

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

75、一個連通圖的生成樹是該圖的連通子圖。若這個連通圖有n個頂點，則它

的生成樹有條邊。

76、無向圖的鄰接矩陣是一個矩陣。

77、如果從?無向圖的任意頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定

是_____________

78、若采用鄰接表的存儲結構，則圖的廣度優(yōu)先搜索類似于二叉樹的遍歷。

79、若圖的鄰接矩陣是對稱矩陣，則該圖一定是。

80、從如圖所示的臨接矩陣可以看出，該圖共有個頂點。如果是有向圖，該圖共有

條??；如果是無向圖，則共有條邊。ABC

81、如果從一個頂點出發(fā)又回到該頂點，則此路徑叫做。_o1rA

82、一個具有個n頂點的無向圖中，要連通全部頂點至少需要條邊。

B二001B

83、給定序列{100,86,48,73,35,39,42,57,66,21},按堆結構的定義,則它一010C

定堆。

84、從未排序序列中選擇一個元素，該元素將當前參加排序的那些元素分成前后兩個部分,

前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而

此時所選元素處在排序的最終位置。這種排序法稱為排序法。

85、折半搜索只適合用于。

86、結點關鍵字轉換為該結點存儲單元地址的函數(shù)H稱為或叫。

87、在索引查找中，首先查找,然后查找相應的,整個索引查找的平均

查找長度等于查找索引表的平均長度與查找相應子表的平均查找長度的o

三、選擇題:

()1.數(shù)據(jù)結構通常是研究數(shù)據(jù)的—及它們之間的聯(lián)系。

A存儲和邏輯結構B存儲和抽象

C理想和抽象D理想與邏輯

<)2.在堆棧中存取數(shù)據(jù)的原則是

A先進先出B后進先出

C先進后出D隨意進出

()3.將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點進行編號，根

結點的編號為1,則編號為49的結點的左孩子的編號為o

A.98B.99

C.50D.48

()4.對于如圖所示二叉樹采用中根遍歷，正確的遍歷序列應為()

A.ABCDEFB.ABECDF

C.CDFBEAD.CBDAEF

()5.設有100個元素，用折半查找法進行查找時，最大比較次數(shù)是一

A.25B.50

C.10D.7

()6.快速排序在____情況下最易發(fā)揮其長處。

A.被排序數(shù)據(jù)中含有多個相同排序碼B.被排序數(shù)據(jù)已基本有序

C.被排序數(shù)據(jù)完全無序D.被排序數(shù)據(jù)中最大值和最小值相差懸殊

()7.由兩個棧共享一個向量空間的好處是。

A減少存取時間，降低下溢發(fā)生的機率B節(jié)省存儲空間，降低上溢發(fā)生的機率

C減少存取時間，降低上溢發(fā)生的機率D節(jié)省存儲空間，降低下溢發(fā)生的機率

()8.某二叉樹的前序和后序序列正好相反，則該二叉樹一定是的二叉樹

A空或者只有一個結點B高度等于其結點數(shù)

C任一結點無左孩子D任一結點無右孩子

()9.設散列表長m=14,散列函數(shù)H(K)=K%H,已知表中已有4個結點：r(15)=4;

r(38)=5;r(61)=6;r(84)=7,其他地址為空，如用二次探測再散列處理沖突，關鍵字為49

的結點地址是.

A8B3

C5D9

()10.在含有n個項點有e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為。

A.eB.2e

C.n2~eD.n2-2e

()11.圖的深度優(yōu)先遍歷類似于二叉樹的。

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

C.后序遍歷