數(shù)據(jù)結(jié)構(gòu)導(dǎo)論模擬試題

（一）單項選擇題

1. 在二維數(shù)組中，每個數(shù)組元素同時處于（）個向量中。

A. 0

B. 1

C. 2

D. n

2. 已知單鏈表A長度為m，單鏈表B長度為n，它們分別由表頭指針?biāo)赶?，若將B 整體連接到A的末尾，其時間復(fù)雜度應(yīng)為（）。

A. O(1)

B. O(m)

C. O(n)

D. O(m+n)

3. 假定一個鏈?zhǔn)疥犃械年狀^和隊尾指針分別為front和rear，則判斷隊空的條件為( )。

A. front == rear

B. front != NULL

C. rear != NULL

D. front == NULL

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

A. 3,2,1

B. 2,1,3

C. 3,1,2

D. 1,3,2

5. 圖的廣度優(yōu)先搜索類似于樹的（）遍歷。

A. 先根

B. 中根

C. 后根

D. 層次

6. 下面程序段的時間復(fù)雜度為( )。

for(int i=0; i

for(int j=0; j

A. O(m2)

B. O(n2)

C. O(m*n)

D. O(m+n)

7. 設(shè)有兩個串t和p，求p在t中首次出現(xiàn)的位置的運算叫做（）。

A. 求子串

B. 模式匹配

C. 串替換

D. 串連接

8 利用雙向鏈表作線性表的存儲結(jié)構(gòu)的優(yōu)點是（）。

A. 便于單向進(jìn)行插入和刪除的操作

B. 便于雙向進(jìn)行插入和刪除的操作

C. 節(jié)省空間

D. 便于銷毀結(jié)構(gòu)釋放空間

9. 設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點的結(jié)構(gòu)為（data, link），且top是指向棧頂?shù)闹羔?。若想在鏈?zhǔn)綏５臈ｍ敳迦胍粋€由指針s所指的結(jié)點，則應(yīng)執(zhí)行( )操作。

A. top->link=s;

B.s->link=top->link; top->link=s;

C. s->link=top; top=s;

D. s->link=top; top=top->link;

10. 一棵具有35個結(jié)點的完全二叉樹的高度為( )。假定空樹的高度為-1。

A. 5

B. 6

C. 7

D. 8

11. 一個有n個頂點和n條邊的無向圖一定是( ) 的。

A．連通 B．不連通 C．無回路 D．有回路

12. 在一個長度為n的順序表的任一位置插入一個新元素的時間復(fù)雜度為（）。

A. O(n)

B. O(n/2)

C. O(1)

D. O(n2)

13. 已知廣義表為A((a,b,c),(d,e,f))，從A中取出原子e的運算是（）。

A．Tail(Head(A)) B．Head(Tail(A))

1

02142

C．Head(Tail(Head(Tail(A)))) D．Head(Head(Tail(Tail(A))))

14. 在一棵樹的靜態(tài)雙親表示中，每個存儲結(jié)點包含( )個域。

A 1

B 2

C 3

D 4

15. 有向圖中的一個頂點的度數(shù)等于該頂點的( )。

A．入度 B．出度

C．入度與出度之和 D．(入度+出度)/２

15. 與鄰接矩陣相比，鄰接表更適合于存儲( )。

A．無向圖 B．連通圖 C．稀疏圖 D．稠密圖

17. 較快的數(shù)據(jù)搜索方法是（）搜索方法。

A. 順序

B. 折半

C. 單鏈

D. 散列

18. 在閉散列表中，散列到同一個地址而引起的“堆積”問題是由于（）引起的。

A. 同義詞之間發(fā)生沖突

B. 非同義詞之間發(fā)生沖突

C. 同義詞之間或非同義詞之間發(fā)生沖突

D. 散列表“溢出”

19. 根據(jù)n個元素建立一個有序單鏈表的時間復(fù)雜度為（）。

