裝訂線裝訂線PAGE2第1頁，共3頁阿壩師范學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法》2022-2023學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖中，至少需要多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)2、一棵二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為BDCAEHFG，則該二叉樹的后序遍歷序列為（）。A.DCBGFHEAB.DCBHGFEAC.BCDGFHEAD.BCDHGFEA3、對(duì)于一個(gè)具有n個(gè)元素的待排序序列，若采用冒泡排序算法進(jìn)行排序，在最壞情況下需要進(jìn)行的比較次數(shù)為？（）A.n(n-1)/2B.nlognC.n-1D.n4、在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)頭指針front和隊(duì)尾指針rear都指向同一個(gè)位置時(shí)，隊(duì)列的狀態(tài)可能是？（）A.隊(duì)滿B.隊(duì)空C.既不滿也不空D.以上都有可能5、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉排序樹，刪除一個(gè)節(jié)點(diǎn)后，重新調(diào)整為二叉排序樹，其時(shí)間復(fù)雜度最壞情況下為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一個(gè)用鄰接矩陣表示的無向圖中，矩陣中的元素表示什么？A.頂點(diǎn)之間的距離B.頂點(diǎn)之間是否有邊C.邊的權(quán)重D.以上都有可能7、鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，包括單鏈表、雙向鏈表等。在單鏈表中，要?jiǎng)h除一個(gè)指定節(jié)點(diǎn)，以下操作錯(cuò)誤的是（）A.首先找到要?jiǎng)h除的節(jié)點(diǎn)B.直接將該節(jié)點(diǎn)從鏈表中移除，無需處理前后節(jié)點(diǎn)的鏈接C.修改前一個(gè)節(jié)點(diǎn)的指針，使其指向要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)D.釋放被刪除節(jié)點(diǎn)所占用的內(nèi)存8、在一個(gè)具有n個(gè)頂點(diǎn)的有向無環(huán)圖中，使用拓?fù)渑判蛩惴?，其結(jié)果的唯一性如何？A.一定唯一B.可能不唯一C.取決于頂點(diǎn)的編號(hào)D.以上都不對(duì)9、在一個(gè)循環(huán)鏈表中，若要?jiǎng)h除鏈表中的最后一個(gè)節(jié)點(diǎn)，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、在一個(gè)具有n個(gè)元素的有序數(shù)組中，采用插入排序進(jìn)行排序，在最好情況下，需要比較的次數(shù)為（）。A.n-1B.nC.0D.n(n-1)/211、在一個(gè)具有n個(gè)元素的順序表中，要在中間位置插入一個(gè)新元素，平均移動(dòng)元素的個(gè)數(shù)約為？A.n/2B.nC.lognD.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、在一個(gè)具有n個(gè)元素的最小堆中，若要將堆頂元素與堆底元素交換，然后調(diào)整堆的結(jié)構(gòu)，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖，采用鄰接表存儲(chǔ)，進(jìn)行深度優(yōu)先遍歷。以下關(guān)于遍歷的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)15、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，采用中序遍歷將其轉(zhuǎn)換為一個(gè)有序的單鏈表。以下關(guān)于轉(zhuǎn)換過程的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)16、若一個(gè)圖的廣度優(yōu)先遍歷序列為ABCDEFG，則其深度優(yōu)先遍歷序列可能為？（）A.ABDCEFGB.ACBDEFGC.ADBCEFGD.AECBDFG17、對(duì)于一個(gè)棧，進(jìn)行入棧和出棧操作時(shí)，以下哪種情況會(huì)導(dǎo)致棧溢出？A.入棧元素過多B.出棧元素過多C.連續(xù)進(jìn)行入棧操作且存儲(chǔ)空間已滿D.連續(xù)進(jìn)行出棧操作且棧為空18、在一個(gè)具有n個(gè)元素的鏈表中，若要在表頭插入一個(gè)新元素，平均需要修改幾個(gè)指針？（）A.1B.2C.nD.n+119、一個(gè)棧的入棧序列是1、2、3、4、5，若第一個(gè)出棧的元素是3，則第5個(gè)出棧的元素不可能是：A.1B.2C.4D.520、以下哪種排序算法在數(shù)據(jù)基本有序時(shí)的時(shí)間復(fù)雜度接近O(n)？A.冒泡排序B.快速排序C.插入排序D.選擇排序二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）說明隊(duì)列的先進(jìn)先出（FIFO）特性對(duì)解決哪些問題有幫助，并舉例說明。2、（本題10分）深入分析在具有n個(gè)頂點(diǎn)和e條邊的有向圖中，如何計(jì)算圖的強(qiáng)連通分量，并給出一種有效的算法和代碼示例。3、（本題10分）什么是二叉搜索樹的刪除操作的平衡二叉樹實(shí)現(xiàn)？請(qǐng)舉例說明。4、（本題10分）解釋如何在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中計(jì)算每個(gè)頂點(diǎn)