成都錦城學院《數(shù)據(jù)結(jié)構(gòu)與算法分析》2022-2023學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁成都錦城學院《數(shù)據(jù)結(jié)構(gòu)與算法分析》

2022-2023學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的雙向鏈表中，若要刪除尾結(jié)點，需要修改幾個指針？（）A.1B.2C.3D.42、對于一個棧，進行入棧和出棧操作時，若棧頂指針top初始值為-1，當進行5次入棧和3次出棧操作后，top的值為多少？（）A.1B.2C.3D.43、在一個具有n個頂點的有向強連通圖中，至少需要多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)4、在圖的最小生成樹算法中，Kruskal算法和Prim算法都能得到最小生成樹，以下關(guān)于這兩個算法的比較，錯誤的是（）A.Kruskal算法基于邊，Prim算法基于節(jié)點B.Kruskal算法需要使用并查集C.Prim算法的時間復雜度通常比Kruskal算法低D.對于稀疏圖，Kruskal算法更優(yōu)5、對于一個具有n個元素的堆，進行刪除操作并調(diào)整堆的時間復雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、以下哪種數(shù)據(jù)結(jié)構(gòu)在查找、插入和刪除操作的綜合性能上表現(xiàn)較好？（）A.二叉搜索樹B.紅黑樹C.B樹D.哈希表7、在一個具有n個頂點的有向圖中，若存在環(huán)，則使用拓撲排序算法會？A.正常排序B.無法排序C.部分排序D.排序結(jié)果不確定8、設(shè)有一個20階的下三角矩陣A，采用壓縮存儲方式，以行序為主存儲其非零元素，第一個非零元素A[1,1]存儲在數(shù)組B[0]中，若A[10,5]在數(shù)組B中的存儲位置為k，則A[8,5]在數(shù)組B中的存儲位置為（）。A.k-18B.k-17C.k-16D.k-159、棧是一種特殊的線性表，遵循先進后出的原則。當一個棧已滿，再進行入棧操作時，通常會發(fā)生什么情況？A.覆蓋棧頂元素B.產(chǎn)生溢出錯誤C.新建一個更大的棧D.自動擴展棧的容量10、在一個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)+8d11、對于一個具有n個元素的哈希表，負載因子（loadfactor）為0.7，當表中元素數(shù)量超過一定閾值時需要進行擴容。以下關(guān)于擴容操作的時間復雜度的描述，哪一個是恰當?shù)?？A.O(1)B.O(n)C.O(logn)D.O(nlogn)12、數(shù)組是一種常見的數(shù)據(jù)結(jié)構(gòu)，它具有固定的大小和連續(xù)的存儲位置。以下關(guān)于數(shù)組的說法中，錯誤的是？（）A.數(shù)組可以通過下標快速訪問其中的元素。B.數(shù)組的插入和刪除操作比較耗時，因為需要移動大量的元素。C.數(shù)組可以存儲不同類型的數(shù)據(jù)元素。D.數(shù)組的長度在創(chuàng)建后不能改變。13、在一個具有n個元素的順序表中，若要在第i個位置（1<=i<=n+1）插入一個新元素，需要移動的元素個數(shù)最少為（）。A.0B.i-1C.n-iD.n-i+114、在一個具有n個頂點的無向圖中，使用廣度優(yōu)先遍歷算法。以下關(guān)于遍歷過程中使用的輔助隊列的空間復雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(n^2)15、在一個堆排序中，最大堆用于升序排序，最小堆用于降序排序。那么對于一個初始無序的數(shù)組，構(gòu)建最大堆的時間復雜度是多少？（）A.O(n)B.O(log?n)C.O(nlog?n)D.O(n2)16、在一個具有n個元素的鏈表中，訪問第i個元素的時間復雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、對于一個具有n個頂點的無向圖，若其所有頂點的度之和為20，則該圖的邊數(shù)為（）。A.5B.10C.15D.2018、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEABC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EACDB19、對于一個具有n個元素的有序鏈表，進行折半查找，其時間復雜度為？A.O(logn)B.O(nlogn)C.O(n)D.不能進行折半查找20、在一棵二叉搜索樹中，刪除一個有兩個子節(jié)點的節(jié)點時，通常采用的方法是：A.用左子樹的最大值替代該節(jié)點B.用右子樹的最小值替代該節(jié)點C.隨機選擇左子樹或右子樹的節(jié)點替代D.不進行替代，直接刪除二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述在一個具有n個頂點的無向圖中，如何使用廣度優(yōu)先搜索算法來生成連通分量。2、（本題10分）數(shù)組的排序算法中，計數(shù)排序的實現(xiàn)過程是怎樣的？時間復雜度和空間復雜度分別是多少？適用于哪些情況？3、（本題10分）闡述并查集中如何快速判斷兩個集合是否相交。4、（本題10分）在一個雙向鏈表中，如何在指