A. O(1)

B. O(n)

C. O(n2)

D. O(nlog2n)

20. 假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為front和rear，則判斷隊空的條件為( )。

A. front+1==rear

B. rear+1==front

C. front==0

D. front==rear

21. 假定一棵二叉樹的第i層上有3i個結(jié)點，則第i+1層上最多有( )個結(jié)點。

A. 3i

B. 6i

C. 9i

D. 2i

22. 對于具有e條邊的無向圖，它的鄰接表中共有( )個邊結(jié)點。

A．e-1 B．e+1 C．2e D．3e

23. 圖的深度優(yōu)先搜索遍歷類似于樹的（）次序遍歷。

A. 先根

B. 中根

C. 后根

D. 層次

24．棧S最多能容納4個元素?，F(xiàn)有6個元素按A、B、C、D、E、F的順序進(jìn)棧, 問下列哪一個序列是可能的出棧序列?( )

A. E、D、C、B、A、F

B. B、C、E、F、A、D

C. C、B、E、D、A、F

D. A、D、F、E、B、C

25．將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點編號為1，則編號為49的結(jié)點的左孩子的編號為：( )

A. 98

B. 99

C. 50

D. 48

26. 對下列關(guān)鍵字序列用快速排序法進(jìn)行排序時，速度最快的情形是：( )

A. {21、25、5、17、9、23、30}

B. {25、23、30、17、21、5、9}

B. {21、9、17、30、25、23、5}

D. {5、9、17、21、23、25、30}

27．對于只在表的首、尾進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為( )

A. 順序表

B. 用頭指針表示的單循環(huán)鏈表

C. 用尾指針表示的單循環(huán)鏈表

D. 單鏈表

28．假設(shè)以第一個元素為分界元素，對字符序列（Q, H, C, Y, P, A, M, S, R, D, F, X）進(jìn)行快速排序，則第一次劃分的結(jié)果是：( )

A. (A, C, D, F, H, M, P, Q, R, S, X, Y)

B. (A, F, H, C, D, P, M, Q, R, S, Y, X)

C. (F, H, C, D, P, A, M, Q, R, S, Y, X)

D. (P, A, M, F, H, C, D, Q, S, Y, R, X)

29．下面是三個關(guān)于有向圖運算的敘述：( )

2

02142

（1）求有向圖結(jié)點的拓?fù)湫蛄?，其結(jié)果必定是唯一的

（2）求兩個指向結(jié)點間的最短路徑，其結(jié)果必定是唯一的

（3）求AOE網(wǎng)的關(guān)鍵路徑，其結(jié)果必定是唯一的

其中哪個（些）是正確的？

A. 只有（1）

B. （1）和（2）

C. 都正確

D. 都不正確

30．若進(jìn)棧序列為a, b, c，則通過入出棧操作可能得到的a, b, c的不同排列個數(shù)為: ( )

A. 4

B. 5

C. 6

D. 7

31. 以下關(guān)于廣義表的敘述中,正確的是：( )

A. 廣義表是由0個或多個單元素或子表構(gòu)成的有限序列

B. 廣義表至少有一個元素是子表

C. 廣義表不能遞歸定義

D) 廣義表不能為空表

32. 排序時掃描待排序記錄序列，順次比較相鄰的兩個元素的大小，逆序時就交換位置。這是哪種排序方法的基本思想？( )

A. 堆排序

B. 直接插入排序

C. 快速排序

D. 冒泡排序

33．已知一個有向圖的鄰接矩陣表示，要刪除所有從第i個結(jié)點發(fā)出的邊，應(yīng)該：( )

A. 將鄰接矩陣的第i行刪除

B. 將鄰接矩陣的第i行元素全部置為0

C. 將鄰接矩陣的第i列刪除

D. 將鄰接矩陣的第i列元素全部置為0

