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

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

一、單項(xiàng)選擇題（100題）

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

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

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

A、1400

B、1404

C、1372

D、1368

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

動(dòng)（）個(gè)元素。（3.0分）

A、n-i

B、n-i+1

C、n-i-1

D、i

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

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

B、根結(jié)點(diǎn)沒(méi)有子樹(shù)

C、不存在

D、沒(méi)有結(jié)點(diǎn)

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

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

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

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

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

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

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

A、k-1

B、k

C、k+1

D、k（k+l）/2

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

A、索引存儲(chǔ)

B、壓縮存儲(chǔ)

C、順序存儲(chǔ)

D、散列存儲(chǔ)

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

是()

A、i>0

B、iWn

C,lWiWn

D、lWiWn+1

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

指針向量大小至少為()

A、n

B、2n

C、e

D、2e

9、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表示，則頂點(diǎn)表向

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

A、都是n

B、都是n+e

C、n和n+e

D、n和2e

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

典序列的次序進(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是一個(gè)對(duì)稱(chēng)矩陣,為了節(jié)省存儲(chǔ),將其下三角部分按行序存放在一

維數(shù)組B[l,n(n-l)/2]中，對(duì)下三角部分中任一元素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、任何一個(gè)無(wú)向連通網(wǎng)的最小生成樹(shù)

A、有一棵或多棵

B、只有1棵

C、一定有多棵

D、可能不存在

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

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

頭結(jié)點(diǎn)開(kāi)始,查找任何一個(gè)元素

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

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

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

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

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

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

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

A、2

B、3

C、4

D、5

15、在一個(gè)鏈隊(duì)中，假設(shè)和分別為隊(duì)首和隊(duì)尾指針,則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算時(shí)

(C)o

A、r=f->next;

B、r=r->next：

C、f=f->next;

D、f=r->next;

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

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

A、1010

B、1016

C、1018

D、1019

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

A、圖的遍歷是從給定的源點(diǎn)出發(fā)對(duì)每一個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次

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

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

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

18、對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表,在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)

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

A、0(1),0(n)

B、0(n),0(n)

C、0(1),0(1)

D、0(n),0(l)

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

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

A、CBEFDA

B、FEDCBA

C、CBEDFA

D、不定

20、對(duì)n個(gè)頂點(diǎn)和e條邊的有向圖，以鄰接矩陣存儲(chǔ)，則求圖中某頂點(diǎn)入度的

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

A、O(n)

B、0(e)

C、0(n+e)

D、0(n2)

21、從沒(méi)有排序序列中挑選元素,并將其一次插入已排序序列末端的方法，稱(chēng)

()

A、歸并排序

B、冒泡排序

C、插入排序

D、選擇排序

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

A、快速排序

B、堆排序

C、歸并排序

D、冒泡排序

23、表示一個(gè)有100個(gè)頂點(diǎn)，1000條邊的無(wú)向圖的鄰接矩陣有()個(gè)非零矩

陣元素。

A、100

B、1000

C、9000

D、1000X2

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

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)中，不屬于二叉樹(shù)的是。

A、B樹(shù)

B、AVL樹(shù)

C、二叉排序樹(shù)

D、哈夫曼樹(shù)

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

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

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

A、棧

B、隊(duì)列

C、樹(shù)

D,線(xiàn)性表

28、在下列排序方法中不需要對(duì)排序碼值進(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、隊(duì)列的特點(diǎn)是O。

A、先進(jìn)先出

B、后進(jìn)先出

C、先進(jìn)后出

D、不進(jìn)不出

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

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

()

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

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

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

D、top[l]=top[2]

32、若長(zhǎng)度為n的線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，訪問(wèn)其第i個(gè)元素的算法時(shí)間

復(fù)雜度為()

A、0(n)

B、0(n'2)

C、0(n-3)

D、0(log2"n)

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

度為()0

A、0(n)

B,0(n2)

C、0(nlog2n)

D、0(log2n)

34、下面敘述正確的是

A、二叉樹(shù)是特殊的樹(shù)

B、二叉樹(shù)等價(jià)于度為2的樹(shù)

C、完全二叉樹(shù)必為滿(mǎn)二叉樹(shù)

D、二叉樹(shù)的左右子樹(shù)有次序之分

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、一個(gè)遞歸算法必須包括()。

A、遞歸調(diào)用

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

C、表達(dá)式求值

D、A,B,C

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

A、0

B、n

C、n(n-1)/2

D、n(n-l)

38、分別以下列序列構(gòu)造二叉排序樹(shù)，與其他三個(gè)序列構(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、若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn),5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)

點(diǎn)個(gè)數(shù)是(B)

A、9

B、11

C、15

D、不確定

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

A、順序查找

B、二分查找

C、插值查找

D、隨機(jī)

41、經(jīng)過(guò)下列棧的運(yùn)算后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)中，從存儲(chǔ)結(jié)構(gòu)上可以將之分為

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

B、順序存儲(chǔ)和非順序存儲(chǔ)

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

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

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

⑵0分)

