數(shù)據(jù)結(jié)構(gòu)填空題

一、填空題（每空1分，共156分）10.假定一棵三叉樹（即度為3的樹）的結(jié)點個數(shù)

為50,則它的最小高度為（）。假定樹根結(jié)點的

1.數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)包括順序、（）、索引深度為0。

和散列等四種?！敬鸢浮?

【答案】鏈接

11.二維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個數(shù)

2.設(shè)關(guān)鍵字序列組元素最多有（）個直接前驅(qū)（或者直接后繼）。

{7,12,26,30,47,58,66,70,82,90},當(dāng)用折半查找方【答案】兩個

法查找時，所需比較的次數(shù)為3次的關(guān)鍵字分別是

（）O12.在堆排序中，對任意一個分支結(jié)點進行調(diào)整運

【答案】7265882算的時間復(fù)雜度為（）o

【答案】0（logn）

2

3.假定一個線性表為{12,23,74,55,63,40,

82,36},若按key%3條件進行劃分，使得同一余數(shù)13.隊列的刪除操作在（）進行。

的元素成【答案】隊頭（或者隊首）

為一個子表，則包含74的子表長度為（）。

【答案】214.設(shè)圖G=（V,E）,V={1,2,3,4},E={<1,

2>,<1,3>,<2,4>,<3,4>},從頂點1出發(fā),對

4.和二分查找相比，順序查找的優(yōu)點是除了不要求圖G進行

表中數(shù)據(jù)元素有序之外，對（）結(jié)構(gòu)也無特殊要求。廣度優(yōu)先搜索的序列有（）種。

【答案】存儲【答案】2

5.設(shè)雙向循環(huán)鏈表每一個結(jié)點結(jié)構(gòu)為15.向一棵二叉搜索樹中插入一個元素時，若元素

的值小于根結(jié)點的值，則應(yīng)把它插入到根結(jié)點的

（data,llink,rlink）,則結(jié)點*p的前驅(qū)結(jié)點的地址

（）上。

為（）。

【答案】左子樹

【答案】p->llink

16.快速排序在平均情況下的時間復(fù)雜度為（兀

6.n個頂點的連通無向圖的生成樹含有（）條邊?！敬鸢浮?（nlogn）

【答案】2

n-l

17.由關(guān)鍵字序列{42,97,75,23,68,34）建成的最大

7.在一個最大堆中，堆頂結(jié)點的值是所有結(jié)點中堆是（）。

的（）?！敬鸢浮?7,68,75,23,42,34

【答案】最大值

18.對于關(guān)鍵字序列（12,13,11,18,60,

8.假定對長度n=50的有序表進行折半搜索，則對15,7,18,25,100）,用篩選法建堆，必須

應(yīng)的判定樹中最底下一層的結(jié)點數(shù)為（）個。

從關(guān)鍵字為（）的

【答案】19

結(jié)點開始。

［答案］60

9.對于帶頭結(jié)點的鏈棧top,取棧頂元素的操作是

（）。

19.從有序表（12,18,30,43,56,78,82,95）中折半

［答案）*y=top->next->data

搜索元素56時，其搜索長度為（）。

【答案】3

萬維試題庫系統(tǒng)第1頁

20.設(shè)有二叉樹根結(jié)點的層次為0,一棵高度為h的30.數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)和（）結(jié)

滿二叉樹中的葉子結(jié)點個數(shù)是（）。構(gòu)兩大類。

【答案】2h【答案】非線性

21.在一個最小堆中，堆頂結(jié)點的值是所有結(jié)點中31.隊列是具有（）特性的線性表。

的（）?！敬鸢浮肯冗M先出

【答案】最小值

32.基本數(shù)據(jù)類型是計算機已經(jīng)實現(xiàn)了的（）。

22.在長度為n的順序表中刪除一個元素時，等概率【答案】數(shù)據(jù)結(jié)構(gòu)

情況下的平均挪移元素的次數(shù)是（）。

【答案】（n-l）/233.n個頂點且含有環(huán)路的無向連通圖中，至少含有

（）條邊。

23.由關(guān)鍵字序列（57,24,76,63,18,31,15）生成的【答案】n

一棵二叉排序樹，其等查找概率情況下查找成功的平

34.若設(shè)L是指向帶表頭的單鏈表，語句

均查找長度為

L->link=L->link->link的作用是（）單鏈表中的

（）。

