第1章 練習(xí)與思考題

練習(xí)1.1

1.1-1（開放問題）
原題：
給出生活中一個需要排序的例子或者現(xiàn)實(shí)生活中需要計算凸殼的一個例子。
回答：
考試成績需要排序得到排名；
計算光線反射的時候需要計算凸殼。

1.1-2（開放問題）
原題：
除速度外，在真實(shí)環(huán)境中還可能使用哪些其他有關(guān)效率的量度？
回答：
個人見解有功率，汽車的百公里加速時間。還有計算機(jī)的空間消耗，資源占用。

1.1-3（開放問題）
原題：
選擇一種你以前已知的數(shù)據(jù)結(jié)構(gòu)，并討論其優(yōu)勢和局限。
回答：
鏈表。鏈表的優(yōu)勢可以概括為“動態(tài)”二字，包括長度（大?。╇S意擴(kuò)增，數(shù)據(jù)的增加、刪除、插入十分方便。
缺點(diǎn)是查找比較麻煩，不支持隨機(jī)存取。

1.1-4（開放問題）
原題：
前面給出的最短路徑與旅行商問題有哪些相似之處？又有哪些不同？
回答：
最短路徑求兩點(diǎn)間最短路。旅行商問題是遍歷所有點(diǎn)，并回到起點(diǎn)的最短路。
兩者共同點(diǎn)是都是最優(yōu)化問題，求最短路。
不同是旅行商問題要求遍歷所有點(diǎn)，整個路徑是一個經(jīng)過所有點(diǎn)的回路。
注意旅行商問題的起點(diǎn)終點(diǎn)并不重要，環(huán)上任意一點(diǎn)都可以作為起、終點(diǎn)。

ps：完整問答會稍后整理并在gayhub上更新。