保山學(xué)院《數(shù)據(jù)結(jié)構(gòu)實(shí)踐》2022-2023學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁保山學(xué)院

《數(shù)據(jù)結(jié)構(gòu)實(shí)踐》2022-2023學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)元素的順序存儲的線性表中，刪除第i個(gè)元素（1<=i<=n），需要移動多少個(gè)元素？（）A.n-iB.iC.n-i+1D.n-i-12、對于一個(gè)循環(huán)隊(duì)列，若隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAX_SIZE，那么判斷隊(duì)空的條件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-13、若一棵二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹的后序遍歷序列為？（）A.BCAB.CBAC.ABCD.ACB4、對于一個(gè)具有n個(gè)元素的有序鏈表，若要在其中插入一個(gè)新元素并保持有序，平均需要移動的元素個(gè)數(shù)為？（）A.n/2B.nC.lognD.nlogn5、若一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EDCAB6、在一個(gè)具有n個(gè)頂點(diǎn)的連通圖中，生成樹的邊數(shù)一定為？（）A.n-1B.nC.n+1D.2n7、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖中，使用弗洛伊德算法求所有頂點(diǎn)對之間的最短路徑，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(n2)C.O(n3)D.O(e3)8、以下關(guān)于并查集的描述，錯(cuò)誤的是：A.并查集可以用于判斷兩個(gè)元素是否在同一個(gè)集合中B.并查集的查找操作時(shí)間復(fù)雜度較低C.并查集的合并操作時(shí)間復(fù)雜度較高D.并查集通常采用樹形結(jié)構(gòu)存儲9、設(shè)有一個(gè)具有n個(gè)元素的最大堆，若要獲取堆中的最大元素，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、紅黑樹是一種自平衡的二叉搜索樹，具有嚴(yán)格的性質(zhì)。以下關(guān)于紅黑樹的描述，不正確的是（）A.節(jié)點(diǎn)要么是紅色，要么是黑色B.根節(jié)點(diǎn)一定是黑色C.從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑上，黑色節(jié)點(diǎn)的數(shù)量相同D.紅黑樹的插入和刪除操作比平衡二叉樹簡單11、以下哪種排序算法在平均情況下的時(shí)間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序12、在一棵平衡二叉樹中，插入一個(gè)新節(jié)點(diǎn)后可能導(dǎo)致失衡，需要進(jìn)行調(diào)整。以下哪種調(diào)整操作可能涉及到旋轉(zhuǎn)次數(shù)最多？（）A.LL型調(diào)整B.RR型調(diào)整C.LR型調(diào)整D.RL型調(diào)整13、在一個(gè)具有n個(gè)元素的鏈表中，若要在表頭插入一個(gè)新元素，平均需要修改幾個(gè)指針？（）A.1B.2C.nD.n+114、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，若每個(gè)節(jié)點(diǎn)都有左子樹和右子樹，則其葉子節(jié)點(diǎn)的個(gè)數(shù)至少為？A.n/2B.(n+1)/2C.n-1D.logn15、在一個(gè)小根堆中，最小的元素總是位于堆頂。若要將一個(gè)元素插入到堆中并保持堆的性質(zhì)，以下哪種操作是必須的？A.從堆頂向下調(diào)整B.從堆底向上調(diào)整C.先刪除堆頂元素再插入D.以上都不對16、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，若度為0的節(jié)點(diǎn)有n0個(gè)，度為1的節(jié)點(diǎn)有n1個(gè)，度為2的節(jié)點(diǎn)有n2個(gè)，則n0與n1、n2之間的關(guān)系為？A.n0=n1+n2B.n0=n2-1C.n0=n1-1D.n0=n2+117、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹，若按照層次遍歷的順序?qū)⒐?jié)點(diǎn)編號為1到n，已知編號為i的節(jié)點(diǎn)有左孩子，則其左孩子的編號為？A.2iB.2i+1C.i*2D.i/218、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無向圖，若采用Prim算法生成最小生成樹，其時(shí)間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(n^3)19、在一個(gè)具有n個(gè)元素的順序表中，要在中間位置插入一個(gè)新元素，平均移動元素的個(gè)數(shù)約為？A.n/2B.nC.lognD.120、對于一個(gè)大根堆，若將堆中所有元素按照層次遍歷的順序存儲到一個(gè)數(shù)組中，以下關(guān)于數(shù)組元素的排列，哪一項(xiàng)是正確的？A.完全無序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)說明如何在一個(gè)二叉樹中進(jìn)行后序遍歷的多線程實(shí)現(xiàn)，給出算法步驟和實(shí)現(xiàn)代碼，并分析其線程同步和效率。2、（本題10分）詳細(xì)闡述B+樹的范圍查詢操作的實(shí)現(xiàn)過程和優(yōu)勢。3、（本題10分）解釋如何合并兩個(gè)有序鏈表為一個(gè)有序鏈表，分析算法的步驟和時(shí)間復(fù)雜度。4、（本題10分）詳細(xì)說明如何在一個(gè)二叉