大学算法设计与分析课期末试题.pdf

一填空题 (选做 5 道 10 分 ) 1 用矩阵幂的方法求斐波那契数其运行时间为 . 2 对于一个可以用动态规划法求解的问题要求问题既要满足的特性又要具有大量 的 . 3 对于一个可以用贪心法求解的问题不仅要求问题满足的特性还应证明其贪心策 略的 . 4 设有 n 个栈操作 PUSH POPMULTIPOP 的序列作用于初始为空的栈 S.不区分三 种操作则每个操作的最坏运行时间为平摊运行时间为