阿壩師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁阿壩師范學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，若要?jiǎng)h除表中所有值為x的結(jié)點(diǎn)，最優(yōu)的算法時(shí)間復(fù)雜度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)2、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表存儲(chǔ)，則其空間復(fù)雜度為：A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)3、在一個(gè)用鄰接矩陣存儲(chǔ)的圖中，若要判斷兩個(gè)節(jié)點(diǎn)是否相鄰，時(shí)間復(fù)雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)4、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣存儲(chǔ)，則存儲(chǔ)空間的復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)5、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖中，采用鄰接表存儲(chǔ)，其時(shí)間復(fù)雜度為？（）A.O(n+e)B.O(n2)C.O(e2)D.O(ne)6、若要在一棵二叉搜索樹中查找一個(gè)特定的值，平均時(shí)間復(fù)雜度為？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)7、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)LRU（最近最少使用）頁面置換算法？A.隊(duì)列B.棧C.哈希表D.雙鏈表8、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的存儲(chǔ)？A.鄰接矩陣和鄰接表B.二叉樹和鏈表C.棧和隊(duì)列D.數(shù)組和哈希表9、棧是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它遵循后進(jìn)先出（LIFO）的原則。以下關(guān)于棧的說法中，錯(cuò)誤的是？（）A.棧可以用數(shù)組或鏈表實(shí)現(xiàn)。B.棧的插入和刪除操作只能在棧頂進(jìn)行。C.?？梢杂糜趯?shí)現(xiàn)函數(shù)調(diào)用、表達(dá)式求值等。D.棧的容量是無限的，可以存儲(chǔ)任意數(shù)量的元素。10、一棵二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為BDCAEHFG，則該二叉樹的后序遍歷序列為（）。A.DCBGFHEAB.DCBHGFEAC.BCDGFHEAD.BCDHGFEA11、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的線性表中，要在第i個(gè)位置插入一個(gè)新元素（1<=i<=n+1），需要移動(dòng)的元素個(gè)數(shù)約為？A.n-iB.iC.n-i+1D.n-i-112、在一個(gè)具有n個(gè)元素的小根堆中，刪除堆頂元素后，將最后一個(gè)元素放到堆頂，然后進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)13、對(duì)于一個(gè)棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則下列不可能的出棧序列是：A.54321B.45321C.12345D.3142514、對(duì)于一個(gè)采用鏈?zhǔn)酱鎯?chǔ)的隊(duì)列，若隊(duì)頭指針和隊(duì)尾指針相同，則隊(duì)列的狀態(tài)為：A.隊(duì)空B.隊(duì)滿C.不確定D.隊(duì)列中只有一個(gè)元素15、在一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉（Dijkstra）算法求單源最短路徑。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)16、在一個(gè)具有n個(gè)元素的雙向鏈表中，要在指定節(jié)點(diǎn)之后插入一個(gè)新節(jié)點(diǎn)，需要修改幾個(gè)指針？A.2B.3C.4D.517、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行插入操作的時(shí)間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)18、對(duì)于一個(gè)大根堆，若將堆中所有元素按照層次遍歷的順序存儲(chǔ)到一個(gè)數(shù)組中，以下關(guān)于數(shù)組元素的排列，哪一項(xiàng)是正確的？A.完全無序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對(duì)19、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，若每個(gè)節(jié)點(diǎn)都有左右子樹，則該二叉樹的葉子節(jié)點(diǎn)數(shù)量與度為2的節(jié)點(diǎn)數(shù)量之間存在特定關(guān)系。以下關(guān)于這種關(guān)系的描述，哪一項(xiàng)是正確的？A.葉子節(jié)點(diǎn)數(shù)量等于度為2的節(jié)點(diǎn)數(shù)量B.葉子節(jié)點(diǎn)數(shù)量比度為2的節(jié)點(diǎn)數(shù)量多1C.葉子節(jié)點(diǎn)數(shù)量比度為2的節(jié)點(diǎn)數(shù)量少1D.兩者之間沒有固定關(guān)系20、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉平衡樹，若要插入一個(gè)新節(jié)點(diǎn)并保持平衡，以下關(guān)于插入操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）闡述并查集中如何通過數(shù)據(jù)結(jié)構(gòu)的改進(jìn)提高空間利用率。2、（本題10分）解釋如何對(duì)一個(gè)鏈表進(jìn)行排序，選擇合適的排序算法（如歸并排序）給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題10分）在一個(gè)雙向鏈表中，如何刪除指定區(qū)間內(nèi)的結(jié)點(diǎn)？4、（本題10分）說明在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖中，如何使用A*算法進(jìn)行啟發(fā)式搜索，并分析算法的性能和適用場(chǎng)景。三