數(shù)據(jù)結(jié)構(gòu)（本科）期末綜合練習(xí)二（填空與判斷題）

填空題

1.數(shù)據(jù)是________的載體，它能夠被計(jì)算機(jī)程序識(shí)別、存儲(chǔ)和加工處理。

2.數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、________和數(shù)據(jù)的運(yùn)算三個(gè)方面。

3.數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)包括線(xiàn)性結(jié)構(gòu)和________結(jié)構(gòu)兩大類(lèi)。

4.數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)包括順序、________、索引和散列等四種。

5.基本數(shù)據(jù)類(lèi)型是計(jì)算機(jī)已經(jīng)實(shí)現(xiàn)了的________。

6.抽象數(shù)據(jù)類(lèi)型的特點(diǎn)是________、信息隱蔽、使用與實(shí)現(xiàn)分離。

7.算法的一個(gè)特性是________，即算法必須執(zhí)行有限步就結(jié)束。

8.面向?qū)ο蟮奶卣鲬?yīng)包括對(duì)象、類(lèi)、________、消息通信。

9.屬性與服務(wù)相同的對(duì)象構(gòu)成類(lèi)，類(lèi)中的每個(gè)對(duì)象稱(chēng)為該類(lèi)的________。

10.對(duì)象的私有狀態(tài)只能通過(guò)該對(duì)象的________才能改變。

11.模板類(lèi)是一種數(shù)據(jù)抽象，它把________當(dāng)作參數(shù)，可以實(shí)現(xiàn)類(lèi)的復(fù)用。

12.在類(lèi)的繼承結(jié)構(gòu)中，位于上層的類(lèi)叫做基類(lèi)，其下層的類(lèi)則叫做________類(lèi)。

13.一維數(shù)組所占用的空間是連續(xù)的。但數(shù)組元素不一定順序存取，通常是按元素的_________存取的。

14.在程序運(yùn)行過(guò)程中不能擴(kuò)充的數(shù)組是__________分配的數(shù)組。這種數(shù)組在聲明它時(shí)必須指定它的大小。

15.在程序運(yùn)行過(guò)程中可以擴(kuò)充的數(shù)組是__________分配的數(shù)組。這種數(shù)組在聲明它時(shí)需要使用數(shù)組指針。

16.二維數(shù)組是一種非線(xiàn)性結(jié)構(gòu)，其中的每一個(gè)數(shù)組元素最多有_________個(gè)直接前驅(qū)（或直接后繼）。

17.若設(shè)一個(gè)n′n的矩陣A的開(kāi)始存儲(chǔ)地址LOC(0,0)

及元素所占存儲(chǔ)單元數(shù)d已知，按行存儲(chǔ)時(shí)其任意一個(gè)矩陣元素a[i][j]的存儲(chǔ)地址為_(kāi)________。

18.對(duì)稱(chēng)矩陣的行數(shù)與列數(shù)_________且以主對(duì)角線(xiàn)為對(duì)稱(chēng)軸，aij

=

aji，因此只存儲(chǔ)它的上三角部分或下三角部分即可。

19.將一個(gè)n階對(duì)稱(chēng)矩陣的上三角部分或下三角部分壓縮存放于一個(gè)一維數(shù)組中，則一維數(shù)組需要存儲(chǔ)_________個(gè)矩陣元素。

20.將一個(gè)n階對(duì)稱(chēng)矩陣A的上三角部分按行壓縮存放于一個(gè)一維數(shù)組B中，A[0][0]存放于B[0]中，則A[I][J]在I≤J時(shí)將存放于數(shù)組B的_________位置。

21.利用三元組表存放稀疏矩陣中的非零元素，則在三元組表中每個(gè)三元組元素對(duì)應(yīng)一個(gè)非零元素的行號(hào)、列號(hào)和_________。

22.線(xiàn)性表是由n（n≥0）個(gè)_________組成的有限序列。

23.若設(shè)串S

=

“documentHash.doc＼0”，則該字符串S的長(zhǎng)度為_(kāi)________。

24.鏈表是一種采用

存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線(xiàn)性表。

25.鏈表只適用于

查找。

26.在鏈表中進(jìn)行插入和

操作的效率比在順序存儲(chǔ)結(jié)構(gòu)中進(jìn)行相同操作的效率高。

27.鏈表對(duì)于數(shù)據(jù)元素的插入和刪除不需要移動(dòng)結(jié)點(diǎn)，只需要改變相應(yīng)結(jié)點(diǎn)的__________的值。

28.鏈接存儲(chǔ)表示的結(jié)點(diǎn)存儲(chǔ)空間一般在程序的運(yùn)行過(guò)程中進(jìn)行動(dòng)態(tài)地_______和釋放。

29.單鏈表中邏輯上相鄰的結(jié)點(diǎn)而在物理位置上_______相鄰。

30.在單鏈表中,除了表頭結(jié)點(diǎn)外,任意結(jié)點(diǎn)的存儲(chǔ)位置由其直接_____結(jié)點(diǎn)的指針域的值所指示。

31.在單鏈表設(shè)置表頭結(jié)點(diǎn)的作用是插入和刪除表中第一個(gè)元素時(shí)不必對(duì)________進(jìn)行特殊處理。

32.若設(shè)L是指向帶表頭的單鏈表,語(yǔ)句

L->link=L->link->link的作用是________單鏈表中的第一個(gè)結(jié)點(diǎn)。

33.在雙向鏈表中,每個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域外,還有兩個(gè)指針域,它們分別指向_________________。

