武漢商學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)》2021-2022學(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)與算法課程設(shè)計(jì)》

2021-2022學(xué)年第一學(xué)期期末試卷題號(hào)一二三四總分得分一、單選題（本大題共20個(gè)小題，每小題1分，共20分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、設(shè)計(jì)一個(gè)電磁波發(fā)射與接收系統(tǒng)，工作頻率在特定頻段，能夠?qū)崿F(xiàn)一定距離內(nèi)的有效通信，并分析其傳播特性。2、假設(shè)在一個(gè)操作系統(tǒng)的內(nèi)存管理中，需要?jiǎng)討B(tài)地分配和回收內(nèi)存塊，并且避免內(nèi)存碎片的產(chǎn)生。以下哪種數(shù)據(jù)結(jié)構(gòu)和算法可以用于實(shí)現(xiàn)有效的內(nèi)存管理？（）A.伙伴系統(tǒng)B.分頁(yè)存儲(chǔ)管理C.分段存儲(chǔ)管理D.段頁(yè)式存儲(chǔ)管理3、二叉搜索樹(shù)是一種特殊的二叉樹(shù)，在查找和操作上具有一定的優(yōu)勢(shì)。對(duì)于二叉搜索樹(shù)的特點(diǎn)，以下描述哪一項(xiàng)是不正確的？（）A.左子樹(shù)上所有節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，右子樹(shù)上所有節(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值B.中序遍歷二叉搜索樹(shù)可以得到一個(gè)有序的序列C.插入、刪除和查找操作在平均情況下的時(shí)間復(fù)雜度均為O(logn)，其中n是節(jié)點(diǎn)數(shù)量D.二叉搜索樹(shù)一定是平衡的，即左右子樹(shù)的高度差不超過(guò)14、當(dāng)處理一個(gè)動(dòng)態(tài)增長(zhǎng)和收縮的數(shù)據(jù)集合時(shí)，例如一個(gè)不斷有元素插入和刪除的集合，以下哪種數(shù)據(jù)結(jié)構(gòu)在空間利用和操作效率上可能表現(xiàn)更優(yōu)（）A.數(shù)組B.鏈表C.哈希表D.二叉搜索樹(shù)5、設(shè)計(jì)一個(gè)簡(jiǎn)單的無(wú)線充電器，能夠?yàn)槭謾C(jī)等設(shè)備進(jìn)行無(wú)線充電，給出充電器的電路原理和設(shè)計(jì)參數(shù)。6、運(yùn)用通信網(wǎng)絡(luò)技術(shù)，設(shè)計(jì)一個(gè)智能工廠的5G專網(wǎng)方案，滿足工業(yè)生產(chǎn)中對(duì)低延遲、高可靠通信的需求。7、在數(shù)據(jù)結(jié)構(gòu)的實(shí)際應(yīng)用中，可能需要對(duì)不同的數(shù)據(jù)結(jié)構(gòu)進(jìn)行組合和改進(jìn)。以下關(guān)于數(shù)據(jù)結(jié)構(gòu)組合和改進(jìn)的描述，不正確的是：（）A.可以將哈希表和鏈表結(jié)合起來(lái)，解決哈希沖突時(shí)采用鏈表存儲(chǔ)沖突元素，提高空間利用率B.可以在二叉搜索樹(shù)的基礎(chǔ)上增加平衡機(jī)制，如AVL樹(shù)或紅黑樹(shù)，提高查找和插入的效率C.對(duì)圖進(jìn)行優(yōu)化時(shí)，可以使用鄰接多重表來(lái)代替鄰接表，以減少存儲(chǔ)空間和提高操作效率D.數(shù)據(jù)結(jié)構(gòu)的組合和改進(jìn)是沒(méi)有限制的，可以隨意創(chuàng)造新的數(shù)據(jù)結(jié)構(gòu)，而不需要考慮其合理性和實(shí)用性8、設(shè)計(jì)一個(gè)簡(jiǎn)單的無(wú)線數(shù)據(jù)傳輸系統(tǒng)，采用Zigbee技術(shù)，實(shí)現(xiàn)多個(gè)節(jié)點(diǎn)之間的通信，描述系統(tǒng)的硬件組成和軟件流程。9、設(shè)計(jì)一個(gè)基于數(shù)字電位器的音量調(diào)節(jié)系統(tǒng)，能夠?qū)崿F(xiàn)對(duì)音頻信號(hào)音量的連續(xù)調(diào)節(jié)，且調(diào)節(jié)范圍可設(shè)定。10、設(shè)計(jì)一個(gè)基于數(shù)字電路的交通信號(hào)燈控制系統(tǒng)，要求能夠?qū)崿F(xiàn)紅、綠、黃三種燈的交替閃爍，并且可以根據(jù)不同時(shí)間段調(diào)整信號(hào)燈的工作模式。11、設(shè)計(jì)一個(gè)基于STM32微控制器的電機(jī)調(diào)速系統(tǒng)，支持PWM調(diào)速和閉環(huán)控制，實(shí)現(xiàn)對(duì)直流電機(jī)或步進(jìn)電機(jī)的精確調(diào)速，提供控制算法和程序框架。12、設(shè)計(jì)一個(gè)基于USB3.1接口的高速數(shù)據(jù)傳輸系統(tǒng)，能夠?qū)崿F(xiàn)大數(shù)據(jù)量的快速傳輸，包括接口電路設(shè)計(jì)和傳輸協(xié)議。13、在一個(gè)大規(guī)模的社交網(wǎng)絡(luò)分析中，需要快速找出兩個(gè)用戶之間的最短路徑以及共同的好友。為了有效地解決這類問(wèn)題，以下哪種數(shù)據(jù)結(jié)構(gòu)是常用的選擇？（）A.迪杰斯特拉算法使用的優(yōu)先隊(duì)列B.弗洛伊德算法使用的矩陣C.廣度優(yōu)先搜索使用的隊(duì)列D.深度優(yōu)先搜索使用的棧14、根據(jù)傳感器原理，設(shè)計(jì)一個(gè)用于智能家居的人體紅外感應(yīng)系統(tǒng)，能夠?qū)崿F(xiàn)自動(dòng)開(kāi)燈、關(guān)空調(diào)等智能控制。15、設(shè)計(jì)一個(gè)低通濾波器電路，截止頻率為1kHz，通帶波紋小于1dB，阻帶衰減大于40dB，采用無(wú)源或有源濾波器實(shí)現(xiàn)，并比較兩者的優(yōu)缺點(diǎn)。16、設(shè)計(jì)一個(gè)簡(jiǎn)單的觸摸顯示屏控制系統(tǒng)，能夠?qū)崿F(xiàn)觸摸操作的響應(yīng)和顯示內(nèi)容的更新，闡述硬件電路和軟件驅(qū)動(dòng)的實(shí)現(xiàn)方法。17、設(shè)計(jì)一個(gè)基于STM32的智能手環(huán)，能夠監(jiān)測(cè)心率、血壓、運(yùn)動(dòng)步數(shù)等健康數(shù)據(jù)，并通過(guò)藍(lán)牙與手機(jī)進(jìn)行數(shù)據(jù)同步。18、設(shè)計(jì)一個(gè)數(shù)字通信中的多址接入方案，如CDMA，實(shí)現(xiàn)多個(gè)用戶的同時(shí)通信，分析系統(tǒng)容量和干擾情況。19、設(shè)計(jì)一個(gè)基于模擬乘法器的調(diào)幅（AM）信號(hào)發(fā)生器，能夠產(chǎn)生幅度調(diào)制的正弦波信號(hào)，并分析其調(diào)制深度和失真度。20、設(shè)計(jì)一個(gè)程控放大器，增益可在1至100倍之間程控調(diào)節(jié)，精度為1%，給出電路設(shè)計(jì)和控制邏輯。二、簡(jiǎn)答題（本大題共5個(gè)小題，共25分)1、（本題5分）闡述并查集中如何處理大規(guī)模數(shù)據(jù)的合并和查詢操作。2、（本題5分）比較堆排序和選擇排序在穩(wěn)定性方面的差異。3、（本題5分）說(shuō)明二叉樹(shù)的遍歷算法在二叉樹(shù)的節(jié)點(diǎn)刪除問(wèn)題變種、樹(shù)的結(jié)構(gòu)修改問(wèn)題中的應(yīng)用。4、（本題5分）在一個(gè)具有n個(gè)元素的鏈表中，如何實(shí)現(xiàn)鏈表的反轉(zhuǎn)操作，給出算法步驟和時(shí)間復(fù)雜度分析。5、（本題5分）解釋如何在一個(gè)有序數(shù)組中進(jìn)行二分查找的同時(shí)統(tǒng)計(jì)目標(biāo)值出現(xiàn)的次數(shù)。三、設(shè)計(jì)題（本大題共5個(gè)小題，共25分)1、（本題5分）設(shè)計(jì)后綴樹(shù)在生物信息學(xué)中的具體應(yīng)用算法，分析其性能。2、（本題5分）設(shè)計(jì)一個(gè)程序，使用堆結(jié)構(gòu)實(shí)現(xiàn)對(duì)一組任務(wù)按照資源需求進(jìn)行優(yōu)先級(jí)排序。3、（本題5分）設(shè)計(jì)一個(gè)程序，使用鏈表實(shí)現(xiàn)對(duì)一組數(shù)據(jù)的插入、刪除和遍歷操作，用戶可以動(dòng)態(tài)地進(jìn)行數(shù)據(jù)管理。4、（本題5分）構(gòu)建一個(gè)算法，在一個(gè)鏈表中找出所有節(jié)點(diǎn)值的乘積為正數(shù)的連續(xù)子鏈表。5、（本題5分）基于Trie樹(shù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)程序，用于快速驗(yàn)證手機(jī)號(hào)碼的合法性。四、綜合題（本大題共3個(gè)小題，共30分)1、（本題10分）一個(gè)在線訂餐系統(tǒng)需要處理餐廳的菜單信息、用戶訂單、配送地址和支付狀態(tài)。設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)和算法，實(shí)現(xiàn)訂單的快速處理和配送優(yōu)化。2、（本題10分）某高校的課程管理系統(tǒng)需要對(duì)課程的選課信息進(jìn)行處理。選課信息包括課程編號(hào)、課程名稱、授課教師、選課學(xué)生名單等。這些信息以隊(duì)列和棧的組合形式存儲(chǔ)。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)以下功能：（1）按照選課先后順序輸出選課學(xué)生名單；（2）撤銷某個(gè)學(xué)生的選課；（3）統(tǒng)計(jì)每門(mén)課程的選課人數(shù)；（4）調(diào)整選課順序，將優(yōu)先選