遼寧大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法分析》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)與算法分析》

2021-2022學(xué)年第一學(xué)期期末試卷題號(hào)一二三四總分得分一、單選題（本大題共15個(gè)小題，每小題2分，共30分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在圖的遍歷算法中，深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）是兩種基本方法。關(guān)于這兩種算法，以下描述哪一項(xiàng)是不正確的？（）A.DFS從起始節(jié)點(diǎn)開始，沿著一條路徑盡可能深地訪問節(jié)點(diǎn)，然后回溯B.BFS從起始節(jié)點(diǎn)開始，逐層地訪問相鄰節(jié)點(diǎn)C.DFS和BFS的時(shí)間復(fù)雜度均與圖的節(jié)點(diǎn)數(shù)量和邊的數(shù)量有關(guān)，通常為O(n+m)，其中n是節(jié)點(diǎn)數(shù)量，m是邊的數(shù)量D.DFS適合用于查找最短路徑，BFS適合用于判斷圖是否連通2、樹的存儲(chǔ)結(jié)構(gòu)除了常見的二叉樹表示法，還有多叉樹的表示方法。關(guān)于多叉樹的存儲(chǔ)方式，以下描述哪一項(xiàng)是不正確的？（）A.可以使用孩子兄弟表示法來存儲(chǔ)多叉樹，便于實(shí)現(xiàn)樹的遍歷和操作B.父指針數(shù)組法通過為每個(gè)節(jié)點(diǎn)存儲(chǔ)指向其父節(jié)點(diǎn)的指針來表示多叉樹C.孩子鏈表法為每個(gè)節(jié)點(diǎn)建立一個(gè)孩子鏈表，存儲(chǔ)其所有孩子節(jié)點(diǎn)的信息D.無論采用哪種存儲(chǔ)方式，對(duì)多叉樹的操作效率都是相同的3、設(shè)計(jì)一個(gè)基于熱電偶的溫度測量系統(tǒng)，能夠測量較高溫度范圍，并對(duì)測量結(jié)果進(jìn)行冷端補(bǔ)償和線性化處理。4、利用電力電子技術(shù)設(shè)計(jì)一個(gè)太陽能充電控制器，實(shí)現(xiàn)對(duì)太陽能電池板輸出的電能進(jìn)行有效管理和存儲(chǔ)。5、選擇排序是另一種基本的排序算法。以下關(guān)于選擇排序的說法，錯(cuò)誤的是：（）A.選擇排序每次從待排序序列中選擇最?。ɑ蜃畲螅┑脑兀诺揭雅判蛐蛄械哪┪睟.選擇排序在最壞情況下的時(shí)間復(fù)雜度為O(n^2)C.選擇排序是一種不穩(wěn)定的排序算法D.選擇排序的空間復(fù)雜度較低6、設(shè)計(jì)一個(gè)數(shù)字電壓表電路，能夠測量直流電壓，測量范圍為0V到100V，精度為±0.1V。7、設(shè)計(jì)一個(gè)基于D/A轉(zhuǎn)換器的方波信號(hào)發(fā)生器電路，輸出頻率范圍為100Hz-10kHz，占空比可調(diào)。8、設(shè)計(jì)一個(gè)基于STM32的智能車載系統(tǒng)，能夠?qū)崿F(xiàn)導(dǎo)航、多媒體播放和車輛狀態(tài)監(jiān)測等功能，描述系統(tǒng)的硬件架構(gòu)和軟件實(shí)現(xiàn)。9、在一個(gè)圖像處理程序中，需要對(duì)圖像的像素進(jìn)行頻繁的操作和存儲(chǔ)。如果圖像是一個(gè)二維的灰度圖像，以下哪種數(shù)據(jù)結(jié)構(gòu)可能是最適合存儲(chǔ)像素值的？（）A.二維數(shù)組，直觀表示圖像像素B.鏈表數(shù)組，每個(gè)鏈表存儲(chǔ)一行像素C.二叉樹，按照像素值大小存儲(chǔ)D.哈希表，通過像素坐標(biāo)映射值10、設(shè)計(jì)一個(gè)基于藍(lán)牙5.0技術(shù)的智能家居設(shè)備組網(wǎng)系統(tǒng)，實(shí)現(xiàn)設(shè)備之間的互聯(lián)互通和協(xié)同工作。11、設(shè)計(jì)一個(gè)數(shù)字鑒相器，能夠測量兩個(gè)高頻信號(hào)的相位差，精度達(dá)到0.1度，給出電路結(jié)構(gòu)和工作原理。12、設(shè)計(jì)一個(gè)基于單片機(jī)的智能家電能耗監(jiān)測系統(tǒng)，實(shí)時(shí)監(jiān)測家電的用電情況并進(jìn)行數(shù)據(jù)分析。13、設(shè)計(jì)一個(gè)溫度控制系統(tǒng)擴(kuò)展電路，能夠增加溫度控制的精度和穩(wěn)定性，并且具有遠(yuǎn)程控制功能。14、設(shè)計(jì)一個(gè)紅外線測距電路，能夠測量物體與傳感器之間的距離，測量范圍為10cm到100cm，精度為±1cm。15、設(shè)計(jì)一個(gè)數(shù)字電壓表電流表電路，能夠同時(shí)測量直流電壓和電流，電壓測量范圍為0V到100V，電流測量范圍為0A到1A，精度為±0.1V和±0.01A。二、簡答題（本大題共3個(gè)小題，共15分)1、（本題5分）解釋什么是后綴樹，并說明其在字符串匹配中的優(yōu)勢。2、（本題5分）詳細(xì)說明如何在一個(gè)圖中判斷兩個(gè)頂點(diǎn)是否在同一個(gè)連通分量中。3、（本題5分）在數(shù)據(jù)結(jié)構(gòu)中，闡述如何使用塊狀鏈表進(jìn)行高效的插入和刪除操作，給出算法步驟和實(shí)現(xiàn)代碼，并分析其性能優(yōu)勢。三、綜合題（本大題共5個(gè)小題，共25分)1、（本題5分）一個(gè)停車場管理系統(tǒng)需要存儲(chǔ)車位信息，包括車位編號(hào)、位置、是否占用、車輛牌照等。系統(tǒng)要能夠快速查找空閑車位、按照車位位置對(duì)車位進(jìn)行排序、車輛入場和出場操作、修改車位的占用狀態(tài)。請(qǐng)選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，并詳細(xì)說明算法和代碼實(shí)現(xiàn)，以及性能分析。2、（本題5分）某音樂平臺(tái)需要對(duì)用戶的播放記錄和收藏歌曲進(jìn)行管理。用戶信息包括用戶ID、播放歷史、收藏歌曲等?？紤]使用左偏樹來存儲(chǔ)這些信息。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)以下功能：（1）查詢用戶最近播放的歌曲；（2）添加用戶新的播放記錄或收藏歌曲；（3）刪除用戶不再喜歡的歌曲；（4）按照播放次數(shù)對(duì)用戶的歌曲進(jìn)行排序。分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題5分）某公司的項(xiàng)目任務(wù)分配系統(tǒng)需要對(duì)多個(gè)項(xiàng)目的任務(wù)和員工分配情況進(jìn)行管理。任務(wù)信息包括任務(wù)編號(hào)、任務(wù)描述、負(fù)責(zé)人、截止日期等，員工信息包括員工編號(hào)、姓名、負(fù)責(zé)任務(wù)等?？紤]使用線索二叉樹來存儲(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ù)雜度。4、（本題5分）某在線圖書館的圖書借閱系統(tǒng)需要記錄圖書的借閱者、借閱時(shí)間、應(yīng)還時(shí)間、是否逾期等信息。設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來管理圖書借閱情況，支持借閱、歸還、續(xù)借等操作，能夠及時(shí)提醒借閱者歸還圖書并統(tǒng)計(jì)圖書的借閱頻率。5、（本題5分）一個(gè)在線課程平臺(tái)的作業(yè)管理系統(tǒng)需要記錄作業(yè)信息、學(xué)生提交情況和教師批改情況。作業(yè)信息包括作業(yè)ID、課程ID、作業(yè)內(nèi)容、截止時(shí)間，學(xué)生提交情況包括學(xué)生ID、作業(yè)ID、提交時(shí)間、提交內(nèi)容，教師批改情況包括作業(yè)ID、批改時(shí)間、批改分?jǐn)?shù)、評(píng)語。請(qǐng)?jiān)O(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來管理作業(yè)數(shù)據(jù)，實(shí)現(xiàn)作業(yè)的發(fā)布、提交、批改、查詢，并統(tǒng)計(jì)學(xué)生的作業(yè)完成情況。四、設(shè)計(jì)題（本大題共3個(gè)小題，共30分)1、（本題10分）設(shè)計(jì)