華東師范大學(xué)《數(shù)據(jù)科學(xué)與工程導(dǎo)論》2021-2022學(xué)年第一學(xué)期期末試卷

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線第1頁(yè)，共3頁(yè)華東師范大學(xué)

《數(shù)據(jù)科學(xué)與工程導(dǎo)論》2021-2022學(xué)年第一學(xué)期期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三四總分得分一、單選題（本大題共20個(gè)小題，每小題1分，共20分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、想象一個(gè)地圖應(yīng)用，需要存儲(chǔ)不同地點(diǎn)之間的距離信息，并能夠快速找到兩個(gè)地點(diǎn)之間的最短路徑。以下哪種數(shù)據(jù)結(jié)構(gòu)和算法的組合可能是最有效的？（）A.鄰接矩陣結(jié)合深度優(yōu)先搜索算法，能表示完整的圖結(jié)構(gòu)，但對(duì)于大規(guī)模圖效率較低B.鄰接表結(jié)合廣度優(yōu)先搜索算法，節(jié)省空間，適合查找最短路徑C.十字鏈表結(jié)合迪杰斯特拉算法，結(jié)構(gòu)復(fù)雜，實(shí)現(xiàn)難度大D.哈希圖結(jié)合A*算法，適用于復(fù)雜的啟發(fā)式搜索，但對(duì)簡(jiǎn)單地圖可能過(guò)于復(fù)雜2、設(shè)計(jì)一個(gè)基于FPGA的數(shù)字信號(hào)濾波系統(tǒng)，支持在線參數(shù)調(diào)整和實(shí)時(shí)濾波，給出硬件設(shè)計(jì)和濾波算法優(yōu)化。3、在一個(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)行去重操作4、設(shè)計(jì)一個(gè)基于ARM處理器的智能家居控制系統(tǒng)，能夠?qū)崿F(xiàn)對(duì)燈光、窗簾、空調(diào)等設(shè)備的遠(yuǎn)程控制和智能調(diào)節(jié)，說(shuō)明系統(tǒng)架構(gòu)和通信協(xié)議。5、設(shè)計(jì)一個(gè)高頻射頻收發(fā)器電路，工作頻率在2.4GHz，支持藍(lán)牙和ZigBee通信，給出電路結(jié)構(gòu)和性能指標(biāo)。6、設(shè)計(jì)一個(gè)數(shù)字圖像處理中基于深度學(xué)習(xí)的圖像去噪系統(tǒng)，分析去噪效果和模型復(fù)雜度。7、設(shè)計(jì)一個(gè)簡(jiǎn)單的太陽(yáng)能路燈控制器，能夠根據(jù)日照時(shí)間和環(huán)境亮度自動(dòng)控制路燈的開(kāi)啟和關(guān)閉。8、假設(shè)正在實(shí)現(xiàn)一個(gè)電話號(hào)碼簿程序，需要快速根據(jù)姓名查找對(duì)應(yīng)的電話號(hào)碼。以下哪種數(shù)據(jù)結(jié)構(gòu)和算法的組合可能是最有效的？（）A.二叉搜索樹(shù)，進(jìn)行姓名查找B.冒泡排序后的數(shù)組，順序查找C.哈希表，直接定位電話號(hào)碼D.插入排序后的數(shù)組，二分查找9、在一個(gè)循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針指向隊(duì)尾元素。假設(shè)隊(duì)列的最大容量為10，當(dāng)前隊(duì)頭指針為5，隊(duì)尾指針為8。此時(shí)，如果進(jìn)行入隊(duì)操作，新元素應(yīng)該存儲(chǔ)在哪個(gè)位置？（）A.9B.0C.8D.710、設(shè)計(jì)一個(gè)基于數(shù)字邏輯的交通燈倒計(jì)時(shí)顯示系統(tǒng)，能夠?qū)崟r(shí)顯示每個(gè)信號(hào)燈的剩余時(shí)間。11、在一個(gè)用鄰接表表示的無(wú)向圖中，要判斷兩個(gè)頂點(diǎn)之間是否存在邊，時(shí)間復(fù)雜度為（）A.O(1)B.O(n)C.O(log?n)D.取決于頂點(diǎn)的度數(shù)12、設(shè)計(jì)一個(gè)簡(jiǎn)單的無(wú)線數(shù)據(jù)傳輸系統(tǒng)，采用Zigbee技術(shù)，實(shí)現(xiàn)多個(gè)節(jié)點(diǎn)之間的通信，描述系統(tǒng)的硬件組成和軟件流程。13、設(shè)計(jì)一個(gè)音頻功率放大器的保護(hù)電路，能夠在過(guò)流、過(guò)壓、過(guò)熱等情況下保護(hù)放大器和揚(yáng)聲器，給出電路設(shè)計(jì)和保護(hù)機(jī)制。14、設(shè)計(jì)一個(gè)基于模擬比較器的電壓監(jiān)測(cè)系統(tǒng)，當(dāng)輸入電壓超過(guò)設(shè)定的上下限時(shí)進(jìn)行報(bào)警。15、插入排序也是一種常見(jiàn)的排序算法。以下關(guān)于插入排序的敘述，不正確的是：（）A.插入排序?qū)⒋判虻脑夭迦氲揭雅判虻牟糠种泻线m的位置B.插入排序在平均情況下的時(shí)間復(fù)雜度為O(n^2)C.插入排序是一種不穩(wěn)定的排序算法D.插入排序?qū)τ谛∫?guī)模數(shù)據(jù)的排序效果較好16、設(shè)計(jì)一個(gè)基于藍(lán)牙5.2技術(shù)的智能手環(huán)，具備健康監(jiān)測(cè)、運(yùn)動(dòng)追蹤和消息提醒功能。17、在排序算法的比較中，穩(wěn)定性是一個(gè)重要的特性。以下關(guān)于排序算法穩(wěn)定性的描述，錯(cuò)誤的是（）A.穩(wěn)定的排序算法在排序過(guò)程中不會(huì)改變相同元素的相對(duì)順序B.冒泡排序、插入排序和歸并排序是穩(wěn)定的排序算法C.選擇排序和快速排序是不穩(wěn)定的排序算法D.排序算法的穩(wěn)定性對(duì)于所有應(yīng)用都是至關(guān)重要的，不穩(wěn)定的算法不能使用18、設(shè)計(jì)一個(gè)簡(jiǎn)單的直流穩(wěn)壓電源，輸出電壓為+5V、+12V和-12V，最大輸出電流為1A，電壓調(diào)整率小于1%，負(fù)載調(diào)整率小于5%。19、設(shè)計(jì)一個(gè)基于STM8的智能車庫(kù)門控制系統(tǒng)，能夠?qū)崿F(xiàn)自動(dòng)開(kāi)關(guān)、遙控和防夾功能，闡述系統(tǒng)組成和控制策略。20、冒泡排序是一種簡(jiǎn)單的排序算法。假設(shè)我們正在使用冒泡排序?qū)?shù)組進(jìn)行排序。以下關(guān)于冒泡排序的描述，哪一項(xiàng)是不準(zhǔn)確的？（）A.冒泡排序通過(guò)反復(fù)比較相鄰元素并交換位置，將最大的元素逐步“浮”到數(shù)組的末尾B.冒泡排序在最壞情況下的時(shí)間復(fù)雜度為O(n^2)，但在最好情況下可以達(dá)到O(n)C.冒泡排序是一種穩(wěn)定的排序算法，相同元素的相對(duì)順序在排序后不會(huì)改變D.冒泡排序的性能優(yōu)于其他所有排序算法，適用于各種規(guī)模的數(shù)據(jù)排序二、簡(jiǎn)答題（本大題共5個(gè)小題，共25分)1、（本題5分）詳細(xì)解釋在一個(gè)具有n個(gè)元素的二叉樹(shù)中，如何進(jìn)行按層遍歷的廣度優(yōu)先搜索的非遞歸實(shí)現(xiàn)。2、（本題5分）簡(jiǎn)述哈希表的哈希函數(shù)設(shè)計(jì)原則，包括均勻性、高效性等方面。3、（本題5分）深入分析在一個(gè)具有n個(gè)元素的鏈表中，如何在鏈表中查找指定值的前一個(gè)節(jié)點(diǎn)。4、（本題5分）解釋如何對(duì)一個(gè)無(wú)序數(shù)組進(jìn)行堆排序，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。5、（本題5分）解釋線段樹(shù)在處理動(dòng)態(tài)區(qū)間問(wèn)題時(shí)的適應(yīng)性和局限性。三、設(shè)計(jì)題（本大題共5個(gè)小題，共25分)1、（本題5分）設(shè)計(jì)一個(gè)程序，從給定的順序表中刪除一個(gè)元素，輸出刪除后的順序表。2、（本題5分）設(shè)計(jì)一個(gè)程序，使用快速排序算法對(duì)一個(gè)無(wú)向圖的邊進(jìn)行排序。3、（本題5分）設(shè)計(jì)一個(gè)程序，使用二叉樹(shù)的層次遍歷算法，輸出給定二叉樹(shù)每層節(jié)點(diǎn)的值。4、（本題5分）設(shè)計(jì)一個(gè)程序，在二叉搜索樹(shù)中刪除一個(gè)具有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)，保持樹(shù)的結(jié)構(gòu)。5、（本題5分）分析在字符串匹配中，結(jié)合多種算法提高匹配效率的設(shè)計(jì)方案。四、綜合題（本大題共3個(gè)小題，共30分)1、（本題10分）一個(gè)在線圖書館的借閱管理系統(tǒng)需要記錄圖書信息、讀者信息和借閱記錄，圖書信息包括圖書ISBN、書名、作者、出版社、可借閱狀態(tài)，讀者信息包括讀者ID、姓名、聯(lián)系方式，借閱記錄包括借閱ID、讀者ID、圖書ISBN、借閱時(shí)間、應(yīng)還時(shí)間。請(qǐng)?jiān)O(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來(lái)管理借閱數(shù)據(jù)，實(shí)現(xiàn)圖書的借閱、歸還、續(xù)借操作，查詢讀者的借閱歷史，并統(tǒng)計(jì)逾期未還的圖書。2、（本題10分）某公司的員工信息（包括員工編號(hào)、姓名、年齡、部門、工資等）以哈希表的形式存儲(chǔ)。由于公司規(guī)模擴(kuò)大，員工數(shù)量急劇增加，導(dǎo)致哈希沖突頻繁。請(qǐng)?zhí)岢龈倪M(jìn)方案，重新設(shè)計(jì)哈希函數(shù)和解決沖突的方法，并分析改進(jìn)后的時(shí)間復(fù)雜度和空間復(fù)雜度。同時(shí)，實(shí)現(xiàn)以下功能：（1）查找特定員工