數據結構習題解析(第3版)（簡體書）
商品資訊
商品簡介
本書主教材按照面向對象程序設計的思想，根據作者多年的教學積累，系統地介紹各類數據結構的功能、表示和實現，對比各類數據結構適用的應用環境；結合實際問題展示算法設計的一般性模式與方法、算法實現的主流技巧，以及算法效率的評判依據和分析方法；以高度概括的體例為線索貫穿全書，并通過對比和類比揭示數據結構與算法的內在聯系，幫助讀者形成整體性認識。
習題解析涵蓋驗證型、拓展型。反思型、實踐型和研究型習題，總計290余道大題、525道小題，激發讀者的求知欲。培養自學能力和獨立思考習慣。主教材和習題解析共計配有340多組，400余幅插圖結合簡練的敘述，40多張表格列舉簡明的規范、過程及要點，280余段代碼及算法配合詳盡而簡潔的注釋，使深奧抽象的概念和過程得以具體化且便于理解和記憶；推薦20余冊經典的專著與教材，提供40余篇重點的學術論文，便于讀者進一步鉆研和拓展。
結合學生基礎、專業方向、教學目標及允許課時總量等各種因素，本書推薦了若干種典型的教學進度及學時分配方案，供授課教師視具體情況參考和選用。
作者簡介
名人/編輯推薦
目次
第1章 緒論
第2章 向量
第3章 列表
第4章 棧與隊列
第5章 二叉樹
第6章 圖
第7章 搜索樹
第8章 高級搜索樹
第9章 詞典
第10章 優先級隊列
第11章 串
第12章 排序
附錄
書摘/試閱
于是，若套用power2（）算法的流程，只要將其中的整數平方運算sqr（）換成矩陣的平方運算，即可實現fib（n）的計算。更重要的是，這里僅涉及2x2矩陣的計算，每次同樣只需常數時間，故整體的運行時間也是O（logn）。
c）以上結論是否矛盾？為什么？
（解答）
以上結論在表面上的確構成悖論。究其根源在于，以上對power2（）與fib（）等算法的時間復雜度分析都假定，整數的乘法、位移和打印等基本操作各自只需O（1）時間——即采用所謂的常數代價準則（uniformcostcriterion）——而這只是在一定程度上的近似。
設參與運算的整數（的數值）為k。不難看出，上述基本操作都需要逐個地讀取k的二進制展開的每一有效比特位，故更為精確地，這些操作的時間成本應該線性正比于k的有效位的總數O（logk）——即采用所謂的對數代價準則（logarithmiccostcriterion）。
當k不是很大時，兩種準則之間的差異并不是不大；而當k很大甚至遠遠超出機器字長之后，二者之間的差異將不容忽略。仍以Fibonacci數為例。因fib（n）=□（φn），故該數列應以φ為比率呈指數遞增，各項的二進制展開長度log2（φn）則以勻速呈線性遞增。根據習題（1—19）所給的估算經驗，相鄰項約相差log2φ=0.694個比特，大致每隔36項相差25個比特。也就是說，自fib（48）后便會導致32位無符號整數的溢出，自fib（94）后便會導致64位無符號整數的溢出。（1—21）考查fib（）算法的二分遞歸版，線性遞歸版和選代版。
a）分別編譯這些算法，針對n=64實際運行并測試對比；
b）三者的運行速度有何差別？為什么？
（解答）
請讀者通過實際動手，獨立完成實測和對比任務，并根據測試結果給出結論。
您曾經瀏覽過的商品
購物須知
大陸出版品因裝訂品質及貨運條件與台灣出版品落差甚大，除封面破損、內頁脫落等較嚴重的狀態，其餘商品將正常出貨。
特別提醒：部分書籍附贈之內容(如音頻mp3或影片dvd等)已無實體光碟提供，需以QR CODE 連結至當地網站註冊“並通過驗證程序”，方可下載使用。
無現貨庫存之簡體書，將向海外調貨：
海外有庫存之書籍，等候約45個工作天;
海外無庫存之書籍，平均作業時間約60個工作天，然不保證確定可調到貨，尚請見諒。
為了保護您的權益，「三民網路書店」提供會員七日商品鑑賞期(收到商品為起始日)。
若要辦理退貨，請在商品鑑賞期內寄回，且商品必須是全新狀態與完整包裝(商品、附件、發票、隨貨贈品等)否則恕不接受退貨。