北京郵電大學(xué)《數(shù)據(jù)科學(xué)基礎(chǔ)》2021-2022學(xué)年第一學(xué)期期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第2頁，共2頁北京郵電大學(xué)《數(shù)據(jù)科學(xué)基礎(chǔ)》

2021-2022學(xué)年第一學(xué)期期末試卷題號(hào)一二三四總分得分一、單選題（本大題共15個(gè)小題，每小題1分，共15分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、使用單片機(jī)設(shè)計(jì)一個(gè)汽車防盜報(bào)警系統(tǒng)，能夠檢測(cè)車輛的異常狀態(tài)并發(fā)出警報(bào)，同時(shí)通過短信通知車主。2、設(shè)計(jì)一個(gè)音頻濾波器數(shù)字控制電路，能夠通過數(shù)字信號(hào)處理器（DSP）對(duì)濾波器的參數(shù)進(jìn)行精確控制，提高音頻質(zhì)量。3、利用數(shù)字電路技術(shù)，設(shè)計(jì)一個(gè)智能公交站牌系統(tǒng)，顯示車輛實(shí)時(shí)位置和預(yù)計(jì)到達(dá)時(shí)間。4、使用單片機(jī)設(shè)計(jì)一個(gè)智能家居安防監(jiān)控系統(tǒng)，能夠?qū)崟r(shí)監(jiān)控家中情況，當(dāng)有異常時(shí)進(jìn)行圖像抓拍和報(bào)警。5、設(shè)計(jì)一個(gè)基于FPGA的UART通信模塊，波特率可設(shè)置，數(shù)據(jù)位、停止位可配置，給出硬件實(shí)現(xiàn)和測(cè)試方案。6、設(shè)計(jì)一個(gè)簡(jiǎn)單的鋰電池充電管理系統(tǒng)，能夠?qū)︿囯姵剡M(jìn)行恒流恒壓充電，充電終止電壓為4.2V，充電電流可調(diào)節(jié)。7、設(shè)計(jì)一個(gè)數(shù)字存儲(chǔ)示波器電路，能夠測(cè)量輸入信號(hào)的波形、頻率、幅度等參數(shù)，并且具有存儲(chǔ)和回放功能。8、設(shè)計(jì)一個(gè)數(shù)字通信中均衡器訓(xùn)練和跟蹤模式的切換策略，分析對(duì)系統(tǒng)性能的影響。9、設(shè)計(jì)一個(gè)基于單片機(jī)的智能小車控制系統(tǒng)，能夠?qū)崿F(xiàn)小車的前進(jìn)、后退、轉(zhuǎn)彎、調(diào)速等功能，并具備避障功能。10、設(shè)計(jì)一個(gè)簡(jiǎn)單的圖像采集系統(tǒng)，使用攝像頭采集圖像數(shù)據(jù)，并通過接口傳輸?shù)接?jì)算機(jī)進(jìn)行處理和顯示，包括硬件接口設(shè)計(jì)和驅(qū)動(dòng)程序編寫。11、利用數(shù)字電路技術(shù)，設(shè)計(jì)一個(gè)銀行自動(dòng)取款機(jī)的控制系統(tǒng)，實(shí)現(xiàn)取款、存款、轉(zhuǎn)賬等功能。12、設(shè)計(jì)一個(gè)基于音頻功率放大器的舞臺(tái)音響系統(tǒng)，輸出功率不小于500W，具備音效調(diào)節(jié)功能。13、設(shè)計(jì)一個(gè)數(shù)字頻率計(jì)，采用計(jì)數(shù)法和測(cè)周期法相結(jié)合，測(cè)量范圍為1Hz至100MHz，給出系統(tǒng)方案和誤差分析。14、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)。對(duì)于哈希表的性能，以下描述哪一項(xiàng)是不正確的？（）A.哈希函數(shù)的設(shè)計(jì)直接影響哈希表的性能，好的哈希函數(shù)可以減少?zèng)_突B.處理哈希沖突的方法有開放尋址法和鏈地址法等C.哈希表的查找、插入和刪除操作的平均時(shí)間復(fù)雜度均為O(1)D.哈希表的性能不受表的裝填因子的影響，裝填因子可以任意取值15、設(shè)計(jì)一個(gè)基于FPGA的交通信號(hào)燈控制系統(tǒng)，能夠根據(jù)不同的時(shí)間段和車流量自動(dòng)調(diào)整信號(hào)燈的時(shí)長(zhǎng)，實(shí)現(xiàn)智能化交通控制。二、簡(jiǎn)答題（本大題共4個(gè)小題，共20分)1、（本題5分）論述跳表在插入和刪除元素時(shí)，如何維護(hù)其結(jié)構(gòu)的平衡性和查找效率。2、（本題5分）詳細(xì)論述在拓?fù)渑判蛩惴ㄖ?，如何判斷一個(gè)有向無環(huán)圖，并給出具體的排序步驟和應(yīng)用場(chǎng)景。3、（本題5分）在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖中，闡述如何使用迪杰斯特拉算法求解單源最短路徑問題，給出算法步驟和時(shí)間復(fù)雜度分析。4、（本題5分）解釋圖的連通性問題的高級(jí)算法，如Tarjan算法、Kosaraju算法等的原理及應(yīng)用場(chǎng)景。三、綜合題（本大題共5個(gè)小題，共25分)1、（本題5分）在一個(gè)在線課程學(xué)習(xí)系統(tǒng)中，學(xué)生需要完成一系列的課程任務(wù)，每個(gè)任務(wù)有不同的要求和截止日期。設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來記錄學(xué)生的任務(wù)完成情況，包括已完成任務(wù)、未完成任務(wù)、任務(wù)提交時(shí)間、得分等，能夠?qū)崟r(shí)跟蹤學(xué)生的學(xué)習(xí)進(jìn)度并及時(shí)提醒學(xué)生即將到期的任務(wù)。2、（本題5分）某醫(yī)院的病歷管理系統(tǒng)需要存儲(chǔ)患者的病歷信息，包含患者編號(hào)、姓名、性別、年齡、病癥、診斷結(jié)果、治療方案等。系統(tǒng)要支持快速檢索特定患者的病歷、按照病癥的嚴(yán)重程度對(duì)病歷進(jìn)行排序、添加新的病歷、刪除舊病歷以及更新病歷內(nèi)容。請(qǐng)選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，并詳細(xì)說明如何實(shí)現(xiàn)這些功能，包括算法思路和代碼實(shí)現(xiàn)，以及性能評(píng)估。3、（本題5分）一個(gè)電影票務(wù)系統(tǒng)需要存儲(chǔ)電影場(chǎng)次信息，如場(chǎng)次編號(hào)、電影名稱、放映時(shí)間、影廳號(hào)、剩余座位數(shù)等。系統(tǒng)要能夠快速查找特定場(chǎng)次、按照剩余座位數(shù)對(duì)場(chǎng)次進(jìn)行排序、新增場(chǎng)次、刪除已結(jié)束場(chǎng)次以及修改場(chǎng)次的剩余座位數(shù)。請(qǐng)選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，并詳細(xì)闡述實(shí)現(xiàn)這些功能的算法和代碼，以及對(duì)系統(tǒng)性能的影響。4、（本題5分）一家超市的庫(kù)存管理系統(tǒng)需要記錄商品的庫(kù)存信息，包括商品編碼、商品名稱、庫(kù)存數(shù)量、進(jìn)貨價(jià)格、銷售價(jià)格等。請(qǐng)?jiān)O(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)庫(kù)存數(shù)據(jù)，實(shí)現(xiàn)商品的快速盤點(diǎn)、庫(kù)存預(yù)警、進(jìn)貨和銷售操作，并統(tǒng)計(jì)商品的利潤(rùn)。5、（本題5分）一個(gè)在線家居設(shè)計(jì)平臺(tái)需要存儲(chǔ)家具模型、用戶設(shè)計(jì)方案和材料清單。設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來方便用戶設(shè)計(jì)和修改方案，并生成報(bào)價(jià)單。四、設(shè)計(jì)題（本大題共4個(gè)小題，共40分)1、（本題10分）設(shè)計(jì)一個(gè)算法，在一個(gè)字符串中找出所有以元音字母開頭和輔音字母結(jié)尾的單詞。2、（本題10分）設(shè)計(jì)一個(gè)程序，在給定的最大堆中插入一個(gè)元素，調(diào)整堆并輸出堆的內(nèi)容。3、（本題10分）設(shè)計(jì)一個(gè)程序，