遼寧石油化工大學《數(shù)據(jù)科學與智能技術(shù)概論》2021-2022學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁遼寧石油化工大學《數(shù)據(jù)科學與智能技術(shù)概論》

2021-2022學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，若rear>front，則隊列中的元素個數(shù)為？A.rear-frontB.rear-front+MAXSIZEC.rear-front-1D.(rear-front+MAXSIZE)%MAXSIZE2、在數(shù)據(jù)結(jié)構(gòu)中，AVL樹的刪除操作比插入操作更復雜，以下關于刪除操作的描述，錯誤的是（）A.可能需要進行多次旋轉(zhuǎn)來保持平衡B.首先找到要刪除的節(jié)點C.刪除后不需要調(diào)整樹的結(jié)構(gòu)D.要考慮刪除節(jié)點的子樹情況3、在一個具有n個元素的有序單鏈表中，進行插入操作時，平均需要移動的元素個數(shù)約為？A.n/2B.nC.lognD.14、在二叉搜索樹中，每個節(jié)點的值都大于其左子樹中所有節(jié)點的值，小于其右子樹中所有節(jié)點的值。以下關于二叉搜索樹的操作，不正確的是（）A.插入操作需要按照節(jié)點值的大小找到合適的位置B.查找操作的時間復雜度在最壞情況下為O(n)C.刪除節(jié)點時，如果該節(jié)點有兩個子節(jié)點，可以選擇其左子樹中的最大節(jié)點或右子樹中的最小節(jié)點進行替換D.二叉搜索樹總是平衡的，即左右子樹的高度差不超過15、在數(shù)據(jù)結(jié)構(gòu)中，基數(shù)排序是一種非比較排序算法，以下關于基數(shù)排序的描述，不正確的是（）A.按照位數(shù)依次進行排序B.可以用于整數(shù)和字符串的排序C.時間復雜度為O(d(n+r))，其中d是位數(shù)，r是基數(shù)D.對數(shù)據(jù)的分布敏感6、已知一個棧的進棧序列為1,2,3,4，出棧序列為3,2,4,1，則棧的容量至少為（）。A.2B.3C.4D.57、在一個具有n個節(jié)點的二叉排序樹中，進行查找操作的平均時間復雜度是多少？A.O(n)B.O(logn)C.O(nlogn)D.取決于樹的形態(tài)8、在一棵二叉樹中，若每個節(jié)點的左子樹和右子樹的高度最多相差1，則該二叉樹被稱為平衡二叉樹。對于一個平衡二叉樹，進行插入操作后，為了保持平衡，可能需要進行多少次旋轉(zhuǎn)調(diào)整？A.0次B.1次C.最多2次D.不確定9、在數(shù)據(jù)結(jié)構(gòu)中，斐波那契堆是一種可合并堆，以下關于斐波那契堆的特點，描述不正確的是（）A.插入操作的時間復雜度為O(1)B.查找最小元素的時間復雜度為O(1)C.刪除最小元素的時間復雜度為O(logn)D.合并操作的時間復雜度為O(n)10、對于一個棧，進行入棧和出棧操作時，若棧頂指針top初始值為-1，當進行5次入棧和3次出棧操作后，top的值為多少？（）A.1B.2C.3D.411、平衡二叉樹是一種特殊的二叉搜索樹，其目的是為了保證查找效率。以下哪種操作可能會導致平衡二叉樹失去平衡？A.插入節(jié)點B.刪除節(jié)點C.查找節(jié)點D.以上都可能12、在一棵二叉樹中，若度為2的節(jié)點有10個，度為1的節(jié)點有20個，那么葉子節(jié)點的數(shù)量是多少？A.11B.21C.30D.無法確定13、以下關于堆的描述，正確的是：A.大頂堆中每個父節(jié)點的值都大于其子節(jié)點的值B.小頂堆中每個父節(jié)點的值都小于其子節(jié)點的值C.堆可以用順序存儲也可以用鏈式存儲D.堆是完全二叉樹14、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時進行先序遍歷，比較節(jié)點值B.同時進行中序遍歷，比較節(jié)點值C.同時進行后序遍歷，比較節(jié)點值D.比較兩棵樹的節(jié)點數(shù)量15、對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A.nB.n^2C.n(n-1)D.n(n+1)16、在一個具有n個節(jié)點的二叉樹中，若先序遍歷序列為ABC，中序遍歷序列為BAC，則后序遍歷序列是什么？A.BCAB.CBAC.ACBD.無法確定17、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA18、對于一個具有n個元素的有序單鏈表，若要在其中查找一個特定元素，其平均時間復雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)19、在圖的存儲結(jié)構(gòu)中，十字鏈表主要用于存儲有向圖，以下關于十字鏈表的特點，描述不正確的是（）A.既能方便地訪問出邊，也能方便地訪問入邊B.存儲空間比鄰接表節(jié)省C.對于刪除邊的操作比較復雜D.不適合用于稀疏有向圖20、對于一個具有n個頂點和e條邊的無向連通圖，其生成樹中邊的條數(shù)為（）。A.nB.n-1C.eD.e-1二、簡答題（本大題共4個小題，共40分)1、（本題10分）簡述哈希表的哈希沖突解決方法中二次探測法的原理及優(yōu)缺點。2、（本題10分）論述在二叉樹的層次遍歷中，如何使用隊列來實現(xiàn)，并分析其時間復雜度和空間復雜度。3、（本題10分）深入探討在一個具有n個元素的二叉搜索樹中，如何求第k小的元素。4、（本題10分）分析在字符串匹配中，如何結(jié)合多種算法提高匹配效率。三、設計題（