34．有一個含頭結(jié)點的雙向循環(huán)鏈表，頭指針為head, 則其為空的條件是：( )

A. head->priro==NULL

B. head->next==NULL

C. head->next==head

D. head->next-> priro==NULL

35. 在順序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 )中，用折半法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為：( )

A. 2

B. 3

C. 4

D. 5

36. 以下哪一個不是隊列的基本運算？( )

A. 從隊尾插入一個新元素

B. 從隊列中刪除第i個元素

C. 判斷一個隊列是否為空

D. 讀取隊頭元素的值

37．對包含n個元素的哈希表進(jìn)行查找，平均查找長度為：( )

A. O(log2n)

B. O(n)

C. O(nlog2n) D 不直接依賴于n

38．將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點編號為1，則編號最大的非葉結(jié)點的編號為：( )

A. 48

B. 49

C. 50

D. 51

39．某二叉樹結(jié)點的中序序列為A、B、C、D、E、F、G，后序序列為B、D、C、A、F、G、E，則其左子樹中結(jié)點數(shù)目為：( )

A. 3

B. 2

C. 4

D. 5

40．下面是順序存儲結(jié)構(gòu)的優(yōu)點。

A. 存儲密度大

B. 插入運算方便

C. 查找方便

D. 適合各種邏輯結(jié)構(gòu)的存儲表示

41．下面關(guān)于串的敘述中，是不正確的。

A. 串是字符的有限序列

B. 空串是由空格構(gòu)成的串

C. 模式匹配是串的一種重要運算

D. 串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?/p>

42．的鄰接矩陣是對稱矩陣。

A. 有向圖

B. 無向圖

C. AOV網(wǎng)

D. AOE網(wǎng)

43．用鏈?zhǔn)椒绞酱鎯Φ年犃校谶M(jìn)行刪除運算時，。

A. 僅修改頭指針

B. 僅修改尾指針

C. 頭、尾指針都要修改

D. 頭、尾指針可能都要修改

3

02142

44．二叉樹的先序遍歷和中序遍歷如下，則該二叉樹右子樹的樹根是。

先序序列：EFHIGJK 中序序列：HFIEJKG

A. E

B. F

C. G

D. H

45．下面方法可以判斷出一個有向圖中是否有環(huán)。

A. 深度優(yōu)先遍歷

B. 拓樸排序

C. 求最短路徑

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

46．從未排序序列中依次取出一個元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為排序法。

A. 插入

B. 選擇

C. 冒泡

D. 都不是

47．一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是。

A. edcba

B. decba

C. dceab

D. abcde

48．n個節(jié)點的完全二叉樹，編號為i的節(jié)點是葉子結(jié)點的條件是。

A. i

B. 2*i<=n

C. 2*i+1>n

D. 2*i>n

49．向一個有128個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動個元素。

A. 64.5

B. 64

C. 63

D. 65

50．在一個單鏈表HL中，若要在指針q所指結(jié)點的后面插入一個由指針p所指向的結(jié)點，則執(zhí)行。

A. q->next=p->next; p->next=q;

B. p->next=q->next; q=p;

C. p->next=p->next; q->next=q;

D. p->next=q->next; q->nxet=p;

51．對一個滿二叉樹，m個樹葉，n個結(jié)點，深度為h，則有。

A. n=h+m

B. h+m=2n

C. m=h-1

D. n=2h-1

52．在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是。

A. 選擇排序

B. 冒泡排序

C. 插入排序

D. 希爾排序

53．用鏈?zhǔn)椒绞酱鎯Φ年犃?，在進(jìn)行插入運算時，。

A. 僅修改頭指針

B. 僅修改尾指針

C. 頭、尾指針都要修改

D. 頭、尾指針可能都要修改

54．在一個長度為n的順序存儲的線性表中，向第i個元素（1≤i≤n+1）插入一個新元素時，需要從后向前依次后移個元素。

A. n-i

B. n-i-1

C. n-i+1