34.線(xiàn)性表的鏈接存儲(chǔ)只能通過(guò)________順序訪(fǎng)問(wèn)。

35.鏈表與順序表、索引表、散列表等都是數(shù)據(jù)邏輯結(jié)構(gòu)的__________表示。

36.設(shè)雙向循環(huán)鏈表每個(gè)結(jié)點(diǎn)結(jié)構(gòu)為(data,llink,rlink),則結(jié)點(diǎn)*p的前驅(qū)結(jié)點(diǎn)的地址為_(kāi)_________。

37.棧是一種限定在表的一端進(jìn)行插入和刪除的線(xiàn)性表，又被稱(chēng)為_(kāi)__________表。

38.隊(duì)列是一種限定在表的一端插入，在另一端刪除的線(xiàn)性表，它又被稱(chēng)為_(kāi)_______表。

39.向一個(gè)鏈?zhǔn)綏２迦胍粋€(gè)新結(jié)點(diǎn)時(shí)，首先把棧頂指針的值賦給新結(jié)點(diǎn)的指針域，然后把新結(jié)點(diǎn)的存儲(chǔ)位置賦給________。

40.隊(duì)列的刪除操作在________進(jìn)行。

41.向一個(gè)順序棧插入一個(gè)元素時(shí)，首先使________后移一個(gè)位置，然后把待插入元素寫(xiě)入到這個(gè)位置上。

42.若設(shè)順序棧的最大容量為MaxSize，top==-1表示?？?，則判斷棧滿(mǎn)的條件是________________。

43.當(dāng)用長(zhǎng)度為MaxSize的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，若用top

==

MaxSize表示?？?，則表示棧滿(mǎn)的條件為_(kāi)_______。

44.向一個(gè)循環(huán)隊(duì)列中插入元素時(shí)，需要首先移動(dòng)________指針，然后再向所指位置寫(xiě)入新元素。

45.向一個(gè)棧頂指針為top的鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行________和top=p操作。

46.在一個(gè)鏈?zhǔn)疥?duì)列中，若隊(duì)頭指針與隊(duì)尾指針的值相同，則表示該隊(duì)列至多有________個(gè)結(jié)點(diǎn)。

47.在一個(gè)鏈?zhǔn)疥?duì)列中，若隊(duì)頭指針與隊(duì)尾指針的值相同，則表示該隊(duì)列至多有________個(gè)結(jié)點(diǎn)。

48.如果一個(gè)對(duì)象部分地包含自己，或自己定義自己，則稱(chēng)這個(gè)對(duì)象是_________的對(duì)象。

49.如果一個(gè)過(guò)程直接或間接地調(diào)用自己，則稱(chēng)這個(gè)過(guò)程是一個(gè)________的過(guò)程。

50.遞歸工作棧起到兩個(gè)作用，其一是將遞歸調(diào)用時(shí)的實(shí)際參數(shù)和返回地址傳遞給下一層遞歸；其二是保存本層的形式參數(shù)和_________。

51.函數(shù)內(nèi)部的局部變量是在進(jìn)入函數(shù)過(guò)程后才分配存儲(chǔ)空間，在函數(shù)過(guò)程執(zhí)行結(jié)束后就________局部變量所占用的存儲(chǔ)空間。

52.迷宮問(wèn)題是一個(gè)回溯控制的問(wèn)題，最好使用__________的方法來(lái)解決。

53.非空廣義表的除第一個(gè)元素外其他元素組成的表稱(chēng)為廣義表的________。

54.廣義表A

（(a,b,c),(d,e,f))的表尾為_(kāi)_______。

55.廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，子表結(jié)點(diǎn)則指示下一層廣義表的________。

56.廣義表的深度定義為廣義表括號(hào)的________。

57.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為_(kāi)_____。

58.一棵樹(shù)的廣義表表示為a(b(c,d(e,f),g(h)),i(j,k(x,y)))，結(jié)點(diǎn)k的所有祖先的結(jié)點(diǎn)數(shù)為_(kāi)_______個(gè)。

59.一棵樹(shù)的廣義表表示為a(b(c,d(e,f),g(h)),i(j,k(x,y)))，結(jié)點(diǎn)f的層數(shù)為_(kāi)________。假定樹(shù)根結(jié)點(diǎn)的層數(shù)為0。

60.假定一棵三叉樹(shù)（即度為3的樹(shù)）的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小高度為_(kāi)_______。假定樹(shù)根結(jié)點(diǎn)的深度為0。

61.在一棵高度為3的四叉樹(shù)中，最多含有________個(gè)結(jié)點(diǎn)，假定樹(shù)根結(jié)點(diǎn)的高度為0。

62.在一棵三叉樹(shù)中，度為3的結(jié)點(diǎn)數(shù)有2個(gè)，度為2的結(jié)點(diǎn)數(shù)有1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，那么度為0的結(jié)點(diǎn)數(shù)有________個(gè)。

63.一棵高度為5的完全二叉樹(shù)中，最多包含有________個(gè)結(jié)點(diǎn)。假定樹(shù)根結(jié)點(diǎn)的高度為0。

64.假定一棵樹(shù)的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則該樹(shù)的高度為_(kāi)_______。假定樹(shù)根結(jié)點(diǎn)的高度為0。

65.在一棵二叉樹(shù)中，假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)數(shù)為_(kāi)_______個(gè)。

66.假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18，則它的最小高度為_(kāi)_______。假定樹(shù)根結(jié)點(diǎn)的高度為0。

67.在一棵高度為h的理想平衡二叉樹(shù)中，最少含有________個(gè)結(jié)點(diǎn)。假定樹(shù)根結(jié)點(diǎn)的高度為0。

