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

《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)》2021-2022學(xué)年第一學(xué)期期末試卷題號(hào)一二三四總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、設(shè)計(jì)一個(gè)基于FPGA的圖像縮放系統(tǒng)，能夠?qū)斎雸D像進(jìn)行任意比例的縮放，說(shuō)明算法原理和硬件實(shí)現(xiàn)。2、設(shè)計(jì)一個(gè)基于FPGA的視頻圖像處理系統(tǒng)，能夠?qū)崿F(xiàn)圖像縮放、旋轉(zhuǎn)、灰度化等基本操作。3、設(shè)計(jì)一個(gè)數(shù)字溫度計(jì)液位計(jì)智能監(jiān)測(cè)電路，能夠自動(dòng)監(jiān)測(cè)溫度和液位的變化，并給出預(yù)警提示。4、在一個(gè)需要對(duì)大量數(shù)據(jù)進(jìn)行去重操作的數(shù)據(jù)處理任務(wù)中，以下哪種數(shù)據(jù)結(jié)構(gòu)可以有效地幫助實(shí)現(xiàn)這個(gè)功能？（）A.集合B.樹(shù)C.鏈表D.隊(duì)列5、設(shè)計(jì)一個(gè)太陽(yáng)能路燈控制器智能管理與節(jié)能優(yōu)化電路，能夠?qū)崿F(xiàn)路燈的智能管理和節(jié)能優(yōu)化，提高能源利用效率。6、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)中，若每個(gè)節(jié)點(diǎn)的度均不超過(guò)2，則該二叉樹(shù)中葉子節(jié)點(diǎn)的數(shù)量至少為：（）A.n/2B.(n+1)/2C.n-1D.n7、設(shè)計(jì)一個(gè)基于單片機(jī)的智能小車(chē)控制系統(tǒng)，能夠?qū)崿F(xiàn)小車(chē)的自動(dòng)避障、循跡和遠(yuǎn)程控制功能。8、設(shè)計(jì)一個(gè)基于數(shù)字信號(hào)處理的語(yǔ)音合成系統(tǒng)，能夠?qū)⑽谋巨D(zhuǎn)換為自然流暢的語(yǔ)音。9、已知一個(gè)棧的進(jìn)棧序列為1，2，3，4，5。則下列序列中，不可能是出棧序列的是：（）A.5，4，3，2，1B.4，5，3，2，1C.4，3，5，1，2D.1，2，3，4，510、設(shè)計(jì)一個(gè)數(shù)字信號(hào)發(fā)生器電路，能夠產(chǎn)生不同類(lèi)型的數(shù)字信號(hào)，如脈沖信號(hào)、方波信號(hào)、正弦波信號(hào)等，信號(hào)頻率和幅度可調(diào)節(jié)。11、AVL樹(shù)是一種平衡二叉搜索樹(shù)。關(guān)于AVL樹(shù)的特點(diǎn)，以下描述哪一項(xiàng)是不正確的？（）A.AVL樹(shù)通過(guò)旋轉(zhuǎn)操作來(lái)保持樹(shù)的平衡，左右子樹(shù)的高度差不超過(guò)1B.在AVL樹(shù)中進(jìn)行插入和刪除操作后，需要通過(guò)調(diào)整來(lái)恢復(fù)平衡，時(shí)間復(fù)雜度為O(logn)C.AVL樹(shù)的查找效率在最壞情況下也能保證為O(logn)D.AVL樹(shù)的空間復(fù)雜度比普通二叉搜索樹(shù)高，不適合存儲(chǔ)大量數(shù)據(jù)12、在數(shù)據(jù)結(jié)構(gòu)的選擇中，需要考慮時(shí)間復(fù)雜度、空間復(fù)雜度和操作的便捷性等因素。以下情況中，優(yōu)先選擇數(shù)組而不是鏈表的是（）A.頻繁進(jìn)行插入和刪除操作B.事先不知道數(shù)據(jù)的規(guī)模大小C.需要快速隨機(jī)訪問(wèn)元素D.內(nèi)存空間有限13、利用數(shù)字邏輯電路設(shè)計(jì)一個(gè)數(shù)字時(shí)鐘分頻器，將輸入時(shí)鐘信號(hào)分頻為不同頻率的輸出信號(hào)。14、使用單片機(jī)設(shè)計(jì)一個(gè)智能空氣質(zhì)量監(jiān)測(cè)儀，能夠檢測(cè)多種污染物濃度并顯示，當(dāng)空氣質(zhì)量超標(biāo)時(shí)進(jìn)行報(bào)警。15、設(shè)計(jì)一個(gè)基于PLC的自動(dòng)化生產(chǎn)線控制系統(tǒng)，能夠?qū)崿F(xiàn)對(duì)生產(chǎn)線上多個(gè)設(shè)備的順序控制、邏輯控制和故障報(bào)警功能。16、設(shè)計(jì)一個(gè)音頻濾波器參數(shù)優(yōu)化電路，能夠根據(jù)輸入音頻信號(hào)的特點(diǎn)自動(dòng)優(yōu)化濾波器的參數(shù)，提高音頻質(zhì)量。17、設(shè)計(jì)一個(gè)溫度報(bào)警器電路，當(dāng)環(huán)境溫度超過(guò)設(shè)定值時(shí)，發(fā)出聲光報(bào)警信號(hào)，報(bào)警溫度可設(shè)置。18、運(yùn)用通信網(wǎng)絡(luò)原理，設(shè)計(jì)一個(gè)企業(yè)數(shù)據(jù)中心的網(wǎng)絡(luò)布線方案，確保高速、可靠的數(shù)據(jù)傳輸。19、設(shè)計(jì)一個(gè)基于D/A轉(zhuǎn)換器的三角波信號(hào)發(fā)生器電路，輸出頻率范圍為100Hz-1kHz，幅度可調(diào)。20、設(shè)計(jì)一個(gè)基于運(yùn)算放大器的求和放大器電路，能夠?qū)崿F(xiàn)多個(gè)輸入信號(hào)的加權(quán)求和。二、簡(jiǎn)答題（本大題共3個(gè)小題，共15分)1、（本題5分）什么是二叉搜索樹(shù)的刪除操作的非遞歸實(shí)現(xiàn)？請(qǐng)描述其實(shí)現(xiàn)過(guò)程。2、（本題5分）比較快速排序和選擇排序在最壞情況下的元素交換次數(shù)。3、（本題5分）在一個(gè)具有n個(gè)元素的有序鏈表中，如何刪除所有值重復(fù)的節(jié)點(diǎn)，只保留一個(gè)，給出算法思路和時(shí)間復(fù)雜度分析。三、設(shè)計(jì)題（本大題共5個(gè)小題，共25分)1、（本題5分）設(shè)計(jì)一個(gè)算法，利用鏈表實(shí)現(xiàn)一個(gè)隊(duì)列，模擬銀行叫號(hào)系統(tǒng)的排隊(duì)情況。2、（本題5分）設(shè)計(jì)一個(gè)基于紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)插入、刪除和查找操作。3、（本題5分）設(shè)計(jì)一個(gè)程序，使用選擇排序算法對(duì)給定的浮點(diǎn)數(shù)數(shù)組進(jìn)行排序，輸出排序后的數(shù)組。4、（本題5分）設(shè)計(jì)一個(gè)程序，使用棧將十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)，并輸出轉(zhuǎn)換結(jié)果。5、（本題5分）設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)和算法，模擬一個(gè)健身房的會(huì)員管理系統(tǒng)，能夠存儲(chǔ)會(huì)員信息、健身課程預(yù)約情況等，實(shí)現(xiàn)會(huì)員注冊(cè)、課程預(yù)約和消費(fèi)記錄功能。四、綜合題（本大題共2個(gè)小題，共20分)1、（本題10分）某音樂(lè)播放平臺(tái)需要管理大量的音樂(lè)文件信息，包括歌曲ID、歌曲名稱(chēng)、歌手、專(zhuān)輯、播放次數(shù)、下載次數(shù)等。設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)這些音樂(lè)信息，能夠快速查找特定歌曲、按照歌手或?qū)］嫹诸?lèi)、更新播放和下載次數(shù)，并統(tǒng)計(jì)熱門(mén)歌曲。2、（本題10分）某醫(yī)院的藥品庫(kù)存管理系統(tǒng)需