算法设计与分析(第2版) 王红梅 胡明 习题答案

习题1

1.

图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现

在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，

图 1.7是这条河以及河上的两个岛和七座桥的

草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。

七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行

2， 经过七座桥，且每次只经历过一次 3， 回到起点

该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。

2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n

2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m

3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C ++描述。

//采用分治法

//对数组先进行快速排序 //在依次比较相邻的差 #include using namespace std;

int partions(int b[],int low,int high) {

图1.7 七桥问题

int prvotkey=b[low];

b[0]=b[low];

while (low

{

while (low=prvotkey)

--high;

b[low]=b[high];

while (low

++low;

b[high]=b[low];

}

b[low]=b[0];

return low;

}

void qsort(int l[],int low,int high)

{

int prvotloc;

if(low

{

prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); //递归调用排序由low 到prvotloc-1

qsort(l,prvotloc+1,high); //递归调用排序由 prvotloc+1到 high

}

}

void quicksort(int l[],int n)

{

qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个

}

int main()

{

int a[11]={0,2,32,43,23,45,36,57,14,27,39};

int value=0;//将最小差的值赋值给value

for (int b=1;b<11;b++)

cout<

cout<

quicksort(a,11);

for(int i=0;i!=9;++i)

{

if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) )

value=a[i+1]-a[i];

else

value=a[i+2]-a[i+1];

}

cout<

return 0;

}

4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述。

#include

using namespace std;

int main()

