長(zhǎng)春工業(yè)大學(xué)人文信息學(xué)院《數(shù)據(jù)結(jié)構(gòu)》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è)長(zhǎng)春工業(yè)大學(xué)人文信息學(xué)院《數(shù)據(jù)結(jié)構(gòu)》

2021-2022學(xué)年第一學(xué)期期末試卷題號(hào)一二三四總分得分批閱人一、單選題（本大題共15個(gè)小題，每小題1分，共15分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、設(shè)計(jì)一個(gè)具有電源管理功能的集成電路，能夠?qū)崿F(xiàn)對(duì)不同電源軌的監(jiān)控和控制，給出電路設(shè)計(jì)和功能驗(yàn)證。2、設(shè)計(jì)一個(gè)具有自動(dòng)校準(zhǔn)功能的模擬信號(hào)采集系統(tǒng)，提高采集精度，給出系統(tǒng)的設(shè)計(jì)方案和校準(zhǔn)算法。3、設(shè)計(jì)一個(gè)基于數(shù)字圖像處理的車(chē)牌識(shí)別停車(chē)場(chǎng)管理系統(tǒng)，實(shí)現(xiàn)車(chē)輛的自動(dòng)識(shí)別和出入管理。4、在數(shù)據(jù)結(jié)構(gòu)的選擇中，需要考慮時(shí)間復(fù)雜度、空間復(fù)雜度和操作的便捷性等因素。以下情況中，優(yōu)先選擇數(shù)組而不是鏈表的是（）A.頻繁進(jìn)行插入和刪除操作B.事先不知道數(shù)據(jù)的規(guī)模大小C.需要快速隨機(jī)訪問(wèn)元素D.內(nèi)存空間有限5、設(shè)計(jì)一個(gè)簡(jiǎn)單的數(shù)字音頻解碼器，能夠解碼常見(jiàn)的音頻格式如MP3、WAV等，給出硬件設(shè)計(jì)和解碼算法。6、設(shè)計(jì)一個(gè)基于FPGA的圖像邊緣檢測(cè)系統(tǒng)，能夠?qū)斎氲幕叶葓D像進(jìn)行實(shí)時(shí)邊緣檢測(cè)，采用Sobel算子，給出硬件架構(gòu)和Verilog代碼實(shí)現(xiàn)。7、設(shè)計(jì)一個(gè)基于FPGA的圖像濾波系統(tǒng)，實(shí)現(xiàn)中值濾波、均值濾波等功能，去除圖像噪聲。8、設(shè)計(jì)一個(gè)太陽(yáng)能熱水器控制器電路，能夠根據(jù)水溫自動(dòng)控制加熱和保溫，并且具有水位顯示和缺水報(bào)警功能。9、設(shè)計(jì)一個(gè)基于單片機(jī)的溫度監(jiān)測(cè)與控制系統(tǒng)，能夠?qū)崟r(shí)采集環(huán)境溫度，當(dāng)溫度超過(guò)設(shè)定閾值時(shí)，啟動(dòng)相應(yīng)的降溫或升溫設(shè)備。10、設(shè)計(jì)一個(gè)簡(jiǎn)單的數(shù)字圖像去噪系統(tǒng)，能夠有效去除圖像中的噪聲，給出系統(tǒng)設(shè)計(jì)和去噪效果分析。11、設(shè)計(jì)一個(gè)基于數(shù)字信號(hào)處理的語(yǔ)音合成系統(tǒng)，能夠?qū)⑽谋巨D(zhuǎn)換為自然流暢的語(yǔ)音。12、設(shè)計(jì)一個(gè)模擬集成電路中的反饋放大器，實(shí)現(xiàn)特定的增益和帶寬要求，分析反饋對(duì)穩(wěn)定性的影響。13、設(shè)計(jì)一個(gè)基于FPGA的圖像銳化系統(tǒng)，能夠增強(qiáng)圖像的邊緣和細(xì)節(jié)，說(shuō)明算法和硬件實(shí)現(xiàn)。14、設(shè)計(jì)一個(gè)基于ARM的工業(yè)自動(dòng)化控制系統(tǒng)，實(shí)現(xiàn)對(duì)生產(chǎn)設(shè)備的監(jiān)控和控制，描述系統(tǒng)架構(gòu)和軟件界面。15、設(shè)計(jì)一個(gè)數(shù)字示波器探頭電路，能夠?qū)⑤斎胄盘?hào)轉(zhuǎn)換為適合示波器測(cè)量的信號(hào)，并且具有衰減和補(bǔ)償功能。二、簡(jiǎn)答題（本大題共4個(gè)小題，共20分)1、（本題5分）詳細(xì)說(shuō)明在堆排序中，如何從無(wú)序數(shù)組構(gòu)建初始堆，以及排序過(guò)程中的調(diào)整操作。2、（本題5分）詳細(xì)闡述B樹(shù)中節(jié)點(diǎn)的分裂和合并操作，以及如何保證樹(shù)的平衡性和查找性能。3、（本題5分）對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的有向圖，如何使用拓?fù)渑判蛩惴ㄅ袛嗍欠翊嬖诙鄠€(gè)合法的拓?fù)湫蛄校?、（本題5分）什么是二叉搜索樹(shù)的平衡？為什么要保持二叉搜索樹(shù)的平衡？有哪些平衡二叉樹(shù)的算法？三、綜合題（本大題共5個(gè)小題，共25分)1、（本題5分）某電商平臺(tái)的優(yōu)惠券發(fā)放系統(tǒng)需要對(duì)優(yōu)惠券的類(lèi)型、面額、使用條件和發(fā)放記錄進(jìn)行管理。優(yōu)惠券信息包括優(yōu)惠券編號(hào)、類(lèi)型、面額、使用條件、發(fā)放記錄等?？紤]使用十字鏈表來(lái)存儲(chǔ)這些信息。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)以下功能：（1）查詢(xún)某種類(lèi)型優(yōu)惠券的剩余數(shù)量；（2）為用戶(hù)發(fā)放優(yōu)惠券并記錄；（3）用戶(hù)使用優(yōu)惠券時(shí)進(jìn)行核銷(xiāo)；（4）統(tǒng)計(jì)不同面額優(yōu)惠券的發(fā)放比例。分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。2、（本題5分）某城市的公交路線管理系統(tǒng)需要存儲(chǔ)公交路線的信息，如路線編號(hào)、起點(diǎn)站、終點(diǎn)站、途經(jīng)站點(diǎn)、發(fā)車(chē)時(shí)間等。系統(tǒng)要實(shí)現(xiàn)快速查找特定路線、按照路線長(zhǎng)度對(duì)路線進(jìn)行排序、新增和刪除路線、修改路線的發(fā)車(chē)時(shí)間等功能。請(qǐng)確定合適的數(shù)據(jù)結(jié)構(gòu)，并詳細(xì)描述算法設(shè)計(jì)和代碼實(shí)現(xiàn)，同時(shí)分析其時(shí)間和空間復(fù)雜度。3、（本題5分）一家電商平臺(tái)的客戶(hù)投訴管理系統(tǒng)需要記錄投訴信息、處理進(jìn)度和處理結(jié)果。投訴信息包括投訴ID、訂單ID、投訴內(nèi)容、投訴時(shí)間，處理進(jìn)度包括進(jìn)度ID、投訴ID、處理步驟、處理人員、處理時(shí)間，處理結(jié)果包括結(jié)果ID、投訴ID、處理結(jié)果、滿(mǎn)意度。設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來(lái)管理投訴數(shù)據(jù)，實(shí)現(xiàn)投訴的受理、處理跟蹤、結(jié)果反饋，并統(tǒng)計(jì)投訴的類(lèi)型和處理滿(mǎn)意度。4、（本題5分）某電商平臺(tái)的促銷(xiāo)活動(dòng)管理系統(tǒng)需要記錄活動(dòng)信息和參與用戶(hù)信息，活動(dòng)信息包括活動(dòng)ID、活動(dòng)名稱(chēng)、活動(dòng)規(guī)則、開(kāi)始時(shí)間、結(jié)束時(shí)間，參與用戶(hù)信息包括用戶(hù)ID、活動(dòng)ID、參與時(shí)間。設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)這些數(shù)據(jù)，能夠快速查詢(xún)活動(dòng)詳情、統(tǒng)計(jì)參與人數(shù)、判斷用戶(hù)是否參與活動(dòng)，并在活動(dòng)結(jié)束后進(jìn)行數(shù)據(jù)清理。5、（本題5分）一個(gè)在線投票系統(tǒng)需要對(duì)投票項(xiàng)目和投票人的選擇進(jìn)行管理。投票項(xiàng)目信息包括項(xiàng)目編號(hào)、項(xiàng)目名稱(chēng)、選項(xiàng)等，投票人信息包括投票人編號(hào)、選擇的選項(xiàng)等。這些信息以線段樹(shù)的形式存儲(chǔ)。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)以下功能：（1）統(tǒng)計(jì)某個(gè)投票項(xiàng)目各個(gè)選項(xiàng)的票數(shù)；（2）新增一個(gè)投票項(xiàng)目；（3）修改投票人的選擇；（4）查詢(xún)票數(shù)最多的選項(xiàng)。分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。四、設(shè)計(jì)題（本大題共4個(gè)小題，共40分)1、（本題10分）使用圖數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)一個(gè)工廠倉(cāng)庫(kù)貨物存儲(chǔ)規(guī)劃系統(tǒng)，優(yōu)化貨物存儲(chǔ)位置。2、（本題