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

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

2、. 在大部分情況下要快D.取決于表遞增還是遞減正確答案 :C數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值的程序設計問題中計算機的操作對象以及它們之間的?和運算等的學科A. 程序B. 關(guān)系C. 運算D.算法正確答案 :B設棧S T用存儲結(jié)構(gòu)表示，那么棧S T為空的條件為 （）A.ST .top-ST .base < > nST .top-base < > 0B.ST .top-ST .base=0C.ST-top.base=n正確答案 :C線性表的順序存儲結(jié)構(gòu)是一種()A. 隨機存取的存儲結(jié)構(gòu)B. 順序存取的存儲結(jié)構(gòu)C. 索引存取的存儲結(jié)構(gòu)D.散列存取的存儲結(jié)構(gòu)正確答案 :A正確答案 :An

3、 個結(jié)點的線索二叉樹上含有的線索數(shù)為（）A.2nB.n lC.nD.n l正確答案 :C與線性表相比，串的插入和刪除操作的特點是（）A. 通常以串整體作為操作對象B. 需要更多的輔助空間C. 算法的時間復雜度較高D.涉及移動的元素更多正確答案 :A對于哈希函數(shù)，沖突只能盡可能得少，不可能完全避免A. 錯誤B. 正確正確答案 :B隊列允許在隊尾刪除，在隊頭插入。（）A. 正確B. 錯誤帶權(quán)無向圖的最小生成樹是唯一的。（）A.正確B.錯誤正確答案:A滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）A.正確B.錯誤正確答案:A一個強連通圖的連通分量只有一個。（）A.正確B.錯誤正確答案:A

4、（?？谱觯╄F路進行列車調(diào)度時,常把站臺設計成棧式結(jié)構(gòu)的站臺，如 右圖所不。試問：（1）設有編號為1,2,3,4,5,6的六輛列車，順序開入棧式結(jié)構(gòu)的站臺，則可能的出棧序列有多少種？（2）試列舉出3個序列，并任選其一說明其進出棧順序。正確答案：（i）可能的不同出棧序列有0K"亦免，132種。（2）不能彳#到435612和154623這樣的出棧序列。因為若在4, 3, 5, 6之后再將1,2出棧，則1,2必須一直在棧中，此日1先進棧，2后進棧，2應壓在1上面，不可能1先于2出棧。154623 也是這種情況。出棧序列 325641和135426可以得到。54213工32工工工工匚32532

5、53256325643256413-15將編號為0和1的兩個棧存放于一個數(shù)組空間Vm中，棧底分別處于數(shù)組的兩端。當?shù)?0號棧的棧頂指針top等于-1時該棧為空，當?shù)?號棧的棧頂指針top1等于m時該棧為空。兩個棧均從兩端向中間增長。當向第 0號棧插入一個新元素時，使 top0增1得到新的棧頂位 置，當向第1號棧插入一個新元素時，使 top1減1得到新的棧頂位置。當 top0+1 = top1 時或top0 = top1-1時，棧空間滿，此時不能再向任一棧加入新的元素。試定義這種雙棧 (Double Stack)結(jié)構(gòu)的類定義，并實現(xiàn)判棧空、判棧滿、插入、刪除算法。試比較順序存儲和鏈式存儲的優(yōu)缺點

6、正確答案：順序存儲查找效率高，插入和刪除效率低；鏈式存儲插入和 刪除效率高，查找效率低。簡述完全二叉樹與滿二叉樹的異同點？已知二叉樹的深度為k0m-1正確答案：完全上叉樹的定義：深度為k,有n個結(jié)點的二叉樹當且僅當 其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應 時，稱為完全二叉樹。特點：葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)；對任一結(jié)點，若其右分支下子孫的最大層次為l ,則其左分支下子孫的最大層次必為l或l+1。滿二叉樹：一棵深度為k,且有2的(k) 次方-1個節(jié)點的二叉樹。特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)。滿二叉樹肯定是完全二叉樹。完全二叉樹不一定是滿二叉樹。樹的路徑長度正確答案 : 樹的路徑長度：從樹中一個結(jié)點到另一