數(shù)據(jù)結(jié)構(gòu)課本習(xí)題答案

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)第一章第一章緒論緒論一、一、單項(xiàng)選擇題單項(xiàng)選擇題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、存儲(chǔ)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、算法、算法2、非線性結(jié)構(gòu)、非線性結(jié)構(gòu)3、線性、樹型、、線性、樹型、圖形圖形4、映射、映射5、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖形結(jié)構(gòu)、圖形結(jié)構(gòu)6、有窮性、確定性、有窮性、確定性、可行性、可行性7、錯(cuò)

2、誤、錯(cuò)誤三、算法分析三、算法分析1、（1）O(n）、(2)O(n)、（3）O(n）、（4）O(n)、（5）O（）、（6）nO（log3n）、（7）O（log2n）2、(1)der()函數(shù)是一個(gè)遞歸排序過程，設(shè)函數(shù)是一個(gè)遞歸排序過程，設(shè)T（n）是排序）是排序n個(gè)元素所需要的時(shí)間。在排序個(gè)元素所需要的時(shí)間。在排序n個(gè)元素時(shí)，算法的計(jì)算時(shí)間主要花費(fèi)在遞歸調(diào)用個(gè)元素時(shí)，算法的計(jì)算時(shí)間主要花費(fèi)在遞歸調(diào)用der()上。第一調(diào)用時(shí)，處理的元素序上。第

3、一調(diào)用時(shí)，處理的元素序列個(gè)數(shù)為列個(gè)數(shù)為n1，也就是對(duì)余下的，也就是對(duì)余下的n1個(gè)元素進(jìn)行排序，所需要的計(jì)算時(shí)間應(yīng)為個(gè)元素進(jìn)行排序，所需要的計(jì)算時(shí)間應(yīng)為T(n1)。又因。又因?yàn)樵谄渲械难h(huán)中，需要為在其中的循環(huán)中，需要n1次比較。所以排序次比較。所以排序n個(gè)元素所需要的時(shí)間為：個(gè)元素所需要的時(shí)間為：T(n)=T(n1)n1n﹥1n﹥1據(jù)此可得：據(jù)此可得：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函數(shù)的時(shí)間復(fù)雜度為函數(shù)的時(shí)間復(fù)雜度為O(n2)（2）解：設(shè)）解：設(shè)fact(n)數(shù)是數(shù)是T(n)。該函數(shù)中語句。該函數(shù)中語句If(n≤1n≤1)return1的運(yùn)行時(shí)間是的運(yùn)行時(shí)間是O（1），語句，語句return(nf

5、act(n1))運(yùn)行時(shí)間是運(yùn)行時(shí)間是T(n1）O(1)其中其中O(1)為乘法運(yùn)算的時(shí)間。為乘法運(yùn)算的時(shí)間。因此因此T(n)=O（1）n≤1n≤1T(n)=T(n1)O(1)n＞1則T(n)=O(1)T(n1)=2O(1)T(n2)這一特點(diǎn)恰好避開了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)，因此，應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。這一特點(diǎn)恰好避開了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)，因此，應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。2、不一定，由于鏈?zhǔn)酱鎯?chǔ)需要額外的空間來存儲(chǔ)指針，所以要比順序存儲(chǔ)多占用空間。在、

6、不一定，由于鏈?zhǔn)酱鎯?chǔ)需要額外的空間來存儲(chǔ)指針，所以要比順序存儲(chǔ)多占用空間。在空間允許的情況下，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以克服順序存儲(chǔ)結(jié)構(gòu)弱點(diǎn)，但空間不允許時(shí)，鏈表存空間允許的情況下，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以克服順序存儲(chǔ)結(jié)構(gòu)弱點(diǎn)，但空間不允許時(shí)，鏈表存儲(chǔ)結(jié)構(gòu)會(huì)出現(xiàn)新的問題。儲(chǔ)結(jié)構(gòu)會(huì)出現(xiàn)新的問題。3、該線性表宜采用鏈表存儲(chǔ)結(jié)構(gòu)。因?yàn)椴捎面準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，插入和刪除操作只需、該線性表宜采用鏈表存儲(chǔ)結(jié)構(gòu)。因?yàn)椴捎面準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，插入和刪除操作只需要改變

7、指針，時(shí)間復(fù)雜度為要改變指針，時(shí)間復(fù)雜度為O（1），而采用順序存儲(chǔ)結(jié)構(gòu)的線性表插入和刪除涉及到數(shù)據(jù)，而采用順序存儲(chǔ)結(jié)構(gòu)的線性表插入和刪除涉及到數(shù)據(jù)的大量移動(dòng)，時(shí)間復(fù)雜度為的大量移動(dòng)，時(shí)間復(fù)雜度為O（n）4、線性結(jié)構(gòu)包括線性表、棧、隊(duì)列、串，線性表的存儲(chǔ)結(jié)構(gòu)又分成順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。、線性結(jié)構(gòu)包括線性表、棧、隊(duì)列、串，線性表的存儲(chǔ)結(jié)構(gòu)又分成順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。用C語言描述語言描述順序存儲(chǔ)類型：順序存儲(chǔ)類型：TypedefstructEle

8、mTypedata[maxlen]存放元素存放元素intlen存放長度存放長度Sqlist鏈?zhǔn)酱鎯?chǔ)類型：鏈?zhǔn)酱鎯?chǔ)類型：TypedefstructnodeElemTypedata數(shù)據(jù)域數(shù)據(jù)域structnodenext指針域指針域SNode5、先找到值為、先找到值為23和15的兩個(gè)結(jié)點(diǎn)，的兩個(gè)結(jié)點(diǎn)，q指向值為指向值為23的結(jié)點(diǎn)，的結(jié)點(diǎn)，p指向值為指向值為15的結(jié)點(diǎn)，的結(jié)點(diǎn)，p和q結(jié)點(diǎn)互換：結(jié)點(diǎn)互換：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