學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)鄭州大學(xué)

《數(shù)據(jù)結(jié)構(gòu)綜合實(shí)驗(yàn)》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、若一個(gè)棧的輸入序列為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,52、在一個(gè)循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，隊(duì)列最大容量為MAXSIZE，若當(dāng)前隊(duì)列長(zhǎng)度為n，則判斷隊(duì)滿的條件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE3、在一個(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)4、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖，其鄰接矩陣中至少有（）個(gè)非零元素。A.nB.n-1C.n(n-1)D.n(n-1)/25、在一個(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)6、在數(shù)據(jù)結(jié)構(gòu)中，哈希表的負(fù)載因子對(duì)性能有很大影響。以下關(guān)于負(fù)載因子的描述，不正確的是（）A.負(fù)載因子越大，哈希沖突的可能性越大B.負(fù)載因子越小，存儲(chǔ)空間利用率越高C.負(fù)載因子通常在0.5到1之間D.可以通過(guò)調(diào)整負(fù)載因子來(lái)優(yōu)化哈希表性能7、在循環(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;8、排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度是衡量算法性能的重要指標(biāo)，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.時(shí)間復(fù)雜度是指算法執(zhí)行所需的時(shí)間與問(wèn)題規(guī)模之間的關(guān)系。B.空間復(fù)雜度是指算法執(zhí)行所需的存儲(chǔ)空間與問(wèn)題規(guī)模之間的關(guān)系。C.不同的排序算法具有不同的時(shí)間復(fù)雜度和空間復(fù)雜度，選擇合適的排序算法可以提高算法的性能。D.排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度越低越好，不需要考慮其他因素。9、以下關(guān)于二叉排序樹(shù)的描述，錯(cuò)誤的是：A.左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值B.右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值C.中序遍歷二叉排序樹(shù)可得到一個(gè)有序序列D.二叉排序樹(shù)的查找效率總是最高的10、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同11、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的棧中，若棧頂指針為top，要判斷棧是否為空，應(yīng)判斷？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL12、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若其所有頂點(diǎn)的度之和為20，則該圖的邊數(shù)為（）。A.5B.10C.15D.2013、對(duì)于一個(gè)具有n個(gè)元素的無(wú)序數(shù)組，使用選擇排序進(jìn)行排序，其交換次數(shù)最多為？A.n-1B.nC.n(n-1)/2D.n^214、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為m，入度之和為k，則m和k的關(guān)系是？（）A.m=kB.m>kC.m<kD.不確定15、以下關(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ù)成正比16、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，若采用鄰接矩陣存儲(chǔ)，則矩陣中非零元素的個(gè)數(shù)至少為？（）A.nB.n-1C.2(n-1)D.n(n-1)/217、在一個(gè)用鏈表實(shí)現(xiàn)的棧中，若要獲取棧底元素的值，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)18、在一個(gè)具有n個(gè)元素的有序數(shù)組中進(jìn)行二分查找，其時(shí)間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(logn)D.O(n^2)19、對(duì)于一個(gè)m行n列的二維數(shù)組，按行優(yōu)先存儲(chǔ)時(shí)，元素a[i][j]（0<=i<m,0<=j<n）的地址計(jì)算公式為：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i20、在一個(gè)具有n個(gè)元素的大頂堆中，若要將堆頂元素與最后一個(gè)元素交換，然后調(diào)整堆，其時(shí)間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋如何在一個(gè)字符串中查找所有不重復(fù)的字符組合。2、（本題10分）解釋在一個(gè)具有n個(gè)節(jié)點(diǎn)的有向無(wú)環(huán)圖中，如何計(jì)算每個(gè)節(jié)點(diǎn)的入度和出度。3、（本題10分）在一個(gè)單鏈表中，如何實(shí)現(xiàn)鏈表的反轉(zhuǎn)操作？請(qǐng)給出具體的算法步驟和代碼示例。4、