濟寧學院《數(shù)據(jù)結構與算法》2021-2022學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁濟寧學院

《數(shù)據(jù)結構與算法》2021-2022學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個小根堆中，最小的元素總是位于堆頂。若要將一個元素插入到堆中并保持堆的性質，以下哪種操作是必須的？A.從堆頂向下調整B.從堆底向上調整C.先刪除堆頂元素再插入D.以上都不對2、對于單鏈表，若要訪問鏈表中的第i個元素，必須從鏈表的頭指針開始依次遍歷，平均時間復雜度為O(n)。那么如果要在鏈表的末尾添加一個新元素，時間復雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)3、一棵哈夫曼樹共有215個節(jié)點，對其進行編碼，共能得到（）種不同的編碼。A.107B.108C.214D.2154、在一個具有n個元素的有序數(shù)組中，使用二分查找查找一個不存在的元素，最多比較次數(shù)約為？A.lognB.nC.n/2D.nlogn5、在一個具有n個頂點的無向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n2D.2n(n-1)6、在一個具有n個節(jié)點的二叉樹中，若先序遍歷序列為ABC，中序遍歷序列為BAC，則后序遍歷序列是什么？A.BCAB.CBAC.ACBD.無法確定7、對于一個采用順序存儲的棧，若棧頂指針top等于-1時，表示：A.棧滿B.?？誄.棧中只有一個元素D.棧中至少有一個元素8、對于一個具有n個節(jié)點的完全二叉樹，若底層從左到右填充，則第i個節(jié)點的左孩子節(jié)點的編號為？A.2iB.2i+1C.i*2D.i*2+19、對于一個具有n個節(jié)點的二叉樹，其先序遍歷、中序遍歷和后序遍歷的結果都是唯一確定的，這個二叉樹一定是（）A.滿二叉樹B.完全二叉樹C.單支樹D.以上都不是10、以下關于拓撲排序的描述，正確的是：A.拓撲排序的結果是唯一的B.一個有環(huán)的圖也可以進行拓撲排序C.拓撲排序可以用于判斷一個圖是否有環(huán)D.拓撲排序只能用于有向圖11、設有一個鏈棧，棧頂指針為top，若要在棧頂插入一個新元素，則需要執(zhí)行的操作是（）。A.s->next=top;top=s;B.top->next=s;top=s;C.s->next=top->next;top->next=s;D.top=s;s->next=NULL;12、紅黑樹是一種自平衡的二叉搜索樹，具有嚴格的性質。以下關于紅黑樹的描述，不正確的是（）A.節(jié)點要么是紅色，要么是黑色B.根節(jié)點一定是黑色C.從根節(jié)點到每個葉子節(jié)點的路徑上，黑色節(jié)點的數(shù)量相同D.紅黑樹的插入和刪除操作比平衡二叉樹簡單13、對于一個具有n個元素的無序數(shù)組，使用插入排序進行排序，其最好情況下的時間復雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、以下關于串的描述，錯誤的是：A.串是一種特殊的線性表B.串的長度是指串中字符的個數(shù)C.空串和空格串是相同的概念D.串的存儲方式有順序存儲和鏈式存儲15、在一個具有n個元素的無序數(shù)組中，使用順序查找算法查找一個特定元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.nlogn16、在一個具有n個元素的順序表中，若要將其逆置，以下關于操作的時間復雜度的描述，哪一項是恰當?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、在一個用數(shù)組實現(xiàn)的循環(huán)隊列中，若隊頭指針front=5，隊尾指針rear=2，隊列容量為10，則隊列中的元素個數(shù)是多少？A.7B.6C.5D.418、平衡二叉樹是一種特殊的二叉搜索樹，通過自動調整保持樹的平衡。以下關于平衡二叉樹的操作，不正確的是（）A.插入節(jié)點可能會導致樹的不平衡，需要進行旋轉調整B.平衡二叉樹的查找效率在最壞情況下為O(logn)C.平衡因子用于判斷節(jié)點是否平衡D.平衡二叉樹的節(jié)點刪除操作比插入操作更復雜19、在一個長度為n的順序表中，刪除第i個元素（1<=i<=n）時，需要移動的元素個數(shù)為：A.n-iB.i-1C.n-i+1D.i20、對于一個具有n個元素的希爾排序，其時間復雜度取決于？（）A.初始序列B.增量序列C.元素值D.以上都是二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述如何使用分塊查找算法在一個較大的有序數(shù)組中提高查找效率。2、（本題10分）解釋什么是斐波那契堆的合并操作及其時間復雜度。3、（本題10分）對于一個用哈希表存儲的整數(shù)集合，解釋如何實現(xiàn)集合的交集、并集和差集運算，給出算法思路和時間復雜度分析。4、（本題10分）解釋堆的概念，包括大根堆和小根堆，給出堆的調整算法步驟，并說明堆在排序算法