賀州學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁賀州學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)》2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)元素的順序表中，在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素時(shí)，需要向后移動的元素個(gè)數(shù)為：A.n-iB.iC.n-i+1D.n-i-12、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的無向完全圖，其邊的數(shù)量為多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/23、若一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EDCAB4、對于一個(gè)具有n個(gè)元素的哈希表，負(fù)載因子（loadfactor）為0.7，當(dāng)表中元素?cái)?shù)量超過一定閾值時(shí)需要進(jìn)行擴(kuò)容。以下關(guān)于擴(kuò)容操作的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(1)B.O(n)C.O(logn)D.O(nlogn)5、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先級隊(duì)列？（）A.二叉樹B.鏈表C.堆D.棧6、棧是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它遵循后進(jìn)先出（LIFO）的原則。以下關(guān)于棧的說法中，錯(cuò)誤的是？（）A.?？梢杂脭?shù)組或鏈表實(shí)現(xiàn)。B.棧的插入和刪除操作只能在棧頂進(jìn)行。C.?？梢杂糜趯?shí)現(xiàn)函數(shù)調(diào)用、表達(dá)式求值等。D.棧的容量是無限的，可以存儲任意數(shù)量的元素。7、以下哪種排序算法在平均情況下的時(shí)間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序8、在一個(gè)具有n個(gè)元素的有序單鏈表中，要查找一個(gè)特定元素，平均時(shí)間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)9、對于一個(gè)具有n個(gè)元素的堆，進(jìn)行堆排序。以下關(guān)于堆排序的平均時(shí)間復(fù)雜度和空間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.平均時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(1)B.平均時(shí)間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(n)C.平均時(shí)間復(fù)雜度為O(logn)，空間復(fù)雜度為O(logn)D.平均時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)10、在一個(gè)具有n個(gè)元素的最小堆中，刪除堆頂元素后，為了恢復(fù)堆的性質(zhì)，需要進(jìn)行的調(diào)整操作的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、對于一個(gè)大根堆，若要?jiǎng)h除堆頂元素并保持堆的性質(zhì)，以下哪種操作是正確的？A.將堆底元素移到堆頂，然后從堆頂向下調(diào)整B.將堆頂元素直接刪除，不進(jìn)行其他操作C.將堆頂元素與任意子節(jié)點(diǎn)交換，然后調(diào)整D.以上都不對12、對于一個(gè)采用鏈?zhǔn)酱鎯Φ年?duì)列，若隊(duì)頭指針和隊(duì)尾指針相同，則隊(duì)列的狀態(tài)為：A.隊(duì)空B.隊(duì)滿C.不確定D.隊(duì)列中只有一個(gè)元素13、在一個(gè)具有n個(gè)元素的順序存儲的線性表中，刪除第i個(gè)元素（1<=i<=n），平均需要移動多少個(gè)元素？（）A.n-iB.iC.(n-i)/2D.n/214、以下關(guān)于快速排序的描述，錯(cuò)誤的是：A.快速排序在平均情況下的時(shí)間復(fù)雜度為O(nlogn)B.快速排序是一種不穩(wěn)定的排序算法C.快速排序在最壞情況下的時(shí)間復(fù)雜度為O(n^2)D.快速排序不需要額外的存儲空間15、對于一個(gè)具有n個(gè)元素的有序鏈表，若要在其中插入一個(gè)新元素并保持有序，平均需要移動的元素個(gè)數(shù)為？（）A.n/2B.nC.lognD.nlogn16、在一個(gè)用鏈表實(shí)現(xiàn)的隊(duì)列中，若要?jiǎng)h除隊(duì)尾元素，需要進(jìn)行哪些操作？A.遍歷鏈表找到隊(duì)尾元素并刪除B.將隊(duì)尾元素的前一個(gè)元素設(shè)為隊(duì)尾C.直接刪除隊(duì)尾元素D.以上都不對17、在一個(gè)具有n個(gè)元素的最小堆中，插入一個(gè)新元素后，為了重新調(diào)整為最小堆，最壞情況下需要比較多少次？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)18、在一個(gè)鏈隊(duì)列中，假設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，刪除隊(duì)頭元素的操作是：A.front=front->nextB.rear=rear->nextC.front->next=NULLD.rear->next=NULL19、對于一個(gè)具有n個(gè)元素的快速排序，在最好情況下，其時(shí)間復(fù)雜度為？（）A.O(nlogn)B.O(n^2)C.O(n)D.O(logn)20、在一個(gè)帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹時(shí)，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個(gè)連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋如何在一個(gè)具有n個(gè)元素的循環(huán)鏈表中，進(jìn)行插入操作，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。2、（本題10分）數(shù)組和鏈表在存儲數(shù)據(jù)方面有哪些不同之處？各自的優(yōu)缺點(diǎn)是什么？3、（本題10分）論述在歸并排序中，如何合并兩個(gè)已排序的子序列，給出具體的實(shí)現(xiàn)代碼。4、（本題10分）深入探討在一個(gè)具有n個(gè)元素的二叉搜索樹中，如何實(shí)現(xiàn)樹的平衡化操作，如AVL樹的旋轉(zhuǎn)調(diào)整。三、設(shè)計(jì)題（本大題共2