數(shù)據(jù)結(jié)構(gòu)(本科)期末綜合練習(xí)一(單選題)

數(shù)據(jù)結(jié)構(gòu)(本科)期末綜合練習(xí)一(單選題)

單選題

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

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

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

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

3.下面程序段的時間復(fù)雜度為(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.執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為()。

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.下面算法的時間復(fù)雜度為()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.一種抽象數(shù)據(jù)類型包括數(shù)據(jù)和()兩個部份。

A.數(shù)據(jù)類型B.操作C.數(shù)據(jù)抽象D.類型說明

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

以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。

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

8.當(dāng)需要進行標(biāo)準(zhǔn)I/O操作時，則應(yīng)在程敘文件中包含iostream.h頭文件，當(dāng)需要進行文件

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

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

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

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

A.所有域長度之和B.最大域所占字節(jié)長度

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

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

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

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

2

()。

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

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

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

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

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

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

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

A.抽象數(shù)據(jù)類型具有封裝性。

B.抽象數(shù)據(jù)類型具有信息隱蔽性。

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

D.抽象數(shù)據(jù)類型的一個特點是使用與實現(xiàn)分離。

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

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

16.多維數(shù)組實際上是由嵌套的()實現(xiàn)的。

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

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

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

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的元素時，需要比較元素和挪移元素的總次數(shù)為

()。

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

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

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

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

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

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

為()=

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

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

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

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

25.設(shè)有一個nn的對稱矩陣A,將其下三角部份按行存放在一個一維數(shù)組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.設(shè)有一個nn的對稱矩陣A,將其上三角部份按行存放在一個一維數(shù)組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.設(shè)有兩個串t和p,求p在t中首次浮現(xiàn)的位置的運算叫做()。

A.求子串B.模式匹配C.串替換D.串聯(lián)接

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

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

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

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

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

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

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

前驅(qū)，若在*q與*p之間插入結(jié)點*s,則應(yīng)執(zhí)行的操作是()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.設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為(data,link)。已知指針p所指結(jié)點不是尾結(jié)點，若在*p之后插入

結(jié)點*s,則應(yīng)執(zhí)行的操作是()。

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.設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為(data,link)。若想摘除p->link所指向的結(jié)點，則應(yīng)執(zhí)行的操作

是()°

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.非空的循環(huán)單鏈表first的尾結(jié)點(由p所指向)滿足的條件是()o

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

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

34.設(shè)單循環(huán)鏈表中結(jié)點的結(jié)構(gòu)為(data,link),且rear是指向非空的帶表頭結(jié)點的單循環(huán)

鏈表的尾結(jié)點的指針。若想刪除鏈表第一個結(jié)點，則應(yīng)執(zhí)行的操作是()。

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個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需要平均比

較的結(jié)點數(shù)是()o

A.nB.n/2

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

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

()o

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

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

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

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

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

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

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

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

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

4

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

40.帶表頭的雙向循環(huán)鏈表的空表滿足（）o

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

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

41.已知L是一個不帶表頭的單鏈表,在表首插入結(jié)點*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是帶表頭的單鏈表,刪除首元結(jié)點的語句是（）.

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

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

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

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

44.當(dāng)利用大小為n的數(shù)組順序存儲一個棧時，假定用top==n表示?？眨瑒t向這個棧插入一

個元素時，首先應(yīng)執(zhí)行（）語句修改top指針。

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

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

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

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

A.前一個B.后一個C.當(dāng)前D.后面

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

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

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

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

C.取出隊頭指針?biāo)傅脑谼.取出隊尾指針?biāo)傅脑?/p>

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

為（）。

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

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

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

A.front==rearB.front!=NULL

C.rear!=NULLD.front==NULL

5

51.設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點的結(jié)構(gòu)為（data,link）,且top是指向棧頂?shù)闹羔?。若想在鏈?zhǔn)綏５臈?/p>

頂插入一個由指針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->Iink=top;top=top->Iink;

52.設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點的結(jié)構(gòu)為（data,link）,且top是指向棧頂?shù)闹羔槨Ｈ粝胝準(zhǔn)綏５?/p>

棧頂結(jié)點，并將被摘除結(jié)點的值保存到x中，則應(yīng)執(zhí)行（）操作。

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.設(shè)循環(huán)隊列的結(jié)構(gòu)是

typedefstruct{

DataTypedata[MaxSize];

intfront,rear;

}Queue;

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

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.設(shè)循環(huán)隊列的結(jié)構(gòu)是

constintMaxSize=100;

typedefintDataType;

typedefstruct{

DataTypedata[MaxSize];

intfront,rear;

}Queue;

若有一個Queue類型的隊列Q,則應(yīng)用（）表達式計算隊列元素的個數(shù)。

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

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

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

應(yīng)將兩棧的（）分別設(shè)在這塊內(nèi)存空間的兩端。

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

56.遞歸是將一個較復(fù)雜的（規(guī)模較大的）問題轉(zhuǎn)化為一個稍為簡單的（規(guī)模較小的）與原問

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

A.相關(guān)B.子類型相關(guān)C.同類型D.不相關(guān)

