安徽工業(yè)大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)安徽工業(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)表達(dá)式求值？A.二叉樹(shù)B.棧C.隊(duì)列D.哈希表2、已知一棵二叉樹(shù)的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA3、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖，采用鄰接表存儲(chǔ)，進(jìn)行深度優(yōu)先遍歷。以下關(guān)于遍歷的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)4、已知一個(gè)圖的鄰接矩陣如下所示，則從頂點(diǎn)V1出發(fā)進(jìn)行深度優(yōu)先遍歷，可能得到的頂點(diǎn)訪問(wèn)序列是（）。|01100||10010||10001||01000||00100|A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V5,V3,V4D.V1,V4,V3,V2,V55、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的存儲(chǔ)？A.鄰接矩陣和鄰接表B.二叉樹(shù)和鏈表C.棧和隊(duì)列D.數(shù)組和哈希表6、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖，其邊的數(shù)量為多少？（）A.n(n-1)/2B.n(n-1)C.n2D.2n7、設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為：A.連接B.模式匹配C.求子串D.求串長(zhǎng)8、排序算法的穩(wěn)定性和時(shí)間復(fù)雜度可以用于選擇合適的排序算法，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.穩(wěn)定性對(duì)于某些應(yīng)用場(chǎng)景非常重要，如對(duì)具有多個(gè)關(guān)鍵字的記錄進(jìn)行排序時(shí)。B.時(shí)間復(fù)雜度是衡量排序算法效率的重要指標(biāo)，不同的排序算法具有不同的時(shí)間復(fù)雜度。C.可以根據(jù)實(shí)際情況選擇穩(wěn)定的或不穩(wěn)定的排序算法，以及時(shí)間復(fù)雜度較低的排序算法。D.排序算法的穩(wěn)定性和時(shí)間復(fù)雜度只適用于理論研究，在實(shí)際應(yīng)用中沒(méi)有實(shí)際價(jià)值。9、對(duì)于一個(gè)具有n個(gè)元素的雙向鏈表，若要在第i個(gè)位置（1<=i<=n）之前插入一個(gè)新節(jié)點(diǎn)，平均需要修改多少個(gè)指針？（）A.1B.2C.3D.410、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)連通圖，其最小生成樹(shù)一定包含圖中的所有節(jié)點(diǎn)嗎？A.一定包含B.不一定包含C.視情況而定D.以上都不對(duì)11、以下哪種排序算法在最壞情況下的交換次數(shù)最少？A.冒泡排序B.快速排序C.選擇排序D.插入排序12、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，當(dāng)進(jìn)行一次出隊(duì)操作后，front指針應(yīng)該如何移動(dòng)？A.front=front->nextB.front=rearC.front不變D.front=NULL13、對(duì)于一個(gè)采用鏈表存儲(chǔ)的棧，若要獲取棧的大?。ㄔ?cái)?shù)量），以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、在一個(gè)具有n個(gè)元素的最小堆中，刪除堆頂元素后，為了恢復(fù)堆的性質(zhì)，需要進(jìn)行的調(diào)整操作的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、對(duì)于一個(gè)具有n個(gè)元素的有序數(shù)組，使用二分查找算法查找一個(gè)特定元素。以下關(guān)于二分查找的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、在一個(gè)B樹(shù)中，每個(gè)節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-117、在一個(gè)具有n個(gè)元素的順序表中，刪除第i個(gè)元素（1<=i<=n），平均需要移動(dòng)的元素個(gè)數(shù)約為？A.n/2B.n-iC.iD.n-i+118、在一個(gè)循環(huán)鏈表中，若要?jiǎng)h除鏈表中的最后一個(gè)節(jié)點(diǎn)，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在一個(gè)循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，隊(duì)列最大容量為MAXSIZE，若當(dāng)前隊(duì)列長(zhǎng)度為n，則判斷隊(duì)滿的條件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE20、在一個(gè)用數(shù)組實(shí)現(xiàn)的棧中，若要將棧的容量擴(kuò)大一倍，以下哪種操作的時(shí)間復(fù)雜度最低？（）A.重新創(chuàng)建一個(gè)更大的數(shù)組并復(fù)制元素B.逐步將元素移動(dòng)到新的更大的數(shù)組中C.直接在原數(shù)組后面追加空間D.以上操作時(shí)間復(fù)雜度相同二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋在一個(gè)有序數(shù)組中進(jìn)行二分查找的基本思路和步驟，分析其時(shí)間復(fù)雜度和空間復(fù)雜度。2、（本題10分）詳細(xì)論述在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，如何進(jìn)行頂點(diǎn)的割點(diǎn)求解。3、（本題10分）數(shù)組的排序算法中，快速排序的實(shí)現(xiàn)過(guò)程是怎樣的？時(shí)間復(fù)雜度和空間復(fù)雜度分別是多少？4、（本題10分）在一個(gè)二叉樹(shù)中，如何進(jìn)行前序遍歷的非遞歸實(shí)現(xiàn)？三、設(shè)計(jì)