已知數(shù)列G（x）滿足：
G（1）=G（2）=G（3）=G（4）=1
G（x）=G（x-1）+G（x-2）+G（x-3）+G（x-4）（x≥5）
根據(jù)遞推式寫出求數(shù)列值的遞歸算法，問原始算法與采用函數(shù)值緩存的算法時間復(fù)雜度分別為多少？（）
A.O（n4）；O（n2）
B.O（5n）；O（1）
C.O（4n）；O（n）
D.O（5n）；O（n2）
您可能感興趣的試卷
你可能感興趣的試題
A.棧
B.列表
C.集合
D.字典
A.迷宮尋路
B.博物館大盜問題
C.二分查找
D.單詞最短編輯距離
A.圖像、語義識別
B.查找有序列表中某元素是否存在
C.計算兩個數(shù)的差
D.求斐波那契數(shù)列第N項的值
A.0.137
B.0.183
C.0.244
D.0.237
A.隊列
B.無序表
C.堆
D.棧
A.算法調(diào)用自身
B.有一個基本結(jié)束條件
C.能夠不斷減小問題規(guī)模
D.對函數(shù)運行結(jié)果進行緩存
A.插入刪除元素時不需要移動表中元素
B.順序存取
C.插入刪除元素時需要移動表中元素
D.隨機存取
A.插入刪除元素時需要修改指針
B.插入刪除元素時不必移動表中元素
C.插入刪除元素時需要移動表中元素
D.隨機存取
A.帶鏈的棧有棧頂指針和棧底指針，因此又稱為雙重鏈表
B.棧可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)的單鏈表實現(xiàn)
C.隊列可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)的雙向鏈表實現(xiàn)
D.節(jié)點中具有多個指針域的鏈表稱為多重鏈表
A.括號匹配算法需要棧結(jié)構(gòu)的參與
B.棧的pop操作時間復(fù)雜度是O（1）
C.棧的特性是后進先出（LIFO）
D.在Python中棧結(jié)構(gòu)可以由list來實現(xiàn)
最新試題
二叉樹的二叉鏈表類型定義如下：閱讀下列算法，并回答問題：（1）該算法的功能是什么？（2）以下算法功能是否等價于上面的算法？
設(shè)二叉樹采用二叉鏈表方式存儲，root指向根結(jié)點，r所指結(jié)點為二叉樹中任一給定的結(jié)點。則可以通過改寫（）算法，求出從根結(jié)點到結(jié)點r之間的路徑。
閱讀下列算法，并回答問題：設(shè)棧S=（1，2，3，4，5，6，7），其中7為棧頂元素。調(diào)用函數(shù)f30（S）后，（1）第一個循環(huán)結(jié)束后，棧T和隊列Q中的內(nèi)容各是什么？（2）第三個循環(huán)語句結(jié)束后，棧S中的內(nèi)容是什么？
則該隊列為空隊列的條件為（）
實現(xiàn)二分查找的遞歸章法如下，在相應(yīng)位置填寫適當(dāng)?shù)膬?nèi)容使算法完整。
若無向圖中任意兩個不同的頂點間都有路徑，則稱該圖為（）。
已知帶頭結(jié)點的鏈隊列指針Q，則該非空隊列取隊頭元素操作的語句是（）
一棵二叉樹的先序序列是：CEDBA，中序序列是：DEBAC ，則該二叉樹的后序序列是（）
在中序遍歷非遞歸算法中，在進入子樹進行訪問前，需要在自定義棧中保存（）
已知某二叉樹的后序遍歷序列是CEFDBA，中序遍歷序列是CBEDFA。與該二叉樹對應(yīng)的樹或森林中，葉子的數(shù)目是（）個。