合工大算法设计与分析考试试卷 吴共庆.pdf

合工大算法设计与分析考试试卷吴共庆

1、以下关于算法设计问题的叙述中正确的是__________。

A、计算机与数值问题的求解——方程式求根、插值问题、数值

积分、函数逼近等有关

B、利用计算机无法解决非数值问题

C、计算机在解决分类、语言翻译、图形识别、解决高等代数和

组合分析等方面的数学

问题、定理证明、公式推导乃至日常生活中各种过程的模拟等

问题中，主要进行

的是判断、比较，而不是算术运算

D、算法设计与分析主要研究对象是非数值问题，当然也包含某

些数值问题

2、算法的特征包括_________。

A、有穷性B、确定性

C、输入和输出D、能行性或可行性

3、以下描述是有关算法设计的基本步骤：

①问题的陈述②算法分析③模型的拟制④算法的实现

⑤算法的详细设计⑥文档的编制，应与其它环节交织在一起

其中正确的顺序是__________。

A、①②③④⑤⑥B、①③⑤②④⑥

C、②④①③⑤⑥D、⑥①③⑤②④

4、以下说法正确的是__________。

A、数学归纳法可以证明算法终止性

B、良序原则是证明算法的正确性的有力工具

C、x=小于或等于x的最大整数（x的低限）

D、x=小于或等于x的最大整数（x的高限）

5、汉诺塔（Hanoi）问题中令h（n）为从A移动n个金片到C

上所用的次数，则递归方程

为__________，其初始条件为__________，将n个金片从A柱

移到C柱上的移动次数

是__________；设菲波那契（Fibonacci）数列中Fn为第n个

月时兔子的对数，则有递

归方程为__________，其中F1=F2=__________。

A、Fn=Fn-1+Fn-2B、h（n）=2h（n-1）+1

C、1D、h（1）=1

E、h（n）=2n-1F、0

6、在一个有向连通图中（如下图所示），找出点A到点B的一

条最短路为__________。

A、最短路：1→3→5→8→10，耗费：20

B、最短路：1→4→6→9→10，耗费：16

C、最短路：1→4→6→9，耗费：12

D、最短路：4→6→9→10，耗费：13