鄭州大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2023-2024學(xué)年期末試卷

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

2023-2024學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)元素的最大堆中，插入一個(gè)新元素后，為了恢復(fù)堆的性質(zhì)，需要進(jìn)行的調(diào)整操作的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)2、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的高效存儲(chǔ)和操作？（）A.二叉樹B.哈希表C.字符數(shù)組D.鏈表3、在循環(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;4、在一個(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)5、在一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)無(wú)向圖中，若采用普里姆（Prim）算法生成最小生成樹，其時(shí)間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)6、對(duì)于一個(gè)采用鏈表存儲(chǔ)的棧，若要獲取棧的大?。ㄔ?cái)?shù)量），以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、若要對(duì)一個(gè)具有n個(gè)元素的數(shù)組進(jìn)行歸并排序，需要額外的輔助空間大小為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、若要對(duì)一個(gè)具有n個(gè)元素的無(wú)序數(shù)組進(jìn)行排序，以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序9、設(shè)有一個(gè)廣義表L=(a,(b,c),d)，其長(zhǎng)度和深度分別為？（）A.3和2B.3和3C.4和2D.4和310、一棵二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為BDCAEHFG，則該二叉樹的后序遍歷序列為（）。A.DCBGFHEAB.DCBHGFEAC.BCDGFHEAD.BCDHGFEA11、對(duì)于一個(gè)具有n個(gè)元素的循環(huán)隊(duì)列，隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列滿的條件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front12、對(duì)于一個(gè)具有n個(gè)元素的哈希表，若采用鏈地址法處理沖突，以下關(guān)于查找操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、在一棵AVL樹中，進(jìn)行插入操作后，可能導(dǎo)致樹失去平衡，此時(shí)需要進(jìn)行的旋轉(zhuǎn)操作最多為（）A.1次B.2次C.logn次D.n次14、以下關(guān)于樹的存儲(chǔ)結(jié)構(gòu)的描述，哪一項(xiàng)是不正確的？（）A.孩子兄弟表示法可以方便地實(shí)現(xiàn)樹的遍歷B.雙親表示法便于查找一個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)C.孩子鏈表表示法在處理多叉樹時(shí)空間利用率較高D.以上存儲(chǔ)結(jié)構(gòu)在時(shí)間復(fù)雜度上沒有明顯差異15、在一個(gè)具有n個(gè)元素的循環(huán)鏈表中，查找第i個(gè)元素（1<=i<=n），平均需要比較的次數(shù)為（）。A.nB.n/2C.(n+1)/2D.(n-1)/216、設(shè)有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，頭指針為head，若要在第一個(gè)元素之前插入一個(gè)新元素，則需要執(zhí)行的操作是（）。A.s->next=head;head=s;B.s->next=head->next;head->next=s;C.head->next=s;s->next=head;D.s->next=head;s=head;17、在一個(gè)具有n個(gè)元素的循環(huán)鏈表中，查找第i個(gè)元素（1<=i<=n），平均需要遍歷的節(jié)點(diǎn)個(gè)數(shù)約為？A.n/2B.nC.2nD.n/418、對(duì)于一個(gè)棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.5B.14C.21D.無(wú)數(shù)種19、對(duì)于一個(gè)具有n個(gè)元素的有序單鏈表，要查找一個(gè)值為x的元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.120、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，若每個(gè)節(jié)點(diǎn)都有左子樹和右子樹，則其葉子節(jié)點(diǎn)的個(gè)數(shù)至少為？A.n/2B.(n+1)/2C.n-1D.logn二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述伸展樹在并發(fā)環(huán)境下的應(yīng)用挑戰(zhàn)和解決方法。2、（本題10分）論述如何使用并查集解決朋友圈問題，給出具體的實(shí)現(xiàn)和分析。3、（本題10分）詳細(xì)闡述在圖的深度優(yōu)先遍歷算法中，如何使用遞歸和非遞歸的方式實(shí)現(xiàn)，以及如何避免重復(fù)訪問節(jié)點(diǎn)。4、（本題10分）論述在一個(gè)具有n個(gè)元素的鏈表中，如何判斷鏈表是否有環(huán)。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20