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

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)湖北理工學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》

2021-2022學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)具有n個(gè)元素的有序數(shù)組，若采用折半插入排序算法進(jìn)行排序，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n2)D.O(logn)2、在一個(gè)具有n個(gè)節(jié)點(diǎn)的圖中，使用弗洛伊德算法求所有節(jié)點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)3、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)，通過(guò)哈希函數(shù)將關(guān)鍵字映射到存儲(chǔ)位置。關(guān)于哈希沖突的解決方法，錯(cuò)誤的是（）A.開(kāi)放定址法通過(guò)尋找空閑位置來(lái)解決沖突B.鏈地址法將沖突的元素存儲(chǔ)在鏈表中C.再哈希法通過(guò)更換哈希函數(shù)來(lái)解決沖突D.哈希沖突無(wú)法避免，且對(duì)查找效率沒(méi)有影響4、設(shè)有一個(gè)用鏈表實(shí)現(xiàn)的雙向循環(huán)鏈表，若要在其中一個(gè)節(jié)點(diǎn)之后插入一個(gè)新節(jié)點(diǎn)，以下關(guān)于插入操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、以下關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的描述，哪一項(xiàng)是正確的？（）A.鄰接矩陣適合存儲(chǔ)稀疏圖B.鄰接表在存儲(chǔ)稠密圖時(shí)空間效率較高C.十字鏈表適合存儲(chǔ)有向圖D.以上都不正確6、在一個(gè)具有n個(gè)元素的順序表中，刪除第i個(gè)元素（1<=i<=n），平均需要移動(dòng)的元素個(gè)數(shù)約為？A.n/2B.n-iC.iD.n-i+17、在二叉樹(shù)中，判斷兩棵二叉樹(shù)是否完全相同，以下方法不正確的是（）A.同時(shí)進(jìn)行先序遍歷，比較節(jié)點(diǎn)值B.同時(shí)進(jìn)行中序遍歷，比較節(jié)點(diǎn)值C.同時(shí)進(jìn)行后序遍歷，比較節(jié)點(diǎn)值D.比較兩棵樹(shù)的節(jié)點(diǎn)數(shù)量8、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的棧中，若要在棧頂插入一個(gè)元素，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序10、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)表達(dá)式求值？A.二叉樹(shù)B.棧C.隊(duì)列D.哈希表11、在一個(gè)哈希表中，若采用線性探測(cè)法解決哈希沖突，當(dāng)發(fā)生沖突時(shí)，新元素會(huì)存儲(chǔ)在什么位置？A.沖突位置的下一個(gè)位置B.沖突位置C.隨機(jī)位置D.以上都不對(duì)12、在一個(gè)具有n個(gè)元素的堆中，查找最大元素的時(shí)間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)13、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，使用克魯斯卡爾（Kruskal）算法生成最小生成樹(shù)。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(nlogn)B.O(eloge)C.O(elogn)D.O(n^2)14、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行插入操作的時(shí)間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、圖的存儲(chǔ)方式和遍歷方式可以用于解決很多實(shí)際問(wèn)題，以下關(guān)于它們的應(yīng)用的說(shuō)法中，錯(cuò)誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等。B.圖的鄰接表可以用于表示稀疏圖，如地圖、電路圖等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問(wèn)題和最小生成樹(shù)問(wèn)題等。D.圖的存儲(chǔ)方式和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒(méi)有實(shí)際價(jià)值。16、數(shù)組通常具有的兩種基本操作是：A.插入和刪除B.查找和修改C.遍歷和排序D.索引和賦值17、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)中，若底層從左到右依次編號(hào)，節(jié)點(diǎn)i的左孩子節(jié)點(diǎn)編號(hào)是多少（假設(shè)根節(jié)點(diǎn)編號(hào)為1）？A.2iB.2i+1C.i*2D.以上都不對(duì)18、對(duì)于一個(gè)大根堆，若要?jiǎng)h除堆頂元素并保持堆的性質(zhì)，以下哪種操作是正確的？A.將堆底元素移到堆頂，然后從堆頂向下調(diào)整B.將堆頂元素直接刪除，不進(jìn)行其他操作C.將堆頂元素與任意子節(jié)點(diǎn)交換，然后調(diào)整D.以上都不對(duì)19、若要對(duì)一個(gè)具有n個(gè)元素的數(shù)組進(jìn)行歸并排序，需要額外的輔助空間大小為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)20、在一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉（Dijkstra）算法求單源最短路徑。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述在堆的調(diào)整過(guò)程中，如何保證堆的性質(zhì)在插入和刪除操作后仍然成立。2、（本題10分）在數(shù)據(jù)結(jié)構(gòu)中，闡述如何使用線段樹(shù)解決區(qū)間查詢和更新問(wèn)題，給出算法步驟和實(shí)現(xiàn)代碼，并分析其性能優(yōu)勢(shì)。3、（本題10分）論述在圖的遍歷中，如何使用標(biāo)記數(shù)組避免重復(fù)訪問(wèn)節(jié)點(diǎn)，以及其實(shí)現(xiàn)的原理。4、（本題10分）深入解釋在利用棧實(shí)現(xiàn)括號(hào)匹配的算法中，如何處理多種類型的括號(hào)，如小括號(hào)、中括號(hào)和大括號(hào)。三、設(shè)計(jì)題（