鹽城工學院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》2022-2023學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁鹽城工學院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》

2022-2023學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個頂點的有向圖，若采用鄰接表表示，則所有鄰接表中的邊節(jié)點總數(shù)為（）。A.nB.n+1C.eD.2e2、在一個具有n個元素的順序表中，若要將其逆置，以下關(guān)于操作的時間復雜度的描述，哪一項是恰當?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、在數(shù)據(jù)結(jié)構(gòu)中，對于一個具有n個元素的有序數(shù)組，使用二分查找算法查找一個特定元素，其平均時間復雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)4、對于一個有向無環(huán)圖，進行拓撲排序可以得到一個線性的序列。以下關(guān)于拓撲排序的說法，錯誤的是？（）A.可以使用深度優(yōu)先搜索來實現(xiàn)B.結(jié)果可能不唯一C.若存在回路則無法進行拓撲排序D.其時間復雜度為O(n2)5、對于一個具有n個節(jié)點的二叉樹，若度為0的節(jié)點有n0個，度為1的節(jié)點有n1個，度為2的節(jié)點有n2個，則n0與n1、n2之間的關(guān)系為？A.n0=n1+n2B.n0=n2-1C.n0=n1-1D.n0=n2+16、對于一個具有n個元素的冒泡排序，若元素基本有序，其時間復雜度接近？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)7、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA8、對于一個具有n個節(jié)點的無向完全圖，其邊的數(shù)量為多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/29、對于一個具有n個頂點和e條邊的帶權(quán)無向圖，使用克魯斯卡爾算法構(gòu)造最小生成樹時，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對10、對于一個具有n個頂點的強連通有向圖，其鄰接矩陣中至少有（）個非零元素。A.nB.n-1C.n(n-1)D.n(n-1)/211、對于單鏈表，若要訪問鏈表中的第i個元素，必須從鏈表的頭指針開始依次遍歷，平均時間復雜度為O(n)。那么如果要在鏈表的末尾添加一個新元素，時間復雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)12、對于一個滿二叉樹，若其高度為h，則其節(jié)點總數(shù)為多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-113、在一個用十字鏈表存儲的有向圖中，查找一個頂點的所有出邊和入邊的時間復雜度是？（）A.O(1)B.O(n)C.O(e)D.O(n+e)14、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠方便地實現(xiàn)集合的交、并、差等運算？（）A.二叉樹B.鏈表C.哈希表D.樹狀數(shù)組15、在一棵完全二叉樹中，若節(jié)點個數(shù)為n，那么其葉子節(jié)點的個數(shù)大約為多少？（）A.n/2B.n/4C.(n+1)/2D.n/316、在一個用鄰接表表示的無向圖中，若要刪除一條邊，需要進行的操作是？（）A.在兩個頂點的鄰接表中刪除對應(yīng)的邊節(jié)點B.只在一個頂點的鄰接表中刪除對應(yīng)的邊節(jié)點C.重新構(gòu)建鄰接表D.以上都不對17、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，具有多種遍歷方式。對于先序遍歷、中序遍歷和后序遍歷，以下描述錯誤的是（）A.先序遍歷先訪問根節(jié)點，然后遞歸遍歷左子樹和右子樹B.中序遍歷先遞歸遍歷左子樹，然后訪問根節(jié)點，最后遞歸遍歷右子樹C.后序遍歷先遞歸遍歷左子樹和右子樹，最后訪問根節(jié)點D.這三種遍歷方式的結(jié)果總是相同的18、樹的遍歷方式有多種，以下關(guān)于它們的說法中，錯誤的是？（）A.前序遍歷是先訪問根節(jié)點，然后遍歷左子樹，最后遍歷右子樹。B.中序遍歷是先遍歷左子樹，然后訪問根節(jié)點，最后遍歷右子樹。C.后序遍歷是先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點。D.樹的遍歷方式只有前序遍歷、中序遍歷和后序遍歷三種。19、在一個具有n個頂點的無向圖中，若采用鄰接矩陣存儲，則存儲空間復雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)20、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEABC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EACDB二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述在一個具有n個頂點的無向圖中，如何使用廣度優(yōu)先搜索算法來生成連通分量。2、（本題10分）解釋如何在一個二叉樹中進行按層之字形遍歷（即奇數(shù)層從左到右，偶數(shù)層從右到左），給出算法步驟和實現(xiàn)代碼，并分析其時間復雜度。3、（本題10分）深入分析在一個具有n個元素的鏈表中，如何查找第k大的元素。4、（本題10分）解釋如何在一個具有n個元素的數(shù)組中，找出兩個數(shù)之和等于給