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

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

試卷總分：100得分：100

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

A、n-1

B、n

C、n+1

D、2n

正確答案:C

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

找成功的平均查找長(zhǎng)度等于

A、1.0

B、2.9

C、3.4

D、5.5

正確答案:B

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

A、0(log2n)

B、0⑴

C、0(n)

D>0(n*log2n)

正確答案:B

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

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

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個(gè)頂點(diǎn)的有向完全圖中含有向邊的數(shù)目最多為

A、n-1

B、n

C、n(n-l)/2

D、n(n-l)

正確答案:D

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

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

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

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

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

正確答案:C

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

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

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

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

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

正確答案:C

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

A、DEBAFC

B、DEFBCA

C、DEBCFA

D、DEBFCA

正確答案：

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

出受限的雙端隊(duì)列得到的輸出序列是

A、1234

B、4132

C、4231

D、4213

正確答案:

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

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

A、5

B、6

C、16

D、17

正確答案:C

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

A、elognu+1

B>logn+1

C、elognu

D、logn-1

正確答案:A

第12題,在圖采用鄰接表存儲(chǔ)時(shí)求最小生成樹(shù)的Prim算法的時(shí)間復(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、為每個(gè)記錄建立一個(gè)索引項(xiàng)

B、為每個(gè)頁(yè)塊建立一個(gè)索引項(xiàng)

C、為每組記錄建立一個(gè)索引項(xiàng)

D、為每個(gè)字段建立一個(gè)索引項(xiàng)

正確答案:A

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

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

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

C、求最小生成樹(shù)的prim算法

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

正確答案:B

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

A、存儲(chǔ)密度大

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

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

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

正確答案:C

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

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、隊(duì)列

C、完全二叉樹(shù)

D、堆

正確答案：

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

址為420A[3][3]的存儲(chǔ)地址為446則A[5][5