北京工業(yè)大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法分析》2021-2022學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁北京工業(yè)大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與算法分析》2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個m行n列的二維數(shù)組中，元素存儲的地址計算公式為LOC(aij)=LOC(a11)+[(i-1)*n+(j-1)]*d，其中d為每個元素所占的存儲單元數(shù)。若按行優(yōu)先存儲，則a23的地址為？（）A.LOC(a11)+5dB.LOC(a11)+6dC.LOC(a11)+7dD.LOC(a11)+8d2、設(shè)有一個棧，元素進(jìn)棧的次序?yàn)锳、B、C、D、E，下列不可能的出棧序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE3、設(shè)有一個具有n個節(jié)點(diǎn)的二叉樹，采用中序遍歷將其轉(zhuǎn)換為一個有序的單鏈表。以下關(guān)于轉(zhuǎn)換過程的時間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)4、設(shè)有一個具有n個元素的最大堆，若要獲取堆中的最大元素，以下關(guān)于操作的時間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、在一個用鏈表實(shí)現(xiàn)的隊(duì)列中，若要刪除隊(duì)頭元素并返回其值，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一棵二叉樹中，若度為2的節(jié)點(diǎn)有10個，度為1的節(jié)點(diǎn)有20個，那么葉子節(jié)點(diǎn)的數(shù)量是多少？A.11B.21C.30D.無法確定7、對于一個具有n個節(jié)點(diǎn)的二叉樹，進(jìn)行先序遍歷和中序遍歷，得到的序列相同，則該二叉樹的形狀為？A.只有一個根節(jié)點(diǎn)B.所有節(jié)點(diǎn)只有左子樹C.所有節(jié)點(diǎn)只有右子樹D.是一棵滿二叉樹8、在字符串處理中，后綴數(shù)組是一種有效的數(shù)據(jù)結(jié)構(gòu)，以下關(guān)于后綴數(shù)組的描述，錯誤的是（）A.可以用于字符串的匹配和查找B.構(gòu)建后綴數(shù)組的時間復(fù)雜度較高C.空間復(fù)雜度相對較低D.不適合處理大規(guī)模字符串9、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEABC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EACDB10、對于一個具有n個元素的希爾排序，其時間復(fù)雜度取決于？（）A.初始序列B.增量序列C.元素值D.以上都是11、在一個具有n個元素的雙向鏈表中，要在指定節(jié)點(diǎn)之后插入一個新節(jié)點(diǎn)，需要修改幾個指針？A.2B.3C.4D.512、對于一個具有n個節(jié)點(diǎn)的二叉樹，其先序遍歷、中序遍歷和后序遍歷的結(jié)果都是唯一確定的，這個二叉樹一定是（）A.滿二叉樹B.完全二叉樹C.單支樹D.以上都不是13、在一個具有n個元素的順序表中，若要將其逆置，以下關(guān)于操作的時間復(fù)雜度的描述，哪一項(xiàng)是恰當(dāng)?shù)模緼.O(1)B.O(logn)C.O(n)D.O(nlogn)14、已知一個哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測法處理沖突。若依次插入關(guān)鍵字31、25、19、49、37、21、13、17，則在查找關(guān)鍵字19時需要進(jìn)行幾次比較？（）A.1B.2C.3D.415、哈希表的性能取決于哈希函數(shù)的設(shè)計和沖突解決方法的選擇，以下關(guān)于它們的說法中，錯誤的是？（）A.好的哈希函數(shù)應(yīng)該具有均勻分布性、隨機(jī)性和高效性等特點(diǎn)。B.沖突解決方法的選擇應(yīng)該根據(jù)哈希表的大小、數(shù)據(jù)的特點(diǎn)和操作的頻率等因素來決定。C.哈希表的性能可以通過調(diào)整哈希函數(shù)和沖突解決方法來優(yōu)化。D.哈希表的性能只取決于哈希函數(shù)的設(shè)計，與沖突解決方法無關(guān)。16、在一個具有n個元素的小頂堆中，若將堆頂元素與最后一個元素交換，然后對堆進(jìn)行調(diào)整，其時間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)17、以下關(guān)于圖的最短路徑算法的描述，哪一項(xiàng)是正確的？（）A.Dijkstra算法不能處理負(fù)權(quán)邊B.Floyd算法的時間復(fù)雜度低于Dijkstra算法C.所有最短路徑算法都能在有向圖和無向圖中使用D.最短路徑一定是唯一的18、線段樹是一種用于處理區(qū)間查詢和更新的數(shù)據(jù)結(jié)構(gòu)。對于線段樹的應(yīng)用，以下說法錯誤的是（）A.可以快速計算給定區(qū)間內(nèi)元素的和B.可以用于查找區(qū)間內(nèi)的最大值和最小值C.構(gòu)建線段樹的時間復(fù)雜度為O(n)D.線段樹的空間復(fù)雜度與節(jié)點(diǎn)數(shù)量成正比19、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的存儲？A.鄰接矩陣和鄰接表B.二叉樹和鏈表C.棧和隊(duì)列D.數(shù)組和哈希表20、若一個圖的鄰接矩陣對角線以下（不包括對角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強(qiáng)連通圖D.弱連通圖二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細(xì)說明隊(duì)列的應(yīng)用場景，如任務(wù)調(diào)度、廣度優(yōu)先搜索等，給出相應(yīng)的算法步驟和實(shí)現(xiàn)代碼。2、（本題10分）在數(shù)據(jù)結(jié)構(gòu)中，闡述如何使用塊狀鏈表進(jìn)行高效的插入和刪除操作，給出算法步驟和實(shí)現(xiàn)代碼，并分析其性能優(yōu)勢。3、（本題10分）解釋數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用場景，如回溯算法、迷宮求解等，并說明其原理。4、（本題10分）論述如何使