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

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

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