惠州學院《數據結構》2021-2022學年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁惠州學院

《數據結構》2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個節(jié)點的無向完全圖，其邊的數量為多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/22、在一個具有n個節(jié)點的二叉排序樹中，刪除一個節(jié)點后，為了保持二叉排序樹的性質，可能需要進行哪些操作？A.僅調整刪除節(jié)點的子樹B.從根節(jié)點開始重新調整C.調整整個樹的結構D.以上都有可能3、設有一個廣義表L=((a,b),c,(d,e))，其表頭和表尾分別為？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)4、在一個棧中，若入棧序列為1,2,3,4，且在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.175、在一個具有n個元素的有序數組中，采用插入排序進行排序，在最好情況下，需要比較的次數為（）。A.n-1B.nC.0D.n(n-1)/26、若一個圖的廣度優(yōu)先遍歷序列為ABCDEFG，則其深度優(yōu)先遍歷序列可能為？（）A.ABDCEFGB.ACBDEFGC.ADBCEFGD.AECBDFG7、對于一個具有n個元素的快速排序，每次劃分選取的基準元素不同，對排序的時間復雜度有何影響？（）A.沒有影響B(tài).可能會提高C.可能會降低D.以上都不對8、在一個m行n列的二維數組中，元素存儲的地址計算公式為LOC(aij)=LOC(a11)+[(i-1)*n+(j-1)]*d，其中d為每個元素所占的存儲單元數。若按行優(yōu)先存儲，則a23的地址為？（）A.LOC(a11)+5dB.LOC(a11)+6dC.LOC(a11)+7dD.LOC(a11)+8d9、對于一個具有n個節(jié)點的無向連通圖，其生成樹的邊數為（）A.n-1B.nC.n+1D.2n10、在一個具有n個節(jié)點的無向圖中，若要判斷兩個節(jié)點之間是否存在路徑，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.普里姆算法D.克魯斯卡爾算法11、對于一個具有n個節(jié)點的二叉排序樹，刪除一個節(jié)點后，重新調整為二叉排序樹，其時間復雜度最壞情況下為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、對于一個具有n個頂點的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同13、在一個鏈式存儲的棧中，若棧頂指針為top，要判斷棧是否為空，應判斷？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL14、已知一個有序表為{12,25,30,45,50,60,70,80}，若采用折半查找法查找值為45的元素，需要比較多少次？（）A.1B.2C.3D.415、在一個具有n個頂點的無向完全圖中，每個頂點的度為多少？（）A.n-1B.nC.2(n-1)D.2n16、對于一個具有n個頂點和e條邊的有向圖，采用鄰接表存儲，進行深度優(yōu)先遍歷。以下關于遍歷的時間復雜度的描述，哪一個是恰當的？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)17、在一個具有n個元素的雙向鏈表中，在p所指的節(jié)點之后插入一個新節(jié)點q，其操作步驟為（）。A.q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;B.q->next=p->next;q->prior=p;p->next=q;p->next->prior=q;C.p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;D.p->next->prior=q;q->next=p->next;q->prior=p;p->next=q;18、在圖的存儲結構中，十字鏈表主要用于存儲有向圖，以下關于十字鏈表的特點，描述不正確的是（）A.既能方便地訪問出邊，也能方便地訪問入邊B.存儲空間比鄰接表節(jié)省C.對于刪除邊的操作比較復雜D.不適合用于稀疏有向圖19、在一個具有n個元素的順序表中，若要在第i個位置（1<=i<=n+1）插入一個新元素，需要移動的元素個數最少為（）。A.0B.i-1C.n-iD.n-i+120、在一個具有n個元素的順序存儲的線性表中，要在第i個位置插入一個新元素（1<=i<=n+1），需要移動的元素個數約為？A.n-iB.iC.n-i+1D.n-i-1二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細闡述如何在一個字符串中進行字符串匹配的模糊搜索。2、（本題10分）論述如何利用并查集解決島嶼數量問題，給出算法思路和代碼實現。3、（本題10分）解釋在一個帶權無向圖中，如何使用弗洛伊德算法求解任意兩點之間的最短路徑，說明算法的空間復雜度和時間復雜度。4、（本題10分）對于一個用哈希表存儲的整數集合，解釋如何實現集合的交集、并集和差集運算，給出算法