廣州大學(xué)《數(shù)據(jù)結(jié)構(gòu)課程實(shí)訓(xùn)》2023-2024學(xué)年第一學(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í)訓(xùn)》

2023-2024學(xué)年第一學(xué)期期末試卷題號(hào)一二三四總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題1分，共20分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、設(shè)計(jì)一個(gè)簡(jiǎn)單的數(shù)字電壓表，能夠測(cè)量0-50V的直流電壓，精度達(dá)到0.1V，并用液晶顯示屏顯示測(cè)量結(jié)果。2、在一個(gè)分布式系統(tǒng)中，各個(gè)節(jié)點(diǎn)需要共享一些全局的狀態(tài)信息，并且能夠快速地檢測(cè)到狀態(tài)的變化。為了實(shí)現(xiàn)這種全局狀態(tài)的管理和同步，以下哪種數(shù)據(jù)結(jié)構(gòu)可能會(huì)被用到？（）A.分布式哈希表B.分布式鏈表C.分布式樹(shù)D.分布式棧3、設(shè)計(jì)一個(gè)集成電路制造中的化學(xué)氣相沉積（CVD）設(shè)備控制系統(tǒng)，優(yōu)化工藝參數(shù)。4、設(shè)計(jì)一個(gè)基于STM8的智能灌溉系統(tǒng)，能夠根據(jù)土壤濕度自動(dòng)控制灌溉設(shè)備，提供系統(tǒng)的硬件電路和軟件控制邏輯。5、設(shè)計(jì)一個(gè)基于CAN總線的分布式控制系統(tǒng)，實(shí)現(xiàn)多個(gè)節(jié)點(diǎn)之間的數(shù)據(jù)通信和協(xié)同控制，闡述總線協(xié)議和系統(tǒng)架構(gòu)。6、設(shè)計(jì)一個(gè)基于藍(lán)牙模塊的智能門(mén)鎖系統(tǒng)，能夠通過(guò)手機(jī)藍(lán)牙開(kāi)鎖，并記錄開(kāi)鎖記錄。7、設(shè)計(jì)一個(gè)太陽(yáng)能路燈控制器，能夠根據(jù)環(huán)境光強(qiáng)自動(dòng)控制路燈的開(kāi)關(guān)和亮度，描述電路原理和控制策略。8、設(shè)計(jì)一個(gè)電子秤數(shù)據(jù)存儲(chǔ)電路，能夠?qū)㈦娮映拥臏y(cè)量數(shù)據(jù)存儲(chǔ)在本地或云端，方便查詢和分析。9、設(shè)計(jì)一個(gè)數(shù)字信號(hào)調(diào)制解調(diào)高速電路，能夠?qū)崿F(xiàn)更高的數(shù)據(jù)傳輸速率，提高通信效率。10、設(shè)計(jì)一個(gè)數(shù)字溫度計(jì)濕度計(jì)電路，能夠同時(shí)測(cè)量環(huán)境溫度和濕度，溫度精度為±0.1℃，濕度精度為±2%RH。11、設(shè)計(jì)一個(gè)基于超聲波傳感器的距離測(cè)量系統(tǒng)，能夠測(cè)量物體與傳感器之間的距離，并顯示測(cè)量結(jié)果。12、設(shè)計(jì)一個(gè)基于UWB技術(shù)的室內(nèi)定位系統(tǒng)，定位精度達(dá)到厘米級(jí)，說(shuō)明系統(tǒng)組成和定位算法。13、設(shè)計(jì)一個(gè)數(shù)字電壓表校準(zhǔn)電路，能夠?qū)?shù)字電壓表進(jìn)行校準(zhǔn)，提高測(cè)量精度。14、設(shè)計(jì)一個(gè)基于數(shù)字信號(hào)處理的音頻分離系統(tǒng)，能夠?qū)⒒旌弦纛l中的不同聲源分離出來(lái)。15、設(shè)計(jì)一個(gè)電源適配器，輸入為交流220V，輸出為直流5V/2A，具有過(guò)壓保護(hù)和短路保護(hù)功能，給出電路設(shè)計(jì)和變壓器參數(shù)計(jì)算。16、設(shè)計(jì)一個(gè)簡(jiǎn)單的無(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)關(guān)設(shè)備，實(shí)現(xiàn)傳感器節(jié)點(diǎn)數(shù)據(jù)的匯聚和轉(zhuǎn)發(fā)，描述網(wǎng)關(guān)的硬件結(jié)構(gòu)和軟件功能。17、在一個(gè)數(shù)據(jù)庫(kù)系統(tǒng)的緩沖區(qū)管理中，需要有效地存儲(chǔ)和替換緩沖區(qū)內(nèi)的數(shù)據(jù)頁(yè)，以提高數(shù)據(jù)庫(kù)的訪問(wèn)性能。以下哪種數(shù)據(jù)結(jié)構(gòu)和算法常用于緩沖區(qū)的管理？（）A.LRU（最近最少使用）算法和鏈表B.FIFO（先進(jìn)先出）算法和隊(duì)列C.MRU（最近最多使用）算法和棧D.Random（隨機(jī)）算法和數(shù)組18、棧是一種特殊的線性結(jié)構(gòu)，遵循后進(jìn)先出的原則。假設(shè)一個(gè)程序中使用了棧來(lái)存儲(chǔ)數(shù)據(jù)。以下關(guān)于棧的描述，哪一項(xiàng)是不準(zhǔn)確的？（）A.?？梢杂糜趯?shí)現(xiàn)函數(shù)調(diào)用時(shí)的參數(shù)傳遞和局部變量存儲(chǔ)B.入棧和出棧操作的時(shí)間復(fù)雜度均為O(1)C.可以使用數(shù)組或鏈表來(lái)實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)D.棧的存儲(chǔ)空間大小是固定的，無(wú)法動(dòng)態(tài)擴(kuò)展19、使用集成電路設(shè)計(jì)一個(gè)乘法器，給出乘法運(yùn)算的速度和精度要求，并進(jìn)行電路設(shè)計(jì)和優(yōu)化。20、設(shè)計(jì)一個(gè)基于單片機(jī)的智能電表系統(tǒng)，能夠準(zhǔn)確測(cè)量電能消耗，并具有數(shù)據(jù)存儲(chǔ)、遠(yuǎn)程通信等功能。二、簡(jiǎn)答題（本大題共5個(gè)小題，共25分)1、（本題5分）在歸并排序中，解釋歸并的概念和實(shí)現(xiàn)步驟，分析歸并排序的時(shí)間復(fù)雜度和空間復(fù)雜度，并舉例說(shuō)明其應(yīng)用場(chǎng)景。2、（本題5分）詳細(xì)闡述在具有n個(gè)元素的雙向循環(huán)鏈表中，如何在指定位置插入節(jié)點(diǎn)，并給出具體的算法步驟和代碼實(shí)現(xiàn)。3、（本題5分）對(duì)于一個(gè)用鄰接表存儲(chǔ)的圖，說(shuō)明如何判斷圖是否為平面圖，給出一種有效的算法并分析其時(shí)間復(fù)雜度。4、（本題5分）論述在二叉樹(shù)的變形結(jié)構(gòu)中，如紅黑樹(shù)、AVL樹(shù)，如何實(shí)現(xiàn)節(jié)點(diǎn)的刪除操作。5、（本題5分）分析KMP算法中next數(shù)組的計(jì)算方法和作用，以及如何通過(guò)優(yōu)化提高匹配效率。三、設(shè)計(jì)題（本大題共5個(gè)小題，共25分)1、（本題5分）設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)一個(gè)公司員工的信息，包括姓名、工號(hào)、部門(mén)、工資等，實(shí)現(xiàn)插入、刪除、查找和遍歷操作。2、（本題5分）以鏈表為基礎(chǔ)，設(shè)計(jì)一個(gè)旅游景點(diǎn)門(mén)票預(yù)訂管理系統(tǒng)，支持門(mén)票的預(yù)訂和退票。3、（本題5分）設(shè)計(jì)一個(gè)算法，用鄰接表表示一個(gè)無(wú)向圖，判斷圖是否為連通圖。4、（本題5分）設(shè)計(jì)一個(gè)程序，使用圖的鄰接表存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)深度優(yōu)先和廣度優(yōu)先遍歷的動(dòng)畫(huà)演示。5、（本題5分）設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)和算法，用于管理一個(gè)醫(yī)院的住院病人費(fèi)用管理系統(tǒng)，能夠準(zhǔn)確計(jì)算病人的住院費(fèi)用。四、綜合題（本大題共3個(gè)小題，共30分)1、（本題10分）某公司的項(xiàng)目任務(wù)分配系統(tǒng)需要對(duì)多個(gè)項(xiàng)目的任務(wù)和員工分配情況進(jìn)行管理。任務(wù)信息包括任務(wù)編號(hào)、任務(wù)描述、負(fù)責(zé)人、截止日期等，員工信息包括員工編號(hào)、姓名、負(fù)責(zé)任務(wù)等?？紤]使用線索二叉樹(shù)來(lái)存儲(chǔ)這些信息。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)以下功能：（1）插入新的任務(wù)或員工信息；（2）刪除已完成的任務(wù)或離職員工信息；（3）按照截止日期對(duì)任務(wù)進(jìn)行排序；（4）查找某個(gè)員工負(fù)責(zé)的所有任務(wù)。分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。2、（本題10分）某航空公司的訂票系統(tǒng)需要對(duì)航班信息和乘客訂票情況進(jìn)行管理。航班信息包括航班號(hào)、起降時(shí)間、起降地點(diǎn)、座位數(shù)量等，乘客訂票信息包括乘客姓名、身份證號(hào)、航班號(hào)、座位號(hào)等。這些信息以哈希表和鏈表的組合形式存儲(chǔ)。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)以下功能：（1）查詢某個(gè)航班的剩余座位數(shù)量；（2）為乘客預(yù)訂指定航班的座位；（3）取消乘客的訂票；（4）統(tǒng)計(jì)每個(gè)航班