第八章試探題庫及答案

一、單項選擇題（每題2分，共10題）1.以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)優(yōu)先隊列？A.數(shù)組B.鏈表C.堆D.棧答案：C2.算法的時間復雜度是指？A.算法執(zhí)行過程中所需的時間B.算法所處理的數(shù)據(jù)量C.算法程序中的語句或指令條數(shù)D.算法在執(zhí)行過程中基本運算的執(zhí)行次數(shù)答案：D3.對一組數(shù)據(jù){5,1,9,3,7}進行排序，若采用冒泡排序，第一趟排序后結(jié)果是？A.{1,5,3,7,9}B.{1,5,9,3,7}C.{5,1,3,7,9}D.{1,5,7,3,9}答案：A4.線性表采用鏈式存儲時，其地址？A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以答案：D5.一棵二叉樹的前序遍歷序列為ABCDE，中序遍歷序列為CBDAE，則后序遍歷序列是？A.CDBEAB.CDBAEC.EDCBAD.CDEBA答案：A6.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的？A.1倍B.2倍C.3倍D.一半答案：A7.哈希表的平均查找長度與？A.哈希函數(shù)有關(guān)B.裝填因子有關(guān)C.哈希表的大小有關(guān)D.關(guān)鍵字個數(shù)有關(guān)答案：B8.棧和隊列的共同點是？A.都是先進先出B.都是先進后出C.只允許在端點處進行插入和刪除操作D.沒有共同點答案：C9.對于順序存儲的線性表，訪問第i個元素的時間復雜度為？A.O(1)B.O(n)C.O(logn)D.O(n2)答案：A10.快速排序在平均情況下的時間復雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)答案：B二、多項選擇題（每題2分，共10題）1.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有？A.棧B.隊列C.樹D.圖答案：AB2.排序算法中，時間復雜度為O(n2)的有？A.冒泡排序B.選擇排序C.插入排序D.歸并排序答案：ABC3.關(guān)于二叉樹的性質(zhì)，正確的有？A.度為0的結(jié)點比度為2的結(jié)點多1個B.第i層最多有2^(i-1)個結(jié)點C.深度為k的二叉樹最多有2^k-1個結(jié)點D.二叉樹一定是完全二叉樹答案：ABC4.以下哪些是圖的存儲結(jié)構(gòu)？A.鄰接矩陣B.鄰接表C.十字鏈表D.順序表答案：ABC5.以下哪些操作是棧支持的？A.入棧B.出棧C.取棧頂元素D.查找棧中任意元素答案：ABC6.屬于查找算法的有？A.順序查找B.二分查找C.哈希查找D.插入排序（可用于查找）答案：ABC7.影響算法時間復雜度的因素有？A.問題規(guī)模B.算法采用的策略C.計算機硬件性能D.編程語言答案：AB8.以下關(guān)于隊列的描述，正確的有？A.先進先出B.可以用數(shù)組實現(xiàn)C.可以用鏈表實現(xiàn)D.隊頭刪除元素，隊尾插入元素答案：ABCD9.樹的遍歷方式有？A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷答案：ABCD10.以下關(guān)于哈希表的說法，正確的有？A.哈希函數(shù)要盡量均勻地將關(guān)鍵字映射到哈希表中B.哈希表可以減少查找時間C.沖突是不可避免的D.開放定址法和鏈地址法是解決沖突的常見方法答案：ABCD三、判斷題（每題2分，共10題）1.線性表的順序存儲結(jié)構(gòu)比鏈式存儲結(jié)構(gòu)更節(jié)省存儲空間。（）答案：×2.冒泡排序是一種穩(wěn)定的排序算法。（）答案：√3.一棵完全二叉樹的葉子結(jié)點一定在最后一層。（）答案：×4.圖的深度優(yōu)先搜索遍歷類似于樹的前序遍歷。（）答案：√5.?？梢杂脕頇z查表達式中的括號是否匹配。（）答案：√6.哈希表中，裝填因子越大，發(fā)生沖突的可能性越小。（）答案：×7.插入排序在數(shù)據(jù)基本有序的情況下效率較高。（）答案：√8.隊列的刪除操作在隊頭進行。（）答案：√9.二叉排序樹的中序遍歷序列是有序的。（）答案：√10.算法的空間復雜度是指算法執(zhí)行過程中所需的臨時存儲空間。（）答案：×四、簡答題（每題5分，共4題）1.簡述棧和隊列的主要區(qū)別。答案：棧是先進后出的數(shù)據(jù)結(jié)構(gòu)，所有操作在棧頂進行；隊列是先進先出的數(shù)據(jù)結(jié)構(gòu)，插入操作在隊尾，刪除操作在隊頭。2.簡述二分查找的基本思想。答案：二分查找針對有序數(shù)組。每次將查找區(qū)間分成兩部分，通過比較關(guān)鍵字與中間元素大小，確定在左半?yún)^(qū)還是右半?yún)^(qū)繼續(xù)查找，直到找到關(guān)鍵字或確定不存在。3.簡述圖的鄰接矩陣存儲結(jié)構(gòu)的優(yōu)缺點。答案：優(yōu)點是簡單直觀，便于判斷頂點間是否有邊；缺點是存儲空間大，對于稀疏圖會浪費大量空間，添加和刪除邊操作效率低。4.簡述二叉樹的性質(zhì)（至少兩條）。答案：度為0的結(jié)點比度為2的結(jié)點多1個；第i層最多有2^(i-1)個結(jié)點；深度為k的二叉樹最多有2^k-1個結(jié)點。五、討論題（每題5分，共4題）1.在實際應用中，如何選擇合適的排序算法？答案：數(shù)據(jù)量小且基本有序時，可選插入排序；數(shù)據(jù)量小但無序，冒泡排序或選擇排序可考慮。數(shù)據(jù)量大時，平均性能好的快速排序較優(yōu)，若要穩(wěn)定性則選歸并排序。對空間要求高且數(shù)據(jù)范圍小，計數(shù)排序等可能合適。2.討論哈希表在解決沖突時開放定址法和鏈地址法的優(yōu)劣。答案：開放定址法優(yōu)點是不用額外指針空間緊湊，缺點是易產(chǎn)生聚集現(xiàn)象影響查找效率；鏈地址法優(yōu)點是不易聚集，刪除操作方便，缺點是需要額外指針空間，對大量數(shù)據(jù)可能鏈過長影響性能。3.分析樹和圖這兩種數(shù)據(jù)結(jié)構(gòu)在實際應用中的場景差異。答案：樹結(jié)構(gòu)適用于具有層次關(guān)系的數(shù)據(jù)，如文件系統(tǒng)目錄、家族樹等；圖結(jié)構(gòu)用于表示多對多關(guān)系，如