安徽理工大學(xué)《數(shù)據(jù)科學(xué)與工程》2021-2022學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁安徽理工大學(xué)

《數(shù)據(jù)科學(xué)與工程》2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種排序算法在平均情況下的時間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序2、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問？（）A.鏈表B.隊列C.棧D.數(shù)組3、在一個具有n個元素的有序數(shù)組中，使用插入排序進(jìn)行排序，其最壞情況下的時間復(fù)雜度為？（）A.O(n)B.O(log?n)C.O(n2)D.O(nlog?n)4、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的最長公共子序列問題？A.二維數(shù)組B.棧C.隊列D.樹5、排序算法的穩(wěn)定性和時間復(fù)雜度可以用于選擇合適的排序算法，以下關(guān)于它們的說法中，錯誤的是？（）A.穩(wěn)定性對于某些應(yīng)用場景非常重要，如對具有多個關(guān)鍵字的記錄進(jìn)行排序時。B.時間復(fù)雜度是衡量排序算法效率的重要指標(biāo)，不同的排序算法具有不同的時間復(fù)雜度。C.可以根據(jù)實(shí)際情況選擇穩(wěn)定的或不穩(wěn)定的排序算法，以及時間復(fù)雜度較低的排序算法。D.排序算法的穩(wěn)定性和時間復(fù)雜度只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價值。6、設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為：A.連接B.模式匹配C.求子串D.求串長7、在一個具有n個頂點(diǎn)的無向圖中，若采用鄰接矩陣存儲，則矩陣中非零元素的個數(shù)至少為？（）A.nB.n-1C.2(n-1)D.n(n-1)/28、對于一個具有n個頂點(diǎn)的無向完全圖，其邊的數(shù)量為多少？（）A.n(n-1)/2B.n(n-1)C.n2D.2n9、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，若要表示一個有向圖，通?？梢允褂媚姆N存儲結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.以上均可10、對于一個具有n個元素的無序數(shù)組，若要對其進(jìn)行排序，以下哪種算法在最壞情況下時間復(fù)雜度最高？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序11、在一個有向圖中，所有頂點(diǎn)的入度之和與出度之和的關(guān)系是：A.入度之和大于出度之和B.入度之和小于出度之和C.入度之和等于出度之和D.沒有確定的關(guān)系12、設(shè)有一個長度為n的順序表，要在第i個元素之前插入一個新元素，并且移動元素的平均次數(shù)為n/2，則插入算法的平均時間復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)13、在一個具有n個節(jié)點(diǎn)的二叉樹中，若先序遍歷序列為ABC，中序遍歷序列為BAC，則后序遍歷序列是什么？A.BCAB.CBAC.ACBD.無法確定14、在一個具有n個頂點(diǎn)的無向圖中，若要判斷兩個頂點(diǎn)之間是否存在路徑，使用哪種算法較為合適？A.迪杰斯特拉算法B.弗洛伊德算法C.深度優(yōu)先遍歷或廣度優(yōu)先遍歷D.拓?fù)渑判?5、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠高效地支持區(qū)間查詢操作？（）A.線段樹B.二叉搜索樹C.堆D.鏈表16、對于一個具有n個元素的有序數(shù)組，使用二分查找算法查找一個特定元素。以下關(guān)于二分查找的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、在一個帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接已選頂點(diǎn)和未選頂點(diǎn)的權(quán)值最小的邊C.任意一條邊D.以上都不對18、在一個有n個頂點(diǎn)和e條邊的無向圖中，采用鄰接矩陣存儲，其空間復(fù)雜度為多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)19、在一個小根堆中，最小的元素總是位于堆頂。若要將一個元素插入到堆中并保持堆的性質(zhì)，以下哪種操作是必須的？A.從堆頂向下調(diào)整B.從堆底向上調(diào)整C.先刪除堆頂元素再插入D.以上都不對20、在一個帶頭結(jié)點(diǎn)的循環(huán)鏈表中，若要判斷鏈表是否為空，應(yīng)檢查？（）A.頭結(jié)點(diǎn)的指針是否為空B.頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)的指針是否指向頭結(jié)點(diǎn)C.尾結(jié)點(diǎn)的指針是否為空D.尾結(jié)點(diǎn)的下一個結(jié)點(diǎn)的指針是否指向頭結(jié)點(diǎn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）在一個具有n個頂點(diǎn)的有向圖中，如何判斷圖中是否存在回路？2、（本題10分）詳細(xì)闡述如何在一個鏈表中刪除所有值為給定值的節(jié)點(diǎn)。3、（本題10分）解釋數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用場景，如表達(dá)式的前綴、中綴、后綴轉(zhuǎn)換等，并說明其原理。4、（本題10分）詳細(xì)闡述基數(shù)排序在處理字符