河北地質(zhì)大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線(xiàn)第1頁(yè)，共3頁(yè)河北地質(zhì)大學(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、設(shè)有一個(gè)用鏈表實(shí)現(xiàn)的雙向循環(huán)鏈表，若要在其中一個(gè)節(jié)點(diǎn)之后插入一個(gè)新節(jié)點(diǎn)，以下關(guān)于插入操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)2、在一個(gè)用鏈表實(shí)現(xiàn)的隊(duì)列中，若要?jiǎng)h除隊(duì)頭元素并返回其值，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、在一個(gè)棧中，若入棧序列為1,2,3,4，且在入棧過(guò)程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.174、在一個(gè)具有n個(gè)元素的數(shù)組中，進(jìn)行順序查找，若查找成功，平均比較次數(shù)約為？A.n/2B.nC.lognD.15、在一個(gè)采用順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表中，若要在第i個(gè)位置插入一個(gè)新元素，需要將第i個(gè)位置及之后的元素依次向后移動(dòng)一位。以下關(guān)于插入操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.時(shí)間復(fù)雜度為O(1)B.時(shí)間復(fù)雜度為O(n)C.時(shí)間復(fù)雜度為O(logn)D.時(shí)間復(fù)雜度為O(nlogn)6、若對(duì)一棵二叉排序樹(shù)進(jìn)行中序遍歷，得到的節(jié)點(diǎn)序列是一個(gè)遞增序列，則該二叉排序樹(shù)（）。A.沒(méi)有左子樹(shù)B.沒(méi)有右子樹(shù)C.左子樹(shù)均為空D.右子樹(shù)均為空7、在一個(gè)用鄰接矩陣存儲(chǔ)的無(wú)向圖中，若要?jiǎng)h除一條邊，需要修改矩陣中的幾個(gè)元素？A.1個(gè)B.2個(gè)C.3個(gè)D.4個(gè)8、在一個(gè)具有n個(gè)元素的大頂堆中，若要將堆頂元素與最后一個(gè)元素交換，然后調(diào)整堆，其時(shí)間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)9、已知一個(gè)有序表為{12,25,30,45,50,60,70,80}，若采用折半查找法查找值為45的元素，需要比較多少次？（）A.1B.2C.3D.410、以下哪種排序算法在元素基本有序的情況下性能最佳？A.快速排序B.冒泡排序C.插入排序D.堆排序11、在一個(gè)具有n個(gè)元素的順序表中，要在中間位置插入一個(gè)新元素，平均移動(dòng)元素的個(gè)數(shù)約為？A.n/2B.nC.lognD.112、在一個(gè)具有n個(gè)元素的無(wú)序數(shù)組中，使用選擇排序進(jìn)行排序，其空間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)13、在一個(gè)具有n個(gè)元素的順序表中，若要在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素，需要移動(dòng)的元素個(gè)數(shù)為？（）A.n-iB.iC.n-i+1D.n-i-114、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)中，若底層從左到右依次編號(hào)，節(jié)點(diǎn)i的左孩子節(jié)點(diǎn)編號(hào)是多少（假設(shè)根節(jié)點(diǎn)編號(hào)為1）？A.2iB.2i+1C.i*2D.以上都不對(duì)15、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的線(xiàn)性表中，要在第i個(gè)位置插入一個(gè)新元素（1<=i<=n+1），需要移動(dòng)的元素個(gè)數(shù)約為？A.n-iB.iC.n-i+1D.n-i-116、對(duì)于一棵二叉搜索樹(shù)，進(jìn)行中序遍歷得到的序列是一個(gè)有序序列。若對(duì)其進(jìn)行刪除操作，以下關(guān)于時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.平均時(shí)間復(fù)雜度為O(logn)，最壞情況為O(n)B.時(shí)間復(fù)雜度始終為O(logn)C.平均時(shí)間復(fù)雜度為O(n)，最壞情況為O(nlogn)D.時(shí)間復(fù)雜度始終為O(n)17、在一個(gè)具有n個(gè)節(jié)點(diǎn)的圖中，若要找出所有的連通分量，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.并查集D.以上都可以18、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列？（）A.二叉樹(shù)B.鏈表C.堆D.棧19、在一個(gè)哈希表中，解決沖突的方法不包括：A.開(kāi)放定址法B.再哈希法C.建立索引表D.鏈地址法20、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在有向圖中，頂點(diǎn)的入度是指指向該頂點(diǎn)的邊的數(shù)量。若要計(jì)算一個(gè)有向圖中所有頂點(diǎn)的入度，哪種算法較為合適？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓?fù)渑判駾.以上都可以二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述在數(shù)據(jù)結(jié)構(gòu)的實(shí)際應(yīng)用中，如何結(jié)合多種數(shù)據(jù)結(jié)構(gòu)解決復(fù)雜問(wèn)題，例如圖和樹(shù)的結(jié)合。2、（本題10分）闡述后綴樹(shù)在圖像處理中的潛在應(yīng)用和相關(guān)技術(shù)。3、（本題10分）解釋圖的最小生成樹(shù)問(wèn)題的變體，如帶權(quán)有向圖的最小生成樹(shù)問(wèn)題、次小生成樹(shù)問(wèn)題等。4、（本題10分）詳細(xì)說(shuō)明如何使用基數(shù)排序?qū)φ麛?shù)或字符串進(jìn)行排序，分析其原理和時(shí)間復(fù)雜度。三、設(shè)計(jì)題（本大題共2個(gè)小題，共