A、直接插入

B、快速排序

C、堆排序

D,歸并排序

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

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、平均時(shí)間為0(nlogn)的排序方法

D、以上都不對(duì)

46、采用順序查找方法查找長(zhǎng)度為n的線(xiàn)性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為

A、n

B、n/2

C、(n+l)/2

D、(n-l)/2

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

映射到HASH表中需要做()次線(xiàn)性探測(cè)。

A、n2

B、n(n+l)

C、n(n+1)/2

D、n(n-l)/2

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

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

A、n+1

B、n-1

C、n

D、n+2

49、對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向凰若采用鄰接矩陣表示,則該矩陣大小是

()

A、N

B、(N-D2

C、(N-1)*N

D、N*N

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

較。

A、n-l

B、n+1

C、n/2

D、n(n-l)/2

參考答案及解析

一、單項(xiàng)選擇題

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)模擬（二）

一、單項(xiàng)選擇題（100題）

1、以下說(shuō)法正確的是（）。

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

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

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

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

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

結(jié)點(diǎn)R[i]若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)

A、R[2i+1]

B、R[2i]

C、R[i/2]

D、R[2i-1]

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

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

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

C、刪除第i個(gè)結(jié)點(diǎn)（iWiWn）

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

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

臨時(shí)建立的隊(duì)數(shù)個(gè)數(shù)是（）。

A、10

B、n

C、5

D、2

5、一棵二叉樹(shù)有100個(gè)結(jié)點(diǎn)，則至少有（）個(gè)葉結(jié)點(diǎn)。

A、1

B、2

C、3

D、4

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

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

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

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

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

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

7、已知一如下10個(gè)記錄的表，其關(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中的位置，則對(duì)于

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

A、2

B、3

C、4

D、5

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

A、0(m)

B、0(n)

C、0(m*n)

D、0(nlog2m)

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

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

()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è)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[l...100,1...100],設(shè)每個(gè)數(shù)組

元素占2個(gè)存儲(chǔ)單元,基地址為10,則L0C[5,5]=

A、818

B、808

C、1010

D、1020

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

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é)點(diǎn)生成的一顆哈夫曼樹(shù)，它的帶權(quán)長(zhǎng)度為（）0

（3.0分）

A、51

B、23

C、53

D、74

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

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個(gè)字符開(kāi)始的連續(xù)k個(gè)字符組成的子

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

A、“ijing”

B、“jing&”

C、“ingNa”

D、“ing&N”

17、鏈隊(duì)列的在建立時(shí)，可以采用（）將幾個(gè)元素鏈接起來(lái)建立單鏈表。

A、頭插法

B、尾插法

C、隨機(jī)插入法

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

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

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

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

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

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

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

A、插入排序

B、快速排序

C、歸并排序

D、選擇排序

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

滿(mǎn)。

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)這門(mén)學(xué)科的研究?jī)?nèi)容下面選項(xiàng)最準(zhǔn)確的是

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

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

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

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

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

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

A、sqStack.data[2]

B、sqStack.data[3]

C、sqStack.data[4]

D、無(wú)法表示

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

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ì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的,稱(chēng)為0

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

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

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

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

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

A、算法程序的運(yùn)行時(shí)間是有限的

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

C、算法程序的長(zhǎng)度是有限的

D、算法只能被有限的用戶(hù)使用

27、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小

是（）

A、n

