算法分析与设计习题集整理

算法分析与设计习题集整理

第一章算法引论

一、填空题：

1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括 时间复杂度 和 空间复杂度 。

2、多项式10()m m A n a n a n a =+++ 的上界为 O(n m ) 。

3、算法的基本特征： 输入、输出、确定性、有限性 。

4、如何从两个方面评价一个算法的优劣： 时间复杂度、空间复杂度 。

5、计算下面算法的时间复杂度记为： O(n 3) 。

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{c[i][j]=0;

for(k=1;k<=n;k++)

c[i][j]= c[i][j]+a[i][k]*b[k][j];

}

6、描述算法常用的方法： 自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。

7、算法设计的基本要求： 正确性 和 可读性 。

8、计算下面算法的时间复杂度记为： O(n 2) 。

for （i ＝1；i

{ y=y+1;

for （j ＝0；j <=2n ；j++ ）

x ＋＋；

}

9、计算机求解问题的步骤：问题分析、数学模型建立、 算法设计与选择 、 算法表示 、 算法分析 、 算法实现 、程序调试、结果整理文档编制。

1、按照时间复杂度从低到高排列：O( 4n 2)、O( logn)、O( 3n )、O( 20n)、O( 2)、O( n 2/3),

O( n!)应该排在哪一位？

答：O( 2)，O( logn)，O( n 2/3)，O( 20n)，O( 4n 2)，O( 3n )，O( n!)

2、什么是算法？算法的特征有哪些？

答：1）算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲，算法：就是解决问题的方法或过程。

2）特征：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性 ； ４)有穷性

3、给出算法的定义？何谓算法的复杂性？

计算下例在最坏情况下的时间复杂性？

for(j=1;j<=n;j++) (1)

for(i=1;i<=n;i++) (2) {c[i][j]=0; (3)

for(k=1;k<=n;k++) (4)

c[i][j]= c[i][j]+a[i][k]*b[k][j]; } (5)

答：1）定义：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。

2）算法的复杂性：指的是算法在运行过程中所需要的资源（时间、空间）多少。所需资源越多，表明算法的复杂性越高

3）该算法的主要元操作是语句5，其执行次数是n 3次。 故该算法的时间复杂度记

为O(n 3).

4、算法A 和算法B 解同一问题，设算法A 的时间复杂性满足递归方程

???>+===1n , n )2/n (T 4)n (T 1n , 1)n (T ，算法B 的时间复杂性满足递归方程

?

??>+===1n , n )4/n (aT )n (T 1n , 1)n (T ，若要使得算法A 时间复杂性的阶高于算法B 时间复杂性的阶，a 的最大整数值可取多少？

答：分别记算法A 和算法B 的时间复杂性为)n (T A 和)n (T B ，解相应的递归方程得：

)n (O )n (T 2A =

?????>=<=4a , )n

(O 4a , )n log n (O 4a , )n (O )n (T a log B 4

依题意，要求最大的整数a 使得)n (T B 〈)n (T A 。显然，当a<=4时，)n (T B 〈)n (T A ；当a>4时，)n (T B 〈(n)T A ?2a log 4< ?a<2

4=16。

所以，所求的a 的最大整数值为15。

5、算法分析的目的？

答：1)为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间；

2)是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。

6、算法设计常用的技术？（写５种）

答： ①分治法; ②回溯法； ③贪心法； ④动态规划法

⑤分治限界法 ； ⑥蛮力法； ⑦倒推法

三、算法设计题

1、蛮力法：百鸡百钱问题？

2、倒推法：穿越沙漠问题？

第二章 分治算法（1）----递归循环

一、填空题：

1、直接或间接地调用自身的算法称为 递归算法 ，用函数自身给出定义的函数称为 递归函数 。

2、递归方程 和 约束函数（递归终止条件）是递归函数的两个要素。

二、判断题：

1、所有的递归函数都能找到对应的非递归定义。 （ √ ）

2、定义递归函数时可以没有初始值。（ X ）

三、简答题：

1、什么是递归算法？递归算法的特点？

答：1 )递归算法:是一个模块（函数、过程）除了可调用其它模块（函数、过程）外，还可以直接或间接地调用自身的算法。

2) 递归算法特点：

①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件）

②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式）

2、比较循环与递归的异同？

答：相同：递归与循环都是解决“重复操作”的机制。

不同：①就效率而言，递归算法的实现往往要比迭代算法耗费更多的时间（调用和返回均需要额外的时间）与存贮空间（用来保存不同次调用情况下变量的当前值的栈栈空间），也限制了递归的深度。②每个迭代算法原则上总可以转换成与它等价的递归算法；反之不然。③递归的层次是可以控制的，而循环嵌套的层次只能是固定的，因此递归是比循环更灵活的重复操作的机制。

3、递归算法解题通常有三个步骤？

答： 1）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。

2）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。

3）设计函数、确定参数：和其它算法模块一样设计函数体中的操作及相关参数。

四、算法设计题：

1、楼梯上有n个台阶，上楼时可以上1步，也可以上2步，设计一递归算法求出共有多少种上楼方法F(n)。

①写出F(n)的递归表达式？

②并写出其相应的递归算法？

解：①写出F(n)的递归表达式

分析：到n阶有两种走法：

1）n-1阶到n阶；

2）n-2阶到n阶；

1 n=1

F(n) ＝ 2 n=2

F(n-1) + F(n-2) n>2

②写出其相应的递归算法？

Int F(int n)

{

if(n=1) return 1;

else if(n=2)

return 2;

else

return F(n-1)+ F(n-2);

}

2、设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：

规则1：每次只能移动1个圆盘；

规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；

规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。

①写出该问题的解题步骤？

②并写出其相应的递归算法？

解：①第一步：将n－1个盘子看成一个整体，从A移到C；

第二步：将第n个盘子移到B;

第三步：将n－1个盘子看成一个整体，从C移到B；

②写出其相应的递归算法：

void hanoi(int n, int a, int b, int c)

