保山學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷_第1頁
保山學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷_第2頁
保山學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷_第3頁
保山學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷_第4頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論