B、（n-l）/2

C,n-1

D>n2

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

A、n

B、n-1

C、n+1

D、不確定

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

A、4

B、5

C、6

D、7

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

A、8

B、7

C、6

D、5

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

A、0（1）

B、0（n）

C、0（log2n）

D、0（n2）

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

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

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

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

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

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

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

A、空，滿(mǎn)

B、滿(mǎn)，空

C、滿(mǎn)，上溢

D、空，下溢

34、設(shè)二維數(shù)組A[L.m,1..n](即m行n列)按行存儲(chǔ)在數(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、在長(zhǎng)度為n的順序表的第i(lsisn+1)個(gè)位置上插入一個(gè)元素，元素的移

動(dòng)次數(shù)為(A)。

A、n-i+1

B、n-i

C、i

D、i-1

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

(Oo

A、按層遍歷

B、前序遍歷

C、中序遍歷

D、后序遍歷

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

A、25

B、50

C、10

D、7

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

是

A、n在m右方

B、n在m左方

C、n是m的祖先

D、n是m的子孫

39、用鏈?zhǔn)酱鎯?chǔ)的棧，在進(jìn)棧操作時(shí)，將要進(jìn)棧的結(jié)點(diǎn)放在鏈表的()

A、頭部

B、尾部

C、中間

D、用戶(hù)指定的位置

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

A、不直接依賴(lài)于n

B、O(n2)

C、O(log2n)

D、0（n）

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

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

B、散列方式和索引方式

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

D、線(xiàn)性存儲(chǔ)結(jié)構(gòu)和非線(xiàn)性存儲(chǔ)結(jié)構(gòu)

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

A、2

B、4

C、6

D、8

43、雙向鏈表的每一個(gè)結(jié)點(diǎn)有（）個(gè)地址域（指針域/引用域）。（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è)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100,1..100],設(shè)每個(gè)數(shù)據(jù)元

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

A、808

B、818

C、1010

D、1020

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

A、單鏈表

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

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

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

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

一端的方法，稱(chēng)為（）o

A、歸并排序

B、冒泡排序

C、插入排序

D、選擇排序

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

列？（C）

A、543612

B,453126

C,346521

D.234156

49、對(duì)二叉樹(shù)的結(jié)點(diǎn)從1開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、

右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編

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

A、先序

B、中序

C、后序

D、從根開(kāi)始按層次遍歷

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

遍歷序列是（）

A、aCbeD

B、DeCaB

C、DeabC

D、CeDba

參考答案及解析

一、單項(xiàng)選擇題

1、D

【解析】解釋?zhuān)簲?shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶

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

2、B

3、A

【解析】解釋?zhuān)涸陧樞虮碇胁迦胍粋€(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度都是0(n2),排序的時(shí)間復(fù)雜度為

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

前驅(qū)都可以直接通過(guò)數(shù)組的下標(biāo)直接定位，時(shí)間復(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

【解析】解釋?zhuān)禾厥庵捣?。取i二戶(hù)1,易知A[l,1]的的下標(biāo)為1,四個(gè)選項(xiàng)中僅有A選項(xiàng)

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

35、A

36、C

37、D

38、B

39、A

40、A

41、A

42、D

43、B

44、C

45、B

【解析】解釋?zhuān)阂孕行驗(yàn)橹?，則L0C[5,5]=[(5-1)*100+(5-1)]*2+10=818。

46、C

47、D

48、C

49、C

【解析】解釋?zhuān)焊鶕?jù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點(diǎn)的順序遍歷二叉

樹(shù)，即后序遍歷二叉樹(shù)。

50、D

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

一、單項(xiàng)選擇題（100題）

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

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

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

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

D、以上三種描述都不對(duì)

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

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

A、5

B、6

C、7

D、8

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

A、-ri

B、-2~2

C、「2

D、0~1

4、用鏈?zhǔn)酱鎯?chǔ)的棧，在進(jìn)行出棧和入棧運(yùn)算時(shí)（）

A、僅修改頭指針

B、僅修改尾指針

C、頭、尾指針都要修改

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

5、下列敘述正確的是。

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

B、棧和隊(duì)列是非線(xiàn)性結(jié)構(gòu)

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

