數據結構(本科)期末綜合練習一(單選題)

單選題

1.一個數組元素]]與(A)的表示等價。

A.*(a+i)B.a+iC.*a+iD.&a+i

2.若需要利用形參直接訪問實參，則應把形參變量說明為(B)參數。

A.指針B.引用C.傳值D.常值

3.下面程序段的時間復雜度為(C)。

for(inti=0;i<m;i++)

for(intj=0;j<n;j++)a[i][j]=i*j;

A.O(m2)B.O(nz)C.O(m*n)D.O(m+n)

4.執行下面程序段時，執行S語句的次數為()。

for(inti=l;i<=n;i++)

for(intj=l;j<=i;j++)S;

A.nsB.m/2C.n(n+l)D.n(n+l)/2

5.下面算法的時間復雜度為()o

intf(unsignedintn){

if(n==O||n==l)return1;

elsereturnn*f(n-1);

A.0(1)B.0(n)C.0(n2)D.0(n!)

6.一種抽象數據類型包括數據和()兩個部份。

A.數據類型B.操作C.數據抽象D.類型說明

7.當一個作為實際傳遞的對象占用的存儲空間較大并可能被修改時，應最好說明為()，

以節省參數值的傳輸時間和存儲參數的空間。

A.基本類型B.引用型C.指針型D.常值引用型

8.當需要進行標準I/O操作時，則應在程敘文件中包含iostream.h頭文件，當需要進行文件

I/O操作時，則應在程敘文件中包含()頭文件。

A.fstream.hB.stdlib.hC.iomanip.hD.string.h

9.一個記錄r理論上占有的存儲空間的大小等于所有域類型長度之和，實際上占有的存儲空

間的大小即記錄長度為()o

A.所有域長度之和B.最大域所占字節長度

C.任意一個域長度D.sizeof(r)的值

10.輸出一個二維數組b|m|[n]中所有元素值的時間復雜度為(

A.O(n)B.O(m+n)C.O(m)D.O(m*n)

11.一個算法的時間復雜度為(3n2+2nlogn+4n-7)/(5n),其數量級形式的復雜度表示為

2

()。

A.O(n)B.O(nlogn)C.O(n?)D.O(logn)2

12.某算法的時間代價為T(n)=100n+10nlogn4；n2+10,其時間復雜度為()?

A.O(n)B.O(nlogn)C.O(m)D.0(1)2

13.某算法僅含程序段1和程序段2,程序段1的執行次數3n%程序段2的執行次數為O.Oln.',

則該算法的時間復雜度為()。

A.O(n)B.O(m)C.O(m)D.0(1)

14.以下說法錯誤的是()。

A.抽象數據類型具有封裝性。

B.抽象數據類型具有信息隱蔽性。

C.使用抽象數據類型的用戶可以自己定義對抽象數據類型中數據的各種操作。

D.抽象數據類型的一個特點是使用與實現分離。

15.在二維數組中，每一個數組元素同時處于()個向量中。

A.0個B.1個C.2個D.n個

16.多維數組實際上是由嵌套的()實現的。

A.一維數組B.多項式C.三元組表D.簡單變量

17.在一個長度為n的順序表中順序搜索一個值為x的元素時，在等概率的情況下，搜索成功

時的數據平均比較次數為()。

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

18.在一個長度為n的順序表中向第i個元素(OWiWn-l)位置插入一個新元素時，需要從后向前挨

次后移()個元素。

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

19.在一個長度為n的順序表中刪除第i個元素(OWi.l)時，需要從前向后挨次前移()

個元素。

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

2

20.在一個長度為n的順序表中刪除一個值為x的元素時，需要比較元素和挪移元素的總次數為

()。

A.(n+l)/2B.n/2C.nD.n+1

21.在一個長度為n的順序表的表尾插入一個新元素的漸進時間復雜度為()。

A.O(n)B.0(1)C.O(m)D.O(logn)2

22.在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為()。

A.O(n)B.O(n/2)C.0(1)D.O(m)

23.在一個長度為n的有序順序表中搜索值為x元素的時間效率最高的算法的漸進時間復雜度

為()=

A.0(1)B.0(C.O(logn)2D.O(n)

24.在二維數組A[8][10]中，每一個數組元素占用3個存儲空間，所有數組元素相繼存

放于一個連續的存儲空間中，則存放該數組至少需要的存儲空間是()。

A.80B.100C.240D.270

25.設有一個nn的對稱矩陣A,將其下三角部份按行存放在一個一維數組B中，A[0]⑼存放

于B[0]中，那末第i行的對角元素存放于8中()處。

A.(i+3)*i/2B.(i+l)*i/2

C.(2n-i+l)*i/2D.(2n-i-l)*i/2

26.設有一個nn的對稱矩陣A,將其上三角部份按行存放在一個一維數組B中，A[0][0]存放

于B|0]中，那末第i行的對角元素A[iHi]存放于8中()處。

A.(i+3)*i/2B.(i+l)*i/2C.(2n-i+l)*i/2D.(2n-i-l)*i/2

27.設有兩個串t和p,求p在t中首次浮現的位置的運算叫做()。

A.求子串B.模式匹配C.串替換D.串聯接

28.不帶頭結點的單鏈表first為空的判定條件是()。

A.first==NULL;B.first->link==NULL;

C.first->link==first;D.first!=NULL;

29.帶頭結點的單鏈表first為空的判定條件是()。

A.first==NULL;B.first->link==NULL;

C.first->link==first;D.first!=NULL;

30.設單鏈表中結點的結構為(data,link)。已知指針q所指結點是指針p所指結點的直接

前驅，若在*q與*p之間插入結點*s,則應執行的操作是()o

A.s->link=p->link;p->link=s;B.q->link=s;s->link=p;

3

C.p->link=s->]ink;s->link=p;D.p->link=s;s->link=q;

31.設單鏈表中結點的結構為(data,link)。已知指針p所指結點不是尾結點，若在*p之后插入

結點*s,則應執行的操作是()。

A.s->link=p;p->link=s;B.p->link=s;s->link=p;

C.s->link=p->link;p=s;D.s->link=p->link;p->link=s;

32.設單鏈表中結點的結構為(data,link)。若想摘除p->link所指向的結點，則應執行的操作

是()°

A.p->link=p->link->link;B.p=p->link;p->link=p->link->link;

C.p->link=p;D.p=p->link->link;

33.非空的循環單鏈表first的尾結點(由p所指向)滿足的條件是()o

A.p->link==NULL;B.p==NULL;

C.p->link==first;D.p==first;

34.設單循環鏈表中結點的結構為(data,link),且rear是指向非空的帶表頭結點的單循環

鏈表的尾結點的指針。若想刪除鏈表第一個結點，則應執行的操作是()。

A.s=rear;rear=rear->link;deletes;

B.rear=rear->link;deleterear;

C.rear=rear->link->link;deleterear;

D.s=rear->link->link;rear->link->link=s->link;deletes;

35.從一個具有n個結點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需要平均比

較的結點數是()o

A.nB.n/2

C.(n-l)/2D.(n+l)/2

36.在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是

()o

A.0(1)B.0(n)C.0(n2)D.O(nlogn)2

37.給定有n個元素的向量，建立一個有序單鏈表的時間復雜度是()。

A.0(1)B.O(n)

C.0(n2)D.0(nk)g,n)

