当前位置：文档之家› 算法分析与设计及案例习题解析

算法分析与设计及案例习题解析

习题解析

第1章

1. 解析：

算法主要是指求解问题的方法。计算机中的算法是求解问题的方法在计算机上的实现。 2. 解析：

算法的五大特征是确定性、有穷性、输入、输出和可行性。 3. 解析：

计算n ????

的算法，其中n 是正整数。可以取循环变量i 的值从1开始，算i 的平方，

取平方值最接近且小于或者等于n 的i 即可。 4. 解析：

可以使用反证法，设i=gcd(m, n)=gcd(n, m mod n)，则设m=a*i ，n=b*i ，且a 与b 互质，这时m mod n=（a-x*b ）*i ，只需要证明b 和a-x*b 互质，假设二者不互质，可以推出a 与b 不互质，因此可以得到证明。 5. 解析：

自然语言描述：十进制整数转换为二进制整数采用“除2取余，逆序排列”法。具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

流程图：如图*.1

开始

输入n

长度len=(logn/log2)

len>=0

输出

(n>>len)&1)

len=len-1

结束

图*.1 十进制整数转换成二进制整数流程图

6. 解析：

a.如果线性表是数组，则可以进行随机查找。由于有序，因此可以进行折半查找，这样可以在最少的比较次数下完成查找。

b.如果线性表是链表，虽然有序，则只能进行顺序查找，从链表头部开始进行比较，当发现当前节点的值大于待查找元素值，则查找失败。

7. 解析：

本题主要是举例让大家了解算法的精确性。过程中不能有含糊不清或者二义性的步骤。大家根据可行的方式总结一下阅读一本书的过程即可。

8. 解析：

数据结构中介绍的字典是一种抽象数据结构，由一组键值对组成，各个键值对的键各不相同，程序可以将新的键值对添加到字典中，或者基于键进行查找、更新或删除等操作。由于本题已知元素唯一，因此大家可以据此建立一个自己的字典结构。实现字典的方法有很多种：

?最简单的就是使用链表或数组，但是这种方式只适用于元素个数不多的情况下；

?要兼顾高效和简单性，可以使用哈希表；

?如果追求更为稳定的性能特征，并且希望高效地实现排序操作的话，则可以使用更为复杂的平衡树。

在字典之上的主要操作可以有：创建操作，添加操作，删除操作，查找操作，以及必要的字典维护操作。

第2章

1. 解析：

根据本章所述，递归算法和非递归算法的数学分析方法分为5个步骤。 2. 解析：

本题相当于对多项式找“主项”，也就是在除去常系数外，影响函数值递增速度最快的项。

22310()n n n θ+∈

2(2)10

n n n θ+∈ c) 1

21()c n

θ+∈，c 为常数

32log (log )n n θ∈

e) 10log3()n n θ∈ 3. 解析：

本题中如果手套分左右手，则最优情况选2只，最差情况选12只。本题中如果手套不分左右手，则最优情况仍然选2只，最差情况选4只。

从本题的初衷推测设置题目应该是分左右手的手套，在考虑颜色的情况下，选择一双进行匹配。 4. 解析：

本题的一般解法可以使用高等数学中求二者比值的极限来确定结果。 a) 相同 b) 第一个小 c) 二者相同 d) 第一个大 e) 二者相同 f) 第一个小 5. 解析：

a) ()(1)555x n x n n =-+=- b) 1

()3(1)4*3n x n x n -=-=

c) *(1)

()(1)2

n n x n x n n -=-+=

d) ()()212

n x n x n n =+=-

6. 解析：

参见本章例2.7。

第3章

1. 解析：

蛮力法主要依靠问题的定义，采用简单直接的求解方法。由此决定了蛮力法是解决问题的最简单也是最普遍的算法，同时其经常作为简单问题求解的方法和衡量其他算法的依据。 2. 解析：

2，6，1，4，5，3，2

结束。

i=5：第六大值2就位，剩余的1也就位，排序结束。

3. 解析：

