1、.一章 7 、 107.使用擴展遞歸技術(shù)求解下列遞推關(guān)系式:二章 1 、 3、 51 . 求下列問題的平凡下界, 并指出其下界是否緊密。( 1)求數(shù)組中的最大元素;(2 )判斷鄰接矩陣表示的無向圖是不是完全圖 ;( 3 )確定數(shù)組中的元素是否都是惟一的;(4 )生成一個具有 n 個元素集合的所有子集。3.畫出在 3 個數(shù) a ,b, c中求中值問題的決策樹 。5.假設(shè)某算法的時間復雜性為T( n)= 2n, 在計算機C1和 C2上運行這個算法 , C2的速度是C1 的 100倍 。若該算法在C1 上運行的時間為 t , 可處理的問題規(guī)模為 n, 在 C2上運行同樣的時間可處理的問題規(guī)模是多少?

2、如果 T( n) = n2, 在C2 上運行 同樣的時間可處理的問題規(guī)模是多少?3: 6 、 7 、 8.6.為 3 .4 .1節(jié)中生成排列對象算法設(shè)計程序上機實現(xiàn), 能對這個算法進行改進嗎?7.最近對問題也可以以k 維空間的形式出現(xiàn), k 維空間中的兩個點維空間的最近對問題設(shè)計蠻力算法, 并分析其時間性能。8.對于一個平面上n 個點的集合S , 設(shè)計蠻力算法求集合S 的凸包的一個極點。四章1 、 3 、棋盤覆蓋、最大子段和1 . 設(shè)計分治算法求一個數(shù)組中最大元素的位置, 建立該算法的遞推式并求解。3.設(shè)計遞歸算法生成n 個元素的所有排列對象。五章3、6、83.拿子游戲?？紤]下面這個游戲: 桌

3、子上有一堆火柴, 游戲開始時共有n 根火柴,.兩個玩家輪流拿走1 、2 、 3 或 4 根火柴, 拿走最后一根火柴的玩家為獲勝方。請為先走的玩家設(shè)計一個制勝的策略( 如果該策略存在) 。6.在 120枚外觀相同的硬幣中 , 有一枚是假幣 , 并且已知假幣與真幣的重量不同, 但不知道假幣與真幣相比較輕還是較重。可以通過一架天平來任意比較兩組硬幣 ,最壞情況下 , 能不能只比較5 次就檢測出這枚假幣 ?8.競 賽 樹 是 一 棵 完 全 二 叉 樹,它 反 映 了 一 系 列 “ 淘 汰 賽 ” 的 結(jié) 果:葉子代表參加比賽的 n 個選手, 每個內(nèi)部結(jié)點代表由該結(jié)點的孩子結(jié)點所代表的選手中的勝者, 顯然, 樹的根結(jié)點就代表了淘汰賽的冠軍。請回答下列問題:( 1)這一系列的淘汰賽中比賽的總場數(shù)是多少?(2 )設(shè)計一個高效的算法, 它能夠利用 比賽中產(chǎn)生的信息確定亞軍。六章1 、 2 、TSP 、多段圖.1 . 動態(tài)規(guī)劃法和分治法之間有什么共同點? 有什么不同點?2.用動態(tài)規(guī)劃法求圖中從頂點0 到頂點15的最短路徑, 寫出求解過程。七章TSP 、圖著色八章1 、 4 、背包問題、 TSP1