57.遞歸調(diào)用時系統(tǒng)需要利用一個（）來實現(xiàn)數(shù)據(jù)的傳遞和控制的轉(zhuǎn)移。

A.隊列B.優(yōu)先級隊列C.雙端隊列D.棧

6

58.在系統(tǒng)實現(xiàn)遞歸調(diào)用時需利用遞歸工作記錄保存()，當(dāng)遞歸調(diào)用程序執(zhí)行結(jié)束時通

過它將控制轉(zhuǎn)到上層調(diào)用程序。

A.調(diào)用地址B.遞歸入口C.返回地址D.遞歸出口

59.在遞歸執(zhí)行過程中，當(dāng)前執(zhí)行的遞歸函數(shù)過程的遞歸工作記錄一定是遞歸工作棧中的棧頂

記錄，稱之為()記錄。

A.活動B.當(dāng)前C.日志D.標(biāo)記

60.將遞歸求解過程改變?yōu)榉沁f歸求解過程的目的是()。

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

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

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

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

62.設(shè)有一個遞歸算法如下

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

if(n<=0)return1;

elsereturnn*fact(n-1);

)

則計算fact(n)需要函數(shù)調(diào)用的次數(shù)為()次。

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

63.設(shè)有一個遞歸算法如下

intX(intn){

if(n<=3)return1;

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

)

試問計算X(X(5))時需要調(diào)用()次*函數(shù)。

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

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

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

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

的執(zhí)行結(jié)果為()。

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.樹中所有結(jié)點的度之和等于所有結(jié)點數(shù)加()。

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

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

A.樹枝結(jié)點B.葉子結(jié)點C.樹根結(jié)點D.空結(jié)點

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

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

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

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

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

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

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

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

)。

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

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

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

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

編號為0。

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

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

假定樹根結(jié)點的編號為0。

A2iB2i-1C2i+1D2i+2

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

編號為()。

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

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

8

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

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

A1B2C3D4

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

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

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

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

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

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

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

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

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

()。

A55B29C58D38

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

結(jié)點個數(shù)為()。

A1B2C3D4

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

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個元素的有序表進行折半搜索，則搜索任一元素的時間復(fù)雜度為()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個結(jié)點的二叉搜索樹中搜索一個元素時，在等概率情況下進行成功搜索的時間復(fù)

雜度大致為()。

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

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

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

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

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

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

種旋轉(zhuǎn)類型。

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

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

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

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

10

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

要修改相關(guān)（）個指針域的值。

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

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

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

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

21

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

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

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

A.極小子圖B.連通子圖C.極小連通子圖D.無環(huán)子圖

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.在一個帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在6的（）中。

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

C.廣度優(yōu)先生成樹D.深度優(yōu)先生成樹

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

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

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

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

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

A.連通的B.不連通的C.無環(huán)的D.有環(huán)的

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

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

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

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

C.進行圖的深度優(yōu)先遍歷D.進行圖的廣度優(yōu)先遍歷

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

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

II

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

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

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

所耗費的時間是（）。

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

117.為了實現(xiàn)圖的廣度優(yōu)先遍歷，BFS算法使用的一個輔助數(shù)據(jù)結(jié)構(gòu)是（）。

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

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

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

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

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

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

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

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

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

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

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

123.在用Kruskal算法求解帶權(quán)連通圖的最?。ù鷥r）生成樹時，通常采用一個（）

輔助結(jié)構(gòu)，判斷一條邊的兩個端點是否在同一個連通分量上。

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

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

）數(shù)。

A.非零B,非整C.非負(fù)D.非正

125.設(shè)有向圖有n個頂點和e條邊，采用鄰接表作為其存儲表示，在進行拓?fù)渑判驎r，總的計

算時間為（）。

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

126.若待排序?qū)ο笮蛄性谂判蚯耙鸦景磁判虼a遞增順序羅列，則采用（）方法比較次數(shù)

至少。

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

12

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

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

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

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

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

129.下列排序算法中，（）算法是不穩(wěn)定的。

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

130.假設(shè)某文件經(jīng)過內(nèi)部排序得到100個初始?xì)w并段，那末如果要求利用多路平衡歸并在3趟

內(nèi)完成排序，則應(yīng)取的歸并路數(shù)至少是（）。

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

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

0（nlogn）,

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

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

A.錦標(biāo)賽排序B.快速排序C.基數(shù)排序D.歸并排序

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

的對象為基準(zhǔn)）所得到的第一次劃分結(jié)果為（）。

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.基數(shù)排序

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

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

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

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

136.5階B樹中，每一個結(jié)點最多允許有（）個關(guān)鍵碼。

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

137.在10階B樹中根結(jié)點所包含的關(guān)鍵碼個數(shù)至少為（）。

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

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

13

度為失敗結(jié)點所處層數(shù)）。

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

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

結(jié)點。

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

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

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

（）。

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

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

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

（）。

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

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

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

143.散列函數(shù)應(yīng)該有這樣的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以（）概率取其值域范圍內(nèi)的每一個值。

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

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

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