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

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

L一個數(shù)組元素a[i]與()的表示等價。A.*(a+i)B.a+iC.*a+iD.&a+i

2.若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為()參數(shù)。A.指針B.引用C.傳值D.

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

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

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

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

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

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

for(intj=1;j<=i；j++)S;

A.n2B.n2/2C.n(n+l)D.n(n+l)/2

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

intf(unsignedintn){

if(n==OIIn==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)一個作為實(shí)際傳遞的對象占用的存儲空間較大并可能被修改時，應(yīng)最好說明為()，以

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

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

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

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

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

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

的大小即記錄長度為()。

A.所有域長度之和B.最大域所占字節(jié)長度C.任意一個域長度D.sizeof(r)的值

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

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

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

A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)

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

A.O(n)B.O(nlog2n)C.O(n2)D.O⑴

13.某算法僅含程序段1和程序段2,程序段1的執(zhí)行次數(shù)3n2,程序段2的執(zhí)行次數(shù)為0.01n3,

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

A.O(n)B.O(n2)C.O(n3)D,0(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

向前依次后移()個元素。

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

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

個元素。

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

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

為()o

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

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

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

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

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

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

為()。

A.0(1)B.O(M)C.O(log2n)D.0(n)

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

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

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

25.設(shè)有一個nxn的對稱矩陣A,將其下三角部分按行存放在一個一維數(shù)組B中，A[0]⑼存放

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

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

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

26.設(shè)有一個nxn的對稱矩陣A,將其上三角部分按行存放在一個一維數(shù)組B中，A⑼⑼存放

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

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)的位置的運(yùn)算叫做()。

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

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

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

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

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

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

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

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

若在*q與*p之間插入結(jié)點(diǎn)*s,則應(yīng)執(zhí)行的操作是()。

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

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

31.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,link)。已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入

結(jié)點(diǎn)*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é)點(diǎn)的結(jié)構(gòu)為(data,link)。若想摘除p->link所指向的結(jié)點(diǎn)，則應(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é)點(diǎn)(由p所指向)滿足的條件是()o

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

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

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

的尾結(jié)點(diǎn)的指針。若想刪除鏈表第一個結(jié)點(diǎn)，則應(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é)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時，在查找成功的情況下，需要平均比較

的結(jié)點(diǎn)數(shù)是()。

A.nB.n/2

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

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

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

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

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

C.O(n2)D.O(nlog2n)

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

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

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

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

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

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

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

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

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

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

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

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

43.棧的插入和刪除操作在（）進(jìn)行。

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依次進(jìn)棧，則出棧次序不可能出現(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+1

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

51.設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為（data,link）,且top是指向棧頂?shù)闹羔槨Ｈ粝朐阪準(zhǔn)綏５臈ｍ敳迦胍?/p>

個由指針s所指的結(jié)點(diǎn)，則應(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;

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

并將被摘除結(jié)點(diǎn)的值保存到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)用（）表達(dá)式計算隊列元素的個數(shù)。

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

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)需要利用一個（）來實(shí)現(xiàn)數(shù)據(jù)的傳遞和控制的轉(zhuǎn)移。

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

58.在系統(tǒng)實(shí)現(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.增強(qiáng)健壯性D.提高可維護(hù)性

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)用（）次X函數(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)),運(yùn)算Head(Head(Tail(A)))的執(zhí)行結(jié)果為

()。

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

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

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),其中的E是(6

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

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

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

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

69.樹中所有結(jié)點(diǎn)的度之和等于所有結(jié)點(diǎn)數(shù)加()。

A.0B.IC.-lD.2

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

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

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

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

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

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

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

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

A.2iB.2i+lC.2i-lD.2n

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

A.2h-IB.2h+1C.2h-lD.2h

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

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

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

號為0o

A.L(n-l)/2jB.Ln/2jC.「n/2]D.Ln/2j-l

77.在一棵完全二叉樹中，若編號為i的結(jié)點(diǎn)存在左子女，則左子女結(jié)點(diǎn)的編號為()o假

定樹根結(jié)點(diǎn)的編號為0。

A2iB2i-1C2i+1D2i+2

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

編號為()。

A.L(i+l)/2jB.L(i-l)/2jC.Li/2JD.Li/2j-l

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

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

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

A1B2C3D4

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

根結(jié)點(diǎn)的高度為0。

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

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

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

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

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

A.nB.n+1C.2*nD.2*n-l

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

()。

A55B29C58D38

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

點(diǎn)個數(shù)為()。

AlB2C3D4

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

A.0(1)B.O(n)C.O(log2n)D.O(nlog2n)

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

()。

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

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

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

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

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

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

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

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

均搜索長度為()。

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

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

為()的值向上取整。

A.Iog2(n+1)B.Iog2nC.n/2D.(n+1)/2

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

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

A.Iog2(n+1)B.Iog2nC.n/2D.(n+1)/2

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

索長度為()除以9。

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

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

()。

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

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

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

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

A.nB.Iog2nC.(h+l)/2D.h+I

97.從具有n個結(jié)點(diǎn)的二叉搜索樹中搜索一個元素時，在等概率情況下進(jìn)行成功搜索的時間復(fù)

雜度大致為()o

A.O(n)B.O(l)C.O(log2n)D.O(n2)

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

A.0(1)B.O(log2n)C.O(n)D.O(nlog2n)

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

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

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

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

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

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

103.設(shè)Gl=(VI,El)和G2=(V2,E2)為兩個圖,如果V1=V2,E1GE2,則稱()。