68.在一棵高度為h的理想平衡二叉樹(shù)中，最多含有________個(gè)結(jié)點(diǎn)。假定樹(shù)根結(jié)點(diǎn)的高度為0。

69.若將一棵樹(shù)A(B(C,D,E),F(G(H),I))按照左子女-右兄弟表示法轉(zhuǎn)換為二叉樹(shù)，該二叉樹(shù)中度為2的結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)_______個(gè)。

70.將一棵樹(shù)按照左子女-右兄弟表示法轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)，則該二叉樹(shù)中樹(shù)根結(jié)點(diǎn)肯定沒(méi)有________子女。

71.在一個(gè)堆的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i(0≤i≤n-1)，則它的左子女元素的下標(biāo)為_(kāi)_____。

72.在一個(gè)堆的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i(0≤i≤n-1)，則它的右子女元素的下標(biāo)為_(kāi)_______。

73.在一個(gè)最小堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的________。

74.在一個(gè)最大堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的________。

75.以順序搜索方法從長(zhǎng)度為n的順序表或單鏈表中搜索一個(gè)元素的漸進(jìn)時(shí)間復(fù)雜度為_(kāi)_______。

76.對(duì)長(zhǎng)度為n的搜索表進(jìn)行搜索時(shí)，假定搜索第i個(gè)元素的概率為pi,搜索長(zhǎng)度（即在搜索過(guò)程中依次同有關(guān)元素比較的總次數(shù)）為ci，則在搜索成功情況下的平均搜索長(zhǎng)度的計(jì)算公式為_(kāi)_______。

77.假定一個(gè)順序表的長(zhǎng)度為40，并假定順序搜索每個(gè)元素的概率都相同，則在搜索成功情況下的平均搜索長(zhǎng)度為_(kāi)_______。

78.從有序表(12,18,30,43,56,78,82,95)中折半搜索元素56時(shí)，其搜索長(zhǎng)度為_(kāi)_______。

79.假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行折半搜索，則對(duì)應(yīng)的判定樹(shù)中最底下一層的結(jié)點(diǎn)數(shù)為_(kāi)_____個(gè)。

80.從一棵二叉搜索樹(shù)中搜索一個(gè)元素時(shí)，若給定值大于根結(jié)點(diǎn)的值，則需要向________繼續(xù)搜索。

81.向一棵二叉搜索樹(shù)中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的________上。

82.根據(jù)n個(gè)元素建立一棵二叉搜索樹(shù)的漸進(jìn)時(shí)間復(fù)雜度大致為_(kāi)____________。

83.在一棵AVL樹(shù)中，每個(gè)結(jié)點(diǎn)的左子樹(shù)高度與右子樹(shù)高度之差的絕對(duì)值不超過(guò)________。

84.根據(jù)一組記錄(56,42,50,64,48)依次插入結(jié)點(diǎn)生成一棵AVL樹(shù)時(shí)，當(dāng)插入到值為_(kāi)______的結(jié)點(diǎn)時(shí)需要進(jìn)行旋轉(zhuǎn)調(diào)整。

85.根據(jù)一組記錄(56,74,63,64,48)依次插入結(jié)點(diǎn)生成一棵AVL樹(shù)時(shí)，當(dāng)插入到值為63的結(jié)點(diǎn)時(shí)需要進(jìn)行________________調(diào)整。

86.根據(jù)一組記錄(56,42,38,64,48)依次插入結(jié)點(diǎn)生成一棵AVL樹(shù)時(shí)，當(dāng)插入到值為38的結(jié)點(diǎn)時(shí)需要進(jìn)行____________調(diào)整。

87.根據(jù)一組記錄(56,42,73,50,64,48,22)依次插入結(jié)點(diǎn)生成一棵AVL樹(shù)時(shí)，當(dāng)插入到值為_(kāi)______的結(jié)點(diǎn)時(shí)才出現(xiàn)不平衡，需要進(jìn)行旋轉(zhuǎn)調(diào)整。

88.在一棵具有n個(gè)結(jié)點(diǎn)的AVL樹(shù)上進(jìn)行插入或刪除元素的漸進(jìn)時(shí)間復(fù)雜度大致為_(kāi)________。

若3個(gè)頂點(diǎn)的圖G的鄰接矩陣為，則圖G一定是________向圖。有

89.n

(n﹥0)

個(gè)頂點(diǎn)的連通無(wú)向圖各頂點(diǎn)的度之和最少為_(kāi)_______。

90.用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間與圖中的________數(shù)有關(guān)。

91.設(shè)圖G

=

(V,E)，V

=

{V0,V1,V2,V3},E

=

{(V0,V1),(V0,V2),(V0,V3),(V1,V3)}，則從頂點(diǎn)V0開(kāi)始的圖G的不同深度優(yōu)先序列有________種。

92.設(shè)圖G

=

(V,E)，V

=

{1,2,3,4},E

=

{<1,2>,<1,3>,<2,4>,<3,4>}，從頂點(diǎn)1出發(fā)，對(duì)圖G進(jìn)行廣度優(yōu)先搜索的序列有________種。

93.n

(n﹥0)

個(gè)頂點(diǎn)的無(wú)向圖中頂點(diǎn)的度的最大值為_(kāi)_______。

94.在重連通圖中每個(gè)頂點(diǎn)的度至少為_(kāi)_______。

95.n個(gè)頂點(diǎn)的連通無(wú)向圖的生成樹(shù)含有________條邊。

