數(shù)據(jù)結(jié)構(gòu)模擬(共五卷)

數(shù)據(jù)結(jié)構(gòu)模擬（一）

一、單項選擇題（100題）

1、二維數(shù)組A行下標(biāo)i的范圍從1到12,列下標(biāo)j的范圍從3到10,采用行序

為主序存儲，每個數(shù)據(jù)元素占用4個存儲單元，該數(shù)組的首地址（即A[l][3]的

地址）為1200,則A[6][5]的地址為（）。

A、1400

B、1404

C、1372

D、1368

2、一個長度為n的順序表中,刪除下標(biāo)為i（OWiWnT）的元素時，需要向前移

動（）個元素。（3.0分）

A、n-i

B、n-i+1

C、n-i-1

D、i

3、“二叉樹為空”意味著二叉樹（）。（3.0分）

A、由一些沒有賦值的空結(jié)點構(gòu)成

B、根結(jié)點沒有子樹

C、不存在

D、沒有結(jié)點

4、在二叉排序樹中，每個結(jié)點的關(guān)鍵字值（）o（5.0分）

A、比左子樹所有結(jié)點的關(guān)鍵字值大，比右子樹所有結(jié)點的關(guān)鍵字值小

B、比左子樹所有結(jié)點的關(guān)鍵字值小，比右子樹所有結(jié)點的關(guān)鍵字值大

C、比左右子樹的所有結(jié)點的關(guān)鍵字值都大

D、與左.右子樹所有結(jié)點的關(guān)鍵字值無必然的大小關(guān)系

5、假定有k個關(guān)鍵字互為同義詞,若用線性探測法把這k個關(guān)鍵字存入哈希表

中，至少要進(jìn)行（）次探測。

A、k-1

B、k

C、k+1

D、k（k+l）/2

6、（3分）線性表適合于順序查找的存儲結(jié)構(gòu)是（C）o

A、索引存儲

B、壓縮存儲

C、順序存儲

D、散列存儲

7、在長度為n的字符串S的第i個位置插入另外一個字符串，i的合法值應(yīng)該

是()

A、i>0

B、iWn

C,lWiWn

D、lWiWn+1

8、在一個具有n個頂點和e條邊的有向圖的鄰接表中，保存頂點單鏈接的表頭

指針向量大小至少為()

A、n

B、2n

C、e

D、2e

9、對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表示，則頂點表向

量的大小和所有鄰接表中的結(jié)點總數(shù)分別是()。

A、都是n

B、都是n+e

C、n和n+e

D、n和2e

10、*給定排序碼值序列為{F,B,J,C,E,A,I,D,C,H},對其按字母的字

典序列的次序進(jìn)行排列，希爾(Shell)排序的第一趟(dl=5)結(jié)果應(yīng)為()。

A、｛B,F,C,J,A,E,D,I,C,H)

B、｛C,B,D,A,E,F,I,C,J,H)

C、｛B,F,C,E,A,I,D,C,H,J)

D、｛A,B,D,C,E,F,I,J,C,H)

11、設(shè)矩陣A是一個對稱矩陣,為了節(jié)省存儲,將其下三角部分按行序存放在一

維數(shù)組B[l,n(n-l)/2]中，對下三角部分中任一元素ai,j(i>=j),在一維數(shù)組B

的下標(biāo)位置k的值是()

A、i(i-l)/2+j-l

B、i(i-l)/2+j

C、i(i+l)/2+j-l

D、i(i+l)/2+j

12、任何一個無向連通網(wǎng)的最小生成樹

A、有一棵或多棵

B、只有1棵

C、一定有多棵

D、可能不存在

13、以下說法正確的是()0

A、在單鏈表中,任何兩個元素的存儲位置之間都有固定的聯(lián)系，因此可以從

頭結(jié)點開始,查找任何一個元素

B、在單鏈表中,要取得某個元素，只要知道該元素的指針即可，因此,單鏈表

是隨機(jī)存取的存儲結(jié)構(gòu)

C、順序存儲方式只能用于存儲線性結(jié)構(gòu)

D、順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高

14、(3分)假設(shè)散列表長m=ll,散列函數(shù)H(key)=key先H表中己有4個結(jié)點：H

(39):。6,H(41):8.H(53):9,H(76):10,占了4個位置，其余位置為

空?，F(xiàn)采用線性探查法處理沖突,存儲關(guān)鍵字85時需要探查的次數(shù)是(C)o

A、2

B、3

C、4

D、5

15、在一個鏈隊中，假設(shè)和分別為隊首和隊尾指針,則刪除一個結(jié)點的運算時

(C)o

A、r=f->next;

B、r=r->next：

C、f=f->next;

D、f=r->next;

16、(4分)順序表中有10個數(shù)據(jù)元素，若第-一個元素的存儲地址是1000,則

最后-一個元素地址是1036,第5個元素的地址是(B)。

A、1010

B、1016

C、1018

D、1019

17、下列敘述中錯誤的是(C)。

A、圖的遍歷是從給定的源點出發(fā)對每一個頂點訪問且僅訪問一次

B、圖的遍歷可以采用深度優(yōu)先遍歷和廣度優(yōu)先遍歷

C、圖的廣度優(yōu)先遍歷只適用于無向圖

D、圖的深度優(yōu)先遍歷是一個遞歸過程

18、對于一個具有n個結(jié)點的單鏈表,在已知的結(jié)點*p后插入一個新結(jié)點的時

間復(fù)雜度和在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度分別為

A、0(1),0(n)

B、0(n),0(n)

C、0(1),0(1)

D、0(n),0(l)

19、已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序

遍歷的結(jié)果為(A)。

A、CBEFDA

B、FEDCBA

C、CBEDFA

D、不定

20、對n個頂點和e條邊的有向圖，以鄰接矩陣存儲，則求圖中某頂點入度的

時間復(fù)雜度為()o

A、O(n)

B、0(e)

C、0(n+e)

D、0(n2)

21、從沒有排序序列中挑選元素,并將其一次插入已排序序列末端的方法，稱

()

A、歸并排序

B、冒泡排序

C、插入排序

D、選擇排序

22、下列各種排序算法中平均時間復(fù)雜度為0(n2)是()。

A、快速排序

B、堆排序

C、歸并排序

D、冒泡排序