38.單鏈表A長度為m,單鏈表B長度為n,若將B聯接在A的末尾，其時間復雜度應為()。

A.0(1)B.0(m)

C.0(n)D.0(m+n)

39.利用雙向鏈表作線性表的存儲結構的優點是()。

A,便于單向進行插入和刪除的操作B.便于雙向進行插入和刪除的操作

4

C.節省空間D.便于銷毀結構釋放空間

40.帶表頭的雙向循環鏈表的空表滿足（）o

A.first=NULL;B.first->rLink==first

C.first->lLink==NULLD.first->rLink==NULL

41.已知L是一個不帶表頭的單鏈表,在表首插入結點*p的操作是（）。

A.p=L;p->link=L;B.p->link=L;p=L;

C.p->link=L;L=p;D.L=p;p->link=L;

42.已知L是帶表頭的單鏈表,刪除首元結點的語句是（）.

A.L=L->link;B.L->link=L->link->link;

C.L=L;D.L->link=L;

43.棧的插入和刪除操作在（）進行。

A.棧頂B.棧底C.任意位置D.指定位置

44.當利用大小為n的數組順序存儲一個棧時，假定用top==n表示棧空，則向這個棧插入一

個元素時，首先應執行（）語句修改top指針。

A.top++;B.top—;C.top=0;D.top;

