南京傳媒學院《數(shù)據(jù)可視化技術》2023-2024學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁南京傳媒學院《數(shù)據(jù)可視化技術》

2023-2024學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個采用順序存儲結構的線性表中，若要在第i個位置插入一個新元素，需要將第i個位置及之后的元素依次向后移動一位。以下關于插入操作的時間復雜度的描述，哪一項是正確的？A.時間復雜度為O(1)B.時間復雜度為O(n)C.時間復雜度為O(logn)D.時間復雜度為O(nlogn)2、二叉樹的性質(zhì)和遍歷方式可以用于解決很多實際問題，以下關于它們的應用的說法中，錯誤的是？（）A.二叉搜索樹可以用于實現(xiàn)高效的查找、插入和刪除操作，適用于數(shù)據(jù)庫索引和文件系統(tǒng)等。B.平衡二叉樹可以用于解決二叉搜索樹的不平衡問題，提高查找效率，適用于大規(guī)模數(shù)據(jù)的存儲和管理。C.二叉樹的遍歷方式可以用于實現(xiàn)二叉樹的復制、遍歷和序列化等操作，適用于數(shù)據(jù)備份和傳輸?shù)?。D.二叉樹的性質(zhì)和遍歷方式只適用于理論研究，在實際應用中沒有實際價值。3、設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為：A.連接B.模式匹配C.求子串D.求串長4、在一個哈希表中，解決沖突的方法不包括：A.開放定址法B.再哈希法C.建立索引表D.鏈地址法5、在一個具有n個元素的順序存儲的線性表中，刪除第i個元素（1<=i<=n），平均需要移動多少個元素？（）A.n-iB.iC.(n-i)/2D.n/26、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），需要移動的元素個數(shù)最多為（）。A.i-1B.n-iC.n-i+1D.n-17、一棵二叉樹的先序遍歷序列為ABDECFGH，中序遍歷序列為DBEAFCGH，則該二叉樹的后序遍歷序列為（）。A.DEBFGCHAB.DEBFHGCAC.DEBHGFCAD.DEBHFCGA8、隊列是另一種特殊的線性數(shù)據(jù)結構，它遵循先進先出（FIFO）的原則。以下關于隊列的說法中，錯誤的是？（）A.隊列可以用數(shù)組或鏈表實現(xiàn)。B.隊列的插入操作在隊尾進行，刪除操作在隊首進行。C.隊列可以用于實現(xiàn)任務調(diào)度、消息傳遞等。D.隊列的容量是無限的，可以存儲任意數(shù)量的元素。9、在一個具有n個節(jié)點的帶權有向圖中，若存在負權邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用10、對于一個具有n個節(jié)點的AVL樹，插入一個新節(jié)點后，調(diào)整樹的平衡，其時間復雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、在一棵二叉樹中，若度為2的節(jié)點有10個，度為1的節(jié)點有20個，那么葉子節(jié)點的數(shù)量是多少？A.11B.21C.30D.無法確定12、以下關于堆的描述，正確的是：A.大頂堆中每個父節(jié)點的值都大于其子節(jié)點的值B.小頂堆中每個父節(jié)點的值都小于其子節(jié)點的值C.堆可以用順序存儲也可以用鏈式存儲D.堆是完全二叉樹13、在一個具有n個節(jié)點的二叉排序樹中，進行查找操作的平均時間復雜度是多少？A.O(n)B.O(logn)C.O(nlogn)D.取決于樹的形態(tài)14、若一個圖的廣度優(yōu)先遍歷序列為ABCDEFG，則其深度優(yōu)先遍歷序列可能為？（）A.ABDCEFGB.ACBDEFGC.ADBCEFGD.AECBDFG15、對于一個具有n個元素的循環(huán)隊列，隊頭指針為front，隊尾指針為rear，隊列滿的條件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front16、對于一個具有n個元素的歸并排序，其時間復雜度為？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)17、圖的存儲方式有鄰接矩陣和鄰接表兩種，以下關于它們的特點的說法中，錯誤的是？（）A.鄰接矩陣適合存儲稠密圖，空間復雜度為O(n^2)。B.鄰接表適合存儲稀疏圖，空間復雜度為O(n+m)，其中n是頂點數(shù)，m是邊數(shù)。C.鄰接矩陣的查找邊的時間復雜度為O(1)。D.鄰接表的插入邊和刪除邊的時間復雜度為O(n)。18、在一個棧中，若入棧序列為1,2,3,4，且在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.1719、在一個具有n個元素的鏈表中，訪問第i個元素的時間復雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)20、在一個用順序存儲結構實現(xiàn)的棧中，若棧頂指針top指向棧頂元素的上一個位置，當棧為空時，top的值為？A.-1B.0C.1D.n-1（其中n為棧的最大容量）二、簡答題（本大題共4個小題，共40分)1、（本題10分）在圖的遍歷中，如何避免重復訪問節(jié)點？請說明具體方法。2、（本題10分）數(shù)組和鏈表在存儲數(shù)據(jù)方面有哪些不同之處？各自的優(yōu)缺點是什么？3、（本題10分）闡述如何在一個鏈表中實現(xiàn)冒泡排序，給出算法步驟和實現(xiàn)代碼，并分析其時間復雜度和空間復雜度。4、（本題10分）詳細闡