邢臺學(xué)院《數(shù)據(jù)結(jié)構(gòu)實驗》2021-2022學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁邢臺學(xué)院《數(shù)據(jù)結(jié)構(gòu)實驗》

2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下關(guān)于拓?fù)渑判虻拿枋?，正確的是：A.拓?fù)渑判虻慕Y(jié)果是唯一的B.一個有環(huán)的圖也可以進(jìn)行拓?fù)渑判駽.拓?fù)渑判蚩梢杂糜谂袛嘁粋€圖是否有環(huán)D.拓?fù)渑判蛑荒苡糜谟邢驁D2、對于一個具有n個頂點的無向圖，若其所有頂點的度之和為20，則該圖的邊數(shù)為（）。A.5B.10C.15D.203、設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5依次入棧，出棧序列不可能是？（）A.54321B.21543C.21345D.154324、對于一個具有n個元素的順序存儲的循環(huán)隊列，隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，若隊列非空，則隊列中元素的個數(shù)為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+15、隊列也是一種線性表，遵循先進(jìn)先出原則。在一個循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，那么判斷隊列為空的條件是什么？A.front==rearB.(rear+1)%MAXSIZE==frontC.front==(rear+1)%MAXSIZED.以上都不對6、對于一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲，若要刪除一條邊，平均需要修改多少個指針？（）A.1B.2C.eD.2e7、對于一個具有n個元素的歸并排序，其時間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)8、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)。在處理哈希沖突時，常用的方法有開放地址法和鏈地址法。以下關(guān)于這兩種方法的描述，哪一項是不準(zhǔn)確的？A.開放地址法會增加查找時間B.鏈地址法需要額外的指針空間C.開放地址法容易產(chǎn)生聚集現(xiàn)象D.鏈地址法的沖突解決更復(fù)雜9、在一個字符串中，要查找某個子串首次出現(xiàn)的位置，通常可以使用哪種算法？（）A.冒泡排序B.快速排序C.順序查找D.二分查找10、在一個用鏈表實現(xiàn)的隊列中，若要實現(xiàn)隊列的遍歷操作，以下哪種方式較為合適？A.從隊頭開始，依次訪問每個節(jié)點B.從隊尾開始，依次向前訪問每個節(jié)點C.隨機訪問鏈表中的節(jié)點D.以上都不對11、若對一棵二叉搜索樹進(jìn)行先序遍歷，得到的節(jié)點序列是一個遞減序列，則該二叉搜索樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空12、若要對一個具有n個元素的無序數(shù)組進(jìn)行排序，以下哪種排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序13、在一棵度為4的樹中，度為4的節(jié)點個數(shù)為1，度為3的節(jié)點個數(shù)為2，度為2的節(jié)點個數(shù)為3，度為1的節(jié)點個數(shù)為4，葉子節(jié)點個數(shù)為（）。A.15B.16C.17D.1814、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實現(xiàn)集合的交集運算，并具有較低的時間復(fù)雜度？A.鏈表B.二叉搜索樹C.哈希表D.并查集15、以下關(guān)于線索二叉樹的描述，錯誤的是：A.線索二叉樹便于在中序遍歷中查找前驅(qū)和后繼節(jié)點B.線索二叉樹中的線索是指向空指針的指針C.線索二叉樹的存儲空間利用率比普通二叉樹高D.線索二叉樹的構(gòu)建過程非常簡單，不需要復(fù)雜的算法16、對于一個具有n個頂點和e條邊的帶權(quán)無向圖，使用克魯斯卡爾算法構(gòu)造最小生成樹時，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對17、在數(shù)據(jù)結(jié)構(gòu)中，哈希表的負(fù)載因子對性能有很大影響。以下關(guān)于負(fù)載因子的描述，不正確的是（）A.負(fù)載因子越大，哈希沖突的可能性越大B.負(fù)載因子越小，存儲空間利用率越高C.負(fù)載因子通常在0.5到1之間D.可以通過調(diào)整負(fù)載因子來優(yōu)化哈希表性能18、在數(shù)據(jù)結(jié)構(gòu)中，鏈表的反轉(zhuǎn)是一個常見的操作，以下關(guān)于鏈表反轉(zhuǎn)的實現(xiàn)方法，錯誤的是（）A.使用三個指針依次遍歷并調(diào)整節(jié)點的鏈接關(guān)系B.遞歸方式實現(xiàn)時不需要額外的輔助空間C.迭代方式的時間復(fù)雜度為O(n)D.遞歸方式的空間復(fù)雜度比迭代方式低19、設(shè)有一個棧，元素進(jìn)棧的次序為A、B、C、D、E，下列不可能的出棧序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE20、已知一個哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測法處理沖突。若依次插入關(guān)鍵字31、25、19、49、37、21、13、17，則在查找關(guān)鍵字19時需要進(jìn)行幾次比較？（）A.1B.2C.3D.4二、簡答題（本大題共4個小題，共40分)1、（本題10分）說明堆的概念和性質(zhì)，闡述最大堆和最小堆的構(gòu)建、插入和刪除操作的過程，并分析其時間復(fù)雜度。2、（本題10分）詳細(xì)闡述在具有n個頂點的有向圖中，如何判斷圖是否存在歐拉回路，并給出具體的算法思想和實現(xiàn)步驟。3、（本題10分）解釋圖的連通性問題的高級算法，如Tarjan算法、Kosaraju算法等的原理及應(yīng)用場景。4、（本題10分）分析