第一個結(jié)點。

【答案】18/7

【答案】刪除

24.數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、（）和數(shù)據(jù)的運算三個

35.已知8個數(shù)據(jù)元素為（34,76,45,18,26,54,

方面。

【答案】存儲結(jié)構(gòu)92,65）,按照挨次插入結(jié)點的方法生成一棵二叉排

序樹后，最后兩層

上的結(jié)點總數(shù)為（）。

25.在一棵m階B樹上，每一個非根結(jié)點的關(guān)鍵碼數(shù)

【答案】_2_

最多為（）個。

【答案】nrl

36.大小為M的順序存儲的循環(huán)隊列sq隊滿的條件為

（）。

26.在雙向鏈表中，每一個結(jié)點除了數(shù)據(jù)域外，還有兩

【答案】（sq.rear+l）%M=sq.front

個指針域，它們分別指向（）。

【答案】前趨結(jié)點和后繼結(jié)點

37.若設(shè)順序棧的最大容量為MaxSize,top==T表

示?？眨瑒t判斷棧滿的條件是（）。

27.普通來說,深度優(yōu)先生成樹的高度比廣度優(yōu)先

【答案】top=MaxSizeT

生成樹的高度要（）o

【答案】高

38.假定一個順序表的長度為40,并假定順序搜索

每一個元素的概率都相同，則在搜索成功情況下的

28.遞歸工作棧起到兩個作用，其一是將遞歸調(diào)用

平均搜索長度為（）。

時的實際參數(shù)和返回地址傳遞給下一層遞歸；其二

【答案】20,5

是保存本層的形

式參數(shù)和（）。

【答案】局部變量

39.在程序運行過程中不能擴充的數(shù)組是（）分

配的數(shù)組。這種數(shù)組在聲明它時必須指定它的大

29.在一個堆的順序存儲中，若一個元素的下標(biāo)為

小。

i（0Wi<n-l）,則它的右子女元素的下標(biāo)為（）。

【答案】靜態(tài)

【答案】2i+2

萬維試題庫系統(tǒng)第2頁

40.設(shè)有程序段為48.在一個鏈?zhǔn)疥犃兄?，若隊頭指針與隊尾指針的

for（i=l;i<10;i++）值相同，則表示該隊列至多有（）個結(jié)點。

for（j=l；j<=i；j++）【答案】一

,z

{p=i*j;printf（''%4d\nzp）;}

則執(zhí)行p=i*j的次數(shù)為（）.49.假定一棵二叉樹的結(jié)點數(shù)為18,則它的最小高

【答案】上度為（）。假定樹根結(jié)點的高度為0。

【答案】4

41.一棵高度為5的徹底二叉樹中，最多包含有

（）個結(jié)點。假定樹根結(jié)點的高度為0。50.在單鏈表中，除了表頭結(jié)點外，任意結(jié)點的

【答案】63存儲位置由其直接（）結(jié)點的指針域的值所指示。

【答案】前驅(qū)

42.第i（i=1,2,…，n-1）趟從參加排序的序

51.由分別帶權(quán)為9,6,2,5,7的五個葉子結(jié)點構(gòu)

列中取出第i個元素，把它插入到由第0個至第i-1

造的哈夫曼樹的帶權(quán)路徑長度為（）?

個元素組成的

【答案】巧

有序表中適當(dāng)?shù)奈恢?，此種排序方法叫做（）排

序。

52.對長度為20的有序表進行二分查找的判定樹

【答案】直接插入

的高度為（）。

【答案】5

43.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素A,B,C,

D,E,和F挨次通過棧S,且一個元素出棧后即進入隊53.快速排序在平均情況下的空間復(fù)雜度為（）o

列Q,若6個元素出【答案】OQog/）

隊列的順序是B,D,C,F,E,A,則棧S的容量至少

是（）。

54.在一個鏈?zhǔn)疥犃兄?，若隊頭指針與隊尾指針的

【答案】3值相同，則表示該隊列至多有（）個結(jié)點。

【答案】1

44.若設(shè)串S=''documentHash.doc\0z/,則該字符

串S的長度為（）。

55.隊列是一種限定在表的一端插入，在另一端刪

【答案】16

除的線性表，它又被稱為（）表。

【答案】先進先出

45.在對m階B樹插入元素的過程中，每向一個結(jié)

點插入一個關(guān)鍵碼后，若該結(jié)點的關(guān)鍵碼個數(shù)等于

