數據結構課本習題答案

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