23、表示一個有100個頂點，1000條邊的無向圖的鄰接矩陣有()個非零矩

陣元素。

A、100

B、1000

C、9000

D、1000X2

24、判斷順序棧(最多結(jié)點數(shù)為m)為棧滿的條件是

A、top==0

B、top!=m

C、top!=0

D>top==m

25、下列排序方法中，()所需的輔助空間最大。(2.0分)

A、選擇排序

B、希爾排序

C、快速排序

D、歸并排序

26、下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是。

A、B樹

B、AVL樹

C、二叉排序樹

D、哈夫曼樹

27、在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時，通常設(shè)置一個打印機(jī)

數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，打印機(jī)則從該緩沖區(qū)中

取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個()結(jié)構(gòu)

A、棧

B、隊列

C、樹

D,線性表

28、在下列排序方法中不需要對排序碼值進(jìn)行比較就能進(jìn)行排序的是()。

A、基數(shù)排序

B、快速排序

C、直接插入排序

D、堆排序

29、棧在()中應(yīng)用。

A、遞歸調(diào)用

B、子程序調(diào)用

C、表達(dá)式求值

D、A,B,C

30、隊列的特點是O。

A、先進(jìn)先出

B、后進(jìn)先出

C、先進(jìn)后出

D、不進(jìn)不出

31、若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[m],top[i]代表第i個

棧(i=1,2)棧頂，棧1的底在v[0],棧2的底在則棧滿的條件是

()

A、top[2]-top[l]=0

B、top[l]+l=top[2]

C、top[l]+top[2]=m

D、top[l]=top[2]

32、若長度為n的線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，訪問其第i個元素的算法時間

復(fù)雜度為()

A、0(n)

