東大22年春學(xué)期《數(shù)據(jù)結(jié)構(gòu)ⅡX》在線平時(shí)作業(yè)1【標(biāo)準(zhǔn)答案】
試卷總分:100 得分:100
一、單選題 (共 20 道試題,共 100 分)
1.BFS算法可用來(lái)解決單源最短路徑問(wèn)題的條件是當(dāng)各邊上的權(quán)值
A.均相等
B.均互不相等
C.不一定相等
D.任意值
2.下列序列中，不構(gòu)成堆的是
A.（1，2，5，3，4，6，7，8，9，10）
B.（10，5，8，4，2，6，7，1，3）
C.（10，9，8，7，3，5，4，6，2）
D.（1，2，3，4，10，9，8，7，6，5）
3.若要在單鏈表中的結(jié)點(diǎn)p之后插入一個(gè)結(jié)點(diǎn)s，則應(yīng)執(zhí)行的語(yǔ)句是
A.s->next=p->next; p->next=s;
B.p->next=s; s->next=p->next;
C.p->next=s->next; s->next=p;
D.s->next=p; p->next=s->next;
4.若在9階B-樹中插入關(guān)鍵字引起結(jié)點(diǎn)分裂，則該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個(gè)數(shù)為
A.4
B.5
C.8
D.9
5.假設(shè)在構(gòu)建散列表時(shí)，采用線性探測(cè)解決沖突。若連續(xù)插入的n個(gè)關(guān)鍵字都是同義詞，則查找其中最后插入的關(guān)鍵字時(shí)，所需進(jìn)行的比較次數(shù)為
A.n-1
B.n
C.n+l
D.n+2
6.文件中，主關(guān)鍵字能唯一標(biāo)識(shí)
A.一個(gè)記錄
B.一組記錄
C.一個(gè)類型
D.一個(gè)文件
7.假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素。已知隊(duì)列的長(zhǎng)度為length，指針rear指向隊(duì)尾元素的下一個(gè)存儲(chǔ)位置，則隊(duì)頭元素所在的存儲(chǔ)位置為
A.(rear-length+m+1)％m
B.(rear-length+m)％m
C.(rear-length+m-1)％m
D.(rear-length)％m
8.設(shè)順序存儲(chǔ)的線性表共有123個(gè)元素，按分塊查找的要求等分成3塊。若對(duì)索引表采用順序查找來(lái)確定塊，并在確定的塊中進(jìn)行順序查找，則在查找概率相等的情況下，分塊查找成功時(shí)的平均查找長(zhǎng)度為
A.21
B.23
C.41
D.62
9.數(shù)據(jù)結(jié)構(gòu)中所定義的數(shù)據(jù)元素，是用于表示數(shù)據(jù)的
A.最小單位
B.最大單位
C.基本單位
D.不可分割的單位
10.對(duì)n個(gè)關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)雜度為
A.O(1)
B.O(logn)
C.O(n)
D.O(n logn)
11.若允許表達(dá)式內(nèi)多種括號(hào)混合嵌套，則為檢查表達(dá)式中括號(hào)是否正確配對(duì)的算法，通常選用的輔助結(jié)構(gòu)是
A.棧
B.線性表
C.隊(duì)列
D.二叉排序樹
12.下面關(guān)于數(shù)據(jù)結(jié)構(gòu)正確的說(shuō)法是
A.一種數(shù)據(jù)類型
B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
C.一組性質(zhì)相同的數(shù)據(jù)元素的集合
D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合
13.如果在數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素只可能有一個(gè)直接前驅(qū)，但可以有多個(gè)直接后繼，則該結(jié)構(gòu)是
A.棧
B.隊(duì)列
C.樹
D.圖
14.下面的說(shuō)法中正確的是
(1)任何一棵二叉樹的葉子節(jié)點(diǎn)在三種遍歷中的相對(duì)次序不變。
(2)按二叉樹定義，具有三個(gè)節(jié)點(diǎn)的二叉樹共有6種。
A.(1)，(2)
B.(1)
C.(2)
D.(1)，(2)都錯(cuò)
15.下列關(guān)鍵字序列中，構(gòu)成小根堆的是
A.{84，46，62，41，28，58，15，37}
B.{84，62，58，46，41，37，28，15}
C.{15，28，46，37，84，41，58，62}
D.{15，28，46，37，84，58，62，41}
16.設(shè)一個(gè)棧的輸入序列為12345，則借助一個(gè)棧所得到的輸出序列不可能是
A.23415
B.54132
C.23145
D.15432
17.對(duì)關(guān)鍵字序列（5，1，4，3，7，2，8，6）進(jìn)行快速排序時(shí)，以第一個(gè)元素5為基準(zhǔn)的一次劃分的結(jié)果為
A.（1，2，3，4，5，6，7，8）
B.（1，4，3，2，5，7，8，6）
C.（2，1，4，3，5，7，8，6）
D.（8，7，6，5，4，3，2，1）
18.在下列各種文件中，不能進(jìn)行順序查找的文件是
A.順序文件
B.索引文件
C.散列文件
D.多重表文件
19.若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上
A.操作的有限集合
B.映象的有限集合
C.類型的有限集合
D.關(guān)系的有限集合
20.引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是
A.出隊(duì)
B.入隊(duì)
C.取隊(duì)頭元素
D.取隊(duì)尾元素
