湖北工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁湖北工程學(xué)院

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在二叉搜索樹中，左子樹的所有節(jié)點(diǎn)值都小于根節(jié)點(diǎn)值，右子樹的所有節(jié)點(diǎn)值都大于根節(jié)點(diǎn)值。若要查找一個(gè)特定值的節(jié)點(diǎn)，以下哪種方法效率最高？A.先序遍歷B.中序遍歷C.后序遍歷D.以上效率相同2、在數(shù)據(jù)結(jié)構(gòu)中，桶排序是一種外部排序算法，以下關(guān)于桶排序的描述，錯(cuò)誤的是（）A.要求輸入數(shù)據(jù)具有特定的分布B.時(shí)間復(fù)雜度為O(n)C.空間復(fù)雜度較高D.適用于大規(guī)模數(shù)據(jù)排序3、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹，若按照層次遍歷的順序?qū)⒐?jié)點(diǎn)編號為1到n，已知編號為i的節(jié)點(diǎn)有左孩子，則其左孩子的編號為？A.2iB.2i+1C.i*2D.i/24、以下哪種數(shù)據(jù)結(jié)構(gòu)可以高效地支持集合的并、交、差等操作？A.二叉搜索樹B.哈希表C.并查集D.平衡二叉樹5、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)文件系統(tǒng)的目錄結(jié)構(gòu)？A.二叉樹B.多叉樹C.鏈表D.棧6、圖的存儲(chǔ)方式和遍歷方式對圖的操作效率有很大影響，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.鄰接矩陣適合存儲(chǔ)稠密圖，查找邊的時(shí)間復(fù)雜度為O(1)，但空間復(fù)雜度較高。B.鄰接表適合存儲(chǔ)稀疏圖，插入邊和刪除邊的時(shí)間復(fù)雜度為O(1)，但查找邊的時(shí)間復(fù)雜度較高。C.深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本遍歷方式，它們的時(shí)間復(fù)雜度都為O(n+m)，其中n是頂點(diǎn)數(shù)，m是邊數(shù)。D.圖的存儲(chǔ)方式和遍歷方式一旦確定，就不能再改變，否則會(huì)影響圖的操作效率。7、在一個(gè)帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接已選頂點(diǎn)和未選頂點(diǎn)的權(quán)值最小的邊C.任意一條邊D.以上都不對8、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖中，采用鄰接表存儲(chǔ)，求頂點(diǎn)的入度的時(shí)間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)9、以下哪種排序算法的空間復(fù)雜度最低？A.歸并排序B.快速排序C.冒泡排序D.插入排序10、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)LRU（最近最少使用）緩存淘汰策略？（）A.隊(duì)列B.棧C.哈希表D.雙向鏈表11、對于一個(gè)具有n個(gè)元素的歸并排序，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)12、在一個(gè)大根堆中，刪除堆頂元素后，為了重新調(diào)整為大根堆，需要進(jìn)行的操作是？（）A.將最后一個(gè)元素移到堆頂，然后從堆頂向下調(diào)整B.將堆中所有元素重新排序C.將堆頂元素與最后一個(gè)元素交換，然后從堆頂向下調(diào)整D.無需調(diào)整13、對于一個(gè)具有n個(gè)元素的有序單鏈表，要查找一個(gè)值為x的元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.114、在一個(gè)具有n個(gè)元素的循環(huán)鏈表中，查找第i個(gè)元素（1<=i<=n），平均需要比較的次數(shù)為（）。A.nB.n/2C.(n+1)/2D.(n-1)/215、對于一個(gè)具有n個(gè)元素的有序數(shù)組，使用二分查找算法查找一個(gè)特定元素。以下關(guān)于二分查找的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)模緼.O(1)B.O(logn)C.O(n)D.O(nlogn)16、數(shù)組通常具有的兩種基本操作是：A.插入和刪除B.查找和修改C.遍歷和排序D.索引和賦值17、圖的存儲(chǔ)方式和遍歷方式可以用于解決很多實(shí)際問題，以下關(guān)于它們的應(yīng)用的說法中，錯(cuò)誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等。B.圖的鄰接表可以用于表示稀疏圖，如地圖、電路圖等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問題和最小生成樹問題等。D.圖的存儲(chǔ)方式和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。18、在一個(gè)具有n個(gè)元素的單鏈表中，若要在第i個(gè)位置（1<=i<=n）插入一個(gè)新元素，平均需要遍歷多少個(gè)節(jié)點(diǎn)？（）A.i-1B.iC.(i-1)/2D.i/219、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，其先序遍歷、中序遍歷和后序遍歷的結(jié)果都是唯一確定的，這個(gè)二叉樹一定是（）A.滿二叉樹B.完全二叉樹C.單支樹D.以上都不是20、在一個(gè)用鏈表實(shí)現(xiàn)的隊(duì)列中，若要實(shí)現(xiàn)隊(duì)列的遍歷操作，以下哪種方式較為合適？A.從隊(duì)頭開始，依次訪問每個(gè)節(jié)點(diǎn)B.從隊(duì)尾開始，依次向前訪問每個(gè)節(jié)點(diǎn)C.隨機(jī)訪問鏈表中的節(jié)點(diǎn)D.以上都不對二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)說明如何在一個(gè)帶權(quán)無向圖中計(jì)算兩個(gè)頂點(diǎn)之間的所有簡單路徑。2、（本題10分）詳細(xì)闡述如何在一個(gè)雙向鏈表中實(shí)現(xiàn)節(jié)點(diǎn)的快速插入和刪除操作。3、（本題10分）解釋如何在一個(gè)有序數(shù)組中進(jìn)行二分查找的同時(shí)統(tǒng)計(jì)目標(biāo)值出現(xiàn)的次數(shù)。4、（本題10分）闡述后綴樹在網(wǎng)絡(luò)流量分析中的