D、二叉樹(shù)是線(xiàn)性結(jié)構(gòu)

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

A、一定連續(xù)

B、一定不連續(xù)

C、不一定連續(xù)

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

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

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

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

C、子串中第一個(gè)字符在主串中的位置

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

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

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

B、由不同頂點(diǎn)所形成的序列

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

D、上述定義都不是

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

A、棧

B、隊(duì)列

C、完全二叉樹(shù)

D、堆

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

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

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

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

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

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

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

A、2

B、3

C、4

D、6

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

A、n<m

B、n>m

C、n<=m

D、n>=m

13、棧和隊(duì)列都是（）。

A、順序存儲(chǔ)的線(xiàn)性結(jié)構(gòu)

B、鏈?zhǔn)酱鎯?chǔ)的非線(xiàn)性結(jié)構(gòu)

C、限制存取點(diǎn)的線(xiàn)性結(jié)構(gòu)

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

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

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

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

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

D、線(xiàn)性表采用鏈接存儲(chǔ)，便于插入和刪除操作。

15、具有4個(gè)頂點(diǎn)的無(wú)向完全圖有一條邊

A、6

B、12

C、16

D、20

16、下面程序段的時(shí)間復(fù)雜性的量級(jí)為()。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é)束后不一定能夠選出一個(gè)元素放在其最終位置上的是()0

A、堆排序

B、冒泡排序

C、快速排序

D、歸并排序

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

為隊(duì)首和隊(duì)尾指針)，則刪除一個(gè)結(jié)點(diǎn)的操作為

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ù)具有同一特點(diǎn)

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

一致

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

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

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

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

A、希爾排序

B、起泡排序

C、插入排序

D、選擇排序

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

A、n

B、2n-l

C、n-1

D、2n-l

22、一個(gè)順序棧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、下列程序的時(shí)間復(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、無(wú)向圖的鄰接矩陣是-一個(gè)(B)。

A、對(duì)角矩陣

B、對(duì)稱(chēng)矩陣

C、上三角矩陣

D、零矩陣

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

(A)o

A、二分查找

B、順序查找

C、分塊查找

D、索順序查找

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

A、1212122020年1月2日

B、1

C、2

D、3

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

A、棧頂

B、棧底

C、任意位置

D、指定位置

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

A、0

B、n

C、n（n-l）/2

D>n（n-1）

29、（4分）判定一個(gè)隊(duì)列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、用鏈表方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。

A、僅修改頭指針

B、僅修改尾指針

C、頭、尾指針都要修改

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

31、算法的計(jì)算量的大小稱(chēng)為計(jì)算的（）<,

A、效率

B、復(fù)雜性

C、現(xiàn)實(shí)性

D、難度

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

A、前序，棧

B、層次，棧

C、前序，隊(duì)列

D、層次，隊(duì)列

33、順序表中第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長(zhǎng)度為2,則第五個(gè)元

素的地址是（）

A、110

B、108

C、100

D、120

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

A、前一個(gè)

B、后一個(gè)

C、當(dāng)前

D、最后

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

A、先序

B、中序

C、后序

D、頭序

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

A、需要判斷棧滿(mǎn)且需要判斷棧空

B、不需要判斷棧滿(mǎn)但需要判斷棧空

C、需要判斷棧滿(mǎn)但不需要判斷棧空

D、不需要判斷棧滿(mǎn)也不需要判斷棧空

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

A、無(wú)法判斷隊(duì)列是否為空

B、無(wú)法判斷隊(duì)列是否為滿(mǎn)

C、隊(duì)列不可能滿(mǎn)

D、以上說(shuō)法都不對(duì)

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

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的長(zhǎng)度和深度分別為（）。

A、1和1

B、1和3

C、1和2

D、2和3

41、在二叉排序樹(shù)的（）序列是一個(gè)遞增有序序列。

A、先序遍歷

B、中序遍歷

C、后序遍歷

D、層次遍歷

42、具有4個(gè)頂點(diǎn)的無(wú)向完全圖有（）條邊

A、6

B、12

C、18

D、20

43、以下說(shuō)法錯(cuò)誤的是（）0

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

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

B、順序存儲(chǔ)的線(xiàn)性表可以隨機(jī)存取

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

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

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

()

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

B、單鏈表與十字鏈表

C、單鏈表與雙鏈表

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

45、(4分)在一個(gè)單鏈表中,若刪除p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn),則執(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叉樹(shù)中有N1個(gè)度數(shù)為1的結(jié)點(diǎn),N2個(gè)度數(shù)為2的結(jié)點(diǎn),……,N4個(gè)

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

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、對(duì)n個(gè)不同的關(guān)鍵字進(jìn)行遞增冒泡排序,在下列哪種情況下比較的次數(shù)最多

()。

A、元素?zé)o序

