裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)鄭州西亞斯學(xué)院《數(shù)據(jù)結(jié)構(gòu)》

2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向完全圖，其弧的條數(shù)為（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/22、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時(shí)間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(n^3)3、若要從一個(gè)具有n個(gè)元素的有序單鏈表中刪除所有值重復(fù)的元素，使得鏈表中每個(gè)元素的值都不同，最優(yōu)的算法時(shí)間復(fù)雜度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)4、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向連通圖，其生成樹中邊的條數(shù)為（）。A.nB.n-1C.eD.e-15、在一個(gè)具有n個(gè)元素的鏈表中，若要在表頭插入一個(gè)新元素，平均需要修改幾個(gè)指針？（）A.1B.2C.nD.n+16、在一個(gè)具有n個(gè)元素的線性表中，采用順序查找法查找一個(gè)特定元素，若查找成功，平均查找長(zhǎng)度為？（）A.(n+1)/2B.n/2C.lognD.n7、在一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通圖中，至少有多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)8、圖的存儲(chǔ)方式有鄰接矩陣和鄰接表兩種，以下關(guān)于它們的特點(diǎn)的說(shuō)法中，錯(cuò)誤的是？（）A.鄰接矩陣適合存儲(chǔ)稠密圖，空間復(fù)雜度為O(n^2)。B.鄰接表適合存儲(chǔ)稀疏圖，空間復(fù)雜度為O(n+m)，其中n是頂點(diǎn)數(shù)，m是邊數(shù)。C.鄰接矩陣的查找邊的時(shí)間復(fù)雜度為O(1)。D.鄰接表的插入邊和刪除邊的時(shí)間復(fù)雜度為O(n)。9、在一個(gè)用十字鏈表存儲(chǔ)的有向圖中，查找一個(gè)頂點(diǎn)的所有出邊和入邊的時(shí)間復(fù)雜度是？（）A.O(1)B.O(n)C.O(e)D.O(n+e)10、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹中，若底層從左到右第x個(gè)節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則x的取值范圍是（）A.[2^(h-1),2^h-1]B.[2^(h-2),2^(h-1)-1]C.[2^(h-1)-1,2^h-2]D.[2^(h-2)-1,2^(h-1)-1]11、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖，采用鄰接表存儲(chǔ)，進(jìn)行深度優(yōu)先遍歷。以下關(guān)于遍歷的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)模緼.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)12、在一個(gè)哈希表中，解決沖突的方法不包括：A.開放定址法B.再哈希法C.建立索引表D.鏈地址法13、設(shè)有一個(gè)帶權(quán)有向圖G=(V,E)，采用拓?fù)渑判蛩惴▽?duì)其進(jìn)行排序，若得到的拓?fù)湫蛄形ㄒ?，則圖G一定是？（）A.有環(huán)圖B.無(wú)環(huán)圖C.強(qiáng)連通圖D.弱連通圖14、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)滿的條件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front15、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的AVL樹，插入一個(gè)新節(jié)點(diǎn)后，調(diào)整樹的平衡，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、對(duì)于一個(gè)棧，進(jìn)行入棧和出棧操作時(shí)，以下哪種情況會(huì)導(dǎo)致棧溢出？A.入棧元素過(guò)多B.出棧元素過(guò)多C.連續(xù)進(jìn)行入棧操作且存儲(chǔ)空間已滿D.連續(xù)進(jìn)行出棧操作且棧為空17、設(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)系18、隊(duì)列也是一種常見的數(shù)據(jù)結(jié)構(gòu)，遵循先進(jìn)先出的原則。對(duì)于一個(gè)循環(huán)隊(duì)列，以下說(shuō)法不正確的是（）A.隊(duì)頭指針和隊(duì)尾指針的移動(dòng)需要考慮循環(huán)的情況B.當(dāng)隊(duì)頭指針等于隊(duì)尾指針時(shí)，隊(duì)列為空C.可以通過(guò)犧牲一個(gè)存儲(chǔ)單元來(lái)區(qū)分隊(duì)列空和隊(duì)列滿的情況D.循環(huán)隊(duì)列可以避免假溢出的問題19、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的廣度優(yōu)先遍歷的輔助隊(duì)列？A.循環(huán)隊(duì)列B.鏈隊(duì)列C.優(yōu)先隊(duì)列D.雙端隊(duì)列20、以下關(guān)于堆的描述，正確的是：A.大頂堆中每個(gè)父節(jié)點(diǎn)的值都大于其子節(jié)點(diǎn)的值B.小頂堆中每個(gè)父節(jié)點(diǎn)的值都小于其子節(jié)點(diǎn)的值C.堆可以用順序存儲(chǔ)也可以用鏈?zhǔn)酱鎯?chǔ)D.堆是完全二叉樹二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述在二叉樹的遍歷中，如何利用線索二叉樹優(yōu)化遍歷效率。2、（本題10分）詳細(xì)解釋在二叉搜索樹中進(jìn)行查找操作的過(guò)程，以及如何保證查找效率的優(yōu)化。3、（本題10分）解釋圖的哈密頓回路和哈密頓路徑是什么，以及如何判斷一個(gè)圖是否存在哈密頓回路或哈密頓路徑。4、（本題10分）在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉搜索樹中，如何查找第k小的元素，給出算法思路