96.11個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)N有10條邊，其中權(quán)值為1,2,3,4,5的邊各2條，則網(wǎng)絡(luò)N的最小生成樹(shù)各邊的權(quán)值之和為_(kāi)________。

97.在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)的最小生成樹(shù)時(shí)，只有當(dāng)一條候選邊的兩個(gè)端點(diǎn)不在同一個(gè)________上，才會(huì)被加入到生成樹(shù)中。

98.一般來(lái)說(shuō),深度優(yōu)先生成樹(shù)的高度比廣度優(yōu)先生成樹(shù)的高度要________。

99.求解帶權(quán)連通圖最小生成樹(shù)的Prim算法使用圖的________作為存儲(chǔ)結(jié)構(gòu)。

100.設(shè)圖的頂點(diǎn)數(shù)為n，則求解最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為_(kāi)_______。

101.第i

(i

=

1,2,…,n-1)

趟從參加排序的序列中取出第i個(gè)元素，把它插入到由第0個(gè)至第i-1個(gè)元素組成的有序表中適當(dāng)?shù)奈恢?，此種排序方法叫做__________排序。

102.第i

(i=0,1,...,n-2)

趟從參加排序的序列中第i個(gè)至第n-1個(gè)元素中挑選出一個(gè)最小元素，把它交換到第i個(gè)位置，此種排序方法叫做_________排序。

103.每次直接或通過(guò)基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列就交換它們的位置，這種排序方法叫做__________排序。

104.每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表，這種排序方法叫做_________排序。

105.在直接選擇排序中，記錄比較次數(shù)的時(shí)間復(fù)雜度為_(kāi)_______。

106.在直接選擇排序中，記錄移動(dòng)次數(shù)的時(shí)間復(fù)雜度為_(kāi)_________。

107.在堆排序中，對(duì)n個(gè)記錄建立初始堆需要調(diào)用__________次調(diào)整算法。

108.在堆排序中，如果n個(gè)對(duì)象的初始堆已經(jīng)建好，那么到排序結(jié)束，還需要從堆頂結(jié)點(diǎn)出發(fā)調(diào)用_________次調(diào)整算法。

109.在堆排序中，對(duì)任意一個(gè)分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間復(fù)雜度為_(kāi)___________。

110.對(duì)n個(gè)數(shù)據(jù)對(duì)象進(jìn)行堆排序，總的時(shí)間復(fù)雜度為_(kāi)_____________。

111.給定一組數(shù)據(jù)對(duì)象的關(guān)鍵碼為{46,79,56,38,40,84}，則利用堆排序方法建立的初始堆（最大堆）為_(kāi)______________。

112.快速排序在平均情況下的時(shí)間復(fù)雜度為_(kāi)__________。

113.快速排序在最壞情況下的時(shí)間復(fù)雜度為_(kāi)___________。

114.快速排序在平均情況下的空間復(fù)雜度為_(kāi)___________。

115.快速排序在最壞情況下的空間復(fù)雜度為_(kāi)___________。

116.給定一組數(shù)據(jù)對(duì)象的關(guān)鍵碼為{46，79，56，38，40，84}，對(duì)其進(jìn)行一趟快速排序處理，得到的右子表中有________個(gè)對(duì)象。

117.在對(duì)n個(gè)數(shù)據(jù)對(duì)象的二路歸并排序中，每趟歸并的時(shí)間復(fù)雜度為_(kāi)___________。

118.在對(duì)n個(gè)數(shù)據(jù)對(duì)象進(jìn)行的二路歸并排序中，整個(gè)歸并過(guò)程的時(shí)間復(fù)雜度為_(kāi)__________。

119.在索引表中，每個(gè)索引項(xiàng)至少包含有__________域和地址域這兩項(xiàng)。

120.假定一個(gè)線(xiàn)性表為

{12,23,74,55,63,40,82,36}，若按key%3條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則包含74的子表長(zhǎng)度為_(kāi)_______。

121.假定一個(gè)線(xiàn)性表為

(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一個(gè)字母進(jìn)行劃分，使得同一個(gè)字母被劃分在一個(gè)子表中，則得到的以a為第一個(gè)字母的子表長(zhǎng)度為_(kāi)_______。

122.在索引表中，若一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)對(duì)象表中的一個(gè)表項(xiàng)，則稱(chēng)此索引為稠密索引，若對(duì)應(yīng)數(shù)據(jù)對(duì)象表中的若干表項(xiàng)，則稱(chēng)此索引為_(kāi)_______索引。

123.假定對(duì)長(zhǎng)度n

=

100的線(xiàn)性表進(jìn)行索引順序搜索，并假定每個(gè)子表的長(zhǎng)度均為，則進(jìn)行索引順序搜索的時(shí)間復(fù)雜度為_(kāi)_______。

124.假定對(duì)長(zhǎng)度n=100的線(xiàn)性表進(jìn)行索引順序搜索，并假定每個(gè)子表的長(zhǎng)度均為，則進(jìn)行索引順序搜索的平均搜索長(zhǎng)度為_(kāi)_______。

125.若對(duì)長(zhǎng)度n=10000的線(xiàn)性表進(jìn)行二級(jí)索引存儲(chǔ)，每級(jí)索引表中的索引項(xiàng)是下一級(jí)20個(gè)表項(xiàng)的索引，則一級(jí)索引表的長(zhǎng)度為_(kāi)_______。

126.若對(duì)長(zhǎng)度n=10000的線(xiàn)性表進(jìn)行二級(jí)索引存儲(chǔ)，每級(jí)索引表中的索引項(xiàng)是下一級(jí)20個(gè)表項(xiàng)的索引，則二級(jí)索引表的長(zhǎng)度為_(kāi)_______。

