保山學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號(hào)學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁保山學(xué)院《數(shù)據(jù)結(jié)構(gòu)》

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