{if (n > 0)

{

hanoi(n-1, a, c, b);

move(a,b);

hanoi(n-1, c, b, a);

} }

第二章分治算法（2）分治算法

一、填空题：

1、在快速排序、插入排序和合并排序算法中，插入排序算法不是分治算法。

2、合并排序算法使用的是分治算法设计的思想。

3、二分搜索算法是利用分治算法思想设计的。

二、简答题：

1、适合用分治算法求解的问题具有的基本特征？

答：1)该问题的规模缩小到一定的程度就可以容易解决;

2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

4）利用该问题分解出子问题解可以合并为该问题解;

2、分治算法基本思想，解题步骤？

三、算法设计题：

1、改写二分查找算法：

设a[1…n]是一个已经排好序的数组，改写二分查找算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j；当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。

并分析其时间复杂度？

解：int binsearch( int a[n], int x ,) //x待查数据

{int mid, i , j; low=1;

int high=n;

while(low<=high)

{mid=(low+high)/2;

if(a[mid]=x) return i=j=mid;

if(a[mid]>x) high=mid-1; //继续在左边查找

else // (a[mid]

low=mid+1; //继续在右边查找

}

i=right; j=left;

return 0；//low大于high查找区间为空，查找失败 }

计算时间复杂性为O(logn)

2、棋盘覆盖在一个2k

×2

k

个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方

格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

求：①简述分治算法的基本思想？

②设计该棋盘覆盖问题的分治算法？

③计算所设计算法的时间复杂度？（要求写出递推公式）

解：①分解：

将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，以便各个击破，分而治之。

对这k个子问题分别求解：

如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止

求小问题解、合并：

将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

②、③

3、金块问题（求最大最小元问题）

老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。

求：①简述分治算法的基本思想？

②设计该金块问题的分治算法？

③计算所设计算法的时间复杂度？（要求写出递推公式）

答：①简述分治算法的基本思想：

问题可以简化为：在含n（n是2的幂（n>=2））个元素的集合中寻找极大元和极小元。

用分治法（二分法）可以用较少比较次数地解决上述问题：

1）将数据等分为两组（两组数据可能差1），目的是分别选取其中的最大（小）值。

2)递归分解直到每组元素的个数≤2,可简单地找到最大(小)值.

3）回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。

②、③

第三章动态规划算法

一、填空题：

1、动态规划算法中存储子问题的解是为了避免重复求解子问题。

2、（最优子结构）是问题能用动态规划算法求解的前提。

3、矩阵连乘问题的算法可由（ 动态规划 ）算法设计实现。

二、判断题：

1、动态规划算法基本要素的是最优子结构。 （ √ ）

2、最优子结构性质是指原问题的最优解包含其子问题的最优解。 （ √ ）

3、动态规划算法求解问题时，分解出来的子问题相互独立。 （ X ）

三、简答题：

1、动态规划算法解题步骤？

答：①找出最优解的性质，并刻划其结构特征;

（即原问题的最优解，包含了子问题的最优解）

②递归地定义最优值;

（即子问题具有重叠性，由子问题定义原问题）

③以自底向上的方式计算出最优值;

④根据计算最优值时得到的信息，构造最优解;

2、动态规划算法基本思想？

答：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题； 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次；

如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

3、动态规划与分治算法异同点？

4、动态规划算法的基本要素？

四、算法设计与计算题：

1、{}12,,,m X x x x =L 和{}12,,,n Y y y y =L 的最长公共子序列为{}12,,,k Z z z z =L 。 问：若用[][]c i j 记录序列{}12,,,i i X x x x =L 和{}

12,,,j j Y y y y =L 公共子序列长度。求：①用动态规划法求解时,计算最优值的递归公式？

②设计计算最优值的算法？以及构造最优解的算法？

2、长江游艇俱乐部在长江上设置了n 个游艇出租站1,2…n.游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。

游艇出租站i 到游艇出租站j 之间的租金为r(i ，j)，其中1<=i

求：①用动态规划法求解时,计算最优值（最少租金）的递归公式？

②设计计算最优值（最少租金）的算法？

③并分析其时间复杂度？

解：①

②计算最优值算法

public static void matrixChain(int [] p, int [][] m, int [][] s)

{ ?????<++==<≤j i j k r k i r j i j i r ]},1[],[{min 0],[j k i

int n=p.length-1;

for (int i = 1; i <= n; i++) m[i][i] = 0; //1个站

for (int r = 2; r <= n; r++)

for (int i = 1; i <= n - r+1; i++)

{ int j=i+r-1;

m[ i][ j] = m[i][i] + m[i+1][ j];

s[ i][ j] = i; //断点位置在i处

for (int k = i+1; k < j; k++)

{int t = m[ i][ k] + m[k+1][ j];

if (t < m[i][j])

{ m[ i][ j] = t; s[ i][ j] = k;}

} } }

构造最优解算法

public void traceback( int s[][],int I,int j)

{

if(i=j) return;

traceback( s, i, s[ i][ j] );

traceback( s, s[ i][ j]+1, j );

System.out.println(“A”+ i +“，”+ s[ i][ j] + “A”+ s[ i][ j]+1 +“,”

+ j )

} //(m[ i, s[ i][ j] ] ) (m[ s[ i][ j]+1, j ] )

③时间复杂度：O(n3)

第 4 章贪心算法

一、填空题：

1、某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱, 且取款的张数最少，统计所需各种币值(100,50,20,10,5,2,1元共七种)的张数。

贪心算法如下：

void greedy_zhaoling ( float GZ, int B[ ], int S[ ] ) //GZ应发工资

{ for( j=1, j<=7;j++) //贪心选择，依次给最大币种

{ A= GZ/B[ j] ; //A表示对应j币种张数

S[ j]= S[ j ]+A ; //S[ j]存放对应j币种总张数

GZ= GZ-A*B[ j] ; }

for(i=1;i<=7;i++)

print( B[ i] , “----”, S[ i] ); //输出币种和对应张数

}

2、贪心算法的两个基本要素是（贪心选择性）和（最优子结构）。

3、给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为M，应如何选择装入背包的物品，使得装入背包中物品的总价值最大。

贪心算法如下：

float greedy_knapsack ( float M, float w[ ], float p[ ], float x[ ] ) // x[ ]背包问题最优解, w[ ]物品重量， P[ ]物品价值

{ int n=w.length;

float pp=0;

float mm＝M; //pp计算当前总价值，mm背包剩余载重

for( int i=1;i<=n; i++ )

{ float ww[ i]= p[ i] / w[ i] ； //计算物品单位价值ww[ ]

x[ i]=0; } //初始化

Mergesort ( w[ ], n ); //按单位价值将物品排序，便于贪心选择

for( int i=1; i<=n; i++ ) //贪心选择，总是选择价值最大放入背包{ if ( w[ i]<=mm ) //当前物品小于背包剩余载重

{ x[ i]=1; mm= mm - w[ i] ; pp= pp + p[ i] ; } else { x[ i]=mm/w[ i]; pp= pp + x[ i]*p[ i] ; break; } //i部分放入背包

}

return pp;

}

