四川理工算法設(shè)計(jì)與分析作者-王紅梅期末考試試題

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

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

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