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