北京交通大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2022-2023學(xué)年期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁北京交通大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》

2022-2023學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對于一個具有n個元素的堆，若要將其所有元素從小到大排序，最好的方法是？A.每次刪除堆頂元素并調(diào)整B.直接使用快速排序C.先構(gòu)建大頂堆再調(diào)整D.以上方法效率相同2、在一個具有n個頂點(diǎn)的無向圖中，若要判斷兩個頂點(diǎn)之間是否存在路徑，使用哪種算法較為合適？A.迪杰斯特拉算法B.弗洛伊德算法C.深度優(yōu)先遍歷或廣度優(yōu)先遍歷D.拓?fù)渑判?、已知一棵二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹的右子樹為空的條件是？（）A.A為根節(jié)點(diǎn)B.B為根節(jié)點(diǎn)C.C為根節(jié)點(diǎn)D.無法確定4、若要對100個元素進(jìn)行排序，以下哪種排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.選擇排序C.插入排序D.歸并排序5、在一個用鏈表實(shí)現(xiàn)的隊(duì)列中，若要刪除隊(duì)頭元素并返回其值，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、已知一個具有n個頂點(diǎn)的無向圖采用鄰接矩陣存儲，若要刪除所有的邊，時間復(fù)雜度為？（）A.O(n)B.O(n2)C.O(nlogn)D.O(e)7、在一個哈希表中，若采用線性探測法解決哈希沖突，當(dāng)發(fā)生沖突時，新元素會存儲在什么位置？A.沖突位置的下一個位置B.沖突位置C.隨機(jī)位置D.以上都不對8、對于一個具有n個頂點(diǎn)和e條邊的無向圖，采用鄰接表存儲時，其空間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)9、以下哪種數(shù)據(jù)結(jié)構(gòu)適合頻繁進(jìn)行插入和刪除操作，并且能夠快速查找最大元素？（）A.數(shù)組B.鏈表C.棧D.最大堆10、在圖的存儲結(jié)構(gòu)中，十字鏈表主要用于存儲有向圖，以下關(guān)于十字鏈表的特點(diǎn)，描述不正確的是（）A.既能方便地訪問出邊，也能方便地訪問入邊B.存儲空間比鄰接表節(jié)省C.對于刪除邊的操作比較復(fù)雜D.不適合用于稀疏有向圖11、在一個具有n個元素的有序鏈表中，若要查找第k個元素，以下關(guān)于查找操作的時間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(k)D.O(n)12、在一個大根堆中，刪除堆頂元素后，為了重新調(diào)整為大根堆，需要進(jìn)行的操作是？（）A.將最后一個元素移到堆頂，然后從堆頂向下調(diào)整B.將堆中所有元素重新排序C.將堆頂元素與最后一個元素交換，然后從堆頂向下調(diào)整D.無需調(diào)整13、在一個鏈隊(duì)列中，假設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，刪除隊(duì)頭元素的操作是：A.front=front->nextB.rear=rear->nextC.front->next=NULLD.rear->next=NULL14、在一個具有n個元素的雙向鏈表中，在p所指的節(jié)點(diǎn)之后插入一個新節(jié)點(diǎn)q，其操作步驟為（）。A.q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;B.q->next=p->next;q->prior=p;p->next=q;p->next->prior=q;C.p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;D.p->next->prior=q;q->next=p->next;q->prior=p;p->next=q;15、對于一個大根堆，若將堆中所有元素按照層次遍歷的順序存儲到一個數(shù)組中，以下關(guān)于數(shù)組元素的排列，哪一項(xiàng)是正確的？A.完全無序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對16、以下關(guān)于字符串匹配算法的描述，哪一項(xiàng)是不正確的？（）A.BF算法的時間復(fù)雜度在最壞情況下較高B.KMP算法通過利用已匹配的部分信息來提高效率C.BM算法在一般情況下比KMP算法效率更高D.所有字符串匹配算法的時間復(fù)雜度都與模式串的長度成正比17、在一個具有n個頂點(diǎn)的無向完全圖中，每個頂點(diǎn)的度為多少？（）A.n-1B.nC.2(n-1)D.2n18、在一個具有n個元素的隊(duì)列中，若要獲取隊(duì)頭元素的前一個元素但不刪除，以下操作不可行的是？（）A.遍歷整個隊(duì)列B.使用輔助數(shù)據(jù)結(jié)構(gòu)C.直接獲取D.以上都不可行19、對于一個具有n個元素的堆，若要刪除堆頂元素并調(diào)整堆，時間復(fù)雜度為？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)20、棧和隊(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í)際價值。二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述在拓?fù)渑判虻臄U(kuò)展應(yīng)用中，如何解決課程安排或項(xiàng)目依賴等問題。2、（本題10分）深入分析在具有n個元素的鏈表中，如何刪除指定位置的節(jié)點(diǎn)，并給出具體的算法步驟和代碼實(shí)現(xiàn)。3、（本題10分）詳細(xì)論述在利用堆進(jìn)行多路歸并排序時，如何構(gòu)建初始堆和進(jìn)行歸并過程，并給出具體的算法步驟和代碼實(shí)現(xiàn)。4、（本題10分）論述在字符串匹配中，BF算法和KMP算法的原理和