{

int a[]={1,2,3,6,4,9,0};

int mid_value=0;//将“既不是最大也不是最小的元素”的值赋值给它

for(int i=0;i!=4;++i)

{

if(a[i+1]>a[i]&&a[i+1]

{

mid_value=a[i+1];

cout<

break;

}

else if(a[i+1]a[i+2])

{

mid_value=a[i+1];

cout<

break;

}

}//for

return 0;

}

5. 编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。

#include

using namespace std;

int main()

{

double value=0;

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

{

value=value*10+1;

if(value%2013==0)

{

cout<<"n至少为:"<

break;

}

}//for

return 0;

}

6. 计算π值的问题能精确求解吗？编写程序，求解满足给定精度要求的π值

#include

using namespace std;

int main ()

{

double a,b;

double arctan(double x);//声明

a = 16.0*arctan(1/5.0);

b = 4.0*arctan(1/239);

cout << "PI=" << a-b << endl;

return 0；

}

double arctan(double x)

{

int i=0;

double r=0,e,f,sqr;//定义四个变量初

sqr = x*x;

e = x;

while (e/i>1e-15)//定义精度范围

{

f = e/i;//f是每次r需要叠加的方程

r = (i%4==1)?r+f:r-f;

e = e*sqr;//e每次乘于x的平方

i+=2;//i每次加2

}//while

return r;

}

7. 圣经上说：神6天创造天地万有，第7日安歇。为什么是6天呢？任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此6是完美数。神6天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数

#include

using namespace std;

int main()

{

int value, k=1;

cin>>value;

for (int i = 2;i!=value;++i)

{

while (value % i == 0 )

{

k+=i;//k为该自然数所有因子之和

value = value/ i;

}

}//for

if(k==value)

cout<<"该自然数是完美数"<

else

cout<<"该自然数不是完美数"<

return 0;

}

8.有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间？

由于甲过桥时间最短，那么每次传递手电的工作应有甲完成

甲每次分别带着乙丙丁过桥

例如：

第一趟：甲，乙过桥且甲回来

第二趟：甲，丙过桥且甲回来

第一趟：甲，丁过桥

一共用时19小时

9．欧几里德游戏：开始的时候，白板上有两个不相等的正整数，两个玩家交替行动，每次行动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这个数字必须是新的，也就是说，和白板上的任何一个已有的数字都不相同，当一方再也写不出新数字时，他就输了。请问，你是选择先行动还是后行动？为什么？

设最初两个数较大的为a, 较小的为b，两个数的最大公约数为factor。

则最终能出现的数包括: factor, factor*2, factor*3, ..., factor*(a/factor)=a. 一共a/factor个。

如果a/factor 是奇数，就选择先行动；否则就后行动。

习题2

1．如果T1(n)=O(f (n))，T2(n)=O(g(n))，解答下列问题：

（1）证明加法定理：T1(n)＋T2(n)=max{O(f (n)), O(g(n))}；

（2）证明乘法定理：T1(n)×T2(n)=O(f (n))×O(g(n))；

（3）举例说明在什么情况下应用加法定理和乘法定理。

,（1）

（2）

（3）比如在

for（f(n)）

{

for(g(n))

}

中应该用乘法定理

如果在“讲两个数组合并成一个数组时”，应当用加法定理

2．考虑下面的算法，回答下列问题：算法完成什么功能？算法的基本语句是什么？基本语句执行了多少次？算法的时间复杂性是多少？

（1）int Stery(int n)

{

int S = 0;

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

S = S + i * i;

return S;

} （2）int Q(int n)

{

if (n == 1)

return 1;

else

return Q(n-1) + 2 * n - 1;

}

（1） 完成的是1-n 的平方和

基本语句：s+=i*i ，执行了n 次

时间复杂度O （n ）

（2） （2）完成的是n 的平方

基本语句：return Q(n -1) + 2 * n – 1，执行了n 次 时间复杂度O （n ）

3. 分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。

（1） 基本语句2*i

基本语句y = y + i * j 执行了2/n 次 一共执行次数=n/2+n/2=O （n ）

（2） 基本语句m+=1执行了(n/2)*n=O(n*n) 4. 使用扩展递归技术求解下列递推关系式：

（1）??

?>-==1

)1(314)(n n T n n T （2）???>+==1)(211)(n n n T n n T

(1) int T(int n) { if(n==1) return 4;

else if(n>1) return 3*T(n-1); } (2)

int T(int n) {

if(n==1) return 1;

else if(n>1) return 2*T(n/3)+n; }

5. 求下列问题的平凡下界，并指出其下界是否紧密。 （1）求数组中的最大元素；

（2）判断邻接矩阵表示的无向图是不是完全图； （3）确定数组中的元素是否都是惟一的；

（1）for (i = 1; i <= n; i++) if (2*i <= n) for (j = 2*i; j <= n; j++) y = y + i * j ； （2）m = 0; for (i = 1; i <= n; i++) for (j = 1; j <= 2*i; j++) m=m+1;

（4）生成一个具有n个元素集合的所有子集

(1)Ω(n) 紧密？

(2)Ω(n*n)

(3)Ω(logn+n)（先进行快排，然后进行比较查找）

(4)Ω(2^n)

7．画出在三个数a, b, c中求中值问题的判定树。

8．国际象棋是很久以前由一个印度人Shashi发明的，当他把该发明献给国王时，国王很高兴，就许诺可以给这个发明人任何他想要的奖赏。Shashi要求以这种方式给他一些粮食：棋盘的第1个方格内只放1粒麦粒，第2格2粒，第3格4粒，第4格8粒，……，以此类推，直到64个方格全部放满。这个奖赏的最终结果会是什么样呢？

#include

using namespace std;

int main()

{

long double result=1;

double j=1;

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

{

j=j*2;

result+=j;

j++;

}

cout<

return 0;

}

习题3

1．假设在文本"ababcabccabccacbab"中查找模式"abccac"，写出分别采用BF算法和KMP 算法的串匹配过

//BF算法

#include

using namespace std;

int BF(char S[], char T[])

{

int index = 0;

int i = 0, j = 0;

while ((S[i] != '\0') && (T[j] != '\0'))

{

if (S[i] == T[j])

{

i++;

j++;

}

else {

++index;

i = index;

j = 0;

}

}

if (T[j] == '\0')

return index + 1;

else

return 0;

}

int main()

{

char s1[19]="ababcabccabccacbab";

char s2[7]="abccac";

cout<< BF( s1, s2) <

return 0;

}

//KMP算法

#include

using namespace std;

void GetNext(char T[ ], int next[ ]) //求模式T的next值

{

int i, j, len;

next[0] = -1;

for (j = 1; T[j]!='\0'; j++) //依次求next[j]

{

for (len = j - 1; len >= 1; len--) //相等子串的最大长度为j-1 {

for (i = 0; i < len; i++) //依次比较T[0]~T[len-1]与T[j-len]~T[j-1]

if (T[i] != T[j-len+i]) break;

if (i == len)

{

next[j] = len; break;

}

}//for

if (len < 1)

next[j] = 0; //其他情况，无相等子串

}//for

}

int KMP(char S[ ], char T[ ]) //求T在S中的序号

{

int i = 0, j = 0;

int next[80]; //假定模式最长为80个字符GetNext(T, next);

while (S[i] != '\0' && T[j] != '\0')

{

if (S[i] == T[j])

{

i++; j++;

}

else {

j = next[j];

if (j == -1) {i++; j++;}

}

}

if (T[j] == '\0') return (i - strlen(T) +1); //返回本趟匹配的开始位置

else

return 0;

}

int main()

{

char s1[]="ababcabccabccacbab";

char s2[]="abccac";

cout<

return 0;

}

2.分式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将6/8化简为3/4。

#include

using namespace std;

int main()

{

int n;//分子

int m;//分母

int factor;//最大公因子

int factor1;

cout<<"输入一个真分数的分子与分母："<

cin>>n>>m;

int r = m % n;//因为是真分数所以分母一定大于分子

factor1=m;

factor=n;

while (r != 0)

{

factor1 =factor;

factor = r;

r = factor1% factor;

}

cout<<"输出该真分数的最简分数："<<(n/factor)<<"/"<<(m/factor)<

return 0;

}