二、判断题：

1、满足贪心选择性质必满足最优子结构性质。（ X ）

三、简答题：

1、贪心算法的基本思想？

2、贪心算法的基本要素？

3、贪心算法与动态规划算法的异同?

四、算法设计题：

1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝150，如果使用贪心方法求解此背包问题（背包不超载的前提下，装载的物品价值达到最大）。

①利用贪心算法求解该问题时，为了进行贪心选择，首先应该做什么？

然后进行贪心装载，给出一种正确的物品装载顺序？并给出其最优装载方案？

②利用贪心思想设计该普通背包问题的贪心算法？

③分析其时间复杂度？

解：① 1）依据不同的标准对这些物品进行排序，标准有重量、价值、单位价值；

2）重量从小到大：FGBAEDC ,得到的贪心解为：FGBAE 全部放入,D放入20% ，得到价值为165；

价值从大到小：DFBEGCA ，得到的贪心解为：DFBE 全部放入,G放入80% ，得到价值为189；

单位价值从大到小：FBGDECA ，得到的贪心解为：FBGD 全部放入,E放入87.5% ，得到价值为190.625；

3)显然使用单位价值得出最佳转载方案。

②、③

2、设有n个活动集合，其中每个活动都要求使用同一资源，如足球场，而在同一时间只能

有一个活动使用该资源。

每个活动i都有一个要求使用该资源起始时间si和结束时间fi，且si < fi；如果选择了活动i，则它在半开区间[si ， fi) 占用资源。

若两个活动[si ， fi)与[sj ， fj)不相交，则称活动i与活动j是相容的；

活动安排问题：就是在所给的活动集合中选出最大相容活动子集合；

求：①利用贪心算法求解该问题的基本思想？

②设计该活动安排问题的贪心算法？并分析其时间复杂度？

3、给定下图G＝(V, E)是一个无向连通图，对每一条边(v, w),其权值为c( v, w)；

求：①利用prim算法构造其最小生成树，画出其选边的过程？

并构造其算法？并分析其时间复杂度？

②利用kruskal算法构造其最小生成树，画出其选边的过程？

并构造其算法？并分析其时间复杂度？

4、对下图中的有向图，应用Dijkstra算法计算从源(顶点1)到其它顶点间最短路径的过程.

要求：给出Dijkstra算法的迭代过程，计算源到给个顶点的最短路径？（用表表示）解：见课本123页表4-2

解：迭代过程：

第５章 回溯算法

一、填空题

1、回溯法与分支限界法搜索方式不同，回溯法按 深度优先 搜索解空间，分支限界法按 广度优先或最小耗费优先 搜索解空间。

二、判断题

1、回溯法中限界函数的目的是剪去得不到最优解的子树。 （ √ ）

2、分支限界法类似于回溯法，也是一种在问题的解空间树T 上搜索问题解的算法，两者的搜索方式是相同的。 （ X ）

三、简答题

1、简述回溯法和分支限界法的相同点和不同点？

2、什么是子集树？ 什么是排列树？什么叫满m 叉树？

3、回溯算法的基本思想？ 回溯算法的解题步骤？

四、算法设计题

1、n 皇后问题

在4×4格的棋盘上放置彼此不受攻击的4个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。用回溯算法解决4皇后问题： ①构造求解该问题的解空间树？ ②设计该4皇后问题的回溯算法？ 解：①解空间树

②回溯算法

2、0－1背包问题：

假设有3个物品，它们的重量和价值如下表所示。若这些物品均不可以被分割，且背包容量M ＝10，问应该如何装入使背包中物品的总价值最大？

用回溯算法求解该0－1背包问题： ①构造求解该问题的解空间树？ ②设计该0－1背包问题的回溯算法？ 解：1）解空间树

;

3、图的着色问题：

如下图，给定无向连通图G 和m 种不同的颜色；用这m 种颜色为图G 的各个顶点着色，是否有一种方法使得图G 中每一条边的两个顶点着不同颜色；

求：①构造求解该问题的解空间树？ ②设计该图的着色问题回溯算法？

解：1）解空间树：

2）算法:

double mcoloring(int mm)

{int m=mm; //m 可用颜色数

double sum=0; //sum 当前着色方案数

backtrack( 1 ); //深度优先搜索解空间

return sum;

}

void backtrack( int t)

{ if ( t>n ) // 搜索到叶子节点

{ sum++; //着色方案数加1

for (int i=1; i<=n; i++)

system.out.print( x[ i] );

} //输出解,顶点i 着颜色x[ i]

else // 搜索到中间节点

{ for(int i=1; i<=m; i++)

{ x[ t]=i; //顶点t 着颜色i=1…m 1

2 3

4 5

if( ok( t ) ) backtrack(t+1);

}

}

}

boolean ok( int k) //当前着色顶点与以前相邻顶点是否同色

