濟(jì)寧學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

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

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