數據結構課本習題答案_第1頁
已閱讀1頁,還剩40頁未讀, 繼續(xù)免費閱讀

下載本文檔

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

文檔簡介

1、數據結構數據結構第一章第一章緒論緒論一、一、單項選擇題單項選擇題1、(1)A(2)B2、(1)B(2)D3、C4、A5、A6、(1)C(2)A7、(1)C(2)A8、C9、C10、B11、D二、填空題二、填空題1、存儲結構、存儲結構、算法、算法2、非線性結構、非線性結構3、線性、樹型、、線性、樹型、圖形圖形4、映射、映射5、線性結構、樹型結構、線性結構、樹型結構、圖形結構、圖形結構6、有窮性、確定性、有窮性、確定性、可行性、可行性7、錯

2、誤、錯誤三、算法分析三、算法分析1、(1)O(n)、(2)O(n)、(3)O(n)、(4)O(n)、(5)O()、(6)nO(log3n)、(7)O(log2n)2、(1)der()函數是一個遞歸排序過程,設函數是一個遞歸排序過程,設T(n)是排序)是排序n個元素所需要的時間。在排序個元素所需要的時間。在排序n個元素時,算法的計算時間主要花費在遞歸調用個元素時,算法的計算時間主要花費在遞歸調用der()上。第一調用時,處理的元素序上。第

3、一調用時,處理的元素序列個數為列個數為n1,也就是對余下的,也就是對余下的n1個元素進行排序,所需要的計算時間應為個元素進行排序,所需要的計算時間應為T(n1)。又因。又因為在其中的循環(huán)中,需要為在其中的循環(huán)中,需要n1次比較。所以排序次比較。所以排序n個元素所需要的時間為:個元素所需要的時間為:T(n)=T(n1)n1n﹥1n﹥1據此可得:據此可得:T(1)=0T(2)=T(1)1=01=1T(n)=T(n1)n1n﹥1n﹥1求解過程

4、為:求解過程為:T(n)=[T(n2)(n2)]n1=[T(n3)(n3)](n2)n1=…=…=(T(1)1)2…=(T(1)1)2…n1n1=012…=012…n1n1=n(n1)=n(n1)/2=O(n2)故der函數的時間復雜度為函數的時間復雜度為O(n2)(2)解:設)解:設fact(n)數是數是T(n)。該函數中語句。該函數中語句If(n≤1n≤1)return1的運行時間是的運行時間是O(1),語句,語句return(nf

5、act(n1))運行時間是運行時間是T(n1)O(1)其中其中O(1)為乘法運算的時間。為乘法運算的時間。因此因此T(n)=O(1)n≤1n≤1T(n)=T(n1)O(1)n>1則T(n)=O(1)T(n1)=2O(1)T(n2)這一特點恰好避開了順序存儲結構的缺點,因此,應選用順序存儲結構。這一特點恰好避開了順序存儲結構的缺點,因此,應選用順序存儲結構。2、不一定,由于鏈式存儲需要額外的空間來存儲指針,所以要比順序存儲多占用空間。在、

6、不一定,由于鏈式存儲需要額外的空間來存儲指針,所以要比順序存儲多占用空間。在空間允許的情況下,鏈式存儲結構可以克服順序存儲結構弱點,但空間不允許時,鏈表存空間允許的情況下,鏈式存儲結構可以克服順序存儲結構弱點,但空間不允許時,鏈表存儲結構會出現新的問題。儲結構會出現新的問題。3、該線性表宜采用鏈表存儲結構。因為采用鏈式存儲結構的線性表,插入和刪除操作只需、該線性表宜采用鏈表存儲結構。因為采用鏈式存儲結構的線性表,插入和刪除操作只需要改變

7、指針,時間復雜度為要改變指針,時間復雜度為O(1),而采用順序存儲結構的線性表插入和刪除涉及到數據,而采用順序存儲結構的線性表插入和刪除涉及到數據的大量移動,時間復雜度為的大量移動,時間復雜度為O(n)4、線性結構包括線性表、棧、隊列、串,線性表的存儲結構又分成順序存儲和鏈式存儲。、線性結構包括線性表、棧、隊列、串,線性表的存儲結構又分成順序存儲和鏈式存儲。用C語言描述語言描述順序存儲類型:順序存儲類型:TypedefstructEle

8、mTypedata[maxlen]存放元素存放元素intlen存放長度存放長度Sqlist鏈式存儲類型:鏈式存儲類型:TypedefstructnodeElemTypedata數據域數據域structnodenext指針域指針域SNode5、先找到值為、先找到值為23和15的兩個結點,的兩個結點,q指向值為指向值為23的結點,的結點,p指向值為指向值為15的結點,的結點,p和q結點互換:結點互換:q→llink→rlink=p→llin

9、k→rlink=pp→llink=q→llinkp→llink=q→llinkp→rlink=qq→llink=p→rlink=qq→llink=pq→rlink!=nullq→rlink!=null6、(1)p→rlink→llink=p→llink→rlink→llink=p→llink;p→llink→rlink=p→llink→rlink=p→rlink→rlink;disposedispose(p)(p)(2)(2)newne

10、w(q)(q)q→llink=pq→llink=pq→rlink=p→rlinkq→rlink=p→rlinkp→rlink→llink=qp→rlink→llink=qp→rlink=qp→rlink=q五、算法分析五、算法分析1、VoidVoid(Lnode(LnodeheadheadElemTypexElemTypey)LnodeLnodeqqppq=headheadp=q→nextq→nextwhile(p→data!=xwhi

溫馨提示

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

評論

0/150

提交評論