45.若讓元素1,2,3挨次進棧，則出棧次序不可能浮現（）種情況。

A.3,2,1B.2,1,3C.3,1,2D.1,3,2

46.在一個順序存儲的循環隊列中，隊頭指針指向隊頭元素的（）位置。

A.前一個B.后一個C.當前D.后面

47.當利用大小為n的數組順序存儲一個隊列時，該隊列的最大長度為（）。

A.n-2B.n-1C.nD.n+l

48.從一個順序存儲的循環隊列中刪除一個元素時，首先需要（）。

A.隊頭指針加一B.隊頭指針減一

C.取出隊頭指針所指的元素D.取出隊尾指針所指的元素

49.假定一個順序存儲的循環隊列的隊頭和隊尾指針分別為front和rear,則判斷隊空的條件

為（）。

A.front+1==rearB.rear+1==front

C.front==0D.front==rear

50.假定一個鏈式隊列的隊頭和隊尾指針分別為front和rear,則判斷隊空的條件為（）。

A.front==rearB.front!=NULL

C.rear!=NULLD.front==NULL

5

51.設鏈式棧中結點的結構為（data,link）,且top是指向棧頂的指針。若想在鏈式棧的棧

頂插入一個由指針s所指的結點，則應執行（）操作。

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

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

52.設鏈式棧中結點的結構為（data,link）,且top是指向棧頂的指針。若想摘除鏈式棧的

棧頂結點，并將被摘除結點的值保存到x中，則應執行（）操作。

A.x=top->data;top=top->link;B.top=top->link;x=top->data;

C.x=top;top=top->link;D.x=top->data;

53.設循環隊列的結構是

typedefstruct{

DataTypedata[MaxSize];

intfront,rear;

}Queue;

若有一個Queue類型的隊列Q,試問判斷隊列滿的條件應為（）。

A.Q.front==Q.rear;B.Q.front-Q.rear==MaxSize;

C.Q.front+Q.rear==MaxSize;D.Q.front==（Q.rear+1）%MaxSize;

54.設循環隊列的結構是

constintMaxSize=100;

typedefintDataType;

typedefstruct{

DataTypedata[MaxSize];

intfront,rear;

}Queue;

若有一個Queue類型的隊列Q,則應用（）表達式計算隊列元素的個數。

A.（Q.rear-Q.front+MaxSize）%MaxSize;B.Q.rear-Q.front+1;

C.Q.rear-Q.front-1;D.Q.rear-Qfront;

55.為增加內存空間的利用率和減少溢出的可能性，由兩個棧共享一塊連續的內存空間時,

應將兩棧的（）分別設在這塊內存空間的兩端。

A.長度B.深度C.棧頂D.棧底

56.遞歸是將一個較復雜的（規模較大的）問題轉化為一個稍為簡單的（規模較小的）與原問

題（）的問題來解決，使之比原問題更挨近可直接求解的條件。

A.相關B.子類型相關C.同類型D.不相關

57.遞歸調用時系統需要利用一個（）來實現數據的傳遞和控制的轉移。

