保山學(xué)院《數(shù)據(jù)結(jié)構(gòu)實踐》2021-2022學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁保山學(xué)院

《數(shù)據(jù)結(jié)構(gòu)實踐》2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個元素的歸并排序，其時間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)2、對于一個具有n個元素的堆，進(jìn)行刪除堆頂元素的操作，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、對于一個循環(huán)隊列，若隊頭指針為front，隊尾指針為rear，隊列最大容量為MAX_SIZE，那么判斷隊空的條件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-14、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠高效地支持區(qū)間查詢操作？（）A.線段樹B.二叉搜索樹C.堆D.鏈表5、在一個具有n個節(jié)點的無向圖中，若邊的數(shù)量遠(yuǎn)遠(yuǎn)小于n(n-1)/2，則適合使用哪種存儲方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以6、以下關(guān)于線性表的描述，正確的是：A.線性表的元素在邏輯上和存儲上都必須是連續(xù)的B.線性表只能采用順序存儲結(jié)構(gòu)C.線性表的長度是固定不變的D.線性表可以是空表，即不含任何元素7、在一個具有n個頂點和e條邊的有向圖中，采用鄰接表存儲，求頂點的入度的時間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)8、在一個具有n個元素的循環(huán)鏈表中，查找第i個元素（1<=i<=n），平均需要遍歷的節(jié)點個數(shù)約為？A.n/2B.nC.2nD.n/49、在數(shù)據(jù)結(jié)構(gòu)中，雙向循環(huán)鏈表相較于單向鏈表，以下優(yōu)勢描述錯誤的是（）A.可以方便地反向遍歷B.插入和刪除節(jié)點的操作更簡單C.查找前一個節(jié)點的時間復(fù)雜度更低D.空間復(fù)雜度更低10、在一個具有n個頂點的無向圖中，若每個頂點的度均為k，則該圖的邊數(shù)為（）。A.nkB.nk/2C.(n-1)k/2D.(n+1)k/211、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時進(jìn)行先序遍歷，比較節(jié)點值B.同時進(jìn)行中序遍歷，比較節(jié)點值C.同時進(jìn)行后序遍歷，比較節(jié)點值D.比較兩棵樹的節(jié)點數(shù)量12、對于一個m行n列的二維數(shù)組，按行優(yōu)先存儲時，元素a[i][j]（0<=i<m,0<=j<n）的地址計算公式為：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i13、對于一個具有n個元素的堆，進(jìn)行堆排序。以下關(guān)于堆排序的平均時間復(fù)雜度和空間復(fù)雜度的描述，哪一個是準(zhǔn)確的？A.平均時間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(1)B.平均時間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(n)C.平均時間復(fù)雜度為O(logn)，空間復(fù)雜度為O(logn)D.平均時間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)14、對于一個具有n個元素的雙向循環(huán)鏈表，若要刪除第i個節(jié)點（1<=i<=n），平均需要修改多少個指針？（）A.2B.3C.4D.515、以下關(guān)于哈希沖突解決方法中二次探測法的描述，哪一項是不正確的？（）A.可以減少聚集現(xiàn)象B.探測的位置是連續(xù)的C.可能會出現(xiàn)找不到空閑位置的情況D.相比線性探測法，性能更優(yōu)16、在一個具有n個元素的最小堆中，若要將堆頂元素與堆底元素交換，然后調(diào)整堆的結(jié)構(gòu)，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、在數(shù)據(jù)結(jié)構(gòu)中，鏈表的反轉(zhuǎn)是一個常見的操作，以下關(guān)于鏈表反轉(zhuǎn)的實現(xiàn)方法，錯誤的是（）A.使用三個指針依次遍歷并調(diào)整節(jié)點的鏈接關(guān)系B.遞歸方式實現(xiàn)時不需要額外的輔助空間C.迭代方式的時間復(fù)雜度為O(n)D.遞歸方式的空間復(fù)雜度比迭代方式低18、在數(shù)據(jù)結(jié)構(gòu)中，伸展樹（SplayTree）通過自調(diào)整保持較好的性能，以下關(guān)于伸展樹的操作，不正確的是（）A.查找操作會將被查找的節(jié)點旋轉(zhuǎn)到根節(jié)點B.插入操作可能會引起多次旋轉(zhuǎn)C.伸展樹的平均性能較好D.伸展樹的空間復(fù)雜度較高19、以下哪種排序算法在平均情況下的時間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序20、在一個具有n個元素的無序數(shù)組中，采用冒泡排序進(jìn)行排序，在最壞情況下，需要比較的次數(shù)為（）。A.n-1B.n(n-1)/2C.n(n+1)/2D.n^2二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細(xì)說明在堆的應(yīng)用擴(kuò)展中，如何使用堆實現(xiàn)TopK問題的求解。2、（本題10分）深入分析在具有n個元素的有序數(shù)組中，如何進(jìn)行二分查找的遞歸實現(xiàn)，并給出時間復(fù)雜度和空間復(fù)雜度的分析。3、（本題10分）深入分析在具有n個頂點和e條邊的無向圖中，如何使用克魯斯卡爾（Kruskal）算法求解最小瓶頸生成樹，并說明其特點和應(yīng)用場景。4、（本題10分）深入解釋在具有n個頂點和e條邊的圖中，如何判斷圖是否連通，以及連通分量的