B、元素遞增有序

C、元素遞減有序

D、都一樣

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

A、堆排序

B、冒泡排序

C、選擇排序

D、快速排序

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

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

A、log2(n)+1

B、log2(n)-1

C、log2(n)

D、log2(n+1)

參考答案及解析

一、單項(xiàng)選擇題

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

【解析】解釋?zhuān)簭V義表的深度是指廣義表中展開(kāi)后所含括號(hào)的層數(shù)，廣義表的長(zhǎng)度是指

廣義表中所含元素的個(gè)數(shù)。根據(jù)定義易知L的長(zhǎng)度為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)模擬(四)

一、單項(xiàng)選擇題(100題)

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

A、按層遍歷

B、前序遍歷

C、中序遍歷

D、后序遍歷

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

佳。

A、線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)

B、隊(duì)列

C、棧

D、線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

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

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

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

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

4、串是()。

A、少于一個(gè)字母的序列

B、任意個(gè)字母的序列

C、不少于一個(gè)字符的序列

D、有限個(gè)字符的序列

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

()o

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

B、小于等于m的最大素?cái)?shù)

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

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

6、用鏈表表示線(xiàn)性表的優(yōu)點(diǎn)是()。

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

B、占用的存儲(chǔ)空間較順序表少

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

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

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

A、a

B、(a)

C、b

D、((a))

8、樹(shù)的后序遍歷等價(jià)于該樹(shù)對(duì)應(yīng)二叉樹(shù)的。

A、層次遍歷

B、前序遍歷

C、中序遍歷

D、后序遍歷

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

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

長(zhǎng)度是(A)。

A、43

B、79

C、198

D、200

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

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

