蘇州大學(xué)《數(shù)據(jù)結(jié)構(gòu)及實(shí)驗(yàn)》2022-2023學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁蘇州大學(xué)《數(shù)據(jù)結(jié)構(gòu)及實(shí)驗(yàn)》

2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一棵度為4的樹中，若有20個(gè)度為4的節(jié)點(diǎn)，10個(gè)度為3的節(jié)點(diǎn)，1個(gè)度為2的節(jié)點(diǎn)，10個(gè)葉子節(jié)點(diǎn)，那么這棵樹的總節(jié)點(diǎn)數(shù)是多少？A.82B.81C.79D.782、一棵二叉樹的先序遍歷序列為ABDECFGH，中序遍歷序列為DBEAFCGH，則該二叉樹的后序遍歷序列為（）。A.DEBFGCHAB.DEBFHGCAC.DEBHGFCAD.DEBHFCGA3、一棵完全二叉樹的第5層（根為第1層）有16個(gè)葉子節(jié)點(diǎn)，則該完全二叉樹的節(jié)點(diǎn)總數(shù)最少為（）。A.47B.55C.63D.644、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無向圖中，若要判斷兩個(gè)節(jié)點(diǎn)之間是否存在路徑，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.普里姆算法D.克魯斯卡爾算法5、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)連通圖，其最小生成樹一定包含圖中的所有節(jié)點(diǎn)嗎？A.一定包含B.不一定包含C.視情況而定D.以上都不對6、對于一個(gè)具有n個(gè)元素的有序單鏈表，若要在其中查找一個(gè)特定元素，平均需要比較的次數(shù)為？（）A.n/2B.nC.lognD.nlogn7、若一個(gè)圖的鄰接矩陣對角線以下（不包括對角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強(qiáng)連通圖D.弱連通圖8、在一個(gè)具有n個(gè)元素的順序表中，若要在第i個(gè)元素之前插入一個(gè)新元素，平均需要移動多少個(gè)元素？（）A.n/2B.nC.iD.n-i9、數(shù)據(jù)結(jié)構(gòu)的應(yīng)用非常廣泛，以下關(guān)于它們的應(yīng)用場景的說法中，錯(cuò)誤的是？（）A.數(shù)組可以用于存儲和處理大量的相同類型的數(shù)據(jù)。B.鏈表可以用于實(shí)現(xiàn)動態(tài)數(shù)據(jù)結(jié)構(gòu)，如棧、隊(duì)列和鏈表等。C.樹可以用于實(shí)現(xiàn)文件系統(tǒng)、數(shù)據(jù)庫索引和表達(dá)式求值等。D.數(shù)據(jù)結(jié)構(gòu)只在計(jì)算機(jī)科學(xué)領(lǐng)域有應(yīng)用，在其他領(lǐng)域沒有實(shí)際價(jià)值。10、哈希表的性能取決于哈希函數(shù)的設(shè)計(jì)和沖突解決方法的選擇，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.好的哈希函數(shù)應(yīng)該具有均勻分布性、隨機(jī)性和高效性等特點(diǎn)。B.沖突解決方法的選擇應(yīng)該根據(jù)哈希表的大小、數(shù)據(jù)的特點(diǎn)和操作的頻率等因素來決定。C.哈希表的性能可以通過調(diào)整哈希函數(shù)和沖突解決方法來優(yōu)化。D.哈希表的性能只取決于哈希函數(shù)的設(shè)計(jì)，與沖突解決方法無關(guān)。11、在一個(gè)具有n個(gè)元素的順序表中，若要?jiǎng)h除第i個(gè)元素（1<=i<=n），并將后面的元素向前移動，平均需要移動多少個(gè)元素？（）A.n-iB.iC.(n-i)/2D.n-i+112、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無向圖中，若要判斷圖是否連通，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.克魯斯卡爾算法D.以上都可以13、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若存在頂點(diǎn)的入度為0，則該圖可能是：A.強(qiáng)連通圖B.弱連通圖C.非連通圖D.以上都不對14、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖中，若存在負(fù)權(quán)邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用15、在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，若要?jiǎng)h除表中所有值為x的結(jié)點(diǎn)，最優(yōu)的算法時(shí)間復(fù)雜度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)16、對于一個(gè)循環(huán)隊(duì)列，若隊(duì)列的最大容量為m，當(dāng)前front指針為5，rear指針為2，則隊(duì)列中的元素個(gè)數(shù)為（）A.7B.3C.m-3D.m-717、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖中，使用鄰接矩陣存儲，進(jìn)行深度優(yōu)先遍歷，其時(shí)間復(fù)雜度為？A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)18、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為m，入度之和為k，則m和k之間的關(guān)系是？（）A.m=kB.m>kC.m<kD.m+k=n19、設(shè)有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，頭指針為head，若要在第一個(gè)元素之前插入一個(gè)新元素，則需要執(zhí)行的操作是（）。A.s->next=head;head=s;B.s->next=head->next;head->next=s;C.head->next=s;s->next=head;D.s->next=head;s=head;20、以下關(guān)于串的描述，錯(cuò)誤的是：A.串是一種特殊的線性表B.串的長度是指串中字符的個(gè)數(shù)C.空串和空格串是相同的概念D.串的存儲方式有順序存儲和鏈?zhǔn)酱鎯Χ⒑喆痤}（本大題共4個(gè)小題，共40分)1、（本題10分）對于一個(gè)用哈希表存儲的整數(shù)集合，解釋如何實(shí)現(xiàn)集合的交集、并集和差集運(yùn)算，給出算法思路和時(shí)間復(fù)雜度分析。2、（本題10分）詳細(xì)說明選擇排序算法在元素基本有序時(shí)的性能表現(xiàn)。3、（本題10分）詳細(xì)論述在一個(gè)具有n個(gè)元素的循環(huán)鏈表中，如何實(shí)現(xiàn)插入、刪除和查找操作，并分析其時(shí)間復(fù)雜度。4、（本題10分）解釋在一個(gè)具有n個(gè)節(jié)點(diǎn)的有向無環(huán)圖中，如何計(jì)算每個(gè)節(jié)點(diǎn)的入度和出度。