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

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記。…………密………………封………………線…………第1頁，共1頁蘇州大學(xué)《數(shù)據(jù)結(jié)構(gòu)及實驗》

2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個用數(shù)組實現(xiàn)的循環(huán)隊列中，若front=rear，則隊列的狀態(tài)可能為（）A.隊空B.隊滿C.既不空也不滿D.以上都有可能2、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)表達式求值？A.二叉樹B.棧C.隊列D.哈希表3、平衡二叉樹是一種特殊的二叉搜索樹，其目的是為了保證查找效率。以下哪種操作可能會導(dǎo)致平衡二叉樹失去平衡？A.插入節(jié)點B.刪除節(jié)點C.查找節(jié)點D.以上都可能4、在數(shù)據(jù)結(jié)構(gòu)中，紅黑樹的插入操作可能會導(dǎo)致樹的不平衡，需要進行調(diào)整。以下關(guān)于調(diào)整過程的描述，不正確的是（）A.可能需要進行顏色修改和旋轉(zhuǎn)操作B.調(diào)整后的紅黑樹仍然滿足紅黑樹的性質(zhì)C.調(diào)整的目的是使樹的高度盡量降低D.每次插入操作都需要進行多次調(diào)整5、若一棵二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹的后序遍歷序列為？（）A.BCAB.CBAC.ABCD.ACB6、在一個具有n個節(jié)點的完全二叉樹中，若底層從左到右依次編號，節(jié)點i的左孩子節(jié)點編號是多少（假設(shè)根節(jié)點編號為1）？A.2iB.2i+1C.i*2D.以上都不對7、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)字典操作，并且能夠快速查找、插入和刪除元素？（）A.棧B.隊列C.二叉搜索樹D.數(shù)組8、在一個具有n個頂點的有向無環(huán)圖中，使用拓?fù)渑判蛩惴ǎ浣Y(jié)果的唯一性如何？A.一定唯一B.可能不唯一C.取決于頂點的編號D.以上都不對9、一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲，其空間復(fù)雜度為？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)10、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，具有多種遍歷方式。對于先序遍歷、中序遍歷和后序遍歷，以下描述錯誤的是（）A.先序遍歷先訪問根節(jié)點，然后遞歸遍歷左子樹和右子樹B.中序遍歷先遞歸遍歷左子樹，然后訪問根節(jié)點，最后遞歸遍歷右子樹C.后序遍歷先遞歸遍歷左子樹和右子樹，最后訪問根節(jié)點D.這三種遍歷方式的結(jié)果總是相同的11、在一個具有n個元素的循環(huán)隊列中，若隊頭指針為front，隊尾指針為rear，且rear<front，則隊列中的元素個數(shù)為？A.rear-frontB.front-rearC.(rear-front+n)%nD.(front-rear+n)%n12、設(shè)有一個帶頭結(jié)點的單鏈表，頭指針為head，若要在第一個元素之前插入一個新元素，則需要執(zhí)行的操作是（）。A.s->next=head;head=s;B.s->next=head->next;head->next=s;C.head->next=s;s->next=head;D.s->next=head;s=head;13、一棵完全二叉樹的第5層（根為第1層）有16個葉子節(jié)點，則該完全二叉樹的節(jié)點總數(shù)最少為（）。A.47B.55C.63D.6414、對于一個具有n個節(jié)點的二叉樹，若每個節(jié)點都有左子樹和右子樹，則其葉子節(jié)點的個數(shù)至少為？A.n/2B.(n+1)/2C.n-1D.logn15、在一個具有n個元素的順序存儲的線性表中，刪除第i個元素（1<=i<=n），需要移動多少個元素？（）A.n-iB.iC.n-i+1D.n-i-116、在一棵二叉搜索樹中，刪除一個有兩個子節(jié)點的節(jié)點時，通常采用的方法是：A.用左子樹的最大值替代該節(jié)點B.用右子樹的最小值替代該節(jié)點C.隨機選擇左子樹或右子樹的節(jié)點替代D.不進行替代，直接刪除17、在一個容量為10的順序存儲的循環(huán)隊列中，若front=4，rear=8，則此時隊列中元素的個數(shù)為：A.4B.5C.6D.718、在一個具有n個元素的順序表中，若要刪除第i個元素（1<=i<=n），并將后面的元素向前移動，平均需要移動多少個元素？（）A.n-iB.iC.(n-i)/2D.n-i+119、一棵二叉樹的先序遍歷序列為ABDECFGH，中序遍歷序列為DBEAFCGH，則該二叉樹的后序遍歷序列為（）。A.DEBFGCHAB.DEBFHGCAC.DEBHGFCAD.DEBHFCGA20、在一個具有n個頂點和m條邊的有向圖中，使用弗洛伊德算法求所有頂點對之間的最短路徑，其時間復(fù)雜度為？A.O(n^2)B.O(n^3)C.O(mn)D.O(m^2)二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細闡述桶排序在處理大規(guī)模數(shù)據(jù)時的優(yōu)化策略。2、（本題10分）闡述后綴樹在圖像處理中的潛在應(yīng)用和相關(guān)技術(shù)。3、（本題10分）解釋如何在一個鏈表中實現(xiàn)插入排序的優(yōu)化，給出算法步驟和實現(xiàn)代碼，并分析其性能改進。4、（本題10分）數(shù)組的切片操作在不同編程語言中的實現(xiàn)方式有哪些