東大22年春學(xué)期《數(shù)據(jù)結(jié)構(gòu)ⅡX》在線平時作業(yè)1【標(biāo)準(zhǔn)答案】
試卷總分:100 得分:100
一、單選題 (共 20 道試題,共 100 分)
1.用二叉鏈表表示具有n個結(jié)點(diǎn)的二叉樹時，值為空的指針域的個數(shù)為
A.n-1
B.n
C.n+l
D.2n
2.已知含10個結(jié)點(diǎn)的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于
A.1.0
B.2.9
C.3.4
D.5.5
3.對長度為n的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為
A.O（log2n）
B.O（1）
C.O（n）
D.O（n*log2n）
4.已知含6個頂點(diǎn)(v0，v1，v2，v3，v4，v5)的無向圖的鄰接矩陣如圖所示，則從頂點(diǎn)v0出發(fā)進(jìn)行深度優(yōu)先遍歷可能得到的頂點(diǎn)訪問序列為
A..(v0，v1，v2，v5，v4，v3)
B.(v0，v1，v2，v3，v4，v5)
C.(v0，v1，v5，v2，v3，v4)
D..(v0，v1，v4，v5，v2，v3)
5.n個頂點(diǎn)的有向完全圖中含有向邊的數(shù)目最多為
A.n-1
B.n
C.n(n-1)/2
D.n(n-1)
6.在以單鏈表為存儲結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用
A.數(shù)據(jù)元素的相鄰地址表示
B.數(shù)據(jù)元素在表中的序號表示
C.指向后繼元素的指針表示
D.數(shù)據(jù)元素的值表示
7.倒排文件的主要優(yōu)點(diǎn)是
A.便于進(jìn)行插入和刪除運(yùn)算
B.便于進(jìn)行文件的恢復(fù)
C.便于進(jìn)行多關(guān)鍵字查詢
D.節(jié)省存儲空間
8.已知二叉樹的先序序列為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ì)列的存儲空間為數(shù)組data[21]，且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為8和3，則該隊(duì)列的當(dāng)前長度為
A.5
B.6
C.16
D.17
11.一棵具有 n個結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是
A.ëlognû+1
B.logn+1
C.ëlognû
D.logn-1
12.在圖采用鄰接表存儲時，求最小生成樹的 Prim 算法的時間復(fù)雜度為
A.O(n)
B.O(n+e)
C.O(n2)
D.O(n3)
13.已知廣義表LS=((a，b，c)，(d，e，f))，運(yùn)算head和tail函數(shù)取出元素e的運(yùn)算是
A.head(tail(LS))
B.tail(head(LS))
C.head(tail(head(tail(LS))))
D.head(tail(tail(head(LS))))
14.稠密索引是在索引表中
A.為每個記錄建立一個索引項(xiàng)
B.為每個頁塊建立一個索引項(xiàng)
C.為每組記錄建立一個索引項(xiàng)
D.為每個字段建立一個索引項(xiàng)
15.如果求一個連通圖中以某個頂點(diǎn)為根的高度最小的生成樹，應(yīng)采用
A.深度優(yōu)先搜索算法
B.廣度優(yōu)先搜索算法
C.求最小生成樹的prim算法
D.拓?fù)渑判蛩惴?/p>
16.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)
A.存儲密度大
B.插入運(yùn)算方便
C.刪除運(yùn)算方便
D.可方便地用于各種邏輯結(jié)構(gòu)的存儲表示
17.判定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是
A.Q.front==NULL
B.Q.rear==NULL
C.Q.front==Q.rear
D.Q.front!=Q.rear
18.下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是
A.棧
B.隊(duì)列
C.完全二叉樹
D.堆
19.二維數(shù)組A按行優(yōu)先順序存儲，其中每個元素占1個存儲單元。若A［1］［1］的存儲地址為420，A［3］［3］的存儲地址為446，則A［5］［5］的存儲地址為
A.470
B.471
C.472
D.473
20.一棵完全二叉樹上有1001個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是
A.250
B.500
C.254
D.以上答案都不對
