北京城市學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(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ù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一棵二叉搜索樹，進(jìn)行中序遍歷得到的序列是一個(gè)有序序列。若對(duì)其進(jìn)行刪除操作，以下關(guān)于時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.平均時(shí)間復(fù)雜度為O(logn)，最壞情況為O(n)B.時(shí)間復(fù)雜度始終為O(logn)C.平均時(shí)間復(fù)雜度為O(n)，最壞情況為O(nlogn)D.時(shí)間復(fù)雜度始終為O(n)2、在一個(gè)用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧中，若棧頂指針top指向棧頂元素的上一個(gè)位置，當(dāng)棧為空時(shí)，top的值為？A.-1B.0C.1D.n-1（其中n為棧的最大容量）3、以下關(guān)于紅黑樹的性質(zhì)，錯(cuò)誤的是：A.每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色B.根節(jié)點(diǎn)是黑色的C.每個(gè)葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）是黑色的D.紅色節(jié)點(diǎn)的子節(jié)點(diǎn)一定是紅色的4、對(duì)于一個(gè)用鏈表表示的線性表，在表頭插入一個(gè)新元素和在表尾插入一個(gè)新元素，哪個(gè)操作更復(fù)雜？A.表頭插入B.表尾插入C.復(fù)雜度相同D.取決于鏈表長(zhǎng)度5、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的線性表中，若要?jiǎng)h除第i個(gè)元素（1<=i<=n），需要找到其前驅(qū)節(jié)點(diǎn)的時(shí)間復(fù)雜度為？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)6、若要對(duì)一棵二叉排序樹進(jìn)行中序遍歷，得到的序列是一個(gè)有序序列，這是因?yàn)槎媾判驑涞亩x具有什么特性？（）A.左子樹的值小于根節(jié)點(diǎn)，右子樹的值大于根節(jié)點(diǎn)B.左子樹和右子樹的深度相同C.每個(gè)節(jié)點(diǎn)的值都不同D.以上都不是7、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的棧中，若棧頂指針為top，要判斷棧是否為空，應(yīng)判斷？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL8、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無(wú)向圖中，使用Prim算法生成最小生成樹。若采用鄰接矩陣存儲(chǔ)圖，以下關(guān)于算法的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)9、在一個(gè)用鏈表實(shí)現(xiàn)的隊(duì)列中，若要?jiǎng)h除隊(duì)頭元素并返回其值，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、在一個(gè)字符串匹配算法中，BM算法相對(duì)于樸素的字符串匹配算法，其優(yōu)勢(shì)在于？（）A.平均性能更好B.代碼更簡(jiǎn)潔C.空間復(fù)雜度更低D.適用于短字符串匹配11、在一棵平衡二叉樹中，插入一個(gè)新結(jié)點(diǎn)后，可能需要進(jìn)行的調(diào)整操作是：A.左旋B.右旋C.左旋和右旋D.不需要調(diào)整12、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的最長(zhǎng)公共子序列問(wèn)題？A.二維數(shù)組B.棧C.隊(duì)列D.樹13、以下哪種數(shù)據(jù)結(jié)構(gòu)在處理頻繁的插入和刪除操作時(shí)，不需要移動(dòng)大量元素？（）A.數(shù)組B.鏈表C.棧D.隊(duì)列14、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹中，若底層從左到右第x個(gè)節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則x的取值范圍是（）A.[2^(h-1),2^h-1]B.[2^(h-2),2^(h-1)-1]C.[2^(h-1)-1,2^h-2]D.[2^(h-2)-1,2^(h-1)-1]15、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹中，若節(jié)點(diǎn)編號(hào)從1開始，對(duì)于編號(hào)為i的節(jié)點(diǎn)，其雙親節(jié)點(diǎn)的編號(hào)是多少？A.i/2B.(i-1)/2C.(i+1)/2D.以上都不對(duì)16、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的線索二叉樹，若n個(gè)節(jié)點(diǎn)中有m個(gè)空指針域，則線索的數(shù)量為？A.mB.m/2C.n+1D.n-117、對(duì)于單鏈表，若要訪問(wèn)鏈表中的第i個(gè)元素，必須從鏈表的頭指針開始依次遍歷，平均時(shí)間復(fù)雜度為O(n)。那么如果要在鏈表的末尾添加一個(gè)新元素，時(shí)間復(fù)雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)18、在一個(gè)順序存儲(chǔ)的棧中，若棧頂指針top為-1，則表示棧（）A.已滿B.為空C.已損壞D.無(wú)法確定19、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無(wú)向圖，使用克魯斯卡爾算法構(gòu)造最小生成樹時(shí)，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個(gè)連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對(duì)20、在一棵二叉搜索樹中，刪除一個(gè)只有左子樹的節(jié)點(diǎn)，其右子樹的節(jié)點(diǎn)需要（）A.替換被刪除節(jié)點(diǎn)B.保持不動(dòng)C.全部刪除D.移動(dòng)到左子樹二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）比較計(jì)數(shù)排序和冒泡排序在處理大量重復(fù)數(shù)據(jù)時(shí)的效率。2、（本題10分）詳細(xì)說(shuō)明如何使用基數(shù)排序?qū)φ麛?shù)或字符串進(jìn)行排序，分析其原理和時(shí)間復(fù)雜度。3、（本題10分）論述如何使用堆優(yōu)化迪杰斯特拉算法求解單源最短路徑問(wèn)題的性能。4、（本題10分）詳細(xì)說(shuō)明如何在一個(gè)無(wú)向圖中判斷是否為二部圖，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度。三、設(shè)