56.當(dāng)用長度為MaxSize的數(shù)組順序存儲一個棧

（）個，則必須

時，若用top==MaxSize表示?？?，則表示棧滿的

把它分裂為2個結(jié)點。

條件為（）。

m

【答案】top=0

46.棧是一種限定在表的一端進行插入和刪除的線性

57.若進棧序列為a,b,c,且進棧和出?？梢源┎?/p>

表，又被稱為（）表。進行，則可能浮現(xiàn)（）個不同的出棧序列。

【答案】后出先進

【答案】5

47.在無向圖G的鄰接矩陣表示中，第j列中非零元的

58.若設(shè)一個n的矩陣A的開始存儲地址LOC（O,0）及元

個數(shù)等于該頂點的（）?

素所占存儲單元數(shù)d已知，按行存儲時其任意一個矩陣元

【答案】度

素的存儲地址為（）。

【答案】LOC（O,0）+（i*n+j）*d

萬維試題庫系統(tǒng)第3頁

59.如果n個頂點的圖是一個環(huán)，則它有（）棵生成70.將一棵樹按照左子女-右兄弟表示法轉(zhuǎn)換成對

樹。應(yīng)的二叉樹，則該二叉樹中樹根結(jié)點肯定沒有（）

案】n子女。

【答案】右

60.設(shè)有程序段為：

for（i=l;i<=10;i++）71.由帶權(quán)為9,6,2,5,7的五個葉子結(jié)點構(gòu)造的

哈夫曼樹，其根結(jié)點的權(quán)值為（）。

for（j=l;j<=i;j++）p=i*j;

【答案】雀_

則執(zhí)行p=i*j的次數(shù)為（）。

【答案】組

72.11個頂點的連通網(wǎng)絡(luò)N有10條邊，其中權(quán)值為

1,2,3,4,5的邊各2條，則網(wǎng)絡(luò)N的最小生成樹

61.在單鏈表中某P結(jié)點后插入S結(jié)點的操作是（）。

【答案】s->next=p->next;p->next=s;各邊的權(quán)值之和為（）o

【答案】30

62.以順序搜索方法從長度為n的順序表或者單鏈

表中搜索一個元素的漸進時間復(fù)雜度為（）。73.線性表是由n缶20）個（）組成的有限序列。

【答案】數(shù)據(jù)元素

【答案】0（n）

63.在直接選擇排序中，記錄比較次數(shù)的時間復(fù)雜

74.給定一組數(shù)據(jù)對象的關(guān)鍵碼為{46,79,56,

度為（）o

【答案】0（n2）38,40,84},對其進行一趟快速排序處理，得到

的右子表中有（）個對象。

【答案】3

64.棧下溢是指在（）時進行出棧操作。

【答案】?？?/p>

75.將一個n階對稱矩陣的上三角部份或者下三角

65.在單鏈表設(shè)置表頭結(jié)點的作用是插入和刪除

部分壓縮存放于一個一維數(shù)組中，則一維數(shù)組需

表中第一個元素時不必對（）進行特殊處理。

【答案】表頭指針要存儲（）個矩陣元素。

【答案】n（n+l）/2

66.一維數(shù)組所占用的空間是連續(xù)的。但數(shù)組元素不一

定順序存取，通常是按元素的（）存取的。

76.對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度

【答案】下標(biāo)（或者順序號）

數(shù)之和為（）o

【答案】n-1

67.利用三元組表存放稀疏矩陣中的非零元素，則在三

元組表中每一個三元組元素對應(yīng)一個非零元素的行號、

77.在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)的最小生成

列

號和（）。樹時，惟獨當(dāng)一條候選邊的兩個端點不在同一個

【答案】值（）上，才會被加

入到生成樹中。

【答案】連通分量

68.克魯斯卡爾算法合用于求（）的網(wǎng)的最小生成

樹。

【答案】邊稀疏78.設(shè)序列{25,36,40,45,48,56,60,68,72,85},當(dāng)

用折半查找方法查找36時，所需比較的次數(shù)為（）。

【答案】_2_

69.用鏈表表示線性表,表中元素之間的邏輯關(guān)系是

通過鏈表中結(jié)點的（）來實現(xiàn)的。

【答案】指針

萬維試題庫系統(tǒng)第4頁

79.哈希查找是通過（）來確定記錄的存儲地址的。90.單鏈表中邏輯上相鄰的結(jié)點而在物理位置上