{ for(int j=1; j<=n; j++)

if( a[ k][ j]&&( x[ j]==x[ k] ) ) //数组a[][]是图的邻接矩阵

//当前顶点k到j有边：a[ k][ j]，且色同：x[ j]==x[ k]

return false;

else return true;}

③算法分析（m种颜色，n个节点）

计算限界函数，一重for循环时间复杂度：O(n);

在最坏的情况下每一个内节点都需要判断约束，内节点个数：1+m+m2+ m3+……+m n-1=(m n-1)/(m-1)个；

故图的m着色问题的回溯算法，时间复杂度为：O(n*m n)

第六章分支限界算法

一、填空题

1、按照活结点表的组织方式的不同，分支限界法包括队列式分支限界算法和优先队列式分支限界算法两种形式。

2、回溯法与分支限界法搜索方式不同，回溯法按深度优先搜索解空间，分支限界法按广度优先或最小耗费优先搜索解空间。

3、队列分支限界算法中，通常用队列实现，体现先进先出原则的原则。

4、优先队列式分支限界算法，通常采用堆实现。

6、回溯法与分支限界算法求解问题时，需要构造对该问题的解空间结构,其解空间结构通常有3种形式，分别是子集树、排列树、满m叉树。

二、判断题

1、分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的搜索方式是相同的。（X）

三、简答题

1、简述分支限界法的基本思想与解题步骤？

2、分支限界算法与回溯算法异同点？

四、算法设计题

1、0－1背包问题：

假设有3个物品，它们的重量和价值如下表所示。若这些物品均不可以被分割，且背包容量M＝10，问应该如何装入使背包中物品的总价值最大？

用分支限界算法求解该0－1背包问题：Array

①构造求解该问题的解空间树？

②给出队列式分支限界算法的求解过程？

如

③设计该0－1

背包问题的分支限界算法？并分析其时间复杂度？

（队列式分支限界，带上界函数）

２、多段图最短路径问题

求：①构造求解该问题的解空间树？

②给出队列式分支限界算法的求解过程？

③设计该问题的分支限界算法？并分析其时间复杂度？

（队列式分支限界，带上界函数）

解：

2）求解过程：

３）算法描述：法１:队列式分支限界法

double shortest( int i)

{ while (true) //队列不空，搜索问题的解空间

{ for ( int j=1; j<=n; j++) //儿子结点入队

{ if (a[ i][ j] < Float.MAX_VALUE) // 顶点i到顶点j可达

{ dist[ j]= dist[ i] +a[ i][ j]; // dist[ i]记录源到顶点ｉ的距离 p[ j]=enode.i; // p[ j]记录顶点j的前驱

enQueue(v[ j], j); // 结点j加入队列

}

}

ew = ((Integer) queue.remove()).intValue(); // 取队首下一扩展结点

if (ew == -1) // 同一层尾部标记ew = -1：同一层结点处理结束

{ if (queue.isEmpty()) return dist[ i]; //判断队列是否为空else { queue.put(new Integer(-1)); } // 同层结点尾部标志

ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点

i++; // 进入下一层

}

}

}

时间复杂度：

第七章概率算法

1、什么叫概率算法？

答：概率算法允许算法在执行的过程中随机选择下一个计算步骤。

2、概率算法有一个基本特征？

答：基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。

3、概率算法可以分为哪4类？

答：1)数值概率算法2)蒙特卡罗算法3)拉斯维加斯算法4)舍伍德算法

4、在概率算法中使用的随机数都是一定程度上随机的，即伪随机数；一般随机数通过线性同余法方法产生。

第8章 NP完全性理论

1、什么是易解问题？什么是难解问题？难解问题分为哪两类？

答：1）易解问题：人们将存在多项式时间算法的问题称为易解问题;

2）难解问题：将需要在指数时间内解决的问题称为难解问题；

3）难解问题有两类： 1）不可判定问题 2）非决定的难处理问题。

2、什么是不可判定问题？什么是非决定的难处理问题？

答：1）不可判定问题：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解它们的任何算法。

2）非决定的难处理问题：这类问题是可判定的（即可解的）。但是，这类问题即使使用非决定的计算机，也不能在多项式时间内求解它们。

3、什么是P类问题？什么是NP完全问题？

答：1）P类问题：是一类能够用确定性算法在多项式时间内求解的判断问题。事实上，所有易解问题都属于P类问题。

2）NP完全问题：对于某问题，很难找到其多项式时间的算法(或许根本不存在)，但是如果给了该问题的一个答案，则可以在多项式时间内判定或验证这个答案是否正确。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。

4、列出几个典型的NP完全问题？

答：（1）图着色问题COLORING

（2）路径问题LONG-PATH

（3）顶点覆盖问题VERTEX-COVER

（4）子集和问题SUBSET-SUM

（5）哈密尔顿回路问题HAM-CYCLE

（6）旅行商问题TSP

（7）装箱问题BIN-PACKING ，能否用k个箱子来装n个物品；

第九章近似算法

1、所有NP完全问题都还没有多项式时间的算法，然而许多NP完全问题都具有很重要的意

义，对于这类问题通常可以采取以下几种解题策略？

答：１）只对问题的特殊实例求解；２）用动态规划或分支限界法求解。

３）启发式方法求解；４）只求近似解

2、利用近似算法求解NP完全问题时，近似算法应该满足下面两个基本的要求？

答：1）算法的时间复杂性：要求算法能在n的多项式时间内完成。

2）解的近似程度：算法的近似解应满足一定的精度。

通常，用来衡量精度的标准有近似比和相对误差。

算法设计与分析考试题及答案

算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】

一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj

算法分析与设计试卷

《算法分析与设计》试卷(A) （时间90分钟满分100分） 一、填空题（30分,每题2分）。 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4．.广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5．衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6．Strassen矩阵乘法是利用（ A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是（ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题，最好用（ B ）算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14．下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。

系统与设计复习题

