青島濱海學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)青島濱海學(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è)具有n個(gè)元素的有序單鏈表中，進(jìn)行插入操作時(shí)，平均需要移動(dòng)的元素個(gè)數(shù)約為？A.n/2B.nC.lognD.12、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹中，其葉子節(jié)點(diǎn)的數(shù)量大約為（）A.n/2B.n/4C.n/8D.n/2-13、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)，通過(guò)哈希函數(shù)將關(guān)鍵字映射到存儲(chǔ)位置。關(guān)于哈希沖突的解決方法，錯(cuò)誤的是（）A.開放定址法通過(guò)尋找空閑位置來(lái)解決沖突B.鏈地址法將沖突的元素存儲(chǔ)在鏈表中C.再哈希法通過(guò)更換哈希函數(shù)來(lái)解決沖突D.哈希沖突無(wú)法避免，且對(duì)查找效率沒有影響4、以下哪種數(shù)據(jù)結(jié)構(gòu)可以快速判斷一個(gè)元素是否在集合中？A.鏈表B.二叉搜索樹C.哈希表D.棧5、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)表達(dá)式樹？A.二叉樹B.鏈表C.棧D.隊(duì)列6、設(shè)有一個(gè)20階的下三角矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)其非零元素，第一個(gè)非零元素A[1,1]存儲(chǔ)在數(shù)組B[0]中，若A[10,5]在數(shù)組B中的存儲(chǔ)位置為k，則A[8,5]在數(shù)組B中的存儲(chǔ)位置為（）。A.k-18B.k-17C.k-16D.k-157、在一個(gè)用鏈表實(shí)現(xiàn)的棧中，若要獲取棧底元素的值，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、對(duì)于一個(gè)棧，若入棧序列為1、2、3、4、5，在入棧過(guò)程中可以出棧，則下列不可能的出棧序列是：A.54321B.45321C.12345D.314259、設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前插入一個(gè)新元素，并且移動(dòng)元素的平均次數(shù)為n/2，則插入算法的平均時(shí)間復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)10、在一棵完全二叉樹中，若節(jié)點(diǎn)個(gè)數(shù)為n，那么其葉子節(jié)點(diǎn)的個(gè)數(shù)大約為多少？（）A.n/2B.n/4C.(n+1)/2D.n/311、對(duì)于一個(gè)用鄰接矩陣存儲(chǔ)的圖，若要判斷兩個(gè)頂點(diǎn)之間是否存在邊，時(shí)間復(fù)雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)12、在一個(gè)用鏈表實(shí)現(xiàn)的隊(duì)列中，若要?jiǎng)h除隊(duì)尾元素，需要進(jìn)行哪些操作？A.遍歷鏈表找到隊(duì)尾元素并刪除B.將隊(duì)尾元素的前一個(gè)元素設(shè)為隊(duì)尾C.直接刪除隊(duì)尾元素D.以上都不對(duì)13、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖，其鄰接矩陣中至少有（）個(gè)非零元素。A.nB.n-1C.n(n-1)D.n(n-1)/214、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉算法求最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)15、若要對(duì)一個(gè)具有n個(gè)元素的無(wú)序數(shù)組進(jìn)行排序，以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序16、在數(shù)據(jù)結(jié)構(gòu)中，鏈表的每個(gè)節(jié)點(diǎn)通常包含數(shù)據(jù)域和指針域。若要在一個(gè)單向鏈表中刪除一個(gè)指定節(jié)點(diǎn)，以下哪種操作是關(guān)鍵步驟？A.修改被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的指針B.修改被刪除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)的指針C.釋放被刪除節(jié)點(diǎn)的內(nèi)存D.以上都是17、在一個(gè)長(zhǎng)度為n的順序表中，刪除第i個(gè)元素（1<=i<=n）時(shí)，需要移動(dòng)的元素個(gè)數(shù)為：A.n-iB.i-1C.n-i+1D.i18、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中，若采用中序遍歷得到的節(jié)點(diǎn)序列是有序的，則該二叉樹可能是什么類型？A.滿二叉樹B.完全二叉樹C.二叉搜索樹D.以上都有可能19、隊(duì)列也是一種常見的數(shù)據(jù)結(jié)構(gòu)，遵循先進(jìn)先出的原則。對(duì)于一個(gè)循環(huán)隊(duì)列，以下說(shuō)法不正確的是（）A.隊(duì)頭指針和隊(duì)尾指針的移動(dòng)需要考慮循環(huán)的情況B.當(dāng)隊(duì)頭指針等于隊(duì)尾指針時(shí)，隊(duì)列為空C.可以通過(guò)犧牲一個(gè)存儲(chǔ)單元來(lái)區(qū)分隊(duì)列空和隊(duì)列滿的情況D.循環(huán)隊(duì)列可以避免假溢出的問題20、數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型（ADT）可以用于提高代碼的可維護(hù)性和可擴(kuò)展性，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.ADT使得數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)與使用分離，用戶只需要關(guān)心數(shù)據(jù)結(jié)構(gòu)的操作集合，而不需要關(guān)心其內(nèi)部實(shí)現(xiàn)。B.ADT可以用多種編程語(yǔ)言實(shí)現(xiàn)，不同的實(shí)現(xiàn)方式可能會(huì)有不同的性能和特點(diǎn)。C.ADT的操作集合應(yīng)該具有明確的語(yǔ)義和規(guī)范，以便用戶正確地使用數(shù)據(jù)結(jié)構(gòu)。D.ADT只適用于線性數(shù)據(jù)結(jié)構(gòu)，不適用于非線性數(shù)據(jù)結(jié)構(gòu)。二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）請(qǐng)說(shuō)明二叉搜索樹的定義和性質(zhì)，闡述其插入、刪除操作的過(guò)程，并分析在最壞情況下二叉搜索樹的性能。2、（本題10分）闡述如何使用隊(duì)列實(shí)現(xiàn)層次遍歷二叉樹的操作，分析算法的步驟和時(shí)間復(fù)雜度。3、（本題10分）詳細(xì)闡述如何使用冒泡排序算法對(duì)一個(gè)具有n個(gè)元素的數(shù)組進(jìn)行排序，分析其最優(yōu)情況和最壞情況下的時(shí)間復(fù)雜度。4、（本題10分）詳細(xì)闡述如何在一個(gè)字符