南京工業(yè)大學(xué)《工程倫理：計(jì)算機(jī)》2021-2022學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁南京工業(yè)大學(xué)《工程倫理：計(jì)算機(jī)》2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下哪種算法的時(shí)間復(fù)雜度最低？（）A.O(n^2)B.O(nlogn)C.O(logn)D.O(n)2、快速排序在最好情況下的時(shí)間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)3、以下哪種算法常用于解決組合優(yōu)化問題？（）A.貪心算法B.回溯法C.分治法D.動(dòng)態(tài)規(guī)劃4、動(dòng)態(tài)規(guī)劃算法通常需要一個(gè)什么來存儲子問題的解？A.數(shù)組B.鏈表C.棧D.隊(duì)列5、在動(dòng)態(tài)規(guī)劃中，優(yōu)化子問題的解存儲方式可以（）A.降低時(shí)間復(fù)雜度B.降低空間復(fù)雜度C.提高可讀性D.以上都是6、一個(gè)算法的時(shí)間復(fù)雜度為O(n2)，如果輸入規(guī)模擴(kuò)大一倍，那么運(yùn)行時(shí)間會(huì)變?yōu)樵瓉淼膸妆?？A.2倍B.4倍C.8倍D.16倍7、以下哪種排序算法在平均情況下性能最優(yōu)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序8、歸并排序的合并操作的時(shí)間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)9、在二叉樹中，中序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹10、算法的最優(yōu)性是指（）A.時(shí)間復(fù)雜度最低B.空間復(fù)雜度最低C.得到的解最優(yōu)D.以上都是11、以下哪種排序算法在平均情況下時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.快速排序12、二分查找算法要求數(shù)據(jù)必須是（）A.有序的B.無序的C.平衡的D.以上都不是13、在遞歸算法中，當(dāng)遞歸深度過大時(shí)可能會(huì)導(dǎo)致（）A.運(yùn)行速度加快B.內(nèi)存溢出C.結(jié)果更準(zhǔn)確D.以上都不是14、在貪心算法中，得到的解可能是（）A.最優(yōu)解B.近似最優(yōu)解C.可行解D.以上都可能15、在貪心算法中，最終的解依賴于（）A.子問題的選擇順序B.問題的規(guī)模C.數(shù)據(jù)的分布D.以上都是16、快速排序的樞軸元素選擇對算法的性能有很大影響，以下哪種選擇方式通常比較好？A.第一個(gè)元素B.最后一個(gè)元素C.中間元素D.隨機(jī)元素17、以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)棧的功能？A.數(shù)組B.鏈表C.隊(duì)列D.二叉樹18、在動(dòng)態(tài)規(guī)劃中，通過保存子問題的解來避免（）A.重復(fù)計(jì)算B.錯(cuò)誤計(jì)算C.遺漏計(jì)算D.以上都是19、在圖的存儲結(jié)構(gòu)中，鄰接矩陣適合存儲什么樣的圖？A.稀疏圖B.稠密圖C.有向圖D.無向圖20、在二叉樹中，后序遍歷的順序是？A.根節(jié)點(diǎn)、左子樹、右子樹B.左子樹、根節(jié)點(diǎn)、右子樹C.左子樹、右子樹、根節(jié)點(diǎn)D.右子樹、根節(jié)點(diǎn)、左子樹二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋選擇排序在數(shù)據(jù)規(guī)模較大時(shí)的效率問題。2、（本題10分）簡述計(jì)數(shù)排序算法的適用場景和實(shí)現(xiàn)方法。3、（本題10分）闡述歸并排序在數(shù)據(jù)壓縮中的作用。4、（本題10分）分析希爾排序算法的特點(diǎn)和優(yōu)勢。三、設(shè)計(jì)題（本大題共2個(gè)小