B、0(n'2)

C、0(n-3)

D、0(log2"n)

33、設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜

度為()0

A、0(n)

B,0(n2)

C、0(nlog2n)

D、0(log2n)

34、下面敘述正確的是

A、二叉樹是特殊的樹

B、二叉樹等價于度為2的樹

C、完全二叉樹必為滿二叉樹

D、二叉樹的左右子樹有次序之分

35、設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ敚瑒t刪除棧頂元素的操作序列為

()o

A、top=top+l

B、top=top-l

C、top->next=top

D、top=top->next

36、一個遞歸算法必須包括()。

A、遞歸調(diào)用

B、子程序調(diào)用

C、表達(dá)式求值

D、A,B,C

37、設(shè)無向圖G中頂點數(shù)為n,則圖G至多有()條邊。

A、0

B、n

C、n(n-1)/2

D、n(n-l)

38、分別以下列序列構(gòu)造二叉排序樹，與其他三個序列構(gòu)造結(jié)果不同的是()0

⑸0分)

A、(100,80,90,60,120,110,130)

B、(100,120,110,130,80,60,90)

C、(100,60,80,90,120,110,130

D、(100,80,60,90,120,130,110)

39、若一棵二叉樹具有10個度為2的結(jié)點,5個度為1的結(jié)點，則度為0的結(jié)

點個數(shù)是(B)

A、9

B、11

C、15

D、不確定

40、鏈表適用于()o(5.0分)

A、順序查找

B、二分查找

C、插值查找

D、隨機(jī)

41、經(jīng)過下列棧的運算后EmptyStaCk(s)的值是()。

InitStaCk(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,x);

A、A、

B、B、

C、1

D、0

42、在數(shù)據(jù)結(jié)構(gòu)中，從存儲結(jié)構(gòu)上可以將之分為

A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

B、順序存儲和非順序存儲

C、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

D、線性結(jié)構(gòu)和非線性結(jié)構(gòu)

43、在任何情況下，時間復(fù)雜度均為0(nlgn)的不穩(wěn)定的排序方法是()。

⑵0分)

A、直接插入

B、快速排序

C、堆排序

D,歸并排序

44、判定一個順序棧ST(最多元素為m0)為棧滿的條件是

A、top!=0

B、top==0

C、top!=m0

D>top==m0-l

45、某內(nèi)排序方法的穩(wěn)定性是指(D)。

A、該排序算法不允許有相同的關(guān)鍵字記錄

B、該排序算法允許有相同的關(guān)鍵字記錄

C、平均時間為0(nlogn)的排序方法

D、以上都不對

46、采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為

A、n

B、n/2

C、(n+l)/2

D、(n-l)/2

47、設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字

映射到HASH表中需要做()次線性探測。

A、n2

B、n(n+l)

C、n(n+1)/2

D、n(n-l)/2

48、設(shè)有一個遞歸算法如下：Intfun(intn){if(n<=0)return0;

elsen+fun(n-l)；}則計算fun(n)(n>0)需要調(diào)用該函數(shù)的次數(shù)為()。

A、n+1

B、n-1

C、n

D、n+2

49、對于一個具有N個頂點的無向凰若采用鄰接矩陣表示,則該矩陣大小是

()

A、N

B、(N-D2

C、(N-1)*N

D、N*N

50、對有n個記錄的表進(jìn)行直接插入排序,在最壞情況下需進(jìn)行()次關(guān)鍵字比

較。

A、n-l

B、n+1

C、n/2

D、n(n-l)/2

參考答案及解析

一、單項選擇題

1、D

2、C

3、D

4、A

5、D

6、C

7、C

8、A

9、D

10、D

11、B

12、A

13、A

14、C

15、C

16、B

17、C

18、A

19、A

20、D

21、D

22、D

23、D

24、D

25、D

26、A

27、B

28、A

29、A

30、A

31、B

32、B

33、D

34、D

35、D

36、B

37、C

38、C

39、B

40、A

41、C

42、B

43、C

44、D

45、D

46、C

47、D

48、A

49、D

50、D

數(shù)據(jù)結(jié)構(gòu)模擬（二）

一、單項選擇題（100題）

1、以下說法正確的是（）。

A、數(shù)據(jù)元素是數(shù)據(jù)的最小單位

B、數(shù)據(jù)項是數(shù)據(jù)的基本單位

C、數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合

D、一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

2、用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組中R[l..n],

結(jié)點R[i]若有左孩子，其左孩子的編號為結(jié)點

A、R[2i+1]

B、R[2i]

C、R[i/2]

D、R[2i-1]

3、在n個結(jié)點的順序表中，算法的時間復(fù)雜度是0（1）的操作是（）。

A、訪問第i個結(jié)點（iWiWn）和求第i個結(jié)點的直接前驅(qū)（2WiWn）

B、在第i個結(jié)點后插入一個新結(jié)點（IWiWn）

C、刪除第i個結(jié)點（iWiWn）

D、將n個結(jié)點從小到大排序

4、有n個十進(jìn)制整數(shù)進(jìn)行基數(shù)排序,其中最大的整數(shù)為5位,則基數(shù)排序過程中

臨時建立的隊數(shù)個數(shù)是（）。

A、10

B、n

C、5

D、2

5、一棵二叉樹有100個結(jié)點，則至少有（）個葉結(jié)點。

A、1

B、2

C、3

D、4

6、算法是描述解決特定問題的思路.方法和步驟,是求解步驟（指令）的有限序

列。其特性除了包含輸入和輸出外,還包括（）。（5.0分）

A、有窮性.正確性.可行性

B、有窮性.正確性.確定性

C、有窮性.確定性.可行性

D、正確性.確定性.可行性

7、已知一如下10個記錄的表，其關(guān)鍵字序列為

(2,15,19,25,30,34,44,55,58,80),用折半查找法查找關(guān)鍵字為55的記錄，比較

次數(shù)是

A、1次

B、2次

C、3次

D、4次

8、若INDEX(S,T)表示求T在S中的位置，則對于

S="BeiJing&Nanjing"，T=“jing”,INDEX(S,T)=()o

A、2

B、3

C、4

D、5

9、設(shè)串長為n,模式串長為m,則KMP算法所需的附加空間為()。

A、0(m)

B、0(n)

C、0(m*n)

D、0(nlog2m)

10、雙向鏈表中有兩個指針域，llink和rlink分別指向前趨及后繼，設(shè)p

指向鏈表中的一個結(jié)點，在P的結(jié)點前插入一個指針q指向的結(jié)點操作是

()o

A、p->llink=q;

B、p->llink=q;Q->rlink=p;p->llink->rlink=q;

C、q->rlink=p;

D、q->llink=p->llink;

q->llink=p->llink;q->rlink=q;P->llink->rlink=q;p->llink=q->rlink;P->1

1ink=q;p->llink=q;

11、下列四種排序方法中，不穩(wěn)定的方法是()

A、直接插入排序

B、冒泡排序

C、歸并排序

D、直接選擇排序

12、假設(shè)以行序為主序存儲二維數(shù)組A=array[l...100,1...100],設(shè)每個數(shù)組

元素占2個存儲單元,基地址為10,則L0C[5,5]=

A、818

B、808

C、1010

D、1020

13、下述編碼中哪一個不是前綴編碼（）

A、{00,01,10,11）

B、{01,0,1,10）

C、{0,10,110,111）

D、[1,01,000,111）

14、由權(quán)值3,6,7,2,5的葉子結(jié)點生成的一顆哈夫曼樹，它的帶權(quán)長度為（）0

（3.0分）

A、51

B、23

C、53

D、74

15、一個隊列的入隊序列是1,2,3,4,5,6,7,則隊列的出隊序列可能是（）。

A、1,2,3,5,7,6,4

B、1,2,3,4,5,6,7

C、7,6,5,4,1,2,3

D、7,6,5,4,3,2,1

16、若SUBSTR⑸i,k）表示求S中從第i個字符開始的連續(xù)k個字符組成的子

串的操作,則對于S="Beijing&Nanjing"，SUBSTR（S,4,5）=（）。

A、“ijing”

B、“jing&”

C、“ingNa”

D、“ing&N”

17、鏈隊列的在建立時，可以采用（）將幾個元素鏈接起來建立單鏈表。

A、頭插法

B、尾插法

C、隨機(jī)插入法

D、需要指定插入位置的方法

18、（6分）數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為0。

A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

B、順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)

C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)

D、簡單結(jié)構(gòu)和構(gòu)造結(jié)構(gòu)

19、下述幾種排序方法中，要求輔助內(nèi)存最大的是（）。

A、插入排序

B、快速排序

C、歸并排序

D、選擇排序

20、順序棧包含兩部分，數(shù)組data[10]和棧頂top,當(dāng)top值為()表示棧

滿。

A、0

B、9

C,10

D、-1

21、下列程序的空間復(fù)雜度是()。

For(i=l;i<=n;++i){for(j=l;j<=m;++j){c[i][j]=0;}}

A、0(m*n)

B、0(m+n)

C、0(m-n)

D、0(m/n)

22、數(shù)據(jù)結(jié)構(gòu)這門學(xué)科的研究內(nèi)容下面選項最準(zhǔn)確的是

A、研究數(shù)據(jù)對象和數(shù)據(jù)之間的關(guān)系

B、研究數(shù)據(jù)對象

C、研究數(shù)據(jù)對象和數(shù)據(jù)的操作

D、研究數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系和操作

23、某順序棧sqStack,其成員包含兩部分:data[10]和top,分別代表數(shù)據(jù)

和棧頂，則表示棧中第三個數(shù)據(jù)元素的是()

A、sqStack.data[2]

B、sqStack.data[3]

C、sqStack.data[4]

D、無法表示

24、在一個單鏈表中，刪除p所指結(jié)點的直接后繼的操作是

A、p->next=p->next->next;

B、p=p->next;p->next=p->next->next;

C、p->next=p->next;

D、p=p->next->next;

25、數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址不相同的,稱為0

A、存儲結(jié)構(gòu)

B、邏輯結(jié)構(gòu)

C、鏈?zhǔn)酱鎯Y(jié)構(gòu)

D、順序存儲結(jié)構(gòu)

26、算法的有窮性是指()。

A、算法程序的運行時間是有限的

B、算法程序所處理的數(shù)據(jù)量是有限的

C、算法程序的長度是有限的

D、算法只能被有限的用戶使用

27、對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小

是（）

A、n

B、（n-l）/2

C,n-1

D>n2

28、如果含有n個頂點的圖形成一個環(huán)，則它有（）棵生成樹

A、n

B、n-1

C、n+1

D、不確定

29、由三個結(jié)點構(gòu)成的二叉樹，共有（）種不同的形態(tài)

A、4

B、5

C、6

D、7

30、設(shè)一棵完全二叉樹中有65個結(jié)點，則該完全二叉樹的深度為（）。

A、8

B、7

C、6

D、5

31、在二叉排序樹中插入一個結(jié)點最壞情況下的時間復(fù)雜度為（）0

A、0（1）

B、0（n）

C、0（log2n）

D、0（n2）

32、（3分）下列關(guān)于散列函數(shù)的說法正確的是（D）。

A、散列函數(shù)越復(fù)雜越好

B、用除余法構(gòu)造的散列函數(shù)是最好的

C、散列函數(shù)越簡單越好

D、在沖突盡可能少的情況下,散列函數(shù)越簡單越好

33、在進(jìn)棧運算時，應(yīng)先判別棧是否①，在出棧運算時.應(yīng)先判別棧是否②，

①②處應(yīng)該是（）

A、空，滿

B、滿，空

C、滿，上溢

D、空，下溢

34、設(shè)二維數(shù)組A[L.m,1..n](即m行n列)按行存儲在數(shù)組B[L.m*n]

中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為()。

A、(i-l)*n+j

B、(i-l)*n+j-l

C,i*(j-l)

D、j*m+i-l

35、在長度為n的順序表的第i(lsisn+1)個位置上插入一個元素，元素的移

動次數(shù)為(A)。

A、n-i+1

B、n-i

C、i

D、i-1

36、(6分)已知二叉排序樹G,要輸出其結(jié)點的有序序列,則采用的遍歷方法是

(Oo

A、按層遍歷

B、前序遍歷

C、中序遍歷

D、后序遍歷

37、設(shè)有100個元素的有序表,采用折半查找方法,成功時最大的比較次數(shù)是()

A、25

B、50

C、10

D、7

38、設(shè)n,m為一棵二叉樹上的兩個結(jié)點，在中序遍歷序列中n在m前的條件

是

A、n在m右方

B、n在m左方

C、n是m的祖先

D、n是m的子孫

39、用鏈?zhǔn)酱鎯Φ臈＃谶M(jìn)棧操作時，將要進(jìn)棧的結(jié)點放在鏈表的()

A、頭部

B、尾部

C、中間

D、用戶指定的位置

40、對包含n個元素的散列表進(jìn)行查找，平均查找長度為

A、不直接依賴于n

B、O(n2)

C、O(log2n)

D、0（n）

41、棧通常采用的兩種存儲結(jié)構(gòu)是（）

A、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)

B、散列方式和索引方式

C、鏈?zhǔn)酱鎯Y(jié)構(gòu)和數(shù)組

D、線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)