127.假定要對(duì)長(zhǎng)度n=100的線(xiàn)性表進(jìn)行散列存儲(chǔ)，并采用開(kāi)散列法處理沖突，則對(duì)于長(zhǎng)度m

=

20的散列表，每個(gè)散列地址的同義詞子表（單鏈表）的長(zhǎng)度平均為_(kāi)_______。

128.在線(xiàn)性表的散列存儲(chǔ)中，裝載因子

a

又稱(chēng)為裝載系數(shù)，若用m表示散列表的長(zhǎng)度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則

a

等于________。

129.對(duì)于包含n個(gè)關(guān)鍵碼的m階B樹(shù)，其最小高度為_(kāi)___________。

130.已知一棵3階B樹(shù)中含有50個(gè)關(guān)鍵碼，則該樹(shù)的最小高度為_(kāi)_______。

131.已知一棵3階B樹(shù)中含有50個(gè)關(guān)鍵碼，則該樹(shù)的最大高度為_(kāi)_______。

132.在一棵m階B樹(shù)上，每個(gè)非根結(jié)點(diǎn)的關(guān)鍵碼數(shù)最少為_(kāi)_________個(gè)。

133.在一棵m階B樹(shù)上，每個(gè)非根結(jié)點(diǎn)的子樹(shù)最少為_(kāi)_______棵。

134.在一棵m階B樹(shù)上，每個(gè)非根結(jié)點(diǎn)的關(guān)鍵碼數(shù)最多為_(kāi)_______個(gè)。

135.在對(duì)m階B樹(shù)插入元素的過(guò)程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)關(guān)鍵碼后，若該結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)等于________個(gè)，則必須把它分裂為2個(gè)結(jié)點(diǎn)。

136.在從m階B樹(shù)刪除關(guān)鍵碼的過(guò)程中，當(dāng)從一個(gè)結(jié)點(diǎn)中刪除掉一個(gè)關(guān)鍵碼后，所含關(guān)鍵碼個(gè)數(shù)等于ém/2ù-2個(gè)，并且它的左、右兄弟結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)均等于________，則必須進(jìn)行結(jié)點(diǎn)合并。

判斷題

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

2.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶(hù)根據(jù)應(yīng)用需要建立的。

3.算法和程序原則上沒(méi)有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)二者是通用的。

4.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。

5.算法和程序都應(yīng)具有下面一些特征：有輸入，有輸出，確定性，有窮性，有效性。

6.只有用面向?qū)ο蟮挠?jì)算機(jī)語(yǔ)言才能描述數(shù)據(jù)結(jié)構(gòu)算法。

7.如果采用如下方式定義一維字符數(shù)組：

const

int

maxSize

=

30;

char

a[maxSize];

則這種數(shù)組在程序執(zhí)行過(guò)程中不能擴(kuò)充。

8.如果采用如下方法定義一維字符數(shù)組：

int

maxSize

=

30;

char

*

a

=

new

char[maxSize];

則這種數(shù)組在程序執(zhí)行過(guò)程中不能擴(kuò)充。

9.數(shù)組是一種靜態(tài)的存儲(chǔ)空間分配，就是說(shuō)，在程序設(shè)計(jì)時(shí)必須預(yù)先定義數(shù)組的數(shù)據(jù)類(lèi)型和存儲(chǔ)空間大小，由編譯程序在編譯時(shí)進(jìn)行分配。

10.多維數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線(xiàn)性的也不是樹(shù)形的。

11.在順序表中，邏輯上相鄰的元素在物理位置上不一定相鄰。

12.順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機(jī)（或直接）訪(fǎng)問(wèn)。

13.插入與刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，因此這兩種操作在數(shù)組中也經(jīng)常被使用。

14.使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲(chǔ)空間。

15.用字符數(shù)組存儲(chǔ)長(zhǎng)度為n的字符串，數(shù)組長(zhǎng)度至少為n+1。

16.線(xiàn)性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)，其存儲(chǔ)結(jié)點(diǎn)的地址可連續(xù)也可不連續(xù)。

17.線(xiàn)性表若采用鏈?zhǔn)酱鎯?chǔ)表示,在刪除時(shí)不需要移動(dòng)元素。

18.在線(xiàn)性鏈表中刪除中間的結(jié)點(diǎn)時(shí)，只需將被刪結(jié)點(diǎn)釋放。

19.在對(duì)雙向循環(huán)鏈表做刪除一個(gè)結(jié)點(diǎn)操作時(shí)，應(yīng)先將被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)鏈接好再執(zhí)行刪除結(jié)點(diǎn)操作。

20.每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素,這種隊(duì)列就是優(yōu)先級(jí)隊(duì)列。

21.鏈?zhǔn)綏Ｅc順序棧相比,一個(gè)明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿(mǎn)的情況。

22.在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中,隊(duì)頭指針指向隊(duì)頭元素的后一個(gè)位置。

23.棧和隊(duì)列都是順序存取的線(xiàn)性表,但它們對(duì)存取位置的限制不同。

24.在使用后綴表示實(shí)現(xiàn)計(jì)算器類(lèi)時(shí)用到一個(gè)棧的實(shí)例,它的作用是暫存運(yùn)算器對(duì)象。

25.在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針。

26.若讓元素1,2,3依次進(jìn)棧，則出棧次序1,3,2是不可能出現(xiàn)的情況。

27.在用單鏈表表示的鏈?zhǔn)疥?duì)列Q中，隊(duì)頭指針為Q->front，隊(duì)尾指針為Q->rear，則隊(duì)空條件為Q->front

