邢臺學院《數據結構實踐》2021-2022學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁邢臺學院

《數據結構實踐》2021-2022學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個元素的順序存儲的循環(huán)隊列，隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，若隊列非空，則隊列中元素的個數為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+12、二叉樹是一種重要的數據結構，具有多種遍歷方式。對于先序遍歷、中序遍歷和后序遍歷，以下描述錯誤的是（）A.先序遍歷先訪問根節(jié)點，然后遞歸遍歷左子樹和右子樹B.中序遍歷先遞歸遍歷左子樹，然后訪問根節(jié)點，最后遞歸遍歷右子樹C.后序遍歷先遞歸遍歷左子樹和右子樹，最后訪問根節(jié)點D.這三種遍歷方式的結果總是相同的3、對于一個具有n個節(jié)點的二叉樹，若度為0的節(jié)點有n0個，度為1的節(jié)點有n1個，度為2的節(jié)點有n2個，則n0與n1、n2之間的關系為？A.n0=n1+n2B.n0=n2-1C.n0=n1-1D.n0=n2+14、在一個具有n個節(jié)點的無向圖中，若要判斷兩個節(jié)點之間是否存在路徑，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.普里姆算法D.克魯斯卡爾算法5、在一個帶頭結點的雙向鏈表中，若要在p所指結點之后插入一個新結點q，需要修改幾個指針？（）A.2B.4C.6D.86、若對一棵二叉排序樹進行中序遍歷，得到的節(jié)點序列是一個遞增序列，則該二叉排序樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空7、在循環(huán)鏈表中，尾指針rear指向鏈表的尾節(jié)點，若要在鏈表中插入一個新的節(jié)點，使其成為新的尾節(jié)點，以下操作正確的是？（）A.rear->next=new_node;new_node->next=rear;rear=new_node;B.new_node->next=rear;rear->next=new_node;rear=new_node;C.rear=new_node;new_node->next=rear->next;rear->next=new_node;D.new_node->next=rear->next;rear->next=new_node;8、在一個具有n個元素的順序表中，若要刪除第i個元素（1<=i<=n），并將后面的元素向前移動，平均需要移動多少個元素？（）A.n-iB.iC.(n-i)/2D.n-i+19、對于一個具有n個元素的哈希表，負載因子越大，發(fā)生沖突的可能性如何變化？（）A.越大B.越小C.不變D.不確定10、在一個哈希表中，解決沖突的方法不包括：A.開放定址法B.再哈希法C.建立索引表D.鏈地址法11、在圖的最短路徑算法中，Dijkstra算法適用于帶權有向圖，以下關于Dijkstra算法的描述，錯誤的是（）A.以起始節(jié)點為中心向外層層擴展B.每次選擇距離起始節(jié)點最近的未訪問節(jié)點C.可以處理負權邊D.時間復雜度為O(n^2)12、在數據結構的應用中，優(yōu)先隊列常用于實現任務調度，以下關于優(yōu)先隊列的描述，錯誤的是（）A.可以使用堆來實現B.元素的出隊順序按照優(yōu)先級確定C.插入元素的時間復雜度為O(logn)D.不支持修改元素的優(yōu)先級13、在一個鏈式存儲的隊列中，進行入隊和出隊操作時，指針的移動方向分別是（）A.入隊向前，出隊向后B.入隊向后，出隊向前C.均向前D.均向后14、在一個帶頭結點的單鏈表中，若要刪除表中所有值為x的結點，最優(yōu)的算法時間復雜度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)15、在一個具有n個元素的小頂堆中，若將堆頂元素與最后一個元素交換，然后對堆進行調整，其時間復雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)16、對于一個具有n個頂點和e條邊的帶權無向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時間復雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)17、圖是一種復雜的數據結構，若要表示一個有向圖，通?？梢允褂媚姆N存儲結構？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.以上均可18、在一個具有n個元素的堆中，查找最大元素的時間復雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)19、在一個哈希表中，解決沖突的方法通常有開放定址法和鏈地址法。如果要保證查找的平均時間復雜度較低，應該優(yōu)先選擇哪種方法？（）A.開放定址法B.鏈地址法C.兩者效果相同D.取決于哈希函數20、設棧的初始狀態(tài)為空，元素1、2、3、4、5依次入棧，出棧序列不可能是？（）A.54321B.21543C.21345D.15432二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋圖的連通性問題的其他變體，如強連通分量的數量、弱連通分量的合并等問題及解決方法。2、（本題10分）分析在數據結構中，如何利用堆進行中位數的查找。3、（本題10分）詳細說明在字符串匹配的多模式匹配中，如AC自動機，如何實現高效的匹配。4、（本題10分）論述在選擇排序中，每一輪選擇最小元素的過程以及其時間復雜度