3.设计算法，判断一个大整数能否被11整除。可以通过以下方法：将该数的十进制表示

从右端开始，每两位一组构成一个整数，然后将这些数相加，判断其和能否被11整除。

例如，将562843748分割成5,62,84,37,48，然后判断(5+62+84+37+48)能否被11整除

//将一个大整数看成一个数组

//数组的奇数位对应数的10倍加上数组偶数对应数的本身

//验证结果能否被11整除

#include

using namespace std;

int main()

{

int a[9]={5,6,2,8,4,3,7,4,8};

int result=0; //result为题目要求的各位之和

for(int i=0;i!=9;++i)

{

if(i%2==0)

result+=a[i]; //i 为偶数位时，结果加上其对应数组数的本身

else

result+=a[i]*10; //i 为奇数位时，结果加上对应数组数的10倍}

if(result%11==0)

cout<<"该整数能被11整除"<

else

cout<<"该整数不能被11整除"<

return 0;

}

4. 数字游戏。把数字1,2,…,9这9个数字填入以下含有加、减、乘、除的四则运算式中，使得该等式成立。要求9个数字均出现一次且仅出现一次，且数字1不能出现在乘和除的一位数中（即排除运算式中一位数为1的平凡情形）。

??×?＋???÷?－?? = 0

5. 设计算法求解a n mod m，其中a、n和m均为大于1的整数。（提示：为了避免a n 超出int型的表示范围，应该每做一次乘法之后对n取模）

#include

using namespace std;

int square(int x)

{

return x*x;

}

//用递归思想

int resultmod(int a, int n)

{

if(n== 0)

return 1;

if(n%2 == 0)

return square(resultmod(a, n/2));//n为偶数的时，取n的一半防止溢出else

return a*resultmod(a, n-1);//n为奇数时，取n-1；

}

int main()

{

int a, n, m;

cout<<"请输入a，n, m: "<<" ";

cin>>a>>n>>m;

cout<

int result = resultmod(a, n);

cout<<"a^n mod m的结果为："<< result % m<

return 0;

}

6. 设计算法，在数组r[n]中删除所有元素值为x的元素，要求时间复杂性为O(n)，空间复杂性为O(1)。

7.设计算法，在数组r[n]中删除重复的元素，要求移动元素的次数较少并使剩余元素间的相对次序保持不变。

#include

using namespace std;

void deletere(int a[],int N)

{

int b[100]={0};

int i,k;

k=0;

static int j=0;

for(i=0;i

b[a[i]]++;

for(i=0;i<100;i++)

{

if(b[i]!=0)

{

if(b[i]==2)

{

k++;

}

a[j]=i;

j++;

}

}

for(i=0;i

cout<

}

int main()

{

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

deletere(a,6);

return 0;

}

//在数组查找相同的元素

//把其中一个相同的数值的元素位置设成一个“特殊数值”

//输出所求函数

#include

using namespace std;

int main()

{

int a[]={1,2,1,5,3,2,9,4,5,5,3,5};

int i,j;

for( i=0;i<12;i++)

{

for(j=0;j

{

if(a[j]==a[i])

a[i]=64787250;//设一个数组不存在的数值

}

}//for

for(i=0;i<12;i++)

{

if(a[i]!=64787250)

cout<

}

cout<

return 0;

}

8. 设表A={a1, a2, …, a n}，将A拆成B和C两个表，使A中值大于等于0的元素存入表B，值小于0的元素存入表C，要求表B和C不另外设置存储空间而利用表A的空间。

//先对A进行快排

//将大于0的元素给B，小于0的元素给C

#include

using namespace std;

int partions(int l[],int low,int high)

{

int prvotkey=l[low];

l[0]=l[low];

while (low

{

while (low=prvotkey)

--high;

l[low]=l[high];

while (low

++low;

l[high]=l[low];

}

l[low]=l[0];

return low;

}

void qsort(int l[],int low,int high)

{

int prvotloc;

if(low

{

prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1); //递归调用排序由low 到prvotloc-1

qsort(l,prvotloc+1,high); //递归调用排序由prvotloc+1到high

}

}

void quicksort(int l[],int n)

{

qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个

}

int main()

{

int a[11]={-2,2,32,43,-23,45,36,-57,14,27,-39};

quicksort(a,11);

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

{

if(a[i]<0)

cout<<"C: "<

else

cout<<"B: "<

}

cout<

return 0;

9. 荷兰国旗问题。要求重新排列一个由字符R, W, B（R代表红色，W代表白色，B代表兰色，这都是荷兰国旗的颜色）构成的数组，使得所有的R都排在最前面，W排在其次，B排在最后。为荷兰国旗问题设计一个算法，其时间性能是O(n)。

//0代表红；1代表白；2代表蓝

#include

using namespace std;

const int N = 20;

void swap_ab ( int *p , int *q )

{

int tmp = *p;

*p = *q;

*q = tmp;

}

void process ( int a[], int n )

{

int *p, *q;

p = q = a;

while ( p != a+n-1 ) //p向前遍历，直到便利完毕

{

if ( *(p+1) < *p )

{

q = p+1;

while ( *q < *(q-1) )

{

swap_ab ( q, q-1 );

--q; //q指针后移

}

} //if

++p;

} //while

}

int main()

int a[N] = { 0, 2, 1, 2, 0, 1, 0, 2, 2, 1, 0, 1, 2, 1, 1, 0, 0, 1, 1, 2}; //待处理的数组

cout << "处理后的数组序列: " <

for (int i=0; i< N; ++i ) cout << a[i] <<" ";

cout << endl; return 0; }

10. 设最近对问题以k 维空间的形式出现，k 维空间的两个点p 1=(x 1, x 2, …, x k )和p 2=(y 1, y 2, …, y k )的欧几里德距离定义为：∑==

k

i i

i

-x y p p d 1

2

21)

(),(。对k 维空间的最近对问题设计

蛮力算法，并分析其时间性能。

11．设计蛮力算法求解小规模的线性规划问题。假设约束条件为：（1）x +y ≤4；（2）x +3y ≤6；（3）x ≥0且y ≥0；使目标函数3x +5y 取得极大值。

#include using namespace std;

int main() {

int x,y,x0,y0;

int summax=0,temp=0; for(x0=0;x0<=4;++x0) {

for(y0=0;(x0+y0<=4)&&(x0+3*y0<=6);++y0)

temp=3*x0+5*y0; if(temp>=summax) { summax=temp; x=x0;//符合sum 最大值的x y=y0;//符合sum 最大值得y }

}//for

cout<<"x= "<

char t[5]="rewq";

for(int i=0;i!=4;++i)

{

if(s[i]!=t[3-i])

{

cout<<"qwer和rewq不是变位词"<

return 0;

break;

}

}

cout<<"qwer和rewq是变位词"<

return 0;

}

15．在美国有一个连锁店叫7-11店，因为这个商店以前是早晨7点开门，晚上11点关门。有一天，一个顾客在这个店挑选了四样东西，然后到付款处去交钱。营业员拿起计算器，按了一些键，然后说：“总共是$7.11。”这个顾客开了个玩笑说：“哦？

难道因为你们的店名叫7-11，所以我就要付$7.11吗？”营业员没有听出这是个玩笑，回答说：“当然不是，我已经把这四样东西的价格相乘才得出这个结果的！”顾客一听非常吃惊，“你怎么把他们相乘呢？你应该把他们相加才对！”营业员答道：“噢，对不起，我今天非常头疼，所以把键按错了。”然后，营业员将结果重算了一遍，将这四样东西的价格加在一起，然而，令他俩更为吃惊的是总和也是$7.11。设计蛮力算法找出这四样东西的价格各是多少？

该算法为：

int $7.11(float a[],float b[],float c[],float d[],int n)

{

for(int i=0;i!=n;++i)

for(int j=0;j!=n;++j)

for(int k=0;k!=n;++k)

for(int m=0;m!=n;++m)

{

if((a[i]+b[j]+c[k]+d[m])==7.11 && a [i]*b[j]*c[k]*d[m]==7.11)

cout<

return 0;

}

return 0;

}

习题4

1.分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关，试说明这几个参数与分治法时间复杂性之间的关系。

2. 证明：如果分治法的合并可以在线性时间内完成，则当子问题的规模之和小于原问题的规模时，算法的时间复杂性可达到O(n)。

O(N)=2*O(N/2)+x

新视野大学英语第二册(第二版)课后翻译原题与答案

01. 她连水都不愿喝一口，更别提留下来吃饭了。 She wouldn't take a drink, much less would she stay for dinner. 02. 他认为我在对他说谎，但实际上我讲的是实话。 He thought I was lying to him, whereas I was telling the truth. 03. 这个星期你每天都迟到，对此你怎么解释？ How do you account for the fact that you have been late every day this week? 04. 他们利润增长，部分原因是采用了新的市场策略。 The increase in their profits is due partly to their new market strategy. 05. 这样的措施很可能会带来工作效率的提高。 Such measures are likely to result in the improvement of work efficiency. 06. 我们已经在这个项目上投入了大量时间和精力，所以我们只能继续。 We have already poured a lot of time and energy into the project, so we have to carry on. 07. 尽管她是家里的独生女，她父母也从不溺爱她。 Despite the fact that she is the only child in her family, she is never babied by her parents. 08. 迈克没来参加昨晚的聚会，也没给我打电话作任何解释。 Mike didn't come to the party last night, nor did he call me to give an explanation. 09. 坐在他旁边的那个人确实发表过一些小说，但决不是什么大作家。 The person sitting next to him did publish some novels, but he is by no means a great writer. 10. 他对足球不感兴趣，也从不关心谁输谁赢。 He has no interest in football and is indifferent to who wins or loses. 11. 经理需要一个可以信赖的助手，在他外出时，由助手负责处理问题。 The manager needs an assistant that he can count on to take care of problems in his absence. 12. 这是他第一次当着那么多观众演讲。 This is the first time that he has made a speech in the presence of so large an audience. 13. 你再怎么有经验，也得学习新技术。 You are never too experienced to learn new techniques. 14. 还存在一个问题，那就是派谁去带领那里的研究工作。(Use an appositional structure.) There remains one problem, namely, who should be sent to head the research there. 15. 由于文化的不同，他们的关系在开始确实遇到了一些困难。 Their relationship did meet with some difficulty at the beginning because of cultural differences. 16. 虽然他历经沉浮，但我始终相信他总有一天会成功的。 Though he has had ups and downs, I believed all along that he would succeed someday. 17. 我对你的说法的真实性有些保留看法。 I have some reservations about the truth of your claim. 18. 她长得并不特别高，但是她身材瘦，给人一种个子高的错觉。 She isn't particularly tall, but her slim figure gives an illusion of height. 19. 有朋自远方来，不亦乐乎？(Use "it" as the formal subject.) It is a great pleasure to meet friends from afar. 20. 不管黑猫白猫，能抓住老鼠就是好猫。(as long as) It doesn't matter whether the cat is black or white as long as it catches mice. 21. 你必须明天上午十点之前把那笔钱还给我。 You must let me have the money back without fail by ten o'clock tomorrow morning. 22. 请允许我参加这个项目，我对这个项目非常感兴趣。 Allow me to take part in this project: I am more than a little interested in it. 23. 人人都知道他比较特殊：他来去随意。(be free to do sth.) Everyone knows that he is special: He is free to come and go as he pleases. 24. 看她脸上不悦的神色，我似乎觉得她有什么话想跟我说。 Watching the unhappy look on her face, I felt as though she wished to say something to me. 25. 他说话很自信，给我留下了很深的印象。(Use "which" to refer back to an idea or situation.)

实用综合教程(第二版)课后练习答案

1、Don 'tlet the failure discourag y e ou.Try again. 2、He dropped out of college after only two weeks. 3、He spoke very highly of her. 4、Peter took advantage of his visit to London to improve his English. 5、The chairman agreed to conside r my suggestion. 6、The idea needs to be tried out. 7、The new road is a major government project. 8、This is our greatest and most encouraging progress; in short,a triumph. 9、The house has belonged to our family for a long time. 10、There was a pause in the talk when Mary came in. 11、We all look forward to your next visit to Nanjing. 12、She discovered that she had lost her purse. 13、The plane will land in five minutes. 14、It used to be thought that the earth was flat. 15、Everyone is fascinated by the singer 's amazing voice. 16、My parents are thinking of spending their holiday in France. 17、She's very modes t about her success. 18、Most plants require sunlight. 19、Be careful to your words when talking to elderly people. 20、Mother called again to make certain that the new air-conditioner would be delivered the next day. 21、I presented a bunch of flowers to Mrs.Link last Christmas. 22、Jack wrapped the gift in a piece of colored paper. 23、Shall I make the introduction?Robert,this is Julia. 24、My mom cleans the house every day and keeps everything in order. 25、This idea appeared in many books. 26、The People's Republic of China was founded in 1949. 27、When will the work on the highway be completed? 28、Oranges are my favorite fruit. 29、Hans Andersen created many lovely characters. 30、The business has expanded from having one office to having twelve. 31、Did you have fun at Disneyland last summer? 32、His lies brought to an end his friendship with Mike. 33、I'll help you as far as I can. 34、He had included a large number of funny stories in the speech. 35、These greenbelts protect 500,000 acres of farmland against moving sands. 36、The TV program is shown to call people's attention to water pollution in China. 37、 A soft wind caused ripples on the surface of the lake. 38、The children formed a circle around her. 39、My mother measured me for a new dress. 40、The park lies at the center of the city. 41、The train would pull out soon. We ran like mad to catch it. 42、My old grandmother has difficulty in remembering things. 43、The company employed about 100 men. 44、She checked the letter before sending it.

新视野大学英语4册第二版课后习题答案.doc

新视野大学英语（第2版）第4册Unit 1答案 III. 1. idle 2. justify 3. discount 4. distinct 5. minute 6.accused 7. object 8. contaminate 9. sustain 10. worship IV. 1. accusing... of 2. end up 3. came upon 4. at her worst 5. pa: 6. run a risk of 7. participate in 8. other than 9. object to/objected V 1. K 2. G 3. C 4. E 5. N 6.0 7.1 8. L 9. A 10. D Collocation VI. 1. delay 2. pain 3. hardship 4. suffering 5. fever 6. defeat 7. poverty 8. treatment 9. noise 10. agony Word building VII. 1. justify 2. glorify 3. exemplifies 4. classified 5. purified 6. intensify 7. identify 8. terrified VIII. 1. bravery 2. jewelry 3. delivery 4. machinery 5. robbery 6. nursery 7. scenery 8. discovery sentence Structure IX. 1. other than for funerals and weddings 2. other than to live an independent life 3. other than that they appealed to his eye . . ` 4. but other than that, he'll eat just about everything . 5. other than that it's somewhere in the town center X. 1. shouldn't have been to the cinema last night 2. would have; told him the answer 3. they needn't have gone at all 4. must have had too much work to do 5. might have been injured seriously XIII. 1 ．B 2.A 3.C 4.D 5. B 6.A 7.B 8.A 9. C 10.A II．D 12.C 13. D 14.A 15. C 16.D 17.B 18.C I9. A 20.D 新视野大学英语（第2版）第4册Unit 2答案 Section A Comprehension o f the text 1. He lived a poor and miserable life during his childhood. 2. Because no one in Britain appeared to appreciate his talent for comedy. His comic figures did not conform to British standards. 3. Because his dress and behavior didn't seem that English. 4. It was the first movie in which Chaplin spoke. 5. He used his physical senses to invent his art as he went along without a prepared script. 6. His transformation of lifeless objects into other kinds of objects, plus the skill with which he executed it again and again. 7. She brought stability and happiness to him and became a center of calm in his family. 8. Comic. Vocabulary III. 1. coarse 2. betrayed 3. incident 4. postponed 5. execute 6. surrounding 7. applause 8. extraordinary 9. clumsy 10. sparked IV. 1. for 2. against 3. up 4. about 5. up 6. to 7. down 8. down 9. in 10. on V. l. I 2.J 3.B 4.D 5.E 6.G 7.F 8.L 9.N 10.A Collocation
VI. 1. service 2. help/hand 3. influence 4. guarantee 5. visit 6. span . 7. welcome 8. spirit 9. duties 10. buildings Word Building

算法设计与分析复习资料1

一 1.循环赛日程表问题的相关叙述。 2.算法运行时所需要占用的存储空间有？ 3.动态规划法的求解步骤 4.解空间树是排列树的问题有。 5.分治法的步骤 6.就会场安排问题，贪心法的最佳贪心策略 7.快速排序法基准元素的选取方法 8.满足满m叉树的问题有？ 9.分支限界法的解题步骤 10.事前分析法相关的影响因素有 11.用分治法求解的问题一般需要具备一些特征，主要有？ 二 1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。 2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n 元组。 3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。 4．一个正在生成孩子的结点称为扩展结点。 5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。 6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。 7．一个自身已生成但其孩子还没有全部生成的结点称为活结点 8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间 9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。 10．分支限界法采用的是宽度优先搜索。 11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法 12．一个所有孩子已经生成的结点称做死结点 13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。 三 1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。 2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采

算法设计与分析第2版 王红梅 胡明 习题答案

精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low=prvotkey)

新视野大学英语册第二版课后习题答案全解

Unit 1答案2版）第4册新视野大学英语（第4. but other than that, he'll eat just about everything . 5. other than that it's somewhere in the town center III. X. 1. idle 2. justify 3. discount 4. distinct 5. minute 1. shouldn't have been to the cinema last night 6.accused 7. object 8. contaminate 9. sustain 10. worship told him the answer 。2. would haveIV. 3. they needn't have gone at all 1. accusing... of 2. end up 3. came upon 4. at her worst 5. pa: 4. must have had too much work to do 6. run a risk of 7. participate in 8. other than 9. object to/objected 5. might have been injured seriously 1. 这种植物只有在培育它的土壤中才能很好地成长。Collocation The plant does not grow well in soils other than the one in which it has been VI. developed. 1. delay 2. pain 3. hardship 4. suffering 5. fever 研究结果表明，无论我们白天做了什么事情，晚上都会做大约两个小时2. 6. defeat 7. poverty 8. treatment 9. noise 10. agony 的梦。Word building Research findings show that we spend about two hours dreaming every night, VII. no matter what we may have done during the day. 1. justify 2. glorify 3. exemplifies 4. classified 有些人往往责怪别人没有尽最大努力，以此来为自己的失败辩护。3. 5. purified 6. intensify 7. identify 8. terrified Some people tend to justify their failure by blaming others for not trying their VIII. best. 1. bravery 2. jewelry 3. delivery 4. machinery 我们忠于我们的承诺：凡是答应做的，我们都会做到。4. 5. robbery 6. nursery 7. scenery 8. discovery We remain true to our commitment: Whatever we promised to do, we would sentence Structure do it. 连贝多芬的父亲都不相信自己儿子日后有一天可能成为世界上最伟大的5. IX. 音乐家。爱迪生也同样如此，他的老师觉得他似乎过于迟钝。1. other than for funerals and weddings Even Beethoven's father discounted the possibility that his son would one day 2. other than to live an independent life become the greatest musician in the world. The same is true of Edison, who 3. other than that they appealed to his eye . . ` 1 / 7 seemed to his teacher to be quite dull. sentence structure 当局控告他们威胁国家安全。6. They were accused by the authorities of threatening the state security. X. 1. it is a wonder to find

算法设计与分析第2版 王红梅 胡明 习题答案

习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Le ｏn ｈar ｄ Ｅul ｅr,１7０7 —17８3)提出并解决了该问题。七桥问题就是这样描述的:一个人就是否能在一次步行中穿越哥尼斯堡(现在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经 过一次,图1、７就是这条河以及河上的两个岛 与七座桥的草图。请将该问题的数据模型抽象 出来,并判断此问题就是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1， 一次步行 2， 经过七座桥,且每次只经历过一次 3， 回到起点 该问题无解:能一笔画的图形只有两类:一类就是所有的点都就是偶点。另一类就是只有二个奇点的图形。 2、在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不就是除法而就是减法。请用伪代码描述这个版本的欧几里德算法 １、r=m-n ２、循环直到r=0?2、１ m ＝n ２、２ n=r ２、3 ｒ=ｍ-n ?3 输出m ３.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码与C ++描述。 //采用分治法 /／对数组先进行快速排序 ／/在依次比较相邻的差 #inc ｌud ｅ ＜ｉostream> ｕsin ｇ n ａｍｅs ｐａc ｅ ｓｔd; in ｔ ｐa ｒｔion ｓ(int b[］,ｉnt l ｏw,ｉnt ｈi ｇｈ) { ｉｎt pr ｖｏtkey=b[lo ｗ]; b ［０］＝b[lo ｗ]; 图1、7 七桥问题

ｗｈile (lｏw<ｈigh) ｛ ｗhilｅ(lｏw＝ｐrvotkey) -－ｈigｈ; ｂ[low]=ｂ[ｈigｈ]; wｈile (low

全新版大学英语综合教程第二版课后练习答案定稿版

全新版大学英语综合教程第二版课后练习答案精编W O R D版 IBM system office room 【A0816H-A0912AAAHH-GX8Q8-GNTHHJ8】

Unit1 Ways of Learning Vocabulary I 1. 1)insert 2)on occasion 3)investigate 4)In retrospect 5)initial 6)phenomen a 7)attached 8)make up for 9)is awaiting 10)not; in the least 11)promote 12)emerged 2. 1)a striking contrast between the standards of living in the north of the country and the south. 2)is said to be superior to synthetic fiber. 3)as a financial center has evolved slowly. 4)is not relevant to whether he is a good lawyer.