==

Q->rear。

28.遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來(lái)實(shí)現(xiàn)對(duì)它的操作。

29.遞歸的算法簡(jiǎn)單、易懂、容易編寫(xiě)，而且執(zhí)行效率也高。

30.遞歸調(diào)用算法與相同功能的非遞歸算法相比，主要問(wèn)題在于重復(fù)計(jì)算太多，而且調(diào)用本身需要分配額外的空間和傳遞數(shù)據(jù)和控制，所以時(shí)間與空間開(kāi)銷(xiāo)通常都比較大。

31.遞歸方法和遞推方法本質(zhì)上是一回事，例如求n!

時(shí)既可用遞推的方法，也可用遞歸的方法。

32.用非遞歸方法實(shí)現(xiàn)遞歸算法時(shí)一定要使用遞歸工作棧。

33.將f

=

+

1/2

+

1/3+

…

+

1/n轉(zhuǎn)化為遞歸函數(shù)時(shí)，遞歸部分為f

(n)

=

f

(n-1)

+

1/n，遞歸結(jié)束條件為f

(1)

=

1。

34.一個(gè)廣義表的表頭總是一個(gè)廣義表。

35.一個(gè)廣義表的表尾總是一個(gè)表。

36.一個(gè)廣義表

（(a),（(b),c),（（(d))))的長(zhǎng)度為3，深度為4。

37.一個(gè)廣義表

（(a),（(b),c),（（(d))))的表尾是

（(b),c),（（(d)))。

38.當(dāng)向一個(gè)最小堆插入一個(gè)具有最小值的元素時(shí)，該元素需要逐層向上調(diào)整，直到被調(diào)整到堆頂位置為止。

39.當(dāng)從一個(gè)最小堆中刪除一個(gè)元素時(shí)，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。

40.二叉樹(shù)是一棵無(wú)序樹(shù)。

41.在一棵二叉樹(shù)中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，對(duì)它分別進(jìn)行前序遍歷和后序遍歷，則具有相同的結(jié)果。

b42.在一棵二叉樹(shù)中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，對(duì)它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的結(jié)果。

43.在一棵二叉樹(shù)中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，對(duì)它分別進(jìn)行前序遍歷和中根遍歷，則具有相同的結(jié)果。

44.在一棵二叉樹(shù)中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，對(duì)它分別進(jìn)行前序遍歷和按層遍歷，則具有相同的結(jié)果。

45.在樹(shù)的存儲(chǔ)中，若使每個(gè)結(jié)點(diǎn)帶有指向雙親結(jié)點(diǎn)的指針，這為在算法中尋找雙親結(jié)點(diǎn)帶來(lái)方便。

46.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)，其高度為h的二叉樹(shù)，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度為O(n)。

47.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)，其高度為h的任何二叉樹(shù)，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度均為O(h)。

48.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的任何二叉樹(shù)，進(jìn)行前序、中序或后序的任一種次序遍歷的空間復(fù)雜度為O(log2n)。

49.在一棵具有n個(gè)結(jié)點(diǎn)的線(xiàn)索二叉樹(shù)中，每個(gè)結(jié)點(diǎn)的指針域可能指向子女結(jié)點(diǎn)，也可能作為線(xiàn)索，使之指向某一種遍歷次序的前驅(qū)或后繼結(jié)點(diǎn)，所有結(jié)點(diǎn)中作為線(xiàn)索使用的指針域共有n個(gè)。

50.線(xiàn)索二叉樹(shù)中的每個(gè)結(jié)點(diǎn)通常包含有5個(gè)數(shù)據(jù)成員。

51.對(duì)具有n個(gè)結(jié)點(diǎn)的堆進(jìn)行插入一個(gè)元素運(yùn)算的時(shí)間復(fù)雜度為O(n)。

52.在順序表中進(jìn)行順序搜索時(shí)，若各元素的搜索概率不等，則各元素應(yīng)按照搜索概率的降序排列存放，則可得到最小的平均搜索長(zhǎng)度。

53.進(jìn)行折半搜索的表必須是順序存儲(chǔ)的有序表。

54.能夠在鏈接存儲(chǔ)的有序表上進(jìn)行折半搜索，其時(shí)間復(fù)雜度與在順序存儲(chǔ)的有序表上相同。

55.假定有兩個(gè)用單鏈有序表表示的集合，則這兩個(gè)集合的交運(yùn)算可得到一個(gè)新的集合單鏈表，其長(zhǎng)度小于等于參加運(yùn)算的任意一個(gè)集合單鏈表的長(zhǎng)度。

56.假定有兩個(gè)用單鏈有序表表示的集合，則這兩個(gè)集合的差運(yùn)算可得到一個(gè)新的集合單鏈表，其長(zhǎng)度小于參加運(yùn)算的任意一個(gè)集合單鏈表的長(zhǎng)度。

57.折半搜索所對(duì)應(yīng)的判定樹(shù)，既是一棵二叉搜索樹(shù)，又是一棵理想平衡二叉樹(shù)。

58.對(duì)于同一組關(guān)鍵碼互不相同的記錄，若生成二叉搜索樹(shù)時(shí)插入記錄的次序不同則得到不同形態(tài)的二叉搜索樹(shù)。

59.對(duì)于同一組記錄，生成二叉搜索樹(shù)的形態(tài)與插入記錄的次序無(wú)關(guān)。

60.對(duì)于兩棵具有相同記錄集合而具有不同形態(tài)的二叉搜索樹(shù)，按中序遍歷得到的結(jié)點(diǎn)序列是相同的。