A.隊列B.優先級隊列C.雙端隊列D.棧

6

58.在系統實現遞歸調用時需利用遞歸工作記錄保存()，當遞歸調用程序執行結束時通

過它將控制轉到上層調用程序。

A.調用地址B.遞歸入口C.返回地址D.遞歸出口

59.在遞歸執行過程中，當前執行的遞歸函數過程的遞歸工作記錄一定是遞歸工作棧中的棧頂

記錄，稱之為()記錄。

A.活動B.當前C.日志D.標記

60.將遞歸求解過程改變為非遞歸求解過程的目的是()。

A.提高速度B.改善可讀性C.增強茁壯性D.提高可維護性

61.如果一個遞歸函數過程中惟獨一個遞歸語句，而且它是過程體的最后語句，則這種遞歸屬

于(),它很容易被改寫為非遞歸過程。

A.單向遞歸B.回溯遞歸C.間接遞歸D.尾遞歸

62.設有一個遞歸算法如下

intfact(intn){//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);

)

則計算fact(n)需要函數調用的次數為()次。

A.nB.n+1C.n+2D.n-1

63.設有一個遞歸算法如下

intX(intn){

if(n<=3)return1;

elsereturnX(n-2)+X(n-4)+1;

)

試問計算X(X(5))時需要調用()次*函數。

A.2次B.3次C.4次D.5次

64.設有一個廣義表A(a),其表尾為()。

A.aB.(())C.()D.(a)

65.設有一個廣義表A((x,(a,b)),(x,(a,b),y)),運算Head(Head(Tail(A)))

的執行結果為()。

A.xB.(a,b)C.(x,(a,b))D.y

66.下列廣義表中的線性表是()0

A.E(a,(b,c))B.E(a,E)C.E(a,b)D.E(a,L())

67.對于一組廣義表A(),B(a,b),C(c,(e,f,g)),D(B,A,C),E(B,D),其中的￡是()。

7

A.線性表B.純表C.遞歸表D.再入表

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

A.Tail(Head(A))B.Head(Tail(A))

C.Head(Tail(Head(Tail(A))))D.Head(Head(Tail(Tail(A))))

69.樹中所有結點的度之和等于所有結點數加()。

A.0B.1C.1D.2

70.在一棵樹中，()沒有前驅結點。

A.樹枝結點B.葉子結點C.樹根結點D.空結點

71.在一棵二叉樹的二叉鏈表中，空指針域數等于非空指針域數加()。

A.2B.1C.0D.1

72.在一棵具有n個結點的二叉樹中，所有結點的空子樹個數等于()。

A.nB.n-1C.n+1D.2*n

73.在一棵具有n個結點的二叉樹的第i層上(假定根結點為第0層，i大于等于0而小于等于

樹的高度)，最多具有()個結點。

A.2iB.2i+lC.2ilD.2n

74.在一棵高度為h(假定樹根結點的層號為0)的徹底二叉樹中，所含結點個數不小于(

)。

A.2H-IB.2h*iC.2h-1D.2h

75.一棵具有35個結點的徹底二叉樹的高度為()。假定空樹的高度為-1。

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

76.在一棵具有n個結點的徹底二叉樹中，樹枝結點的最大編號為()。假定樹根結點的

編號為0。

A.(n-1)/2B.n/2C.n/2D.n/2-1

77.在一棵徹底二叉樹中，若編號為i的結點存在左子女，則左子女結點的編號為()。

假定樹根結點的編號為0。

A2iB2i-1C2i+1D2i+2

78.在一棵徹底二叉樹中，假定樹根結點的編號為0,對于編號為i(i>0)的結點，其雙親結點的

編號為()。

A.(i+l)/2B.(i-l)/2C.i/2D.i/2-1

79.在一棵樹的左子女-右兄弟表示法中，一個結點的右子女是該結點的()結點。

8