D. i

55．一個棧的入棧序列是12345，則棧的不可能的輸出序列是。

A. 23415

B. 54132

C. 23145

D. 15432

56．5個頂點的有向圖最多有條弧。

A. 5

B. 20

C. 4

D. 25

57．假定一個鏈隊的隊首和隊尾指針分別為front和rear，則判斷隊空的條件為。

A. front==rear

B. front!=NULL

C. rear!=NULL

D. front==NULL

58．若某線性表中最常用的操作是提取第i個元素及找第i個元素的前驅(qū)元素，則采用（）存儲方式最省時間。

A.單鏈表

B.雙鏈表

C.單向循環(huán)鏈表

D.順序表

59．將含有100個結(jié)點的完全二叉樹從根開始自上向下，每層從左到右依次編號，且設(shè)根結(jié)點的編號為1，則編號69的結(jié)點的雙親的編號為（）。

A. 34

B. 35

C. 33

D. 無法確定

60. 單循環(huán)鏈表的主要優(yōu)點是（）。

4

02142

A. 不再需要頭指針了

B. 已知某結(jié)點的位置后，很容易找到其前驅(qū)

C. 在進(jìn)行插入、刪除運算時，能更好地保證鏈表不斷開

D. 從表中任一結(jié)點出發(fā)都能掃描到整個鏈表

61. 一個棧的入棧順序是1、2、3、4、5，則此棧不可能的輸出順序為（）。

A. 5、4、3、2、1

B. 4、5、3、2、1

C. 4、3、5、1、2

D. 1、2、3、4、5

62. 串是一種特殊的線性表，其特殊性表現(xiàn)在（）。

A. 可以順序存儲

B.數(shù)據(jù)元素是一個字符

C可以鏈?zhǔn)酱鎯? D.數(shù)據(jù)元素是多個字符

63. n個頂點的無向圖中最多有（）條邊。

A. n(n-1)/2

B. n(n-1)

C. n(n+1)

D. n(n+1)/2

64. 6個頂點的無向圖中，至少有（）條邊才能保證是一個連通圖。

A. 5

B. 6

C. 7

D. 8

65．若某線性表中最常用的操作是刪除第1個元素，則不宜采用（）存儲方式。

A.單鏈表

B.雙鏈表

C.單向循環(huán)鏈表

D.順序表

66．在一棵完全二叉樹的順序存儲方式中，若編號i的結(jié)點有右孩子，則其右孩子的編號為（）。

A. 2i

B. 2i-1

C. 2i+1

D. i/2

67. 按照二叉樹的定義，具有3個結(jié)點的二叉樹有（）種不同形態(tài)。

A. 3

B. 4

C. 5

D. 6

68. 在長為n的順序表中，刪除第i個元素(1≤i≤n+1)需要向前移動（）個元素。

A. n-i

B. n-i+1

C. n-i-1

D. i

69. 一個隊的入隊順序是1、2、3、4、5，則此隊的出隊順序為（）。

A. 5、4、3、2、1

B. 4、5、3、2、1

C. 4、3、5、1、2

D. 1、2、3、4、5

70. 棧是一種特殊的線性表，其特殊性表現(xiàn)在（）。

A. 可以順序存儲

B.只能從端點進(jìn)行插入和刪除

C. 可以鏈?zhǔn)酱鎯?/p>

D. 可以在任何位置進(jìn)行插入和刪除

71. 一棵二叉樹中，第k層上最多有（）個結(jié)點。

A. 2k

B.2k-1

C.2k

D.2k-1

72. 一棵有18個結(jié)點的二叉樹，其高度最小為（）層。

A. 4

B. 5

C. 6

D. 18

73.有向圖中，所有頂點入度和是所有頂點出度和的（）倍。

A. 0.5

B. 1

C. 2

D. 4

（二）填空題

1.數(shù)據(jù)元素之間存在的相互關(guān)系稱為。

