石河子大學(xué)《數(shù)據(jù)科學(xué)與工程引論》2022-2023學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁石河子大學(xué)

《數(shù)據(jù)科學(xué)與工程引論》2022-2023學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的線性表中，采用順序查找法查找一個特定元素，若查找成功，平均查找長度為？（）A.(n+1)/2B.n/2C.lognD.n2、在數(shù)據(jù)結(jié)構(gòu)中，哈弗曼編碼是一種用于數(shù)據(jù)壓縮的編碼方式，以下關(guān)于哈弗曼編碼的描述，錯誤的是（）A.出現(xiàn)頻率高的字符編碼較短B.編碼是唯一的C.解碼過程簡單D.對所有數(shù)據(jù)都能達到很好的壓縮效果3、在一個用鄰接表表示的無向圖中，若要刪除一條邊，需要進行哪些操作？A.在兩個相關(guān)頂點的鄰接表中刪除對應(yīng)的邊節(jié)點B.只在一個頂點的鄰接表中刪除對應(yīng)的邊節(jié)點C.重新構(gòu)建鄰接表D.以上都不對4、以下哪種排序算法在元素數(shù)量較少時性能較好？A.歸并排序B.快速排序C.插入排序D.堆排序5、數(shù)組是一種常見的數(shù)據(jù)結(jié)構(gòu)，它具有固定的大小和連續(xù)的存儲位置。以下關(guān)于數(shù)組的說法中，錯誤的是？（）A.數(shù)組可以通過下標(biāo)快速訪問其中的元素。B.數(shù)組的插入和刪除操作比較耗時，因為需要移動大量的元素。C.數(shù)組可以存儲不同類型的數(shù)據(jù)元素。D.數(shù)組的長度在創(chuàng)建后不能改變。6、在一個循環(huán)隊列中，若隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，則判斷隊滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front7、設(shè)有一個具有n個節(jié)點的二叉樹，若每個節(jié)點都有左右子樹，則該二叉樹的葉子節(jié)點數(shù)量與度為2的節(jié)點數(shù)量之間存在特定關(guān)系。以下關(guān)于這種關(guān)系的描述，哪一項是正確的？A.葉子節(jié)點數(shù)量等于度為2的節(jié)點數(shù)量B.葉子節(jié)點數(shù)量比度為2的節(jié)點數(shù)量多1C.葉子節(jié)點數(shù)量比度為2的節(jié)點數(shù)量少1D.兩者之間沒有固定關(guān)系8、以下關(guān)于字符串匹配算法的描述，哪一項是不正確的？（）A.BF算法的時間復(fù)雜度在最壞情況下較高B.KMP算法通過利用已匹配的部分信息來提高效率C.BM算法在一般情況下比KMP算法效率更高D.所有字符串匹配算法的時間復(fù)雜度都與模式串的長度成正比9、在一個具有n個元素的單鏈表中，若要在第i個位置（1<=i<=n）插入一個新元素，平均需要遍歷多少個節(jié)點？（）A.i-1B.iC.(i-1)/2D.i/210、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一個元素，其存儲地址為1，每個元素占一個存儲單元，則a85的地址為？（）A.33B.32C.18D.4011、在一個長度為n的有序數(shù)組中進行二分查找，其時間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(logn)D.O(n2)12、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)優(yōu)先級隊列？（）A.二叉樹B.鏈表C.堆D.棧13、在一個具有n個元素的順序表中，要在中間位置插入一個新元素，平均移動元素的個數(shù)約為？A.n/2B.nC.lognD.114、在數(shù)據(jù)結(jié)構(gòu)中，使用并查集解決集合合并問題時，以下關(guān)于路徑壓縮的描述，錯誤的是（）A.可以提高查找效率B.不改變集合的關(guān)系C.增加了合并操作的復(fù)雜度D.使樹的高度降低15、已知一個哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測法處理沖突。若依次插入關(guān)鍵字31、25、19、49、37、21、13、17，則在查找關(guān)鍵字19時需要進行幾次比較？（）A.1B.2C.3D.416、在哈夫曼編碼中，對于出現(xiàn)頻率較高的字符，其編碼長度通常怎樣？（）A.較長B.較短C.固定不變D.隨機確定17、若一個鏈表的每個節(jié)點只包含數(shù)據(jù)域和指針域，且指針域只指向其后繼節(jié)點，這種鏈表稱為：A.單向鏈表B.雙向鏈表C.循環(huán)鏈表D.靜態(tài)鏈表18、一個有序序列為{12,18,24,35,47,50,62,83,90,115,134}，當(dāng)用二分法查找值為90的元素時，需要比較的次數(shù)是（）。A.1B.2C.3D.419、在一個具有n個頂點的連通圖中，生成樹的邊數(shù)一定為？（）A.n-1B.nC.n+1D.2n20、在二叉搜索樹中，左子樹的所有節(jié)點值都小于根節(jié)點值，右子樹的所有節(jié)點值都大于根節(jié)點值。若要查找一個特定值的節(jié)點，以下哪種方法效率最高？A.先序遍歷B.中序遍歷C.后序遍歷D.以上效率相同二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的算法思想，并比較它們在不同情況下的優(yōu)劣。2、（本題10分）論述跳表在數(shù)據(jù)動態(tài)更新頻繁情況下的性能優(yōu)化策略。3、（本題10分）詳細說明堆的性質(zhì)（大根堆、小根堆），以及如何進行堆的構(gòu)建、插入和刪除操作。4、（本題10分）解釋如何在一個字符串中進行模式匹配，如使用KMP算法，給出算法步驟和原理