A.G1是G2的子圖B.G2是G1的子圖

C.G1是G2的連通分量D.G2是G1的連通分量

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

A.入度B.出度C.入度與出度之和D.(入度+出度)/2

105.一個連通圖的生成樹是包含圖中所有頂點(diǎn)的一個()。

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

106.n個頂點(diǎn)的連通圖中至少含有()。

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

107.n個頂點(diǎn)的強(qiáng)連通圖中至少含有()。

A.n-1條有向邊B.n條有向邊C.n(n-l)/2條有向邊D.n(n-l)條有向邊

108.在一個帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的()中。

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

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

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

A.e-1B.eC.2(e-l)D.2e

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

A.n-1B.nC.n(n-l)/2D.n(n-l)

111.一個有n個頂點(diǎn)和n條邊的無向圖一定是()o

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

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

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

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

A.查找一條邊B.求一個頂點(diǎn)的鄰接點(diǎn)

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

114.在一個有向圖的鄰接矩陣表示中，刪除一條邊＜vi,vj＞需要耗費(fèi)的時間是()。

A.0(1)B.0(i)C.0(j)D.O(i+j)

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

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

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

所耗費(fèi)的時間是（）。

A.0（n）B.0（e）C.0（n+e）D.0（n2）

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

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

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

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

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

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

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

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

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

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

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

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

123.在用Kruskal算法求解帶權(quán)連通圖的最小（代價）生成樹時，通常采用一個（）輔助結(jié)

構(gòu)，判斷一條邊的兩個端點(diǎn)是否在同一個連通分量上。

A.位向量B.堆C.并查集D.生成樹頂點(diǎn)集合

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

（）數(shù)。

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

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

間為（）。

A.O（nlog2e）B.O（n+e）C.O（ne）D.O（n2）

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

少。

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

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

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

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

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

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ù)雜度不高于

O（nlog2n）o

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ù)不能超過1.5,則散列表的長度應(yīng)至少為（）。

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

A.400B.526C.624D.676

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

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

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

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

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

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

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

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

點(diǎn)。

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

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

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

（）。

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

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

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

（）。

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è)散列地址空間為k為表項(xiàng)的關(guān)鍵碼，散列函數(shù)采用除留余數(shù)法，即Hash（k）=k%po

為了減少發(fā)生沖突的頻率，一般取p為（）。

A.mB.小于m的最大質(zhì)數(shù)

C.大于m的最小質(zhì)數(shù)D.小于m的最大合數(shù)

145.在采用開散列法解決沖突時，每一個散列地址所鏈接的同義詞子表中各個表項(xiàng)的（）值

相同。

A.關(guān)鍵碼B.非關(guān)鍵碼C.散列函數(shù)D.某個域

146.解決散列法中出現(xiàn)的沖突問題常采用的方法是（）。

A.數(shù)字分析法、除留余數(shù)法、平方取中法

B.數(shù)字分析法、除留余數(shù)法、線性探查法

C.數(shù)字分析法、線性探查法、雙散列法

D.線性探查法、雙散列法、開散列法

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

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

C.同義詞之間或非同義詞之間發(fā)生沖突D.散列表“溢出”

148.采用線性探查法解決沖突時所產(chǎn)生的?系列后繼散列地址（）。

A.必須大于原散列地址B.必須小于原散列地址

C.可以大于或小于原散列地址D.不能超過散列表長度的一半

149.對存儲有n個元素的長度為m的散列表進(jìn)行搜索，平均搜索長度（）。

A.為O(log2n)B.為O（n）

C.與n/m值有關(guān)D.與n/m值無關(guān)

單選題參考解答

1.A2.B3.C4.D5.B6.B7.B8.A

9.D10.D11.A12.C13.C14.C15.C16.A

17.C18.A19.C20.C21.B22.A23.C24.C

25.A26.C27.B28.A29.B30.B31.D32.A

33.C34.D35.D36.B37.C38.C39.B40.B

41.C42.B43.A44.B45.C46.A47.B48.A

49.D50.D51.C52.A53.D54.A55.D56.C

57.D58.C59.A60.A61.D62.B63.C64.C

65.A66.C67.D68.C69.C70.C71.A72.C

73.A74.D75.A76.D77.C78.B79.A80.B

81.B82.B83.D84.A85.C86.C87.D88.C

89.A90.B91.A92.B93.C94.B95.D96.D

97.C98.B99.A100.C101.B102.D103.A104.C

105.C106.A107.B108.A109.D110.C111.D112.C

113.A114.A115.C116.A117.B118.B119.B120.D

121.A122.D123.C124.C125.B126.A127.C128.B

129.D130.C131.C132.C133.C134.D135.A136.C

137.B138.A139.B140.C141.B142.D143.D144.B

145.C146.D147.C148.C149.C

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

填空題

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

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

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

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

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

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

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

8.面向?qū)ο蟮奶卣鲬?yīng)包括對象、類、、消息通信。

9.屬性與服務(wù)相同的對象構(gòu)成類，類中的每個對象稱為該類的______。

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

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

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

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

取的。

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

的大小。

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

組指針。

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

繼)。

17.若設(shè)一個nxn的矩陣A的開始存儲地址L0C(0,0)及元素所占存儲單元數(shù)d已知，按行存儲時

其任意一個矩陣元素a[i][j]的存儲地址為o

18.對稱矩陣的行數(shù)與列數(shù)_______且以主對角線為對稱軸，a”=皿，因此只存儲它的上三角部

分或下三角部分即可。

19.將一個n階對稱矩陣的上三