吉林大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)》2021-2022學(xué)年期末試卷

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

2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比較的次數(shù)是：A.1B.2C.3D.42、在一個具有n個節(jié)點(diǎn)的二叉樹中，若采用中序遍歷得到的節(jié)點(diǎn)序列是有序的，則該二叉樹可能是什么類型？A.滿二叉樹B.完全二叉樹C.二叉搜索樹D.以上都有可能3、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的高效存儲和操作？（）A.二叉樹B.哈希表C.字符數(shù)組D.鏈表4、數(shù)組通常具有的兩種基本操作是：A.插入和刪除B.查找和修改C.遍歷和排序D.索引和賦值5、對于一個具有n個頂點(diǎn)的無向連通圖，若要判斷其是否存在環(huán)，以下哪種算法的時間復(fù)雜度最低？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓?fù)渑判駾.以上算法時間復(fù)雜度相同6、對于一個具有n個元素的有序鏈表，進(jìn)行折半查找，其時間復(fù)雜度為？A.O(logn)B.O(nlogn)C.O(n)D.不能進(jìn)行折半查找7、以下哪種排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序8、設(shè)有一個帶權(quán)有向圖G=(V,E)，采用拓?fù)渑判蛩惴▽ζ溥M(jìn)行排序，若得到的拓?fù)湫蛄形ㄒ?，則圖G一定是？（）A.有環(huán)圖B.無環(huán)圖C.強(qiáng)連通圖D.弱連通圖9、在一個具有n個元素的無序數(shù)組中，使用選擇排序進(jìn)行排序。以下關(guān)于選擇排序的時間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)10、若對一棵二叉搜索樹進(jìn)行先序遍歷，得到的節(jié)點(diǎn)序列是一個遞減序列，則該二叉搜索樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空11、若對線性表的操作只有兩種，即插入和刪除，且以鏈表作為存儲結(jié)構(gòu)，則插入和刪除操作的時間復(fù)雜度分別為：A.O(n)和O(n)B.O(1)和O(1)C.O(n)和O(1)D.O(1)和O(n)12、隊(duì)列也是一種線性表，遵循先進(jìn)先出原則。在一個循環(huán)隊(duì)列中，隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAXSIZE，那么判斷隊(duì)列為空的條件是什么？A.front==rearB.(rear+1)%MAXSIZE==frontC.front==(rear+1)%MAXSIZED.以上都不對13、對于一個用鏈表表示的線性表，在表頭插入一個新元素和在表尾插入一個新元素，哪個操作更復(fù)雜？A.表頭插入B.表尾插入C.復(fù)雜度相同D.取決于鏈表長度14、對于一個用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列，若隊(duì)列已滿，此時front=10，rear=20，隊(duì)列的最大容量為50，那么下一個入隊(duì)元素應(yīng)該存儲在哪個位置？A.21B.0C.30D.無法確定15、對于一個具有n個頂點(diǎn)和e條邊的有向圖，其鄰接矩陣中非零元素的個數(shù)最多為？（）A.eB.2eC.n^2D.n(n-1)16、對于一個具有n個頂點(diǎn)的完全二叉樹，其葉子節(jié)點(diǎn)的數(shù)量為？（）A.n/2B.(n+1)/2C.n-1D.n17、在一個長度為n的有序數(shù)組中進(jìn)行二分查找，其時間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(logn)D.O(n2)18、設(shè)有一個棧S和一個隊(duì)列Q，初始時棧為空，隊(duì)列為{1,2,3,4,5}。經(jīng)過一系列入棧和出棧、入隊(duì)和出隊(duì)操作后，棧頂元素為3，此時隊(duì)列的頭元素為？（）A.1B.2C.4D.519、在一個具有n個頂點(diǎn)的無向圖中，若采用鄰接矩陣存儲，則存儲空間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)20、在一個哈希表中，若采用線性探測法解決哈希沖突，當(dāng)發(fā)生沖突時，新元素會存儲在什么位置？A.沖突位置的下一個位置B.沖突位置C.隨機(jī)位置D.以上都不對二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細(xì)闡述在利用哈希表存儲數(shù)據(jù)時，如何解決哈希沖突，以及如何提高哈希表的查找效率。2、（本題10分）什么是二叉搜索樹的插入操作的自平衡優(yōu)化方法？請舉例說明。3、（本題10分）闡述隊(duì)列在分布式系統(tǒng)中的應(yīng)用，如消息隊(duì)列、任務(wù)分發(fā)等，并解釋其作用。4、（本題10分）詳細(xì)闡述二叉樹的前序、中序和后序遍歷的遞歸和非遞歸實(shí)現(xiàn)方法，并舉例說明其應(yīng)用場景。三、設(shè)計(jì)題