邢臺(tái)學(xué)院《數(shù)據(jù)科學(xué)》2022-2023學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)邢臺(tái)學(xué)院《數(shù)據(jù)科學(xué)》

2022-2023學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下關(guān)于圖的遍歷算法的描述，哪一項(xiàng)是正確的？（）A.深度優(yōu)先遍歷和廣度優(yōu)先遍歷都能訪問(wèn)到圖中的所有節(jié)點(diǎn)B.深度優(yōu)先遍歷適合用于求解最短路徑問(wèn)題C.廣度優(yōu)先遍歷的空間復(fù)雜度低于深度優(yōu)先遍歷D.兩種遍歷算法的時(shí)間復(fù)雜度都與圖的邊數(shù)成正比2、在數(shù)據(jù)結(jié)構(gòu)中，字典樹(shù)（Trie樹(shù)）常用于字符串的存儲(chǔ)和查找，以下關(guān)于字典樹(shù)的特點(diǎn)，不正確的是（）A.對(duì)于前綴相同的字符串可以節(jié)省存儲(chǔ)空間B.查找操作的時(shí)間復(fù)雜度與字符串長(zhǎng)度有關(guān)C.適合用于詞頻統(tǒng)計(jì)D.插入和刪除操作比較復(fù)雜3、在一個(gè)大根堆中，刪除堆頂元素后，為了重新調(diào)整為大根堆，需要進(jìn)行的操作是？（）A.將最后一個(gè)元素移到堆頂，然后從堆頂向下調(diào)整B.將堆中所有元素重新排序C.將堆頂元素與最后一個(gè)元素交換，然后從堆頂向下調(diào)整D.無(wú)需調(diào)整4、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問(wèn)？（）A.鏈表B.隊(duì)列C.棧D.數(shù)組5、在一個(gè)循環(huán)隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAXSIZE，則判斷隊(duì)滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front6、在一個(gè)具有n個(gè)元素的順序表中，若要在第i個(gè)位置（1<=i<=n+1）插入一個(gè)新元素，需要移動(dòng)的元素個(gè)數(shù)最少為（）。A.0B.i-1C.n-iD.n-i+17、設(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)8、若一棵二叉樹(shù)的中序遍歷序列是ABCDEFG，后序遍歷序列是BDCAFGE，則其先序遍歷序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB9、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的棧中，若棧頂指針為top，要判斷棧是否為空，應(yīng)判斷？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL10、在一個(gè)哈希表中，負(fù)載因子越大，說(shuō)明什么？A.哈希沖突越少B.存儲(chǔ)空間利用率越高C.查找效率越高D.以上都不對(duì)11、在一個(gè)采用順序存儲(chǔ)結(jié)構(gòu)的線性表中，若要在第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)12、二叉樹(shù)是一種重要的數(shù)據(jù)結(jié)構(gòu)。對(duì)于一個(gè)滿二叉樹(shù)，若其高度為h，則節(jié)點(diǎn)總數(shù)為多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-113、對(duì)于一個(gè)采用順序存儲(chǔ)的棧，若要判斷棧是否為空，以下哪種方法是最有效的？A.檢查棧頂元素是否為NULLB.檢查棧頂指針是否為-1C.檢查棧頂指針是否等于棧的最大容量D.檢查棧中元素的數(shù)量是否為014、在一個(gè)具有n個(gè)元素的大根堆中，刪除堆頂元素后，將最后一個(gè)元素放到堆頂，然后進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)15、一棵哈夫曼樹(shù)共有215個(gè)節(jié)點(diǎn)，對(duì)其進(jìn)行編碼，共能得到（）種不同的編碼。A.107B.108C.214D.21516、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無(wú)向圖中，使用Prim算法生成最小生成樹(shù)。若采用鄰接矩陣存儲(chǔ)圖，以下關(guān)于算法的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)17、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，進(jìn)行先序遍歷和中序遍歷，得到的序列相同，則該二叉樹(shù)的形狀為？A.只有一個(gè)根節(jié)點(diǎn)B.所有節(jié)點(diǎn)只有左子樹(shù)C.所有節(jié)點(diǎn)只有右子樹(shù)D.是一棵滿二叉樹(shù)18、在數(shù)據(jù)結(jié)構(gòu)中，對(duì)于一個(gè)具有n個(gè)元素的有序數(shù)組，使用二分查找算法查找一個(gè)特定元素，其平均時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)19、在循環(huán)鏈表中，尾指針rear指向鏈表的尾節(jié)點(diǎn)，若要在鏈表中插入一個(gè)新的節(jié)點(diǎn)，使其成為新的尾節(jié)點(diǎn)，以下操作正確的是？（）A.rear->next=new_node;new_node->next=rear;rear=new_node;B.new_node->next=rear;rear->next=new_node;rear=new_node;C.rear=new_node;new_node->next=rear->next;rear->next=new_node;D.new_node->next=rear->next;rear->next=new_node;20、在一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉（Dijkstra）算法求單源最短路徑。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）鏈表的插入和刪除操作與數(shù)組相比有哪些優(yōu)勢(shì)？請(qǐng)舉例說(shuō)明。2、（本題10分）詳細(xì)闡述AVL樹(shù)和紅黑樹(shù)在自平衡機(jī)制上的差異，以及它們適用的不同場(chǎng)景。3、（本題10分）分析在字符串匹配中，如何利用后綴自動(dòng)機(jī)提高匹配效率。4、（本題10