2022年工碩數據結構試題及答案1_第1頁
2022年工碩數據結構試題及答案1_第2頁
2022年工碩數據結構試題及答案1_第3頁
全文預覽已結束

付費下載

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

2022年工碩數據結構試題及答案12、全部試題的答案寫在答題紙上。

一、推斷以下表達的對錯。

（1）線性表的規律挨次與物理挨次總是全都的。

（2）線性表的挨次存儲表示優于鏈式存儲表示。

（3）線性表若采納鏈式存儲表示時全部結點之間的存儲單元地址可連續可不連續。

（4）二維數組是其數組元素為線性表的線性表。

（5）每種數據構造都應具備三種根本運算：插入、刪除和搜尋。

二、設單鏈表中結點的構造為

typedefstructnode{file://鏈表結點定義

ElemTypedata；file://數據

structnode*Link；file://結點后繼指針

}ListNode；

（1）已知指針p所指結點不是尾結點，若在*p之后插入結點*s，則應執行以下哪一個操作？

A.s->link=p；p->link=s；

B.s->link=p->link；p->link=s；

C.s->link=p->link；p=s；

D.p->link=s；s->link=p；

（2）非空的循環單鏈表first的尾結點（由p所指向）滿意：

A.p->link==NULL；

B.p==NULL；

C.p->link==first；

D.p==first；

三、設有一個挨次棧S，元素s1，s2，s3，s4，s5，s6依次進棧，假如6個元素的出棧挨次為s2，s3，s4，s6，s5，s1，則挨次棧的容量至少應為多少？

四、一棵具有n個結點的抱負平衡二叉樹（即除離根最遠的最底層外其他各層都是滿的，最底層有若干結點）有多少層？若設根結點在第0層，則樹的高度h如何用n來表示（留意n可能為0）？

五、從供選擇的答案中選擇與下面有關圖的表達中各括號相匹配的詞句，將其編號填入相應的括號內。

（1）對于一個具有n個結點和e條邊的無向圖，若采納鄰接表表示，則頂點表的大小為（A），全部邊鏈表中邊結點的總數為（B）。

（2）采納鄰接表存儲的圖的深度優先遍歷算法類似于樹的（C）。

（3）采納鄰接表存儲的圖的廣度優先遍歷算法類似于樹的（D）。

（4）推斷有向圖是否存在回路，除了可以利用拓撲排序方法外，還可以利用（E）。

供選擇的答案

A：①n②n+1③n-1④n+e

B：①e/2②e③2e④n+e

C~D：①中根遍歷②先根遍歷③后根遍歷④按層次遍歷

E：①求關鍵路徑的方法②求最短路徑的Dijkstra方法

③深度優先遍歷算法④廣度優先遍歷算法

六、填空題

（1）在用于表示有向圖的鄰接矩陣中，對第i行的元素進展累加，可得到第i個頂點的（①）度，而對第j列的元素進展累加，可得到第j個頂點的（②）度。

（2）一個連通圖的生成樹是該圖的（③）連通子圖。若這個連通圖有n個頂點，則它的生成樹有（④）條邊。

（3）給定序列{100，86，48，73，35，39，42，57，66，21}，按堆構造的定義，則它肯定（⑤）堆。

（4）在進展直接插入排序時，其數據比擬次數與數據的初始排列（⑥）關；而在進展直接選擇排序時，

溫馨提示

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

評論

0/150

提交評論