2.數(shù)據(jù)結(jié)構(gòu)從邏輯上分為結(jié)構(gòu)和結(jié)構(gòu)。

3.線性表的順序存儲結(jié)構(gòu)稱為。

4.所有插入在表的一端進(jìn)行，而所有刪除在表的另一端進(jìn)行的線性表稱為。

5.深度為h的二叉樹,最少有個結(jié)點。

6.折半查找要求待查表為表。

7.n個記錄按其關(guān)鍵字大小遞增或遞減的次序排列起來的過程稱為。

5

02142

8.存儲數(shù)據(jù)時,不僅要存儲數(shù)據(jù)元素的 ,還要存儲元素之間的相互。

9．將一棵有100個結(jié)點的完全二叉樹按層編號，則編號為49的結(jié)點X，其雙親PARENT（X）的編號為_ ___。

10、一個字符串相等的充要條件是和。

11、在有向圖的鄰接表和逆鄰接表表示中，每個頂點的邊鏈表中分別鏈接著該頂點的所有

和_ 結(jié)點。

11、在一個長度為n 的順序表中向第 i 個元素（0

要向后移動_ 個元素。

12、_ 是只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。

13、設(shè)主串T＝“abxxyxyxxbaa”,模式串P＝“xyxx”則第_ 次匹配成功。

14、在一棵二叉樹中，第5層上的結(jié)點數(shù)最多為_ 。（根的層次為1）

15、假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組中，其中B［0］存儲

矩陣中第1個元素a1,1 ，則B[31] 中存放的元素是_ 。

16、有n個結(jié)點的二叉鏈表中，其中空的指針域為n+1，指向孩子的指針個數(shù)為_ 。

17、二叉樹后序遍歷的順序是ABCDE，則該二叉樹的根結(jié)點是_ 。

18、對于一個具有n 個頂點和e 條邊的無向圖，若采用鄰接表表示，則整個鄰接表中的結(jié)

點總數(shù)是_ 。

19、在單鏈表上難以實現(xiàn)的排序方法有_ 和_ 。

20、_ 查找法的平均查找長度與元素個數(shù)n無關(guān)。

21、在有n 個元素的順序表的任意位置插入一個元素所需移動結(jié)點的平均次數(shù)為

_ 。

22、_ 是插入和刪除元素都在表的同一端進(jìn)行的線性表。

23、廣義表L＝（a,b,c,L）,則其長度為_ 。

24、在樹中，除跟結(jié)點外，其他結(jié)點都有且只有一個_ 結(jié)點。

26、在串s=“structure”中，以t 為首字符的子串有_ 個。

27、廣度優(yōu)先搜索遍歷類似于樹的按_ 遍歷的過程。

28、已知一棵完全二叉樹中共有768個結(jié)點為，則該樹中共有_ 個葉子結(jié)點。

29、在有序表（12,24,36,48,60,72,84）中二分查找關(guān)鍵字72時所需進(jìn)行的關(guān)鍵字比較次

數(shù)為_ 。

30、兩個長度分別m和n（m>n）的排好序的表歸并成一個排好序的表，至少要進(jìn)行_ 次

鍵值比較。通常從四個方面評價算法的質(zhì)量：_________、_________、_________和_________。

31、一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為________。

32、若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指

針。在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。

33、對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點

分別有_______個和________個。

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

向完全圖中，包含有________條邊。

35、36.在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。

36、37.中序遍歷二叉排序樹所得到的序列是___________序列。

38.快速排序的最壞時間復(fù)雜度為___________，平均時間復(fù)雜度為__________。

39.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立

的初始堆為___________________________。

40．?dāng)?shù)據(jù)的物理結(jié)構(gòu)主要包括________和________兩種情況。

6

02142

41.設(shè)一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為__________；若用二叉鏈表作

為該完全二叉樹的存儲結(jié)構(gòu)，則共有___________個空指針域。

