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

作业题讲解作业1－5:试用ADL语言编写一个算法，判断任一整数n是否为素数算法S(n.flag)/*判断整数n是否为素数，将结果保存到变量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判断]WHILE(i≤n-1)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌该算法的时间复杂性最好为：O(1)最坏情况为：O(n)算法S(n.flag)/*判断整数n是否为素数，将结果保存到变量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判断]WHILE(i≤「n/2)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌该算法的时间复杂性最好为：O(1)最坏情况为：O(n)算法S(n.flag)/*判断整数n是否为素数，将结果保存到变量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判断]WHILE(i≤「n1/2)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌该算法的时间复杂性最好为：O(1)最坏情况为：O(n1/2)作业1－11证明对正整数n≥3，算法BS的元素比较次数T（n）≤5n/3-2。已知信息T（n）=0n=11n=2T(n/2」)+T(「n/2)+2n2数学归纳法证明证明n=3时成立假设nk时都成立,证明n=k时也成立作业1－11n=3时，T(3)=T(1)+T(2)+2=3，5*3/3-2=3，命题成立。假设nk时命题成立。n=k时,T(k)=T()+T()+2,...(1)当k≥3时，有k≥，即k-1≥≥所以有T()≤5*()/3-2,T()≤5*()/3-2成立,...(2)又知k=+,…(3)由(1)(2)(3)，有T(k)=T()+T()+2≤[5*()/3-2]＋[5*()/3-2]+2=5*(+)/3-2=5*k/3-2综上，命题得证。k/2k/22/kk/2k/2k/2k/22/k2/kk/2k/22/k2/kk/2k/2k/22/k2/k2-1编写算法Reverse(A[],n)，将顺序存储的线性表A=(a1,a2,…,an)转换为A=(an,…,a2,a1)，要求转换过程中用尽可能少的辅助空间。2-1只需从线性表的第一个数据元素开始，将第i个数据元素与第n-i+1个数据元素相交换即可。在这个过程中，i的变化范围是1到。这里只需要一个辅助空间temp.n/22-1算法Reverse（A，n.A）Reverse1.[元素互换]FORi=1TODO(temp←A[i].A[i]←A[n-i+1].A[n-i+1]←temp.).▌n/22-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(r≠NULL)DO(next(p)q.//反转结点pqp.//移动3个指针pr.rnext(r).)RV3[最后一个结点的处理]next(p)q.next(head)p.▌2-17对于顺序堆栈和链式堆栈s，分别编写函数SelectItem（Stack&s，intn），要求在堆栈中查找元素n在栈中第一次出现的位置，并将该位置元素移至栈顶，同时其他元素次序不变。（注意：用int匹配堆栈的模板）2-17算法思想示例：n=34103412stemp3472103412stemp3472103412stemp3472从使用的角度来讲，链式堆栈与顺序堆栈没有区别。2-17intSelectItem(Stackint&s,intn){AStackinttemp(100);//顺序堆栈LStackinttemp;//链式堆栈booleanflag=false;intloc=0;while(!s.isEmpty()&&s.Peek()!=n){temp.Push(s.Pop());loc++;}2-17if(s.peek()==n)then{s.Pop();flag=true;}while(!temp.isEmpty())s.Push(temp.Pop());if(flag)thens.Push(n)elseloc=-1;returnloc;}