學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁保山學院《數據結構》

2022-2023學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個用鏈表實現的隊列中，若要刪除隊尾元素，需要進行哪些操作？A.遍歷鏈表找到隊尾元素并刪除B.將隊尾元素的前一個元素設為隊尾C.直接刪除隊尾元素D.以上都不對2、在一個具有n個元素的循環隊列中，若隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，則隊列中元素的個數為？A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+13、對于一個具有n個元素的小根堆，若要刪除堆頂元素并重新調整堆，以下關于操作的平均時間復雜度的描述，哪一項是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、在一個具有n個元素的雙向鏈表中，在p所指的節點之后插入一個新節點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;5、棧是一種特殊的線性表，其操作遵循后進先出原則。若一個棧的初始狀態為空，現在依次將元素1、2、3、4、5入棧，然后再依次出棧，那么出棧的順序是什么？（）A.12345B.54321C.32154D.215436、在一個具有n個頂點的無向圖中，若采用鄰接矩陣存儲，則矩陣中非零元素的個數至少為？（）A.nB.n-1C.2(n-1)D.n(n-1)/27、在一個用鏈表實現的棧中，若要獲取棧底元素的值，需要的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、若一棵二叉樹的中序遍歷序列是ABCDEFG，后序遍歷序列是BDCAFGE，則其先序遍歷序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB9、對于一個具有n個元素的雙向循環鏈表，若要刪除第i個節點（1<=i<=n），平均需要修改多少個指針？（）A.2B.3C.4D.510、對于一個具有n個元素的堆排序，其空間復雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、設有一個棧，元素進棧的次序為A、B、C、D、E，下列不可能的出棧序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE12、對于一個用鏈表表示的線性表，在表頭插入一個新元素和在表尾插入一個新元素，哪個操作更復雜？A.表頭插入B.表尾插入C.復雜度相同D.取決于鏈表長度13、在一個具有n個元素的順序表中，若要在第i個元素之前插入一個新元素，平均需要移動多少個元素？（）A.n/2B.nC.iD.n-i14、在一個長度為n的有序線性表中進行二分查找，在最壞情況下，需要比較的次數為（）。A.O(n)B.O(n^2)C.O(log?n)D.O(nlog?n)15、在一個具有n個元素的雙向循環鏈表中，刪除一個節點后，需要修改幾個指針？A.2B.3C.4D.516、若要對一個具有n個元素的有序鏈表進行二分查找，是否可行？（）A.可行B.不可行C.有時可行D.取決于鏈表長度17、一棵完全二叉樹的第5層（根為第1層）有16個葉子節點，則該完全二叉樹的節點總數最少為（）。A.47B.55C.63D.6418、在一個用鄰接矩陣存儲的圖中，若要判斷兩個節點是否相鄰，時間復雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)19、對于一個具有n個節點的二叉樹，其先序遍歷、中序遍歷和后序遍歷的結果都是唯一確定的，這個二叉樹一定是（）A.滿二叉樹B.完全二叉樹C.單支樹D.以上都不是20、已知一棵二叉排序樹的中序遍歷序列為{10,12,15,18,20,25,30}，則其可能的前序遍歷序列為？（）A.20,18,15,12,10,25,30B.10,12,15,18,20,25,30C.30,25,20,18,15,12,10D.10,12,18,15,20,30,25二、簡答題（本大題共4個小題，共40分)1、（本題10分）對于一個具有n個頂點的無向圖，如何使用廣度優先搜索算法計算頂點的度？2、（本題10分）詳細闡述桶排序在處理大規模數據時的優化策略。3、（本題10分）解釋字符串匹配的常見算法，如暴力匹配算法、KMP算法，分析它們的時間復雜度和改進思路。4、（本題10分）對于一個用鏈表實現的棧，如何實現棧的逆序操作，要求空間復雜度為O(