青島大學《數(shù)據(jù)科學與語言》2022-2023學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁青島大學

《數(shù)據(jù)科學與語言》2022-2023學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個頂點的強連通圖中，至少有多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)2、在一個循環(huán)隊列中，若隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，則判斷隊滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front3、數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型（ADT）是一種定義數(shù)據(jù)結(jié)構(gòu)的方式，它包括數(shù)據(jù)的存儲結(jié)構(gòu)和操作集合。以下關(guān)于ADT的說法中，錯誤的是？（）A.ADT使得數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)與使用分離，提高了代碼的可維護性和可擴展性。B.ADT可以用多種編程語言實現(xiàn)，不同的實現(xiàn)方式可能會有不同的性能和特點。C.ADT的操作集合包括插入、刪除、查找、遍歷等基本操作。D.ADT只適用于線性數(shù)據(jù)結(jié)構(gòu)，不適用于非線性數(shù)據(jù)結(jié)構(gòu)。4、以下關(guān)于二叉排序樹的描述，錯誤的是：A.左子樹上所有結(jié)點的值均小于根結(jié)點的值B.右子樹上所有結(jié)點的值均大于根結(jié)點的值C.中序遍歷二叉排序樹可得到一個有序序列D.二叉排序樹的查找效率總是最高的5、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)圖的存儲？A.鄰接矩陣和鄰接表B.二叉樹和鏈表C.棧和隊列D.數(shù)組和哈希表6、在一個具有n個元素的有序鏈表中，若要查找第k個元素，以下關(guān)于查找操作的時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(k)D.O(n)7、對于一個具有n個頂點和e條邊的有向完全圖，其弧的條數(shù)為（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/28、設(shè)有一個循環(huán)隊列，存儲空間為Q[0..m-1]，初始時front=rear=m?，F(xiàn)經(jīng)過一系列入隊與退隊操作后，front=20，rear=15，則此時隊列中的元素個數(shù)為（）。A.5B.6C.m-5D.m+59、在一個具有n個元素的小根堆中，刪除堆頂元素后，將最后一個元素放到堆頂，然后進行調(diào)整，其時間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)10、棧和隊列在計算機科學中有很多應(yīng)用，以下關(guān)于它們的應(yīng)用場景的說法中，錯誤的是？（）A.?？梢杂糜趯崿F(xiàn)表達式求值、括號匹配等。B.隊列可以用于實現(xiàn)任務(wù)調(diào)度、消息隊列等。C.棧和隊列可以用于實現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊列只能在編程語言的底層實現(xiàn)中使用，不能在實際應(yīng)用中直接使用。11、設(shè)有一個具有n個頂點的有向圖，采用鄰接表存儲。若要計算每個頂點的出度，以下關(guān)于操作的時間復(fù)雜度的描述，哪一項是恰當?shù)模緼.O(n)B.O(n+e)C.O(n^2)D.O(e)12、在一個具有n個頂點的有向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n13、對于一個具有n個節(jié)點的線索二叉樹，若n個節(jié)點中有m個空指針域，則線索的數(shù)量為？A.mB.m/2C.n+1D.n-114、在一個鏈式存儲的隊列中，若隊頭指針為front，隊尾指針為rear，當進行一次出隊操作后，front指針應(yīng)該如何移動？A.front=front->nextB.front=rearC.front不變D.front=NULL15、在一個B樹中，每個節(jié)點的關(guān)鍵字數(shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-116、已知一個哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測法處理沖突。若依次插入關(guān)鍵字31、25、19、49、37、21、13、17，則在查找關(guān)鍵字19時需要進行幾次比較？（）A.1B.2C.3D.417、對于一個具有n個頂點的無向圖，若其邊的集合為{(1,2),(1,3),(2,3),(2,4),(3,4)}，則該圖的鄰接表存儲中，頂點2的鏈表中包含的頂點有：A.1,3,4B.1,3C.3,4D.1,418、對于一個具有n個頂點的強連通有向圖，其鄰接矩陣中至少有（）個非零元素。A.nB.n-1C.n(n-1)D.n(n-1)/219、在一個具有n個元素的順序存儲的線性表中，要在第i個位置插入一個新元素（1<=i<=n+1），需要移動的元素個數(shù)約為？A.n-iB.iC.n-i+1D.n-i-120、在一個具有n個元素的順序表中，若要將其逆置，以下關(guān)于操作的時間復(fù)雜度的描述，哪一項是恰當?shù)模緼.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋在一個具有n個頂點的無向圖中，如何判斷是否存在歐拉回路。2、（本題10分）詳細闡述如何在一個帶權(quán)有向圖中計算兩個頂點之間的次短路徑。3、（本題10分）在一個鏈表中，如何查找鏈表的中間結(jié)點？4、（本題10分）詳細闡述如何在一個帶權(quán)有向圖中計算源點到所有頂點的次短路徑集合。三、