选择排序不稳定，如3.1.1节例子：4,4,2。冒泡排序稳定。

4. 解析：

如2题例子，到i=4时就没有发生交换的活动了。这时可以在冒泡排序的交换部分加入一个布尔变量，如本次循环中没有发生交换，则以后的扫描就可以不进行。

5. 解析：

如果n个点共线，则其最近对只需要考察相邻的点对，因此在对点进行按行坐标排序后，只需要两两计算相邻两点距离，就可以找到最近对。

6. 解析：

所有的过程与寻找二维空间中的最近点对类似，只是计算距离的公式变为：

sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z)

使用循环计算任意两个点之间的距离，然后记录最小值即可。

类似的，如果推广到n维空间，需要考虑空间中任意两点的距离计算公式，同样计算每两个点之间的距离，并记录最小距离即可。

7. 解析：

a) 线段的凸包为本身，极点为两个端点。

b) 正方形的凸包为本身，极点为四个顶点。

c) 正方形的边界不是凸包，凸包为正方形（包括边界和内部）。

d) 直线的凸包为本身，没有极点。

8. 解析：

哈密顿回路的穷举查找算法，首选选择起点（图中任意一个点开始），之后不断寻找下一个点，下一个点应该满足：

1) 不在已经走过的点中；

2)与上一个点有直连路径。

如果这样能找到回到起点的路径，并且遍历所有点，则为一条哈密顿回路。然后依次进行下一个可行点的选择。

9. 解析：

生成给定元素的一个排列，通过连续比较它们之间的元素，检查它们是否符合排序的要求。如果符合就停止，否则重新生成新的排列。

最差情况生成排列的个数是!n，每趟连续元素比较次数为n-1次。所以效率类型为

O n n 。

(!*(1))

第4章

1. 解析：

假定把16枚硬币上网例子看作一个大的问题。

（1）把这一问题分成两个小问题，随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组；这样，就把16个硬币的问题分成两个8个银币的问题来解决；

（2）判断A组和B组中是否有伪币，可以使用仪器比较A组硬币和B组硬币的重量；假如两组硬币重量相等，则可以判断伪币不存在；假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中；

（3）假设B是轻的那一组，因此再把它分成两组，每组有4个硬币，称其中一组为B1，另一组为B2，比较这两组，肯定有一组轻一些，假设B1轻，则伪币在B1中，再将B1分为两组，每组有两个硬币，称其中一组为B1a,另一组为B1b。比较这两组，可以得到一个较轻的组，由于这个组织有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪个硬币轻一些，轻币就是要找的伪币；

最终，比较次数为4次。

2. 解析：

逆序对是指在序列{a0,a1,a2...a n}中，若a ij)，则(a i,a j)上一对逆序对。而逆序数是指序列中逆序对的个数。例如：1 2 3是顺序，则逆序数是0；1 3 2中(2,3)满足逆序对的条件，所以逆序数只有1；3 2 1中(1,2)(1,3)(2,3)满足逆序对，所以逆序是3。由定义不能想象，序列n的逆序数范围在[0,n*(n-1)/2]，其中顺序时逆序数为0，完全逆序时逆序数是n*(n-1)/2。

对于一个数组s将其分为2个部分s1和s2，求s1和s2的逆序对个数，再求s1和s2合并后逆序对的个数：这个过程与merge排序的过程是一样的，可以使用merge排序求得。

代码如下：

//a为字符数组，len为字符数组的长度

int number = 0; //number表示逆序对的个数

void copy(char *dest, char *src, int l, int r)

{

while(l <= r)

{

dest[l] = src[l]; l++;

}

void mergeSort(char *a, int size)

{

char *b = (char*)malloc(sizeof(char) * size);

mergePass(a, b, 0, size - 1);

free(b);

}

void mergePass(char *a, char *b, int l, int r)

mergePass(a,b,m+1,r);

merge(a,b,l,m,r);

copy(a,b,l,r);

}

void merge(char *a, char *b, int l, int m, int r)