42、在一棵二叉樹上第4層的結(jié)點數(shù)最多為

A、2

B、4

C、6

D、8

43、雙向鏈表的每一個結(jié)點有（）個地址域（指針域/引用域）。（3.0分）

A、1

B、2

C、3

D、0

44、設(shè)有串sl=Mwelcometozdsoftcolleage!w和s2="so"，那么s2在si

中的索引位置是

A、12

B、14

C、13

D、10

45、假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100,1..100],設(shè)每個數(shù)據(jù)元

素占2個存儲單元，基地址為10,則L0C[5,5]=（）。

A、808

B、818

C、1010

D、1020

46、設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點，則選用（）最節(jié)省時間。

A、單鏈表

B、單循環(huán)鏈表

C、帶尾指針的單循環(huán)鏈表

D、帶頭結(jié)點的雙循環(huán)鏈表

47、從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的

一端的方法，稱為（）o

A、歸并排序

B、冒泡排序

C、插入排序

D、選擇排序

48、有六個元素6,5,4,3,2,1的順序進(jìn)棧，問下列哪一個不是合法的出棧序

列？（C）

A、543612

B,453126

C,346521

D.234156

49、對二叉樹的結(jié)點從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點的編號大于其左、

右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編

號，可采用（）遍歷實現(xiàn)編號。

A、先序

B、中序

C、后序

D、從根開始按層次遍歷

50、已知某二叉樹的后序遍歷序列是DabeC,中序遍歷序列是DebaC,它的前序

遍歷序列是（）

A、aCbeD

B、DeCaB

C、DeabC

D、CeDba

參考答案及解析

一、單項選擇題

1、D

【解析】解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶

有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。

2、B

3、A

【解析】解釋：在順序表中插入一個結(jié)點的時間復(fù)雜度都是0(n2),排序的時間復(fù)雜度為

0(n2)或0(nlog2n)。順序表是一種隨機(jī)存取結(jié)構(gòu)，訪問第i個結(jié)點和求第i個結(jié)點的直接

前驅(qū)都可以直接通過數(shù)組的下標(biāo)直接定位，時間復(fù)雜度是0(1)O

4、A

5、A

6、C

7、B

8、C

9、A

10、C

11、C

12、A

13、B

14、A

15、B

16、B

17、B

18、C

19、C

20、B

21、A

22、D

23、A

24、A

25、C

26、A

27、D

28、A

29、B

30、B

31、B

32、D

33、B

34>A

【解析】解釋：特殊值法。取i二戶1,易知A[l,1]的的下標(biāo)為1,四個選項中僅有A選項

能確定的值為1,故選A。

35、A

36、C

37、D

38、B

39、A

40、A

41、A

42、D

43、B

44、C

45、B

【解析】解釋：以行序為主，則L0C[5,5]=[(5-1)*100+(5-1)]*2+10=818。

46、C

47、D

48、C

49、C

【解析】解釋：根據(jù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點的順序遍歷二叉

樹，即后序遍歷二叉樹。

50、D

數(shù)據(jù)結(jié)構(gòu)模擬（三）

一、單項選擇題（100題）

1、下面敘述正確的是（）。

A、算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)

B、算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)

C、算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止

D、以上三種描述都不對

2、設(shè)樹T的度為4,其中度為1,2,3和4的結(jié)點個數(shù)分別為4,2,1,1則T中

的葉子數(shù)為（D）

A、5

B、6

C、7

D、8

3、在一棵平衡二叉樹中，每個結(jié)點的平衡因子的取值范圍是（）。

A、-ri

B、-2~2

C、「2

D、0~1

4、用鏈?zhǔn)酱鎯Φ臈?，在進(jìn)行出棧和入棧運算時（）

