408考試真題及答案

一、單項選擇題（每題2分，共10題）1.下列排序算法中，平均時間復(fù)雜度最小的是（）A.冒泡排序B.選擇排序C.插入排序D.快速排序2.線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，其地址（）A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以3.一個棧的入棧序列為1,2,3,4,5，則不可能的出棧序列是（）A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,54.若一棵完全二叉樹有768個結(jié)點，則該二叉樹中葉結(jié)點的個數(shù)是（）A.257B.258C.384D.3855.對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)6.具有n個頂點的有向圖最多有（）條邊。A.n(n-1)B.n(n+1)C.n(n-1)/2D.n(n+1)/27.順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。A.順序存儲B.鏈?zhǔn)酱鎯.順序存儲或鏈?zhǔn)酱鎯.索引存儲8.設(shè)森林F中有三棵樹，第一、第二、第三棵樹的結(jié)點個數(shù)分別為M1、M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（）A.M1B.M1+M2C.M2+M3D.M39.若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用（）存儲方式最節(jié)省時間。A.單鏈表B.雙鏈表C.帶頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表10.哈希表的平均查找長度（）A.與處理沖突方法有關(guān)而與表的長度無關(guān)B.與處理沖突方法無關(guān)而與表的長度有關(guān)C.與處理沖突方法有關(guān)且與表的長度有關(guān)D.與處理沖突方法無關(guān)且與表的長度無關(guān)二、多項選擇題（每題2分，共10題）1.以下屬于數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)的有（）A.線性結(jié)構(gòu)B.樹形結(jié)構(gòu)C.圖形結(jié)構(gòu)D.順序結(jié)構(gòu)2.下列排序算法中，穩(wěn)定的排序算法有（）A.冒泡排序B.歸并排序C.基數(shù)排序D.堆排序3.以下關(guān)于棧的描述正確的有（）A.棧是一種先進后出的線性表B.棧的插入和刪除操作都在棧頂進行C.?？梢宰鳛閷崿F(xiàn)遞歸調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)D.順序棧和鏈棧在操作性能上沒有區(qū)別4.完全二叉樹的特點包括（）A.葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)B.對任一結(jié)點，如果其右子樹的深度為d，則其左子樹的深度必為d或d+1C.每個結(jié)點的度要么為0，要么為2D.若有度為1的結(jié)點，則該結(jié)點只有左孩子5.下列關(guān)于圖的說法正確的是（）A.無向圖的鄰接矩陣一定是對稱矩陣B.有向圖的鄰接表表示中，頂點v的出邊表中的邊結(jié)點個數(shù)就是v的出度C.圖的廣度優(yōu)先搜索遍歷類似于樹的層次遍歷D.任何一個連通圖的生成樹是該圖的一個極小連通子圖6.以下哪些操作可以在鏈表上高效實現(xiàn)（）A.插入元素B.刪除元素C.隨機訪問元素D.查找特定元素7.哈希函數(shù)的設(shè)計原則包括（）A.均勻性B.簡單性C.唯一性D.隨機性8.下列關(guān)于堆的描述正確的有（）A.大頂堆中每個結(jié)點的值都大于或等于其子結(jié)點的值B.小頂堆可以用于實現(xiàn)優(yōu)先隊列C.堆排序是一種不穩(wěn)定的排序算法D.堆的插入操作平均時間復(fù)雜度為O(logn)9.以下屬于查找算法的有（）A.二分查找B.插值查找C.斐波那契查找D.平衡二叉樹查找10.以下關(guān)于樹和二叉樹的轉(zhuǎn)換說法正確的是（）A.任何一棵樹都可以唯一地轉(zhuǎn)換為一棵二叉樹B.樹轉(zhuǎn)換為二叉樹后，其根結(jié)點的右子樹必為空C.二叉樹轉(zhuǎn)換為樹時，二叉樹中某結(jié)點是其雙親的左孩子，則把該結(jié)點的右孩子、右孩子的右孩子……都與該結(jié)點的雙親結(jié)點用線連起來D.樹和二叉樹的轉(zhuǎn)換不改變結(jié)點間的相對層次關(guān)系三、判斷題（每題2分，共10題）1.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)的存儲結(jié)構(gòu)是一一對應(yīng)的。（）2.線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更節(jié)省存儲空間。（）3.隊列是一種先進先出的線性表，其插入操作在隊頭進行，刪除操作在隊尾進行。（）4.二叉樹的前序遍歷和中序遍歷可以唯一確定一棵二叉樹。（）5.圖的深度優(yōu)先搜索遍歷序列唯一。（）6.快速排序在最壞情況下的時間復(fù)雜度為O(n^2)。（）7.哈希表中，裝填因子越大，發(fā)生沖突的可能性越小。（）8.平衡二叉樹的左右兩個子樹的高度差的絕對值不超過1。（）9.堆是一種完全二叉樹。（）10.插入排序是一種穩(wěn)定的排序算法。（）四、簡答題（每題5分，共4題）1.簡述棧和隊列的區(qū)別。-棧是先進后出，插入和刪除都在棧頂進行；隊列是先進先出，插入在隊尾，刪除在隊頭。二者操作規(guī)則不同。2.簡述圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)的優(yōu)缺點。-鄰接矩陣優(yōu)點：直觀、容易實現(xiàn)，判斷兩頂點間有無邊時間復(fù)雜度為O(1)；缺點：空間復(fù)雜度高，O(n^2)。鄰接表優(yōu)點：節(jié)省空間，適合稀疏圖；缺點：判斷兩頂點間有無邊較復(fù)雜，時間復(fù)雜度高。3.簡述快速排序的基本思想。-選擇一個基準(zhǔn)值，通過一趟排序?qū)⒋庞涗浄指舫蓛刹糠?，使得左邊部分記錄的值均小于等于基?zhǔn)值，右邊部分記錄的值均大于等于基準(zhǔn)值，然后分別對這兩部分繼續(xù)進行排序，直到整個數(shù)組有序。4.簡述二叉排序樹的性質(zhì)。-若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；它的左、右子樹也分別為二叉排序樹。五、討論題（每題5分，共4題）1.討論在實際應(yīng)用中如何選擇合適的數(shù)據(jù)結(jié)構(gòu)。-需考慮數(shù)據(jù)的操作特點，如頻繁插入刪除選鏈表；頻繁隨機訪問選數(shù)組。還要考慮數(shù)據(jù)量大小、內(nèi)存限制等。如數(shù)據(jù)量小且操作簡單，簡單數(shù)組可能合適；數(shù)據(jù)復(fù)雜量大，可能需更復(fù)雜結(jié)構(gòu)如哈希表、平衡樹等。2.討論排序算法在不同場景下的應(yīng)用。-數(shù)據(jù)量小且基本有序，插入排序或冒泡排序合適；數(shù)據(jù)量較大且要求平均性能好，快速排序常用；對穩(wěn)定性有要求，歸并排序或基數(shù)排序可選；若要維護一個有序集合且動態(tài)插入刪除，堆排序或平衡樹相關(guān)排序更優(yōu)。3.討論哈希表在處理沖突時不同方法的優(yōu)缺點。-開放定址法優(yōu)點是簡單直觀，缺點是容易產(chǎn)生聚集現(xiàn)象，影響查找效率；鏈地址法優(yōu)點是沖突處理簡單，不易產(chǎn)生聚集，缺點是指針增加了額外空間開銷。具體選擇需依實際情況，如對空間敏感可選開放定址法，對查找效率要求高可選鏈地址法。4.討論樹和二叉樹在不同領(lǐng)域的應(yīng)用。-樹在文件系統(tǒng)目錄結(jié)構(gòu)、家族族譜等領(lǐng)域應(yīng)用廣泛，體現(xiàn)層次關(guān)系。二叉樹在排序算法（二叉排序樹）、哈夫曼編碼等方面應(yīng)用多，其結(jié)構(gòu)特點便于實現(xiàn)高效的查找、編碼等操作。答案一、單項選擇題1.D2.D3.C4.C5.C6.A7.C8.C9.