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

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)賀州學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》

2022-2023學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的廣度優(yōu)先遍歷的輔助隊(duì)列？A.循環(huán)隊(duì)列B.鏈隊(duì)列C.優(yōu)先隊(duì)列D.雙端隊(duì)列2、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖，采用鄰接表存儲(chǔ)，進(jìn)行深度優(yōu)先遍歷。以下關(guān)于遍歷的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)模緼.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)3、在一棵度為4的樹(shù)中，度為4的節(jié)點(diǎn)個(gè)數(shù)為1，度為3的節(jié)點(diǎn)個(gè)數(shù)為2，度為2的節(jié)點(diǎn)個(gè)數(shù)為3，度為1的節(jié)點(diǎn)個(gè)數(shù)為4，葉子節(jié)點(diǎn)個(gè)數(shù)為（）。A.15B.16C.17D.184、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，若要判斷兩個(gè)頂點(diǎn)之間是否存在路徑，使用哪種算法較為合適？A.迪杰斯特拉算法B.弗洛伊德算法C.深度優(yōu)先遍歷或廣度優(yōu)先遍歷D.拓?fù)渑判?、在數(shù)據(jù)結(jié)構(gòu)中，使用棧來(lái)實(shí)現(xiàn)表達(dá)式求值，以下關(guān)于表達(dá)式求值的過(guò)程，描述錯(cuò)誤的是（）A.遇到操作數(shù)入棧B.遇到運(yùn)算符時(shí)，彈出棧頂?shù)膬蓚€(gè)操作數(shù)進(jìn)行計(jì)算C.括號(hào)不影響求值的順序D.最終棧頂元素即為表達(dá)式的結(jié)果6、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行刪除操作并調(diào)整堆的時(shí)間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、已知一棵二叉樹(shù)的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為：A.CBEFDGAB.CEBFDGAC.CBEFAGDD.CEBFAGD8、在一棵二叉搜索樹(shù)中，刪除一個(gè)有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)時(shí)，通常采用的方法是：A.用左子樹(shù)的最大值替代該節(jié)點(diǎn)B.用右子樹(shù)的最小值替代該節(jié)點(diǎn)C.隨機(jī)選擇左子樹(shù)或右子樹(shù)的節(jié)點(diǎn)替代D.不進(jìn)行替代，直接刪除9、在一個(gè)具有n個(gè)元素的鏈表中，若要在表頭插入一個(gè)新元素，平均需要修改幾個(gè)指針？（）A.1B.2C.nD.n+110、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的平衡二叉樹(shù)，插入一個(gè)新節(jié)點(diǎn)并調(diào)整平衡，其平均時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若存在頂點(diǎn)的入度為0，則該圖可能是：A.強(qiáng)連通圖B.弱連通圖C.非連通圖D.以上都不對(duì)12、設(shè)有一個(gè)棧S和一個(gè)隊(duì)列Q，初始時(shí)棧為空，隊(duì)列為{1,2,3,4,5}。經(jīng)過(guò)一系列入棧和出棧、入隊(duì)和出隊(duì)操作后，棧頂元素為3，此時(shí)隊(duì)列的頭元素為？（）A.1B.2C.4D.513、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，使用深度優(yōu)先搜索算法進(jìn)行遍歷。以下關(guān)于算法中使用的標(biāo)記數(shù)組的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(n)C.O(e)D.O(n^2)14、已知一棵二叉樹(shù)的后序遍歷序列為DABEC，中序遍歷序列為DEABC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EACDB15、在一個(gè)棧中，若入棧序列為1,2,3,4，且在入棧過(guò)程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.1716、若要對(duì)一棵二叉排序樹(shù)進(jìn)行中序遍歷，得到的序列是一個(gè)有序序列，這是因?yàn)槎媾判驑?shù)的定義具有什么特性？（）A.左子樹(shù)的值小于根節(jié)點(diǎn)，右子樹(shù)的值大于根節(jié)點(diǎn)B.左子樹(shù)和右子樹(shù)的深度相同C.每個(gè)節(jié)點(diǎn)的值都不同D.以上都不是17、圖的存儲(chǔ)方式和遍歷方式對(duì)圖的操作效率有很大影響，以下關(guān)于它們的說(shuō)法中，錯(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ì)影響圖的操作效率。18、設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)其下三角部分，第一個(gè)元素A[1,1]存儲(chǔ)在數(shù)組B[0]中，若A[8,5]在數(shù)組B中的存儲(chǔ)位置為k，則A[7,5]在數(shù)組B中的存儲(chǔ)位置為（）。A.k-13B.k-12C.k-11D.k-1019、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的無(wú)向完全圖，其邊的數(shù)量為多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/220、以下關(guān)于圖的遍歷算法的描述，哪一項(xiàng)是正確的？（）A.深度優(yōu)先遍歷和廣度優(yōu)先遍歷都能訪問(wèn)到圖中的所有節(jié)點(diǎn)B.深度優(yōu)先遍歷適合用于求解最短路徑問(wèn)題C.廣度優(yōu)先遍歷的空間復(fù)雜度低于深度優(yōu)先遍歷D.兩種遍歷算法的時(shí)間復(fù)雜度都與圖的邊數(shù)成正比二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）比較歸并排序和快速排序在對(duì)隨機(jī)數(shù)據(jù)的排序效果。2、（本題10分）詳細(xì)闡述基數(shù)排序算法的基本思想和適用場(chǎng)景，并說(shuō)明其時(shí)間復(fù)雜度。3、（本題10分）詳細(xì)論述在利用二叉樹(shù)存儲(chǔ)數(shù)據(jù)時(shí)，如何進(jìn)行前序遍歷、中序遍歷和后序遍歷，并給出相應(yīng)的遞歸和非遞歸實(shí)現(xiàn)代碼。4、（本題10分）詳細(xì)闡述B樹(shù)在文件系統(tǒng)中的應(yīng)用和優(yōu)化