A、僅修改頭指針

B、僅修改尾指針

C、頭、尾指針都要修改

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

5、下列敘述正確的是。

A、線性表是線性結(jié)構(gòu)

B、棧和隊列是非線性結(jié)構(gòu)

C、線性鏈表是非線性結(jié)構(gòu)

D、二叉樹是線性結(jié)構(gòu)

6、連續(xù)存儲設(shè)計時，存儲單元的地址（）。

A、一定連續(xù)

B、一定不連續(xù)

C、不一定連續(xù)

D、部分連續(xù)，部分不連續(xù)

7、一個子串在包含它的主串中的位置是指。。

A、子串中最后的那個字符在主串中的位置

B、子串的最后那個字符在主串中首次出現(xiàn)的位置

C、子串中第一個字符在主串中的位置

D、子串的第一個字符在主串中首次出現(xiàn)的位置

8、圖中有關(guān)路徑的定義是（A）o

A、由頂點和相鄰頂點序偶構(gòu)成的邊所形成的序列

B、由不同頂點所形成的序列

C、由不同邊所形成的序列

D、上述定義都不是

9、下列數(shù)據(jù)中，（C）是非線性數(shù)據(jù)結(jié)構(gòu)。

A、棧

B、隊列

C、完全二叉樹

D、堆

10、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成

A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)

D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

11、在一個帶頭結(jié)點的雙向循環(huán)鏈表中，若要在p所指向的結(jié)點之前插入一個

新結(jié)點，則需要相繼修改（）個指針域的值。

A、2

B、3

C、4

D、6

12、某哈希查找表有n條記錄，對應(yīng)的哈希函數(shù)具有m個值，則（）

A、n<m

B、n>m

C、n<=m

D、n>=m

13、棧和隊列都是（）。

A、順序存儲的線性結(jié)構(gòu)

B、鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)

C、限制存取點的線性結(jié)構(gòu)

D、限制存取點的非線性結(jié)構(gòu)

14、下面關(guān)于線性表的敘述中，錯誤的是哪一個？（B）

A、線性表采用順序存儲,必須占用一片連續(xù)的存儲單元。

B、線性表采用順序存儲,便于進(jìn)行插入和刪除操作。

C、線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。

D、線性表采用鏈接存儲，便于插入和刪除操作。

15、具有4個頂點的無向完全圖有一條邊

A、6

B、12

C、16

D、20

16、下面程序段的時間復(fù)雜性的量級為()。Intfun(int

n){1=1,s=l;While(s<n)S+=++I;ReturnI;}

A、0(n/2)

B、O(logn)

C、0(n)

D、0(nl/2)

17、一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是()0

A、堆排序

B、冒泡排序

C、快速排序

D、歸并排序

18、在存儲結(jié)構(gòu)上，如果用帶頭節(jié)點單鏈表實現(xiàn)隊列(假定front和rear分別

為隊首和隊尾指針)，則刪除一個結(jié)點的操作為

A、front.next=front.next,next

B、rear=rear.next

C、rear=front.next

D、front=front,next

19、通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著

()o

A、數(shù)據(jù)具有同一特點

B、不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要

一致

C、每個數(shù)據(jù)元素都一樣

D、數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等

20、排序方法中，從未排序序列中依次取出元素與已排序序列(初始時為空)

中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為()

A、希爾排序

B、起泡排序

C、插入排序

D、選擇排序

21、高度為n、結(jié)點數(shù)也為n的二叉樹，共有()棵。

A、n

B、2n-l

C、n-1

D、2n-l

22、一個順序棧S,其棧頂元素下標(biāo)為top,則將元素e入棧的操作是(),,

(4.0分)

A、S[top]=e;top++;

B、top++;S[top]=e;

C、S[top]=e;

D>S[top]=e;

23、下列程序的時間復(fù)雜度是()。

For(i=l;i<=n;++i){for(j=l;j<=n;++j){c[i][j]=0;}}

A、0(n*n)

B、0(n)

C、0(2n)

D、0(2n*n)

24、無向圖的鄰接矩陣是-一個(B)。

A、對角矩陣

B、對稱矩陣

C、上三角矩陣

D、零矩陣

25、(3分)下列選項中,其平均查找性能與基于二叉排序樹的查找相當(dāng)?shù)氖?/p>

(A)o

A、二分查找

B、順序查找

C、分塊查找

D、索順序查找

26、在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的()倍

A、1212122020年1月2日

B、1

C、2

D、3

27、棧的插入與刪除操作在()進(jìn)行。(4.0分)

A、棧頂

B、棧底

C、任意位置

D、指定位置

28、設(shè)圖G中頂點數(shù)為n,則圖G至少有()條邊。

A、0

B、n

C、n（n-l）/2

D>n（n-1）

29、（4分）判定一個隊列QU（最多元素為m）為空的條件是（C）。

A、QU->rear-QU->front==m

B、QU->rear-QU->front-1==m

C、QU->front==QU->rear

D、Q（J->front==QU->rear+l

30、用鏈表方式存儲的隊列，在進(jìn)行刪除運算時（）。

A、僅修改頭指針

B、僅修改尾指針

C、頭、尾指針都要修改

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

31、算法的計算量的大小稱為計算的（）<,

A、效率

B、復(fù)雜性

C、現(xiàn)實性

D、難度

32、圖的廣度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（）。

A、前序，棧

B、層次，棧

C、前序，隊列

D、層次，隊列

33、順序表中第一個元素的存儲地址是100,每個元素的長度為2,則第五個元

素的地址是（）

A、110

B、108

C、100

D、120

34、在一個順序循環(huán)隊列中，隊尾指向隊尾元素的（）位置。

A、前一個

B、后一個

C、當(dāng)前

D、最后

35、在一棵二叉排序樹上按（）遍歷得到的結(jié)點序列是一個有序序列

A、先序

B、中序

C、后序

D、頭序

36、（4分）若棧采用鏈?zhǔn)酱鎯Y(jié)構(gòu),則下列說法中正確的是（B）。

A、需要判斷棧滿且需要判斷棧空

B、不需要判斷棧滿但需要判斷棧空

C、需要判斷棧滿但不需要判斷?？?/p>

D、不需要判斷棧滿也不需要判斷?？?/p>