A.兄弟B.父子C.祖先D.子孫

80.在一棵樹的靜態雙親表示中，每一個存儲結點包含()個域。

A1B2C3D4

81.已知一棵二叉樹的廣義表表示為a(b(c),d(e(,g(h)),f)),則該二叉樹的高度為()。

假定樹根結點的高度為0。

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

82.已知一棵樹的邊集表示為{<A,B>,<A,C>,<B,D>,<C,E>,<C,F>,<C,G>,<F,H>,<F,I>},

則該樹的深度為()o假定樹根結點的高度為0。

A.2B.3C.4D.5

83.利用n個值作為葉結點的權生成的霍夫曼樹中共包含有()個結點。

A.nB.n+lC.2*nD.2*n-l

84.利用3,6,8,12這四個值作為葉子結點的權，生成一棵霍夫曼樹，該樹的帶權路徑長度為

()。

A55B29C58D38

85.一棵樹的廣義表表示為a(b,c(e,f(g)),d),當用左子女-右兄弟鏈表表示時，右指針域非空的

結點個數為()。

A1B2C3D4

86.向具有n個結點的堆中插入一個新元素的時間復雜度為()。

A.0(1)B.O(n)C.O(logn)D.O(nlogn)22

87.若搜索每一個元素的概率相等，則在長度為n的順序表上搜索任一元素的平均搜索長度

為()。

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

88.對長度為10的順序表進行搜索，若搜索前面5個元素的概率相同，均為1/8,搜索后面5

個元素的概率相同，均為3/40,則搜索任一元素的平均搜索長度為()。

A.5.5B.5C.39/8D.19/4

89.對長度為3的順序表進行搜索，若搜索第一個元素的概率為1/2,搜索第二個元素的概率

為1/3,搜索第三個元素的概率為1/6,則搜索任一元素的平均搜索長度為()。

A.5/3B.2C.7/3D.4/3

90.對長度為n的單鏈有序表，若搜索每一個元素的概率相等，則搜索任一元素的搜索成功的平

均搜索長度為()。

A.n/2B.(n+l)/2C.(n-l)/2D.n/4

9

91.對于長度為n的順序存儲的有序表，若采用折半搜索，則對所有元素的搜索長度中最大的

為()的值向上取整。

A.log(n+1)B.lognC.n/2D.(n+l)/222

92.對于長度為n的順序存儲的有序表，若采用折半搜索，則對所有元素的搜索長度中最大的

為()的值的向下取整加1。

A.log(n+1)B.lognC.n/2D.(n+l)/222

93.對于長度為9的順序存儲的有序表，若采用折半搜索，在等概率情況下搜索成功的平均搜

索長度為()除以9。

A.20B.18C.25D.22

94.對于長度為18的順序存儲的有序表，若采用折半搜索，則搜索第15個元素的搜索長度為(

)°

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

95.對具有n個元素的有序表進行折半搜索，則搜索任一元素的時間復雜度為()o

A.O(n)B.O(m)C.0(1)D.O(logn)2

96.在一棵高度為h的具有n個元素的二叉搜索樹中，搜索一個元素的最大搜索長度為(

)。

A.nB.lognC.(h+l)/2D.h+12

97.從具有n個結點的二叉搜索樹中搜索一個元素時，在等概率情況下進行成功搜索的時間復

雜度大致為()。

A.0(n)B.0(1)C.O(logn)D.0(m)2

98.向具有n個結點的二叉搜索樹中插入一個元素的時間復雜度大致為()o

A.0(1)B.O(Iogn)C.O(n)D.O(nlogn)2

99.在一棵AVL樹中，每一個結點的平衡因子的取值范圍是()o

A.-1IB.-22C.12D.01

100.向一棵AVL樹插入元素時，可能引起對最小不平衡子樹的調整過程，此調整分為()

種旋轉類型。

A.2B.3C.4D.5

101.向一棵AVL樹插入元素時，可能引起對最小不平衡子樹的左單或者右單旋轉的調整過程,

