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

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

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