1、.第13章习题.作业15 试用试用ADL语言编写一个算法，判断任一整数语言编写一个算法，判断任一整数 n 是否为素数。是否为素数。.考察知识点考察知识点l判断素数判断素数n素数素数大于大于1的自然数中，除了的自然数中，除了1和此整和此整数自身外，不能被其他自然数整除的数。数自身外，不能被其他自然数整除的数。n判断：对于指定的判断：对于指定的n，如果，如果2,n-1内的整内的整数都不能整除数都不能整除n，则，则n为素数。为素数。lADL语言写算法语言写算法n算法证明很难，可以使用边界条件和特殊算法证明很难，可以使用边界条件和特殊数据，人工模拟算法执行过程。数据，人工模拟算法执行过程。.完成情况完
2、成情况n思想思想基本正确，对素数定义的理解：基本正确，对素数定义的理解：1？n算法算法特殊情况处理：特殊情况处理：n 1？算法输出；？算法输出；nADL语言的使用：语言的使用：运算符号：运算符号：MOD(模模)，DIV(除数除数)，/(除除)；，（取整）；（取整）；？sqrt?fabs()?输入输出参数：设置返回值；中间用输入输出参数：设置返回值；中间用“.”分隔；分隔；条件语句：条件语句：if then else ；for i1 to n step 1(i=i+1?)赋值语句：赋值语句：.参考答案算法算法 S(n.flag)/*判断整数判断整数n是否为素数，将结果保存到变量是否为素数，将结果
3、保存到变量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.).n正确性验证：正确性验证：n假定假定n7，模拟执行过程，对，模拟执行过程，对i2，3，4，5，6时，分别判断时，分别判断(7 mod i)的取值是否的取值是否为为0。n改进：改进：n-1？n/2 、n1/21/2 n=a b,na2,bn/2,a,b,2,bn/2,a,b,n/2 nann1/21/2,bn,bn1/21/2
4、,a,a,n1/21/2 ,b,b.参考答案2算法算法 S(n.flag)/*判断整数判断整数n是否为素数，将结果保存到变量是否为素数，将结果保存到变量flag*/S1n1？IF(n1)THEN(flagfalse.RETURN.)S2初始化初始化 i2.flagtrue.S3求余判断求余判断 WHILE(i n/2 )DO (IF(n MOD i)=0 THEN (flagfalse.RETURN.)ii+1.).作业1-8n若若A(n)=amnm+a1n+a0是关于是关于n的的m次多项式，次多项式，证明证明A(n)=O(nm)。n设设f(n)和和g(n)是正整数集到正实数集的函数，称是正整
5、数集到正实数集的函数，称f(n)是是O(g(n)当且仅当存在正常数当且仅当存在正常数C和和n0，使得对任，使得对任意的意的n n0，有，有f(n)Cg(n)。n完成情况完成情况：令：令n01，C am+a1+a0，amnm+a1n+a0 Cnm 注意：注意：当当ai 0时，时，aini ainm不一定成立不一定成立。.n证明：对于所有的证明：对于所有的n1，有：，有：A(n)=i=0,maini i=0,m|ai|ni nm i=0,m|ai|ni-m nm i=0,m|ai|令令C i=0,m|ai|，有，有A(n)Cnm 所以，所以，A(n)=O(nm)。参考答案参考答案.作业111n 证
6、明对正整数证明对正整数n3，算法，算法BS的元素比较的元素比较次数次数T(n)5n/3-2。n已知：已知：0 n=1 T(n)=1 n=2 T(n/2 )+T(n/2 )+2 n2.n考察知识点考察知识点：数学归纳法：数学归纳法n基础归纳：基础归纳：n=c(初值初值)时，命题是正确的；时，命题是正确的；n归纳步骤：如果归纳步骤：如果nk1时，命题成立，则时，命题成立，则nk时，命题也成立。时，命题也成立。n完成情况完成情况：n利用结论利用结论T(n)3n/22，需要注意前提，需要注意前提条件条件当当n是是2的幂时的幂时；由由n=k反推反推nk-1时的情况。时的情况。.0 n=1 T(n)=1
7、n=2 T(n/2 )+T(n/2 )+2 n2nn=3 时，时，T(3)=T(1)+T(2)+2=3，5 3/3-2=3，命题成立。，命题成立。n假设假设n (k+1)/2 (k+1)/2 ，即即k (k+1)/2 (k+1)/2 所以：所以：T(k+1)/2 )5(k+1)/2)/3-2,(1)T(k+1)/2 )5(k+1)/2 )/3-2 (2)T(k+1)=T(k+1)/2 )+T(k+1)/2)+2 5(k+1)/2)/3-25(k+1)/2 )/3-2+2 =5(k+1)/2 +(k+1)/2 )/3-2 /k1=(k+1)/2 +(k+1)/2 =5(k+1)/3-2 综上，命
8、题得证。综上，命题得证。.作业112n给出算法给出算法BS的非递归算法，并说明算法最的非递归算法，并说明算法最多需要多大的辅助空间。多需要多大的辅助空间。.算法算法SM(A,n.max,min)SM1初始化初始化 maxminA1.SM2比较比较 FOR I=2 TO n DO/求最大和最小元素求最大和最小元素 (IF AI max THEN maxAI.IF AI min THEN minAI).BS算法算法算法BS（A，i，j.fmax，fmin）/在数组在数组A的第的第i个元素到第个元素到第j个元素之间寻找最大和最个元素之间寻找最大和最/小元素，已知小元素，已知i j。BS1 递归出口递
9、归出口IF i=j THEN（fmaxfminAi.RETURN.）IF i=j 1 THEN（IF Ai Aj THEN（fmaxAj.fminAi）.ELSE（fmaxAi.fminAj）.RETURN）.BS2 取中值取中值 mid (i+j)/2 BS3 递归调用递归调用 BS（A，i，mid.gmax，gmin）BS（A，mid+1，j.hmax，hmin）.BS4 合并合并 fmaxmaxgmax，hmax.fminmingmin，hmin.完成情况完成情况n做的很少做的很少nSM方法；（没有体现分治思想）方法；（没有体现分治思想）n依次对比邻近的两个元素，找到较大较小者，依次对比
10、邻近的两个元素，找到较大较小者，不断更新全局最大最小值；不断更新全局最大最小值；n依次对比，用数组存放每对的最大最小值；依次对比，用数组存放每对的最大最小值；n两个栈分别存放当前起始和终止元素下标；两个栈分别存放当前起始和终止元素下标；一个栈存储中间值，另一个存放最大最小值。一个栈存储中间值，另一个存放最大最小值。（没法确定起始和终止元素的下标）（没法确定起始和终止元素的下标）.n辅助空间辅助空间：因为采用某种特殊结构，而增加：因为采用某种特殊结构，而增加占用的空间；占用的空间；n占用空间占用空间：算法运行所需要的空间；：算法运行所需要的空间；n方法方法3：数组；：数组；n方法方法4：栈：栈.
11、方法4n基本思想基本思想：n创建两个栈，一个存放起始元素的下标，一创建两个栈，一个存放起始元素的下标，一个存放终止元素的下标。个存放终止元素的下标。n每次从栈中弹出一对下标，若两者相等或相每次从栈中弹出一对下标，若两者相等或相差为差为1，则找到最大最小值，否则找到中间，则找到最大最小值，否则找到中间下标，形成两对新的下标，压入栈内。下标，形成两对新的下标，压入栈内。.示例n数组A=3,9,21,15,8,1916初始：压入起始和结束下标初始：压入起始和结束下标 1和和6；循环：循环：弹出元素弹出元素1和和6；两者不相等、；两者不相等、相差不相差不为为1；取中值取中值(1+6)/2=3；形成两；
12、形成两对新的下标，对新的下标，(1,3)和和(4,6);压入栈；压入栈；弹出弹出4和和6，两者不相等、相差不为两者不相等、相差不为1；取中值取中值(4+6)/2=5；形成两对新的；形成两对新的下标，下标，(4,5)和和(6,6);压入栈内；压入栈内；1346134566.A=3,9,21,15,8,19134566弹出弹出(6,6)，相等，元素值为，相等，元素值为19，则，则fmax maxfmax,19=19，fmin minfmin,19=19；弹出弹出(4,5)，相差为，相差为1，元素值为，元素值为15和和8，则，则fmax max19,15,8=19，fmin min19,15,8=8
13、；13.参考答案n算法算法f(A,i,j.fmax,fmin)nf1.初始化初始化 fmaxfminAi.Lstack left;Lstack right;/存储起始和终止下标存储起始和终止下标 left.push(i).right.push(j).nf2.求最大、最小值求最大、最小值 While(!left.IsEmpty()DO (l left.pop().r right.pop().IF l=r THEN /相等相等 (fmaxmaxfmax,Al.fmin minfmin,Al.)ELSE(IF r-l=1 /相差为相差为1 THEN(fmaxmaxfmax,Al,Ar.fmin mi
14、nfmin,Al,Ar.)ELSE(mid=(i+j)/2.left.push(l).left.push(mid+1).right.push(mid).Right.push(r).).n辅助空间：栈辅助空间：栈nn/2n/2n/4n/41log2n.作业21编写算法编写算法Reverse(A,n)，将顺序存储的，将顺序存储的线性表线性表A=(a1,a2,an)转换为转换为A=(an,a2,a1)，要求转换过程中使用尽可能少的辅，要求转换过程中使用尽可能少的辅助空间。助空间。关键点关键点：限制辅助空间的使用：限制辅助空间的使用如果没有这个限制，则可以有多种方法：如果没有这个限制，则可以有多种方法
15、：n辅助数组；辅助数组；n双下标同时向中间移动双下标同时向中间移动.分析n只需从线性表的第一个数据元素开始，只需从线性表的第一个数据元素开始，将第将第i i个数据元素与第个数据元素与第n-i+1n-i+1个数据元素个数据元素相交换即可。相交换即可。ni i的变化范围是的变化范围是1 1到到 n/2n/2。a a1 1a a2 2a an-1n-1a an na an na an-1n-1a a2 2a a1 11+n1+n2+(n-1)2+(n-1)(n-1)+2(n-1)+2 n+1n+1.参考答案算法算法ReverseReverse（A A，n.An.A）Reverse1.Reverse1
16、.元素互换元素互换 FOR i=1 TO FOR i=1 TO n/2 DO DO Ai An-i+1.Ai An-i+1.作业2-8n在单链表类在单链表类SLISTSLIST中添加一个成员函数，将单中添加一个成员函数，将单链表中元素的次序完全颠倒。链表中元素的次序完全颠倒。.n利用堆栈；利用堆栈；n从表头删除，插入表尾；从表头删除，插入表尾；(不推荐不推荐)n换数据域的取值，换数据域的取值，p1和和p2向中间移动，更换向中间移动，更换数据域的取值。数据域的取值。headp1p2.方法4n思想：从左向右，依次更换邻近结点的指针方向。思想：从左向右，依次更换邻近结点的指针方向。n初始设置，第一个
17、元素需要被放到表尾，指向空指初始设置，第一个元素需要被放到表尾，指向空指针，针，p1=null，p2=next(head)/第一个元素第一个元素headp22p3345p1nullp11p26P3 next(p2)next(P2)P1./反转P1 P2.P2 P3.参考答案n算法 Reverse(head.head)/*将指针 head 所指向的链表倒置*/RV1空链表和1个节点链表 IF(next(head)=NULL)RETURN.RV2指针初始化/P1,P2 分别指向两个连续的节点P1 NULL.P2 next(head).RV3反转链表WHILE(P2 NULL)DO(P3 next(
18、p2)next(P2)P1./反转节点指针 P1 P2.P2 P3./移动3个指针）RV4head指向反转链表 next(head)P1.p1p2.作业211n已知线性表中的元素以已知线性表中的元素以data值递增有序排列，并以值递增有序排列，并以单链表做存储结构。试写一高效的算法，删除表中单链表做存储结构。试写一高效的算法，删除表中所有值大于所有值大于mink且小于且小于maxk的元素，同时释放被的元素，同时释放被删结点空间，并分析算法的时间复杂度。删结点空间，并分析算法的时间复杂度。n链表是有序的：链表是有序的：找到区间找到区间n特殊情况的处理特殊情况的处理：表为空，：表为空，元素都大于元
19、素都大于maxk(第一个元素大于第一个元素大于maxk)；元素都小于元素都小于mink(最后一个元素小于最后一个元素小于mink)。.n主要思想主要思想：找到大于找到大于mink的第一个元素，删除操作，直至元的第一个元素，删除操作，直至元素大于素大于maxk。n时间复杂度时间复杂度：比较为基本运算比较为基本运算 最好最好：空，元素都大于空，元素都大于maxk（找不到）（找不到）/O(1)最坏：元素都小于最坏：元素都小于mink（找不到），（找不到），元素都小于元素都小于maxk，O(n)；.算法 LD(L,mink,maxk)nLD1.特殊情况特殊情况 IF mink maxk THEN(RE
20、TURN.)nLD2.初始化初始化 phead.prevp.p next(p)nLD3.找找 WHILE(p NULL AND data(p)maxk)DO (IF(data(p)mink)THEN (prev p.p next(p)/向后移动向后移动 ELSE(next(prev)next(p).q p.p next(p).AVAILq.)/删除删除qRETURN.prevheadpPprevp.作业217n对于顺序堆栈和链式堆栈对于顺序堆栈和链式堆栈s，分别编写函数，分别编写函数SelectItem(Stack&s,int n)，要求在，要求在堆栈中查找元素堆栈中查找元素n在栈中第一次出现
21、的位置，在栈中第一次出现的位置，并将该位置元素移至栈顶，同时其他元素并将该位置元素移至栈顶，同时其他元素次序不变。（注意：用次序不变。（注意：用int匹配堆栈的模板）匹配堆栈的模板）.n基本思想基本思想：n取栈顶元素，若不匹配，则进行弹栈操作；取栈顶元素，若不匹配，则进行弹栈操作；n找到（或无法找到）后恢复原来的元素次找到（或无法找到）后恢复原来的元素次序。序。n关键点：关键点：记录弹出的顺序，后弹出的元素能记录弹出的顺序，后弹出的元素能够先被压回原来的栈够先被压回原来的栈，因此需要使用一个辅，因此需要使用一个辅助堆栈。助堆栈。.示例101051511212s shelpStackhelpSt
22、ack51517 73 3n=5151511212101051517 73 37 751515151121210103 37 77 73 35151.参考答案int SelectItem(Stack&s,int n)AStack temp(100);/顺序堆栈，辅助栈顺序堆栈，辅助栈 /LStack temp;/链式堆栈链式堆栈 bool flag=false;/是否存在元素是否存在元素n int loc=0;/记录记录n所在的位置所在的位置 while(!s.isEmpty()&s.Peek()!=n)temp.Push(s.Pop();loc+;栈非空且当前元素不等于n.if(!s.isE
23、mpty()s.Pop();flag=true;/弹出弹出n while(!temp.isEmpty()/将辅助栈中元素压入原栈将辅助栈中元素压入原栈 s.Push(temp.Pop();if(flag)then s.Push(n)；else loc=-1;return loc;因为找到元素而跳出循环.作业225n编写并实现双端队列类，双端队列是可进行如编写并实现双端队列类，双端队列是可进行如下操作的线性表。下操作的线性表。n(1)push(item)item插入到队列的前端；插入到队列的前端；n(2)pop(item)删除前端元素且赋给删除前端元素且赋给item；n(3)inject(ite
24、m)item插入尾端；插入尾端；n(4)eject(item)删除尾端元素且赋给删除尾端元素且赋给item.n结点结构结点结构SLNode：数据域和指针域；：数据域和指针域；n类成员：队首和队尾的类成员：队首和队尾的SLNode类型指针、指示元类型指针、指示元素个数的整型变量；素个数的整型变量；nPush(item插入队列前端插入队列前端)若空，则加入一个以若空，则加入一个以item为数据域的结点，元素为数据域的结点，元素个数为个数为1；否则，；否则，temp记录原队首指针记录原队首指针front；创建以创建以item为数据域的新结点，作为新的队首，赋为数据域的新结点，作为新的队首，赋值给值给
25、front；front的指针域指向的指针域指向temp，元素个数加，元素个数加1。.nPop(删除前端元素，并赋值删除前端元素，并赋值item)n若空，则错误；否则，若空，则错误；否则，temp记录原队首指针记录原队首指针front；队首后移，即队首后移，即frontnext(front)；返回返回temp的数据域；的数据域；删除删除temp结点，元素个数减结点，元素个数减1；若大小为零，则队尾指针若大小为零，则队尾指针rear赋值为赋值为NULL。.nInject(item插入队尾插入队尾)n若空，则加入一个以若空，则加入一个以item为数据域的结为数据域的结点，元素个数为点，元素个数为1；
26、否则，；否则，创建以创建以item为数据域的新结点为数据域的新结点temp，作为新的队尾，即作为新的队尾，即next(rear)temp；队尾指针后移，即队尾指针后移，即rear next(rear);元素个数加元素个数加1。.nEject(删除队尾元素并赋值给删除队尾元素并赋值给item)n若空，则出错；否则，若空，则出错；否则，找到队尾指针的前驱指针找到队尾指针的前驱指针 temp front.IF(temp rear)THEN (WHILE(next(temp)rear)DO (temp next(temp)队尾指针更新，即队尾指针更新，即rear temp，要删除结点是要删除结点是ne
27、xt(temp)，返回数据域，删除结点，元，返回数据域，删除结点，元素个数减素个数减1。若大小为零，若大小为零，front和和rear赋值为赋值为NULL。.作业310n设稀疏矩阵设稀疏矩阵M Mm m n n中有中有t t个非零元素，用三元个非零元素，用三元组表的方式存储组表的方式存储.请设计一个算法，计算请设计一个算法，计算矩阵矩阵M M的转置矩阵的转置矩阵N N，且算法的时间复杂性，且算法的时间复杂性为为O(n+t).O(n+t).注意，书中给出的算法的复杂注意，书中给出的算法的复杂性为性为O(nO(n t)t)。.M=50 0 0 010 0 20 0 0 0 0 0-30 0 -60
28、 5N=50 10 0 -300 0 0 00 20 0 -600 0 0 50050a01010a11220a230-30a332-60a4335a50050b00110b103-30b22120b323-60b4335b5算法的关键是求出算法的关键是求出a中元素在中元素在b中的位置中的位置.a0a1a2a3a4a500502120011033523-6003-30j=0,k=0,a0,列坐标=0；存储j=0;k=1;a1,列坐标=0；存储j=0;k=2;a2,列坐标=2；j=0;k=3;a3,列坐标=0；存储j=0;k=4;j=0;k=5;j=1;k=0005030-301010.a0a1
29、a2a3a4a500502120011033523-6003-30005030-301010j=1,k=0,a0,列坐标=0j；j=1,k=1;列坐标1j=1,k=2;j=1,k=3;j=1,k=4;j=1,k=5;j=2,k=0；j=2,k=1；j=2,k=2，列坐标=2=j2201.005030-30101033532-601220a0a1a2a3a4a500502120011033523-6003-30b2axby?y=列坐标小于列坐标小于col(ax)的元素个数的元素个数+列坐标等于列坐标等于col(ax)且在且在ax之前的之前的 元素个数元素个数.a0a1a2a3a4a5005021
30、20011033523-6003-30基本思想：302101230123num0335pos.a0a1a2a3a4a500502120011033523-6003-3003102231num00132335pos005030-30101033532-601220b0b1b2b3b4b5.a0a1a2a3a4a500502120011033523-6003-300335pos0050.a0a1a2a3a4a500502120011033523-6003-301335pos00501010.a0a1a2a3a4a500502120011033523-6003-302335pos0050101012
31、20.a0a1a2a3a4a500502120011033523-6003-302345pos005030-3010101220.a0a1a2a3a4a500502120011033523-6003-303345pos005030-30101032-601220.a0a1a2a3a4a500502120011033523-6003-303355pos005030-30101033532-601220.a0a1a2a3a4a500502120011033523-6003-303356pos005030-30101033532-601220.f(j)a b c a b c a c a b c a-1 -1 -1 0 1 2 3 -1 0 1 2 3 作业2-15.a b c a a b b a b c a b .
