青島黃海學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》2021-2022學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁青島黃海學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》

2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在二叉樹的序列化和反序列化過程中，以下方法不能保證唯一性的是（）A.先序遍歷序列化B.中序遍歷序列化C.后序遍歷序列化D.層序遍歷序列化2、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時(shí)間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)3、以下關(guān)于字符串匹配的BM算法的描述，哪一項(xiàng)是不正確的？（）A.從模式串的尾部開始匹配B.利用了壞字符和好后綴規(guī)則C.在一般情況下比KMP算法效率低D.可以通過預(yù)處理提高匹配速度4、對于一個(gè)棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.5B.14C.21D.無數(shù)種5、棧和隊(duì)列的應(yīng)用場景非常廣泛，以下關(guān)于它們的應(yīng)用的說法中，錯誤的是？（）A.棧可以用于實(shí)現(xiàn)函數(shù)調(diào)用、表達(dá)式求值和括號匹配等。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、在一個(gè)鏈?zhǔn)酱鎯Φ臈Ｖ?，若要在棧頂插入一個(gè)元素，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、若要對一個(gè)具有n個(gè)元素的數(shù)組進(jìn)行歸并排序，需要額外的輔助空間大小為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同9、設(shè)有一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)無向圖，使用普里姆（Prim）算法求最小生成樹。在算法執(zhí)行過程中，需要選擇一個(gè)頂點(diǎn)作為起始點(diǎn)。以下關(guān)于起始點(diǎn)選擇對算法時(shí)間復(fù)雜度的影響，哪一個(gè)是恰當(dāng)?shù)?？A.起始點(diǎn)的選擇對時(shí)間復(fù)雜度沒有影響B(tài).選擇不同的起始點(diǎn)可能導(dǎo)致時(shí)間復(fù)雜度不同C.選擇頂點(diǎn)度最小的作為起始點(diǎn)可以降低時(shí)間復(fù)雜度D.選擇頂點(diǎn)度最大的作為起始點(diǎn)可以降低時(shí)間復(fù)雜度10、棧和隊(duì)列在計(jì)算機(jī)科學(xué)中有很多應(yīng)用，以下關(guān)于它們的應(yīng)用場景的說法中，錯誤的是？（）A.棧可以用于實(shí)現(xiàn)表達(dá)式求值、括號匹配等。B.隊(duì)列可以用于實(shí)現(xiàn)任務(wù)調(diào)度、消息隊(duì)列等。C.棧和隊(duì)列可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊(duì)列只能在編程語言的底層實(shí)現(xiàn)中使用，不能在實(shí)際應(yīng)用中直接使用。11、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA12、設(shè)有一個(gè)廣義表L=(a,(b,c),d)，其長度和深度分別為？（）A.3和2B.3和3C.4和2D.4和313、一棵哈夫曼樹中，葉子節(jié)點(diǎn)的編碼長度一定（）非葉子節(jié)點(diǎn)的編碼長度。A.大于B.等于C.小于D.不小于14、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無向圖中，使用Prim算法生成最小生成樹。若采用鄰接矩陣存儲圖，以下關(guān)于算法的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)15、在一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通圖中，至少有（）條邊。A.n-1B.nC.n(n-1)D.n(n-1)/216、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖中，使用弗洛伊德算法求所有頂點(diǎn)對之間的最短路徑，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(n2)C.O(n3)D.O(e3)17、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖，采用鄰接表存儲，進(jìn)行深度優(yōu)先遍歷。以下關(guān)于遍歷的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)模緼.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)18、在一個(gè)循環(huán)隊(duì)列中，若隊(duì)頭指針front=5，隊(duì)尾指針rear=2，則隊(duì)列中的元素個(gè)數(shù)為：A.7B.3C.2D.不確定19、以下關(guān)于圖的存儲結(jié)構(gòu)的描述，錯誤的是：A.鄰接矩陣適合存儲稠密圖B.鄰接表適合存儲稀疏圖C.十字鏈表是鄰接表和逆鄰接表的結(jié)合D.鄰接多重表只適合無向圖20、對于一個(gè)具有n個(gè)元素的雙向循環(huán)鏈表，若要刪除第i個(gè)節(jié)點(diǎn)（1<=i<=n），平均需要修改多少個(gè)指針？（）A.2B.3C.4D.5二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）對于一個(gè)具有n個(gè)頂點(diǎn)的有向圖，如何判斷是否存在拓?fù)湫蛄校?、（本題10分）論述在動態(tài)規(guī)劃的問題建模中，如何將實(shí)際問題轉(zhuǎn)化為合適的動態(tài)規(guī)劃模型。3、（本題10分）什么是二叉搜索樹的插入操作的遞歸實(shí)現(xiàn)？請描述其實(shí)現(xiàn)過程。4、（本題10分）詳細(xì)解釋在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，如何使用廣度優(yōu)先搜索算法計(jì)算圖的連通分量個(gè)數(shù)，并