北京郵電大學(xué)《算法與數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線(xiàn)…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)北京郵電大學(xué)

《算法與數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、分治法的設(shè)計(jì)步驟不包括以下哪個(gè)？A.分解問(wèn)題B.解決子問(wèn)題C.合并子問(wèn)題的解D.隨機(jī)選擇子問(wèn)題2、在貪心算法中，每一步的選擇都是（）A.全局最優(yōu)B.局部最優(yōu)C.隨機(jī)的D.以上都不是3、空間復(fù)雜度主要考慮（）A.算法執(zhí)行過(guò)程中占用的內(nèi)存空間B.算法執(zhí)行過(guò)程中占用的硬盤(pán)空間C.算法執(zhí)行過(guò)程中占用的網(wǎng)絡(luò)帶寬D.以上都是4、以下哪種算法常用于解決凸包問(wèn)題？（）A.Graham掃描法B.Dijkstra算法C.Prim算法D.Kruskal算法5、以下哪個(gè)算法可以用于求解圖的最小生成樹(shù)問(wèn)題？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克魯斯卡爾算法6、以下哪個(gè)不是算法的評(píng)價(jià)指標(biāo)？（）A.正確性B.可讀性C.可擴(kuò)展性D.代碼長(zhǎng)度7、以下哪個(gè)不是貪心算法的基本要素？A.貪心選擇性質(zhì)B.最優(yōu)子結(jié)構(gòu)性質(zhì)C.重疊子問(wèn)題性質(zhì)D.無(wú)后效性8、快速排序的空間復(fù)雜度主要取決于？A.遞歸調(diào)用的深度B.數(shù)據(jù)的規(guī)模C.樞軸元素的選擇D.排序的穩(wěn)定性9、以下哪個(gè)算法可以用于判斷一個(gè)圖是否為連通圖？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.普里姆算法10、在貪心算法中，得到的解可能是（）A.最優(yōu)解B.近似最優(yōu)解C.可行解D.以上都可能11、以下關(guān)于算法復(fù)雜度的說(shuō)法中，錯(cuò)誤的是？A.時(shí)間復(fù)雜度是指算法執(zhí)行所需的時(shí)間B.空間復(fù)雜度是指算法執(zhí)行所需的存儲(chǔ)空間C.算法的時(shí)間復(fù)雜度和空間復(fù)雜度可以相互獨(dú)立D.算法的時(shí)間復(fù)雜度總是小于空間復(fù)雜度12、在有向圖中，進(jìn)行深度優(yōu)先搜索時(shí)，需要使用什么數(shù)據(jù)結(jié)構(gòu)來(lái)記錄已訪(fǎng)問(wèn)的頂點(diǎn)？A.數(shù)組B.鏈表C.棧D.隊(duì)列13、以下哪個(gè)不是動(dòng)態(tài)規(guī)劃算法的應(yīng)用場(chǎng)景？A.資源分配問(wèn)題B.背包問(wèn)題C.圖的遍歷問(wèn)題D.矩陣鏈乘法問(wèn)題14、以下哪個(gè)不是圖的基本操作？A.插入頂點(diǎn)B.刪除頂點(diǎn)C.查找頂點(diǎn)D.排序頂點(diǎn)15、以下哪種排序算法在平均情況下時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.快速排序16、歸并排序的空間復(fù)雜度主要取決于什么？A.數(shù)據(jù)的規(guī)模B.遞歸調(diào)用的深度C.合并操作的次數(shù)D.數(shù)據(jù)的類(lèi)型17、在二叉樹(shù)中，前序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹(shù)、右子樹(shù)B.左子樹(shù)、根節(jié)點(diǎn)、右子樹(shù)C.左子樹(shù)、右子樹(shù)、根節(jié)點(diǎn)D.右子樹(shù)、根節(jié)點(diǎn)、左子樹(shù)18、以下哪個(gè)算法可以用于求解最大子數(shù)組和問(wèn)題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法19、時(shí)間復(fù)雜度和空間復(fù)雜度需要在設(shè)計(jì)算法時(shí)進(jìn)行（）A.單獨(dú)考慮B.綜合考慮C.先考慮時(shí)間復(fù)雜度D.先考慮空間復(fù)雜度20、以下哪個(gè)不是動(dòng)態(tài)規(guī)劃算法的關(guān)鍵步驟？（）A.定義狀態(tài)B.找出狀態(tài)轉(zhuǎn)移方程C.確定初始狀態(tài)D.進(jìn)行貪心選擇二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋選擇排序在隨機(jī)數(shù)據(jù)下的性能特點(diǎn)。2、（本題10分）闡述歸并排序在數(shù)據(jù)排序的穩(wěn)定性?xún)?yōu)化方面的方法。3、（本題10分）闡述堆排序在數(shù)據(jù)頻繁更新場(chǎng)景下的局限性。4、（本題10分）簡(jiǎn)述在社交網(wǎng)絡(luò)分析中的關(guān)系挖掘算法。