此時需要修改相關()個指針域的值。

A.2B.3C.4D,5

10

102.向一棵AVL樹插入元素時，可能引起對最小不平衡子樹的雙向旋轉的調整過程，此時需

要修改相關（）個指針域的值。

A.2B.3C.4D.5

103.設G=,（Y，￡）和6彳（,、產）為兩個圖，如果VV,EE,則稱（）。，i?2

A.q坤GM字圖B:G嵬G的子圖?2

C.d息G的連通分量D.G是G的連通分量I2

21

104.有向圖的一個頂點的度數等于該頂點的（）。

A.入度B.出度C.入度與出度之和D.（入度+出度）/2

105.一個連通圖的生成樹是包含圖中所有頂點的一個（）。

A.極小子圖B.連通子圖C.極小連通子圖D.無環子圖

106.n個頂點的連通圖中至少含有（）。

A.n-1條邊B.n條邊C.n（n-l）/2條邊D.n（n-l）條邊

107.n個頂點的強連通圖中至少含有（）.

A.n-1條有向邊B.n條有向邊C.n（n-l）/2條有向邊D.n（n-l）條有向邊

108.在一個帶權連通圖G中，權值最小的邊一定包含在6的（）中。

A.最小生成樹B.生成樹

C.廣度優先生成樹D.深度優先生成樹

109.對于具有e條邊的無向圖，它的鄰接表中有（）個邊結點。

A.e-1B.eC.2（e-l）D.2e

110.具有n個頂點的有向無環圖最多可包含（）條有向邊。

A.n-1B.nC.n（n-1）/2D.n（n-l）

111.一個有n個頂點和n條邊的無向圖一定是（）。

A.連通的B.不連通的C.無環的D.有環的

112.在n個頂點的有向無環圖的鄰接矩陣中至少有（）個零元素。

A.nB.n（n-l）/2C.n（n+1）/2D.n（n-l）

113.對于有向圖，其鄰接矩陣表示比鄰接表表示更易于（）。

A.查找一條邊B.求一個頂點的鄰接點

C.進行圖的深度優先遍歷D.進行圖的廣度優先遍歷

114.在一個有向圖的鄰接矩陣表示中，刪除一條邊＜,匕＞需要耗費的時間是（）。

A.0（1）B.O（i）C.O（j）D.O（i+j）

II

115.與鄰接矩陣相比，鄰接表更適合于存儲（）。

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

116.設一個有n個頂點和e條邊的有向圖采用鄰矩陣表示，要計算某個頂點的出度

所耗費的時間是（）。

A.0（n）B.O（e）C.O（n+e）D.0（m）

117.為了實現圖的廣度優先遍歷，BFS算法使用的一個輔助數據結構是（）。

A.棧B.隊列C.二叉樹D.樹

118.設無向圖的頂點個數為n,則該圖最多有（）條邊。

A.n-1B.n（n-l）/2C.n（n+l）/2D.n（n-l）

119.在一個無向圖中，所有頂點的度數之和等于所有邊數的（）倍。

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

120.若采用鄰接矩陣存儲具有n個頂點的無向圖，則該鄰接矩陣是一個（）。

A.上三角矩陣B.稀疏矩陣C.對角矩陣D.對稱矩陣

121.圖的深度優先搜索類似于樹的（）次序遍歷。

A.先根B.中根C.后根D.層次

122.圖的廣度優先搜索類似于樹的（）次序遍歷。

A.先根B.中根C.后根D.層次

123.在用Kruskal算法求解帶權連通圖的最小（代價）生成樹時，通常采用一個（）

輔助結構，判斷一條邊的兩個端點是否在同一個連通分量上。

A.位向量B.堆C.并查集D.生成樹頂點集合

124.采用Dijkstra算法求解帶權有向圖的最短路徑問題時，要求圖中每條邊所帶的權值必須是（

）數。

