北方民族大學(xué)《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)》2021-2022學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁北方民族大學(xué)《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)》

2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、已知一個(gè)圖的鄰接矩陣如下所示，則從頂點(diǎn)V1出發(fā)進(jìn)行深度優(yōu)先遍歷，可能得到的頂點(diǎn)訪問序列是（）。|01100||10010||10001||01000||00100|A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V5,V3,V4D.V1,V4,V3,V2,V52、若一棵二叉樹的葉子節(jié)點(diǎn)數(shù)為n0，度為2的節(jié)點(diǎn)數(shù)為n2，則n0和n2之間的關(guān)系是？（）A.n0=n2-1B.n0=n2+1C.n0=2n2-1D.n0=2n2+13、若要在一棵二叉搜索樹中查找一個(gè)特定的值，平均時(shí)間復(fù)雜度為？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)4、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)滿的條件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front5、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問？（）A.鏈表B.隊(duì)列C.棧D.數(shù)組6、對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若其所有頂點(diǎn)的度之和為20，則該圖的邊數(shù)為（）。A.5B.10C.15D.207、以下關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的描述，錯(cuò)誤的是：A.鄰接矩陣適合存儲(chǔ)稠密圖B.鄰接表適合存儲(chǔ)稀疏圖C.十字鏈表是鄰接表和逆鄰接表的結(jié)合D.鄰接多重表只適合無向圖8、在一個(gè)循環(huán)隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAXSIZE，則判斷隊(duì)滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front9、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列？（）A.二叉樹B.鏈表C.堆D.棧10、對于一個(gè)具有n個(gè)元素的有序鏈表，進(jìn)行折半查找，其時(shí)間復(fù)雜度為？A.O(logn)B.O(nlogn)C.O(n)D.不能進(jìn)行折半查找11、在一個(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.以上都不對12、對于一棵具有n個(gè)節(jié)點(diǎn)的二叉搜索樹，其平均查找長度的上限大約為？A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)13、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無向圖中，若要判斷圖是否連通，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.克魯斯卡爾算法D.以上都可以14、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEABC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EACDB15、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)操作系統(tǒng)中的進(jìn)程調(diào)度？A.隊(duì)列B.棧C.樹D.圖16、對于一個(gè)具有n個(gè)元素的冒泡排序，在最壞情況下，需要進(jìn)行多少次比較操作？（）A.n(n-1)/2B.nC.n+1D.n-117、對于一個(gè)具有n個(gè)元素的待排序序列，若采用冒泡排序算法進(jìn)行排序，在最壞情況下需要進(jìn)行的比較次數(shù)為？（）A.n(n-1)/2B.nlognC.n-1D.n18、在一個(gè)具有n個(gè)元素的鏈表中，若要在表頭插入一個(gè)新元素，平均需要修改幾個(gè)指針？（）A.1B.2C.nD.n+119、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的最長公共子序列問題？A.二維數(shù)組B.棧C.隊(duì)列D.樹20、設(shè)有一個(gè)具有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)二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋在平衡二叉搜索樹中，如何通過調(diào)整策略降低樹的高度。2、（本題10分）詳細(xì)闡述在圖的最短路徑算法中，如何處理動(dòng)態(tài)的邊權(quán)值變化。3、（本題10分）解釋線段樹在處理區(qū)間相交問題時(shí)的思路和算法。4、（本題10分）解釋如何在一個(gè)二叉搜索樹中進(jìn)行查找操作的多線程優(yōu)化，給出算法步驟和實(shí)現(xiàn)代碼，并分析其線程安全和