數(shù)據(jù)結(jié)構(gòu)考試題及答案

一、單項(xiàng)選擇題（每題2分，共10題）1.線性表采用順序存儲結(jié)構(gòu)，訪問第i個元素的時(shí)間復(fù)雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n2)2.棧的操作特性是（）A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.都不對3.一個隊(duì)列的入隊(duì)序列是1,2,3,4，則隊(duì)列的輸出序列是（）A.4,3,2,1B.1,2,3,4C.3,2,1,4D.1,4,2,34.具有n個節(jié)點(diǎn)的完全二叉樹的深度為（）A.log?nB.log?n+1C.?log?n?+1D.?log?n?+15.對一組數(shù)據(jù)(84,47,25,15,21)排序，數(shù)據(jù)的排列次序在排序的過程中的變化為(1)8447251521(2)1547258421(3)1521258447(4)1521254784，則采用的排序方法是（）A.選擇排序B.冒泡排序C.插入排序D.快速排序6.圖的深度優(yōu)先遍歷類似于樹的（）A.層次遍歷B.先序遍歷C.中序遍歷D.后序遍歷7.在一個單鏈表中，若要刪除p節(jié)點(diǎn)的后繼節(jié)點(diǎn)，則執(zhí)行（）A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;8.散列表的平均查找長度（）A.與處理沖突方法有關(guān)而與表的長度無關(guān)B.與處理沖突方法無關(guān)而與表的長度有關(guān)C.與處理沖突方法和表的長度都有關(guān)D.與處理沖突方法和表的長度都無關(guān)9.順序查找適合于存儲結(jié)構(gòu)為（）的線性表。A.順序存儲B.鏈?zhǔn)酱鎯.順序存儲或鏈?zhǔn)酱鎯.索引存儲10.若某鏈表最常用的操作是在鏈表尾部插入節(jié)點(diǎn)和刪除尾節(jié)點(diǎn)，則采用（）存儲方式最節(jié)省時(shí)間。A.單鏈表B.帶頭節(jié)點(diǎn)的單鏈表C.雙鏈表D.帶尾指針的循環(huán)雙鏈表二、多項(xiàng)選擇題（每題2分，共10題）1.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有（）A.棧B.隊(duì)列C.樹D.圖2.以下哪些操作是棧支持的（）A.入棧B.出棧C.取棧頂元素D.遍歷3.完全二叉樹的特點(diǎn)有（）A.葉子節(jié)點(diǎn)只能出現(xiàn)在最下兩層B.最下層的葉子節(jié)點(diǎn)集中在左部C.若有度為1的節(jié)點(diǎn)，則該節(jié)點(diǎn)只有左孩子D.一定是滿二叉樹4.以下排序算法中，穩(wěn)定的排序算法有（）A.冒泡排序B.選擇排序C.插入排序D.歸并排序5.圖的遍歷方法有（）A.深度優(yōu)先遍歷B.廣度優(yōu)先遍歷C.先序遍歷D.中序遍歷6.以下關(guān)于哈希表的說法正確的是（）A.哈希表是一種存儲結(jié)構(gòu)B.哈希函數(shù)的選擇很重要C.哈希表可以減少查找時(shí)間D.哈希表一定會產(chǎn)生沖突7.對于二叉排序樹，以下說法正確的是（）A.左子樹所有節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值B.右子樹所有節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值C.中序遍歷二叉排序樹可以得到一個有序序列D.插入新節(jié)點(diǎn)時(shí)不會破壞二叉排序樹的性質(zhì)8.單鏈表的優(yōu)點(diǎn)有（）A.插入和刪除操作不需要移動大量元素B.可以隨機(jī)訪問任意節(jié)點(diǎn)C.存儲密度高D.適合動態(tài)存儲分配9.以下哪些是樹的遍歷方式（）A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷10.以下屬于查找算法的有（）A.順序查找B.二分查找C.哈希查找D.冒泡查找三、判斷題（每題2分，共10題）1.線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更節(jié)省空間。（）2.棧和隊(duì)列都是特殊的線性表。（）3.二叉樹的前序遍歷和中序遍歷結(jié)果相同，則該二叉樹所有節(jié)點(diǎn)都沒有左子樹。（）4.快速排序在任何情況下的時(shí)間復(fù)雜度都是O(nlogn)。（）5.圖的鄰接矩陣表示法中，無向圖的鄰接矩陣一定是對稱矩陣。（）6.哈希表中，沖突是不可避免的。（）7.中序線索二叉樹的遍歷可以不使用棧。（）8.順序查找的平均查找長度為n/2。（）9.完全二叉樹一定是滿二叉樹。（）10.對于一個帶權(quán)連通圖，其最小生成樹是唯一的。（）四、簡答題（每題5分，共4題）1.簡述棧和隊(duì)列的區(qū)別。答：棧是先進(jìn)后出，元素進(jìn)出遵循后進(jìn)先出原則；隊(duì)列是先進(jìn)先出，元素按進(jìn)入順序依次出隊(duì)。2.簡述二叉排序樹的插入過程。答：若二叉排序樹為空，則新節(jié)點(diǎn)作為根節(jié)點(diǎn)插入；否則，將新節(jié)點(diǎn)的值與根節(jié)點(diǎn)比較，小于根節(jié)點(diǎn)值則插入左子樹，大于則插入右子樹，依此遞歸直到找到合適位置插入。3.簡述選擇排序的基本思想。答：在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。4.簡述圖的鄰接表存儲結(jié)構(gòu)。答：圖的鄰接表存儲結(jié)構(gòu)對圖中每個頂點(diǎn)建立一個單鏈表，第i個單鏈表中的節(jié)點(diǎn)表示依附于頂點(diǎn)i的邊（對有向圖是以頂點(diǎn)i為尾的弧）。每個單鏈表附設(shè)一個表頭節(jié)點(diǎn)，表頭節(jié)點(diǎn)中存放頂點(diǎn)i的編號。五、討論題（每題5分，共4題）1.討論不同排序算法在不同數(shù)據(jù)規(guī)模和數(shù)據(jù)特征下的應(yīng)用場景。答：小規(guī)模數(shù)據(jù)，插入排序較簡單高效；數(shù)據(jù)基本有序時(shí)，冒泡排序也不錯。大規(guī)模數(shù)據(jù)，快速排序平均性能好；穩(wěn)定排序需求時(shí)，歸并排序適用。數(shù)據(jù)元素值范圍小且密集，計(jì)數(shù)排序有優(yōu)勢。2.討論線性表順序存儲和鏈?zhǔn)酱鎯υ诓煌瑧?yīng)用場景下的優(yōu)缺點(diǎn)。答：順序存儲優(yōu)點(diǎn)是可隨機(jī)訪問，存儲密度高；缺點(diǎn)是插入刪除需移動大量元素，適合數(shù)據(jù)變動少、頻繁隨機(jī)訪問場景。鏈?zhǔn)酱鎯?yōu)點(diǎn)是插入刪除操作方便，缺點(diǎn)是不能隨機(jī)訪問，存儲密度低，適合數(shù)據(jù)頻繁變動場景。3.討論哈希表中處理沖突的方法及其優(yōu)缺點(diǎn)。答：開放定址法，優(yōu)點(diǎn)是簡單直觀，缺點(diǎn)是容易產(chǎn)生聚集現(xiàn)象。鏈地址法，優(yōu)點(diǎn)是處理沖突簡單，不易產(chǎn)生聚集；缺點(diǎn)是需要額外指針空間，當(dāng)沖突多鏈表長時(shí)查找效率下降。4.討論樹和圖這兩種數(shù)據(jù)結(jié)構(gòu)在實(shí)際問題中的應(yīng)用。答：樹常用于文件系統(tǒng)目錄結(jié)構(gòu)、家族族譜等層次結(jié)構(gòu)表示；圖可用于社交網(wǎng)絡(luò)關(guān)系建模、交通網(wǎng)絡(luò)規(guī)劃、最短路徑問題求解等，能很好描述復(fù)雜關(guān)系和路徑問題。答案一、單項(xiàng)選擇題1.A2.B3.B4.C5.A6.B7.B8.A9.C10.D二、多項(xiàng)選擇題