北京聯(lián)合大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷

自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁北京聯(lián)合大學(xué)

《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(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)2、對(duì)于一個(gè)具有n個(gè)元素的有序單鏈表，若要在其中查找一個(gè)特定元素，其平均時(shí)間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)3、設(shè)有一個(gè)鏈棧，棧頂指針為top，若要在棧頂插入一個(gè)新元素，則需要執(zhí)行的操作是（）。A.s->next=top;top=s;B.top->next=s;top=s;C.s->next=top->next;top->next=s;D.top=s;s->next=NULL;4、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖中，若存在負(fù)權(quán)邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用5、棧和隊(duì)列的應(yīng)用場(chǎng)景非常廣泛，以下關(guān)于它們的應(yīng)用的說法中，錯(cuò)誤的是？（）A.棧可以用于實(shí)現(xiàn)函數(shù)調(diào)用、表達(dá)式求值和括號(hào)匹配等。B.隊(duì)列可以用于實(shí)現(xiàn)任務(wù)調(diào)度、消息隊(duì)列和廣度優(yōu)先搜索等。C.棧和隊(duì)列可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊(duì)列只適用于計(jì)算機(jī)科學(xué)領(lǐng)域，在其他領(lǐng)域沒有實(shí)際價(jià)值。6、在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，若度為2的結(jié)點(diǎn)數(shù)為m，則葉子結(jié)點(diǎn)數(shù)為：A.n-mB.m+1C.(n+1)/2D.n-2m+17、在一個(gè)用鄰接表表示的無向圖中，若要?jiǎng)h除一條邊，需要進(jìn)行哪些操作？A.在兩個(gè)相關(guān)頂點(diǎn)的鄰接表中刪除對(duì)應(yīng)的邊節(jié)點(diǎn)B.只在一個(gè)頂點(diǎn)的鄰接表中刪除對(duì)應(yīng)的邊節(jié)點(diǎn)C.重新構(gòu)建鄰接表D.以上都不對(duì)8、在一個(gè)具有n個(gè)節(jié)點(diǎn)的圖中，使用弗洛伊德算法求所有節(jié)點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)9、對(duì)于一個(gè)具有n個(gè)元素的無序數(shù)組，若要找出第k小的元素，以下哪種算法較為合適？（）A.冒泡排序B.快速排序C.選擇排序D.堆排序10、在一棵二叉搜索樹中，刪除一個(gè)有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)時(shí)，通常采用的方法是：A.用左子樹的最大值替代該節(jié)點(diǎn)B.用右子樹的最小值替代該節(jié)點(diǎn)C.隨機(jī)選擇左子樹或右子樹的節(jié)點(diǎn)替代D.不進(jìn)行替代，直接刪除11、對(duì)于一個(gè)具有n個(gè)元素的冒泡排序，若要交換相鄰兩個(gè)元素，平均需要移動(dòng)多少次？（）A.0B.1C.2D.312、若哈希函數(shù)H(key)=key%7，要將關(guān)鍵字38插入到長(zhǎng)度為7的哈希表中，其存儲(chǔ)位置是：A.3B.5C.6D.013、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹，若底層從左到右填充，則第i個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的編號(hào)為？A.2iB.2i+1C.i*2D.i*2+114、已知一個(gè)有序表為{12,25,30,45,50,60,70,80}，若采用折半查找法查找值為45的元素，需要比較多少次？（）A.1B.2C.3D.415、在一個(gè)順序存儲(chǔ)的數(shù)組中實(shí)現(xiàn)一個(gè)簡(jiǎn)單的棧結(jié)構(gòu)，若棧頂指針top初始值為-1，當(dāng)進(jìn)行一次入棧操作后，top的值應(yīng)該如何變化？A.top不變B.top=top+1C.top=top-1D.top=016、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，若一個(gè)二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，那么它的后序遍歷序列是什么？（）A.BCAB.CBAC.CABD.ACB17、在數(shù)據(jù)結(jié)構(gòu)中，鏈表的每個(gè)節(jié)點(diǎn)通常包含數(shù)據(jù)域和指針域。若要在一個(gè)單向鏈表中刪除一個(gè)指定節(jié)點(diǎn)，以下哪種操作是關(guān)鍵步驟？A.修改被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的指針B.修改被刪除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)的指針C.釋放被刪除節(jié)點(diǎn)的內(nèi)存D.以上都是18、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素（1<=i<=n），需要移動(dòng)多少個(gè)元素？（）A.n-iB.iC.n-i+1D.n-i-119、對(duì)于一個(gè)具有n個(gè)元素的有序鏈表，若要在其中插入一個(gè)新元素并保持有序，平均需要移動(dòng)的元素個(gè)數(shù)為？（）A.n/2B.nC.lognD.nlogn20、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向連通圖，利用Prim算法構(gòu)造最小生成樹時(shí)，其時(shí)間復(fù)雜度為：A.O(n^2)B.O(elogn)C.O(nlogn)D.O(e^2)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋跳表的概念和數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，說明其插入、刪除和查找操作的算法步驟，分析跳表與其他搜索結(jié)構(gòu)的性能比較。2、（本題10分）詳細(xì)闡述在具有n個(gè)元素的循環(huán)隊(duì)列中，如何實(shí)現(xiàn)隊(duì)列元素的刪除操作，并保證隊(duì)列的正常運(yùn)行，給出具體的算法步驟和代碼。3、（本題10分）解釋如何在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用插入排序算法進(jìn)行排序，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。4、（本題10分）在一個(gè)具有n個(gè)元素的有序數(shù)組中，如何查找最后一個(gè)小于給定值的元素，給出算