安徽工業(yè)大學《數(shù)據(jù)結構與算法》2022-2023學年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁安徽工業(yè)大學

《數(shù)據(jù)結構與算法》2022-2023學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種數(shù)據(jù)結構常用于實現(xiàn)表達式求值？A.二叉樹B.棧C.隊列D.哈希表2、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA3、對于一個具有n個頂點和e條邊的有向圖，采用鄰接表存儲，進行深度優(yōu)先遍歷。以下關于遍歷的時間復雜度的描述，哪一個是恰當?shù)模緼.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)4、已知一個圖的鄰接矩陣如下所示，則從頂點V1出發(fā)進行深度優(yōu)先遍歷，可能得到的頂點訪問序列是（）。|01100||10010||10001||01000||00100|A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V5,V3,V4D.V1,V4,V3,V2,V55、以下哪種數(shù)據(jù)結構常用于實現(xiàn)圖的存儲？A.鄰接矩陣和鄰接表B.二叉樹和鏈表C.棧和隊列D.數(shù)組和哈希表6、對于一個具有n個頂點的無向完全圖，其邊的數(shù)量為多少？（）A.n(n-1)/2B.n(n-1)C.n2D.2n7、設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為：A.連接B.模式匹配C.求子串D.求串長8、排序算法的穩(wěn)定性和時間復雜度可以用于選擇合適的排序算法，以下關于它們的說法中，錯誤的是？（）A.穩(wěn)定性對于某些應用場景非常重要，如對具有多個關鍵字的記錄進行排序時。B.時間復雜度是衡量排序算法效率的重要指標，不同的排序算法具有不同的時間復雜度。C.可以根據(jù)實際情況選擇穩(wěn)定的或不穩(wěn)定的排序算法，以及時間復雜度較低的排序算法。D.排序算法的穩(wěn)定性和時間復雜度只適用于理論研究，在實際應用中沒有實際價值。9、對于一個具有n個元素的雙向鏈表，若要在第i個位置（1<=i<=n）之前插入一個新節(jié)點，平均需要修改多少個指針？（）A.1B.2C.3D.410、對于一個具有n個節(jié)點的帶權連通圖，其最小生成樹一定包含圖中的所有節(jié)點嗎？A.一定包含B.不一定包含C.視情況而定D.以上都不對11、以下哪種排序算法在最壞情況下的交換次數(shù)最少？A.冒泡排序B.快速排序C.選擇排序D.插入排序12、在一個鏈式存儲的隊列中，若隊頭指針為front，隊尾指針為rear，當進行一次出隊操作后，front指針應該如何移動？A.front=front->nextB.front=rearC.front不變D.front=NULL13、對于一個采用鏈表存儲的棧，若要獲取棧的大?。ㄔ財?shù)量），以下關于操作的時間復雜度的描述，哪一個是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、在一個具有n個元素的最小堆中，刪除堆頂元素后，為了恢復堆的性質(zhì)，需要進行的調(diào)整操作的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、對于一個具有n個元素的有序數(shù)組，使用二分查找算法查找一個特定元素。以下關于二分查找的時間復雜度的描述，哪一個是恰當?shù)模緼.O(1)B.O(logn)C.O(n)D.O(nlogn)16、在一個B樹中，每個節(jié)點的關鍵字數(shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-117、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），平均需要移動的元素個數(shù)約為？A.n/2B.n-iC.iD.n-i+118、在一個循環(huán)鏈表中，若要刪除鏈表中的最后一個節(jié)點，需要的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在一個循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，隊列最大容量為MAXSIZE，若當前隊列長度為n，則判斷隊滿的條件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE20、在一個用數(shù)組實現(xiàn)的棧中，若要將棧的容量擴大一倍，以下哪種操作的時間復雜度最低？（）A.重新創(chuàng)建一個更大的數(shù)組并復制元素B.逐步將元素移動到新的更大的數(shù)組中C.直接在原數(shù)組后面追加空間D.以上操作時間復雜度相同二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋在一個有序數(shù)組中進行二分查找的基本思路和步驟，分析其時間復雜度和空間復雜度。2、（本題10分）詳細論述在一個具有n個頂點的無向圖中，如何進行頂點的割點求解。3、（本題10分）數(shù)組的排序算法中，快速排序的實現(xiàn)過程是怎樣的？時間復雜度和空間復雜度分別是多少？4、（本題10分）在一個二叉樹中，如何進行前序遍歷的非遞歸實現(xiàn)？三、設計