北京師范大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2023-2024學(xué)年期末試卷

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

2023-2024學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、已知一個(gè)圖的鄰接矩陣如下所示：ABCDA0110B1011C1100D0100則該圖中頂點(diǎn)A的度為：A.1B.2C.3D.42、在一個(gè)具有n個(gè)元素的鏈表中，訪問第i個(gè)元素的時(shí)間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、排序算法的穩(wěn)定性和時(shí)間復(fù)雜度可以用于選擇合適的排序算法，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.穩(wěn)定性對于某些應(yīng)用場景非常重要，如對具有多個(gè)關(guān)鍵字的記錄進(jìn)行排序時(shí)。B.時(shí)間復(fù)雜度是衡量排序算法效率的重要指標(biāo)，不同的排序算法具有不同的時(shí)間復(fù)雜度。C.可以根據(jù)實(shí)際情況選擇穩(wěn)定的或不穩(wěn)定的排序算法，以及時(shí)間復(fù)雜度較低的排序算法。D.排序算法的穩(wěn)定性和時(shí)間復(fù)雜度只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。4、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字典操作，并且能夠快速查找、插入和刪除元素？（）A.棧B.隊(duì)列C.二叉搜索樹D.數(shù)組5、在一個(gè)m行n列的二維數(shù)組中，元素存儲(chǔ)的地址計(jì)算公式為LOC(aij)=LOC(a11)+[(i-1)*n+(j-1)]*d，其中d為每個(gè)元素所占的存儲(chǔ)單元數(shù)。若按行優(yōu)先存儲(chǔ)，則a23的地址為？（）A.LOC(a11)+5dB.LOC(a11)+6dC.LOC(a11)+7dD.LOC(a11)+8d6、在一個(gè)具有n個(gè)元素的有序單鏈表中，要查找一個(gè)特定元素，平均時(shí)間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)7、在一個(gè)具有n個(gè)元素的循環(huán)鏈表中，查找第i個(gè)元素（1<=i<=n），平均需要遍歷的節(jié)點(diǎn)個(gè)數(shù)約為？A.n/2B.nC.2nD.n/48、若一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBDAEGF，則其后序遍歷序列為？（）A.CDBGFEAB.CDBFGEAC.CDBAGFED.CDBEAGF9、對于一個(gè)用鏈表實(shí)現(xiàn)的棧，若要獲取棧中元素的個(gè)數(shù)，以下哪種方法效率較高？A.遍歷鏈表B.維護(hù)一個(gè)計(jì)數(shù)器C.以上效率相同D.以上都不對10、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若存在環(huán)，則使用拓?fù)渑判蛩惴〞?huì)？A.正常排序B.無法排序C.部分排序D.排序結(jié)果不確定11、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中，若每個(gè)節(jié)點(diǎn)都有左右孩子，則葉子節(jié)點(diǎn)的數(shù)量與度為2的節(jié)點(diǎn)數(shù)量有什么關(guān)系？A.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量+1B.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量-1C.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量D.以上都不對12、對于一個(gè)具有n個(gè)元素的哈希表，若采用鏈地址法處理沖突，以下關(guān)于查找操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、在一個(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.以上都不對14、對于一個(gè)具有n個(gè)元素的堆，進(jìn)行插入操作的時(shí)間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、圖的存儲(chǔ)方式有鄰接矩陣和鄰接表兩種，以下關(guān)于它們的特點(diǎn)的說法中，錯(cuò)誤的是？（）A.鄰接矩陣適合存儲(chǔ)稠密圖，空間復(fù)雜度為O(n^2)。B.鄰接表適合存儲(chǔ)稀疏圖，空間復(fù)雜度為O(n+m)，其中n是頂點(diǎn)數(shù)，m是邊數(shù)。C.鄰接矩陣的查找邊的時(shí)間復(fù)雜度為O(1)。D.鄰接表的插入邊和刪除邊的時(shí)間復(fù)雜度為O(n)。16、在一個(gè)具有n個(gè)元素的最小堆中，若要將堆頂元素與堆底元素交換，然后調(diào)整堆的結(jié)構(gòu)，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、若一棵二叉樹的先序遍歷序列和后序遍歷序列分別為ABC和CBA，則其中序遍歷序列為：A.BCAB.CABC.ABCD.無法確定18、在一個(gè)順序存儲(chǔ)的棧中，若要實(shí)現(xiàn)共享?xiàng)?，即兩個(gè)棧共用一個(gè)數(shù)組空間，以下關(guān)于棧頂指針的設(shè)置，哪一種方案較為合理？A.兩個(gè)棧的棧頂指針分別從數(shù)組的兩端向中間移動(dòng)B.兩個(gè)棧的棧頂指針都從數(shù)組的同一端開始移動(dòng)C.一個(gè)棧的棧頂指針從數(shù)組的開頭移動(dòng)，另一個(gè)從結(jié)尾移動(dòng)D.以上都可以19、若要對一個(gè)具有n個(gè)元素的數(shù)組進(jìn)行歸并排序，需要額外的輔助空間大小為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)20、在一個(gè)哈希表中，負(fù)載因子越大，說明什么？A.哈希沖突越少B.存儲(chǔ)空間利用率越高C.查找效率越高D.以上都不對二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，如何處理有向圖中的重邊和自環(huán)。2、（本題10分）詳細(xì)闡述在具有n個(gè)元素的循環(huán)隊(duì)列中，如何判斷隊(duì)列是否已滿和是否為空，并給出具體的實(shí)現(xiàn)方法和代碼。3、（本題10分）深入解釋在鏈表中，如何實(shí)現(xiàn)頭插法和尾插法創(chuàng)建鏈表，并比較它們在不同場景下的優(yōu)缺點(diǎn)。4、（本題10分）深入解釋在具有n個(gè)頂點(diǎn)的無向圖中，如何使用普里姆（Prim）算法