《系统分析与设计》复习题 一．选择题： 1.面向对象的特点主要概括为（C ）。 A. 可分解性、可组合性、可分类性 B. 继承性、封装性、 多态性 C. 抽象性、继承性、封装性、多态性 D. 封装性、易维护性、 可扩展性、可重用性 2.信息按照（ C ）可以分为战略信息、战术信息和作业信息。 A. 应用领域 B. 加工顺序 C. 管理的层次 D. 反映形式 3.按照处理的对象，可把组织的信息系统分为（B ）和管理 信息系统两大类。 A. 电子数据处理系统 B. 作业信息系统 C. 决策支持系统 D. 情报处理系统 4.在开发一个企业管理信息系统时，首先要进行用户调查，调查 中收集的主要信息包括（ D ）。 A. 管理目标、人力资源、业务流程和数据流程信息 B. 组织结构、功能体系、业务流程和数据流程信息 C. 企业性质、客户资源、业务流程和数据流程信息 D. 管理目标、功能体系、业务流程和数据流程信息 5.系统流程图也称为业务流程图，它表达的是（B ）。 A. 数据在系统各部件间的流动情况 B. 对数据进行加工

处理的控制过程 C. 逻辑数据流图 D. 白盒子形式的组成系统 的每个部件 6.一般子系统的划分是在系统（ C ）阶段，根据对系统的功 能/数据分析的结果提出的。 A. 需求分析 B. 逻辑阶段 C. 总体设计 D. 详细设计 7.信息系统流程图是以新系统的（ D ）为基础绘制的。 A. E-R图 B. 管理功能图 C. 业务流程图 D. 数据流图 8.在关系规范化过程中，一般来讲，满足（C ）的关系即可 满足信息处理的要求，就可以认为是比较规范的关系。 A. 第一范式 B. 第二范式 C. 第三范式 D. BC范式 9.信息系统开发的结构化方法的一个主要原则是（ A ）。 A. 自顶向下原则 B. 自底向上原则 C. 分步实施原则 D. 重点突破原则 10.用户开发应用系统的主要手段是（ A ）。 A. 生命周期法 B. 原型法 C. 第四代语言 D. 面向对象 方法 11.系统规划的主要任务包括（ A ）。 A. 明确组织的信息需求、制定系统总体结构方案 B. 对系统进行经济、技术和使用方面的可行性研究 C. 选择计算机和网络系统的方案 D. 确定软件系统的模块结构

《算法设计与分析》试卷A

《算法设计与分析》试卷 一．计算题（共25分） 1. 用表示函数f与g之间的关系。（10分，每小题2分） (1) f(n)=10000n g(n)=n-10000 (2) f(n)=2n g(n)=3n/n (3) f(n)=n3log2n g(n)=n2log3n (4) f(n)=log2n g(n)=log3n (5) f(n)=100n+n100 g(n)=n! 2.估计下列算法的时间复杂性的阶。(10分，每小题5分) (1)算法A的时间复杂性为， (2)算法B的时间复杂性为 3. 计算下面算法中count=count+1的执行次数（5分） 算法 COUNT count=0 for i=1 to for j=i to i+5 for k=1 to i2 count=count+1 end for end for end for 二．简答题（共15分） 1. 随机算法分成那几类，各有什么特点？（7分） 2．最大k乘积问题：设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。对于给定的I和k，求出I的最大k乘积。当用动态规划求解该问题时，最优子结构是什么？递归关系式是什么？（8分） 三．算法填空题（共45分，每空3分） 1. 以下是计算x m的值的过程 power ( x, m ) if m=0 then y=_____ (1)_______ else y=_____ (2)_______

装订 线 y=y*y if m 为奇数 then y=x*y

C=multiply( A , B) //计算两个矩阵乘积C=AB。 return C end if end matchain_product 3. 以下是迷宫问题的算法 算法 MAZE 输入：正整数m, n，表示迷宫的数组M[0..m+1, 0..n+1] (迷宫数据存于M[1..m, 1..n]中)，迷宫的入口位置(ix, iy),出口位置(ox, oy)。 输出：迷宫中入口至出口的一条通路，若无通路，则输出no solution。 M[0, 0..n+1]=M[m+1, 0..n+1]=1

算法设计与分析考试题及答案

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。

算法设计与分析试卷A及答案

考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------

考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------

参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x =

信息系统分析与设计考试相关习题及答案

一、选择填空 4. 业务系统规划法（BSP）的核心是（） A. 明确企业目标 B. 定义（识别）业务过程 C. 进行数据分析 D. 确定信息结构答案： C 5. 下面哪一项企业关键成功因素的特点是错误的：（）。 A. 少量的易于识别的可操作的目标 B. 可确保企业的成功 C. 由企业的所有CSF决定组织的信息需求答案： B 7. 一般子系统的划分是在系统（）阶段，根据对系统的功能/数据分析的结果提出的。 A. 需求分析 B. 逻辑阶段 C. 总体设计 D. 详细设计答案： A 10. 信息系统流程图是以新系统的（）为基础绘制的。 A. E-R图 B. 管理功能图 C. 业务流程图 D. 数据流程图答案： D 14. 信息系统开发的结构化方法的一个主要原则是（）。 A. 自顶向下原则 B. 自底向上原则 C. 分步实施原则 D. 重点突破原则答案： A 16. 一般来说，占维护工作比例最高的是（）。 A. 纠错性维护 B. 适应性维护 C. 完善性维护 D. 预防性维护答案： C 19. 系统规划的主要任务包括（）。 A. 明确组织的信息需求、制定系统总体结构方案 B. 对系统进行经济、技术和使用方面的可行性研究 C. 选择计算机和网络系统的方案 D. 确定软件系统的模块结构答案： A 20. 系统设计阶段的主要成果是（）。 A. 用户的决策方针 B. 用户的分析方案 C. 系统设计说明书 D. 系统总体设计方案答案： C 21. 信息系统建设的结构化方法中用户必须参与的原则是用户必须参与（）。 A. 系统建设中各阶段工作 B. 系统分析工作 C. 系统设计工作 D. 系统实施工作答案： A 22. 结构化生命周期法的主要缺点之一是（）。 A. 系统开发周期长 B. 缺乏标准、规范 C. 用户参与程度低 D. 主要工作集中在实施阶段答案： A 23. MIS规划的主要内容是（）。 A. MIS战略规划，组织信息需求分析，系统目标 B. 组织信息需求分析，系统目标，资源分配 C. MIS战略规划，资源分配，系统目标 D. MIS战略规划，组织信息需要分析，资源分配答案： A 28. 生命周期法的特点之一是（）。 A. 整个系统的开发工作是非劳动密集型的 B. 系统开发时间短 C. 对用户需求的变更不能做出迅速响应 D. 适合大型复杂系统答案： C 29. 系统测试中应遵循的一条原则是：测试工作应该由以下人员来承担（）。 A. 原程序作者 B. 专门的测试人员 C. 系统设计人员 D. 用户答案： B 30. 系统维护中要解决的问题来源于（）。 A. 系统分析阶段 B. 系统设计阶段 C. 系统实施阶段 D. 三者都包括答案： D 31. 在原型法中，原型是进行开发的系统的（）。 A. 反映用户最基本需求的可以运行的实验模型 B. 某一主要部分的详细设计方案（物理模型）

