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

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫(xiě)、漏寫(xiě)或字跡不清者，成績(jī)按零分記?！堋狻€…………第1頁(yè)，共1頁(yè)長(zhǎng)春工業(yè)大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與算法》2022-2023學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、設(shè)有一個(gè)具有n個(gè)頂點(diǎn)的有向圖，采用鄰接表存儲(chǔ)。若要計(jì)算每個(gè)頂點(diǎn)的出度，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是恰當(dāng)?shù)?？A.O(n)B.O(n+e)C.O(n^2)D.O(e)2、排序算法的穩(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à)值。3、在二叉搜索樹(shù)的刪除操作中，如果刪除的節(jié)點(diǎn)是其父節(jié)點(diǎn)的唯一子節(jié)點(diǎn)，以下處理方式錯(cuò)誤的是（）A.直接將該節(jié)點(diǎn)刪除，不做其他調(diào)整B.將該節(jié)點(diǎn)的值替換為其父節(jié)點(diǎn)的值，并刪除父節(jié)點(diǎn)C.將該節(jié)點(diǎn)的左子樹(shù)或右子樹(shù)替代該節(jié)點(diǎn)D.以上處理方式都不對(duì)4、對(duì)于一個(gè)具有n個(gè)元素的有序鏈表，若要在其中插入一個(gè)新元素并保持有序，平均需要移動(dòng)的元素個(gè)數(shù)為？（）A.n/2B.nC.lognD.nlogn5、在一個(gè)具有n個(gè)元素的雙向鏈表中，在p所指的節(jié)點(diǎn)之后插入一個(gè)新節(jié)點(diǎn)q，其操作步驟為（）。A.q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;B.q->next=p->next;q->prior=p;p->next=q;p->next->prior=q;C.p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;D.p->next->prior=q;q->next=p->next;q->prior=p;p->next=q;6、在一個(gè)具有n個(gè)元素的順序表中，在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)的元素個(gè)數(shù)為：A.n-iB.iC.n-i+1D.n-i-17、以下關(guān)于哈希表沖突解決方法的描述，哪一項(xiàng)是不正確的？（）A.鏈地址法會(huì)增加存儲(chǔ)空間的開(kāi)銷B.開(kāi)放定址法的查找效率一定高于鏈地址法C.再哈希法可以減少?zèng)_突的發(fā)生D.建立公共溢出區(qū)可以存儲(chǔ)發(fā)生沖突的元素8、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)LRU（最近最少使用）頁(yè)面置換算法？A.隊(duì)列B.棧C.哈希表D.雙鏈表9、在一個(gè)哈希表中，解決沖突的方法通常有開(kāi)放定址法和鏈地址法。如果要保證查找的平均時(shí)間復(fù)雜度較低，應(yīng)該優(yōu)先選擇哪種方法？（）A.開(kāi)放定址法B.鏈地址法C.兩者效果相同D.取決于哈希函數(shù)10、在一個(gè)哈希表中，負(fù)載因子越大，說(shuō)明什么？A.哈希沖突越少B.存儲(chǔ)空間利用率越高C.查找效率越高D.以上都不對(duì)11、以下關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的描述，錯(cuò)誤的是：A.鄰接矩陣適合存儲(chǔ)稠密圖B.鄰接表適合存儲(chǔ)稀疏圖C.十字鏈表是鄰接表和逆鄰接表的結(jié)合D.鄰接多重表只適合無(wú)向圖12、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字典操作，并且能夠快速查找、插入和刪除元素？（）A.棧B.隊(duì)列C.二叉搜索樹(shù)D.數(shù)組13、以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序14、在一棵完全二叉樹(shù)中，若節(jié)點(diǎn)個(gè)數(shù)為n，那么其葉子節(jié)點(diǎn)的個(gè)數(shù)大約為多少？（）A.n/2B.n/4C.(n+1)/2D.n/315、若哈希函數(shù)H(key)=key%7，要將關(guān)鍵字38插入到長(zhǎng)度為7的哈希表中，其存儲(chǔ)位置是：A.3B.5C.6D.016、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的完全二叉樹(shù)，其葉子節(jié)點(diǎn)的數(shù)量為？（）A.n/2B.(n+1)/2C.n-1D.n17、以下哪種圖的遍歷算法可以用于判斷一個(gè)圖是否為連通圖？A.深度優(yōu)先遍歷B.廣度優(yōu)先遍歷C.兩者均可D.兩者均不可18、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的紅黑樹(shù)，插入一個(gè)新節(jié)點(diǎn)后，調(diào)整樹(shù)的結(jié)構(gòu)以保持紅黑樹(shù)性質(zhì)，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、已知一棵二叉排序樹(shù)的中序遍歷序列為{10,12,15,18,20,25,30}，則其可能的前序遍歷序列為？（）A.20,18,15,12,10,25,30B.10,12,15,18,20,25,30C.30,25,20,18,15,12,10D.10,12,18,15,20,30,2520、在一個(gè)具有n個(gè)元素的鏈表中，要?jiǎng)h除所有值為x的節(jié)點(diǎn)，最好的方法是？A.逐個(gè)刪除B.先查找再刪除C.建立新鏈表D.以上方法效率相同二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述在一個(gè)具有n個(gè)元素的二叉樹(shù)中，如何計(jì)算樹(shù)的高度，并分析其時(shí)間復(fù)雜度。2、（本題10分）論述AVL樹(shù)的平衡調(diào)整操作對(duì)樹(shù)的結(jié)構(gòu)和性能的長(zhǎng)期影響。3、（本題10分）解釋并舉例說(shuō)明在一個(gè)具有n個(gè)元素的順序表中，如何進(jìn)行計(jì)數(shù)排序。4、（本題10分）分析在數(shù)據(jù)結(jié)構(gòu)中，如何利用隊(duì)列實(shí)現(xiàn)層次遍歷的優(yōu)化。