22春季東北大學(xué)《數(shù)據(jù)結(jié)構(gòu)Ⅱ》在線平時作業(yè)1-1

【奧鵬】數(shù)據(jù)結(jié)構(gòu)n-［東北大學(xué)］《數(shù)據(jù)結(jié)構(gòu)II》在線平時作業(yè)1

試卷總分：100得分：100

第1題,用二叉鏈表表示具有n個結(jié)點的二叉樹時值為空的指針域的個數(shù)為

A、n-1

B、n

C、n+1

D、2n

正確答案:C

第2題，已知含10個結(jié)點的二叉排序樹是一棵完全二叉樹則該二叉排序樹在等概率情況下查

找成功的平均查找長度等于

A、1.0

B、2.9

C、3.4

D、5.5

正確答案:B

第3題,對長度為n的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為

A、0(log2n)

B、0⑴

C、0(n)

D>0(n*log2n)

正確答案:B

第4題，已知含6個頂點v0vlv2v3v4v5的無向圖的鄰接矩陣如圖所示則從頂點v0出發(fā)進(jìn)行深

度優(yōu)先遍歷可能得到的頂點訪問序列為

A>.(v0,vl,v2,v5,v4,v3)

B、(vO,vl,v2,v3,v4,v5)

C、(vO,vl,v5,v2,v3,v4)

D>.(vO,vl,v4,v5,v2,v3)

正確答案：

第5題,n個頂點的有向完全圖中含有向邊的數(shù)目最多為

A、n-1

B、n

C、n(n-l)/2

D、n(n-l)

正確答案:D

第6題,在以單鏈表為存儲結(jié)構(gòu)的線性表中數(shù)據(jù)元素之間的邏輯關(guān)系用

A、數(shù)據(jù)元素的相鄰地址表示

B、數(shù)據(jù)元素在表中的序號表示

C、指向后繼元素的指針表示

D、數(shù)據(jù)元素的值表示

正確答案:C

第7題，倒排文件的主要優(yōu)點是

A、便于進(jìn)行插入和刪除運(yùn)算

B、便于進(jìn)行文件的恢復(fù)

C、便于進(jìn)行多關(guān)鍵字查詢

D、節(jié)省存儲空間

正確答案:C

第8題，已知二叉樹的先序序列為ABDECF中序序列為DBEAFC則后序序列為

A、DEBAFC

B、DEFBCA

C、DEBCFA

D、DEBFCA

正確答案：

第9題，若以1234作為雙端隊列的輸入序列則既不能由輸入受限的雙端隊列得到也不能由輸

出受限的雙端隊列得到的輸出序列是

A、1234

B、4132

C、4231

D、4213

正確答案:

第10題，已知循環(huán)隊列的存儲空間為數(shù)組data[21]且當(dāng)前隊列的頭指針和尾指針的值分別為

8和3則該隊列的當(dāng)前長度為

A、5

B、6

C、16

D、17

正確答案:C

第11題，一棵具有n個結(jié)點的完全二叉樹的樹高度深度是

A、elognu+1

B>logn+1

C、elognu

D、logn-1

正確答案:A

第12題,在圖采用鄰接表存儲時求最小生成樹的Prim算法的時間復(fù)雜度為

A、0(n)

B、0(n+e)

C、0(n2)

D、0(n3)

正確答案：

第13題，已知廣義表LS=abcdef運(yùn)算head和tail函數(shù)取出元素e的運(yùn)算是

A、head(tail(LS))

B、tail(head(LS))

C>head(tai1(head(tai1(LS))))

D、head(tai1(tai1(head(LS))))

正確答案：

第14題，稠密索引是在索引表中

A、為每個記錄建立一個索引項

B、為每個頁塊建立一個索引項

C、為每組記錄建立一個索引項

D、為每個字段建立一個索引項

正確答案:A

第15題,如果求一個連通圖中以某個頂點為根的高度最小的生成樹應(yīng)采用

A、深度優(yōu)先搜索算法

B、廣度優(yōu)先搜索算法

C、求最小生成樹的prim算法

D、拓?fù)渑判蛩惴?/p>

正確答案:B

第16題,下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點

A、存儲密度大

B、插入運(yùn)算方便

C、刪除運(yùn)算方便

D、可方便地用于各種邏輯結(jié)構(gòu)的存儲表示

正確答案:C

第17題，判定“帶頭結(jié)點的鏈隊列為空”的條件是

A、Q.front==NULL

B、Q.rear二二NULL

C、Q.front=Q.rear

D、Q.front!=Q.rear

正確答案:c

第18題,下列數(shù)據(jù)結(jié)構(gòu)中屬于非線性數(shù)據(jù)結(jié)構(gòu)的是

A、棧

B、隊列

C、完全二叉樹

D、堆

正確答案：

第19題，二維數(shù)組A按行優(yōu)先順序存儲其中每個元素占1個存儲單元若A[1][1]的存儲地

址為420A[3][3]的存儲地址為446則A[5][5