【答案】哈希函數(shù)（）相鄰。

【答案】不一定

80.對n個數(shù)據(jù)對象進行堆排序，總的時間復(fù)雜度

為（兀91.鏈表只合用于（）查找。

【答案】O（nlogn）【答案】順序

2

81.在線性表的散列存儲中，裝載因子a又稱為裝92.在堆排序中，如果n個對象的初始堆已經(jīng)建好，

載系數(shù)，若用m表示散列表的長度，n表示待散列存那末到排序結(jié)束，還需要從堆頂結(jié)點出發(fā)調(diào)用（）

儲的元素的個次調(diào)整算法。

數(shù)，則a等于（）?！敬鸢浮縩-1

【答案】n/m

93.向一個順序棧插入一個元素時，首先使（）后移

82.設(shè)圖的頂點數(shù)為n,則求解最短路徑的Dijkstra算

一個位置，然后把待插入元素寫入到這個位置上。

法的時間復(fù)雜度為（）.

【答案】棧頂指針

【答案】03）

94.在帶表頭結(jié)點的單鏈表中刪除某一指定結(jié)點，必

83.已知一棵3階B樹中含有50個關(guān)鍵碼，則該樹的

須找到該結(jié)點的（）結(jié)點。

最大高度為（）o

【答案】前一個

【答案】5

95.在一棵高度為3的四叉樹中，最多含有（）

84.從一棵二叉搜索樹中搜索一個元素時，若給定

個結(jié)點，假定樹根結(jié)點的高度為0。

值大于根結(jié)點的值，則需要向（）繼續(xù)搜索。

【答案】85

【答案】右子樹

96.在含有3個結(jié)點a,b,c的二叉樹中，前序序列為abc

85.鏈接存儲表示的結(jié)點存儲空間普通在程序的

且后序序列為cba的二叉樹有（）棵。

運行過程中進行動態(tài)地（）和釋放。

【答案】分配【答案】4

86.線性表的鏈接存儲只能通過（）順序訪問。97.設(shè)圖G=（V,E）,V={VO,VI,V2,V3},E=

【答案】鏈接指針{（VO,VI）,（VO,V2）,（VO,V3）,（VI,V3）},則

從頂點

V0開始的圖G的不同深度優(yōu)先序列有（）種。

87.直接插入排序在初始有序時，進行（）次關(guān)鍵

【答案】4

字比較。

【答案】n-1

98.在普通情況下用直接插入排序、選擇排序和冒

泡排序的過程中，所需記錄交換次數(shù)至少的是

88.若將一棵樹A（B（C,D,E）,F（G（H）,I））按照左子女一

（）。

右兄弟表示法轉(zhuǎn)換為二叉樹，該二叉樹中度為2的結(jié)點的

【答案】選擇排序

個數(shù)為（）個。

【答案】2

99.在鏈表的結(jié)點中，數(shù)據(jù)元素所占的存儲量和整

89.每次直接或者通過基準(zhǔn)元素間接比較兩個元素

個結(jié)點所占的存儲量之比稱作（）o

,若浮現(xiàn)逆序羅列就交換它們的位置，這種排序

【答案】存儲密度

方法叫做（）排序。

【答案】交換

萬維試題庫系統(tǒng)第5頁

100.用鄰接矩陣存儲圖，占用的存儲空間與圖中110.第i（i=0,l,...,n-2）趟從參加排序的序列

的（）數(shù)有關(guān)。中第i個至第nT個元素中挑選出一個最小元素，把

【答案】頂點它交換到第i個

位置，此種排序方法叫做（）排序。

101.對稱矩陣的行數(shù)與列數(shù)（）且以主對角線為【答案】直接選擇

對稱軸，a=a,因此只存儲它的上三角部份或

者

下三角部曲即可：111.快速排序在最壞情況下的時間復(fù)雜度為

（）o

【答案】相等

【答案】Ofe）

102.在直接選擇排序中，記錄挪移次數(shù)的時間復(fù)

112.由關(guān)鍵字序列{36,96,84,18,52,27}建成的最

雜度為（）o小堆是（）。

【答案】0（n）

【答案】（18,36,27,96,52,84）

103.對關(guān)鍵字序列（15,18,11,13,19,16,12,113.深度為10的徹底二叉樹，至少有（）個結(jié)點。

