北航研究生期末考試題及答案

一、單項(xiàng)選擇題（每題2分，共20分）1.以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先隊(duì)列？A.棧B.隊(duì)列C.堆D.鏈表答案：C2.算法的時(shí)間復(fù)雜度取決于（）A.問(wèn)題規(guī)模B.計(jì)算機(jī)性能C.算法語(yǔ)言D.程序員水平答案：A3.對(duì)于一棵二叉排序樹，其左子樹中節(jié)點(diǎn)的值（）根節(jié)點(diǎn)的值。A.大于B.小于C.等于D.大于等于答案：B4.以下排序算法中，平均時(shí)間復(fù)雜度為O(nlogn)的是（）A.冒泡排序B.選擇排序C.歸并排序D.插入排序答案：C5.圖的廣度優(yōu)先搜索算法利用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.堆D.優(yōu)先隊(duì)列答案：B6.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和，這是因?yàn)椋ǎ〢.每條邊都有一個(gè)入度和一個(gè)出度B.入度和出度是對(duì)稱的C.這是圖的基本性質(zhì)D.以上都不對(duì)答案：A7.散列表的平均查找長(zhǎng)度取決于（）A.散列函數(shù)B.裝填因子C.處理沖突的方法D.以上都是答案：D8.以下關(guān)于遞歸算法的說(shuō)法，正確的是（）A.遞歸算法效率一定比非遞歸算法高B.遞歸算法需要更多的?？臻gC.遞歸算法不能轉(zhuǎn)換為非遞歸算法D.遞歸算法不適合解決復(fù)雜問(wèn)題答案：B9.一棵完全二叉樹有100個(gè)節(jié)點(diǎn)，其葉子節(jié)點(diǎn)的個(gè)數(shù)為（）A.50B.51C.49D.48答案：A10.對(duì)n個(gè)元素進(jìn)行快速排序，最好情況下的時(shí)間復(fù)雜度是（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)答案：B二、多項(xiàng)選擇題（每題2分，共20分）1.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有（）A.數(shù)組B.鏈表C.棧D.隊(duì)列答案：ABCD2.下列排序算法中，穩(wěn)定的排序算法有（）A.冒泡排序B.插入排序C.歸并排序D.基數(shù)排序答案：ABCD3.圖的存儲(chǔ)結(jié)構(gòu)有（）A.鄰接矩陣B.鄰接表C.十字鏈表D.鄰接多重表答案：ABCD4.二叉樹的遍歷方式有（）A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷答案：ABCD5.哈希函數(shù)的構(gòu)造方法有（）A.直接定址法B.數(shù)字分析法C.平方取中法D.折疊法答案：ABCD6.以下哪些算法可以用于圖的最短路徑問(wèn)題（）A.Dijkstra算法B.Floyd算法C.Prim算法D.Kruskal算法答案：AB7.數(shù)據(jù)結(jié)構(gòu)中，棧的應(yīng)用場(chǎng)景有（）A.表達(dá)式求值B.括號(hào)匹配C.深度優(yōu)先搜索D.遞歸調(diào)用答案：ABCD8.下列關(guān)于平衡二叉樹的說(shuō)法正確的是（）A.左右子樹高度差的絕對(duì)值不超過(guò)1B.是一棵二叉排序樹C.插入、刪除操作后可能需要調(diào)整平衡D.所有節(jié)點(diǎn)的平衡因子只能是-1、0、1答案：ABCD9.以下哪些是動(dòng)態(tài)存儲(chǔ)分配的方法（）A.棧式存儲(chǔ)分配B.堆式存儲(chǔ)分配C.靜態(tài)存儲(chǔ)分配D.順序存儲(chǔ)分配答案：AB10.以下哪些屬于算法的特性（）A.有窮性B.確定性C.可行性D.輸入輸出答案：ABCD三、判斷題（每題2分，共20分）1.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更節(jié)省存儲(chǔ)空間。（）答案：錯(cuò)2.快速排序在最壞情況下的時(shí)間復(fù)雜度為O(n^2)。（）答案：對(duì)3.完全二叉樹一定是滿二叉樹。（）答案：錯(cuò)4.圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷都需要借助隊(duì)列。（）答案：錯(cuò)5.哈希表中，裝填因子越大，發(fā)生沖突的可能性越小。（）答案：錯(cuò)6.任何一個(gè)遞歸算法都可以轉(zhuǎn)換為非遞歸算法。（）答案：對(duì)7.堆排序是一種不穩(wěn)定的排序算法。（）答案：對(duì)8.二叉排序樹的中序遍歷序列是有序的。（）答案：對(duì)9.鄰接矩陣適合存儲(chǔ)稀疏圖。（）答案：錯(cuò)10.拓?fù)渑判蜻m用于有向無(wú)環(huán)圖。（）答案：對(duì)四、簡(jiǎn)答題（每題5分，共20分）1.簡(jiǎn)述棧和隊(duì)列的區(qū)別。答案：棧是后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，元素的插入和刪除都在棧頂進(jìn)行；隊(duì)列是先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，元素在隊(duì)尾插入，在隊(duì)頭刪除。2.簡(jiǎn)述二叉排序樹的性質(zhì)。答案：二叉排序樹左子樹所有節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值，右子樹所有節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值，左右子樹也分別是二叉排序樹。3.簡(jiǎn)述Dijkstra算法的基本思想。答案：從源點(diǎn)出發(fā)，不斷選擇距離源點(diǎn)最近且未確定最短路徑的頂點(diǎn)，更新其鄰接頂點(diǎn)到源點(diǎn)的距離，直到所有頂點(diǎn)的最短路徑都確定。4.簡(jiǎn)述歸并排序的基本步驟。答案：將待排序序列分成兩個(gè)子序列，對(duì)兩個(gè)子序列分別進(jìn)行排序，然后將排序好的子序列合并成一個(gè)有序的序列，重復(fù)此過(guò)程直到整個(gè)序列有序。五、討論題（每題5分，共20分）1.討論在實(shí)際應(yīng)用中，如何選擇合適的數(shù)據(jù)結(jié)構(gòu)和算法。答案：要考慮問(wèn)題的特點(diǎn)、數(shù)據(jù)規(guī)模、操作頻率等。如頻繁插入刪除選鏈表，查找多則考慮哈希表等。還要權(quán)衡時(shí)間和空間復(fù)雜度，依據(jù)實(shí)際需求如性能要求、資源限制來(lái)選擇。2.討論排序算法在不同場(chǎng)景下的適用性。答案：穩(wěn)定排序適合對(duì)穩(wěn)定性有要求的場(chǎng)景，如數(shù)據(jù)庫(kù)排序。簡(jiǎn)單排序算法適合數(shù)據(jù)量小的情況?？焖倥判虻雀咝判蜻m合大數(shù)據(jù)量。堆排序適合求topK問(wèn)題等，根據(jù)具體需求選用。3.討論圖的存儲(chǔ)結(jié)構(gòu)對(duì)圖算法的影響。答案：鄰接矩陣適合稠密圖，實(shí)現(xiàn)簡(jiǎn)單但空間開銷大，一些算法實(shí)現(xiàn)方便。鄰接表適合稀疏圖，節(jié)省空間，但遍歷等操作實(shí)現(xiàn)與矩陣不同。不同