南京藝術(shù)學(xué)院《數(shù)據(jù)結(jié)構(gòu)（Ⅰ）》2023-2024學(xué)年第一學(xué)期期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁南京藝術(shù)學(xué)院

《數(shù)據(jù)結(jié)構(gòu)（Ⅰ）》2023-2024學(xué)年第一學(xué)期期末試卷題號一二三四總分得分一、單選題（本大題共15個小題，每小題1分，共15分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、設(shè)計一個基于STM32的智能農(nóng)業(yè)灌溉系統(tǒng)，能夠根據(jù)土壤濕度和氣象數(shù)據(jù)自動控制灌溉設(shè)備的運行，實現(xiàn)精準(zhǔn)灌溉和水資源節(jié)約。2、利用鎖相環(huán)技術(shù)設(shè)計一個頻率合成器，能夠輸出穩(wěn)定的、可調(diào)節(jié)的頻率信號，給出頻率合成器的整體架構(gòu)和各部分的詳細(xì)設(shè)計。3、設(shè)計一個光通信中的摻鉺光纖放大器（EDFA）驅(qū)動電路，實現(xiàn)對EDFA的穩(wěn)定驅(qū)動和增益控制。4、利用傳感器設(shè)計一個自動照明控制系統(tǒng)，根據(jù)環(huán)境光線強度自動控制燈光的開啟和關(guān)閉，并可以調(diào)節(jié)燈光亮度。5、歸并排序同樣是一種分治算法，它將數(shù)組不斷地分成兩半，然后將兩半合并成一個有序的數(shù)組。歸并排序的空間復(fù)雜度主要取決于：（）A.數(shù)組的初始大小B.遞歸的深度C.合并操作的次數(shù)D.數(shù)據(jù)的分布情況6、設(shè)計一個無線遙控器智能學(xué)習(xí)電路，能夠?qū)W習(xí)其他遙控器的編碼，實現(xiàn)一個遙控器控制多個設(shè)備。7、設(shè)計一個基于FPGA的UART通信模塊，波特率可設(shè)置，數(shù)據(jù)位、停止位可配置，給出硬件實現(xiàn)和測試方案。8、利用電力電子技術(shù)設(shè)計一個直流電機驅(qū)動器，實現(xiàn)電機的正反轉(zhuǎn)、調(diào)速和制動控制。9、設(shè)計一個基于數(shù)字邏輯的電梯控制系統(tǒng)，實現(xiàn)電梯的上下運行、樓層停靠和超重報警等功能。10、在一個編譯器的符號表實現(xiàn)中，需要存儲變量名、類型、作用域等信息，并能夠快速查找、插入和刪除符號。以下哪種數(shù)據(jù)結(jié)構(gòu)可能是最適合的？（）A.紅黑樹，平衡的搜索結(jié)構(gòu)B.鏈表，動態(tài)操作方便C.棧，后進(jìn)先出管理符號D.隊列，先進(jìn)先出處理符號11、設(shè)計一個太陽能充電控制器，能夠?qū)μ柲茈姵匕宓妮敵鲞M(jìn)行控制和管理，實現(xiàn)對蓄電池的有效充電，包括電路設(shè)計和控制策略。12、B樹和B+樹常用于數(shù)據(jù)庫和文件系統(tǒng)中。假設(shè)我們正在分析一個B樹的結(jié)構(gòu)。以下關(guān)于B樹和B+樹的描述，哪一項是不準(zhǔn)確的？（）A.B樹的階數(shù)越大，樹的高度越小，查找效率越高B.B+樹的所有葉子節(jié)點通過指針連接成一個鏈表，便于范圍查詢C.B樹和B+樹在插入和刪除節(jié)點時，都需要進(jìn)行分裂和合并操作來保持樹的結(jié)構(gòu)D.B樹和B+樹只適用于數(shù)據(jù)量較小的情況，對于大規(guī)模數(shù)據(jù)不適用13、運用通信網(wǎng)絡(luò)技術(shù)，設(shè)計一個智能工廠的5G專網(wǎng)方案，滿足工業(yè)生產(chǎn)中對低延遲、高可靠通信的需求。14、設(shè)計一個高頻射頻放大器電路，工作頻率在5GHz，增益大于20dB，給出電路結(jié)構(gòu)和穩(wěn)定性分析。15、假設(shè)正在開發(fā)一個股票交易系統(tǒng)，需要實時記錄每只股票的價格變化，并能夠快速地找出價格漲幅最大和跌幅最大的股票。同時，要支持對股票價格的歷史數(shù)據(jù)進(jìn)行分析。以下哪種數(shù)據(jù)結(jié)構(gòu)和算法的搭配最適合這個系統(tǒng)？（）A.最大堆和最小堆，分別存儲漲幅和跌幅最大的股票信息B.紅黑樹和中序遍歷，獲取股票價格的排序C.跳表和插入排序，更新股票價格數(shù)據(jù)D.線段樹和歸并排序，分析股票價格歷史數(shù)據(jù)二、簡答題（本大題共4個小題，共20分)1、（本題5分）深入探討在一個具有n個元素的循環(huán)隊列中，如何有效地判斷隊列是否已滿。2、（本題5分）在一個具有n個頂點的有向圖中，如何判斷圖中是否存在回路？3、（本題5分）描述二叉樹的遍歷算法在二叉樹的路徑問題變種（如路徑之和為給定值的路徑數(shù)量）中的應(yīng)用。4、（本題5分）解釋什么是后綴表達(dá)式，說明如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，并利用棧實現(xiàn)后綴表達(dá)式的求值。三、綜合題（本大題共5個小題，共25分)1、（本題5分）某學(xué)校的選課系統(tǒng)需要記錄課程和學(xué)生的選課信息。課程有課程ID、課程名稱、授課教師、容量等，學(xué)生選課信息包括學(xué)生ID、課程ID。請設(shè)計數(shù)據(jù)結(jié)構(gòu)來管理選課數(shù)據(jù)，能夠快速查詢課程余量、學(xué)生選課情況、退選和補選操作，并統(tǒng)計每門課程的選課人數(shù)。2、（本題5分）一家電商平臺的物流跟蹤系統(tǒng)需要記錄包裹的運輸軌跡，包括包裹單號、運輸節(jié)點、到達(dá)時間、運輸狀態(tài)。請設(shè)計數(shù)據(jù)結(jié)構(gòu)來存儲運輸軌跡數(shù)據(jù)，能夠快速查詢包裹的當(dāng)前位置、歷史軌跡、預(yù)計到達(dá)時間，并統(tǒng)計不同運輸節(jié)點的處理效率。3、（本題5分）某旅游公司的旅游線路管理系統(tǒng)需要存儲旅游線路的信息，如線路編號、線路名稱、行程安排、價格、成團人數(shù)等。系統(tǒng)要能夠快速查找特定線路、按照價格對線路進(jìn)行排序、新增旅游線路、修改線路信息、刪除冷門線路。請設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)和算法，并給出代碼實現(xiàn)和性能評估。4、（本題5分）某在線圖書館的圖書借閱系統(tǒng)需要記錄圖書的借閱者、借閱時間、應(yīng)還時間、是否逾期等信息。設(shè)計數(shù)據(jù)結(jié)構(gòu)來管理圖書借閱情況，支持借閱、歸還、續(xù)借等操作，能夠及時提醒借閱者歸還圖書并統(tǒng)計圖書的借閱頻率。5、（本題5分）一個在線視頻會議系統(tǒng)需要對參會人員的狀態(tài)和發(fā)言順序進(jìn)行管理。參會人員信息包括人員編號、姓名、狀態(tài)（在線/離線）、發(fā)言順序等。這些信息以三元組表的形式存儲。請設(shè)計算法實現(xiàn)以下功能：（1）查詢在線參會人員名單；（2）調(diào)整參會人員的發(fā)言順序；（3）人員離線時更新狀態(tài)；（4）統(tǒng)計發(fā)言次數(shù)超過一定閾值的人員數(shù)量。分析算法的時間復(fù)雜度和空間復(fù)雜度。四、設(shè)計題（本大題共4個小題，共40分)1、（本題10分）設(shè)計一個程序，使用合適的數(shù)據(jù)結(jié)構(gòu)存儲一個醫(yī)院的患者病歷信息（患者編號、姓名、病癥、診斷結(jié)果等），并支持按照病癥進(jìn)行分類查詢和統(tǒng)計。2、（本題10分）設(shè)計一個程序，使用圖的數(shù)據(jù)結(jié)