37、對于順序循環(huán)隊列，以下說法正確的是（）

A、無法判斷隊列是否為空

B、無法判斷隊列是否為滿

C、隊列不可能滿

D、以上說法都不對

38、采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）

A、接層遍歷

B、中序遍歷

C、先序遍歷

D、后序遍歷

39、設(shè)一組初始記錄關(guān)鍵字序列為（Q,H,C,Y,P,A,M,S,R,D,F,X）,

則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（）。

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

B、P,A,C,S,Q,D,F,X,R,H,M,Y

C、A,D,C,R,F,Q,M,S,Y,P,H,X

D、H,C,Q,P,A,M,S,R,D,F,X,Y

40、設(shè)廣義表L=（（a,b,c））,則L的長度和深度分別為（）。

A、1和1

B、1和3

C、1和2

D、2和3

41、在二叉排序樹的（）序列是一個遞增有序序列。

A、先序遍歷

B、中序遍歷

C、后序遍歷

D、層次遍歷

42、具有4個頂點的無向完全圖有（）條邊

A、6

B、12

C、18

D、20

43、以下說法錯誤的是（）0

A、求表長、定位這兩種運算,在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率，比采用鏈

式存儲結(jié)構(gòu)時實現(xiàn)的效率低

B、順序存儲的線性表可以隨機(jī)存取

C、由于順序存儲要求連續(xù)存儲區(qū)域,所以在存儲管理上不夠靈活

D、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)

44、根據(jù)線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的指針數(shù)，將線性鏈表分成

()

A、單鏈表與循環(huán)鏈表

B、單鏈表與十字鏈表

C、單鏈表與雙鏈表

D、循環(huán)鏈表與多鏈表

45、(4分)在一個單鏈表中,若刪除p指向結(jié)點的后繼結(jié)點,則執(zhí)行的操作為

(A)o

A、q=p->next;p->next=p->next->next;free(q)

B、p=p->next;q=p->next;p=q->next;fe(e)

C、q=p->next->next;p=p->next;free(q)

D、p=p->next->next;q=p->next;feeq)

46、設(shè)一棵4叉樹中有N1個度數(shù)為1的結(jié)點,N2個度數(shù)為2的結(jié)點,……,N4個

度數(shù)為4的結(jié)點,則該樹中共有()個葉子結(jié)點。

A、N1+N2

B、N1+2*N2+3*N3

C、N2+N3+4*N4

D、N2+2*N3+3*N4+1

47、如果讓元素1,2,3,4,5,6,7依次進(jìn)棧，則出棧次序不可能出現(xiàn)()的情況

A、1,2,3,4,5,6,7

B、7,6,1,4,3,2,5

C、3,2,1,4,5,6,7

D、1,2,3,4,5,7,6

48、對n個不同的關(guān)鍵字進(jìn)行遞增冒泡排序,在下列哪種情況下比較的次數(shù)最多

()。

A、元素?zé)o序

B、元素遞增有序

C、元素遞減有序

D、都一樣

49、時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為0(nlog2n)的是()。

A、堆排序

B、冒泡排序

C、選擇排序

D、快速排序

50、設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多

比較次數(shù)不超過()o

A、log2(n)+1

B、log2(n)-1

C、log2(n)

D、log2(n+1)

參考答案及解析

一、單項選擇題

1、C

2、D

3、A

4、D

5、A

6、A

7、D

8、A

9、C

10、C

11、C

12、D

13、C

14、B

15、A

16、D

17、D

18、A

19、B

20、C

21、B

22、B

23、A

24、B

25、A

26、C

27、A

28、A

29、C

30、D

31、B

32、D

33、B

34、B

35、B

36、B

37、D

38、C

39、D

40、C

【解析】解釋：廣義表的深度是指廣義表中展開后所含括號的層數(shù)，廣義表的長度是指

廣義表中所含元素的個數(shù)。根據(jù)定義易知L的長度為1,深度為2。

41、B

42、A

43、D

44、C

45、A

46、D

47、B

48、C

49、A

50、A

數(shù)據(jù)結(jié)構(gòu)模擬(四)

一、單項選擇題(100題)

1、采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的。

A、按層遍歷

B、前序遍歷

C、中序遍歷

D、后序遍歷

2、設(shè)計一個判別表達(dá)式中左右括號是否配對出現(xiàn)的算法，采用()數(shù)據(jù)結(jié)構(gòu)最

佳。

A、線性表的順序存儲結(jié)構(gòu)

B、隊列

C、棧

D、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

3、計算機(jī)算法必須具備輸入、輸出、()等5個特性。

A、可行性、可移植性和可擴(kuò)展性

B、可行性、確定性和有窮性

C、確定性、有窮性和穩(wěn)定性

D、易讀性、安全性和穩(wěn)定性

4、串是()。

A、少于一個字母的序列

B、任意個字母的序列

C、不少于一個字符的序列

D、有限個字符的序列

5、設(shè)散列表中有m個存儲單元，散列函數(shù)H(key)=key%p,則p最好選擇

()o

A、小于等于m的最大奇數(shù)

B、小于等于m的最大素數(shù)

C、小于等于m的最大偶數(shù)

D、小于等于m的最大合數(shù)

6、用鏈表表示線性表的優(yōu)點是()。

A、便于隨機(jī)存取

B、占用的存儲空間較順序表少

C、便于進(jìn)行插入和刪除操作

D、元素的物理順序與邏輯順序相同

7、廣義表A=((a),a)的表頭是()。

A、a

B、(a)

C、b

D、((a))

8、樹的后序遍歷等價于該樹對應(yīng)二叉樹的。

A、層次遍歷

B、前序遍歷

C、中序遍歷

D、后序遍歷

9、(3分)某索引順序表共有元素395個，.平均分成5塊。若先對引表采用順序

查找,再對塊中元素進(jìn)行順序查找,則在等概率情況下,分塊查找成功的平均查找

長度是(A)。

A、43

B、79

C、198

D、200

10、給定一段文本中的4個字符(u,v,w.x)及其出現(xiàn)頻率(fu,fv,fw,

fx),若對應(yīng)的哈夫曼編碼為u:00,v:010,w:011,x:l,則下列哪組頻率可能對

應(yīng)(fu,fv,fw.fx)?(B)o

A、15,23,16,45