5)by a little-known sixteen-century Italian poet have found their way into some English magazines. 3. 1)be picked up; can’t accomplish; am exaggerating 2)somewhat; the performance; have neglected; they apply to 3)assist; On the other hand; are valid; a superior II 1)continual 2)continuous 3)continual 4)continuous 5)principal 6)principal 7)principle 8)principles 9)principal III 1.themselves 2.himself/herself 3.herself/by herself/on her own 4.itself

算法设计与分析第2版王红梅胡明习题答案

算法设计与分析(第2版)-王红梅-胡明-习题 答案 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783） 提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图 1.7是这条河以及河上的两个岛和七座桥的 草图。请将该问题的数据模型抽象出来，并判 断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n 2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C ++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 图1.7 七桥问题

#include using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low=prvotkey) --high; b[low]=b[high]; while (low

新视野大学英语2册课后题答案

新视野大学英语Book II课后练习题答案 Unit 1 Section A Language focus 3.Words in use 1.condense 2.exceed 3.deficit 4.exposure 5.asset 6.adequate https://www.wendangku.net/doc/c112870194.html,petent 8.adjusting 9.precisely 10.beneficial 4.Word building Words learned new words formed -al/ial manager managerial editor editorial substantial substance survive survival traditional tradition marginal margin -cy Consistent consistency Accurate accuracy Efficiency efficient -y Recover recovery Minister ministry assemble assembly 5. 1.editorial 2.recovery 3.accuracy 4.substance 5.managerial 6.margin 7.assembly 8.Ministry 9.survival 10.tradition 11.consistency 12.efficient

