南京信息工程大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2022-2023學(xué)年期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁南京信息工程大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與算法》2022-2023學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、若一棵二叉樹的葉子節(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+12、樹的遍歷方式有多種，以下關(guān)于它們的說法中，錯誤的是？（）A.前序遍歷是先訪問根節(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。B.中序遍歷是先遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遍歷右子樹。C.后序遍歷是先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點(diǎn)。D.樹的遍歷方式只有前序遍歷、中序遍歷和后序遍歷三種。3、若要對一個具有n個元素的數(shù)組進(jìn)行歸并排序，需要額外的輔助空間大小為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、在一個具有n個元素的順序表中，若要在第i個元素（1<=i<=n）之前插入一個新元素，需要移動的元素個數(shù)為？（）A.n-iB.iC.n-i+1D.n-i-15、以下關(guān)于字符串匹配算法的描述，哪一項(xiàng)是不正確的？（）A.BF算法的時間復(fù)雜度在最壞情況下較高B.KMP算法通過利用已匹配的部分信息來提高效率C.BM算法在一般情況下比KMP算法效率更高D.所有字符串匹配算法的時間復(fù)雜度都與模式串的長度成正比6、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問？（）A.鏈表B.隊(duì)列C.棧D.數(shù)組7、在一個具有n個頂點(diǎn)的有向強(qiáng)連通圖中，至少需要多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)8、在一個具有n個元素的小根堆中，刪除堆頂元素后，將最后一個元素放到堆頂，然后進(jìn)行調(diào)整，其時間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)9、對于一個具有n個元素的有序數(shù)組，若采用折半插入排序算法進(jìn)行排序，其時間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n2)D.O(logn)10、以下關(guān)于平衡二叉樹旋轉(zhuǎn)調(diào)整的描述，正確的是：A.旋轉(zhuǎn)調(diào)整一定會改變樹的中序遍歷結(jié)果B.左旋操作是將右子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)樽笞庸?jié)點(diǎn)C.右旋操作是將左子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)橛易庸?jié)點(diǎn)D.平衡二叉樹不需要進(jìn)行旋轉(zhuǎn)調(diào)整11、設(shè)有一個廣義表L=((a,b),c,(d,e))，其表頭和表尾分別為？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)12、在一棵度為4的樹中，度為4的節(jié)點(diǎn)個數(shù)為1，度為3的節(jié)點(diǎn)個數(shù)為2，度為2的節(jié)點(diǎn)個數(shù)為3，度為1的節(jié)點(diǎn)個數(shù)為4，葉子節(jié)點(diǎn)個數(shù)為（）。A.15B.16C.17D.1813、在一個具有n個頂點(diǎn)的無向圖中，若要判斷兩個頂點(diǎn)之間是否存在路徑，使用哪種算法較為合適？A.迪杰斯特拉算法B.弗洛伊德算法C.深度優(yōu)先遍歷或廣度優(yōu)先遍歷D.拓?fù)渑判?4、在一個具有n個節(jié)點(diǎn)的完全二叉樹中，若底層從左到右依次編號，節(jié)點(diǎn)i的左孩子節(jié)點(diǎn)編號是多少（假設(shè)根節(jié)點(diǎn)編號為1）？A.2iB.2i+1C.i*2D.以上都不對15、以下關(guān)于堆的描述，正確的是：A.大頂堆中每個父節(jié)點(diǎn)的值都大于其子節(jié)點(diǎn)的值B.小頂堆中每個父節(jié)點(diǎn)的值都小于其子節(jié)點(diǎn)的值C.堆可以用順序存儲也可以用鏈?zhǔn)酱鎯.堆是完全二叉樹16、對于一個具有n個頂點(diǎn)的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同17、對于一個用數(shù)組實(shí)現(xiàn)的最小堆，若要刪除堆頂元素并調(diào)整堆，以下操作正確的是？（）A.將堆尾元素移到堆頂，然后從堆頂向下調(diào)整B.將堆頂元素與堆尾元素交換，然后從堆頂向下調(diào)整C.將堆頂元素刪除，然后重新構(gòu)建堆D.以上都不對18、若一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBDAEGF，則其后序遍歷序列為？（）A.CDBGFEAB.CDBFGEAC.CDBAGFED.CDBEAGF19、在圖的最小生成樹算法中，Kruskal算法和Prim算法都能得到最小生成樹，以下關(guān)于這兩個算法的比較，錯誤的是（）A.Kruskal算法基于邊，Prim算法基于節(jié)點(diǎn)B.Kruskal算法需要使用并查集C.Prim算法的時間復(fù)雜度通常比Kruskal算法低D.對于稀疏圖，Kruskal算法更優(yōu)20、對于一個有向無環(huán)圖（DAG），進(jìn)行拓?fù)渑判虻姆椒ú恢挂环N。以下關(guān)于拓?fù)渑判虻拿枋觯e誤的是（）A.可以使用深度優(yōu)先搜索實(shí)現(xiàn)B.結(jié)果不唯一C.可以用于判斷圖中是否存在環(huán)D.所有節(jié)點(diǎn)的入度在排序過程中不會改變二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋什么是并查集，并說明其在解決某些問題中的應(yīng)用。2、（本題10分）在一個具有n個頂點(diǎn)的無向圖中，如何找出所有的生成樹，給出一種有效的算法并分析其時間復(fù)雜度。3、（本題10分）在一個具有n個元素的有序鏈表和有序數(shù)組中，分別說明如何進(jìn)行合并操作，給出算法步驟和時間復(fù)雜度分析。4、（本題10分）深入分析在具有n個元素的有序鏈表中，如何進(jìn)行插入操作以保持鏈表