B、30,12,20,33

C、41,12,20,32

D、55,22,18,46

11、對于長度為18的順序存儲的有序表，若采用二分查找，則查找第15個

元素的查找長度為()。(1分)

A、3

B、4

C、5

D、6

12、一棵二叉樹的第7層上最多含有的結(jié)點數(shù)為。

A、4

B、64

C、127

D、128

13、(6分)若希望1000個無序元素中盡快求得前10個最大元素,應(yīng)借用(A)o

A、堆排序

B、快速排序

C、冒泡排序

D、歸并排序

14、下列程序段的時間復(fù)雜度為()。For(i=0;i<m;i++)for(j=0;

j<t;j++)c[i][j]=0;For(i=0;i<m;i++)for(j=0;j<t;

j++)for(k=0;k<n;k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];

A、0(m*n*t)

B、0(m+n+t)

C、0(m+n*t)

D、0(m*t+n)

15、最大容量為maxsize的循環(huán)隊列，隊尾指針是rear,隊頭是front,則

隊滿條件為()

A、(rear+1)maxsize==(front+1)maxsize

B、(front+1)maxsize==rear

C、(rear+1)maxsize==front

D、rear==front

16、一個有序表為｛1,3,9,12,32,41,45,62,75,77,82,95,100),

當(dāng)用二分查找值為82的結(jié)點時，查找成功時的比較次數(shù)為()。(1分)

A、1

B、2

C、4

D、8

17、單鏈表不具備的特點是()0(3.0分)

A、插入.刪除不需要移動元素

B、鏈表長度可動態(tài)增長

C、所需空間與線性長度成正比

D、可隨機(jī)訪問任一個元素

18、(6分)在下列排序方法中，記錄關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無

關(guān)的方法是(D)。

A、直接插入排序

B、冒泡排序

C、希爾排序

D、直接選擇排序

19、設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，all

為第一元素，其存儲地址為1,每個元素占一個地址空間，則a85的地址為

()。

A、13

B、32

C、33

D、40

20、對于線性表(7,34,55,25,64,46,20,10)進(jìn)行散列存儲時，若選用

H(K)=K附作為散列函數(shù)，則散列地址為1的元素有()個.

A、1

B、2

C,3

D、4

21、若已知一個棧的入棧序列是1,2,3,..,n,其輸出序列為pl,p2,p3,…,pn,

若pl=n,則pn為()o

A、1

B、n

C、n/2

D、n-1

22、(3分)若某二叉樹的后序遍歷序列為dabec,中序遍歷序列是debac,則它的

前序遍歷序列是(B)。

A、acbed

B、cedba

C、deabc

D、decab.

23、串的長度是指()。

A、串中所含不同字母的個數(shù)

B、串中所含字符的個數(shù)

C、串中所含不同字符的個數(shù)

D、串中所含非空格字符的個數(shù)

24、將序列(100,80,90,60,120,110,130,1,2,3)生成二叉排序樹,則該樹的高度

為

A、4

B、5

C、6

D、7

25、遞歸函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為()的數(shù)據(jù)結(jié)構(gòu)。

A、隊列

B、多維數(shù)組

C、棧

D、線性表

26、串“ababaaababaa”的next數(shù)組為()。

A、012345678999

B、012121111212

C、011234223456

D、0123012322345

27、深度為h的滿m叉樹的第k層有（）個結(jié)點。（IWkWH）

A、mk-1

B、mk-1

C>mh-1

D、mh-l

28、表長為n的順序存儲的線性表，當(dāng)在任意位置上插入或刪除一個元素的概

率相等時，插入一個元素所需移動元素的平均個數(shù)為（D、），刪除一個元素需

要移動元素的平均個數(shù)為（）

A、（n-l）/2

B、n

C、（n+l）/2

D、n/2

29、（3分）在一非空二叉樹的中序遍歷序列中,根結(jié)點的右邊（A）o

A、只有右子樹上的所有結(jié)點

B、只有右子樹.上的部分結(jié)點

C、只有左子樹上的部分結(jié)點

D、只有左子樹上的所有結(jié)點

30、高度為5（不設(shè)計外部結(jié)點）的3階B-樹至少有（）個結(jié)點。

A、32

B、31

C、64

D、108

31、G是一個簡單的非連通無向圖，共有28條邊，則該圖至少有（）個頂

點。

A、6

B、7

C、8

D、9

32、序列⑵5,4,1,8,6,7,3｝是第一趟遞增排序后的結(jié)果，則采用的排序方法可

能是（）。

A、快速排序

B、冒泡排序

C、堆排序

D、直接插入排序

33、在帶權(quán)圖的最短路徑問題中，路徑長度是指。

A、路徑上的頂點數(shù)

B、路徑上的邊數(shù)

C、路徑上的頂點數(shù)與邊數(shù)之和

D、路徑上各邊的權(quán)值之和

34、數(shù)據(jù)的基本單位（）

A、數(shù)據(jù)結(jié)構(gòu)

B、數(shù)據(jù)元素

C、數(shù)據(jù)項

D、文件

35、設(shè)一個順序有序表A[l:14]中有14個元素，則采用二分法查找元素A[4]的

過程中比較元素的順序為（）o

A、A[l],A[2],A[3],A[4]

B,A[l],A[14],A[7].,A[4]

C、A[7],A[3],A[5],A[4]

D、A[7],A[5],A[3],A[4]

36、向一個棧頂指針為HS的鏈棧中將一個S指針?biāo)傅慕Y(jié)點入棧，執(zhí)行（）。

A、HS->next=s

B、S->next=HS->next;HS->next=s

C、S->next=HS;HS=s

D、S->next=HS;HS=HS->next

37、（4分）從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點時,用x保存被刪結(jié)點的

值,則執(zhí)行⑻。

A、x=HS;HS=HS->next;

B、x=HS->data;

C、HS=HS->next;x=HS->data;

D>x=HS->data;HS=HS->next;

38、給定一個無序的單鏈表,要求的空間復(fù)雜度為0（1）,則建立一個長度為n的

有序單鏈表的時間復(fù)雜度為（）

A、0（n）

B、0（1）

C、0（n、2）

D、0（log2n）

39、非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足

A、p->next==NULL

B、p==NULL

C、p->next==head

D>p==head

