長(zhǎng)春工業(yè)大學(xué)《數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)導(dǎo)論》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)長(zhǎng)春工業(yè)大學(xué)

《數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)導(dǎo)論》2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、一棵完全二叉樹的第5層（根為第1層）有16個(gè)葉子節(jié)點(diǎn)，則該完全二叉樹的節(jié)點(diǎn)總數(shù)最少為（）。A.47B.55C.63D.642、在數(shù)據(jù)結(jié)構(gòu)中，基數(shù)排序是一種非比較排序算法，以下關(guān)于基數(shù)排序的描述，不正確的是（）A.按照位數(shù)依次進(jìn)行排序B.可以用于整數(shù)和字符串的排序C.時(shí)間復(fù)雜度為O(d(n+r))，其中d是位數(shù)，r是基數(shù)D.對(duì)數(shù)據(jù)的分布敏感3、對(duì)于一個(gè)具有n個(gè)元素的順序存儲(chǔ)的棧，若要判斷棧是否已滿，應(yīng)判斷？（）A.top==n-1B.top==nC.top>=n-1D.top>=n4、在數(shù)據(jù)結(jié)構(gòu)中，AVL樹的刪除操作比插入操作更復(fù)雜，以下關(guān)于刪除操作的描述，錯(cuò)誤的是（）A.可能需要進(jìn)行多次旋轉(zhuǎn)來(lái)保持平衡B.首先找到要?jiǎng)h除的節(jié)點(diǎn)C.刪除后不需要調(diào)整樹的結(jié)構(gòu)D.要考慮刪除節(jié)點(diǎn)的子樹情況5、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)。對(duì)于一個(gè)滿二叉樹，若其高度為h，則節(jié)點(diǎn)總數(shù)為多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-16、在一個(gè)具有n個(gè)元素的無(wú)序鏈表中，若要對(duì)其進(jìn)行快速排序，以下關(guān)于快速排序的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)7、若一個(gè)圖的廣度優(yōu)先遍歷序列為ABCDEFG，則其深度優(yōu)先遍歷序列可能為？（）A.ABDCEFGB.ACBDEFGC.ADBCEFGD.AECBDFG8、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)連通圖，其最小生成樹一定包含圖中的所有節(jié)點(diǎn)嗎？A.一定包含B.不一定包含C.視情況而定D.以上都不對(duì)9、在數(shù)據(jù)結(jié)構(gòu)中，鏈表的反轉(zhuǎn)是一個(gè)常見的操作，以下關(guān)于鏈表反轉(zhuǎn)的實(shí)現(xiàn)方法，錯(cuò)誤的是（）A.使用三個(gè)指針依次遍歷并調(diào)整節(jié)點(diǎn)的鏈接關(guān)系B.遞歸方式實(shí)現(xiàn)時(shí)不需要額外的輔助空間C.迭代方式的時(shí)間復(fù)雜度為O(n)D.遞歸方式的空間復(fù)雜度比迭代方式低10、在一個(gè)順序存儲(chǔ)的棧中，若要實(shí)現(xiàn)共享?xiàng)?，即兩個(gè)棧共用一個(gè)數(shù)組空間，以下關(guān)于棧頂指針的設(shè)置，哪一種方案較為合理？A.兩個(gè)棧的棧頂指針分別從數(shù)組的兩端向中間移動(dòng)B.兩個(gè)棧的棧頂指針都從數(shù)組的同一端開始移動(dòng)C.一個(gè)棧的棧頂指針從數(shù)組的開頭移動(dòng)，另一個(gè)從結(jié)尾移動(dòng)D.以上都可以11、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無(wú)向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時(shí)間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)12、設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為：A.連接B.模式匹配C.求子串D.求串長(zhǎng)13、對(duì)于一個(gè)用鏈表實(shí)現(xiàn)的棧，若要在棧頂插入一個(gè)元素，時(shí)間復(fù)雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)14、在一個(gè)具有n個(gè)元素的小頂堆中，若將堆頂元素與最后一個(gè)元素交換，然后對(duì)堆進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)15、已知一個(gè)圖的鄰接表存儲(chǔ)結(jié)構(gòu)，若要判斷任意兩個(gè)頂點(diǎn)之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索16、對(duì)于一個(gè)棧，若入棧序列為1、2、3、4、5，在入棧過(guò)程中可以出棧，則可能得到的出棧序列有多少種？（）A.5B.14C.21D.無(wú)數(shù)種17、以下關(guān)于二叉排序樹的描述，錯(cuò)誤的是：A.左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值B.右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值C.中序遍歷二叉排序樹可得到一個(gè)有序序列D.二叉排序樹的查找效率總是最高的18、以下關(guān)于哈夫曼樹的描述，正確的是：A.哈夫曼樹一定是完全二叉樹B.哈夫曼樹中不存在度為1的節(jié)點(diǎn)C.哈夫曼樹的帶權(quán)路徑長(zhǎng)度是唯一的D.哈夫曼樹的構(gòu)建過(guò)程不需要進(jìn)行節(jié)點(diǎn)的比較和交換19、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中，若采用中序遍歷得到的節(jié)點(diǎn)序列是有序的，則該二叉樹可能是什么類型？A.滿二叉樹B.完全二叉樹C.二叉搜索樹D.以上都有可能20、在一個(gè)具有n個(gè)頂點(diǎn)的圖中，若存在回路，則深度優(yōu)先遍歷可能會(huì)出現(xiàn)什么情況？（）A.訪問某些頂點(diǎn)多次B.無(wú)法完成遍歷C.結(jié)果不正確D.以上都有可能二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）在一個(gè)鏈表中，如何查找鏈表中環(huán)的入口結(jié)點(diǎn)？2、（本題10分）解釋什么是AVL樹，并說(shuō)明其在保持平衡方面的調(diào)整策略。3、（本題10分）詳細(xì)論述在具有n個(gè)頂點(diǎn)和e條邊的圖中，如何使用廣度優(yōu)先搜索算法計(jì)算兩點(diǎn)之間的最短路徑，并給出具體的算法步驟和代碼實(shí)現(xiàn)。4、（本題10分）論述在動(dòng)態(tài)規(guī)劃的狀態(tài)定義中，如何準(zhǔn)確捕捉問題的本質(zhì)特征以建立有效的狀態(tài)轉(zhuǎn)移方程。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分)1、（