61.在二叉搜索樹(shù)中，若各結(jié)點(diǎn)的搜索概率不等，使得搜索概率越大的結(jié)點(diǎn)離樹(shù)根越近，則得到的是最優(yōu)二叉搜索樹(shù)。

62.在二叉搜索樹(shù)中，若各結(jié)點(diǎn)的搜索概率不等，使得搜索概率越小的結(jié)點(diǎn)離樹(shù)根越近，則得到的是最優(yōu)二叉搜索樹(shù)。

63.用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中的頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。

64.鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用。

65.鄰接矩陣適用于稠密圖（邊數(shù)接近于頂點(diǎn)數(shù)的平方），鄰接表適用于稀疏圖（邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù)的平方）。

66.存儲(chǔ)無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，因此可以只存儲(chǔ)鄰接矩陣的下（上）三角部分。

67.強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖。

68.對(duì)任何用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（AOV網(wǎng)）進(jìn)行拓?fù)渑判虻慕Y(jié)果都是唯一的。

69.有回路的有向圖不能完成拓?fù)渑判颉?/p>

70.在AOE網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。

71.用邊表示活動(dòng)的網(wǎng)絡(luò)（AOE網(wǎng)）的關(guān)鍵路徑是指從源點(diǎn)到終點(diǎn)的路徑長(zhǎng)度最長(zhǎng)的路徑。

72.對(duì)于AOE網(wǎng)絡(luò)，加速任一關(guān)鍵活動(dòng)就能使整個(gè)工程提前完成。

73.對(duì)于AOE網(wǎng)絡(luò)，任一關(guān)鍵活動(dòng)延遲將導(dǎo)致整個(gè)工程延遲完成。

74.在AOE網(wǎng)絡(luò)中，可能同時(shí)存在幾條關(guān)鍵路徑，稱(chēng)所有關(guān)鍵路徑都需通過(guò)的有向邊為橋。如果加速這樣的橋上的關(guān)鍵活動(dòng)就能使整個(gè)工程提前完成。

75.對(duì)一個(gè)連通圖進(jìn)行一次深度優(yōu)先搜索可以遍訪(fǎng)圖中的所有頂點(diǎn)。

76.圖中各個(gè)頂點(diǎn)的編號(hào)是人為的，不是它本身固有的，因此可以根據(jù)需要進(jìn)行改變。

77.如果無(wú)向圖中每個(gè)頂點(diǎn)的度都大于等于2，則該圖中必有回路。

78.如果有向圖中各個(gè)頂點(diǎn)的度都大于2，則該圖中必有回路。

79.圖的深度優(yōu)先搜索是一種典型的回溯搜索的例子，可以通過(guò)遞歸算法求解。

80.圖的廣度優(yōu)先搜索算法通常采用非遞歸算法求解。

81.對(duì)一個(gè)有向圖進(jìn)行拓?fù)渑判颍欢梢詫D的所有頂點(diǎn)按其關(guān)鍵碼大小排列到一個(gè)拓?fù)溆行虻男蛄兄小?/p>

82.直接選擇排序是一種穩(wěn)定的排序方法。

83.若將一批雜亂無(wú)章的數(shù)據(jù)按堆結(jié)構(gòu)組織起來(lái),則堆中數(shù)據(jù)必然按從小到大的順序線(xiàn)性排列。

84.當(dāng)輸入序列已經(jīng)基本有序時(shí)，起泡排序需要比較關(guān)鍵碼的次數(shù)，比快速排序還要少。

85.在任何情況下，快速排序需要進(jìn)行關(guān)鍵碼比較的次數(shù)都是O(nlog2n)。

86.若用m

個(gè)初始?xì)w并段參加

k

路平衡歸并排序，則歸并趟數(shù)應(yīng)為élog2mù。

87.堆排序是一種穩(wěn)定的排序算法。

88.任何基于排序碼比較的算法，對(duì)n個(gè)數(shù)據(jù)對(duì)象進(jìn)行排序時(shí)，最壞情況下的時(shí)間復(fù)雜度都不會(huì)大于O(nlog2n)。

89.裝載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的裝滿(mǎn)程度。

90.在用散列表存儲(chǔ)關(guān)鍵碼集合時(shí)，可以用雙散列法尋找下一個(gè)空位置。在設(shè)計(jì)再散列函數(shù)時(shí)，要求計(jì)算出的值與表的大小m

互質(zhì)。

91.一棵3

階B樹(shù)是平衡的3

路搜索樹(shù)，反之，一棵平衡的3

路搜索樹(shù)是3

階B樹(shù)。

92.閉散列法通常比開(kāi)散列法時(shí)間效率更高。

93.一棵

m

階

B

樹(shù)中每個(gè)結(jié)點(diǎn)最多有

m-1

個(gè)關(guān)鍵碼，最少有

ém/2ù-1個(gè)關(guān)鍵碼。

94.在索引順序結(jié)構(gòu)上實(shí)施分塊搜索，在等概率情況下，其平均搜索長(zhǎng)度不僅與子表個(gè)數(shù)有關(guān)，而且與每一個(gè)子表中的對(duì)象個(gè)數(shù)有關(guān)。

95.在索引順序結(jié)構(gòu)的搜索中，對(duì)索引表既可以采取順序搜索，也可以采用折半搜索。

96.在散列法中采取開(kāi)散列（鏈地址）法來(lái)解決沖突時(shí),其裝載因子的取值一定在(0,1)之間。

