沈陽城市學(xué)院《數(shù)據(jù)可視化R語言》2021-2022學(xué)年期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記。…………密………………封………………線…………第1頁，共1頁沈陽城市學(xué)院

《數(shù)據(jù)可視化R語言》2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的循環(huán)隊列中，若隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，則隊列中元素的個數(shù)為？A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+12、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)文件系統(tǒng)的目錄結(jié)構(gòu)？A.二叉樹B.多叉樹C.鏈表D.棧3、在一個具有n個元素的小根堆中，刪除堆頂元素后，將最后一個元素放到堆頂，然后進(jìn)行調(diào)整，其時間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)4、在一個順序存儲的隊列中，若要在隊尾插入一個元素，需要移動元素的平均次數(shù)為（）A.0B.n/2C.nD.n-15、已知一個圖的鄰接表存儲結(jié)構(gòu)，若要判斷任意兩個頂點之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索6、在一個帶頭結(jié)點的單鏈表中，若要刪除表中所有值為x的結(jié)點，最優(yōu)的算法時間復(fù)雜度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)7、若要對一棵二叉排序樹進(jìn)行中序遍歷，得到的序列是一個有序序列，這是因為二叉排序樹的定義具有什么特性？（）A.左子樹的值小于根節(jié)點，右子樹的值大于根節(jié)點B.左子樹和右子樹的深度相同C.每個節(jié)點的值都不同D.以上都不是8、在數(shù)據(jù)結(jié)構(gòu)中，斐波那契堆是一種可合并堆，以下關(guān)于斐波那契堆的特點，描述不正確的是（）A.插入操作的時間復(fù)雜度為O(1)B.查找最小元素的時間復(fù)雜度為O(1)C.刪除最小元素的時間復(fù)雜度為O(logn)D.合并操作的時間復(fù)雜度為O(n)9、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)圖的廣度優(yōu)先遍歷的輔助隊列？A.循環(huán)隊列B.鏈隊列C.優(yōu)先隊列D.雙端隊列10、若要對一個具有n個元素的無序數(shù)組進(jìn)行排序，以下哪種排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序11、對于一個具有n個元素的順序存儲的循環(huán)隊列，隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，若隊列非空，則隊列中元素的個數(shù)為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+112、對于一個具有n個節(jié)點的完全二叉樹，若按層序編號，則編號為i的節(jié)點，其雙親節(jié)點的編號為？A.i/2B.(i-1)/2C.2iD.2i+113、對于一個滿二叉樹，若其高度為h，則其節(jié)點總數(shù)為多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-114、對于一個采用鏈?zhǔn)酱鎯Φ年犃?，若隊頭指針和隊尾指針相同，則隊列的狀態(tài)為：A.隊空B.隊滿C.不確定D.隊列中只有一個元素15、在一個循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，隊列最大容量為MAXSIZE，若當(dāng)前隊列長度為n，則判斷隊滿的條件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE16、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，有鄰接矩陣和鄰接表兩種存儲方式。對于一個稀疏圖，以下說法正確的是（）A.鄰接矩陣比鄰接表更節(jié)省存儲空間B.鄰接表更適合用于存儲和遍歷C.兩種存儲方式的時間復(fù)雜度相同D.稀疏圖的邊數(shù)很少，節(jié)點數(shù)很多17、對于單鏈表，若要訪問鏈表中的第i個元素，必須從鏈表的頭指針開始依次遍歷，平均時間復(fù)雜度為O(n)。那么如果要在鏈表的末尾添加一個新元素，時間復(fù)雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)18、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為（）。A.CEABDB.CEDBAC.CABDED.CEDAB19、在一個B樹中，每個節(jié)點的關(guān)鍵字?jǐn)?shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-120、在一個具有n個元素的有序單鏈表中，若要查找一個特定元素，以下關(guān)于查找操作的時間復(fù)雜度的描述，哪一項是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋如何在一個具有n個元素的最小堆中，找出第k小的元素，并分析其時間復(fù)雜度。2、（本題10分）闡述如何在一個具有n個頂點和e條邊的帶權(quán)無向圖中，使用Johnson算法求解所有頂點對之間的最短路徑問題，分析其原理和時間復(fù)雜度。3、（本題10分）深入探討在一個具有n個元素的小根堆中，如何使用堆來實現(xiàn)優(yōu)先隊列的功能。4、（本題10分）論述伸展