湖北工業(yè)大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷

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

《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個大根堆，若要刪除堆頂元素并保持堆的性質(zhì)，以下哪種操作是正確的？A.將堆底元素移到堆頂，然后從堆頂向下調(diào)整B.將堆頂元素直接刪除，不進行其他操作C.將堆頂元素與任意子節(jié)點交換，然后調(diào)整D.以上都不對2、在一個具有n個節(jié)點的二叉排序樹中，刪除一個節(jié)點后，為了保持二叉排序樹的性質(zhì)，可能需要進行哪些操作？A.僅調(diào)整刪除節(jié)點的子樹B.從根節(jié)點開始重新調(diào)整C.調(diào)整整個樹的結(jié)構(gòu)D.以上都有可能3、在一個哈希表中，負(fù)載因子越大，說明什么？A.哈希沖突越少B.存儲空間利用率越高C.查找效率越高D.以上都不對4、在一個用鏈表實現(xiàn)的隊列中，若要實現(xiàn)隊列的遍歷操作，以下哪種方式較為合適？A.從隊頭開始，依次訪問每個節(jié)點B.從隊尾開始，依次向前訪問每個節(jié)點C.隨機訪問鏈表中的節(jié)點D.以上都不對5、設(shè)有一個字符串S="helloworld"，要計算字符串S的長度（不包括結(jié)束符'\0'），以下函數(shù)正確的是？（）A.intlength(char*s){intcount=0;while(*s!='\0'){count++;s++;}returncount;}B.intlength(char*s){intcount=0;for(;*s!='\0';s++){count++;}returncount;}C.intlength(char*s){intcount=0;do{count++;s++;}while(*s!='\0');returncount;}D.intlength(char*s){intcount=0;while(s[count]!='\0'){count++;}returncount;}6、在一個循環(huán)鏈表中，若要刪除鏈表中的最后一個節(jié)點，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、對于一個具有n個頂點和e條邊的帶權(quán)有向圖，使用弗洛伊德（Floyd）算法求所有頂點對之間的最短路徑。以下關(guān)于該算法的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)模緼.O(n)B.O(n^2)C.O(n^3)D.O(e^3)8、以下哪種排序算法在元素基本有序的情況下性能最佳？A.快速排序B.冒泡排序C.插入排序D.堆排序9、以下關(guān)于并查集的描述，錯誤的是：A.并查集可以用于判斷兩個元素是否在同一個集合中B.并查集的查找操作時間復(fù)雜度較低C.并查集的合并操作時間復(fù)雜度較高D.并查集通常采用樹形結(jié)構(gòu)存儲10、對于一個采用順序存儲的棧，若棧頂指針top等于-1時，表示：A.棧滿B.?？誄.棧中只有一個元素D.棧中至少有一個元素11、在一個具有n個元素的無序數(shù)組中，使用選擇排序進行排序。以下關(guān)于選擇排序的時間復(fù)雜度的描述，哪一項是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)12、在數(shù)據(jù)結(jié)構(gòu)中，塊狀鏈表結(jié)合了鏈表和數(shù)組的優(yōu)點，以下關(guān)于塊狀鏈表的特點，描述不正確的是（）A.適合頻繁的插入和刪除操作B.可以提高隨機訪問的效率C.每個塊內(nèi)部是有序的D.空間復(fù)雜度比普通鏈表低13、在一個棧中，若入棧序列為1,2,3,4，且在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.1714、若對一棵二叉排序樹進行中序遍歷，得到的節(jié)點序列是一個遞增序列，則該二叉排序樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空15、在一個具有n個元素的無序數(shù)組中，使用冒泡排序進行排序。以下關(guān)于冒泡排序的時間復(fù)雜度的描述，哪一項是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)16、設(shè)有一個廣義表L=(a,(b,c),d)，其長度和深度分別為？（）A.3和2B.3和3C.4和2D.4和317、在一個具有n個元素的無序數(shù)組中，使用順序查找算法查找一個特定元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.nlogn18、在數(shù)據(jù)結(jié)構(gòu)中，使用隊列來實現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過程的描述，錯誤的是（）A.從起始節(jié)點開始入隊B.隊列為空時結(jié)束遍歷C.訪問節(jié)點時將其未訪問的鄰接節(jié)點入隊D.節(jié)點不會被重復(fù)訪問19、在一個具有n個節(jié)點的有向圖中，若存在多個入度為0的節(jié)點，進行拓?fù)渑判驎r，應(yīng)該選擇哪個節(jié)點作為起始節(jié)點？A.任意一個入度為0的節(jié)點B.編號最小的入度為0的節(jié)點C.編號最大的入度為0的節(jié)點D.以上都不對20、對于一個具有n個頂點和e條邊的帶權(quán)無向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)二、簡答題（本大題共4個小題，共40分)1、（本題10分）闡述哈希表的工作原理，包括哈希函數(shù)的設(shè)計和處理沖突的方法，并分析其查找效率。2、（本題10分）分析在數(shù)據(jù)結(jié)構(gòu)中，如何利用優(yōu)先隊列實現(xiàn)Dijkstra算法求解最短路徑問題。3、（本題10分）論述在動態(tài)規(guī)劃的求解過程中，如何通過備忘錄方法避免重復(fù)計算。4、（本題10分）論述跳表在插入操作中隨機層數(shù)生