應(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、對(duì)于長(zhǎng)度為18的順序存儲(chǔ)的有序表，若采用二分查找，則查找第15個(gè)

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

A、3

B、4

C、5

D、6

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

A、4

B、64

C、127

D、128

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

A、堆排序

B、快速排序

C、冒泡排序

D、歸并排序

14、下列程序段的時(shí)間復(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)隊(duì)列，隊(duì)尾指針是rear,隊(duì)頭是front,則

隊(duì)滿(mǎn)條件為()

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

B、(front+1)maxsize==rear

C、(rear+1)maxsize==front

D、rear==front

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

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

A、1

B、2

C、4

D、8

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

A、插入.刪除不需要移動(dòng)元素

B、鏈表長(zhǎng)度可動(dòng)態(tài)增長(zhǎng)

C、所需空間與線(xiàn)性長(zhǎng)度成正比

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

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

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

A、直接插入排序

B、冒泡排序

C、希爾排序

D、直接選擇排序

19、設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，all

為第一元素，其存儲(chǔ)地址為1,每個(gè)元素占一個(gè)地址空間，則a85的地址為

()。

A、13

B、32

C、33

D、40

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

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

A、1

B、2

C,3

D、4

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

若pl=n,則pn為()o

A、1

B、n

C、n/2

D、n-1

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

前序遍歷序列是(B)。

A、acbed

B、cedba

C、deabc

D、decab.

23、串的長(zhǎng)度是指()。

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

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

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

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

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

為

A、4

B、5

C、6

D、7

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

A、隊(duì)列

B、多維數(shù)組

C、棧

D、線(xiàn)性表

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

A、012345678999

B、012121111212

C、011234223456

D、0123012322345

27、深度為h的滿(mǎn)m叉樹(shù)的第k層有（）個(gè)結(jié)點(diǎn)。（IWkWH）

A、mk-1

B、mk-1

C>mh-1

D、mh-l

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

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

要移動(dòng)元素的平均個(gè)數(shù)為（）

A、（n-l）/2

B、n

C、（n+l）/2

D、n/2

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

A、只有右子樹(shù)上的所有結(jié)點(diǎn)

B、只有右子樹(shù).上的部分結(jié)點(diǎn)

C、只有左子樹(shù)上的部分結(jié)點(diǎn)

D、只有左子樹(shù)上的所有結(jié)點(diǎn)

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

A、32

B、31

C、64

D、108

31、G是一個(gè)簡(jiǎn)單的非連通無(wú)向圖，共有28條邊，則該圖至少有（）個(gè)頂

點(diǎn)。

A、6

B、7

C、8

D、9

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

能是（）。

A、快速排序

B、冒泡排序

C、堆排序

D、直接插入排序

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

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

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

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

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

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

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

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

C、數(shù)據(jù)項(xiàng)

D、文件

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

過(guò)程中比較元素的順序?yàn)椋ǎ﹐

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、向一個(gè)棧頂指針為HS的鏈棧中將一個(gè)S指針?biāo)傅慕Y(jié)點(diǎn)入棧，執(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分）從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用x保存被刪結(jié)點(diǎn)的

值,則執(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、給定一個(gè)無(wú)序的單鏈表,要求的空間復(fù)雜度為0（1）,則建立一個(gè)長(zhǎng)度為n的

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

A、0（n）

B、0（1）

C、0（n、2）

D、0（log2n）

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

A、p->next==NULL

B、p==NULL

C、p->next==head

D>p==head

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

A、算法一定沒(méi)有輸出

B、算法可以沒(méi)有輸出

C、算法至少有一個(gè)輸出

D、算法必須有多個(gè)

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

除結(jié)點(diǎn)的值保存到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ì)算機(jī)程序

B、解決問(wèn)題的計(jì)算方法

C、排序算法

D、解決問(wèn)題的有限運(yùn)算序列

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

A、n2-2

B、n2-l

C、n2+l

D、n2+2

44、在單鏈表結(jié)點(diǎn)p之后插入結(jié)點(diǎn)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ù)組稱(chēng)為隨機(jī)存儲(chǔ)結(jié)構(gòu)是因?yàn)椋ǎ﹐

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

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

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

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

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

森林F對(duì)應(yīng)的二叉樹(shù)根節(jié)點(diǎn)的右子樹(shù)的個(gè)數(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)過(guò)（）次比較。

A、1

B、2

C、3

D、4

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

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

B、散鏈方式和索引方式

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

D、線(xiàn)性存儲(chǔ)結(jié)構(gòu)和非線(xiàn)性存儲(chǔ)結(jié)構(gòu)

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

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

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

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

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

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

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

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

C、數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類(lèi)型

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

參考答案及解析

一、單項(xiàng)選擇題

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

【解析】解釋?zhuān)簒=top->data將結(jié)點(diǎn)的值保存到x中，top=top->link棧頂指針指向棧頂

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

42、D

43、C

44、B

45、B

46、D

47、C

48、A

49、D

50、A

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

一、單項(xiàng)選擇題（100題）

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

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

A、a[-top]=x;

B、a[top--]=x

C、a[++top]=x

DNa[top++]=x

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

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

A、0（log2n）

B、0（1）

C、0（n）

D、0（rT2）

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

A、2

B、3

C、4

D、5

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

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

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

C、S->rear==0

D、s->front==0

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

A、dacb

B、abed

C、deba

D>cadb

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

50個(gè)元素,則隊(duì)列的尾指針值為（B）o

A、3

B、37

C,50

D、97

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

T2中結(jié)點(diǎn)的(B)。

A、前序

B、中序

C,后序

D、層序

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

A、0(n)

B、0(n2)

C、0(n/2)

D、0(log2n)

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

A、229

B、0.229

C、229E-2

D、"229”

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

()o

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

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

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

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

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

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

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

C、數(shù)據(jù)項(xiàng)

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

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

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

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

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

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

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

A、程序

B、問(wèn)題求解步驟的描述

C、要滿(mǎn)足五個(gè)基本特性

D、A和C.

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

A、單鏈表

B、順序表

C、循環(huán)鏈表

D、靜態(tài)鏈表

15、