《(精选)中国科学院大学历年计算机算法作业和历年习题.doc》由会员分享，可在线阅读，更多相关《(精选)中国科学院大学历年计算机算法作业和历年习题.doc（83页珍藏版）》请在金锄头文库上搜索。
1、中国科学院大学历年习题习题一 复杂性分析初步1. 试确定下述程序的执行步数，该函数实现一个mn矩阵与一个np矩阵之间的乘法： 矩阵乘法运算 template void Mult(T *a, T *b, int m, int n, int p) /mn矩阵a与np矩阵b相成得到mp矩阵c for(int i=0; im; i+) for(int j=0; jp; j+) T sum=0; for(int k=0; kn; k+) Sum+=aik*bkj; Cij=sum; 语 句 s/e 频率 总步数template void Mult(T *a, T *b, int m, int n, in
2、t p) 0 0 0for(int i=0; im; i+) 1 m+1 m+1for(int j=0; jp; j+) 1 m*(p+1) m*p+m T sum=0; 1 m*p m*p for(int k=0; kn; k+) 1 m*p*(n+1) m*p*n+m*p Sum+=aik*bkj; 1 m*p*n m*p*n Cij=sum; 1 m*p m*p 总 计 2*m*p*n+4*m*p+2*m+1其中 s/e 表示每次执行该语句所要执行的程序步数。频率是指该语句总的执行次数。2 函数MinMax用来查找数组a0:n-1中的最大元素和最小元素，以下给出两个程序。令n为实例特征。
3、试问：在各个程序中，a中元素之间的比较次数在最坏情况下各是多少？ 找最大最小元素 方法一templatebool MinMax(T a, int n, int& Min, int& Max)/寻找a0:n-1中的最小元素与最大元素 /如果数组中的元素数目小于1，则还回false if(n1) return false; Min=Max=0; /初始化 for(int i=1; iai) Min=i; if(aMaxai) Max=i; return true;最好，最坏，平均比较次数都是 2*（n-1） 找最大最小元素 方法二templatebool MinMax(T a, int n, in
4、t& Min, int& Max)/寻找a0:n-1中的最小元素与最大元素 /如果数组中的元素数目小于1，则还回false if(n1) return false; Min=Max=0; /初始化 for(int i=1; iai) Min=i; else if(aMax=(2n)/2=n，而一个含有n个顶点的树有n-1条边。因m=nn-1，故该图一定含有圈。（定义：迹是指边不重复的途径，而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不重复的闭迹称为圈。）2）证明：设有向图最长的有向迹每个顶点出度大于等于1，故存在为的出度连接点，使得成为一条有向边，
5、若则得到比更长的有向迹，与P矛盾，因此必有，从而该图一定含有有向圈。2.设D是至少有三个顶点的连通有向图。如果D中包含有向的Euler环游（即是通过D中每条有向边恰好一次的闭迹），则D中每一顶点的出度和入度相等。反之，如果D中每一顶点的出度与入度都相等，则D一定包含有向的Euler环游。这两个结论是正确的吗？请说明理由。如果G是至少有三个顶点的无向图，则G包含Euler环游的条件是什么？证明：1）若图D中包含有向Euler环游，下证明每个顶点的入度和出度相等。如果该有向图含有Euler环游，那么该环游必经过每个顶点至少一次，每经过一次，必为“进”一次接着“出”一次，从而入度等于出度。从而，对于
6、任意顶点，不管该环游经过该顶点多少次，必有入度等于出度。2）若图D中每个顶点的入度和出度相等，则该图D包含Euler环游。证明如下。对顶点个数进行归纳。当顶点数|v(D)|=2时，因为每个点的入度和出度相等，易得构成有向Euler环游。假设顶点数|v(D)|=k时结论成立，则当顶点数|v(D)|=k + 1时，任取vv(D).设S=以v为终点的边，K=以v为始点的边，因为v的入度和出度相等，故S和K中边数相等。记G=D-v.对G做如下操作:任取S和K中各一条边，设在D中，则对G和S做如下操作 , ，重复此步骤直到S为空。这个过程最终得到的G有k个顶点，且每个顶点的度与在G中完全一样。由归纳假设
7、，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为树。思路二：当时，两个顶点一条边且连通无环路，显然是
8、树。设当时，命题成立，则当时，因为G连通且无环路，所以至少存在一个顶点，他的度数为1，设该顶点所关联的边为那么去掉顶点和，便得到了一个有k-1个顶点的连通无向无环路的子图，且的边数，顶点数。由于m=n-1,所以，由归纳假设知，是树。由于相当于在中为添加了一个子节点，所以G也是树。由（1），（2）原命题得证。4. 假设用一个的数组来描述一个有向图的邻接矩阵，完成下面工作：1）编写一个函数以确定顶点的出度，函数的复杂性应为：2）编写一个函数以确定图中边的数目，函数的复杂性应为3）编写一个函数删除边，并确定代码的复杂性。解答：（1）邻接矩阵表示为，待确定的顶点为第m个顶点int CountVout(
9、int *a,int n,int m)int out = 0;for(int i=0;in;i+) if(am-1i=1) out+;return out;（2）确定图中边的数目的函数如下：int EdgeNumber(int*a,int n)int num =0;for(int i=0;in;i+) for(int j=0;jn;j+) if(aij=1) num+;return num;（3）删除边（i , j）的函数如下：void deleteEdge(int *a，int i ,int j) if(ai-1j-1=0) return; ai-1j-1 = 0;return;代码的时间复杂性为(1) 5.实现图的D-搜索算法，要求用SPARKS语言写出算法的伪代码，或者用一种计算机高级语言写出程序。解:D搜索算法的