6.Banked cloze 1.L 2.C 3.J 4.A 5.I 6.O 7.N 8.E 9.H 10.F 7.Expressions in use 1.feel obliged to 2.be serious about 3.run into 4.distinguish between 5.thrust upon 6.was allergic to 7.get lost 8.be attracted to 9.make sense 10.looked upon as 9.Translate the following paragraph into Chinese. 人们普遍认为英语是一种世界语言，经常被许多不以英语为第一语言的国家使用。与其他语言一样，英语也发生了很大的变化。英语的历史可以分为三个主要阶段，古英语，中古英语和现代英语。英语起源于公元5世纪，当时三个日耳曼部落入侵英国，他们对于英语语言的形成起了很大的作用。在中世纪和现代社会初期，英语的影响遍及不列颠群岛。从17世纪初，它的影响力开始在世界各地显现。欧洲几百年的探险和殖民过程导致了英语的重大变化。今天，由于美国电影，电视，音乐，贸易和技术，包括互联网的大受欢迎，美国英语的影响力尤其显著。 10.Translate the following paragraph into English Chinese calligraphy is a unique art and the unique art treasure in the world. The formation and development of the Chinese calligraphy is closely related to the emergence and evolution of Chinese characters. In this long evolutionary process,Chinese characters have not only played an important role in exchanging ideas and transmitting culture but also developed into a unique art form.Calligraphic works well reflect calligraphers’ personal feeling, knowledge, self-cultivation, personality, and so forth, thus there is an e xpression that “seeing the calligraphers’ handwriting is like seeing the person”. As one of the treasures of Chinese culture, Chinese calligraphy shines splendidly in the world’s treasure house of culture and art. Section B 4.words in use 1.mysterious 2.desperate 3.devise 4.negotiate 5.recalled 6.specifically 7.depict 8.ignorance 9.expand 10.confusion 5.Expressions in use

