玉溪師范學(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è)元素的堆，進(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)2、若一個(gè)圖的廣度優(yōu)先遍歷序列為ABCDEFG，則其深度優(yōu)先遍歷序列可能為？（）A.ABDCEFGB.ACBDEFGC.ADBCEFGD.AECBDFG3、設(shè)有一個(gè)鏈棧，棧頂指針為top，若要在棧頂插入一個(gè)新元素，則需要執(zhí)行的操作是（）。A.s->next=top;top=s;B.top->next=s;top=s;C.s->next=top->next;top->next=s;D.top=s;s->next=NULL;4、若要在一個(gè)具有n個(gè)元素的有序數(shù)組中插入一個(gè)新元素，同時(shí)保持?jǐn)?shù)組有序，平均需要移動(dòng)多少個(gè)元素？（）A.n/2B.nC.lognD.15、二叉樹(shù)是一種重要的數(shù)據(jù)結(jié)構(gòu)，以下關(guān)于二叉樹(shù)的性質(zhì)的說(shuō)法中，錯(cuò)誤的是？（）A.二叉樹(shù)的每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。B.二叉樹(shù)的左子樹(shù)和右子樹(shù)是有順序的。C.滿二叉樹(shù)是一種特殊的二叉樹(shù)，所有的葉節(jié)點(diǎn)都在同一層。D.完全二叉樹(shù)是一種特殊的滿二叉樹(shù)，所有的節(jié)點(diǎn)都在同一層。6、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的棧中，若棧頂指針為top，要判斷棧是否為空，應(yīng)判斷？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL7、二叉樹(shù)的遍歷方式可以遞歸實(shí)現(xiàn)，也可以非遞歸實(shí)現(xiàn)，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.遞歸實(shí)現(xiàn)的二叉樹(shù)遍歷方式簡(jiǎn)單直觀，但可能會(huì)導(dǎo)致棧溢出問(wèn)題。B.非遞歸實(shí)現(xiàn)的二叉樹(shù)遍歷方式需要使用?；蜿?duì)列來(lái)輔助實(shí)現(xiàn)。C.非遞歸實(shí)現(xiàn)的二叉樹(shù)遍歷方式比遞歸實(shí)現(xiàn)的效率更高。D.二叉樹(shù)的遍歷方式只能用遞歸或非遞歸方式實(shí)現(xiàn)，不能用其他方式實(shí)現(xiàn)。8、若要對(duì)一個(gè)具有n個(gè)元素的無(wú)序數(shù)組進(jìn)行排序，以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序9、已知一個(gè)有序表為{5,10,15,20,25,30,35,40,45,50}，使用折半查找法查找值為35的元素，需要比較的次數(shù)是（）。A.1B.2C.3D.410、對(duì)于一個(gè)用數(shù)組實(shí)現(xiàn)的小根堆，若要將堆頂元素與最后一個(gè)元素交換，然后重新調(diào)整堆，以下關(guān)于調(diào)整的方向，哪一項(xiàng)是正確的？A.從堆頂向下調(diào)整B.從堆底向上調(diào)整C.先從堆頂向下調(diào)整，再?gòu)亩训紫蛏险{(diào)整D.以上都不對(duì)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、以下哪種排序算法在數(shù)據(jù)基本有序時(shí)的時(shí)間復(fù)雜度接近O(n)？A.冒泡排序B.快速排序C.插入排序D.選擇排序13、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，使用深度優(yōu)先搜索算法進(jìn)行遍歷。以下關(guān)于算法中使用的標(biāo)記數(shù)組的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(n)C.O(e)D.O(n^2)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、以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實(shí)現(xiàn)一個(gè)可以快速查找最大值和最小值的數(shù)據(jù)集合？A.鏈表B.棧C.隊(duì)列D.堆16、在一個(gè)具有n個(gè)元素的大頂堆中，插入一個(gè)新元素后，需要進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)17、圖的存儲(chǔ)方式和遍歷方式可以用于解決很多實(shí)際問(wèn)題，以下關(guān)于它們的應(yīng)用的說(shuō)法中，錯(cuò)誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，適用于社交網(wǎng)絡(luò)分析和交通網(wǎng)絡(luò)規(guī)劃等。B.圖的鄰接表可以用于表示稀疏圖，適用于地圖繪制和電路圖設(shè)計(jì)等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問(wèn)題和最小生成樹(shù)問(wèn)題等，適用于物流配送和通信網(wǎng)絡(luò)優(yōu)化等。D.圖的存儲(chǔ)方式和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒(méi)有實(shí)際價(jià)值。18、在一個(gè)具有n個(gè)元素的小根堆中，刪除堆頂元素后，將最后一個(gè)元素放到堆頂，然后進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)19、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的無(wú)向完全圖，其邊的數(shù)量為多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/220、在一個(gè)順序存儲(chǔ)的隊(duì)列中，若要在隊(duì)尾插入一個(gè)元素，需要移動(dòng)元素的平均次數(shù)為（）A.0B.n/2C.nD.n-1二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）闡述如何將一個(gè)具有n個(gè)元素的無(wú)序數(shù)組構(gòu)建為一個(gè)最小堆，并分析其時(shí)間復(fù)雜度。2、（本題10分）在一個(gè)順序表中，插入和刪除操作在平均情況下的時(shí)間復(fù)雜度分別是多少？并解釋為什么會(huì)是這樣的復(fù)雜度。3、（本題10分）闡述如何使用并查集解決集合合并和查詢問(wèn)題，說(shuō)明并查集的優(yōu)化方法和時(shí)間復(fù)雜度。4、（本題10分）詳細(xì)闡述在具有n個(gè)頂點(diǎn)的圖中，如何使用迪杰斯特拉（Dijkstra）算法求解每對(duì)頂點(diǎn)之間的最短路徑，并分析其時(shí)間