玉林師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)》2021-2022學(xué)年第一學(xué)期期末試卷

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績按零分記。…………密………………封………………線…………第1頁，共1頁玉林師范學(xué)院

《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)》2021-2022學(xué)年第一學(xué)期期末試卷題號(hào)一二三四總分得分批閱人一、單選題（本大題共15個(gè)小題，每小題2分，共30分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、設(shè)計(jì)一個(gè)基于數(shù)字信號(hào)處理的語音增強(qiáng)系統(tǒng)，能夠在噪聲環(huán)境下提高語音的清晰度和可懂度。2、在一個(gè)圖的表示和處理中，如果圖的邊數(shù)相對(duì)較少，并且需要快速判斷兩個(gè)頂點(diǎn)之間是否存在邊，以下哪種圖的存儲(chǔ)結(jié)構(gòu)可能是最優(yōu)的？（）A.鄰接矩陣，直觀表示頂點(diǎn)之間的關(guān)系B.鄰接表，節(jié)省存儲(chǔ)空間C.十字鏈表，方便進(jìn)行頂點(diǎn)和邊的操作D.邊集數(shù)組，集中存儲(chǔ)邊的信息3、設(shè)計(jì)一個(gè)基于藍(lán)牙Mesh網(wǎng)絡(luò)的智能家居控制系統(tǒng)，實(shí)現(xiàn)多個(gè)設(shè)備的協(xié)同控制，描述網(wǎng)絡(luò)架構(gòu)和控制策略。4、選擇排序是另一種常見的排序算法。以下關(guān)于選擇排序的說法中，不正確的是（）A.選擇排序每次從待排序序列中選擇最小（或最大）的元素放到已排序序列的末尾B.選擇排序在最壞情況下的時(shí)間復(fù)雜度為O(n^2)C.選擇排序的空間復(fù)雜度為O(1)D.選擇排序是一種穩(wěn)定的排序算法5、設(shè)計(jì)一個(gè)自動(dòng)控制系統(tǒng)中的速度控制器，用于控制電機(jī)的轉(zhuǎn)速，滿足特定的動(dòng)態(tài)和穩(wěn)態(tài)性能指標(biāo)。6、根據(jù)數(shù)字信號(hào)處理理論，設(shè)計(jì)一個(gè)音頻頻譜分析儀，能夠顯示音頻信號(hào)的頻譜分布。7、設(shè)計(jì)一個(gè)音頻DAC轉(zhuǎn)換器電路，實(shí)現(xiàn)高保真音頻輸出，給出電路結(jié)構(gòu)和性能指標(biāo)。8、設(shè)計(jì)一個(gè)基于運(yùn)算放大器的求和放大器電路，能夠?qū)崿F(xiàn)多個(gè)輸入信號(hào)的加權(quán)求和。9、設(shè)計(jì)一個(gè)基于單片機(jī)的智能車位引導(dǎo)系統(tǒng)，能夠?qū)崟r(shí)顯示停車場內(nèi)的車位占用情況，并引導(dǎo)車輛快速找到空閑車位。10、在一個(gè)有n個(gè)頂點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉（Dijkstra）算法求從源點(diǎn)到其他各頂點(diǎn)的最短路徑，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)11、在圖的應(yīng)用中，最小生成樹是一個(gè)重要的概念。關(guān)于最小生成樹的算法，以下說法錯(cuò)誤的是（）A.Prim算法和Kruskal算法都可以用于求解最小生成樹B.Prim算法從一個(gè)頂點(diǎn)開始，逐步擴(kuò)展生成樹C.Kruskal算法按照邊的權(quán)值從小到大選擇邊來構(gòu)建生成樹D.最小生成樹是唯一的，無論使用哪種算法得到的結(jié)果都相同12、設(shè)計(jì)一個(gè)基于ADC和微控制器的風(fēng)速測量系統(tǒng)，能夠測量0-30m/s的風(fēng)速，精度達(dá)到0.1m/s。13、歸并排序是一種基于分治思想的排序算法。對(duì)于歸并排序的過程和特點(diǎn)，以下描述哪一項(xiàng)是不正確的？（）A.歸并排序?qū)?shù)組不斷地分成兩半，分別進(jìn)行排序，然后將排序好的兩部分合并起來B.歸并排序在任何情況下的時(shí)間復(fù)雜度均為O(nlogn)，空間復(fù)雜度為O(n)C.歸并排序是一種穩(wěn)定的排序算法，能夠保持相同元素的相對(duì)順序D.歸并排序在處理大規(guī)模數(shù)據(jù)時(shí)，性能不如快速排序和冒泡排序14、設(shè)計(jì)一個(gè)基于霍爾傳感器的電機(jī)轉(zhuǎn)速測量系統(tǒng)，能夠?qū)崟r(shí)測量電機(jī)的轉(zhuǎn)速并將數(shù)據(jù)顯示出來。15、在一個(gè)有向圖中，頂點(diǎn)表示城市，邊表示城市之間的道路，邊的權(quán)重表示道路的長度。如果要使用迪杰斯特拉算法找到從源頂點(diǎn)到其他所有頂點(diǎn)的最短路徑，以下哪個(gè)步驟是算法的核心？（）A.每次選擇距離源頂點(diǎn)最近的未訪問頂點(diǎn)B.從源頂點(diǎn)開始依次訪問所有頂點(diǎn)C.不斷更新頂點(diǎn)的距離值D.隨機(jī)選擇一個(gè)頂點(diǎn)作為起始點(diǎn)二、簡答題（本大題共3個(gè)小題，共15分)1、（本題5分）對(duì)于一個(gè)用哈希表存儲(chǔ)的整數(shù)對(duì)集合，解釋如何設(shè)計(jì)哈希函數(shù)和處理沖突，給出具體的示例和代碼。2、（本題5分）闡述如何在一個(gè)循環(huán)隊(duì)列中實(shí)現(xiàn)元素的入隊(duì)和出隊(duì)操作，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題5分）比較冒泡排序和快速排序在對(duì)小規(guī)模數(shù)據(jù)的處理速度。三、綜合題（本大題共5個(gè)小題，共25分)1、（本題5分）某公司的項(xiàng)目進(jìn)度跟蹤系統(tǒng)需要記錄項(xiàng)目的各個(gè)階段、負(fù)責(zé)人、開始時(shí)間、預(yù)計(jì)結(jié)束時(shí)間、實(shí)際進(jìn)度等信息。設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來直觀展示項(xiàng)目進(jìn)度，支持項(xiàng)目階段的調(diào)整、負(fù)責(zé)人變更等操作，能夠及時(shí)發(fā)現(xiàn)項(xiàng)目延期風(fēng)險(xiǎn)并進(jìn)行預(yù)警。2、（本題5分）一個(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ù)雜度。3、（本題5分）一個(gè)在線購物車系統(tǒng)需要對(duì)用戶添加的商品進(jìn)行管理。商品信息包括商品ID、名稱、價(jià)格、數(shù)量等。購物車以棧和隊(duì)列的組合形式實(shí)現(xiàn)。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)以下功能：（1）添加商品到購物車；（2）從購物車中刪除指定商品；（3）按照價(jià)格從高到低輸出購物車中的商品；（4）計(jì)算購物車中商品的總價(jià)。分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。4、（本題5分）一個(gè)在線點(diǎn)餐外賣系統(tǒng)需要管理餐廳信息、菜品信息、用戶訂單、配送信息等。設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)餐廳和菜品的添加、刪除、修改，用戶訂單的處理和配送狀態(tài)的跟蹤，能夠優(yōu)化配送路線和提高訂單處理效率。5、（本題5分）某醫(yī)院的藥品庫存管理系統(tǒng)需要對(duì)藥品的種類、數(shù)量和有效期進(jìn)行管理。藥品信息包括藥品編號(hào)、名稱、數(shù)量、有效期等。這些信息以哈希桶的形式存儲(chǔ)。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)以下功能：（1）查詢某種藥品的庫存數(shù)量和有效期；（2）藥品入庫時(shí)添加信息；（3）藥品過期時(shí)刪除信息；（4）統(tǒng)計(jì)即將過期的藥品數(shù)量。分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。四、設(shè)計(jì)題（本大題共3個(gè)小題，共30分)1、（本題10