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

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

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