華東師范大學(xué)《數(shù)據(jù)科學(xué)與工程基礎(chǔ)》2021-2022學(xué)年第一學(xué)期期末試卷

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績(jī)按零分記。…………密………………封………………線…………第1頁，共1頁華東師范大學(xué)《數(shù)據(jù)科學(xué)與工程基礎(chǔ)》

2021-2022學(xué)年第一學(xué)期期末試卷題號(hào)一二三四總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、字符串的操作和處理在計(jì)算機(jī)編程中經(jīng)常遇到。對(duì)于字符串的匹配算法，以下描述哪一項(xiàng)是不正確的？（）A.樸素的字符串匹配算法通過逐個(gè)字符比較來查找模式串在主串中的位置，時(shí)間復(fù)雜度較高B.KMP（Knuth-Morris-Pratt）算法通過利用已經(jīng)匹配的部分信息來提高匹配效率C.BM（Boyer-Moore）算法從右向左比較字符，在某些情況下性能優(yōu)于KMP算法D.所有的字符串匹配算法在最壞情況下的時(shí)間復(fù)雜度都是O(m*n)，其中m是模式串長(zhǎng)度，n是主串長(zhǎng)度2、在數(shù)據(jù)結(jié)構(gòu)中，散列表（哈希表）用于快速查找數(shù)據(jù)。以下關(guān)于散列表的描述，錯(cuò)誤的是（）A.散列函數(shù)的設(shè)計(jì)對(duì)散列表的性能有很大影響B(tài).處理沖突的方法有開放地址法和鏈地址法C.散列表的查找時(shí)間復(fù)雜度始終為O(1)D.散列表的裝填因子會(huì)影響其性能3、設(shè)計(jì)一個(gè)圖像處理中基于區(qū)域的圖像分割效果評(píng)估系統(tǒng)，包括準(zhǔn)確性和邊界完整性等指標(biāo)。4、在數(shù)據(jù)結(jié)構(gòu)的實(shí)際應(yīng)用中，優(yōu)先隊(duì)列常用于處理具有優(yōu)先級(jí)的任務(wù)。以下關(guān)于優(yōu)先隊(duì)列的實(shí)現(xiàn)方式，錯(cuò)誤的是：（）A.可以用堆來實(shí)現(xiàn)優(yōu)先隊(duì)列，插入和刪除操作的時(shí)間復(fù)雜度都較低B.可以用有序數(shù)組來實(shí)現(xiàn)優(yōu)先隊(duì)列，但插入操作的時(shí)間復(fù)雜度較高C.可以用無序數(shù)組來實(shí)現(xiàn)優(yōu)先隊(duì)列，查找最大（或最?。┰氐臅r(shí)間復(fù)雜度為O(1)D.無論采用哪種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)優(yōu)先隊(duì)列，其性能都相同5、設(shè)計(jì)一個(gè)簡(jiǎn)單的電力線通信系統(tǒng)，能夠在電力線上實(shí)現(xiàn)數(shù)據(jù)傳輸，包括調(diào)制解調(diào)電路和通信協(xié)議。6、設(shè)計(jì)一個(gè)簡(jiǎn)單的光電編碼器接口電路，能夠準(zhǔn)確讀取編碼器的輸出信號(hào)，用于位置測(cè)量，闡述電路原理和接口程序。7、設(shè)計(jì)一個(gè)基于藍(lán)牙低功耗和Wi-Fi的雙模通信模塊，實(shí)現(xiàn)靈活的通信方式選擇，描述模塊的硬件組成和通信協(xié)議。8、設(shè)計(jì)一個(gè)基于CPLD的數(shù)字信號(hào)發(fā)生器，能夠產(chǎn)生多種復(fù)雜的數(shù)字信號(hào)，包括信號(hào)類型選擇和參數(shù)設(shè)置。9、設(shè)計(jì)一個(gè)數(shù)字頻率計(jì)自動(dòng)測(cè)量電路，能夠自動(dòng)測(cè)量輸入信號(hào)的頻率，并將測(cè)量結(jié)果顯示出來。10、在圖的遍歷算法中，深度優(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適合用于判斷圖是否連通11、利用模擬電路技術(shù)，設(shè)計(jì)一個(gè)用于音頻功率放大器的保護(hù)電路，防止過載和短路損壞設(shè)備。12、跳表是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)。關(guān)于跳表的特點(diǎn)，以下描述哪一項(xiàng)是不正確的？（）A.跳表通過在鏈表中增加多層索引來提高查找效率B.插入和刪除操作在平均情況下的時(shí)間復(fù)雜度為O(logn)C.跳表的空間復(fù)雜度比普通鏈表高，但低于平衡二叉搜索樹D.跳表的性能不受數(shù)據(jù)分布的影響，始終保持較好的查找效率13、歸并排序同樣是一種分治算法，它將數(shù)組不斷地分成兩半，然后將兩半合并成一個(gè)有序的數(shù)組。歸并排序的空間復(fù)雜度主要取決于：（）A.數(shù)組的初始大小B.遞歸的深度C.合并操作的次數(shù)D.數(shù)據(jù)的分布情況14、在一個(gè)大型企業(yè)的員工管理系統(tǒng)中，需要存儲(chǔ)員工的基本信息，如姓名、工號(hào)、部門、職位等，并且能夠按照部門快速查找和統(tǒng)計(jì)員工數(shù)量。為了實(shí)現(xiàn)這樣的功能，以下哪種數(shù)據(jù)結(jié)構(gòu)是比較合適的選擇？（）A.字典樹B.堆C.跳表D.并查集15、使用數(shù)字信號(hào)處理技術(shù)設(shè)計(jì)一個(gè)音頻濾波器，能夠?qū)斎氲囊纛l信號(hào)進(jìn)行特定頻率范圍的濾波，如低通、高通或帶通濾波。16、設(shè)計(jì)一個(gè)數(shù)字頻率合成器電路，能夠產(chǎn)生不同頻率的正弦波、方波和三角波，頻率范圍為1Hz到10MHz。17、在數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)中，實(shí)踐是非常重要的。以下關(guān)于數(shù)據(jù)結(jié)構(gòu)實(shí)踐的描述，錯(cuò)誤的是：（）A.通過實(shí)際編程實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)可以加深對(duì)其理解B.可以通過解決實(shí)際問題來應(yīng)用所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識(shí)C.實(shí)踐只需要在電腦上完成，不需要在現(xiàn)實(shí)場(chǎng)景中思考D.實(shí)踐過程中可以發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)和不足18、在數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)中，理解和掌握基本概念是非常重要的，以下關(guān)于數(shù)據(jù)結(jié)構(gòu)概念的描述，正確的是：（）A.數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合B.數(shù)據(jù)結(jié)構(gòu)只關(guān)注數(shù)據(jù)的存儲(chǔ)方式，不關(guān)心數(shù)據(jù)的操作和處理C.不同的數(shù)據(jù)結(jié)構(gòu)適用于不同的應(yīng)用場(chǎng)景，沒有一種數(shù)據(jù)結(jié)構(gòu)是萬能的D.數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和選擇對(duì)程序的性能和效率沒有影響19、設(shè)計(jì)一個(gè)基于鎖相環(huán)的頻率合成器電路，輸出頻率范圍為100kHz-1GHz，頻率分辨率不大于1kHz，相位噪聲小于-100dBc/Hz@1kHz偏移。20、在字符串匹配算法中，KMP算法是一種高效的算法，以下關(guān)于KMP算法的描述，不正確的是：（）A.KMP算法通過利用已經(jīng)匹配的部分信息，避免了不必要的回溯，提高了匹配效率B.KMP算法的時(shí)間復(fù)雜度主要取決于模式串的長(zhǎng)度，與主串的長(zhǎng)度無關(guān)C.KMP算法的核心是計(jì)算模式串的next數(shù)組，用于確定匹配失敗時(shí)的移動(dòng)位置D.KMP算法在任何情況下的性能都優(yōu)于樸素的字符串匹配算法二、簡(jiǎn)答題（本大題共3個(gè)小題，共15分)1、（本題5分）比較快速排序和冒泡排序在最好情況下的性能表現(xiàn)。2、（本題5分）闡述如何在一個(gè)有序鏈表中查找中位數(shù)，分析所使用的算法和時(shí)間復(fù)雜度。3、（本題5分）詳細(xì)闡述在一個(gè)具有n個(gè)元素的二叉樹中，如何計(jì)算樹的高度，并分析其時(shí)間復(fù)雜度。三、設(shè)計(jì)題（本大題共5個(gè)小題，共25分)1、（本題5分）設(shè)計(jì)一個(gè)程序，使用圖的數(shù)據(jù)結(jié)構(gòu)表示城市交通網(wǎng)絡(luò)中的智能導(dǎo)航系統(tǒng)，實(shí)現(xiàn)最短路徑和實(shí)時(shí)路況的結(jié)合功能。2、（本題5分）設(shè)計(jì)一個(gè)程序，利用伸展樹結(jié)構(gòu)存儲(chǔ)用戶的消費(fèi)記錄，實(shí)現(xiàn)快速插入、查找和刪除操作。3、（本題5分）利用隊(duì)列結(jié)構(gòu)設(shè)計(jì)一個(gè)學(xué)校運(yùn)動(dòng)會(huì)比賽項(xiàng)目報(bào)名管理系統(tǒng)，模擬報(bào)名的排隊(duì)和處理過程。4、（本題5分）實(shí)現(xiàn)一個(gè)算法，計(jì)算一個(gè)圖的著色方案數(shù)。5、（本題5分）分析在字符串匹配中利用后綴自動(dòng)機(jī)提高匹配效率的設(shè)計(jì)和實(shí)現(xiàn)。四、綜合題（本大題共2個(gè)小題，共20分)1、（本題10分）某電商平臺(tái)的推薦系統(tǒng)需要根據(jù)用戶的購買歷史、瀏覽記錄和收藏夾等信息為用戶推薦商品。設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)用戶