荊楚理工學(xué)院《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)》2022-2023學(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)實(shí)驗(yàn)》2022-2023學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)有向無(wú)環(huán)圖，進(jìn)行拓?fù)渑判蚩梢缘玫揭粋€(gè)線性的序列。以下關(guān)于拓?fù)渑判虻恼f(shuō)法，錯(cuò)誤的是？（）A.可以使用深度優(yōu)先搜索來(lái)實(shí)現(xiàn)B.結(jié)果可能不唯一C.若存在回路則無(wú)法進(jìn)行拓?fù)渑判駾.其時(shí)間復(fù)雜度為O(n2)2、對(duì)于一個(gè)具有n個(gè)元素的冒泡排序，若要交換相鄰兩個(gè)元素，平均需要移動(dòng)多少次？（）A.0B.1C.2D.33、在一個(gè)具有n個(gè)元素的鏈表中，若要在表頭插入一個(gè)新元素，平均需要修改幾個(gè)指針？（）A.1B.2C.nD.n+14、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹，若底層從左到右填充，則第i個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的編號(hào)為？A.2iB.2i+1C.i*2D.i*2+15、在數(shù)據(jù)結(jié)構(gòu)中，棧是一種特殊的線性表，遵循先進(jìn)后出的原則。以下關(guān)于棧的操作，錯(cuò)誤的是（）A.入棧操作將元素添加到棧頂B.出棧操作取出并刪除棧頂元素C.可以在棧的任意位置進(jìn)行插入和刪除操作D.棧頂指針始終指向棧頂元素6、在一個(gè)具有n個(gè)元素的循環(huán)鏈表中，查找第i個(gè)元素（1<=i<=n），平均需要比較的次數(shù)為（）。A.nB.n/2C.(n+1)/2D.(n-1)/27、在一個(gè)具有n個(gè)節(jié)點(diǎn)的有向圖中，若存在環(huán)，則使用拓?fù)渑判蛩惴〞?huì)出現(xiàn)什么情況？A.正常完成排序B.無(wú)法完成排序C.排序結(jié)果不準(zhǔn)確D.以上都不對(duì)8、對(duì)于一個(gè)用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列，若隊(duì)列已滿，此時(shí)front=10，rear=20，隊(duì)列的最大容量為50，那么下一個(gè)入隊(duì)元素應(yīng)該存儲(chǔ)在哪個(gè)位置？A.21B.0C.30D.無(wú)法確定9、在一個(gè)采用順序存儲(chǔ)結(jié)構(gòu)的線性表中，若要在第i個(gè)位置插入一個(gè)新元素，需要將第i個(gè)位置及之后的元素依次向后移動(dòng)一位。以下關(guān)于插入操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.時(shí)間復(fù)雜度為O(1)B.時(shí)間復(fù)雜度為O(n)C.時(shí)間復(fù)雜度為O(logn)D.時(shí)間復(fù)雜度為O(nlogn)10、在一個(gè)具有n個(gè)元素的無(wú)序數(shù)組中，使用選擇排序進(jìn)行排序。以下關(guān)于選擇排序的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)11、在一個(gè)具有n個(gè)元素的有序鏈表中，若要查找第k個(gè)元素，以下關(guān)于查找操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(k)D.O(n)12、一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，采用鄰接表存儲(chǔ)，其空間復(fù)雜度為？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)13、在一棵完全二叉樹中，若節(jié)點(diǎn)個(gè)數(shù)為n，那么其葉子節(jié)點(diǎn)的個(gè)數(shù)大約為多少？（）A.n/2B.n/4C.(n+1)/2D.n/314、以下哪種排序算法在數(shù)據(jù)基本有序時(shí)的時(shí)間復(fù)雜度接近O(n)？A.冒泡排序B.快速排序C.插入排序D.選擇排序15、在數(shù)據(jù)結(jié)構(gòu)中，基數(shù)排序是一種非比較排序算法，以下關(guān)于基數(shù)排序的描述，不正確的是（）A.按照位數(shù)依次進(jìn)行排序B.可以用于整數(shù)和字符串的排序C.時(shí)間復(fù)雜度為O(d(n+r))，其中d是位數(shù)，r是基數(shù)D.對(duì)數(shù)據(jù)的分布敏感16、在一個(gè)用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列中，若隊(duì)頭指針front=5，隊(duì)尾指針rear=2，隊(duì)列容量為10，則隊(duì)列中的元素個(gè)數(shù)是多少？A.7B.6C.5D.417、對(duì)于一個(gè)具有n個(gè)元素的順序存儲(chǔ)的棧，若要判斷棧是否已滿，應(yīng)判斷？（）A.top==n-1B.top==nC.top>=n-1D.top>=n18、對(duì)于一個(gè)大根堆，若將堆中所有元素按照層次遍歷的順序存儲(chǔ)到一個(gè)數(shù)組中，以下關(guān)于數(shù)組元素的排列，哪一項(xiàng)是正確的？A.完全無(wú)序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對(duì)19、在一個(gè)有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，采用鄰接矩陣存儲(chǔ)，其空間復(fù)雜度為多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)20、在一個(gè)循環(huán)隊(duì)列中，若隊(duì)頭指針front=5，隊(duì)尾指針rear=2，則隊(duì)列中的元素個(gè)數(shù)為：A.7B.3C.2D.不確定二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）數(shù)組的查找算法中，線性查找的實(shí)現(xiàn)過(guò)程和時(shí)間復(fù)雜度是多少？在什么情況下適用？2、（本題10分）闡述如何使用隊(duì)列實(shí)現(xiàn)層次遍歷二叉樹的操作，分析算法的步驟和時(shí)間復(fù)雜度。3、（本題10分）分析在數(shù)據(jù)結(jié)構(gòu)中，如何利用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先搜索算法。4、（本題10分）分析在字符串匹配中，如何利用后綴自動(dòng)機(jī)提高