惠州學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁惠州學(xué)院《數(shù)據(jù)結(jié)構(gòu)》

2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、圖的存儲方式和遍歷方式對圖的操作效率有很大影響，以下關(guān)于它們的說法中，錯誤的是？（）A.鄰接矩陣適合存儲稠密圖，查找邊的時間復(fù)雜度為O(1)，但空間復(fù)雜度較高。B.鄰接表適合存儲稀疏圖，插入邊和刪除邊的時間復(fù)雜度為O(1)，但查找邊的時間復(fù)雜度較高。C.深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本遍歷方式，它們的時間復(fù)雜度都為O(n+m)，其中n是頂點數(shù)，m是邊數(shù)。D.圖的存儲方式和遍歷方式一旦確定，就不能再改變，否則會影響圖的操作效率。2、一棵完全二叉樹的第6層（根為第1層）有8個葉子節(jié)點，則該完全二叉樹的節(jié)點總數(shù)最多為（）。A.39B.56C.111D.1193、以下哪種數(shù)據(jù)結(jié)構(gòu)在處理頻繁的插入和刪除操作時，不需要移動大量元素？（）A.數(shù)組B.鏈表C.棧D.隊列4、在一個具有n個節(jié)點的完全二叉樹中，若底層從左到右依次編號，節(jié)點i的左孩子節(jié)點編號是多少（假設(shè)根節(jié)點編號為1）？A.2iB.2i+1C.i*2D.以上都不對5、設(shè)有一個帶權(quán)有向圖G=(V,E)，采用拓?fù)渑判蛩惴▽ζ溥M行排序，若得到的拓?fù)湫蛄形ㄒ?，則圖G一定是？（）A.有環(huán)圖B.無環(huán)圖C.強連通圖D.弱連通圖6、設(shè)有一個帶頭結(jié)點的單鏈表，頭指針為head，若要在第一個元素之前插入一個新元素，則需要執(zhí)行的操作是（）。A.s->next=head;head=s;B.s->next=head->next;head->next=s;C.head->next=s;s->next=head;D.s->next=head;s=head;7、對于一個具有n個元素的無序數(shù)組，使用插入排序進行排序，其最好情況下的時間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)8、以下哪種排序算法在最壞情況下的交換次數(shù)最少？A.冒泡排序B.快速排序C.選擇排序D.插入排序9、若一棵二叉樹的層次遍歷序列為ABCDEFGHI，則其可能的中序遍歷序列有多少種？（）A.1B.n!C.2^nD.不確定10、設(shè)有一個用鏈表實現(xiàn)的雙向循環(huán)鏈表，若要在其中一個節(jié)點之后插入一個新節(jié)點，以下關(guān)于插入操作的時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、在一個具有n個元素的數(shù)組中，進行冒泡排序，在最壞情況下，需要比較的次數(shù)為？（）A.n-1B.n(n-1)/2C.n2D.nlog?n12、對于一個循環(huán)隊列，若隊列的最大容量為m，當(dāng)前front指針為5，rear指針為2，則隊列中的元素個數(shù)為（）A.7B.3C.m-3D.m-713、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，若一個二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，那么它的后序遍歷序列是什么？（）A.BCAB.CBAC.CABD.ACB14、對于一個具有n個頂點和m條邊的有向圖，使用鄰接表存儲，其入度和出度的計算時間復(fù)雜度分別為（）A.O(n)和O(m)B.O(m)和O(n)C.O(n+m)和O(n+m)D.O(n^2)和O(n^2)15、在一個哈希表中，若采用線性探測法解決哈希沖突，當(dāng)發(fā)生沖突時，新元素會存儲在什么位置？A.沖突位置的下一個位置B.沖突位置C.隨機位置D.以上都不對16、若一個圖的鄰接矩陣對角線以下（不包括對角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強連通圖D.弱連通圖17、在一棵AVL樹中，進行插入操作后，可能導(dǎo)致樹失去平衡，此時需要進行的旋轉(zhuǎn)操作最多為（）A.1次B.2次C.logn次D.n次18、對于一個具有n個元素的堆，若要將其所有元素從小到大排序，最好的方法是？A.每次刪除堆頂元素并調(diào)整B.直接使用快速排序C.先構(gòu)建大頂堆再調(diào)整D.以上方法效率相同19、對于一個具有n個頂點的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時間復(fù)雜度為：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)20、在數(shù)據(jù)結(jié)構(gòu)中，桶排序是一種外部排序算法，以下關(guān)于桶排序的描述，錯誤的是（）A.要求輸入數(shù)據(jù)具有特定的分布B.時間復(fù)雜度為O(n)C.空間復(fù)雜度較高D.適用于大規(guī)模數(shù)據(jù)排序二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋數(shù)據(jù)結(jié)構(gòu)中棧的壓棧和彈棧操作的含義，并舉例說明其在實際中的應(yīng)用。2、（本題10分）比較計數(shù)排序和桶排序在空間復(fù)雜度上的差異，并分析原因。3、（本題10分）闡述如何在一個圖中找到兩個節(jié)點之間的所有路徑，給出算法步驟和實現(xiàn)代碼，并分析其時間復(fù)雜度。4、（本題10分）詳細(xì)說明如何對一個平衡二叉樹進行插入操作，并保持其平衡特性。三、設(shè)計題（本大題共2個小題，共20分)1、（本題1