C语言程序设计第二版习题参考答案

C语言程序设计习题参考答案 习题1 一、判断题 1．在计算机中，小数点和正负号都有专用部件来保存和表示。 2．二进制是由0和1两个数字组成的进制方式。 3．二进制数的逻辑运算是按位进行的，位及位之间没有进位和借位的关系。 4．在整数的二进制表示方法中，0的原码、反码都有两种形式。 5．有符号数有三种表示法：原码、反码和补码。 6．常用字符的ASCII码值从小到大的排列规律是：空格、阿拉伯数字、大写英文字母、小写英文字母。 解：1．F 2．T 3．T 4．T 5．T 6．T 二、单选题 1．在计算机中，最适合进行数值加减运算的数值编码是。 A. 原码 B. 反码 C. 补码 D. 移码 2．已知英文小写字母m的ASCII码为十进制数109，则英文小写字母y的ASCII码为十进制数。 A. 112 B. 120 C. 121 D. 122 3．关于ASCII码，在计算机中的表示方法准确地描述是。 A. 使用8位二进制数，最右边一位为1 B. 使用8位二进制数，最左边一位为1 C. 使用8位二进制数，最右边一位为0 D. 使用8位二进制数，最左边一位为0 4．设在机器字长4位，X＝0111B，Y＝1011B，则下列逻辑运算中，正确的是___________。 A. X∧Y＝1000 B. X∨Y＝1111 C. X⊕Y＝0011 D. ˉY ＝1000 5．下列叙述中正确的是（）。 A．高级语言就是机器语言 B．汇编语言程序、高级语言程序都是计算机程序，但只有机器语言程序才是计算机可以直接识别并执行的程序 C．C语言因为具有汇编语言的一些特性，所以是汇编语言的一种 D．C源程序经过编译、连接，若正确，执行后就能得到正确的运行结果

