鄭州航空工業(yè)管理學院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁鄭州航空工業(yè)管理學院

《數(shù)據(jù)結(jié)構(gòu)》2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下關(guān)于串的描述，錯誤的是：A.串是一種特殊的線性表B.串的長度是指串中字符的個數(shù)C.空串和空格串是相同的概念D.串的存儲方式有順序存儲和鏈式存儲2、對于一個有向無環(huán)圖，進行拓撲排序可以得到一個線性的序列。以下關(guān)于拓撲排序的說法，錯誤的是？（）A.可以使用深度優(yōu)先搜索來實現(xiàn)B.結(jié)果可能不唯一C.若存在回路則無法進行拓撲排序D.其時間復(fù)雜度為O(n2)3、在一個容量為10的順序存儲的循環(huán)隊列中，若front=4，rear=8，則此時隊列中元素的個數(shù)為：A.4B.5C.6D.74、對于一個用數(shù)組實現(xiàn)的小根堆，若要將堆頂元素與最后一個元素交換，然后重新調(diào)整堆，以下關(guān)于調(diào)整的方向，哪一項是正確的？A.從堆頂向下調(diào)整B.從堆底向上調(diào)整C.先從堆頂向下調(diào)整，再從堆底向上調(diào)整D.以上都不對5、對于一個具有n個元素的無序數(shù)組，使用快速排序算法進行排序，在平均情況下的空間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實現(xiàn)集合的交集運算，并具有較低的時間復(fù)雜度？A.鏈表B.二叉搜索樹C.哈希表D.并查集7、在一個具有n個元素的無序數(shù)組中，使用冒泡排序進行排序。以下關(guān)于冒泡排序的時間復(fù)雜度的描述，哪一項是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)8、在一個具有n個節(jié)點的有向圖中，若存在環(huán)，則使用拓撲排序算法會出現(xiàn)什么情況？A.正常完成排序B.無法完成排序C.排序結(jié)果不準確D.以上都不對9、在一個具有n個元素的無序數(shù)組中，采用冒泡排序進行排序，在最壞情況下，需要比較的次數(shù)為（）。A.n-1B.n(n-1)/2C.n(n+1)/2D.n^210、已知一個圖的鄰接表如下所示，則從頂點V1出發(fā)進行廣度優(yōu)先遍歷，可能得到的頂點訪問序列是（）。V1:->V2->V3V2:->V4V3:->V4->V5V4:->V5V5:A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V4,V3,V5D.V1,V4,V2,V3,V511、在一個具有n個節(jié)點的二叉樹中，若采用中序遍歷得到的節(jié)點序列是有序的，則該二叉樹可能是什么類型？A.滿二叉樹B.完全二叉樹C.二叉搜索樹D.以上都有可能12、一個有序序列為{12,18,24,35,47,50,62,83,90,115,134}，當用二分法查找值為90的元素時，需要比較的次數(shù)是（）。A.1B.2C.3D.413、在一個具有n個頂點和e條邊的無向圖中，使用克魯斯卡爾（Kruskal）算法生成最小生成樹。以下關(guān)于該算法的時間復(fù)雜度的描述，哪一項是正確的？A.O(nlogn)B.O(eloge)C.O(elogn)D.O(n^2)14、對于一個具有n個頂點和e條邊的無向圖，使用深度優(yōu)先搜索算法進行遍歷。以下關(guān)于算法中使用的標記數(shù)組的空間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(n)C.O(e)D.O(n^2)15、在一個具有n個元素的有序數(shù)組中，使用二分查找算法查找一個特定元素，其時間復(fù)雜度為？（）A.O(n)B.O(log?n)C.O(n2)D.O(nlog?n)16、在一個具有n個元素的循環(huán)雙鏈表中，若要在表頭插入一個新元素，以下關(guān)于插入操作的時間復(fù)雜度的描述，哪一項是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、在一個具有n個元素的雙向鏈表中，刪除一個指定節(jié)點，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)18、已知一個哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測法處理沖突。若依次插入關(guān)鍵字31、25、19、49、37、21、13、17，則在查找關(guān)鍵字19時需要進行幾次比較？（）A.1B.2C.3D.419、對于一個用鄰接矩陣存儲的圖，若要判斷兩個頂點之間是否存在邊，時間復(fù)雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)20、在數(shù)據(jù)結(jié)構(gòu)中，對于線性表的順序存儲和鏈式存儲，以下說法正確的是：順序存儲結(jié)構(gòu)可以隨機訪問元素，但插入和刪除操作效率較低；鏈式存儲結(jié)構(gòu)插入和刪除操作方便，但不能隨機訪問。那么在頻繁進行插入和刪除操作的情況下，應(yīng)優(yōu)先選擇哪種存儲結(jié)構(gòu)？（）A.順序存儲B.鏈式存儲C.兩者均可D.無法確定二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋二叉樹的前序遍歷、中序遍歷和后序遍歷的定義，并分別闡述其遞歸和非遞歸的實現(xiàn)方法。2、（本題10分）詳細論述在利用哈希表存儲整數(shù)數(shù)據(jù)時，如何確定哈希表的大小，以及如何處理哈希沖突以提高存儲和查找效率。3、（本題10分）詳細闡述如何使用計數(shù)排序算法對一個具有n個元素的數(shù)組進行排序，給出算法步驟和適用條件。4、（本題10分）詳細闡述如何在一個具有n個元素的無序數(shù)組中，使用插入排序算法進行排序，分析其時間復(fù)雜度和空間復(fù)