軟件設(shè)計師-數(shù)據(jù)結(jié)構(gòu)

精品文檔-下載后可編輯軟件設(shè)計師-數(shù)據(jù)結(jié)構(gòu)軟件設(shè)計師-數(shù)據(jù)結(jié)構(gòu)

1.【單選題】1分|若元素以a，b，c，d，e的順序進入一個初始為空的棧中，每個元素進棧、出棧各1次，要求出棧的第一個元素為d，則合法的出棧序列共有（57）種。

A4

B5

C6

D24

2.【單選題】1分|設(shè)某二叉樹采用二叉鏈表表示（即結(jié)點的兩個指針分別指示左、右孩子）。當該二叉樹包含k個節(jié)點時，其二叉鏈表節(jié)點中必有（59）個空的孩子指針。

Ak-1

BK

Ck+1

D2k

3.【單選題】1分|以下關(guān)于無向連通圖G的敘述中，不正確的是（60）。

AG中任意兩個頂點之間均有邊存在

BG中任意兩個頂點之間存在路徑

C從G中任意頂點出發(fā)可遍歷圖中所有頂點

DG的臨接矩陣是對稱矩陣

4.【單選題】1分|設(shè)有n階三對角矩陣A,即非零元素都位于主對角線以及與主對角線平行且緊鄰的兩條對角線上,現(xiàn)對該矩陣進行按行壓縮存儲,若其壓儲空間用數(shù)組B表示,A的元素下標從0開始,B的元素下標從1開始。已知A[0,0]存儲在B[1],A[n-1,n-1]存儲在B[3n-2],那么非零元素A[i,j](0≤i

A2i+j-1

B2i+j

C2i+j+1

D3i-j+1

5.【單選題】1分|對下面的二叉樹進行順序存儲(用數(shù)組MEM表示),已知結(jié)點A、B、C在MEM中對應(yīng)元素的下標分別為1、2、3,那么結(jié)點D、E、F對應(yīng)的數(shù)組元素下標為()。

A4、5、6

B4、7、10

C6、7、8

D6、7、14

6.【單選題】1分|用哈希表存儲元素時,需要進行沖突(碰撞)處理,沖突是指()。

A關(guān)鍵字被依次映射到地址編號連續(xù)的存儲位置

B關(guān)鍵字不同的元素被映射到相同的存儲位置

C關(guān)鍵字相同的元素被映射到不同的存儲位置

D關(guān)鍵字被映射到哈希表之外的位置

7.【單選題】1分|對有n個結(jié)點、e條邊且采用數(shù)組表示法(即鄰接矩陣存儲)的無向圖進行深度優(yōu)先遍歷,時間復雜度為()。

AO(n^2)

BO(e^2)

CO(n+e)

DO(n*e)

8.【單選題】1分|具有三個結(jié)點的二叉樹有五種，可推測出具有四個節(jié)點的二叉樹有（）種。

A10

B11

C14

D15

9.【單選題】1分|設(shè)散列函數(shù)為H（key）key%11對于關(guān)鍵礙序列(23,40,91,17,19,10,31,65,26),用線件探杳法解決沖突構(gòu)造的哈希表為()

A

B

C

D

10.【單選題】1分|對于有序表（8,15,19,23,26,31,40,65,91），用二分法進行查找時,可能的關(guān)鍵字比較順序為()。

A26,23,19

B26,8,19

C26，40,65

D26,31,40

11.【單選題】1分|若一棵二叉樹的高度（即層數(shù)）為h，則該二叉樹（）。

A有個結(jié)點

B有個結(jié)點

C最少有個結(jié)點

D最多有個結(jié)點

12.【單選題】1分|對于一個長度為n(n＞1)且元素互異的序列，令其所有元素依次通過一個初始為空的棧后，再通過一個初始為空的隊列。假設(shè)隊列和棧的容量都足夠大，且只要棧非空就可以進行出棧操作，只要隊列非空就可以進行出隊操作，那么以下敘述中，正確的是（）。

A出隊序列和出棧序列一定互為逆序

B出隊序列和出棧序列一定相同

C入棧序列與入隊序列一定相同

D入棧序列與入隊序列一定互為逆序

13.【單選題】1分|設(shè)有一個包含n個元素的有序線性表。在等概率情況下刪除其中的一個元素，若采用順序存儲結(jié)構(gòu)，則平均需要移動（請作答此空）個元素；若采用單鏈表存儲，則平均需要移動（）個元素。

A1

B(n-1)/2

CLogn

Dn

14.【單選題】1分|設(shè)有一個包含n個元素的有序線性表。在等概率情況下刪除其中的一個元素，若采用順序存儲結(jié)構(gòu)，則平均需要移動（）個元素；若采用單鏈表存儲，則平均需要移動（請作答此空）個元素。

A0

B1

C(n-1)/2

Dn/2

15.【單選題】1分|設(shè)某循環(huán)隊列Q的定義中有front和rear兩個域變量，其中，front指示隊頭元素的位置，rear指示隊尾元素之后的位置，如下圖所示。若該隊列的容量為M，則其長度為（