江蘇海洋大學《數(shù)據(jù)結(jié)構(gòu)B》2021-2022學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁江蘇海洋大學《數(shù)據(jù)結(jié)構(gòu)B》

2021-2022學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個節(jié)點的二叉樹中，若采用后序遍歷得到的節(jié)點序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定2、對于一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲時，其空間復雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)3、在一個具有n個頂點的連通圖中，生成樹的邊數(shù)一定為？（）A.n-1B.nC.n+1D.2n4、以下關(guān)于紅黑樹的性質(zhì)，錯誤的是：A.每個節(jié)點要么是紅色，要么是黑色B.根節(jié)點是黑色的C.每個葉子節(jié)點（NIL節(jié)點）是黑色的D.紅色節(jié)點的子節(jié)點一定是紅色的5、已知一個圖的鄰接矩陣如下所示，則從頂點V1出發(fā)進行深度優(yōu)先遍歷，可能得到的頂點訪問序列是（）。|01100||10010||10001||01000||00100|A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V5,V3,V4D.V1,V4,V3,V2,V56、設(shè)有一個具有n個節(jié)點的二叉搜索樹，若要查找一個值大于給定值的最小節(jié)點，以下關(guān)于查找操作的時間復雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、在一個具有n個元素的順序表中，在第i個元素（1<=i<=n）之前插入一個新元素時，需要向后移動的元素個數(shù)為：A.n-iB.iC.n-i+1D.n-i-18、一棵哈夫曼樹中，葉子節(jié)點的編碼長度一定（）非葉子節(jié)點的編碼長度。A.大于B.等于C.小于D.不小于9、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)LRU（最近最少使用）頁面置換算法？A.隊列B.棧C.哈希表D.雙鏈表10、在一個具有n個節(jié)點的二叉排序樹中，進行查找操作的平均時間復雜度是多少？A.O(n)B.O(logn)C.O(nlogn)D.取決于樹的形態(tài)11、圖的存儲方式和遍歷方式可以用于解決很多實際問題，以下關(guān)于它們的應(yīng)用的說法中，錯誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等。B.圖的鄰接表可以用于表示稀疏圖，如地圖、電路圖等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問題和最小生成樹問題等。D.圖的存儲方式和遍歷方式只適用于理論研究，在實際應(yīng)用中沒有實際價值。12、在數(shù)據(jù)結(jié)構(gòu)中，優(yōu)先隊列可以用堆來實現(xiàn)，以下關(guān)于堆調(diào)整的描述，錯誤的是（）A.插入元素時，從下往上調(diào)整堆B.刪除堆頂元素時，從上往下調(diào)整堆C.調(diào)整堆的過程中，節(jié)點的值可能會交換D.調(diào)整堆的時間復雜度與堆的大小無關(guān)13、已知一個圖的鄰接表如下所示，則從頂點V1出發(fā)進行廣度優(yōu)先遍歷，可能得到的頂點訪問序列是（）。V1:->V2->V3V2:->V4V3:->V4->V5V4:->V5V5:A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V4,V3,V5D.V1,V4,V2,V3,V514、若要在一個具有n個元素的有序數(shù)組中插入一個新元素，同時保持數(shù)組有序，平均需要移動多少個元素？（）A.n/2B.nC.lognD.115、若要對n個元素進行快速排序，在最壞情況下，其時間復雜度為？（）A.O(n)B.O(log?n)C.O(nlog?n)D.O(n2)16、在一個B樹中，每個節(jié)點的關(guān)鍵字數(shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-117、以下關(guān)于圖的存儲結(jié)構(gòu)的描述，哪一項是正確的？（）A.鄰接矩陣適合存儲稀疏圖B.鄰接表在存儲稠密圖時空間效率較高C.十字鏈表適合存儲有向圖D.以上都不正確18、在一個鏈式存儲的線性表中，若要刪除第i個元素（1<=i<=n），需要找到其前驅(qū)節(jié)點的時間復雜度為？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)19、以下關(guān)于二叉排序樹的描述，錯誤的是：A.左子樹上所有結(jié)點的值均小于根結(jié)點的值B.右子樹上所有結(jié)點的值均大于根結(jié)點的值C.中序遍歷二叉排序樹可得到一個有序序列D.二叉排序樹的查找效率總是最高的20、在一個鏈式存儲的隊列中，若隊頭指針為front，隊尾指針為rear，當進行一次出隊操作后，front指針應(yīng)該如何移動？A.front=front->nextB.front=rearC.front不變D.front=NULL二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細闡述圖的拓撲排序的概念和應(yīng)用場景，給出拓撲排序的算法步驟，并分析其時間復雜度。2、（本題10分）鏈表的循環(huán)鏈表有哪些特點和應(yīng)用場景？如何判斷一個鏈表是否為循環(huán)鏈表？3、（本題10分）深入探討在一個具有n個元素的二叉搜索樹中，如何進行樹的遍歷操作的應(yīng)用，如計算樹中節(jié)點值的和。4、（本題10分）在圖的