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