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

一、單項(xiàng)選擇題（每題2分，共10題）1.以下哪種數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)？（）A.樹B.圖C.棧D.二叉樹答案：C2.鏈表不具有的特點(diǎn)是（）。A.插入、刪除不需要移動(dòng)元素B.可隨機(jī)訪問(wèn)任一元素C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性長(zhǎng)度成正比答案：B3.順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（）。A.108B.100C.110D.120答案：A4.棧的操作原則是（）。A.先進(jìn)先出B.后進(jìn)先出C.只能刪除棧頂元素D.只能插入棧頂元素答案：B5.隊(duì)列的操作原則是（）。A.先進(jìn)先出B.后進(jìn)先出C.只能刪除隊(duì)頭元素D.只能插入隊(duì)尾元素答案：A6.二叉樹的第i層上最多有（）個(gè)結(jié)點(diǎn)。A.2iB.2i-1C.2^(i-1)D.2^i+1答案：C7.對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹，其高度為（）。A.nlog?nB.log?nC.?log?n?+1D.不確定答案：D8.以下哪種排序算法是不穩(wěn)定的？（）A.冒泡排序B.插入排序C.歸并排序D.快速排序答案：D9.散列表的查找效率取決于（）。A.散列函數(shù)B.處理沖突的方法C.裝填因子D.以上都是答案：D10.圖的深度優(yōu)先搜索類似于二叉樹的（）。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷答案：A二、多項(xiàng)選擇題（每題2分，共10題）1.以下屬于線性結(jié)構(gòu)的有（）。A.數(shù)組B.鏈表C.棧D.隊(duì)列答案：ABCD2.鏈表的類型有（）。A.單鏈表B.雙向鏈表C.循環(huán)鏈表D.靜態(tài)鏈表答案：ABCD3.棧的應(yīng)用有（）。A.表達(dá)式求值B.函數(shù)調(diào)用C.括號(hào)匹配D.深度優(yōu)先搜索輔助結(jié)構(gòu)答案：ABCD4.隊(duì)列的應(yīng)用有（）。A.操作系統(tǒng)中的作業(yè)調(diào)度B.廣度優(yōu)先搜索輔助結(jié)構(gòu)C.緩沖池D.打印任務(wù)排隊(duì)答案：ABCD5.二叉樹的遍歷方式有（）。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷答案：ABCD6.排序算法的評(píng)價(jià)指標(biāo)有（）。A.時(shí)間復(fù)雜度B.空間復(fù)雜度C.穩(wěn)定性D.初始數(shù)據(jù)的敏感性答案：ABCD7.以下屬于內(nèi)部排序算法的有（）。A.冒泡排序B.希爾排序C.堆排序D.歸并排序答案：ABCD8.散列函數(shù)的設(shè)計(jì)要求有（）。A.計(jì)算簡(jiǎn)單B.散列地址分布均勻C.盡可能避免沖突D.與處理沖突方法無(wú)關(guān)答案：ABC9.圖的存儲(chǔ)結(jié)構(gòu)有（）。A.鄰接矩陣B.鄰接表C.十字鏈表D.鄰接多重表答案：ABCD10.以下關(guān)于樹的說(shuō)法正確的是（）。A.樹是一種非線性結(jié)構(gòu)B.樹有一個(gè)根節(jié)點(diǎn)C.樹的節(jié)點(diǎn)之間有層次關(guān)系D.樹的子樹之間不相交答案：ABCD三、判斷題（每題2分，共10題）1.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更節(jié)省存儲(chǔ)空間。（）答案：錯(cuò)誤2.棧和隊(duì)列都是操作受限的線性表。（）答案：正確3.二叉樹中每個(gè)節(jié)點(diǎn)的度最多為2。（）答案：正確4.完全二叉樹一定是滿二叉樹。（）答案：錯(cuò)誤5.快速排序是一種穩(wěn)定的排序算法。（）答案：錯(cuò)誤6.散列表中裝填因子越大，發(fā)生沖突的可能性越小。（）答案：錯(cuò)誤7.圖的鄰接矩陣表示法中，矩陣的對(duì)角線元素一定為0。（）答案：錯(cuò)誤8.樹的深度和高度是相同的概念。（）答案：正確9.對(duì)于單鏈表，只能從頭節(jié)點(diǎn)開始遍歷。（）答案：正確10.歸并排序的時(shí)間復(fù)雜度是O(nlog?n)。（）答案：正確四、簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述順序表和鏈表的優(yōu)缺點(diǎn)。答案：順序表優(yōu)點(diǎn)：可隨機(jī)訪問(wèn)，存儲(chǔ)密度大。缺點(diǎn)：插入、刪除操作需移動(dòng)大量元素，需預(yù)先分配足夠空間。鏈表優(yōu)點(diǎn)：插入、刪除操作方便，不需要預(yù)先分配大量空間。缺點(diǎn)：不能隨機(jī)訪問(wèn)，存儲(chǔ)密度小。2.簡(jiǎn)述二叉樹的性質(zhì)。答案：二叉樹第i層最多有2^(i-1)個(gè)結(jié)點(diǎn)；深度為k的二叉樹最多有2^k-1個(gè)結(jié)點(diǎn)；對(duì)任何二叉樹，如果其葉結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。3.簡(jiǎn)述散列函數(shù)的作用。答案：散列函數(shù)的作用是將關(guān)鍵字映射為散列表中的存儲(chǔ)地址，通過(guò)這個(gè)映射關(guān)系，在查找元素時(shí)可以直接根據(jù)關(guān)鍵字計(jì)算出其可能的存儲(chǔ)位置，提高查找效率。4.簡(jiǎn)述圖的廣度優(yōu)先搜索算法的基本思想。答案：從圖中某個(gè)頂點(diǎn)v出發(fā)，先訪問(wèn)v，然后依次訪問(wèn)v的各個(gè)未被訪問(wèn)的鄰接點(diǎn)，再分別從這些鄰接點(diǎn)出發(fā)依次訪問(wèn)它們的鄰接點(diǎn)，直到所有頂點(diǎn)都被訪問(wèn)。五、討論題（每題5分，共4題）1.討論在何種情況下應(yīng)選擇順序表而不是鏈表。答案：當(dāng)需要頻繁隨機(jī)訪問(wèn)元素，且數(shù)據(jù)量相對(duì)固定，插入和刪除操作較少時(shí)，選擇順序表。例如在查詢固定大小數(shù)組中的元素時(shí)，順序表更合適。2.討論二叉樹在實(shí)際中的應(yīng)用。答案：二叉樹在編碼方面有應(yīng)用，如哈夫曼編碼；在搜索方面，二叉搜索樹可提高搜索效率；在表達(dá)式表示上也有應(yīng)用，如表達(dá)式樹。3.討論排序算法穩(wěn)定性的意義。答案：排序算法穩(wěn)定性在某些場(chǎng)景下很重要