(完整版)算法设计与分析期末考试卷及答案a

一．填空题(每空 2 分，共30分) 1．算法的时间复杂性指算法中的执行次数。 2．在忽略常数因子的情况下，O、和三个符号中，提供了算法运行时间的一个上界。 3．设D n表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入 I 出现的概率，则算法的平均情况下时间复杂性A(n)= 。 4．分治算法的时间复杂性常常满足如下形式的递归方程： f (n) d , n n0 f(n) af(n/c) g(n) , n n0 其中，g(n)表示。 5. 分治算法的基本步骤包括。6．回溯算法的基本思想是。 7．动态规划和分治法在分解子问题方面的不同点是。 8．贪心算法中每次做出的贪心选择都是最优选择。 9．PQ 式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级 10．选择排序、插入排序和归并排序算法中，算法是分治算法。 11．随机算法的一个基本特征是对于同一组输入，不同的运行可能得到的结果。12. 对于下面的确定性快速排序算法，只要在步骤3 前加入随机 化步骤，就可得到一个随机化快速排序算法，该随机化步骤的功能是。 算法QUICKSORT 输入：n 个元素的数组A[1..n] 。 输出：按非降序排列的数组 A 中的元素

1. quicksort(1, n) end QUICKSORT ＿ ＿ 过程 quicksort(A, low, high) ＿ ＿ // 对 A[low..high] 中的元素按非降序排序。 ＿ 号 学 2. if low

5.《算法设计与分析》试题库

《算法分析与设计》试题库 （一） 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B.分支限界法 C.分治法 B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move( n, a,b); hanoi(n-1, C, B, A); 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座 B 上，并 D.动态规划算法

3. 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C.最优子结构性质与重叠子问题性质

D.预排序与递归调用 4. 算法分析中，记号0表示(B),记号0表示(A),记号。表示(D) A. 渐进下界 B. 渐进上界 C. 非紧上界 D. 紧渐进界 E. 非紧下界 5. 以下关于渐进记号的性质是正确的有：(A) A. f(n) - P(g(n)),g(n) - 心(h(n))二f(n) - P(h(n)) B. f(n) =0(g(n)),g(n) =0(h(n))二h(n) =0(f(n)) C. O(f(n ))+0(g( n)) = O(mi n{f(n ),g( n)}) D. f(n) =0(g(n)) = g(n) -0(f (n)) 6?能采用贪心算法求最优解的问题，一般具有的重要性质为：(A) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C. 最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7.回溯法在问题的解空间树中，按(D)策略，从根结点出发搜索解空间树。 A. 广度优先 B.活结点优先 C.扩展结点优先 D.深度优先

软件系统分析与设计考试题

题目内容： 一、单项选择题：（本大题共20小题，每题1分，共20分） ? 1. 组成UML有三种基本的建筑块是：（?A ），事物和图 A、关系?????????????????? B、类 C、用例?????????????????? D、实体 2、UML体系包括三个部分：UML基本构造块，（?A ）和UML公共机制 A、UML规则????????????? B、UML命名 C、UML模型????????????? D、UML约束 3、UML中的事物包括：结构事物，分组事物，注释事物和（ D) A、实体事物?????????? ???????? B、边界事物 C、控制事物?????????????????? D、动作事物 4、（ A）模型的缺点是缺乏灵活性，特别是无法解决软件需求不明确或不准确的问题 A、瀑布模型?????????????????? B、原型模型 C、增量模型?????????????????? D、螺旋模型 5、下面哪个不是UML中的静态视图（A? ） A.状态图??????????????????? B.用例图 C.对象图??????????????????? D.类图 6、（?A ）技术是将一个活动图中的活动状态进行分组，每一组表示一个特定的类、人或部门，他们负责完成组内的活动。 ? A、泳道??????????????????? B、分叉汇合 ? C、分支??????????????????? D、转移 7、下列关于状态图的说法中，正确的是（ C ） A. 状态图是UML中对系统的静态方面进行建模的五种图之一。 B. 状态图是活动图的一个特例，状态图中的多数状态是活动状态 C.活动图和状态图是对一个对象的生命周期进行建模，描述对象随时间变化的 行为。 D. 状态图强调对有几个对象参与的活动过程建模，而活动图更强调对单个反应 型对象建模 8、对反应型对象建模一般使用（?A ）图 A、状态图??????????????????? B、顺序图 ?C、活动图??????????????????? D、类图

信息系统分析与设计考试题库及答案

