青島大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)青島大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)》

2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、鏈表是另一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。以下關(guān)于鏈表的說(shuō)法中，錯(cuò)誤的是？（）A.鏈表的插入和刪除操作比較方便，只需要修改指針即可。B.鏈表可以動(dòng)態(tài)地增長(zhǎng)和縮小，不像數(shù)組那樣受固定長(zhǎng)度的限制。C.鏈表的訪問(wèn)速度比數(shù)組慢，因?yàn)樾枰闅v鏈表才能找到特定的元素。D.鏈表只能存儲(chǔ)整數(shù)類(lèi)型的數(shù)據(jù)元素。2、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，采用中序遍歷將其轉(zhuǎn)換為一個(gè)有序的單鏈表。以下關(guān)于轉(zhuǎn)換過(guò)程的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)3、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A.nB.n^2C.n(n-1)D.n(n+1)4、在一個(gè)用鄰接矩陣存儲(chǔ)的無(wú)向圖中，若要?jiǎng)h除一條邊，需要修改矩陣中的幾個(gè)元素？A.1個(gè)B.2個(gè)C.3個(gè)D.4個(gè)5、已知一個(gè)棧的進(jìn)棧序列為1,2,3,4,5，下列序列中不可能是出棧序列的是（）。A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,56、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和m條邊的有向圖，使用鄰接表存儲(chǔ)，其入度和出度的計(jì)算時(shí)間復(fù)雜度分別為（）A.O(n)和O(m)B.O(m)和O(n)C.O(n+m)和O(n+m)D.O(n^2)和O(n^2)7、已知一個(gè)圖的鄰接表存儲(chǔ)結(jié)構(gòu)，若要判斷任意兩個(gè)頂點(diǎn)之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索8、在一棵紅黑樹(shù)中，插入一個(gè)新節(jié)點(diǎn)后，調(diào)整樹(shù)的結(jié)構(gòu)以保持紅黑性質(zhì)的操作次數(shù)最多為（）A.1B.2C.lognD.n9、在一個(gè)用十字鏈表存儲(chǔ)的有向圖中，查找一個(gè)頂點(diǎn)的所有出邊和入邊的時(shí)間復(fù)雜度是？（）A.O(1)B.O(n)C.O(e)D.O(n+e)10、哈希表的性能取決于哈希函數(shù)的設(shè)計(jì)和沖突解決方法的選擇，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.好的哈希函數(shù)應(yīng)該具有均勻分布性、隨機(jī)性和高效性等特點(diǎn)。B.沖突解決方法的選擇應(yīng)該根據(jù)哈希表的大小、數(shù)據(jù)的特點(diǎn)和操作的頻率等因素來(lái)決定。C.哈希表的性能可以通過(guò)調(diào)整哈希函數(shù)和沖突解決方法來(lái)優(yōu)化。D.哈希表的性能只取決于哈希函數(shù)的設(shè)計(jì)，與沖突解決方法無(wú)關(guān)。11、在數(shù)據(jù)結(jié)構(gòu)中，使用隊(duì)列來(lái)實(shí)現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過(guò)程的描述，錯(cuò)誤的是（）A.從起始節(jié)點(diǎn)開(kāi)始入隊(duì)B.隊(duì)列為空時(shí)結(jié)束遍歷C.訪問(wèn)節(jié)點(diǎn)時(shí)將其未訪問(wèn)的鄰接節(jié)點(diǎn)入隊(duì)D.節(jié)點(diǎn)不會(huì)被重復(fù)訪問(wèn)12、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)中，若采用后序遍歷得到的節(jié)點(diǎn)序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無(wú)法確定13、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同14、設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前插入一個(gè)新元素，并且移動(dòng)元素的平均次數(shù)為n/2，則插入算法的平均時(shí)間復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)15、若要從一個(gè)具有n個(gè)元素的有序單鏈表中刪除所有值重復(fù)的元素，使得鏈表中每個(gè)元素的值都不同，最優(yōu)的算法時(shí)間復(fù)雜度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)16、對(duì)于一個(gè)用鄰接矩陣存儲(chǔ)的圖，若要判斷兩個(gè)頂點(diǎn)之間是否存在邊，時(shí)間復(fù)雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)17、已知一個(gè)哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測(cè)法處理沖突。若依次插入關(guān)鍵字31、25、19、49、37、21、13、17，則在查找關(guān)鍵字19時(shí)需要進(jìn)行幾次比較？（）A.1B.2C.3D.418、在一棵平衡二叉樹(shù)中，插入一個(gè)新節(jié)點(diǎn)后可能導(dǎo)致失衡，需要進(jìn)行調(diào)整。以下哪種調(diào)整操作可能涉及到旋轉(zhuǎn)次數(shù)最多？（）A.LL型調(diào)整B.RR型調(diào)整C.LR型調(diào)整D.RL型調(diào)整19、數(shù)組通常具有的兩種基本操作是：A.插入和刪除B.查找和修改C.遍歷和排序D.索引和賦值20、在數(shù)據(jù)結(jié)構(gòu)中，使用并查集解決集合合并問(wèn)題時(shí)，以下關(guān)于路徑壓縮的描述，錯(cuò)誤的是（）A.可以提高查找效率B.不改變集合的關(guān)系C.增加了合并操作的復(fù)雜度D.使樹(shù)的高度降低二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）比較快速排序和歸并排序在空間利用上的不同，并舉例說(shuō)明。2、（本題10分）解釋如何在一個(gè)二叉搜索樹(shù)中進(jìn)行層次遍歷的迭代實(shí)現(xiàn)，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度。3、（本題10分）解釋如何在一個(gè)字符串中查找第一個(gè)只出現(xiàn)一次的字符。4、（本題10分）闡述在一個(gè)帶權(quán)有向圖中，如何使用迪杰斯特拉算法求解單源最短路徑問(wèn)題，分析算法的正確性和時(shí)