北京城市學(xué)院《工程三級(jí)實(shí)訓(xùn)（Androd移動(dòng)開(kāi)發(fā)技術(shù)）》2021-2022學(xué)年期末試卷

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線第1頁(yè)，共3頁(yè)北京城市學(xué)院《工程三級(jí)實(shí)訓(xùn)（Androd移動(dòng)開(kāi)發(fā)技術(shù)）》2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在回溯法中，當(dāng)所有可能的選擇都嘗試過(guò)后，算法（）A.停止B.繼續(xù)C.重新開(kāi)始D.以上都不是2、在分治法中，合并子問(wèn)題的解的時(shí)間復(fù)雜度通常為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、空間復(fù)雜度主要考慮（）A.算法執(zhí)行過(guò)程中占用的內(nèi)存空間B.算法執(zhí)行過(guò)程中占用的硬盤(pán)空間C.算法執(zhí)行過(guò)程中占用的網(wǎng)絡(luò)帶寬D.以上都是4、以下哪種排序算法的平均時(shí)間復(fù)雜度為O(nlogn)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序5、在遞歸算法中，當(dāng)遞歸深度過(guò)大時(shí)可能會(huì)導(dǎo)致（）A.運(yùn)行速度加快B.內(nèi)存溢出C.結(jié)果更準(zhǔn)確D.以上都不是6、動(dòng)態(tài)規(guī)劃算法的核心是？A.遞歸B.貪心選擇C.記憶化搜索D.分治7、歸并排序的空間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)8、在圖的遍歷中，廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊(duì)列C.鏈表D.樹(shù)9、以下哪個(gè)不是貪心算法的局限性？A.不一定能得到全局最優(yōu)解B.算法的時(shí)間復(fù)雜度較高C.對(duì)問(wèn)題的性質(zhì)有一定要求D.難以證明算法的正確性10、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)棧的功能？A.數(shù)組B.鏈表C.隊(duì)列D.二叉樹(shù)11、以下哪個(gè)不是算法的評(píng)價(jià)指標(biāo)？（）A.正確性B.可讀性C.可擴(kuò)展性D.代碼長(zhǎng)度12、以下哪種算法常用于解決皇后問(wèn)題？（）A.貪心算法B.回溯法C.動(dòng)態(tài)規(guī)劃D.分治法13、以下哪種算法常用于構(gòu)建最小生成樹(shù)？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法14、在圖的遍歷中，深度優(yōu)先搜索和廣度優(yōu)先搜索的主要區(qū)別是？A.遍歷的順序不同B.時(shí)間復(fù)雜度不同C.空間復(fù)雜度不同D.適用的圖類(lèi)型不同15、算法的最優(yōu)性是指（）A.時(shí)間復(fù)雜度最低B.空間復(fù)雜度最低C.得到的解最優(yōu)D.以上都是16、算法的正確性是指（）A.對(duì)于任意輸入都能得到正確結(jié)果B.對(duì)于大部分輸入能得到正確結(jié)果C.對(duì)于特定輸入能得到正確結(jié)果D.以上都不是17、在算法設(shè)計(jì)中，如何提高算法的可讀性？A.使用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)B.減少注釋和文檔C.采用簡(jiǎn)潔明了的代碼風(fēng)格D.增加算法的時(shí)間復(fù)雜度18、在圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表適合存儲(chǔ)什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無(wú)向圖19、時(shí)間復(fù)雜度和空間復(fù)雜度需要在設(shè)計(jì)算法時(shí)進(jìn)行（）A.單獨(dú)考慮B.綜合考慮C.先考慮時(shí)間復(fù)雜度D.先考慮空間復(fù)雜度20、以下哪個(gè)算法可以用于解決0-1背包問(wèn)題？A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃法二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）以字符串相似性度量問(wèn)題為例，分析動(dòng)態(tài)規(guī)劃算法的應(yīng)用。2、（本題10分）說(shuō)明如何用分支限界法解決多目標(biāo)優(yōu)化問(wèn)題。3、（本題10分）解釋桶排序算法的工作原理和優(yōu)缺點(diǎn)。4、（本題10分）分析在物流配送中的路徑規(guī)劃算法。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分