吉林建筑大學(xué)《數(shù)據(jù)結(jié)構(gòu)B》2021-2022學(xué)年第一學(xué)期期末試卷

學(xué)校________________班級(jí)____________姓名____________考場____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁吉林建筑大學(xué)《數(shù)據(jù)結(jié)構(gòu)B》

2021-2022學(xué)年第一學(xué)期期末試卷題號(hào)一二三四總分得分一、單選題（本大題共15個(gè)小題，每小題2分，共30分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、采用模擬電子技術(shù)設(shè)計(jì)一個(gè)運(yùn)算跨導(dǎo)放大器（OTA），給出其性能特點(diǎn)和應(yīng)用場景。2、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉搜索樹，其平均查找長度的期望值在什么量級(jí)？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、根據(jù)數(shù)字信號(hào)處理理論，設(shè)計(jì)一個(gè)圖像銳化處理系統(tǒng)，增強(qiáng)圖像的邊緣和細(xì)節(jié)信息。4、設(shè)計(jì)一個(gè)基于PLC的熱電廠鍋爐控制系統(tǒng)，實(shí)現(xiàn)對(duì)鍋爐水位、蒸汽壓力、溫度等參數(shù)的自動(dòng)控制。5、假設(shè)正在設(shè)計(jì)一個(gè)網(wǎng)絡(luò)數(shù)據(jù)包過濾系統(tǒng)，需要根據(jù)數(shù)據(jù)包的源地址、目的地址、協(xié)議類型等信息進(jìn)行快速的過濾和處理。以下哪種數(shù)據(jù)結(jié)構(gòu)和算法的組合最適合實(shí)現(xiàn)數(shù)據(jù)包的高效過濾？（）A.決策樹和分類算法B.位圖和位運(yùn)算C.圖和最短路徑算法D.數(shù)組和遍歷算法6、設(shè)計(jì)一個(gè)數(shù)字信號(hào)調(diào)制解調(diào)多模式電路，能夠支持多種調(diào)制解調(diào)方式，提高通信的靈活性。7、設(shè)計(jì)一個(gè)簡單的無線充電系統(tǒng)，輸出功率為5W，效率不低于70%，說明系統(tǒng)原理和關(guān)鍵部件。8、設(shè)計(jì)一個(gè)數(shù)字信號(hào)處理中IIR濾波器和FIR濾波器的性能比較方案，在相同條件下分析濾波效果和資源消耗。9、利用鎖相環(huán)技術(shù)設(shè)計(jì)一個(gè)頻率合成器，能夠輸出穩(wěn)定的、可調(diào)節(jié)的頻率信號(hào)，給出頻率合成器的整體架構(gòu)和各部分的詳細(xì)設(shè)計(jì)。10、設(shè)計(jì)一個(gè)基于運(yùn)算放大器的求和放大器電路，能夠?qū)崿F(xiàn)多個(gè)輸入信號(hào)的加權(quán)求和。11、設(shè)計(jì)一個(gè)基于ARM處理器的嵌入式系統(tǒng)，實(shí)現(xiàn)特定的功能，如數(shù)據(jù)采集、處理和傳輸，描述系統(tǒng)的硬件架構(gòu)和軟件編程思路。12、設(shè)計(jì)一個(gè)基于藍(lán)牙m(xù)esh技術(shù)的智能照明控制系統(tǒng)，能夠?qū)崿F(xiàn)多個(gè)燈具的分組控制和場景切換。13、設(shè)計(jì)一個(gè)基于Arduino的智能寵物喂食器，能夠根據(jù)設(shè)定的時(shí)間和食量自動(dòng)為寵物投放食物，并通過手機(jī)APP進(jìn)行遠(yuǎn)程控制和監(jiān)控。14、樹的存儲(chǔ)方式有多種，如雙親表示法、孩子表示法、孩子兄弟表示法等。假設(shè)要快速找到一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，以下哪種存儲(chǔ)方式可能最為合適？（）A.雙親表示法B.孩子表示法C.孩子兄弟表示法D.以上方式效果相同15、設(shè)計(jì)一個(gè)基于運(yùn)算放大器的電壓比較器電路，能夠比較兩個(gè)輸入電壓的大小，并輸出高低電平信號(hào)。二、簡答題（本大題共3個(gè)小題，共15分)1、（本題5分）解釋數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用場景，如遞歸函數(shù)的實(shí)現(xiàn)、深度優(yōu)先搜索的輔助結(jié)構(gòu)等，并說明其原理。2、（本題5分）解釋如何在一個(gè)具有n個(gè)元素的堆中，進(jìn)行插入操作，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題5分）詳細(xì)說明如何在二叉搜索樹中查找第k小的元素，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度。三、綜合題（本大題共5個(gè)小題，共25分)1、（本題5分）某銀行的賬戶管理系統(tǒng)需要存儲(chǔ)客戶的賬戶信息，如賬戶號(hào)碼、客戶姓名、余額、交易記錄等。設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)賬戶的開戶、銷戶、存款、取款、轉(zhuǎn)賬等操作，同時(shí)能夠快速查詢賬戶余額和交易明細(xì)，保障賬戶數(shù)據(jù)的安全性和準(zhǔn)確性。2、（本題5分）一個(gè)社交網(wǎng)絡(luò)平臺(tái)需要管理用戶之間的好友關(guān)系。好友關(guān)系以鄰接表的形式存儲(chǔ)在圖結(jié)構(gòu)中。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)以下功能：（1）判斷兩個(gè)用戶是否為好友；（2）找出某個(gè)用戶的所有好友；（3）計(jì)算某個(gè)用戶的好友度數(shù)；（4）找出共同好友最多的兩個(gè)用戶。分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題5分）一個(gè)圖書館的讀者借閱管理系統(tǒng)需要存儲(chǔ)讀者的借閱信息，包括讀者編號(hào)、讀者姓名、借閱圖書編號(hào)、借閱日期、應(yīng)還日期等。系統(tǒng)要支持快速查找讀者的借閱記錄、按照應(yīng)還日期對(duì)借閱記錄進(jìn)行排序、新增借閱、歸還圖書操作。請(qǐng)?jiān)O(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)和算法，并給出代碼實(shí)現(xiàn)和性能評(píng)估。4、（本題5分）某學(xué)校的圖書館管理系統(tǒng)需要記錄大量的圖書信息，包括圖書編號(hào)、書名、作者、出版社、出版年份、館藏?cái)?shù)量、借閱狀態(tài)等。請(qǐng)為該系統(tǒng)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，能夠快速查找特定圖書、按作者或出版社分類查詢、統(tǒng)計(jì)熱門圖書，并支持新書的入庫和舊書的刪除操作。5、（本題5分）某醫(yī)院的病歷管理系統(tǒng)需要對(duì)患者的病歷信息進(jìn)行高效存儲(chǔ)和檢索。病歷信息包括患者編號(hào)、姓名、病癥、治療方案、主治醫(yī)師等?？紤]使用B樹或B+樹來存儲(chǔ)這些信息。請(qǐng)?jiān)O(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)并實(shí)現(xiàn)以下功能：（1）插入一個(gè)新的病歷；（2）刪除一個(gè)指定的病歷；（3）根據(jù)患者編號(hào)快速查找病歷；（4）按病癥對(duì)病歷進(jìn)行排序并輸出。分析所設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和算法的性能。四、設(shè)計(jì)題（本大題共3個(gè)小題，共30分)1、（本題10分）設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)