奧鵬蘭大數(shù)據(jù)結(jié)構(gòu)19秋學(xué)期考試在線考核試題

1、正確答案:D一棵含有18個節(jié)點(diǎn)的二叉樹的高度至少為（）A. 3B. 4C. 5D. 6正確答案:C棧的插入和刪除操作在（）A.棧底B.任意位置C.棧頂D.指定位置正確答案:C以下不是棧的基本運(yùn)算的是（）A.刪除棧頂元素B.刪除棧底元素C.判斷棧是否為空D.將棧置為空棧正確答案:B設(shè)s 1= “GOOD,s2= BYE則字符串si和s2連接后的結(jié)果是A. BYE GOODB. GOOD BYEC. BYEDGOODD. GOODBYE當(dāng)在一個有序的順序存儲表上查找一個數(shù)據(jù)時， 即可用折半查找， 也可 用順序查找，但前者比后者的查找速度（）A.必定快B.不一定C.在大部分情況下要快D.取決于表遞增

2、還是遞減正確答案:C數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的？和運(yùn)算等的學(xué)科A.程序B.關(guān)系C.運(yùn)算D.算法正確答案:B設(shè)棧S T用存儲結(jié)構(gòu)表示，那么棧S T為空的條件為（）A. ST .top-ST .base v nST .top-base v 0B. ST .top-ST .base=0C. ST-top.base=n正確答案:C線性表的順序存儲結(jié)構(gòu)是一種（）A.隨機(jī)存取的存儲結(jié)構(gòu)B.順序存取的存儲結(jié)構(gòu)C.索引存取的存儲結(jié)構(gòu)正確答案:AD.散列存取的存儲結(jié)構(gòu)正確答案:An個結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（）A. 2nB. n-lC. nD. n + l正確

3、答案:C與線性表相比，串的插入和刪除操作的特點(diǎn)是（）A.通常以串整體作為操作對象B.需要更多的輔助空間C.算法的時間復(fù)雜度較高D.涉及移動的元素更多正確答案:A對于哈希函數(shù)，沖突只能盡可能得少，不可能完全避免A.錯誤B.正確正確答案:B隊(duì)列允許在隊(duì)尾刪除，在隊(duì)頭插入。（）A.正確B.錯誤正確答案:A帶權(quán)無向圖的最小生成樹是唯一的A.正確B.錯誤 正確答案:A滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）A.正確B.錯誤 正確答案:A一個強(qiáng)連通圖的連通分量只有一個。（）A.正確B.錯誤 正確答案:A（?？谱觯╄F路進(jìn)行列車調(diào)度時，常把站臺設(shè)計成棧式結(jié)構(gòu)的站臺，如 右圖所示。試問：（1）

4、設(shè)有編號為1,2,3,4,5,6的六輛列車，順序開入棧式結(jié)構(gòu)的 站臺，則可能的出棧序列有多少種？（2）試列舉出3個序列，并任選其一說明其進(jìn)出棧順序。正確答案：（1）可能的不同出棧序列有（他+ 1）*弗-種。（2）不能得到 435612和 154623這樣的出棧序列。因?yàn)槿粼?, 3, 5, 6之后再將 1,2出棧，則 1,2 必須一直在棧中，此時 1先進(jìn)棧，2 后進(jìn)棧，2應(yīng)壓在 1上面，不可能 1 先于 2 出棧。154623 也是這種情況。出棧序列325641和 135426可以得到。3-15將編號為 0 和 1 的兩個棧存放于一個數(shù)組空間Vm中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?0號棧的棧頂指

5、針 top0等于-1時該棧為空，當(dāng)?shù)?1號棧的棧頂指針 top1等于 m時該棧為空。兩個棧均從兩端向中間增長。當(dāng)向第0號棧插入一個新元素時，使 top0增 1得到新的棧頂位置，當(dāng)向第 1 號棧插入一個新元素時，使 top1減 1得到新的棧頂位置。當(dāng) top0+1 = top1時或 top0 =top1-1時，?？臻g滿，此時不能再向任一棧加入新的元素。試定義這種雙棧 (Double Stack)結(jié)構(gòu)的類定義，并實(shí)現(xiàn)判?？铡⑴袟M、插入、刪除算法。試比較順序存儲和鏈?zhǔn)酱鎯Φ膬?yōu)缺點(diǎn)正確答案：順序存儲查找效率高，插入和刪除效率低；鏈?zhǔn)酱鎯Σ迦牒?刪除效率高，查找效率低。簡述完全二叉樹與滿二叉樹的異同點(diǎn)

6、？已知二叉樹的深度為k0m-1正確答案:完全二叉樹的定義：深度為k,有n個結(jié)點(diǎn)的丑叉樹當(dāng)且僅當(dāng) 其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng) 時，稱為完全二叉樹。特點(diǎn)：葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；對任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l ,則其左分支下子孫的最大層次必為l或l+1。滿二叉樹：一棵深度為k,且有2的(k)次方-1個節(jié)點(diǎn)的二叉樹。特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。 滿 二叉樹肯定是完全二叉樹。完全二叉樹不一定是滿二叉樹。LI32BI32542131111I一325325325632564325641樹的路徑長度 正確答案:樹的路徑長度：從樹中一個結(jié)點(diǎn)到另一個