42、設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。

43、設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和

等于頂點i的____，第i列上所有元素之和等于頂點i的____。設(shè)哈夫曼樹中共有n個結(jié)點，則該哈夫曼樹中有________個度數(shù)為1的結(jié)點。

44、設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，則e和d的關(guān)系為

_________。

45、__________遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列（填先序、中序或

后序）。

46、設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較

________次就可以斷定數(shù)據(jù)元素X是否在查找表中。

47、不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為

____________。

48、設(shè)有n個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第

i個結(jié)點的雙親結(jié)點編號為________，右孩子結(jié)點的編號為________。

49、設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的

一趟快速排序結(jié)果為__________________。

50、設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖

的一種拓?fù)湫蛄袨開___________________。

51、下列算法實現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請在下劃線處填上正確的語句。

struct record{int key; int others;};

int hashsqsearch(struct record hashtable[ ],int k)

{

int i,j; j=i=k % p;

while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}

if (_______________________ ) return(j); else return(-1);

} j+1，hashtable[j].key==k

52、下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請在下劃線處填上正確的語句。

typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;

bitree *bstsearch(bitree *t, int k)

{

if (t==0 ) return(0);else while (t!=0)

if (t->key==k)_____________; else if (t->key>k) t=t->lchild;

else_____________;

}

return(t)，t=t->rchild

53、設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為________，快速排序的平

均時間復(fù)雜度為_________。

54、設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點X，則刪除結(jié)點X需要執(zhí)行的語句序列為

_________________________________________________________（設(shè)結(jié)點中的兩個指針域

7

02142

分別為llink和rlink）。根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____ 3_______。

55、深度為k的完全二叉樹中最少有____ 2k-1____個結(jié)點。

56、設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，K n)，則用篩選法思想建堆必須從第__ n/2_個元

素開始進(jìn)行篩選。

59、設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有_________個葉子結(jié)點；若采用二叉鏈表作為

存儲結(jié)構(gòu)，則該樹中有_____個空指針域。

60、設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲________個隊

列元素；當(dāng)前實際存儲________________個隊列元素（設(shè)頭指針F指向當(dāng)前隊頭元素的前一個位置，尾指針指向當(dāng)前隊尾元素的位置）。

61、設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_____

個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_____個元素。

62、設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速

排序結(jié)果為______________________________。

63、設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列

建成的初始堆為________________________。

64、設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個數(shù)_________第i列上非0

元素的個數(shù)（填等于，大于或小于）。

65、設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該

二叉樹的序列為_____________。

66、設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上

正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標(biāo)志0。

typedef struct node {int key; struct node *next;} lklist;

void createlkhash(lklist *hashtable[ ])

{

int i,k; lklist *s;

for(i=0;i

for(i=0;i

{

s=(lklist *)malloc(sizeof(lklist)); s->key=a[i];

k=a[i] % p; s->next=hashtable[k];_______________________;

}

}

hashtable[i]=0，hashtable[k]=s

三、應(yīng)用題主要考點

1、二叉樹的遍歷與恢復(fù)（即已知二叉樹對其遍歷、已知遍歷序列恢復(fù)二叉樹）、哈夫曼樹的

構(gòu)造

2、圖的存儲結(jié)構(gòu)（鄰接矩陣、鄰接表）、圖的應(yīng)用（最小生成樹、拓?fù)渑判颍?/p>

3、各種查找方法（二叉排序樹、散列表、平均查找長度）

4、各種排序方法

8

四、算法設(shè)計題主要考點

1、線性表的簡單算法(順序表和單鏈表的基本運算)。

2、二叉樹的簡單應(yīng)用算法(如二叉樹的遍歷、求二叉樹的高度、二叉樹中葉子節(jié)點數(shù)等)。

3、查找算法（順序查找、二分查找）。

4、排序算法（如插入、交換、選擇排序等）。

9