一、选择填空 1. 信息按照（C ）可以分为战略信息、战术信息和作业信息）可以分为战略信息、战术信息和作业信息。 A. 应用领域 B. 加工顺序 C. 管理的层次 D. 反映形式 2. 按照处理的对象，可把组织的信息系统分为( B ) 和管理信息系统两大类。按照处理的对象，可把组织的信息系统分为) 和管理信息系统两大类。 A. 电子数据处理系统 B. 作业信息系统 C. 决策支持系统 D. 情报处理系统 3. 信息系统对管理职能的支持，归根到底是对( D ) 的支持。 A. 计划 B. 组织 C. 控制 D. 决策 4. 业务系统规划法（BSP）的核心是（C ） A. 明确企业目标 B. 定义（识别）业务过程 C. 进行数据分析 D. 确定信息结构 5. 下面哪一项企业关键成功因素的特点是错误的：（ B ）。 A. 少量的易于识别的可操作的目标 B. 可确保企业的成功 C. 由企业的所有CSF决定组织的信息需求 6. 下面哪一项不是信息系统局部开发层次的优势：（ D ）。 A. 相对简单的IT开发 B. 帮助理论的证明 C. 组织变化的阻力最小 D. 优化组织过程 7. 一般子系统的划分是在系统（ A ）阶段，根据对系统的功能/数据分析的结果提出的。 A. 需求分析 B. 逻辑阶段 C. 总体设计 D. 详细设计 8. 在新产品开发机构重组中，以开发某一新产品为目标，组织集设计、工艺、生产、供应、检验人员为一体的承包组，打破部门的界限，实行团队管理，以及将设计、工艺、生产制造并行交叉的作业管理，这属于（ C ）。 A. 功能内的BPR B. 组织间的BPR C. 功能间的BPR D. 功能内的BPR 9. 数据存贮设计则根据数据资源分布具体确定了数据存贮的（ A ）。 A. 逻辑方式 B. 物理方式 10. 信息系统流程图是以新系统的（ D ）为基础绘制的。 A. E-R图 B. 管理功能图 C. 业务流程图 D. 数据流程图 11. 在关系规范化过程中，一般来讲，满足（ C ）的关系即可满足信息处理的要求，就可以认为是比较规范的关系。 A. 第一范式 B. 第二范式 C. 第三范式 D. BC范式 12. RUP中的软件生命周期在时间上被分解为四个顺序的阶段，分别是：初始阶段(Inception)、细化阶段(Elaboration)、构造阶段(Construction)和交付阶段(Transition)，每个阶段结束于一个主要的里程碑(Major Milestones)。构建阶段结束时是第三个重要的里程碑：( C ) A. 生命周期目标(Lifecycle Objective)里程碑 C. 初始功能(Initial Operational)里程碑 B. 生命周期结构(Lifecycle Architecture)里程碑 D. 产品发布(Product Release)里程碑 13. 从社会经济发展的角度来看，信息化是指（ D ）。 A. 计算机和网络的应用规模与效益不断增长的过程 B. 社会上进行交换的信息量不断增长的过程 C. 计算机硬件产业、软件产业、信息服务产业不断发展的过程 D. 人们的信息活动的规模不断扩大以致在国民经济中起主导作用的过程

算法分析与设计模拟试卷A

算法设计与分析期末考试模拟试卷 A卷 考试说明： 承诺： 本人已学习了《北京工业大学考场规则》和《北京工业大学学生违纪处分条例》，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。若有违反，愿接受相应的处分。 承诺人：学号：班号： 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。注：本试卷共三大题，共 6 页，满分100分，考试时答案请写在试卷空白处。 一、算法时间复杂性问题（共30分） Part 1. The Time Complexity Of the Algorithm Test 1、试证明下面的定理：[12分] (1) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)+g(n)=O(s(n)+r(n)) (2) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)*g(n)=O(s(n)*r(n)) 1. Prove the following Theorem [12 marks] (1) if f(n)=O(s(n)) and g(n)=O(r(n)), to prove f(n)+g(n)=O(s(n)+r(n)) (2) if f(n)=O(s(n)) and g(n)=O(r(n))，to prove f(n)*g(n)=O(s(n)*r(n))

2、已知有如下的断言： f(n)=O(s(n))并且g(n)=O(r(n))蕴含f(n)-g(n)=O(s(n)-r(n)) 请你举出一个反例。[8分] 2. Known as the following assertion If f(n)=O(s(n)) and g(n)=O(r(n))，then f(n)-g(n)=O(s(n)-r(n)) 。 Please cite a counter-example [8 marks] 3、假设某算法在输入规模为n时的计算时间为：T（n）=3*2n，在A型计算机上实现并完成该算法的时间为t秒，现有更先进的B型计算机，其运算速度为A 型计算机的256倍。试求出若在先进的B型机上运行同一算法则在t秒内能求解输入规模为多大的问题？[10分] 3. Assume that in the case of the input size is n, the computing time of the algorithm required is T（n）=3*2n. It would take t seconds to implement the algorithm on Computer A. Computer B is more advanced. The operation ability of Computer B is 256 times of Computer A. If the same algorithm running on Computer B, please find out the input size so that the algorithm would solve in t seconds.[10 marks]

算法分析与设计复习题及答案

