中国科学院大学历年计算机算法作业和历年习题
- 格式：doc
- 大小：1.96 MB
- 文档页数：78
中国科学院大学历年习题
习题一 复杂性分析初步
1. 试确定下述程序的执行步数，该函数实现一个m×n矩阵与一个n×p矩阵之间的乘法：
矩阵乘法运算
template
void Mult(T **a, T **b, int m, int n, int p)
{//m×n矩阵a与n×p矩阵b相成得到m×p矩阵c
for(int i=0; i
for(int j=0; j
T sum=0;
for(int k=0; k
Sum+=a[i][k]*b[k][j];
C[i][j]=sum;
}
}
其中 s/e 表示每次执行该语句所要执行的程序步数。
频率是指该语句总的执行次数。
2． 函数MinMax用来查找数组a[0:n-1]中的最大元素和最小元素，以下给出两个程序。令n为实例特征。试问：在各个程序中，a中元素之间的比较次数 语 句 s/e 频率 总步数
template
void Mult(T **a, T **b, int m, int n, int p) 0 0 0
{
for(int i=0; i
for(int j=0; j
T sum=0; 1 m*p m*p
for(int k=0; k
Sum+=a[i][k]*b[k][j]; 1 m*p*n m*p*n
C[i][j]=sum; 1 m*p m*p
}
}
总 计 2*m*p*n+4*m*p+2*m+1 在最坏情况下各是多少？
找最大最小元素 方法一
template
bool MinMax(T a[], int n, int& Min, int& Max)
{//寻找a[0:n-1]中的最小元素与最大元素
//如果数组中的元素数目小于1，则还回false
if(n<1) return false;
Min=Max=0; //初始化
for(int i=1; i
if(a[Min]>a[i]) Min=i;
if(a[Max]
}
return true;
}
最好，最坏，平均比较次数都是 2*（n-1）
找最大最小元素 方法二
template
bool MinMax(T a[], int n, int& Min, int& Max)
{//寻找a[0:n-1]中的最小元素与最大元素
//如果数组中的元素数目小于1，则还回false
if(n<1) return false;
Min=Max=0; //初始化
for(int i=1; i
if(a[Min]>a[i]) Min=i;
else if(a[Max]
}
return true;
}
最坏2*（n-1）， 最好 n-1, 平均2)1(3n
3.证明以下不等式不成立：
1).);(9102nOn
2).)(log22nnn； 4．证明：当且仅当0)(/)(limngnfn时，))(()(ngonf。
5.下面那些规则是正确的？为什么？
1).))(/)(()(/)())(()()),(()(nGnFOngnfnGOngnFOnf；错
2).))(/)(()(/)())(()()),(()(nGnFngnfnGOngnFOnf；错
3).))(/)(()(/)())(()()),(()(nGnFngnfnGOngnFOnf；错
4).))(/)(()(/)())(()()),(()(nGnFngnfnGngnFnf；错
5).))(/)(()(/)())(()()),(()(nGnFngnfnGngnFnf。错
6). ))(/)(()(/)())(()()),(()(nGnFngnfnGngnFnf 对
6. 按照渐进阶从低到高的顺序排列以下表达式:
!,,20,3,log,43/22nnnnnn
顺序：!3420log23/2nnnnnn
7. 1) 假设某算法在输入规模是n时为nnT2*3)(. 在某台计算机上实现并完成该算法的时间是t秒.现有另一台计算机,其运行速度为第一台的64倍,
那么,在这台计算机上用同一算法在t秒内能解决规模为多大的问题?
关系式为 时间复杂度（计算步数）*运行速度(时间/每步)=运行所需时间，即
ttnT0*)(
解：设在新机器上t秒内能解决规模为m的问题，时间复杂度变为mmT2*3)(，
由于新机器运行速度提高64倍，则运行速度变为640tt新，
由关系式,*)(0ttnTttmT新*)(，得
ttn0*2*3，
ttm64*2*30
解得 规模 时间复杂度（步数） 原运行速度（时间/每步） 总时间
n nnT2*3)( 0t t 6nm
2) 若上述算法改进后，新算法的计算复杂度为2)(nnT, 则在新机器上用t秒时间能解决输入规模为多大的问题？
设在新机器上用t秒时间能解决输入规模为N的问题，则
由于新复杂度 2)(NNT新，新机器的运行速度为640tt新，
代入关系式ttNT新新*)(，得
002*2*364*tttNn，
解得
nN238
3）若进一步改进算法，最新的算法的时间复杂度为 8)(nT，其余条件不变，在新机器上运行，在t秒内能够解决输入规模为多大的问题？
设可解决的最大时间复杂度为maxT，则
00max*2*364*tttTn
可解决的最大时间复杂度为nT2*192max，（n为原始的输入规模）。
因为max8)(TnT，且)(nT为常数不随输入规模n变化，
所以任意规模的n都可在t秒内解决。
8. Fibonacci数有递推关系：
1),2()1(1,10,1)(nnFnFnnnF
试求出)(nF的表达式。
解：方法一：
当1n时，由递推公式)2()1()(nFnFnF得
特征方程为 12xx
解得
2511x，2512x
则可设
nnxcxcnF2211)(
由2)2(F，3)3(F，解得52511c，52512c
故])251()251[(51)(11nnnF，
当1,0n时，带入验证亦成立。
故])251()251[(51)(11nnnF
方法二：
也可直接推导
)2()1()(nFnFnF
可得
)][211nnnnaaaa
可得
251,，
设
1nnnaab，
则nb为等比数列，先求出nb，然后代入即可求得na。
第二章部分习题参考答案
1.证明下列结论：
1）在一个无向图中，如果每个顶点的度大于等于2，则该该图一定含有圈；
2）在一个有向图D中，如果每个顶点的出度都大于等于1，则该图一定含有一个有向圈。
1）证明：设无向图最长的迹,10kVVVP每个顶点度大于等于2，故存在与1V相异的点'V与0V相邻，若,'PV则得到比P更长的迹，与P的取法矛盾。因此，PV'，是闭迹，从而存在圈.0'10VVVV
证明*：设在无向图G中，有n个顶点，m条边。由题意知，m>=(2n)/2=n，而一个含有n个顶点的树有n-1条边。因m>=n>n-1，故该图一定含有圈。
（定义：迹是指边不重复的途径，而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不重复的闭迹称为圈。）
2）证明：设有向图最长的有向迹,10kVVVP每个顶点出度大于等于1，故存在'V为kV的出度连接点，使得'VVk成为一条有向边，若,'PV则得到比P更长的有向迹，与P矛盾，因此必有PV'，从而该图一定含有有向圈。
2.设D是至少有三个顶点的连通有向图。如果D中包含有向的Euler环游（即是通过D中每条有向边恰好一次的闭迹），则D中每一顶点的出度和入度相等。反之，如果D中每一顶点的出度与入度都相等，则D一定包含有向的Euler环游。这两个结论是正确的吗？请说明理由。如果G是至少有三个顶点的无向图，则G包含Euler环游的条件是什么？
证明：1）若图D中包含有向Euler环游，下证明每个顶点的入度和出度相等。
如果该有向图含有Euler环游，那么该环游必经过每个顶点至少一次，每经过一次，必为“进”一次接着“出”一次，从而入度等于出度。从而，对于任意顶点，不管该环游经过该顶点多少次，必有入度等于出度。
2）若图D中每个顶点的入度和出度相等，则该图D包含Euler环游。证明如下。 对顶点个数进行归纳。
当顶点数|v(D)|=2时，因为每个点的入度和出度相等，易得构成有向Euler环游。
假设顶点数|v(D)|=k时结论成立，则
当顶点数|v(D)|=k + 1时，任取v∈v(D).设S={以v为终点的边}，K={以v为始点的边}，因为v的入度和出度相等，故S和K中边数相等。记G=D-v.对G做如下操作:
任取S和K中各一条边21ee、，设在D中vve11，22vve，则对G和S做如下操作 21vvGG, }{2eSS，重复此步骤直到S为空。这个过程最终得到的G有k个顶点，且每个顶点的度与在G中完全一样。由归纳假设，G中存在有向Euler环游，设为C。在G中从任一点出发沿C的对应边前行，每当遇到上述添加边v1v2时，都用对应的两条边e1，e2代替，这样可以获得有向Euler环游。
3）G是至少有三个顶点的无向图，则G包含Euler环游等价于G中无奇度顶点。（即任意顶点的度为偶数）。
3．设G是具有n个顶点和m条边的无向图，如果G是连通的，而且满足m = n-1,证明G是树。
证明：思路一：
只需证明G中无圈。
若G中有圈，则删去圈上任一条边G仍连通。而每个连通图边数e>=n(顶点数) – 1，但删去一条边后G中只有n-2条边，此时不连通，从而矛盾，故G中无圈，所以G为树。
