長春工業(yè)大學(xué)《數(shù)據(jù)可視化》2021-2022學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁長春工業(yè)大學(xué)

《數(shù)據(jù)可視化》2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個元素的順序存儲的循環(huán)隊列，隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，若隊列非空，則隊列中元素的個數(shù)為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+12、在一棵二叉樹中，若每個節(jié)點的左子樹和右子樹的高度最多相差1，則該二叉樹被稱為平衡二叉樹。對于一個平衡二叉樹，進行插入操作后，為了保持平衡，可能需要進行多少次旋轉(zhuǎn)調(diào)整？A.0次B.1次C.最多2次D.不確定3、在一個鏈隊列中，假設(shè)隊頭指針為front，隊尾指針為rear，刪除隊頭元素的操作是：A.front=front->nextB.rear=rear->nextC.front->next=NULLD.rear->next=NULL4、在數(shù)據(jù)結(jié)構(gòu)中，斐波那契堆是一種可合并堆，以下關(guān)于斐波那契堆的特點，描述不正確的是（）A.插入操作的時間復(fù)雜度為O(1)B.查找最小元素的時間復(fù)雜度為O(1)C.刪除最小元素的時間復(fù)雜度為O(logn)D.合并操作的時間復(fù)雜度為O(n)5、在數(shù)據(jù)結(jié)構(gòu)中，桶排序是一種外部排序算法，以下關(guān)于桶排序的描述，錯誤的是（）A.要求輸入數(shù)據(jù)具有特定的分布B.時間復(fù)雜度為O(n)C.空間復(fù)雜度較高D.適用于大規(guī)模數(shù)據(jù)排序6、已知一個完全二叉樹的節(jié)點總數(shù)為100，其葉子節(jié)點的個數(shù)為（）。A.49B.50C.51D.不確定7、在一個用十字鏈表存儲的有向圖中，查找一個頂點的所有出邊和入邊的時間復(fù)雜度是？（）A.O(1)B.O(n)C.O(e)D.O(n+e)8、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)，通過哈希函數(shù)將關(guān)鍵字映射到存儲位置。關(guān)于哈希沖突的解決方法，錯誤的是（）A.開放定址法通過尋找空閑位置來解決沖突B.鏈地址法將沖突的元素存儲在鏈表中C.再哈希法通過更換哈希函數(shù)來解決沖突D.哈希沖突無法避免，且對查找效率沒有影響9、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)并查集？（）A.數(shù)組B.鏈表C.樹D.哈希表10、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實現(xiàn)字符串的模式匹配操作？A.二叉樹B.哈希表C.棧D.后綴樹11、若一棵二叉樹的葉子節(jié)點數(shù)為n0，度為2的節(jié)點數(shù)為n2，則n0和n2之間的關(guān)系是？（）A.n0=n2-1B.n0=n2+1C.n0=2n2-1D.n0=2n2+112、已知一個圖的鄰接表存儲結(jié)構(gòu)，若要判斷任意兩個頂點之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索13、已知一個哈希表的長度為11，哈希函數(shù)為H(key)=key%11，采用二次探測法處理沖突。若依次插入關(guān)鍵字15、38、61、84，則在查找關(guān)鍵字61時需要進行幾次探測？（）A.1B.2C.3D.414、以下哪種排序算法在平均情況下的時間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序15、在一個具有n個節(jié)點的二叉排序樹中，刪除一個節(jié)點后，為了保持二叉排序樹的性質(zhì)，可能需要進行哪些操作？A.僅調(diào)整刪除節(jié)點的子樹B.從根節(jié)點開始重新調(diào)整C.調(diào)整整個樹的結(jié)構(gòu)D.以上都有可能16、在一個具有n個頂點的有向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n17、對于一個具有n個元素的無序數(shù)組，使用插入排序進行排序，其最好情況下的時間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)18、對于一個具有n個元素的快速排序，每次劃分選取的基準(zhǔn)元素不同，對排序的時間復(fù)雜度有何影響？（）A.沒有影響B(tài).可能會提高C.可能會降低D.以上都不對19、在一個具有n個頂點和m條邊的無向圖中，若采用鄰接表存儲，則存儲空間復(fù)雜度主要取決于？A.nB.mC.n+mD.n^220、已知一個棧的進棧序列為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,5二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋如何判斷一個二叉樹是否為滿二叉樹，給出相應(yīng)的算法和代碼。2、（本題10分）深入探討在一個具有n個元素的二叉搜索樹中，如何求第k小的元素。3、（本題10分）闡述隊列在任務(wù)調(diào)度中的應(yīng)用，如任務(wù)隊列、優(yōu)先級隊列等，并解釋其作用。4、（本題10分）在一個具有n個元素的雙向鏈表中，說明如何實現(xiàn)向前和向后的遍歷，以及如何在雙向鏈表中插入和刪除節(jié)點。三、設(shè)計題（本大題共2個小