東大22年春學期《數(shù)據(jù)結(jié)構(gòu)ⅡX》在線平時作業(yè)3【標準答案】
試卷總分:100 得分:100
一、單選題 (共 20 道試題,共 100 分)
1.在待排關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是
A.直接插入排序
B.快速排序
C.直接選擇排序
D.歸并排序
2.一個具有1025個結(jié)點的二叉樹的高h為
A.11
B.10
C.11至1025之間
D.10至1024之間
3.已知含10個結(jié)點的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于
A.1.0
B.2.9
C.3.4
D.5.5
4.一棵樹高為K的完全二叉樹至少的結(jié)點是
A.2k –1
B.2k-1 –1
C.2k-1
D.2k
5.在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是
A.插入
B.刪除
C.排序
D.查找
6.有關(guān)二叉樹下列說法正確的是
A.二叉樹的度為2
B.一棵二叉樹的度可以小于2
C.二叉樹中至少有一個結(jié)點的度為2
D.二叉樹中任何一個結(jié)點的度都為2
7.若要在O(1)的時間復雜度上實現(xiàn)兩個循環(huán)鏈表頭尾相接，則應對兩個循環(huán)鏈表各設(shè)置一個指針，分別指向
A.各自的頭結(jié)點
B.各自的尾結(jié)點
C.各自的第一個元素結(jié)點
D.一個表的頭結(jié)點，另一個表的尾結(jié)點
8.對長度為n的關(guān)鍵字序列進行堆排序的空間復雜度為
A.O（log2n）
B.O（1）
C.O（n）
D.O（n*log2n）
9.多維數(shù)組之所以有行優(yōu)先順序和列優(yōu)先順序兩種存儲方式是因為
A.數(shù)組的元素處在行和列兩個關(guān)系中
B.數(shù)組的元素必須從左到右順序排列
C.數(shù)組的元素之間存在次序關(guān)系
D.數(shù)組是多維結(jié)構(gòu)，內(nèi)存是一維結(jié)構(gòu)
10.對n個關(guān)鍵字的序列進行快速排序，平均情況下的空間復雜度為
A.O(1)
B.O(logn)
C.O(n)
D.O(n logn)
11.在一個單鏈表中，若刪除*p結(jié)點的后繼結(jié)點，則執(zhí)行操作
A.q=p->next;p->next=q->next;free(q);
B.p=p->next;p->next=p->next->next;free(p);
C.p->next=q->next;free(p->next);
D.p=p->next->next;free(p->next);
12.為便于判別有向圖中是否存在回路，可借助于
A.廣度優(yōu)先搜索算法
B.最小生成樹算法
C.最短路徑算法
D.拓撲排序算法
13.連通圖是指圖中任意兩個頂點之間
A.都連通的無向圖
B.都不連通的無向圖
C.都連通的有向圖
D.都不連通的有向圖
14.能進行二分查找的線性表,必須以
A.順序方式存儲,且元素按關(guān)鍵字有序
B.鏈式方式存儲,且元素按關(guān)鍵字有序
C.順序方式存儲,且元素按關(guān)鍵字分塊有序
D.鏈式方式存儲,且元素按關(guān)鍵字分塊有序
15.二維數(shù)組A的每個元素是由6個字符組成的串，其行下標i=0，l，…，8，列下標為j=1，2．…．10。設(shè)每個字符占一個字節(jié),若按行先存儲，元素A[8，5]的起始地址與A按列存儲時起始地址相同的元素是
A.A[8，5]
B.A[3，10]
C.A[5，8]
D.A[0，9]
16.下面的說法中正確的是
(1)任何一棵二叉樹的葉子節(jié)點在三種遍歷中的相對次序不變。
(2)按二叉樹定義，具有三個節(jié)點的二叉樹共有6種。
A.(1)，(2)
B.(1)
C.(2)
D.(1)，(2)都錯
17.以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是
A.循環(huán)隊列
B.鏈表
C.哈希表
D.棧
18.如果求一個連通圖中以某個頂點為根的高度最小的生成樹，應采用
A.深度優(yōu)先搜索算法
B.廣度優(yōu)先搜索算法
C.求最小生成樹的prim算法
D.拓撲排序算法
19.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復雜度為
A.O(0)
B.O(1)
C.O(n)
D.O(n2)
20.在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并使鏈表仍然有序的時間復雜度是
A.O(1)
B.O(n)
C.O(nlogn)
D.O(n2)
