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

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

一、單項(xiàng)選擇題（每題2分，共20分）1.線性表采用順序存儲(chǔ)結(jié)構(gòu)，訪問第i個(gè)元素的時(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.都不對(duì)3.鏈表不具備的特點(diǎn)是（）A.可隨機(jī)訪問B.插入刪除效率高C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性表長(zhǎng)度成正比4.一棵二叉樹的前序遍歷序列為ABCDE，中序遍歷序列為CBADE，則后序遍歷序列為（）A.CBADEB.CBEDAC.EDCBAD.EDCAB5.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣存儲(chǔ)，則該矩陣的大小是（）A.nB.(n-1)2C.n2D.(n+1)26.以下排序算法中，平均時(shí)間復(fù)雜度為O(nlogn)的是（）A.冒泡排序B.插入排序C.快速排序D.選擇排序7.順序查找長(zhǎng)度為n的線性表，在等概率情況下，平均查找長(zhǎng)度為（）A.nB.n/2C.(n+1)/2D.(n-1)/28.隊(duì)列的“先進(jìn)先出”特性是指（）A.最早插入隊(duì)列中的元素總是最后被刪除B.當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C.每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作D.先插入的元素總是先被刪除9.若一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，則該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)是（）A.257B.258C.384D.38510.散列表的平均查找長(zhǎng)度（）A.與處理沖突方法有關(guān)而與表的長(zhǎng)度無關(guān)B.與處理沖突方法無關(guān)而與表的長(zhǎng)度有關(guān)C.與處理沖突方法和表的長(zhǎng)度都有關(guān)D.與處理沖突方法和表的長(zhǎng)度都無關(guān)二、多項(xiàng)選擇題（每題2分，共20分）1.以下屬于線性結(jié)構(gòu)的有（）A.棧B.隊(duì)列C.二叉樹D.圖2.關(guān)于棧的說法正確的有（）A.棧是一種操作受限的線性表B.棧的操作遵循先進(jìn)后出原則C.棧可以用于表達(dá)式求值D.棧的插入和刪除操作只能在棧頂進(jìn)行3.鏈表的優(yōu)點(diǎn)包括（）A.內(nèi)存利用率高B.插入刪除操作方便C.可隨機(jī)訪問D.無需連續(xù)存儲(chǔ)空間4.二叉樹的遍歷方式有（）A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷5.以下哪些排序算法是穩(wěn)定的（）A.冒泡排序B.插入排序C.歸并排序D.快速排序6.圖的存儲(chǔ)結(jié)構(gòu)有（）A.鄰接矩陣B.鄰接表C.十字鏈表D.鄰接多重表7.哈希函數(shù)的構(gòu)造方法有（）A.直接定址法B.除留余數(shù)法C.數(shù)字分析法D.平方取中法8.以下關(guān)于隊(duì)列的描述正確的是（）A.隊(duì)列是一種操作受限的線性表B.隊(duì)列的操作遵循先進(jìn)先出原則C.循環(huán)隊(duì)列可以避免假溢出D.隊(duì)列可以用鏈表實(shí)現(xiàn)9.樹和二叉樹的區(qū)別有（）A.二叉樹每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹，樹則無此限制B.二叉樹可以為空，樹不能為空C.二叉樹有左右子樹之分，樹無此概念D.二叉樹和樹的存儲(chǔ)結(jié)構(gòu)完全不同10.查找算法有（）A.順序查找B.二分查找C.哈希查找D.插值查找三、判斷題（每題2分，共20分）1.順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除操作效率高。（）2.棧和隊(duì)列都是特殊的線性表。（）3.鏈表的刪除操作不需要移動(dòng)元素，所以時(shí)間復(fù)雜度為O(1)。（）4.完全二叉樹一定是滿二叉樹。（）5.快速排序在任何情況下的時(shí)間復(fù)雜度都是O(nlogn)。（）6.圖的廣度優(yōu)先搜索類似于樹的層次遍歷。（）7.哈希表是一種基于關(guān)鍵字直接訪問的數(shù)據(jù)結(jié)構(gòu)。（）8.隊(duì)列的插入操作在隊(duì)頭進(jìn)行，刪除操作在隊(duì)尾進(jìn)行。（）9.二叉排序樹的中序遍歷序列是有序序列。（）10.對(duì)于n個(gè)元素進(jìn)行排序，堆排序的時(shí)間復(fù)雜度為O(nlogn)。（）四、簡(jiǎn)答題（每題5分，共20分）1.簡(jiǎn)述棧和隊(duì)列的區(qū)別。答案：棧操作遵循先進(jìn)后出原則，插入和刪除都在棧頂進(jìn)行；隊(duì)列操作遵循先進(jìn)先出原則，插入在隊(duì)尾，刪除在隊(duì)頭。2.簡(jiǎn)述二分查找的基本思想。答案：在有序數(shù)組中，取中間元素與目標(biāo)元素比較。若相等則找到；若目標(biāo)元素小，在左半部分繼續(xù)查找；若大，則在右半部分查找，重復(fù)此過程直到找到或確定不存在。3.簡(jiǎn)述圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的不同。答案：深度優(yōu)先搜索是沿著一條路徑盡可能深地探索，直到無法繼續(xù)再回溯；廣度優(yōu)先搜索是按層次依次訪問頂點(diǎn)，先訪問的頂點(diǎn)的鄰接頂點(diǎn)先被訪問。4.簡(jiǎn)述選擇排序的基本步驟。答案：在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?。然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。五、討論題（每題5分，共20分）1.分析順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在不同場(chǎng)景下的優(yōu)缺點(diǎn)及適用情況。答案：順序存儲(chǔ)結(jié)構(gòu)優(yōu)點(diǎn)是存儲(chǔ)密度大，可隨機(jī)訪問；缺點(diǎn)是插入刪除效率低，需連續(xù)空間。適用于數(shù)據(jù)變動(dòng)少、頻繁隨機(jī)訪問場(chǎng)景。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)點(diǎn)是插入刪除效率高，無需連續(xù)空間；缺點(diǎn)是存儲(chǔ)密度小，不可隨機(jī)訪問。適用于數(shù)據(jù)變動(dòng)頻繁場(chǎng)景。2.討論在實(shí)際應(yīng)用中如何選擇合適的排序算法。答案：若數(shù)據(jù)量小且基本有序，冒泡、插入排序合適；數(shù)據(jù)量較大時(shí)，快速、歸并、堆排序較好。穩(wěn)定排序需求時(shí)選冒泡、插入、歸并排序。對(duì)空間要求高可選堆排序。要綜合考慮數(shù)據(jù)規(guī)模、初始狀態(tài)、穩(wěn)定性及空間等因素。3.探討二叉樹遍歷方式在實(shí)際問題中的應(yīng)用。答案：前序遍歷可用于先訪問根節(jié)點(diǎn)做特定操作，如打印樹結(jié)構(gòu)。中序遍歷用于二叉排序樹，可得到有序序列。后序遍歷用于在子樹處理完后處理根節(jié)點(diǎn)，如計(jì)算樹中節(jié)點(diǎn)值之和。層次遍歷用于按層處理節(jié)點(diǎn)，如逐層打印二叉樹。4.談?wù)劰１碓谔岣卟檎倚史矫娴脑砑翱赡苡龅降膯栴}和解決方法。答案：哈希表通過哈希函數(shù)將關(guān)鍵字映射到存儲(chǔ)位置，理想情況下可直接訪問，提高查找效率?？赡苡龅?jīng)_突問題，解決方法有開放定址法，如線性探測(cè)；鏈地址法，將沖突元素鏈在同一位置。答案一、單項(xiàng)選擇題1.A2.B3.A4.B5.C6.C7.C8.D9.C10.C二、多項(xiàng)選擇題1.AB