算法分析与设计复习题及答案一、单选题 1．D 2．B 3．C 4．D 5．D 6．D 7．C 8．D 9．B 10．C 11．D 12．B 13．D 14．C 15．C 16．D 17．D 18．D 19．D 20．C 1．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 2．根据执行算法的计算机指令体系结构，算法可以分为（）。 Ａ精确算法与近似算法Ｂ串行算法语并行算法 Ｃ稳定算法与不稳定算法Ｄ３２位算法与６４位算法 3．具有１0个节点的完全二叉树的高度是（）。 Ａ６Ｂ５Ｃ3Ｄ 2 4．下列函数关系随着输入量增大增加最快的是（）。 Ａlog2n B n2 C 2n D n! 5．下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6．Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7．4个盘子的汉诺塔，至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8．下列序列不是堆的是（）。 A 99，85，98，77，80，60，82，40，22，10，66 B 99，98，85，82，80，77，66，60，40，22，10 C 10，22，40，60，66，77，80，82，85，98，99 D 99，85，40，77，80，60，66，98，82，10，22 9．Strassen矩阵乘法的算法复杂度为（）。 ＡΘ(n3)ＢΘ(n2.807) ＣΘ(n2) ＤΘ(n) 10．集合A的幂集是（）。 A．A中所有元素的集合 B. A的子集合 C． A 的所有子集合的集合 D. 空集 11．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 12．从排序过程是否完全在内存中显示，排序问题可以分为（）。 Ａ稳定排序与不稳定排序Ｂ内排序与外排序 Ｃ直接排序与间接排序Ｄ主排序与辅助排序 13．下列（）不是衡量算法的标准。 Ａ时间效率Ｂ空间效率 Ｃ问题难度Ｄ适应能力 14．对于根树，出度为零的节点为（）。 Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分支节点 15．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（）。 Ａ０Ｂ２Ｃ４Ｄ６ 16．下列程序段的算法时间的复杂度为（）。 for i ←0 to n do for j ←0 to m do

系统分析与设计复习题

《系统分析与设计》复习题 一、复习要点 1.系统是由处于一定环境中的若干相互联系和相互作用的要素组成并为达到整体目的而存在的集 合。 2.信息系统是指利用计算机、网络、数据库等现代信息技术，处理组织中的数据、业务、管理和 决策等问题，并为组织目标服务的综合系统。信息系统开发的步骤是，在系统规划后，循环进行系统分析、系统设计、系统构建与实施、系统评价工作。信息系统的经济效益可分为三大类：一次性收益，非一次性收益和不可定量的收益 3.系统规划阶段的任务是对组织的环境、战略、目标、现行系统的状况进行初步调查，根据组织 目标和发展战略，确定信息系统的发展战略，对建设新系统的需求做出分析和预测，同时考虑建设新系统所受的各种约束，研究建设新系统的必要性和可能性。对于确定的信息系统项目，要明确其目标，并对目标进行权衡和量化。 4.系统分析的主要活动有系统初步调查、系统可行性研究、系统详细调查研究和新系统逻辑方案 的提出，主要任务是尽可能弄清用户对信息的需求，完成新系统的逻辑设计，规定新系统应当做什么。 5.常用的调查研究的方法有问卷调查法、召开调查会、业务实践、专家访谈、电子问卷。如果系 统初步调查结果表明，拟开发项目有必要也有可能进行时，可向主管单位提出系统开发建议书,需要进行可行性研究安排。 6.可行性研究又叫可行性分析，它是所有工程项目在开始阶段必须进行的一项工作。可行性研究 是指项目正式开发之前，先投入一定的精力，通过一套准则，从经济、技术、社会等方面对项目的必要性、可能性、合理性，以及项目所面临的重大风险进行分析和评价，得出项目是否可行的结论。可行性研究的主要成果是可行性研究报告和系统开发任务书。 7.需求分析是强调用户对新开发的信息系统的需要和要求，结合组织的目标、现状、实力和技术 等因素，通过深入细致的分析，确定出合理可行的信息系统需求，并通过规范的形式描述需求的过程。需求分析结束时，应当提出需求分析报告交上级审查。信息系统需求分为功能需求和非功能需求两类。 8.系统设计用来确定系统的结构，即系统的组成以及各组成成分之间的相互关系，详细设计用来 确定模块内部的算法和数据结构，产生描述各模块程序过程的详细设计文档。系统设计是对系统分析的深化和细化，其目的是提出能够指导信息系统实现的设计方案。系统实施以系统分析

算法设计与分析试卷(2010)

内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

《算法分析与设计》期末试题及参考答案

《算法分析与设计》期末试题及参考答案 一、简要回答下列问题： 1.算法重要特性是什么？ 1.确定性、可行性、输入、输出、有穷性 2. 2.算法分析的目的是什么？ 2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 3.算法的时间复杂性与问题的什么因素相关？ 3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。 4.算法的渐进时间复杂性的含义？ 4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的 算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 6.简述二分检索（折半查找）算法的基本过程。 6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较， 如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]

信息系统分析与设计考试题库和答案1.doc

信息系统分析与设计考试题库和答案1 信息系统分析与设计考试题库及答案 一,选择填空 1. 信息按照( )可以分为战略信息,战术信息和作业信息)可以分为战略信息,战术信息和作业信息. A. 应用领域 B. 加工顺序 C. 管理的层次 D. 反映形式 答案: C 2. 按照处理的对象,可把组织的信息系统分为( ) 和管理信息系统两大类. A. 电子数据处理系统 B. 作业信息系统 C. 决策支持系统 D. 情报处理系统 答案: B 3. 信息系统对管理职能的支持,归根到底是对( ) 的支持.

A. 计划 B. 组织 C. 控制 D. 决策 答案: D 4. 业务系统规划法(BSP)的核心是( ) A. 明确企业目标 B. 定义(识别)业务过程 C. 进行数据分析 D. 确定信息结构 答案: C 5. 下面哪一项企业关键成功因素的特点是错误的: ( ). A. 少量的易于识别的可操作的目标 B. 可确保企业的成功 C. 由企业的所有CSF决定组织的信息需求 答案: B 6. 下面哪一项不是信息系统局部开发层次的优势:( ).

A. 相对简单的IT开发 B. 帮助理论的证明 C. 组织变化的阻力最小 D. 优化组织过程 答案: D 7. 一般子系统的划分是在系统( )阶段,根据对系统的功能/数据分析的结果提出的. A. 需求分析 B. 逻辑阶段 C. 总体设计 D. 详细设计 答案: A 8. 在新产品开发机构重组中,以开发某一新产品为目标,组织集设计,工艺,生产,供应,检验人员为一体的承包组,打破部门的界限,实行团队管理,以及将设计,工艺,生产制造并行交叉的作业管理,这属于( ). A. 功能内的BPR B. 组织间的BPR C. 功能间的BPR