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

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

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