算法设计与分析C++语言描述(陈慧南版)课后答案

第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环） 若考虑其他语句，则没有这么多，可能就601倍。 第二章 32P 2-8.（1）画线语句的执行次数为 log n ????。(log )n O 。划线语句的执行次数应该理解为一格整体。 （2）画线语句的执行次数为 111 (1)(2) 16 j n i i j k n n n ===++= ∑∑∑。3()n O 。 （3 ）画线语句的执行次数为 。O 。 （4）当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++， 当n 为偶数时画线语句的执行次数为2 (2)4 n +。2()n O 。 2-10.（1）当1n ≥时，225825n n n -+≤，所以，可选5c =，01n =。 对于0n n ≥，22 ()5825f n n n n =-+≤，所以，22 582()n n n -+=O 。 （2）当8n ≥时，2222 582524n n n n n -+≥-+≥，所以，可选4c =，08n =。对于0n n ≥， 22()5824f n n n n =-+≥，所以，22582()n n n -+=Ω。 （3）由（1）、（2）可知，取14c =，25c =，08n =，当0n n ≥时，有22212582c n n n c n ≤-+≤，所以 22582()n n n -+=Θ。 2-11. (1) 当3n ≥时，3 log log n n n <<，所以()20log 21f n n n n =+<，3 ()log 2g n n n n =+>。可选21 2 c = ，03n =。对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。注意：是f (n )和g (n )的关系。 （2）当4n ≥时，2 log log n n n <<，所以2 2 ()/log f n n n n =<，2 2 ()log g n n n n =≥。可选1c =，04n =。对于0n n ≥，2 ()()f n n cg n <≤，即()(())f n g n =O 。 （3）因为log log(log )()(log ) n n f n n n ==，()/log log 2n g n n n n ==。当4n ≥时，log(log )()n f n n n =≥，