阜陽師范大學(xué)《數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)專業(yè)導(dǎo)論》2021-2022學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁阜陽師范大學(xué)《數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)專業(yè)導(dǎo)論》

2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)元素的無序數(shù)組中，采用冒泡排序進(jìn)行排序，在最壞情況下，需要比較的次數(shù)為（）。A.n-1B.n(n-1)/2C.n(n+1)/2D.n^22、對于一個(gè)具有n個(gè)頂點(diǎn)的有向圖，若采用鄰接表表示，則所有鄰接表中的邊節(jié)點(diǎn)總數(shù)為（）。A.nB.n+1C.eD.2e3、在一個(gè)平衡二叉搜索樹中，插入一個(gè)新節(jié)點(diǎn)后，可能需要進(jìn)行的調(diào)整操作次數(shù)最多為（）A.1B.lognC.nD.nlogn4、設(shè)有一個(gè)m階的B樹，每個(gè)非葉子節(jié)點(diǎn)至少有┌m/2┐個(gè)孩子，則一棵3階B樹中，根節(jié)點(diǎn)最少有幾個(gè)孩子？（）A.1B.2C.3D.45、在二叉搜索樹中，每個(gè)節(jié)點(diǎn)的值都大于其左子樹中所有節(jié)點(diǎn)的值，小于其右子樹中所有節(jié)點(diǎn)的值。以下關(guān)于二叉搜索樹的操作，不正確的是（）A.插入操作需要按照節(jié)點(diǎn)值的大小找到合適的位置B.查找操作的時(shí)間復(fù)雜度在最壞情況下為O(n)C.刪除節(jié)點(diǎn)時(shí)，如果該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，可以選擇其左子樹中的最大節(jié)點(diǎn)或右子樹中的最小節(jié)點(diǎn)進(jìn)行替換D.二叉搜索樹總是平衡的，即左右子樹的高度差不超過16、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，若要表示一個(gè)有向圖，通常可以使用哪種存儲結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.以上均可7、在一個(gè)具有n個(gè)元素的有序數(shù)組中進(jìn)行二分查找，其時(shí)間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(logn)D.O(n^2)8、對于一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時(shí)間復(fù)雜度為：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)9、若要對一個(gè)具有n個(gè)元素的無序數(shù)組進(jìn)行排序，以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序10、在數(shù)據(jù)結(jié)構(gòu)中，優(yōu)先隊(duì)列可以用堆來實(shí)現(xiàn)，以下關(guān)于堆調(diào)整的描述，錯(cuò)誤的是（）A.插入元素時(shí)，從下往上調(diào)整堆B.刪除堆頂元素時(shí)，從上往下調(diào)整堆C.調(diào)整堆的過程中，節(jié)點(diǎn)的值可能會交換D.調(diào)整堆的時(shí)間復(fù)雜度與堆的大小無關(guān)11、在一個(gè)具有n個(gè)頂點(diǎn)和m條邊的無向圖中，若采用鄰接表存儲，則存儲空間復(fù)雜度主要取決于？A.nB.mC.n+mD.n^212、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向完全圖，其弧的條數(shù)為（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/213、若一個(gè)棧的輸入序列為1,2,3,4,5，不可能得到的輸出序列是？（）A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,514、一棵二叉樹的先序遍歷序列為ABDECFGH，中序遍歷序列為DBEAFCGH，則該二叉樹的后序遍歷序列為（）。A.DEBFGCHAB.DEBFHGCAC.DEBHGFCAD.DEBHFCGA15、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖中，采用鄰接表存儲，求頂點(diǎn)的入度的時(shí)間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)16、圖的存儲方式和遍歷方式可以用于解決很多實(shí)際問題，以下關(guān)于它們的應(yīng)用的說法中，錯(cuò)誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，適用于社交網(wǎng)絡(luò)分析和交通網(wǎng)絡(luò)規(guī)劃等。B.圖的鄰接表可以用于表示稀疏圖，適用于地圖繪制和電路圖設(shè)計(jì)等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問題和最小生成樹問題等，適用于物流配送和通信網(wǎng)絡(luò)優(yōu)化等。D.圖的存儲方式和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。17、在一個(gè)具有n個(gè)元素的單鏈表中，若要在第i個(gè)位置（1<=i<=n）插入一個(gè)新元素，平均需要遍歷多少個(gè)節(jié)點(diǎn)？（）A.i-1B.iC.(i-1)/2D.i/218、在一棵度為4的樹中，度為4的節(jié)點(diǎn)個(gè)數(shù)為1，度為3的節(jié)點(diǎn)個(gè)數(shù)為2，度為2的節(jié)點(diǎn)個(gè)數(shù)為3，度為1的節(jié)點(diǎn)個(gè)數(shù)為4，葉子節(jié)點(diǎn)個(gè)數(shù)為（）。A.15B.16C.17D.1819、已知一個(gè)棧的進(jìn)棧序列為1,2,3,4，出棧序列為3,2,4,1，則棧的容量至少為（）。A.2B.3C.4D.520、在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，若采用鄰接矩陣存儲，則矩陣中非零元素的個(gè)數(shù)至少為？（）A.nB.n-1C.2(n-1)D.n(n-1)/2二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)說明選擇排序算法的基本思想和在最壞情況下的時(shí)間復(fù)雜度分析。2、（本題10分）說明二叉樹的遍歷算法在二叉樹的平衡檢查優(yōu)化問題、樹的對稱問題變種中的應(yīng)用。3、（本題10分）論述在堆排序的優(yōu)化中，如何避免頻繁的調(diào)整操作以提高性能。4、（本題10分）對于一個(gè)具有n個(gè)元素的環(huán)形鏈表，如何判斷鏈表中是否存在環(huán)？請給出具體的算法思路和代碼示例。三、設(shè)計(jì)題（本大題共2個(gè)