A.非零B,非整C.非負D.非正

125.設有向圖有n個頂點和e條邊，采用鄰接表作為其存儲表示，在進行拓撲排序時，總的計

算時間為（）。

A.O（nloge）B.O（n+e）C.0（n0D.O（m）2

126.若待排序對象序列在排序前已基本按排序碼遞增順序羅列，則采用（）方法比較次數

至少。

A.直接插入排序B.快速排序C.歸并排序D.直接選擇排序

12

127.對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣

的排序操作，直到子序列為空或者只剩一個元素為止。這樣的排序方法是（）。

A.直接選擇排序B.直接插入排序C.快速排序D.起泡排序

128.對5個不同的數據元素進行直接插入排序，最多需要進行（）次比較。

A.8B.10C.15D.25

129.下列排序算法中，（）算法是不穩定的。

A.起泡排序B.直接插入排序C,基數排序D.快速排序

130.假設某文件經過內部排序得到100個初始歸并段，那末如果要求利用多路平衡歸并在3趟

內完成排序，則應取的歸并路數至少是（）。

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

131.在基于排序碼比較的排序算法中，（）算法在最壞情況下的時間復雜度不高于

0（nlogn）,

'A.起泡排序B.希爾排序C.堆排序D.快速排序

132.在下列排序算法中，（）算法使用的附加空間與輸入序列的長度及初始羅列無關。

A.錦標賽排序B.快速排序C.基數排序D.歸并排序

133.一個對象序列的排序碼為{46,79,56,38,40,84）,采用快速排序（以位于最左位置

的對象為基準）所得到的第一次劃分結果為（）。

A.{38,46,79,56,40,84}B.{38,79,56,46,40,84）

C.{40,38,46,79,56,84}D.{38,46,56,79,40,84）

134.如果將所有中國人按照生日（不考慮年份，只考慮月、日）來排序，那末使用下列排序

算法中（）算法最快。

A.歸并排序B.希爾排序C.快速排序D.基數排序

135.設有一個含有200個元素的表待散列存儲，用線性探查法解決沖突，按關鍵碼查詢時找

到一個元素的平均探查次數不能超過L5,則散列表的長度應至少為（）。

（注：平均探查次數的計算公式為S={1+1/（1-a）}/2,其中a為裝填因子）

A.400B.526C.6241"D.676

136.5階B樹中，每一個結點最多允許有（）個關鍵碼。

A.2B.3C.4D.5

137.在10階B樹中根結點所包含的關鍵碼個數至少為（）。

A.0B.1C.3D.4

138.在一棵高度為h的B樹中，葉結點處于第（）層。（注：樹根結點為第0層，B樹高

13

度為失敗結點所處層數）。

A.h-1B.hC.h+1D.h+2

139.在一棵高度為h的B樹中，插入一個新關鍵碼時，為搜索插入位置需讀取（）個

結點。

A.h-1B.hC.h+1D.h+2

140.當對一個線性表R[60]進行索引順序搜索（分塊搜索）時，若共分成為了1（）個子表，每一個

子表有6個表項。假定對索引表和數據子表都采用順序搜索，則搜索每一個表項的平均搜索長度為

（）。

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

141.當對一個線性表R[60]進行索引順序搜索（分塊搜索）時，若共分成為了8個子表，每一個

子表有6個表項。假定對索引表和數據子表都采用順序搜索，則搜索每一個表項的平均搜索長度為

（）。

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

142.既希翼較快的搜索又便于線性表動態變化的搜索方法是（）。

A.順序搜索B.折半搜索C.散列搜索D.索引順序搜索

143.散列函數應該有這樣的性質，即函數值應當以（）概率取其值域范圍內的每一個值。

A.最大B.最小C.平均D.同等

144.設散列地址空間為（）m-Lk為表項的關鍵碼，散列函數采用除留余數法，即Hash（k尸k%p。

為了減少發生沖突的頻率，普通取p