貴州工程應(yīng)用技術(shù)學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》2021-2022學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁貴州工程應(yīng)用技術(shù)學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》

2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)。對于一個(gè)滿二叉樹，若其高度為h，則節(jié)點(diǎn)總數(shù)為多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-12、以下關(guān)于平衡二叉樹旋轉(zhuǎn)調(diào)整的描述，正確的是：A.旋轉(zhuǎn)調(diào)整一定會(huì)改變樹的中序遍歷結(jié)果B.左旋操作是將右子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)樽笞庸?jié)點(diǎn)C.右旋操作是將左子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)橛易庸?jié)點(diǎn)D.平衡二叉樹不需要進(jìn)行旋轉(zhuǎn)調(diào)整3、對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣存儲(chǔ)，則存儲(chǔ)空間的復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)4、設(shè)有一個(gè)廣義表L=((a,b),c,(d,e))，其表頭和表尾分別為？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)5、在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用順序查找算法查找一個(gè)特定元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.nlogn6、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向連通圖，利用Prim算法構(gòu)造最小生成樹時(shí)，其時(shí)間復(fù)雜度為：A.O(n^2)B.O(elogn)C.O(nlogn)D.O(e^2)7、已知一個(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,V58、在一個(gè)具有n個(gè)元素的線性表中，采用順序查找法查找一個(gè)特定元素，若查找成功，平均查找長度為？（）A.(n+1)/2B.n/2C.lognD.n9、若對一棵二叉排序樹進(jìn)行中序遍歷，得到的節(jié)點(diǎn)序列是一個(gè)遞增序列，則該二叉排序樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空10、在一個(gè)用鄰接矩陣存儲(chǔ)的圖中，若要判斷兩個(gè)節(jié)點(diǎn)是否相鄰，時(shí)間復(fù)雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)11、在一個(gè)哈希表中，解決沖突的方法通常有開放定址法和鏈地址法。如果要保證查找的平均時(shí)間復(fù)雜度較低，應(yīng)該優(yōu)先選擇哪種方法？（）A.開放定址法B.鏈地址法C.兩者效果相同D.取決于哈希函數(shù)12、已知一個(gè)完全二叉樹的節(jié)點(diǎn)總數(shù)為100，其葉子節(jié)點(diǎn)的個(gè)數(shù)為（）。A.49B.50C.51D.不確定13、在一個(gè)具有n個(gè)元素的小根堆中，最小元素的值位于（）。A.根節(jié)點(diǎn)B.任意節(jié)點(diǎn)C.葉子節(jié)點(diǎn)D.無法確定14、棧是一種特殊的線性表，其操作遵循后進(jìn)先出原則。若一個(gè)棧的初始狀態(tài)為空，現(xiàn)在依次將元素1、2、3、4、5入棧，然后再依次出棧，那么出棧的順序是什么？（）A.12345B.54321C.32154D.2154315、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，若每個(gè)節(jié)點(diǎn)都有左右子樹，則該二叉樹的葉子節(jié)點(diǎn)數(shù)量與度為2的節(jié)點(diǎn)數(shù)量之間存在特定關(guān)系。以下關(guān)于這種關(guān)系的描述，哪一項(xiàng)是正確的？A.葉子節(jié)點(diǎn)數(shù)量等于度為2的節(jié)點(diǎn)數(shù)量B.葉子節(jié)點(diǎn)數(shù)量比度為2的節(jié)點(diǎn)數(shù)量多1C.葉子節(jié)點(diǎn)數(shù)量比度為2的節(jié)點(diǎn)數(shù)量少1D.兩者之間沒有固定關(guān)系16、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)滿的條件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front17、在一個(gè)具有n個(gè)元素的順序表中，在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)的元素個(gè)數(shù)為：A.n-iB.iC.n-i+1D.n-i-118、在一個(gè)具有n個(gè)元素的循環(huán)隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，且rear<front，則隊(duì)列中的元素個(gè)數(shù)為？A.rear-frontB.front-rearC.(rear-front+n)%nD.(front-rear+n)%n19、已知一個(gè)帶權(quán)有向圖G=(V,E)，頂點(diǎn)集合V={1,2,3,4,5}，邊集合E={(1,2,5),(1,3,3),(2,4,2),(3,4,6),(3,5,4),(4,5,1)}，采用迪杰斯特拉（Dijkstra）算法求從頂點(diǎn)1到頂點(diǎn)5的最短路徑，經(jīng)過的中間頂點(diǎn)依次為？（）A.2,4B.3,4C.2,3D.3,520、對于一個(gè)具有n個(gè)頂點(diǎn)的連通圖，其生成樹中邊的數(shù)量為：A.n-1B.nC.n+1D.不確定二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）深入探討在有向圖和無向圖中，如何判斷圖是否連通，以及求連通分量的方法。2、（本題10分）闡述如何在一個(gè)具有n個(gè)元素的雙向鏈表中，進(jìn)行查找操作，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題10分）詳細(xì)說明隊(duì)列的特點(diǎn)和基本操作，闡述循環(huán)隊(duì)列是如何解決順序隊(duì)列中“假溢出”問題的，并給出循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷條件。4、（本題10分）詳細(xì)闡述在堆的應(yīng)用中，如何使用堆實(shí)現(xiàn)優(yōu)先級隊(duì)列，