97.AVL樹(shù)（平衡二叉搜索樹(shù)）的所有葉結(jié)點(diǎn)不一定在同一層次上，同樣，平衡m路搜索樹(shù)的葉結(jié)點(diǎn)也不一定在同一層次上。

98.在一棵B樹(shù)中，所有葉結(jié)點(diǎn)都處在同一層上，所有葉結(jié)點(diǎn)中空指針數(shù)等于所有關(guān)鍵碼的總數(shù)加1。

99.向一棵B樹(shù)插入關(guān)鍵碼的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的分裂，則新樹(shù)比原樹(shù)的高度減少1。

100.從一棵B樹(shù)刪除關(guān)鍵碼的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的合并，則新樹(shù)比原樹(shù)的高度增加1。

填空題參考解答

1.信息

2.存儲(chǔ)結(jié)構(gòu)

3.非線(xiàn)性

4.鏈接

5.數(shù)據(jù)結(jié)構(gòu)

6.數(shù)據(jù)封裝

7.有窮性

8.繼承

9.實(shí)例

10.操作（或服務(wù)）11.數(shù)據(jù)類(lèi)型

12.派生（或子）

13.下標(biāo)（或順序號(hào)）14.靜態(tài)

15.動(dòng)態(tài)

16.兩個(gè)

17.LOC(0,0)+(i*n+j)*d

18.相等19.n(n+1)/2

20.(2n-I-1)*I/2+J

21.值

22.數(shù)據(jù)元素

23.16

24.鏈?zhǔn)剑ɑ蜴溄樱?/p>

25.順序

26.刪除

27.指針域

28.分配

29.不一定

30.前驅(qū)

31.表頭指針

32.刪除

33.前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)34.鏈接指針

35.存儲(chǔ)

36.p->llink

37.后出先進(jìn)

38.先進(jìn)先出

39.棧頂指針

40.隊(duì)頭（或隊(duì)首）

41.棧頂指針

42.top==MaxSize-1

43.top

==

0

44.隊(duì)尾45.p->link=top

46.1

47.一

48.遞歸

49.遞歸

50.局部變量

51.釋放

52.遞歸

53.表尾

54.（(d,e,f))

55.表頭結(jié)點(diǎn)

56.重?cái)?shù)

57.n-1

58.2

59.3

60.4

61.85

62.6

63.63

64.3

65.6

66.4

67.2h

68.2h+1-1

69.2

70.右

71.2i+1

72.2i+2

73.最小值

74.最大值

75.O(n)

76.77.20.5

78.3

79.19

80.右子樹(shù)

81.左子樹(shù)

82.O(nlog2n)

83.1

84.50

85.先右后左雙旋轉(zhuǎn)86.右單旋轉(zhuǎn)

87.64

88.O(log2n)

89.2(n-1)

90.頂點(diǎn)

91.4

92.2

93.n-1

94.2

95.n-1

96.30

97.連通分量

98.高

99.鄰接矩陣

100.O(n2)

101.直接插入

102.直接選擇

103.交換

104.二路歸并

105.O(n2)106.O(n)

107.n/2

108.n-1

109.O(log2n)

110.O(nlog2n)

111.84，79，56，38，40，46

112.O(nlog2n)

113.O(n2)

114.O(log2n)

115.O(n)

116.3

117.O(n)

118.O(nlog2n)

119.關(guān)鍵碼

120.2

121.3

122.稀疏

123.O()124.11

125.500

126.25

127.5

128.n/m

129.élogm(n+1)ù

130.4

131.5

132.ém/2ù-1

133.ém/2ù

134.m-1

135.m

136.ém/2ù-1

判斷題參考解答

1.錯(cuò)2.對(duì)3.錯(cuò)4.對(duì)5.錯(cuò)6.錯(cuò)7.對(duì)8.錯(cuò)9.錯(cuò)10.對(duì)

11.錯(cuò)12.對(duì)13.錯(cuò)14.對(duì)15.對(duì)16.對(duì)17.對(duì)18.錯(cuò)19.對(duì)

20.對(duì)21.對(duì)22.錯(cuò)23.對(duì)24.對(duì)25.對(duì)26.錯(cuò)27.錯(cuò)28.對(duì)29.錯(cuò)

30.對(duì)31.錯(cuò)32.錯(cuò)33.對(duì)34.錯(cuò)35.對(duì)36.對(duì)37.錯(cuò)38.對(duì)39.對(duì)

40.錯(cuò)41.錯(cuò)42.對(duì)43.錯(cuò)44.對(duì)45.對(duì)46.對(duì)47.錯(cuò)48.錯(cuò)49.錯(cuò)

50.對(duì)51.錯(cuò)52.對(duì)53.對(duì)54.錯(cuò)55.對(duì)56.錯(cuò)57.對(duì)58.對(duì)59.錯(cuò)

60.對(duì)61.對(duì)62.錯(cuò)63.對(duì)64.錯(cuò)65.對(duì)66.對(duì)67.對(duì)68.錯(cuò)69.對(duì)

70.錯(cuò)71.對(duì)72.錯(cuò)73.對(duì)74.對(duì)75.對(duì)76.對(duì)77.對(duì)78.錯(cuò)79.對(duì)

80.對(duì)81.錯(cuò)82.錯(cuò)83.錯(cuò)84.對(duì)85.錯(cuò)86.錯(cuò)87.錯(cuò)88.錯(cuò)89.對(duì)

90.對(duì)91.錯(cuò)92.錯(cuò)93.錯(cuò)94.對(duì)95.對(duì)96.錯(cuò)97.對(duì)98.對(duì)99.錯(cuò)

100.錯(cuò)