17,10,8）進行增量為5的一趟希爾排序的結(jié)果為【答案】512

（）?

114.在一棵二叉樹中，假定雙分支結(jié)點數(shù)為5個，

【答案】（15,12,11,10,8,16,18,17,13,單分支結(jié)點數(shù)為6個，則葉子結(jié)點數(shù)為（）個。

19）【答案】6

104.已知徹底二叉樹有200個結(jié)點，則整個二叉樹有115.向一個棧頂指針為top的鏈?zhǔn)綏Ｖ胁迦胍粋€

（）個度為1的結(jié)點。新結(jié)點*P時，應(yīng)執(zhí)行（）和top=p操作。

【答案】_L【答案】p->link=top

105.普里姆算法合用于求（）的網(wǎng)的最小生成樹。116.假設(shè)用<x,y>表示樹的邊（其中x是y的雙親），

【答案】邊稠密已知一棵樹的邊集為

{<b,d>,<a,b>,<c,g>,<c,f>,<c,h>,<a,c>},該樹的度是

106.在一個堆的順序存儲中，若一個元素的下標(biāo)（）o【答案】3

為i（OWiWnT）,則它的左子女元素的下標(biāo)為

（）?117,設(shè)待排序的表為（42,55,12,47,94,06,

【答案】2i+l18,63）,利用快速排序方法對其進行排序，經(jīng)第一

趟排序后，表的狀態(tài)為（）。

107.若用鄰接矩陣表示有向圖，則頂點i的入度等［答案］（18.06.12.42.94,47.55.63）

于矩陣中（）。

【答案】所對應(yīng)列中的非零元素個數(shù)118.估算算法時間復(fù)雜度時考慮的問題規(guī)模通常是

指算法求解問題的（）?

108.鏈隊列l(wèi)q為空的條件為（）?！敬鸢浮枯斎肓?/p>

［答案］La->rear=la.front

119.在一棵三叉樹中，度為3的結(jié)點數(shù)有2個，度

109.長度為11的有序表進行折半查找時，在等查找為2的結(jié)點數(shù)有1個，度為1的結(jié)點數(shù)為2個，那末度

性善藁劉堂找成功的平均查找長度為（兒為0的結(jié)點數(shù)有（）個。

【答案】6

萬維試題庫系統(tǒng)第6頁

120.n（n>0）個頂點的連通無向圖各頂點的度之和最130.設(shè)循環(huán)隊列用數(shù)組A[m]表示,隊頭、隊尾指針分

少為（）。別是front和rear,則判定隊滿的條件為（）。

【答案】2（n-l）【答案】（rear+1）%M=front

121.對n個元素的序列進行冒泡排序時，（）情況131.求解帶權(quán)連通圖最小生成樹的Prim算法使用

下比較次數(shù)至少，比較次數(shù)為（）。圖的（）作為存儲結(jié)構(gòu)。

【答案】初始數(shù)據(jù)有序n-1【答案】鄰接矩陣

122.在程序運行過程中可以擴充的數(shù)組是（）分132.在堆排序中，對n個記錄建立初始堆需要調(diào)用

配的數(shù)組。這種數(shù)組在聲明它時需要使用數(shù)組指（）次調(diào)整算法。

針?！敬鸢浮縩/2

【答案】動態(tài)

133.已知一棵二叉樹的先根序列為ABDFCE,

123.已知一棵3階B樹中含有50個關(guān)鍵碼，則該樹中根序列為DEBACE,則后根序列為（）。

的最小高度為（）o【答案】FDBECA

【答案】4

134.用折半查找法查找一個線性表中的元素時，此

124.僅允許在表的同一端進行插入和刪除運算的線線性表必須是（）。

性表被稱為（）o【答案】有序的

【答案】棧

135.在有向圖的鄰接矩陣表示中，第j列元素之和等

125.鏈表與順序表、索引表、散列表等都是數(shù)據(jù)于第j個頂點的（）。

邏輯結(jié)構(gòu)的（）表示。【答案】入度

【答案】存儲

136.在鏈表中進行插入和（）操作的效率比在順

126.如果一個對象部份地包含自己，或者自己定序存儲結(jié)構(gòu)中進行相同操作的效率高。

義自己，則稱這個對象是（）的對象?！敬鸢浮縿h除

【答案】遞歸

137.算法的一個特性是（），即算法必須執(zhí)行有限步

127.在有向圖的鄰接表表示中，每一