一、填空题（20分）
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算法的思想。
3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。
4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。
5.设S=｛X1，X2，···，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)递归关系表达式为什么？
6.描述0-1背包问题。
三、简答题（30分）
1.流水作业调度中，已知有n个作业，机器M1和M2上加工作业i所需的时间分别为a i和b i，请写出流水作业调度问题的johnson法则中对a i和b i的排序算法。（函数名可写为sort(s,n)）
2.最优二叉搜索树问题的动态规划算法（设函数名binarysearchtree)）答案：
一、填空
1．确定性有穷性可行性 0个或多个输入一个或多个输出
2.时间复杂性空间复杂性时间复杂度高低
3. 该问题具有最优子结构性质
4.{BABCD}或{CABCD}或{CADCD｝
5.一个（最优）解
6.子问题子问题子问题
7.回溯法
8. o(n*2n) o(min{nc,2n})
9.最优子结构重叠子问题
10.动态规划法
二、综合题
1.①问题具有最优子结构性质；②构造最优值的递归关系表达式；
③最优值的算法描述；④构造最优解；
2. ①令N1={i|a i=b i}；②将N1中作业按a i的非减序排序得到N1’，将N2中作业按b i的非增序排序得到N2’；③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度。
3.步骤为：N1={1，3}，N2={2，4}；
N1’={1，3}， N2’={4，2}；
最优值为：38
4.解空间为{(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.二叉树T 的平均路长P=∑=+n i 1
Ci)(1*bi +∑=n
j 0
dj *aj
{
m[i][j]=0 (i>j)
6.已知一个背包的容量为C ，有n 件物品，物品i 的重量为W i ，价值为V i ，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 三、简答题
1.
void sort(flowjope s[],int n) {
m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]} (1<=i<=j<=n,m[i][i-1]=0)
int i,k,j,l;
for(i=1;i<=n-1;i++)//-----选择排序
{
k=i;
while(k<=n&&s[k].tag!=0) k++;
if(k>n) break;//-----没有a i，跳出
else
{
for(j=k+1;j<=n;j++)
if(s[j].tag==0)
if(s[k].a>s[j].a) k=j;
swap(s[i].index,s[k].index);
swap(s[i].tag,s[k].tag);
}
}
l=i;//-----记下当前第一个b i的下标
for(i=l;i<=n-1;i++)
{
k=i;
for(j=k+1;j<=n;j++)
if(s[k].b swap(s[i].index,s[k].index); //-----只移动index和tag swap(s[i].tag,s[k].tag); } } 2. void binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w) { int i,j,k,t,l; for(i=1;i<=n+1;i++) { w[i][i-1]=a[i-1]; m[i][i-1]=0; } for(l=0;l<=n-1;l++)//----l是下标j-i的差 for(i=1;i<=n-l;i++) { j=i+l; w[i][j]=w[i][j-1]+a[j]+b[j]; m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j]; s[i][j]=i; for(k=i+1;k<=j;k++) { t=m[i][k-1]+m[k+1][j]+w[i][j]; if(t { m[i][j]=t; s[i][j]=k; } } } } 一、填空题（本题15分，每小题1分） 1、算法就是一组有穷的，它们规定了解决某一特定类型问题的。 2、在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基 本计算模型是、、。 3、算法的复杂性是的度量，是评价算法优劣的重要依据。 4、计算机的资源最重要的是和资源。因而，算法的复杂性有和 之分。 5、f(n)= 6×2n+n2，f(n)的渐进性态f(n)= O( ) 6、贪心算法总是做出在当前看来的选择。也就是说贪心算法并不从整体最优考 虑，它所做出的选择只是在某种意义上的。 7、许多可以用贪心算法求解的问题一般具有2个重要的性质：性质和性 质。 二、简答题（本题25分，每小题5分） 1、简单描述分治法的基本思想。 2、简述动态规划方法所运用的最优化原理。 3、何谓最优子结构性质？ 4、简单描述回溯法基本思想。 5、何谓P、NP、NPC问题 三、算法填空（本题20分，每小题5分） 1、n后问题回溯算法 (1)用二维数组A[N][N]存储皇后位置,若第i行第j列放有皇后,则A[i][j]为非0值,否则值为0。 (2)分别用一维数组M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。 for(j=0;j if( 1 ) /*安全检查*/ { A[i][j]=i+1; /*放皇后*/ 2 ； if(i==N-1) 输出结果； else 3 ；; /*试探下一行*/ 4 ； /*去皇后*/ 5 ；; } 2、数塔问题。有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。 for(r=n-2;r>=0;r--) //自底向上递归计算 for(c=0; 1 ;c++) if( t[r+1][c]>t[r+1][c+1]) 2 ； else 3 ； 3、Hanoi算法 Hanoi(n,a,b,c) if （n==1） 1 ； else { 2 ； 3 ； Hanoi(n-1,b, a, c); } 4、Dijkstra算法求单源最短路径 d[u]:s到u的距离 p[u]:记录前一节点信息 Init-single-source(G,s) for each vertex v∈V[G] do { d[v]=∞; 1 } d[s]=0 Relax(u,v,w) if d[v]>d[u]+w(u,v) then { d[v]=d[u]+w[u,v]; 2 } dijkstra(G,w,s) 1. Init-single-source(G,s) 2. S=Φ 3. Q=V[G] 4.while Q<> Φ do u=min(Q) S=S∪{u} for each vertex 3 do 4 四、算法理解题（本题10分） 根据优先队列式分支限界法，求下 图中从v1点到v9点的单源最短路 径，请画出求得最优解的解空间树。 要求中间被舍弃的结点用×标记， 获得中间解的结点用单圆圈○框 起，最优解用双圆圈◎框起。 五、算法理解题（本题5分） 设有n=2k个运动员要进行循环赛， 现设计一个满足以下要求的比赛日程表： ①每个选手必须与其他n-1名选手比赛各一次； ②每个选手一天至多只能赛一次； ③循环赛要在最短时间内完成。 （1）如果n=2k，循环赛最少需要进行几天； （2）当n=23=8时，请画出循环赛日程表。 六、算法设计题（本题15分） 分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。 七、算法设计题（本题10分） 通过键盘输入一个高精度的正整数n(n的有效位数≤240)，去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n 和s，寻找一种方案，使得剩下的数字组成的新数最小。 【样例输入】 178543 S=4 【样例输出】 13 一、填空题（本题15分，每小题1分） 1．规则一系列运算 2. 随机存取机RAM(Random Access Machine)；随机存取存储程序机RASP(Random Access Stored Program Machine)；图灵机(Turing Machine) 3. 算法效率 4. 时间、空间、时间复杂度、空间复杂度 5．2n 6．最好局部最优选择 7. 贪心选择最优子结构 二、简答题（本题25分，每小题5分） 6、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问 题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 7、“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n 个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。 8、某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 9、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索， 解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。 10、P(Polynomial问题)：也即是多项式复杂程度的问题。 NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 NPC(NP Complete)问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。 三、算法填空（本题20分，每小题5分） 1、n后问题回溯算法 (1) !M[j]&&!L[i+j]&&!R[i-j+N] (2) M[j]=L[i+j]=R[i-j+N]=1; (3) try(i+1,M,L,R,A) (4) A[i][j]=0 (5) M[j]=L[i+j]=R[i-j+N]=0 2、数塔问题。 （1）c<=r (2)t[r][c]+=t[r+1][c] （3）t[r][c]+=t[r+1][c+1] 3、Hanoi算法 （1）move(a,c) （2）Hanoi(n-1, a, c , b) （3）Move(a,c) 4、（1）p[v]=NIL （2）p[v]=u (3) v∈adj[u] （4）Relax(u,v,w) 四、算法理解题（本题10分） 五、（1）8天（2分）； （2）当n=23=8时，循环赛日程表（3分）。 六、算法设计题（本题15分）1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 （1）贪心算法 O （nlog （n ）） ? 首先计算每种物品单位重量的价值Vi/Wi ，然后，依贪心选择策略，将尽可能多的 单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C ，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 ? 具体算法可描述如下： void Knapsack(int n,float M,float v[],float w[],float x[]) {Sort(n,v,w); int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) {if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; } （2）动态规划法 O(nc) m(i ，j)是背包容量为j ，可选择物品为i ，i+1，…，n 时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i ，j)的递归式如下。 void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=min(w[n]-1,c); for (j=0;j<=jMax;j++) /*m(n,j)=0 0= for (j=w[n];j<=c;j++) /*m(n,j)=v[n] j>=w[n]*/ m[n][j]=v[n]; for (i=n-1;i>1;i--) { int jMax=min(w[i]-1,c); for (j=0;j<=jMax;j++) /*m(i,j)=m(i+1,j) 0= for (j=w[i];j<=c;j++)/*m(n,j)=v[n] j>=w[n]*/ m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } i i i i w j w j j i m v w j i m j i m j i m <≤≥?? ?++-++=0),1(} ),1(),,1(max{),(n n n w j w j v j n m <≤≥???=00),( （3）回溯法O(2n) cw:当前重量cp:当前价值bestp：当前最优值 void backtrack(int i) //回溯法 i初值1 { if(i > n) //到达叶结点 { bestp = cp; return; } if(cw + w[i] <= c) //搜索左子树 { cw += w[i]; cp += p[i]; backtrack(i+1); cw -= w[i]; cp -= p[i]; } if(Bound(i+1)>bestp) //搜索右子树 backtrack(i+1); } 七、算法设计题（本题10分） 为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。 具体算法如下： 输入s, n; while（s > 0 ） { i=1; //从串首开始找 while (i < length(n)) && (n[i] {i++;} delete(n,i,1); //删除字符串n的第i个字符 s--; } while (length(n)>1)&& (n[1]=‘0’) delete(n,1,1); //删去串首可能产生的无用零 输出n; 算法设计与分析考试题 及答案 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 1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。 测试成绩：100.0分。恭喜您顺利通过考试！ 单选题 1. 简单地说，合作是：√ A 凝成团队的行动 B 凝成企业的行动 C 凝成组织的行动 D 凝成部门的行动 正确答案： A 2. 处于怠工的状态的员工特点不包括：√ A 眼里只有自己 B 恃才傲物 C 自命不凡 D 相信别人 正确答案： D 3. 管理就是要：√ A 使得员工都发挥其价值 B 使得每个人都发挥其价值 C 使得中层管理者都发挥其价值 D 使得高层管理者都发挥其价值 正确答案： B 4. 西方国家的生产线故意做成很多，这一段由你来做，那一段由他来做，这样做是为了：√ A 从某种程度上进行了分工 B 从某种程度上避免了偷懒 C 从某种程度上实现了合作 D 从某种程度上提高了效率 正确答案： B 5. “分裂繁殖制度”的提出者是：√ A 丰田 B 联想 C 微软 D 格兰仕 正确答案： D 6. 从业状态的员工的特点是：√ A 没尽全力，薪水却没少拿，感觉自己占了便宜 B 贡献出来的价值只有自身能力的50%～80% C 尽了全力，薪水也没少拿，感觉自己占了便宜 D 没尽全力，薪水却没少拿，感觉自己占了吃了亏正确答案： A 7. 建设和推进企业文化，要基于：√ A 现代精神 B 组织精神 C 团队精神 D 传统精神 正确答案： C 8. 对人心的训练，要靠：√ A 别人 B 企业 C 社会 D 自己 正确答案： D 9. 大雁是成人字形飞翔的原因是：√ A 可以增加阻力 B 使领头雁借助到别的大雁的力量而使自己飞翔 C 使每一只借助到别的大雁的力量而使自己飞翔 D 使除领头雁以外的每一只借助到别的大雁的力量而使自己飞翔 正确答案： D 10. 关于合作重要性的理解错误的是：√ A 一定程度上说，合作是关系到每个人的生存之道 B 合作精神应该是老总们、主管们关注的事 C 合作精神是一种团队精神 D 有没有团队精神，是关系着自己的生存与荣辱的，应该是每一个人的命题正确答案： B 11. 当企业文化倡导追求完美时，它应该是：√ A 深入每个领导的行动的 B 深入每个员工的骨髓、心灵的 C 深入每个员工的行动的 D 深入每个员工的工作的 正确答案： B 12. “拉绳实验”背后的作祟者是：√ A 行动 B 人情 C 人脉 D 人心 正确答案： D 13. 团队中的成员应该相互：√ A 对立 B 竞争 《复变函数》试卷 第1页（共4页） 《复变函数》试卷 第2页（共4页） XXXX 学院2016—2017学年度第一学期期末考试 复变函数 试卷 一、单项选择题（本大题共10小题，每题3分，共30分，请从每题备选项中选出唯一符合题干要求的选项，并将其前面的字母填在题中括号内。） 1. =)i Re(z ( ) A.)i Re(z - B.)i Im(z C.z Im - D.z Im 2. 函数2 ) (z z f =在复平面上 ( ) A.处处不连续 B. 处处连续，处处不可导 C.处处连续，仅在点0= z 处可导 D.处处连续，仅在点0=z 处解析 3.设复数a 与b 有且仅有一个模为1，则b a b a --1的值 ( ) A.大于1 B.等于1 C.小于1 D.无穷大 4. 设x y z f y x z i )(i +-=+=，，则=')(z f ( ) A.i 1+ B.i C.1- D.0 5.设C 是正向圆周 1=z ，i 2sin π=?dz z z C n ，则整数n 等于 ( ) A.1- B.0 C.1 D.2 6.0=z 是2 1 )( z e z f z -=的 ( ) A.1阶极点 B.2阶极点 C. 可去奇点 D.本性奇点 7.幂级数!2)1(0 n z n n n n ∑∞ =-的和函数是 ( ) A.z e - B.2 z e C.2 z e - D.z sin 8.设C 是正向圆周 2=z ，则 =?C z dz 2 ( ) A.0 B.i 2π- C.i π D.i 2π 9.设函数)(z f 在)0( 00+∞≤<<- 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-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 团队合作精神测试 当今社会的竞争日趋激烈，信息量成几何级增长。任何一个组织的成功都不能仅仅依靠某一个人单枪匹马作战，因此团队精神的重要性不言而喻。没有团队合作精神的人，将很难在这个社会立足。那么，来看看你的团队合作精神如何？ 1、当班级来了一个新同学，你会怎么做： A、这跟我没有太大关系； B、主动和他/她打招呼，帮助他/她尽快适应学校； C、他/她跟我主动打招呼后再去帮助他/她。 2、当班级组织体育活动时，你会： A、积极参与，即使自己体育不太好也会在旁边加油； B、不是强迫参加就不参加，忙自己的事情更重要； C、自己喜欢的项目就参加，不喜欢的就不参加。 3、当你和朋友一起聚餐点菜的时候，你会怎么做： A、点自己最喜欢吃的菜； B、点大多数朋友都比较喜欢吃的菜； C、点自己喜欢大家也还能吃的菜。 4、和几个朋友一起约定去景点玩的时候，你： A、总是比约定时间早到几分钟； B、一般是最晚到，让别人等你； C、有时候早到，有时候晚到。 5、你所参加的球队打比赛失败了，你会: A、抱怨那些没打好的人； B、鼓励大家不要气馁； C、让大家一起找出原因。 6、同学遇到不会做的题，而你正好会做，你会： A、如果是自己的竞争对手就不告诉他； B、给他讲一遍，如果还是不懂的话就让他去问别人； C、耐心地给他解答，直到他听懂为止。 7、宿舍同学生病的时候，你会： A、跟自己关系好就照顾照顾，不好就算了； B、人人都应该学会照顾自己，不能指望别人； C、仔细照顾他，为他做一些力所能及的事情。 8、宿舍熄灯后，你一般： A、已经忙好事情躺在床上了； B、忙一些事情，不时发出声响； C、忙一些事，但尽量轻手轻脚。 9、你的好朋友这次考试比你成绩好，你会： A、衷心地向他表示祝贺，并向他请教； B、表面表示祝贺，心里不太舒服； C、心里很不舒服，暂时先不理他。 10、对于那些学习成绩很差的人，一般情况下你会怎样看待他们： A、他们天生就比较笨，不想和他们打交道； B、他们可能是不够勤奋，再努力点就好了； C、他们在某些方面有我所不具有的优点。 《复变函数》考试试题（一） 一、 判断题（20分）： 1.若f(z)在z 0的某个邻域内可导，则函数f(z)在z 0解析. ( ) 2.有界整函数必在整个复平面为常数. ( ) 3.若 } {n z 收敛，则 } {Re n z 与 } {Im n z 都收敛. ( ) 4.若f(z)在区域D 内解析，且 0)('≡z f ，则C z f ≡)(（常数）. ( ) 5.若函数f(z)在z 0处解析，则它在该点的某个邻域内可以展开为幂级数. ( ) 6.若z 0是)(z f 的m 阶零点，则z 0是1/)(z f 的m 阶极点. ( ) 7.若 ) (lim 0 z f z z →存在且有限，则z 0是函数f(z)的可去奇点. ( ) 8.若函数f(z)在是区域D 内的单叶函数，则)(0)('D z z f ∈?≠. ( ) 9. 若f (z )在区域D 内解析, 则对D 内任一简单闭曲线C 0)(=? C dz z f . ( ) 10.若函数f(z)在区域D 内的某个圆内恒等于常数，则f(z)在区域D 内恒等于常数.（ ） 二.填空题（20分） 1、 =-?=-1||0 0)(z z n z z dz __________.（n 为自然数） 2. =+z z 22cos sin _________. 3.函数z sin 的周期为___________. 4.设 11 )(2+= z z f ，则)(z f 的孤立奇点有__________. 5.幂级数 n n nz ∞ =∑的收敛半径为__________. 6.若函数f(z)在整个平面上处处解析，则称它是__________. 7.若ξ =∞ →n n z lim ，则= +++∞→n z z z n n (i) 21______________. = )0,(Re n z z e s ，其中n 为自然数. 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(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、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 团队合作精神测试题 姓名：应聘岗位：日期：提示：每题的答案中有“A”、“B”、“C”三项选择，选出符合你心理行为的一项打“√”。 1、如果某位中学校长请你为即将毕业的学生举办一次介绍公司情况的晚间讲座，而那天晚上恰好播放你“追踪”的电视连续剧的最后一集，你是： A、立即接受邀请。 B、同意去，但要求改期。 C、以有约在先为由拒绝邀请。 2、如果某位重要客户在周末下午5：30打来电话，说他们购买的设备出了故障，要求紧急更换零部件，而主管人员及维修师均已下班，你是： A、亲自驾车去30公里以外的地方送货。 B、打电话给维修师，要求他立即处理此事。 C、告诉客户下周才能解决。 3、如果某位与你竞争激烈的同事向你借一本经营管理畅销书，你是： A、立即借给他。 B、同一借给他，但声明此书无用。 C、告诉他书被遗忘在火车上了。 4、如果某位同事为方便自己出去旅游而要求与你调换休息时间，在你还未决定如何度假的情况下，你是： A、马上应允。 B、告诉他你要回家请示夫人。 C、拒绝调换，推说自己已经参加旅游团了。 5、你如果在急匆匆地驾车去赴约途中看到你秘书的车出了故障，停在路边，你是： A、毫不犹豫地下车帮忙修车。 B、告诉他你有急事，不能停下来帮他修车，但一定帮他找修理工。 C、装作没看见他，径直驶过去。 6、如果某位同事在你准备下班回家时，请求你留下来听他“倾吐苦水”，你是： A、立即同意。 B、劝他等第二天再说。 C、以夫人生病为由拒绝他的请求。 7、如果某位同事因要去医院探望夫人，要求你替他去接一位乘夜班机来的大人物，你是： A、立即同意。 B、找借口劝他另找别人。 C、以汽车坏了为由拒绝。 8、如果某位同事的儿子想选择与你同样的专业，请你为他做些求职指导，你是： A、马上同意。 B、答应他的请求，但同时声明你的意见可能已经过时，他最好再找些最新资料作参考。 C、只答应谈及分钟。 9、你在某次会议上发表的演讲很精彩，会后几位同事向你索取讲话纲要，你是： A、同意-并立即复印。 B、同意-但并不十分重视。 C、同意-但转眼即忘记。 10、如果你参加了一个新技术培训班，学到了一些对许多同事都有益的知识，你是： A、返回后立即向大家宣布并分发才考资料。 B、只泛泛地介绍一下情况。 C、把这个课程贬得一钱不值，不泄漏任何信息。 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型: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.下面不是不合作的表现的是： 1. ?A? 明哲保身 2. ?B?怕担责任 3. ?C?有成就感 4. ?D?爱发牢骚 正确 2.处于怠工的状态的员工特点不包括： 1. ?A?眼里只有自己 2. ?B? 恃才傲物 3. ?C?自命不凡 4. ?D?相信别人 正确 3.西方国家的生产线故意做成很多，这一段由你来做，那一段由他来做，这样做是为了： 1. ?A? 从某种程度上进行了分工 2. ?B?从某种程度上避免了偷懒 3. ?C?从某种程度上实现了合作 4. ?D?从某种程度上提高了效率 正确 4.建设和推进企业文化，要基于： 1. ?A?现代精神 2. ?B?组织精神 3. ?C?团队精神 4. ?D?传统精神 正确 5.一个企业，门槛是最低的时候是： 1. ?A? 创业阶段 2. ?B? 成长阶段 3. ?C? 成熟阶段 4. ?D? 壮大阶段 错误 6.完成目标的必由之路是： 1. ?A? 合作和分工 2. ?B? 协从和协作 3. ?C? 合作和协从 4. ?D? 合作和协作 正确 7.一个人能力的施展是在： 1. ?A? 同一的阶段下表现出来的 2. ?B? 不同的阶段下表现出来的 3. ?C? 每一阶段中表现出来的 4. ?D? 任何的阶段中表现出来的 正确 8.关于合作重要性的理解错误的是： 1. ?A? 一定程度上说，合作是关系到每个人的生存之道 2. ?B?合作精神应该是老总们、主管们关注的事 3. ?C?合作精神是一种团队精神 4. ?D?有没有团队精神，是关系着自己的生存与荣辱的，应该是每一个人的命题 正确 9.员工要成为当下制度的受益者，必须： 1. ?A? 反对制度 2. ?B? 抵抗制度 3. ?C? 拒绝制度 4. ?D? 迎合制度 正确 10.不合作的后果由轻到重，依次呈现的，即： 1. ?A?缺乏成就感——怕担责任，爱发牢骚——会对团队和自己都缺少承诺——从业状态 ——怠工的状态——自我价值得不到淋漓尽致地发挥 2. ?B? 怕担责任，爱发牢骚——会对团队和自己都缺少承诺——缺乏成就感——从业状态 ——怠工的状态——自我价值得不到淋漓尽致地发挥 3. ?C? 怕担责任，爱发牢骚——缺乏成就感——会对团队和自己都缺少承诺——怠工的 状态——从业状态——自我价值得不到淋漓尽致地发挥 复变函数与积分变换期末试题 一．填空题（每小题3分，共计15分） 1． 2 3 1i -的幅角是（ 2,1,0,23±±=+-k k ππ）；2. )1(i Ln +-的主值是 （ i 4 32ln 21π + ）；3. 211)(z z f +=，=)0() 5(f （ 0 ），4．0=z 是 4sin z z z -的（ 一级 ）极点；5． z z f 1 )(=，=∞]),([Re z f s （-1 ）； 二．选择题（每题3分，共15分） 1．解析函数),(),()(y x iv y x u z f +=的导函数为（ ）； （A ） y x iu u z f +=')(； （B ）y x iu u z f -=')(； （C ） y x iv u z f +=')(； （D ）x y iv u z f +=')(. 2．C 是正向圆周3=z ，如果函数=)(z f （ ），则0d )(=?C z z f ． （A ） 23-z ； （B ）2)1(3--z z ； （C ）2)2()1(3--z z ； （D ）2 ) 2(3 -z . 3．如果级数∑∞ =1 n n n z c 在2=z 点收敛，则级数在 （A ）2-=z 点条件收敛 ； （B ）i z 2=点绝对收敛； （C ）i z +=1点绝对收敛； （D ）i z 21+=点一定发散． ４．下列结论正确的是( ) （A ）如果函数)(z f 在0z 点可导，则)(z f 在0z 点一定解析； (B) 如果)(z f 在C 所围成的区域内解析，则 0)(=? C dz z f （C ）如果 0)(=? C dz z f ，则函数)(z f 在C 所围成的区域内一定解析； （D ）函数 ),(),()(y x iv y x u z f +=在区域内解析的充分必要条件是 ),(y x u 、),(y x v 在该区域内均为调和函数． 5．下列结论不正确的是（ ）． (A) 的可去奇点；为z 1 sin ∞(B) 的本性奇点；为z sin ∞ (C) ;1sin 1 的孤立奇点为 z ∞(D) .sin 1的孤立奇点为z ∞ 三．按要求完成下列各题（每小题10分，共40分） （1）．设)()(2 2 2 2 y dxy cx i by axy x z f +++++=是解析函数，求 .,,,d c b a 解：因为)(z f 解析，由C-R 条件 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 一、填空题（每小题2分） 1、复数i 212-- 的指数形式是 2、函数w =z 1将Z S 上的曲线()1122=+-y x 变成W S (iv u w +=)上 的曲线是 3.若01=+z e ,则z ＝ 4、()i i +1= 5、积分()?+--+i dz z 2222= 6、积分 ?==1sin 21z dz z z i π 7、幂级数()∑∞ =+0 1n n n z i 的收敛半径R= 8、0=z 是函数 z e z 1 11- -的 奇点 9、=??? ? ??-=1Re 21z e s z z 10、将点∞,i,0分别变成0,i,∞的分式线性变换=w 二、单选题（每小题2分） 1、设α为任意实数，则α1=（ ） A 无意义 B 等于1 C 是复数其实部等于1 D 是复数其模等于1 2、下列命题正确的是（ ） A i i 2< B 零的辐角是零 C 仅存在一个数z,使得z z -=1 D iz z i =1 3、下列命题正确的是（ ） A 函数()z z f =在z 平面上处处连续 B 如果()a f '存在,那么()z f '在a 解析 C 每一个幂级数在它的收敛圆周上处处收敛 D 如果v 是u 的共轭调和函数,则u 也是v 的共轭调和函数 4、根式31-的值之一是（ ） A i 232 1- B 2 23i - C 223i +- D i 2 3 21+ - 5、下列函数在0=z 的去心邻域内可展成洛朗级数的是（ ） A z 1sin 1 B z 1 cos C z ctg e 1 D Lnz 6、下列积分之值不等于0的是( ) A ? =- 1 2 3 z z dz B ?=- 1 2 1 z z dz C ?=++12 42z z z dz D ?=1 cos z z dz 7、函数()z z f arctan =在0=z 处的泰勒展式为（ ） A ()∑∞ =+-0 2121n n n n z （z <1） B () ∑∞ =+-0 1 221n n n n z （z <1） C ()∑∞ =++-0 1 2121n n n n z （z <1） D () ∑∞ =-0 221n n n n z （z <1） 8、幂级数n n n z 20 1)1(∑∞ =+-在1 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 《复变函数》考试试题（一） 1、 =-?=-1||0 0)(z z n z z dz __________.（n 为自然数） 2.=+z z 2 2 cos sin _________. 3.函数z sin 的周期为___________. 4.设 11 )(2+= z z f ，则)(z f 的孤立奇点有__________. 5.幂级数 n n nz ∞ =∑的收敛半径为__________. 6.若函数f(z)在整个平面上处处解析，则称它是__________. 7.若ξ =∞ →n n z lim ，则= +++∞→n z z z n n (i) 21______________. 8. =)0,( Re n z z e s ________，其中n 为自然数. 9. z z sin 的孤立奇点为________ . 10.若0z 是)(z f 的极点，则___ )(lim 0 =→z f z z . 三.计算题（40分）： 1. 设 )2)(1(1 )(--= z z z f ，求)(z f 在} 1||0:{<<=z z D 内的罗朗展式. 2. .cos 1 1||?=z dz z 3. 设 ? -++=C d z z f λ λλλ1 73)(2，其中 }3|:|{==z z C ，试求).1('i f + 4. 求复数 11 +-= z z w 的实部与虚部. 四. 证明题.(20分) 1. 函数 )(z f 在区域D 内解析. 证明：如果|)(|z f 在D 内为常数， 那么它在 D 内为常数. 2. 试证 : ()f z = 在割去线段0Re 1z ≤≤的z 平面内能分出两 个单值解析分支, 并求出支割线0Re 1z ≤≤上岸取正值的那支在1 z =-的值. 《复变函数》考试试题（二） 二. 填空题. (20分) 一、填空题（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.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai算法设计与分析考试题及答案
中科院陈玉福计算机算法设计与分析期末简答题答案
网络学院团队精神考试答案
《复变函数》-期末试卷及答案(A卷)
算法设计与分析考试题及答案
算法设计与分析试卷(2010)
团队合作精神测试
复变函数考试试题与答案各种总结
算法设计与分析试卷(2010)
计算机算法设计与分析期末考试复习题
团队合作精神测试题
算法设计与分析试卷及答案
团队精神考试题及答案
复变函数与积分变换期末试题(附有答案)
算法设计与分析期末试题答案解析
复变函数试题及答案
算法设计与分析试卷及答案.doc
复变函数期末考试复习题及答案详解
算法设计与分析试题与答案
相关主题
文本预览