{

int i = l, j = m + 1;

while( i <= m && j <= r)

{

if(a[i] <= a[j]) b[l++] = a[i++];

while(i <= m) b[l++] = a[i++];

while(j <= r) b[l++] = a[j++];

}

3. 解析：

当序列A[1..n]中的元素的个数n=2时，通过直接比较即可找出序列的第2大元素。当n>2时，先求出序列A[1..n-1]中的第1大元素x1和第2大元素x2；然后，通过2次比较即可在三个元素x1，x2和A[n]中找出第2大元素，该元素即为A[1..n]中的第2大元素。SecondElement (A[low..high], max1, max2)

{ //假设主程序中调用该过程条件为high-low>=2

if(high-low==2)

{ if(A[low]

else { max2=A[high]; max1=A[low]; }

}

else

{ SecondElement (A[low .. high],x1,x2);

if(x1<=A[n]) {max2=max1; max1=A[n];}

else

if(x2>=A[n]) {max2=x2; max1=x1;}

else {max2=A[n]; max1=x1;}

}

该算法的时间复杂度满足如下递归方程：T(n)=T(n-1)+2; T(2)=1。解得T(n)=2n-3。

4. 解析：

如果在算法SELECT执行中每次标准元素都恰好选取的是序列中的真正中值元素，那算法的行为与二分查找算法类似。最坏情况下，每次在原序列的一半上进行查找。此时如果标准元素得到时间为T（n）；如果标准元素得到时间为T（1），则算法的最坏情况时间与二分检索一样，为T（logn）。

5. 解析：

对于两棵二叉树T1和T2，若其根结点值相同，且其左右子树分别对应相同，则T1=T2，否则T1≠T2。其描述如下：

Boolean BTEQUAL(BT T1, BT T2)

{

if(T1= =NULL&&T2==NULL) return True ; //均为空树

if(T1&&T2&&T1.data==T2.data&&BTEQUAL(T1.lchild,T2.lchild) &&BTEQUAL

(T1.lchild,T2.lchild)) return True;

return False;

}

6. 解析：

快速分类算法是根据分治策略设计出来的算法。其关键步骤就是“划分”：根据某个元素v为标准，将序列中的元素重新整理，使得整理后的序列中v之前的元素都不大于v，而v 之后的元素都不小于v。此时，元素v即找到了其最终的位置。要得到序列的排序结果，再只需对v之前的元素和v之后的元素分别排序即可，这可通过递归处理来完成。

7. 解析：

当序列中的元素都相同时，每次执行算法SPLIT时，仅出现一次元素交换，即将序列的第一个元素与最后一个元素交换，且划分元素的新位置为该序列的最后一个位置。因此，在元素均相同的数组A[1..n]上，算法QUICKSORT的执行特点为：每次划分后剩下A[1..n-2]未处理，…，第n-1此划分后剩下A[1]（已有序）。在这类实例上，算法的执行时间为：(n-1)+(n-2)+…+2+1=(n2)，属于最坏的情况。

此外，算法最后所得结果中各元素顺序如下：A[2],A[3],A[4],…,A[n],A[1]（这里，A[i]表示输入时的第i个元素，i=1,2,…,n）。

8. 解析：

算法QUICKSORT所需要的工作空间是指其递归执行时所需要的栈空间，其大小与递归调用的深度成比例。考虑算法在n个元素上执行时的递归调用树，树最高可为T(n)，最矮可为T(logn)。所以，算法所需的工作空间在T(logn)到T(n)之间变化。

第5章

1. 解析：

0个元素的幂集为空集；

1个元素的幂集为空集和本身；（可以看做空集并空集加入元素的集合）

2个元素的幂集为1个元素的幂集和该幂集中每个集合加入新元素的集合的并集；

类似的继续下去可以生成n个元素的幂集。

2. 解析：

插入排序：2，6，1，4，5，3，2

2| 6 1 4 5 3 2 i=1：A[1]插入

2 6| 1 4 5

3 2 i=2：A[2]插入

1 2 6| 4 5 3 2 i=3：A[3]插入

1 2 4 6| 5 3 2 i=4：A[4]插入 1 2 4 5 6| 3 2 i=5：A[5]插入 1 2 3 4 5 6| 2 i=6：A[6]插入 1

结束

3. 解析：

对照给出的算法，进行链表插入排序。这时，每次进行插入时均需要从链表头部节点开始，寻找插入位置。因此要设置相邻的两个指针，用于寻找插入位置。具体请大家自己完成。 4. 解析：

折半插入排序：

//输入：待排序数组A[0..n-1]

//输出：排好序后的数组A[0..n-1] void ISort(&A[0..n-1])

｛

/* v 用来保存待插入元素；s, t, k 分别是插入位置寻找时使用的指针，s 指向头，t

指向尾，k 指向中间。*/ for(i=1; i<=n-1; i++) { v=A[i]; s=0; t=i; k=??

??+2t s ; while(t>=s && v<>A[k]) { if(v<>A[k]) { s=k+1;

k=??

??+2t s ;

}; else { t=k-1; k=??

??+2t s ; };

};

if(A[k]

for(j=i-1; j>=k; j--)

最差效率为：(log )n n θ。 5. 解析：

用减一法进行拓扑排序，每次删除入度为0的结点即可，所有可能情况共有7种： d-a-b-c-g-e-f ；d-a-b-c-g-f-e ；d-a-b-g-c-e-f ； d-a-b-g-c-f-e ；d-a-c-b-g-e-f ；d-a-c-b-g-f-e ； d-a-b-g-e-c-f 。

同样，可以用深度优先遍历时，出栈顺序的逆序作为拓扑排序。 6．解析：

字典序列算法是一种非递归算法。而它正是STL 中Next_permutation 的实现算法。它的整体思想是让排列成为可递推的数列，也就是说从前一状态的排列，可以推出一种新的状态，直到最终状态。比如说，最初状态是12345，最终状态是54321。其实我觉得这跟我们手动做全排列是一样的。首先是12345，然后12354，然后12435，12453....逐渐地从后往前递增。

看看算法描述：

首先，将待排序列变成有序（升序）序列。然后，从后向前寻找，找到相邻的两个元素，Ti

接着，如果没有结束，从后向前找到第一个元素Tk，使得Tk>Ti(很多时候k=j)，找到它，交换Ti跟Tk，并且将Tj到Tn(Tn是最后一个元素)的子序列进行倒置操作。输出此序列。并回到第二步继续寻找ij。

例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下：

自右至左找出排列中第一个比右边数字小的数字4 839647521

在该数字后的数字中找出比4大的数中最小的一个5 839647521

将5与4交换839657421

将7421倒转839651247

所以839647521的下一个排列是839651247。

839651247的下一个排列是839651274。

int set[MAX]={1,2,3,4};

int flag=0;

//swap a and b

void swap(int *a,int *b)

//reverse a range of a set

void reverse(int start,int end)

{

int index_r=0;

int new_end=end-start;

for(index_r=0;index_r<=new_end/2;index_r++)

swap(&set[index_r+start],&set[new_end-index_r+start]); }

printf("%d ",set[index]);

printf("\n");

}

//find out all of the permutation in the set with first element 1 to n. void find_next()

{

set_print();

int index_i,index_j,index_k;

flag=0;

for(index_i=n-2;index_i>0;index_i--)

for(index_k=n-1;index_k>0;index_k--)

if(set[index_k]>set[index_i])

break;

swap(&set[index_i],&set[index_k]);

reverse(index_j,n-1);

swap(&set[0],&set[i]);

说到汉诺塔问题，首先想到的是最经典的递归解法。

在求格雷码的方法中，提到可以观察格雷码每一次改变的位数和汉诺塔每次移动的盘子的编号，从而产生一种不需要递归和堆栈的汉诺塔解法。

在生成格雷码的算法中，依次改变的位数是最低位和从右往左数第一个1所在位的左一位，对应汉诺塔的盘子就是最小的盘子和中间某个盘子。最小的盘子有两种可能的移动方案，其他的盘子只有一种可能。对于最小盘子移动到的柱子的解决方法是，根据观察，当盘子总数是奇数时，最小盘子的位置依次是“3->2->1->3->2->1...”；当总数是偶数时，这个顺序是“2->3->1->2->3->1...”。据此从格雷码到汉诺塔的一种对应解决方案就产生了。

for(i = 0; i < MAX; i++){

position[0] = circle[i];

i = (++i)%3;

FLIP_DIGIT(digit[0]);

}

else{

for(j = 0 ; j < n && digit[j]=='0'; j++)

FLIP_DIGIT(digit[j+1]);

cout<"<<6-position[j+1]-position[0]<

position[j+1] = 6-position[j+1]-position[0];

}

FLIP(even);

}

cout<<"========================="<

n m 52 34 26 68 13 136 6 272 +136 3 544

avg p n C n n n θ+=-+∈。最高效的排序算法其效率为：(log )n n θ。

因此，如果只做一次查找，不需要进行排序后再折半查找。 10. 解析：

构造2-3树的数据结构。之后建立插入节点和分裂的算法。

第6章

1. 解析：

以所经过的权值之和最大值为例进行说明。

行进的过程中，每次只有两种选择：向左或向右。一个有n 层的数字三角形的完整路径有2n 条，所以当n 比较大的时候，搜索全部路径，从中找出最大值，效率较低。

采用动态规划方法实现。

用d (i ,j )表示从位置(i ,j )出发时得到的最大值（包括位置(i ,j )本身），可以写出最大值的递归方程：

(,)(,)max{(1,),(1,1)}d i j a i j d i j d i j =++++

由于递归方程中包含了重复子问题，直接采用递归方程求解，效率较低。采用动态规划的备忘录方法，用一张二维表记录中间过程的值，可以把时间效率提高到n 2。 2. 解析：

采用动态规划方法实现。

用f[i]表示以a i 为结尾的最长上升子序列的长度，可建立如下递归方程：

1[][]11

[]max {[]1}

1j i a j a i i f i f j i <=<<

=??

=?+>??

f[]是单调递增的，因为如果有i=f[j]，那么f[i]必定可以被f[j]的内容所更新。每处理到一个a i ，要找到一个k 满足f[k –1]= a i ，并用a i 更新f[k]，最终max{k|f[k]!=∞}就是答案。

可以编写出时间复杂度为O (n 2)的动态规划算法。 3. 解析：

用sum[i,j ] 表示将从第i 颗石子开始的接下来j 颗石子合并所得的分值。用f [i,j ] 表示将第从第i 颗石子开始的接下来j 颗石子合并所得的重量的最小值。有如下递归方程：

0[,]min{[,][1,](,)}

i j

f i j f i k f k j sum i j i k j

+++<=

可以编写出时间复杂度为O (n 3)的动态规划算法。

如果采用四边形不等式优化动态规划算法，可得到时间复杂度为O (n 2)的动态规划算法，是一种比较高效的优化算法。 4. 解析：

按照动态规划求解多阶段决策的思路，每投资一个项目作为一个阶段，将原问题划分阶段，从而将静态模型转化为动态。用x k (k =1,2,3)表示第k 个项目的投资额，其中用s k 表示投资第k 个项目前的资金数(k =1,2,3,4，k =4为虚设的阶段)，则有0≤x k ≤s k 以及s k+1 = s k -x k 成立。用v k (s k , x k )表示在当前在资金数为s k ，投资额为x k 的情况下的投资效益值。为便于理解，如下图所示表示各阶段内容。

根据以上分析，可写出求解问题的递归式和特殊值：

4,0k k k k k k k k k k k f x v s x f s k s s x x st f x s s +++=+==-=??=??==?

万元

采用逆序倒推的方法，先计算在第三阶段，即投资项目3时的最大效益，再考虑第二阶段，即投资项目2时的最大效益，此时利用递归公式，其最大效益的获得是在所有在第二阶段的当前效益与第三阶段最大效益的累加和中求取最大值，同样方法获取第一阶段的最大效益。 5. 解析：

利用高斯公式，从1到n 的自然数之和为：1+2+3……+n=n*(n+1)/2 。

题目要求：对于从1到N 的连续整集合，划分为两个子集合，且保证每个集合的数字和是相等的。因而，划分之后每个子集全的数字应该为n*(n+1)/2的一半，即n*(n+1)/4由于两个子集中都是整数，所以n*(n+1)必为偶数，则可以设s=n*(n+1),并判断s%4 ，则，s/=4是划分之后子集合的数字和。

dyn[j]数组表示任意个数加起来等于j 的组数，则有下面公式成立：

dyn[j]= dyn[j]+dyn[j-i]; 其中dyn[j-i]表示加起来等于j-i 的组数，利用上述公式，可得到问题的解。 6. 解析：

a[i,j]保存第i 行第j 列的宝藏价值。令f[i,j]为从（1，1）走过第i 行第j 列时所能收集的宝藏的最大价值。有如下递归方程：

[,]max{[1,],[,1]}[,],1f i j f i j f i j a i j i n m =--+<=<=

同时满足：a[i,j]≠-1 初始 [1,1][1,1]f a =

采用动态规划算法，利用递推公式构造并求解二维表f[i,j]，目标即求解出f[n,m]即可。 7. 解析：

按照样例输入如下：

5 6 4 4 3 4 4 5

a[i]表示第i 首歌曲的长度。令f[i,j,k]表示前i 首歌曲，用j 张光盘，另加k 分钟能够发行的最多歌曲树木。有如下递归方程：

[,,]max{[1,,]

//[1,,[]]1

//[]:[1,1,[]]1//([])(1)}

f i j k f i j k i f i j k a i a i k k i

f i j t a i a i k and j k =---+<=---+>>=不刻录第首歌

分钟能够录制的歌曲分钟无法录制歌曲i 但还有光盘可用采用动态规划算法，利用递推公式构造并求解二维表f[i,j,k]，目标即求解出f[n,m,0]或f[n,m-1,t]即可。 8. 解析：

按照样例输入如下：

ACDEF ABCDE

令f[i,j]为将A 的前i 个字符变成B 的前j 个字符所用的最少操作步数。从后向前依次比较分析，f[i,j]有以下三种情况；

(1)删除A 中的前i-1 个字符中的最后一个字符，问题变为将A 中前i-1 个字符转换为B 中的前j 个字符，即：f[I,j]=f[i-1,j]+1;

(2)在A 的前i-1 个字符中的最后插入一个字符，插入后使a[i+1]=b[j]，问题变为将A 中的前i 个字符转换为B 中的前j-1 个字符，即：i[I,j]=f[i,j-1]+1;

(3)将A 中的一个字符转换为另一个字符。

如果a[i]=b[j]，则f[i,j]=f[i-1,j-1]

如果a[i]<>b[j]，将a[i] 换成b[j]；则f[i,j]=f[i-1,j-1]+1 综上所述，有如下递归方程：

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

算法设计与分析考试题及答案 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)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。

2015年算法分析与设计期末考试试卷B卷

西南交通大学2015 — 2016学年第(一)学期考试试卷课程代码 3244152课程名称算法分析与设计考试时间 120分钟阅卷教师签字： __________________________________ 填空题(每空1分，共15分) 1、程序是 (1) 用某种程序设计语言的具体实现。 2、矩阵连乘问题的算法可由 (2) 设计实现。 3、从分治法的一般设计模式可以看出，用它设计出的程序一般是 (3) 4、大整数乘积算法是用 (4) 来设计的。 5、贪心算法总是做出在当前看来 (5) 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 (6) o 6、回溯法是一种既带有 (7) 又带有 (8) 的搜索算法。 7、平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 (9) 类型 8、在忽略常数因子的情况下，0、门和0三个符号中， (10) 提供了算法运行时间的一个上界。 9、算法的“确定性”指的是组成算法的每条 (11) 是清晰的，无歧义的。 10、冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。 11、算法就是一组有穷 (13)，它们规定了解决某一特定类型问题的 (14) o 12、变治思想有三种主要的类型：实例化简，改变表现， (15) o 、 ___________________________________________________________________________________ L 线订装封密线订装封密、 __________________ 二线订装封密级班选择题(每题2分，共20 分)

系统与设计复习题

《系统分析与设计》复习题一．选择题： 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. 确定软件系统的模块结构

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

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.深度优先

算法设计与分析试卷(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

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

题目内容：一、单项选择题：（本大题共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、类图

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

湖南科技学院二○年学期期末考试信息与计算科学专业年级《算法设计与分析》试题考试类型:开卷试卷类型:C卷考试时量:1２０分钟题号一二三四五总分统分人得分阅卷人复查人一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14

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

一、选择填空 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. 人们的信息活动的规模不断扩大以致在国民经济中起主导作用的过程

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

算法分析与设计复习题及答案一、单选题 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.系统设计用来确定系统的结构，即系统的组成以及各组成成分之间的相互关系，详细设计用来确定模块内部的算法和数据结构，产生描述各模块程序过程的详细设计文档。系统设计是对系统分析的深化和细化，其目的是提出能够指导信息系统实现的设计方案。系统实施以系统分析

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

《算法分析与设计》期末试题及参考答案一、简要回答下列问题： 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

《算法分析与设计》期末复习题

一、选择题 1．一个.java文件中可以有（）个public类。 A．一个B．两个C．多个D．零个 2．一个算法应该是（） A．程序B．问题求解步骤的描述 C．要满足五个基本特性D．A和C 3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（）A．唯一性B．有穷性C．有0个或多个输入D．有输出 4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（） A．3，15，130，20，98，67B．3，15，20，130，98，67 C．3，15，20，67，130，98 D．3，15，20，67，98，130 5．下列关于算法的描述，正确的是（） A．一个算法的执行步骤可以是无限的B．一个完整的算法必须有输出 C．算法只能用流程图表示D．一个完整的算法至少有一个输入 6．Java Application源程序的主类是指包含有（）方法的类。 A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法 7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（） A．分治法B．减治法C．蛮力法D．变治法 8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。 A、import java.awt.* ; B、import java.applet.Applet ; C、import java.io.* ; D、import java.awt.Graphics ; 9．计算某球队平均年龄的部分算法流程图如图所示，其中：c用来记录已输入球员的人数，sum用来计算有效数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。

相关主题

 算法分析与设计考试题

史料教学案例设计解析

算法分析与设计考试

系统分析与设计考试题

算法分析与设计试卷

算法分析与设计试题

文本预览

相关文档

算法分析与设计考试题目

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

算法分析与设计试题

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

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

算法设计与分析课程期末试卷A卷自测

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

《算法分析与设计》期末考试复习题纲(完整版)

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

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

算法分析与设计试卷(答案)

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

2015年算法分析与设计期末考试试卷A卷

算法设计与分析期末考试卷及答案a.(优选)

算法分析与设计试题完整版

《算法分析与设计试卷2016-2017》

《算法分析与设计》期末考试复习题纲(完整版)

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

算法设计与分析考试题目及复习资料

算法分析与设计考试题目

最新文档

幼儿园小班科学《小动物过冬》PPT课件教案

2021年春新青岛版(五四制)科学四年级下册 20.《露和霜》教学课件

自然教育课件

小学语文优质课火烧云教材分析及课件

(超详)高中语文知识点归纳汇总

高中语文基础知识点总结(5篇)

高中语文基础知识点总结(最新)

高中语文知识点整理总结

高中语文知识点归纳

高中语文基础知识点总结大全

超详细的高中语文知识点归纳

高考语文知识点总结高中

高中语文知识点总结归纳

高中语文知识点整理总结

高中语文知识点归纳

高中语文知识点归纳(大全)

高中语文知识点总结归纳(汇总8篇)

高中语文基础知识点整理

化工厂应急预案

化工消防应急预案(精选8篇)