浙江工業(yè)大學(xué)之江學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)浙江工業(yè)大學(xué)之江學(xué)院

《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表中，若要?jiǎng)h除表頭結(jié)點(diǎn)，需要修改幾個(gè)指針？（）A.0B.1C.2D.32、對(duì)于一個(gè)具有n個(gè)元素的無(wú)序鏈表，若要對(duì)其進(jìn)行排序，以下哪種排序算法較為合適？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序3、在一個(gè)順序存儲(chǔ)的棧中，若棧頂指針top為-1，則表示棧（）A.已滿B.為空C.已損壞D.無(wú)法確定4、若一個(gè)棧的輸入序列為1,2,3,4,5，不可能得到的輸出序列是？（）A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,55、以下哪種數(shù)據(jù)結(jié)構(gòu)可以高效地支持集合的并、交、差等操作？A.二叉搜索樹(shù)B.哈希表C.并查集D.平衡二叉樹(shù)6、在一個(gè)具有n個(gè)頂點(diǎn)的有向無(wú)環(huán)圖中，使用拓?fù)渑判蛩惴?，其結(jié)果的唯一性如何？A.一定唯一B.可能不唯一C.取決于頂點(diǎn)的編號(hào)D.以上都不對(duì)7、若要對(duì)100個(gè)元素進(jìn)行排序，以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.選擇排序C.插入排序D.歸并排序8、在數(shù)據(jù)結(jié)構(gòu)中，AVL樹(shù)的刪除操作比插入操作更復(fù)雜，以下關(guān)于刪除操作的描述，錯(cuò)誤的是（）A.可能需要進(jìn)行多次旋轉(zhuǎn)來(lái)保持平衡B.首先找到要?jiǎng)h除的節(jié)點(diǎn)C.刪除后不需要調(diào)整樹(shù)的結(jié)構(gòu)D.要考慮刪除節(jié)點(diǎn)的子樹(shù)情況9、在一個(gè)具有n個(gè)元素的無(wú)序數(shù)組中，使用順序查找算法查找一個(gè)特定元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.nlogn10、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的存儲(chǔ)？A.鄰接矩陣和鄰接表B.二叉樹(shù)和鏈表C.棧和隊(duì)列D.數(shù)組和哈希表11、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的平衡二叉樹(shù)，插入一個(gè)新節(jié)點(diǎn)并調(diào)整平衡，其平均時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、在一個(gè)棧中，若入棧序列為1,2,3,4，且在入棧過(guò)程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.1713、以下關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的描述，哪一項(xiàng)是正確的？（）A.鄰接矩陣適合存儲(chǔ)稀疏圖B.鄰接表在存儲(chǔ)稠密圖時(shí)空間效率較高C.十字鏈表適合存儲(chǔ)有向圖D.以上都不正確14、已知一個(gè)哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測(cè)法處理沖突。若依次插入關(guān)鍵字31、25、19、49、37、21、13、17，則在查找關(guān)鍵字19時(shí)需要進(jìn)行幾次比較？（）A.1B.2C.3D.415、在數(shù)據(jù)結(jié)構(gòu)中，使用棧來(lái)實(shí)現(xiàn)表達(dá)式求值，以下關(guān)于表達(dá)式求值的過(guò)程，描述錯(cuò)誤的是（）A.遇到操作數(shù)入棧B.遇到運(yùn)算符時(shí)，彈出棧頂?shù)膬蓚€(gè)操作數(shù)進(jìn)行計(jì)算C.括號(hào)不影響求值的順序D.最終棧頂元素即為表達(dá)式的結(jié)果16、一棵完全二叉樹(shù)的第5層（根為第1層）有16個(gè)葉子節(jié)點(diǎn)，則該完全二叉樹(shù)的節(jié)點(diǎn)總數(shù)最少為（）。A.47B.55C.63D.6417、對(duì)于一個(gè)用鄰接矩陣存儲(chǔ)的圖，若要判斷兩個(gè)頂點(diǎn)之間是否存在邊，時(shí)間復(fù)雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)18、對(duì)于一個(gè)循環(huán)隊(duì)列，若隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAX_SIZE，那么判斷隊(duì)空的條件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-119、對(duì)于一個(gè)具有n個(gè)元素的冒泡排序，若要交換相鄰兩個(gè)元素，平均需要移動(dòng)多少次？（）A.0B.1C.2D.320、在數(shù)據(jù)結(jié)構(gòu)中，字典樹(shù)（Trie樹(shù)）常用于字符串的存儲(chǔ)和查找，以下關(guān)于字典樹(shù)的特點(diǎn)，不正確的是（）A.對(duì)于前綴相同的字符串可以節(jié)省存儲(chǔ)空間B.查找操作的時(shí)間復(fù)雜度與字符串長(zhǎng)度有關(guān)C.適合用于詞頻統(tǒng)計(jì)D.插入和刪除操作比較復(fù)雜二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)說(shuō)明如何在一個(gè)二叉樹(shù)中進(jìn)行后序遍歷的多線程實(shí)現(xiàn)，給出算法步驟和實(shí)現(xiàn)代碼，并分析其線程同步和效率。2、（本題10分）描述二叉樹(shù)的遍歷算法在二叉樹(shù)的路徑總和問(wèn)題、節(jié)點(diǎn)間最大距離問(wèn)題中的應(yīng)用。3、（本題10分）比較冒泡排序和快速排序在對(duì)小規(guī)模數(shù)據(jù)的處理速度。4、（本題10分）詳細(xì)闡述在利用二叉搜索樹(shù)進(jìn)行查找操作時(shí)，如何優(yōu)化查找效率，以及在不平衡情況下如何進(jìn)行調(diào)整。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20