40、下列關(guān)于算法輸出的敘述中，正確的是（）。

A、算法一定沒有輸出

B、算法可以沒有輸出

C、算法至少有一個輸出

D、算法必須有多個

41、鏈?zhǔn)綏＝Y(jié)點為：（data,link）,top指向棧頂.若想摘除棧頂結(jié)點，并將刪

除結(jié)點的值保存到x中，則應(yīng)執(zhí)行操作（）o

A、x=top->data;top=top->link；

B、top=top->link;x=top->link；

C、x=top;top=top->link；

D>x=top->link；

42、算法是（）。

A、計算機(jī)程序

B、解決問題的計算方法

C、排序算法

D、解決問題的有限運算序列

43、在一棵二叉樹中,度為0的結(jié)點數(shù)為nO,度為2的結(jié)點數(shù)為n2,則n0=（）

A、n2-2

B、n2-l

C、n2+l

D、n2+2

44、在單鏈表結(jié)點p之后插入結(jié)點s,正確的操作是（）。（3.0分）

A、p.next=s;s.next=p.next;

B、s.next=p.next;p.next=s;

C、p.next=s;p.next=s.next;

D>p.next=s.next;p.next=s;

45、將數(shù)組稱為隨機(jī)存儲結(jié)構(gòu)是因為（）o

A、數(shù)組元素是隨機(jī)的

B、隨時可以對數(shù)組元素進(jìn)行訪問

C、對數(shù)組的任一元素的存取時間是相等的

D、數(shù)組的存儲結(jié)構(gòu)是不定的

46、設(shè)森林F中有三棵樹，第一，第二，第三棵的結(jié)點個數(shù)分別為Ml,M2,M3。與

森林F對應(yīng)的二叉樹根節(jié)點的右子樹的個數(shù)是（）。（3.0分）

A、Ml

B、M1+M2

C、M3

D、M2+M3

47、設(shè)有序表中的元素為（13,18,24,35,47,50,62）,則在其中利用二分

法查找值為24的元素需要經(jīng)過（）次比較。

A、1

B、2

C、3

D、4

48、（4分）棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是（A）。

A、順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)

B、散鏈方式和索引方式

C、鏈表存儲結(jié)構(gòu)和數(shù)組

D、線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)

49、（4分）下列關(guān)于隊列的敘述中，錯誤的是（D）。

A、隊列是一種先進(jìn)先出的線性表

B、隊列是-種后進(jìn)后出的線性表

C、循環(huán)隊列中進(jìn)行出隊操作時要判斷隊列是否為空

D、在鏈隊列中進(jìn)行入隊操作時要判斷隊列是否為滿

50、抽象數(shù)據(jù)類型的三個組成部分分別為（）。

A、數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作

B、數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

C、數(shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型

D、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型

參考答案及解析

一、單項選擇題

1、B

2、C

3、B

4、D

5、B

6、C

7、B

8、C

9、A

10、B

11、B

12、B

13、A

14、A

15、C

16、D

17、D

18、D

19、C

20、D

21、A

22、B

23、B

24、C

25、C

26、C

27、A

28、D

29、A

30、B

31、D

32、D

33、D

34、B

35、C

36、B

37、D

38、C

39、C

40、C

41、A

【解析】解釋：x=top->data將結(jié)點的值保存到x中，top=top->link棧頂指針指向棧頂

下一結(jié)點，即摘除棧頂結(jié)點。

42、D

43、C

44、B

45、B

46、D

47、C

48、A

49、D

50、A

數(shù)據(jù)結(jié)構(gòu)模擬（五）

一、單項選擇題（100題）

1、假定利用數(shù)組A[N]順序存儲一個棧，top表示棧頂指針，已知棧未滿，則X

入棧時所執(zhí)行的操作是（）o

A、a[-top]=x;

B、a[top--]=x

C、a[++top]=x

DNa[top++]=x

2、若長度為n的線性表采用順序存儲結(jié)構(gòu),在其第i個位置插入一個新元素算

法的時間復(fù)雜度（）o

A、0（log2n）

B、0（1）

C、0（n）

D、0（rT2）

3、設(shè)T是赫夫曼樹，具有5個葉結(jié)點，樹T的高度最高可以是（）

A、2

B、3

C、4

D、5

4、循環(huán)隊列S為滿的條件是（）。

A、S->rear==S->front

B、S->rear+l）%maxsiae==s->front

C、S->rear==0

D、s->front==0

5、已知輸入序列為abed經(jīng)過隊列后能得到的輸出序列有（）

A、dacb

B、abed

C、deba

D>cadb

6、假設(shè)以數(shù)組A[60]存放循環(huán)隊列的元素，其期指針是front=47.當(dāng)前隊列有

50個元素,則隊列的尾指針值為（B）o

A、3

B、37

C,50

D、97

7、(3分)如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的后序就是

T2中結(jié)點的(B)。

A、前序

B、中序

C,后序

D、層序

8、順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為()。

A、0(n)

B、0(n2)

C、0(n/2)

D、0(log2n)

9、下面屬于整數(shù)類I的實例的是()

A、229

B、0.229

C、229E-2

D、"229”

10、設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為

()o

A、第i行非0元素的個數(shù)之和

B、第i列非0元素的個數(shù)之和

C、第i行0元素的個數(shù)之和

D、第i列0元素的個數(shù)之和

11、計算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是()

A、數(shù)據(jù)

B、數(shù)據(jù)元素

C、數(shù)據(jù)項

D、數(shù)據(jù)庫

12、(3分)下列關(guān)于哈夫曼樹的敘述中，錯誤的是(A)。

A、用n個結(jié)點構(gòu)造的哈夫曼樹是唯一的

B、哈夫曼樹中只有度為0或度為2的結(jié)點

C、樹中兩個權(quán)值最小的結(jié)點可能是兄弟結(jié)點

D、同-結(jié)點集構(gòu)造的二叉樹中，哈夫曼樹的WPL最小

13、一個算法應(yīng)該是()。

A、程序

B、問題求解步驟的描述

C、要滿足五個基本特性

D、A和C.

14、從表中任一結(jié)點出發(fā)，都能掃描整個表的是()。

A、單鏈表

B、順序表

C、循環(huán)鏈表

D、靜態(tài)鏈表

15、