2010年作业题(第1、2章)

1、作业题讲解,作业15: 试用ADL语言编写一个算法，判断任一整数 n 是否为素数,算法 S (n. flag) /*判断整数n是否为素数，将结果保存到变量flag*/ S1n1？ IF (n1) THEN (flagfalse. RETURN.) S2初始化 i2. flagtrue. S3求余判断 WHILE (in-1) DO (IF (n MOD i)=0 THEN (flagfalse. RETURN.) ii+1.) 该算法的时间复杂性最好为：O(1) 最坏情况为：O(n),算法 S (n. flag) /*判断整数n是否为素数，将结果保存到变量flag*/ S1n1？ IF (n1

2、) THEN (flagfalse. RETURN.) S2初始化 i2. flagtrue. S3求余判断 WHILE (i n/2 ) DO (IF (n MOD i)=0 THEN (flagfalse. RETURN.) ii+1.) 该算法的时间复杂性最好为：O(1) 最坏情况为：O(n),算法 S (n. flag) /*判断整数n是否为素数，将结果保存到变量flag*/ S1n1？ IF (n1) THEN (flagfalse. RETURN.) S2初始化 i2. flagtrue. S3求余判断 WHILE (i n 1/2 ) DO (IF (n MOD i)=0 THE

3、N (flagfalse. RETURN.) ii+1.) 该算法的时间复杂性最好为：O(1) 最坏情况为：O(n1/2),作业111,证明对正整数n3，算法BS的元素比较次数T（n）5n/3-2。 已知信息 T（n）= 0 n=1 1 n=2 T( n/2)+T(n/2 )+2 n2 数学归纳法证明 证明 n=3 时成立 假设 n k 时都成立,证明 n= k时也成立,作业111,n=3 时， T(3)=T(1)+T(2)+2=3，5*3/3-2=3，命题成立。 假设n ，即k-1 所以有T( )5*( )/3-2, T( )5*( )/3-2 成立, .(2) 又知 k= + , (3)

4、由(1)(2)(3)，有 T(k) = T( )+T( )+2 5*( )/3-25*( )/3-2+2 = 5*( + )/3-2 = 5*k/3-2 综上，命题得证。,2-1,编写算法Reverse ( A , n)，将顺序存储的线性表A=( a1, a2, , an )转换为A=( an, a2, a1)，要求转换过程中用尽可能少的辅助空间。,2-1,只需从线性表的第一个数据元素开始，将第i个数据元素与第n-i+1个数据元素相交换即可。在这个过程中，i的变化范围是1到 。这里只需要一个辅助空间temp.,2-1,算法Reverse（A，n . A） Reverse1.元素互换 FOR i

5、=1 TO DO ( temp Ai. Ai An-i+1. An-i+1 temp. ). ,2-8,设计一个算法，将链表的链接完全颠倒。,算法1：类似于习题2-1，将第i个与第n-i+1个结点的数据域互换。 算法2：遍历链表的同时修改指针。 算法3：使用堆栈，实现单链表求逆。,2-8,算法 reverse ( head. head) /*将指针 head 所指向的链表倒置*/ RV1指针初始化 /q,p,r 分别指向三个连续的结点 q NULL. p next(head). r next(p). RV2反转链表 WHILE( rNULL ) DO ( next(p) q. /反转结点p qp. /移动3个指针 pr. r next(r). ) RV3最后一个结点的处理 next(p)q. next(head)p.,2-17,对于顺序堆栈和链式堆栈s，分别编写函数SelectItem（ Stack flag = true; while(!te