賀州學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線第1頁(yè)，共3頁(yè)賀州學(xué)院

《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列？（）A.二叉樹(shù)B.鏈表C.堆D.棧2、在一個(gè)具有n個(gè)元素的雙向鏈表中，在p所指的節(jié)點(diǎn)之后插入一個(gè)新節(jié)點(diǎn)q，其操作步驟為（）。A.q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;B.q->next=p->next;q->prior=p;p->next=q;p->next->prior=q;C.p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;D.p->next->prior=q;q->next=p->next;q->prior=p;p->next=q;3、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的棧中，若要在棧頂插入一個(gè)元素，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、在一個(gè)有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比較的次數(shù)是：A.1B.2C.3D.45、二叉樹(shù)是一種重要的數(shù)據(jù)結(jié)構(gòu)。對(duì)于一個(gè)滿二叉樹(shù)，若其高度為h，則節(jié)點(diǎn)總數(shù)為多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-16、對(duì)于一個(gè)具有n個(gè)元素的堆，若要將其所有元素從小到大排序，最好的方法是？A.每次刪除堆頂元素并調(diào)整B.直接使用快速排序C.先構(gòu)建大頂堆再調(diào)整D.以上方法效率相同7、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖中，使用弗洛伊德算法求所有頂點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(n2)C.O(n3)D.O(e3)8、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的完全二叉樹(shù)，其葉子節(jié)點(diǎn)的數(shù)量為？（）A.n/2B.(n+1)/2C.n-1D.n9、在一個(gè)具有n個(gè)元素的最小堆中，插入一個(gè)新元素并調(diào)整為最小堆，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、若要在一棵二叉搜索樹(shù)中查找一個(gè)特定的值，平均時(shí)間復(fù)雜度為？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)11、在一個(gè)有向無(wú)環(huán)圖中，進(jìn)行拓?fù)渑判虻慕Y(jié)果是唯一的嗎？A.一定唯一B.一定不唯一C.可能唯一，也可能不唯一D.以上都不對(duì)12、在數(shù)據(jù)結(jié)構(gòu)中，優(yōu)先隊(duì)列可以用堆來(lái)實(shí)現(xiàn)，以下關(guān)于堆調(diào)整的描述，錯(cuò)誤的是（）A.插入元素時(shí)，從下往上調(diào)整堆B.刪除堆頂元素時(shí)，從上往下調(diào)整堆C.調(diào)整堆的過(guò)程中，節(jié)點(diǎn)的值可能會(huì)交換D.調(diào)整堆的時(shí)間復(fù)雜度與堆的大小無(wú)關(guān)13、哈希表是一種常用的數(shù)據(jù)結(jié)構(gòu)，它通過(guò)哈希函數(shù)將鍵映射到存儲(chǔ)位置。以下關(guān)于哈希表的說(shuō)法中，錯(cuò)誤的是？（）A.哈希表的查找速度非?？?，平均時(shí)間復(fù)雜度為O(1)。B.哈希函數(shù)的設(shè)計(jì)直接影響哈希表的性能。C.哈希表可能會(huì)出現(xiàn)沖突，即不同的鍵被映射到同一個(gè)存儲(chǔ)位置。D.哈希表只能存儲(chǔ)整數(shù)類型的鍵值對(duì)。14、若要對(duì)一個(gè)具有n個(gè)元素的無(wú)序數(shù)組進(jìn)行排序，以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序15、以下關(guān)于哈希表沖突解決方法的描述，哪一項(xiàng)是不正確的？（）A.鏈地址法會(huì)增加存儲(chǔ)空間的開(kāi)銷B.開(kāi)放定址法的查找效率一定高于鏈地址法C.再哈希法可以減少?zèng)_突的發(fā)生D.建立公共溢出區(qū)可以存儲(chǔ)發(fā)生沖突的元素16、在一棵度為4的樹(shù)中，若有20個(gè)度為4的節(jié)點(diǎn)，10個(gè)度為3的節(jié)點(diǎn)，1個(gè)度為2的節(jié)點(diǎn)，10個(gè)葉子節(jié)點(diǎn)，那么這棵樹(shù)的總節(jié)點(diǎn)數(shù)是多少？A.82B.81C.79D.7817、在一個(gè)用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列中，若front=rear，則隊(duì)列的狀態(tài)可能為（）A.隊(duì)空B.隊(duì)滿C.既不空也不滿D.以上都有可能18、已知一個(gè)棧的進(jìn)棧序列為1,2,3,4,5，下列序列中不可能是出棧序列的是（）。A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,519、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠方便地實(shí)現(xiàn)集合的交、并、差等運(yùn)算？（）A.二叉樹(shù)B.鏈表C.哈希表D.樹(shù)狀數(shù)組20、以下關(guān)于二叉排序樹(shù)的描述，錯(cuò)誤的是：A.左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值B.右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值C.中序遍歷二叉排序樹(shù)可得到一個(gè)有序序列D.二叉排序樹(shù)的查找效率總是最高的二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋什么是AVL樹(shù)，說(shuō)明其平衡調(diào)整的策略和方法，并給出插入和刪除操作時(shí)的平衡調(diào)整示例。2、（本題10分）詳細(xì)闡述在快速排序算法中，如何選擇基準(zhǔn)元素，以及如何進(jìn)行分區(qū)操作和排序過(guò)程。3、（本題10分）論述如何使用線段樹(shù)解決動(dòng)態(tài)區(qū)間最大值問(wèn)題，給出更新和查詢的方法。4、（本題10分）數(shù)組的排序算法中，堆排序的實(shí)現(xiàn)過(guò)程是怎樣的？時(shí)間復(fù)雜度和空間復(fù)雜度