麗江文化旅游學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》2021-2022學(xué)年第一學(xué)期期末試卷

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線第1頁(yè)，共3頁(yè)麗江文化旅游學(xué)院

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》2021-2022學(xué)年第一學(xué)期期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三四總分得分批閱人一、單選題（本大題共15個(gè)小題，每小題1分，共15分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)需要對(duì)大量整數(shù)進(jìn)行排序，并且內(nèi)存空間有限的情況下。以下哪種排序算法可能比較適合？（）A.歸并排序B.冒泡排序C.桶排序D.選擇排序2、考慮隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，它遵循先進(jìn)先出的原則。假設(shè)一個(gè)銀行需要管理客戶的排隊(duì)等待服務(wù)，每個(gè)客戶按照到達(dá)的順序接受服務(wù)。為了有效地組織和管理客戶的等待過(guò)程，以下關(guān)于隊(duì)列的操作，哪個(gè)是最關(guān)鍵的（）A.隨機(jī)刪除隊(duì)列中的元素B.在隊(duì)列中間插入新的客戶C.讀取隊(duì)列頭部的客戶信息D.對(duì)隊(duì)列中的元素進(jìn)行排序3、設(shè)計(jì)一個(gè)音頻功率放大器，采用AB類放大方式，在8Ω負(fù)載下輸出功率不小于80W，給出電路設(shè)計(jì)和散熱考慮。4、運(yùn)用數(shù)字電路設(shè)計(jì)一個(gè)密碼鎖系統(tǒng)，用戶通過(guò)輸入正確的密碼才能打開鎖，同時(shí)具有錯(cuò)誤輸入次數(shù)限制和報(bào)警功能。5、設(shè)計(jì)一個(gè)低通數(shù)字濾波器，截止頻率為500Hz，采樣頻率為2kHz，采用窗函數(shù)法進(jìn)行設(shè)計(jì)。6、使用單片機(jī)設(shè)計(jì)一個(gè)智能電子秤系統(tǒng)，能夠準(zhǔn)確測(cè)量物體重量，并具有去皮、計(jì)價(jià)等功能。7、設(shè)計(jì)一個(gè)基于運(yùn)算放大器的儀表放大器電路，具有高共模抑制比和高輸入阻抗，給出電路結(jié)構(gòu)和參數(shù)計(jì)算。8、運(yùn)用電子電路知識(shí)，設(shè)計(jì)一個(gè)具有過(guò)流保護(hù)和短路保護(hù)功能的直流電源電路。9、利用射頻技術(shù)設(shè)計(jì)一個(gè)藍(lán)牙音頻耳機(jī)，實(shí)現(xiàn)高質(zhì)量的無(wú)線音頻傳輸和控制功能。10、鏈表是另一種重要的數(shù)據(jù)結(jié)構(gòu)，與數(shù)組相比具有不同的特點(diǎn)。以下關(guān)于鏈表的描述，不正確的是：（）A.鏈表中的元素通過(guò)指針鏈接在一起，存儲(chǔ)位置可以是不連續(xù)的，插入和刪除操作只需修改指針，效率較高B.單向鏈表只能從表頭向表尾遍歷，而雙向鏈表可以從表頭和表尾雙向遍歷，更加靈活C.鏈表的查找操作需要從頭節(jié)點(diǎn)依次遍歷，效率相對(duì)較低，但在不知道元素位置的情況下仍能進(jìn)行插入和刪除D.鏈表不需要預(yù)先分配連續(xù)的存儲(chǔ)空間，因此不會(huì)出現(xiàn)存儲(chǔ)空間浪費(fèi)的情況，且其內(nèi)存使用效率總是高于數(shù)組11、設(shè)計(jì)一個(gè)基于USBType-C接口的電源傳輸系統(tǒng)，支持PD快充協(xié)議，能夠提供不同的電壓和電流輸出，給出硬件設(shè)計(jì)和協(xié)議實(shí)現(xiàn)。12、設(shè)計(jì)一個(gè)程控濾波器，帶寬和中心頻率可程控調(diào)節(jié)，給出電路實(shí)現(xiàn)和控制邏輯。13、樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，具有層次關(guān)系。以下關(guān)于樹的描述，不正確的是：（）A.二叉樹的每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)B.二叉搜索樹的左子樹中的節(jié)點(diǎn)值小于根節(jié)點(diǎn)值，右子樹中的節(jié)點(diǎn)值大于根節(jié)點(diǎn)值，便于快速查找、插入和刪除C.平衡二叉樹通過(guò)自動(dòng)調(diào)整保持樹的平衡，提高了查找效率，但插入和刪除操作相對(duì)復(fù)雜D.樹的遍歷方式包括前序遍歷、中序遍歷和后序遍歷，且每種遍歷方式的時(shí)間復(fù)雜度都是相同的，與樹的結(jié)構(gòu)無(wú)關(guān)14、棧是一種特殊的線性結(jié)構(gòu)，遵循后進(jìn)先出的原則。假設(shè)一個(gè)程序中使用了棧來(lái)存儲(chǔ)數(shù)據(jù)。以下關(guān)于棧的描述，哪一項(xiàng)是不準(zhǔn)確的？（）A.?？梢杂糜趯?shí)現(xiàn)函數(shù)調(diào)用時(shí)的參數(shù)傳遞和局部變量存儲(chǔ)B.入棧和出棧操作的時(shí)間復(fù)雜度均為O(1)C.可以使用數(shù)組或鏈表來(lái)實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)D.棧的存儲(chǔ)空間大小是固定的，無(wú)法動(dòng)態(tài)擴(kuò)展15、設(shè)計(jì)一個(gè)具有相位補(bǔ)償功能的放大器電路，提高電路的穩(wěn)定性和帶寬，給出電路設(shè)計(jì)和相位補(bǔ)償分析。二、簡(jiǎn)答題（本大題共4個(gè)小題，共20分)1、（本題5分）數(shù)組和鏈表在存儲(chǔ)數(shù)據(jù)方面有哪些不同之處？各自的優(yōu)缺點(diǎn)是什么？2、（本題5分）詳細(xì)解釋在一個(gè)具有n個(gè)元素的二叉樹中，如何進(jìn)行后序遍歷的非遞歸實(shí)現(xiàn)。3、（本題5分）詳細(xì)闡述圖的拓?fù)渑判虻母拍詈蛻?yīng)用場(chǎng)景，給出拓?fù)渑判虻乃惴ú襟E，并分析其時(shí)間復(fù)雜度。4、（本題5分）詳細(xì)闡述在拓?fù)渑判虻幕A(chǔ)上，如何進(jìn)一步判斷圖是否為有向無(wú)環(huán)圖。三、綜合題（本大題共5個(gè)小題，共25分)1、（本題5分）一個(gè)學(xué)校的實(shí)驗(yàn)室設(shè)備管理系統(tǒng)需要存儲(chǔ)設(shè)備的信息，如設(shè)備編號(hào)、設(shè)備名稱、設(shè)備類型、購(gòu)買日期、使用狀態(tài)等。系統(tǒng)要支持快速查找特定設(shè)備、按照購(gòu)買日期對(duì)設(shè)備進(jìn)行排序、新增設(shè)備、維修設(shè)備、報(bào)廢設(shè)備。請(qǐng)確定恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，并詳細(xì)闡述算法和代碼實(shí)現(xiàn)，以及性能優(yōu)化策略。2、（本題5分）某城市的公交系統(tǒng)需要對(duì)公交線路和站點(diǎn)進(jìn)行管理。線路和站點(diǎn)信息以有向無(wú)環(huán)圖的形式存儲(chǔ)。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)以下功能：（1）查找從起點(diǎn)到終點(diǎn)經(jīng)過(guò)最少站點(diǎn)的公交線路；（2）判斷兩條公交線路是否存在交叉站點(diǎn)；（3）新增一條公交線路時(shí)，如何更新整個(gè)公交網(wǎng)絡(luò)；（4）計(jì)算每個(gè)站點(diǎn)的客流量。分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題5分）某醫(yī)院的體檢管理系統(tǒng)需要記錄體檢項(xiàng)目、體檢人員信息、體檢結(jié)果和建議等。設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)這些信息，實(shí)現(xiàn)體檢項(xiàng)目的設(shè)置，體檢人員信息的錄入，體檢結(jié)果的存儲(chǔ)和分析，以及個(gè)性化的體檢建議生成，并能夠快速查詢和統(tǒng)計(jì)體檢數(shù)據(jù)。4、（本題5分）某在線考試的監(jiān)考系統(tǒng)需要實(shí)時(shí)監(jiān)控考生的答題狀態(tài)、行為異常和交卷時(shí)間。設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)和算法，保障考試的公平公正和順利進(jìn)行。5、（本題5分）某外賣配送平臺(tái)需要根據(jù)騎手的位置和訂單信息進(jìn)行任務(wù)分配，確保高效配送。設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)和算法，實(shí)現(xiàn)訂單的合理分配和配送路徑規(guī)劃。四、設(shè)計(jì)題（本大題共4個(gè)小題，共40分)1、（本題10分）設(shè)計(jì)一個(gè)算法，對(duì)一個(gè)二叉排序樹進(jìn)行中序遍歷的非遞歸實(shí)現(xiàn)。2、（本題10分）設(shè)計(jì)一