【奧鵬】南開大學(xué)21秋學(xué)期《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)4

1、【奧鵬】南開大學(xué) 21 秋學(xué)期《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)試卷總分:100 得分:100一、單選題 (共 30 道試題,共 60 分)1.不含任何結(jié)點(diǎn)的空樹（）A.是一棵樹B.是一棵二叉樹C.是一棵樹也是一棵二叉樹D.既不是樹也不是二叉樹答案:C2.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn) 0 出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）{圖}A.0 1 3 2B.0 2 3 1C.0 3 2 1D.0 1 2 3答案:D3.設(shè)串 s1=’ABC

2、DEFG’ ，s2=’PQRST’ ，函數(shù) con(x,y)返回 x 和 y 串的連接串，subs(s, i, j)返回串 s 的從序號(hào) i 開始的 j 個(gè)字符組成的子串，len(s)返回串 s 的長(zhǎng)度，則 con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的結(jié)果串是（）A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF答案:D4.對(duì)ｎ個(gè)不同的排序碼進(jìn)行冒泡排序，在下列哪種情

3、況下比較的次數(shù)最多。()A.從小到大排列好的B.從大到小排列好的C.元素?zé)o序D.元素基本有序答案:B5.有 8 個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有（）條邊A.5B.6C.7D.8答案:C6.對(duì)有 n 個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是()12.鏈表適用于()查找A.順序B.二分法C.順序，也能二分法D.隨機(jī)答案:A13.有 8 個(gè)結(jié)點(diǎn)的有向完全圖有（）條邊A.14B.28C.56D.112答案:C14.快速排序在下列哪種情況下

4、最易發(fā)揮其長(zhǎng)處()A.被排序的數(shù)據(jù)中含有多個(gè)相同排序碼B.被排序的數(shù)據(jù)已基本有序C.被排序的數(shù)據(jù)完全無(wú)序D.被排序的數(shù)據(jù)中的最大值和最小值相差懸殊答案:C15.折半查找有序表（4，6，10，12，20，30，50，70，88，100） 。若查找表中元素 58，則它將依次與表中()比較大小，查找結(jié)果是失敗。A.20，70，30，50B.30，88，70，50C.20，50D.30，88，50答案:A16.在表長(zhǎng)為ｎ的鏈表中進(jìn)行線性查找，它