吉首大學(xué)《數(shù)據(jù)結(jié)構(gòu)B》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁吉首大學(xué)《數(shù)據(jù)結(jié)構(gòu)B》

2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個長度為n的順序表中，刪除第i個元素（1<=i<=n）時，需要移動的元素個數(shù)為：A.n-iB.i-1C.n-i+1D.i2、在一個具有n個元素的無序數(shù)組中，使用冒泡排序進(jìn)行排序。以下關(guān)于冒泡排序的時間復(fù)雜度的描述，哪一項是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)3、在一個具有n個節(jié)點的二叉排序樹中，刪除一個節(jié)點后，為了保持二叉排序樹的性質(zhì)，可能需要進(jìn)行哪些操作？A.僅調(diào)整刪除節(jié)點的子樹B.從根節(jié)點開始重新調(diào)整C.調(diào)整整個樹的結(jié)構(gòu)D.以上都有可能4、一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲，其空間復(fù)雜度為？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)5、在一個棧中，若入棧序列為1,2,3,4，且在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.176、若一個圖的廣度優(yōu)先遍歷序列為ABCDEFG，則其深度優(yōu)先遍歷序列可能為？（）A.ABDCEFGB.ACBDEFGC.ADBCEFGD.AECBDFG7、在一個具有n個元素的大頂堆中，若要將堆頂元素與最后一個元素交換，然后調(diào)整堆，其時間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)8、在一個鏈隊列中，假設(shè)隊頭指針為front，隊尾指針為rear，刪除隊頭元素的操作是：A.front=front->nextB.rear=rear->nextC.front->next=NULLD.rear->next=NULL9、以下關(guān)于哈希表沖突解決方法的描述，哪一項是不正確的？（）A.鏈地址法會增加存儲空間的開銷B.開放定址法的查找效率一定高于鏈地址法C.再哈希法可以減少沖突的發(fā)生D.建立公共溢出區(qū)可以存儲發(fā)生沖突的元素10、以下關(guān)于樹的存儲結(jié)構(gòu)的描述，哪一項是不正確的？（）A.孩子兄弟表示法可以方便地實現(xiàn)樹的遍歷B.雙親表示法便于查找一個節(jié)點的雙親節(jié)點C.孩子鏈表表示法在處理多叉樹時空間利用率較高D.以上存儲結(jié)構(gòu)在時間復(fù)雜度上沒有明顯差異11、棧是一種特殊的線性表，其操作遵循后進(jìn)先出原則。若一個棧的初始狀態(tài)為空，現(xiàn)在依次將元素1、2、3、4、5入棧，然后再依次出棧，那么出棧的順序是什么？（）A.12345B.54321C.32154D.2154312、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時進(jìn)行先序遍歷，比較節(jié)點值B.同時進(jìn)行中序遍歷，比較節(jié)點值C.同時進(jìn)行后序遍歷，比較節(jié)點值D.比較兩棵樹的節(jié)點數(shù)量13、設(shè)有一個具有n個頂點的帶權(quán)無向圖，使用普里姆（Prim）算法求最小生成樹。在算法執(zhí)行過程中，需要選擇一個頂點作為起始點。以下關(guān)于起始點選擇對算法時間復(fù)雜度的影響，哪一個是恰當(dāng)?shù)?？A.起始點的選擇對時間復(fù)雜度沒有影響B(tài).選擇不同的起始點可能導(dǎo)致時間復(fù)雜度不同C.選擇頂點度最小的作為起始點可以降低時間復(fù)雜度D.選擇頂點度最大的作為起始點可以降低時間復(fù)雜度14、對于一個具有n個元素的有序鏈表，若要在其中查找一個特定元素，其平均時間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)15、對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A.nB.n^2C.n(n-1)D.n(n+1)16、對于一個具有n個元素的有序雙向鏈表，查找中間元素的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、對于一個用鏈表表示的線性表，在表頭插入一個新元素和在表尾插入一個新元素，哪個操作更復(fù)雜？A.表頭插入B.表尾插入C.復(fù)雜度相同D.取決于鏈表長度18、對于一個具有n個節(jié)點的紅黑樹，插入一個新節(jié)點后，調(diào)整樹的結(jié)構(gòu)以保持紅黑樹性質(zhì)，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，若要表示一個有向圖，通?？梢允褂媚姆N存儲結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.以上均可20、設(shè)有一個具有n個頂點的有向圖，采用鄰接表存儲。若要計算每個頂點的出度，以下關(guān)于操作的時間復(fù)雜度的描述，哪一項是恰當(dāng)?shù)?？A.O(n)B.O(n+e)C.O(n^2)D.O(e)二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述在樹的遍歷優(yōu)化中，如何利用線索化和緩存機(jī)制提高性能。2、（本題10分）對于一個用鏈表實現(xiàn)的雙向循環(huán)隊列，說明其入隊、出隊操作的實現(xiàn)方法，以及如何判斷隊列是否為空或已滿。3、（本題10分）詳細(xì)說明如何在一個具有n個頂點的圖中，使用鄰接矩陣存儲結(jié)構(gòu)判斷兩個頂點之間是否存在邊，并分析其時間復(fù)雜度。4、（本題10分）在一個二叉樹中，如何判斷兩棵二叉樹是否相同