昆明理工大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2020-2021學(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)與算法》

2020-2021學(xué)年第一學(xué)期期末試卷題號(hào)一二三四總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題1分，共20分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、設(shè)計(jì)一個(gè)基于藍(lán)牙4.2技術(shù)的智能手環(huán)，能夠監(jiān)測(cè)運(yùn)動(dòng)數(shù)據(jù)（如步數(shù)、距離、消耗卡路里等）和睡眠質(zhì)量。2、在一個(gè)具有n個(gè)頂點(diǎn)和m條邊的無向圖中，使用鄰接表存儲(chǔ)，空間復(fù)雜度大約是多少？（）A.O(n+m)B.O(n^2)C.O(m^2)D.O(nm)3、設(shè)計(jì)一個(gè)基于ADC和微控制器的光照強(qiáng)度測(cè)量系統(tǒng)，能夠測(cè)量0-10000lux的光照強(qiáng)度，精度達(dá)到1lux。4、設(shè)計(jì)一個(gè)基于模擬積分器和比較器的電壓-頻率轉(zhuǎn)換器（VFC），分析其性能特點(diǎn)。5、在數(shù)據(jù)結(jié)構(gòu)中，數(shù)組是一種常見的存儲(chǔ)結(jié)構(gòu)。關(guān)于數(shù)組的特點(diǎn)和應(yīng)用，以下描述不正確的是（）A.數(shù)組的元素在內(nèi)存中是連續(xù)存儲(chǔ)的，便于隨機(jī)訪問B.數(shù)組的大小在定義后通常不能改變C.二維數(shù)組在內(nèi)存中是按行優(yōu)先或列優(yōu)先的順序存儲(chǔ)的D.數(shù)組只能用于存儲(chǔ)相同類型的數(shù)據(jù)，不能存儲(chǔ)不同類型的數(shù)據(jù)6、設(shè)計(jì)一個(gè)基于藍(lán)牙的智能門鎖系統(tǒng)，能夠通過手機(jī)藍(lán)牙開鎖，并記錄開鎖日志，描述系統(tǒng)硬件和軟件設(shè)計(jì)。7、設(shè)計(jì)一個(gè)基于模擬移相器和濾波器的相位補(bǔ)償系統(tǒng)，改善系統(tǒng)的相位特性。8、想象一個(gè)需要對(duì)一組數(shù)據(jù)進(jìn)行范圍查詢（例如查找大于某個(gè)值且小于另一個(gè)值的數(shù)據(jù)）的場(chǎng)景，以下哪種數(shù)據(jù)結(jié)構(gòu)可能是最有效的？（）A.二叉搜索樹，通過中序遍歷可以實(shí)現(xiàn)范圍查詢，但效率一般B.線段樹，專門用于高效的區(qū)間查詢和更新C.哈希表，不便于進(jìn)行范圍查詢D.隊(duì)列，先進(jìn)先出，無法實(shí)現(xiàn)范圍查詢9、設(shè)計(jì)一個(gè)基于PLC的自動(dòng)化灌溉系統(tǒng)，能夠根據(jù)土壤濕度自動(dòng)控制灌溉設(shè)備的啟停。10、設(shè)計(jì)一個(gè)基于數(shù)字電位器的音量調(diào)節(jié)系統(tǒng)，能夠?qū)崿F(xiàn)對(duì)音頻信號(hào)音量的連續(xù)調(diào)節(jié)，且調(diào)節(jié)范圍可設(shè)定。11、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉排序樹中，查找一個(gè)特定元素的平均時(shí)間復(fù)雜度為：（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)12、設(shè)計(jì)一個(gè)基于運(yùn)算放大器的音頻放大器電路，要求輸入阻抗不小于10kΩ，輸出功率不小于10W，總諧波失真小于1%。13、在一個(gè)需要對(duì)一組數(shù)據(jù)進(jìn)行去重操作的場(chǎng)景中，以下哪種數(shù)據(jù)結(jié)構(gòu)可以有效地實(shí)現(xiàn)這個(gè)功能？（）A.集合，自動(dòng)去除重復(fù)元素B.數(shù)組，需要額外的算法進(jìn)行去重C.鏈表，去重操作復(fù)雜且效率低D.棧，不適合進(jìn)行去重操作14、設(shè)計(jì)一個(gè)簡(jiǎn)單的雷達(dá)測(cè)距系統(tǒng)，能夠測(cè)量目標(biāo)物體的距離，并顯示測(cè)量結(jié)果，分析其測(cè)量精度和誤差來源。15、設(shè)計(jì)一個(gè)簡(jiǎn)單的集成電路放大器，要求具有特定的增益、帶寬和輸入輸出阻抗，分析其性能并優(yōu)化設(shè)計(jì)以滿足特定要求。16、利用數(shù)字電路技術(shù)，設(shè)計(jì)一個(gè)地鐵自動(dòng)檢票系統(tǒng)，實(shí)現(xiàn)車票驗(yàn)證、扣費(fèi)和閘機(jī)控制功能。17、設(shè)計(jì)一個(gè)基于STM32的無刷直流電機(jī)驅(qū)動(dòng)系統(tǒng)，采用FOC控制算法，實(shí)現(xiàn)精確調(diào)速和位置控制，給出系統(tǒng)組成和軟件流程。18、設(shè)計(jì)一個(gè)計(jì)算機(jī)網(wǎng)絡(luò)中的IP地址分配方案，滿足特定網(wǎng)絡(luò)規(guī)模和拓?fù)浣Y(jié)構(gòu)的需求。19、設(shè)計(jì)一個(gè)基于FPGA的圖像旋轉(zhuǎn)系統(tǒng)，能夠?qū)斎雸D像進(jìn)行90度、180度和270度旋轉(zhuǎn)，說明算法和硬件實(shí)現(xiàn)。20、設(shè)計(jì)一個(gè)集成電路制造中的化學(xué)氣相沉積（CVD）設(shè)備控制系統(tǒng)，優(yōu)化工藝參數(shù)。二、簡(jiǎn)答題（本大題共5個(gè)小題，共25分)1、（本題5分）解釋在平衡二叉搜索樹中，插入操作導(dǎo)致不平衡時(shí)的單旋轉(zhuǎn)和雙旋轉(zhuǎn)的適用情況。2、（本題5分）在一個(gè)具有n個(gè)頂點(diǎn)的無向連通圖中，闡述如何使用普里姆算法和克魯斯卡爾算法構(gòu)建最小生成樹，比較兩種算法的思路和時(shí)間復(fù)雜度。3、（本題5分）分析在數(shù)據(jù)結(jié)構(gòu)中如何使用鏈表實(shí)現(xiàn)棧和隊(duì)列，并比較其與順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的優(yōu)缺點(diǎn)。4、（本題5分）在一個(gè)具有n個(gè)元素的有序數(shù)組中，如何進(jìn)行二分查找的變形操作，如查找第一個(gè)等于給定值的元素，給出算法思路和時(shí)間復(fù)雜度分析。5、（本題5分）解釋堆的概念，包括大根堆和小根堆，給出堆的調(diào)整算法步驟，并說明堆在排序算法中的應(yīng)用。三、設(shè)計(jì)題（本大題共5個(gè)小題，共25分)1、（本題5分）設(shè)計(jì)一個(gè)程序，使用桶排序?qū)o定的一組整數(shù)進(jìn)行排序，輸出排序后的數(shù)組。2、（本題5分）設(shè)計(jì)一個(gè)程序，使用弗洛伊德算法求一個(gè)有向網(wǎng)中任意兩點(diǎn)之間的最短路徑。3、（本題5分）設(shè)計(jì)一個(gè)程序，使用鏈表實(shí)現(xiàn)對(duì)一組數(shù)據(jù)的插入、刪除和遍歷操作，用戶可以動(dòng)態(tài)地進(jìn)行數(shù)據(jù)管理。4、（本題5分）以哈希表為基礎(chǔ)，設(shè)計(jì)一個(gè)在線音樂平臺(tái)歌曲熱度統(tǒng)計(jì)系統(tǒng)，能夠?qū)崟r(shí)更新歌曲的熱度排名。5、（本題5分）設(shè)計(jì)Sunday算法的實(shí)現(xiàn)，用于字符串匹配，與其他算法對(duì)比。四、綜合題（本大題共3個(gè)小題，共30分)1、（本題10分）一個(gè)在線視頻會(huì)議系統(tǒng)需要對(duì)參會(huì)人員的狀態(tài)和發(fā)言順序進(jìn)行管理。參會(huì)人員信息包括人員編號(hào)、姓名、狀態(tài)（在線/離線）、發(fā)言順序等。這些信息以三元組表的形式存儲(chǔ)。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)以下功能：（1）查詢?cè)诰€參會(huì)人員名單；（2）調(diào)整參會(huì)人員的發(fā)言順序；（3）人員離線時(shí)更新狀態(tài)；（4）統(tǒng)計(jì)發(fā)言次數(shù)超過一定閾值的人員數(shù)量。分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。2、（本題10分）某醫(yī)院的信息系統(tǒng)需要存儲(chǔ)患者的病歷信息，包括基本信息、診斷結(jié)果、治療方案、用藥記錄等。設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，能夠方便地按照患者編號(hào)、疾病類型或治療時(shí)間進(jìn)行查詢和統(tǒng)計(jì)，并支持