【习题课】第1-3章课件

第1－3章习题.第1－3章习题.1作业1－5

试用ADL语言编写一个算法，判断任一整数n是否为素数。.作业1－5试用ADL语言编写一个算法，判断任一整数n2考察知识点判断素数素数——大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。判断：对于指定的n，如果[2,n-1]内的整数都不能整除n，则n为素数。ADL语言写算法算法证明很难，可以使用边界条件和特殊数据，人工模拟算法执行过程。.考察知识点判断素数.3完成情况思想——基本正确，对素数定义的理解：1？算法——特殊情况处理：n1？算法输出；ADL语言的使用：运算符号：MOD(模)，DIV(除数)，/(除)；

，（取整）；％？sqrt?fabs()?

输入输出参数：设置返回值；中间用“.”分隔；条件语句：ifthenelse；

fori＝1tonstep1(i=i+1?)

赋值语句：.完成情况思想——基本正确，对素数定义的理解：1？.4参考答案算法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.)▌.参考答案算法S(n.flag).5正确性验证：假定n＝7，模拟执行过程，对i＝2，3，4，5，6时，分别判断(7modi)的取值是否为0。改进：n-1？——n/2、n1/2n=ab,a≥2,b≤n/2,…a,…b,…n/2a≤n1/2,b≥n1/2,…a,…n1/2,…b…

.正确性验证：.6参考答案2算法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.)▌.参考答案2算法S(n.flag).7作业1-8若A(n)=amnm+…+a1n+a0是关于n的m次多项式，证明A(n)=O(nm)。设f(n)和g(n)是正整数集到正实数集的函数，称f(n)是O(g(n))当且仅当存在正常数C和n0，使得对任意的nn0，有f(n)Cg(n)。完成情况：令n0＝1，C＝am+…+a1+a0，

amnm+…+a1n+a0Cnm

注意：当ai0时，ainiainm不一定成立。.作业1-8若A(n)=amnm+…+a1n+a0是关于n的m8证明：对于所有的n≥1，有：

A(n)=i=0,…,maini≤i=0,…,m|ai|ni≤

nmi=0,…,m|ai|ni-m

≤

nmi=0,…,m|ai|

令C＝i=0,…,m|ai|，有A(n)≤

Cnm

所以，

A(n)=O(nm)。参考答案.证明：对于所有的n≥1，有：参考答案.9作业1－11

证明对正整数n≥3，算法BS的元素比较次数T(n)≤5n/3-2。已知：0n=1T(n)=1n=2T(n/2)+T(n/2)+2n>2.作业1－11证明对正整数n≥3，算法BS的元素比较次数T(10考察知识点：数学归纳法基础归纳：n=c(初值)时，命题是正确的；归纳步骤：如果n＝k－1时，命题成立，则n＝k时，命题也成立。完成情况：利用结论T(n)＝3n/2－2，需要注意前提条件——当n是2的幂时；由n=k反推n＝k-1时的情况。.考察知识点：数学归纳法.110n=1

T(n)=1n=2

T(n/2)+T(n/2)+2n>2n=3时，T(3)=T(1)+T(2)+2=3，53/3-2=3，命题成立。假设n<=k时命题成立，需证明n=k+1时成立。

当k≥3时，有(k+1)>(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-2]＋[5((k+1)/2)/3-2]+2=5((k+1)/2+(k+1)/2)/3-2//k＋1=(k+1)/2+(k+1)/2

=5(k+1)/3-2综上，命题得证。.012作业1－12给出算法BS的非递归算法，并说明算法最多需要多大的辅助空间。.作业1－12给出算法BS的非递归算法，并说明算法最多需要多大13算法SM(A,n.max,min)

SM1[初始化]max←min←A[1].

SM2[比较]

FORI=2TOnDO

//求最大和最小元素

(IFA[I]>maxTHENmax←A[I].IFA[I]<minTHENmin←A[I]).

▌.算法SM(A,n.max,min).14BS算法算法BS（A，i，j.fmax，fmin）//在数组A的第i个元素到第j个元素之间寻找最大和最//小元素，已知ij。BS1[递归出口]IFi=jTHEN（fmax←fmin←A[i].RETURN.）IFi=j1THEN

（IFA[i]<A[j]THEN（fmax←A[j].fmin←A[i]）. ELSE（fmax←A[i].fmin←A[j]）.RETURN）..BS算法算法BS（A，i，j.fmax，fmin）15BS2[取中值] mid←(i+j)/2BS3[递归调用]BS（A，i，mid.gmax，gmin）

BS（A，mid+1，j.hmax，hmin）.BS4[合并] fmax←max{gmax，hmax}. fmin←min{gmin，hmin}.■

.BS2[取中值].16完成情况做的很少SM方法；（没有体现分治思想）依次对比邻近的两个元素，找到较大较小者，不断更新全局最大最小值；依次对比，用数组存放每对的最大最小值；两个栈分别存放当前起始和终止元素下标；一个栈存储中间值，另一个存放最大最小值。（没法确定起始和终止元素的下标）.完成情况做的很少.17辅助空间：因为采用某种特殊结构，而增加占用的空间；占用空间：算法运行所需要的空间；方法3：数组；方法4：栈.辅助空间：因为采用某种特殊结构，而增加占用的空间；.18方法4基本思想：创建两个栈，一个存放起始元素的下标，一个存放终止元素的下标。每次从栈中弹出一对下标，若两者相等或相差为1，则找到最大最小值，否则找到中间下标，形成两对新的下标，压入栈内。.方法4基本思想：.19示例数组A=[3,9,21,15,8,19]16初始：压入起始和结束下标1和6；循环：弹出元素1和6；两者不相等、相差不为1；取中值(1+6)/2=3；形成两对新的下标，(1,3)和(4,6);压入栈；弹出4和6，两者不相等、相差不为1；取中值(4+6)/2=5；形成两对新的下标，(4,5)和(6,6);压入栈内；1346134566.示例数组A=[3,9,21,15,8,19]16初始：压入起20A=[3,9,21,15,8,19]134566弹出(6,6)，相等，元素值为19，则fmaxmax{fmax,19}=19，fminmin{fmin,19}=19；弹出(4,5)，相差为1，元素值为15和8，则fmaxmax{19,15,8}=19，fminmin{19,15,8}=8；13.A=[3,9,21,15,8,19]134566弹出(6,621参考答案算法f(A,i,j.fmax,fmin)f1.[初始化]fmaxfminA[i].Lstack<int>left;Lstack<int>right;//存储起始和终止下标left.push(i).right.push(j).f2.[求最大、最小值]While(!left.IsEmpty())DO(lleft.pop().rright.pop().

.参考答案算法f(A,i,j.fmax,fmin).22IFl=rTHEN//相等(fmaxmax{fmax,A[l]}.fminmin{fmin,A[l]}.)ELSE(IFr-l=1//相差为1THEN(fmaxmax{fmax,A[l],A[r]}.fminmin{fmin,A[l],A[r]}.)ELSE(mid=(i+j)/2.left.push(l).left.push(mid+1).right.push(mid).Right.push(r).))).IFl=rTHEN//23辅助空间：栈nn/2n/2n/4n/4…1log2n.辅助空间：栈nn/2n/2n/4n/4…1log2n.24作业2－1编写算法Reverse(A[],n)，将顺序存储的线性表A=(a1,a2,…,an)转换为A=(an,…,a2,a1)，要求转换过程中使用尽可能少的辅助空间。关键点：限制辅助空间的使用如果没有这个限制，则可以有多种方法：辅助数组；双下标同时向中间移动.作业2－1编写算法Reverse(A[],n)，将顺25分析只需从线性表的第一个数据元素开始，将第i个数据元素与第n-i+1个数据元素相交换即可。i的变化范围是1到n/2。a1a2…an-1ananan-1…a2a11+n2+(n-1)…(n-1)+2n+1.分析只需从线性表的第一个数据元素开始，将第i个数据元素与第n26参考答案算法Reverse（A，n.A）Reverse1.[元素互换]FORi=1TOn/2DOA[i]←→A[n-i+1].▌.参考答案算法Reverse（A，n.A）.27作业2-8在单链表类SLIST中添加一个成员函数，将单链表中元素的次序完全颠倒。.作业2-8在单链表类SLIST中添加一个成员函数，将单链表中28利用堆栈；从表头删除，插入表尾；(不推荐)换数据域的取值，p1和p2向中间移动，更换数据域的取值。…headp1p2.利用堆栈；…headp1p2.29方法4思想：从左向右，依次更换邻近结点的指针方向。初始设置，第一个元素需要被放到表尾，指向空指针，p1=null，p2=next(head)//第一个元素headp22p3345p1nullp11p26P3next(p2)next(P2)P1. //反转P1P2.P2P3..方法4思想：从左向右，依次更换邻近结点的指针方向。headp30参考答案算法Reverse(head.head)/*将指针head所指向的链表倒置*/RV1[空链表和1个节点链表]IF(next(head)=NULL)RETURN.RV2[指针初始化] //P1,P2分别指向两个连续的节点

P1NULL. P2next(head)..参考答案算法Reverse(head.head).31RV3[反转链表] WHILE(P2≠NULL)DO (P3next(p2) next(P2)P1. //反转节点指针

P1P2.P2P3.//移动3个指针 ）RV4[head指向反转链表]

next(head)P1.

▌p1p2.RV3[反转链表]p1p2.32作业2－11已知线性表中的元素以data值递增有序排列，并以单链表做存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素，同时释放被删结点空间，并分析算法的时间复杂度。链表是有序的：找到区间特殊情况的处理：表为空，元素都大于maxk(第一个元素大于maxk)；元素都小于mink(最后一个元素小于mink)。.作业2－11已知线性表中的元素以data值递增有序排列，并以33主要思想：找到大于mink的第一个元素，删除操作，直至元素大于maxk。时间复杂度：比较为基本运算最好：空，元素都大于maxk（找不到）//O(1)最坏：元素都小于mink（找不到），

元素都小于maxk，O(n)；.主要思想：.34算法LD(L,mink,maxk)LD1.[特殊情况]IF

minkmaxkTHEN(RETURN.)LD2.[初始化]p←head.prev←p.p←next(p)LD3.[找]WHILE(pNULLANDdata(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.算法LD(L,mink,maxk)LD1.[特殊情况35作业2－17对于顺序堆栈和链式堆栈s，分别编写函数SelectItem(Stack&s,intn)，要求在堆栈中查找元素n在栈中第一次出现的位置，并将该位置元素移至栈顶，同时其他元素次序不变。（注意：用int匹配堆栈的模板）.作业2－17对于顺序堆栈和链式堆栈s，分别编写函数Selec36基本思想：取栈顶元素，若不匹配，则进行弹栈操作；找到（或无法找到）后恢复原来的元素次序。关键点：记录弹出的顺序，后弹出的元素能够先被压回原来的栈，因此需要使用一个辅助堆栈。.基本思想：.37示例105112shelpStack5173n=515112105173751511210377351.示例105112shelpStack5173n=51511238参考答案intSelectItem(Stack<int>&s,intn){AStack<int>temp(100);//顺序堆栈，辅助栈

//LStack<int>temp;//链式堆栈

boolflag=false;//是否存在元素nintloc=0;//记录n所在的位置

while(!s.isEmpty()&&s.Peek()!=n

){temp.Push(s.Pop());loc++;}栈非空且当前元素不等于n.参考答案intSelectItem(Stack<int>39if(!s.isEmpty()){s.Pop();flag=true;}//弹出nwhile(!temp.isEmpty())//将辅助栈中元素压入原栈

{s.Push(temp.Pop());}if(flag)thens.Push(n)；

elseloc=-1;returnloc;}因为找到元素而跳出循环.if(!s.isEmpty())因为找到元素40作业2－25编写并实现双端队列类，双端队列是可进行如下操作的线性表。(1)push(item)－－item插入到队列的前端；(2)pop(item)－－删除前端元素且赋给item；(3)inject(item)－－item插入尾端；(4)eject(item)－－删除尾端元素且赋给item.作业2－25编写并实现双端队列类，双端队列是可进行如下操作的41结点结构SLNode：数据域和指针域；类成员：队首和队尾的SLNode类型指针、指示元素个数的整型变量；Push(item插入队列前端)

若空，则加入一个以item为数据域的结点，元素个数为1；否则，temp记录原队首指针front；

创建以item为数据域的新结点，作为新的队首，赋值给front；front的指针域指向temp，元素个数加1。.结点结构SLNode：数据域和指针域；.42Pop(删除前端元素，并赋值item)若空，则错误；否则，temp记录原队首指针front；

队首后移，即frontnext(front)；

返回temp的数据域；

删除temp结点，元素个数减1；

若大小为零，则队尾指针rear赋值为NULL。.Pop(删除前端元素，并赋值item).43Inject(item插入队尾)若空，则加入一个以item为数据域的结点，元素个数为1；否则，创建以item为数据域的新结点temp，作为新的队尾，即next(rear)temp；队尾指针后移，即rearnext(rear);元素个数加1。.Inject(item插入队尾).44Eject(删除队尾元素并赋值给item)若空，则出错；否则，

找到队尾指针的前驱指针tempfront.IF(temprear)THEN(WHILE(next(temp)rear)DO(tempnext(temp))队尾指针更新，即reartemp，

要删除结点是next(temp)，返回数据域，删除结点，元素个数减1。

若大小为零，front和rear赋值为NULL。.Eject(删除队尾元素并赋值给item).45作业3－10设稀疏矩阵Mmn中有t个非零元素，用三元组表的方式存储.请设计一个算法，计算矩阵M的转置矩阵N，且算法的时间复杂性为O(n+t).注意，书中给出的算法的复杂性为O(nt)。.作业3－10设稀疏矩阵Mmn中有t个非零元素，用三元组表的46M=500001002000000-300-605N=50100-3000000200-6000050050a[0]1010a[1]1220a[2]30-30a[3]32-60a[4]335a[5]0050b[0]0110b[1]03-30b[2]2120b[3]23-60b[4]335b[5]算法的关键是求出a中元素在b中的位置.M=50000N=501047Bindex＝0；FORj=0TOn－1DO

FORk=0TOt－1DOIFcol(A[k])=jThen (row(B[Bindex])=j. col(B[Bindex])=row(A[k]). value(B[Bindex])=Value(A[k]).

Bindex++）a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30j=0,k=0,a[0],列坐标=0；存储j=0;k=1;a[1],列坐标=0；存储j=0;k=2;a[2],列坐标=2；j=0;k=3;a[3],列坐标=0；存储j=0;k=4;j=0;k=5;j=1;k=0005030-301010.Bindex＝0；a[0]0050212001103352348a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30005030-301010j=1,k=0,a[0],列坐标=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=jFORj=0TOn－1DO

FORk=0TOt－1DOIFcol(A[k])=jThen2201.a[0]00502120011033523-6003-30049005030-30101033532-601220a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30b[2]a[x]b[y]?y=列坐标小于col(a[x])的元素个数+

列坐标等于col(a[x])且在a[x]之前的元素个数.005030-30101033532-601220a[0]050a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30基本思想：

数组num存储a中每列非零元素个数；数组pos存储a中每列第一个非零元素在b的三元组表中的位置；

302101230123num0335pos.a[0]00502120011033523-6003-30基51算法:TRANSPOSE(A.B)TP1[初始化]

n←Rows(B)←Cols(A).//B的行数等于A的列数，B的列数等于A的行数

Cols(B)←Rows(A).

t←Count(B)←Count(A).//B中非0元素的个数等于A中非0元素的个数TP2[定义数组num]

FORi←0TOn-1DO

num[i]←0.

FORi←0TOt-1DO（

j←col(A

[i]). num[j]←num[j]+1.）//A中每列非零元素个数

pos[0]

←0//定义数组pos

FORi←1TOn-1DO(pos[i]←pos[i-1]+num[i-1]).算法:TRANSPOSE(A.B).52a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-3003102231num00132335pos005030-30101033532-601220b[0]b[1]b[2]b[3]b[4]b[5].a[0]00502120011033523-6003-30053TP3[处理三元组表]FORi←0TOt-1DO(p←col(A[i]).//列坐标k←pos[p].//该列坐标的元素在b中的位置col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).

pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-300335pos0050.TP3[处理三元组表]a[0]00502120011033554TP3[处理三元组表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-301335pos00501010.TP3[处理三元组表]a[0]00502120011033555TP3[处理三元组表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-302335pos005010101220.TP3[处理三元组表]a[0]00502120011033556TP3[处理三元组表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-302345pos005030-3010101220.TP3[处理三元组表]a[0]00502120011033557TP3[处理三元组表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-303345pos005030-30101032-601220.TP3[处理三元组表]a[0]00502120011033558TP3[处理三元组表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-303355pos005030-30101033532-601220.TP3[处理三元组表]a[0]00502120011033559TP3[处理三元组表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-303356pos005030-30101033532-601220.TP3[处理三元组表]a[0]00502120011033560f(j)abcabcacabca-1-1-10123-10123作业2-15.f(j)abcabca61abcaabbabcab…..abcaabb62第1－3章习题.第1－3章习题.63作业1－5

试用ADL语言编写一个算法，判断任一整数n是否为素数。.作业1－5试用ADL语言编写一个算法，判断任一整数n64考察知识点判断素数素数——大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。判断：对于指定的n，如果[2,n-1]内的整数都不能整除n，则n为素数。ADL语言写算法算法证明很难，可以使用边界条件和特殊数据，人工模拟算法执行过程。.考察知识点判断素数.65完成情况思想——基本正确，对素数定义的理解：1？算法——特殊情况处理：n1？算法输出；ADL语言的使用：运算符号：MOD(模)，DIV(除数)，/(除)；

，（取整）；％？sqrt?fabs()?

输入输出参数：设置返回值；中间用“.”分隔；条件语句：ifthenelse；

fori＝1tonstep1(i=i+1?)

赋值语句：.完成情况思想——基本正确，对素数定义的理解：1？.66参考答案算法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.)▌.参考答案算法S(n.flag).67正确性验证：假定n＝7，模拟执行过程，对i＝2，3，4，5，6时，分别判断(7modi)的取值是否为0。改进：n-1？——n/2、n1/2n=ab,a≥2,b≤n/2,…a,…b,…n/2a≤n1/2,b≥n1/2,…a,…n1/2,…b…

.正确性验证：.68参考答案2算法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.)▌.参考答案2算法S(n.flag).69作业1-8若A(n)=amnm+…+a1n+a0是关于n的m次多项式，证明A(n)=O(nm)。设f(n)和g(n)是正整数集到正实数集的函数，称f(n)是O(g(n))当且仅当存在正常数C和n0，使得对任意的nn0，有f(n)Cg(n)。完成情况：令n0＝1，C＝am+…+a1+a0，

amnm+…+a1n+a0Cnm

注意：当ai0时，ainiainm不一定成立。.作业1-8若A(n)=amnm+…+a1n+a0是关于n的m70证明：对于所有的n≥1，有：

A(n)=i=0,…,maini≤i=0,…,m|ai|ni≤

nmi=0,…,m|ai|ni-m

≤

nmi=0,…,m|ai|

令C＝i=0,…,m|ai|，有A(n)≤

Cnm

所以，

A(n)=O(nm)。参考答案.证明：对于所有的n≥1，有：参考答案.71作业1－11

证明对正整数n≥3，算法BS的元素比较次数T(n)≤5n/3-2。已知：0n=1T(n)=1n=2T(n/2)+T(n/2)+2n>2.作业1－11证明对正整数n≥3，算法BS的元素比较次数T(72考察知识点：数学归纳法基础归纳：n=c(初值)时，命题是正确的；归纳步骤：如果n＝k－1时，命题成立，则n＝k时，命题也成立。完成情况：利用结论T(n)＝3n/2－2，需要注意前提条件——当n是2的幂时；由n=k反推n＝k-1时的情况。.考察知识点：数学归纳法.730n=1

T(n)=1n=2

T(n/2)+T(n/2)+2n>2n=3时，T(3)=T(1)+T(2)+2=3，53/3-2=3，命题成立。假设n<=k时命题成立，需证明n=k+1时成立。

当k≥3时，有(k+1)>(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-2]＋[5((k+1)/2)/3-2]+2=5((k+1)/2+(k+1)/2)/3-2//k＋1=(k+1)/2+(k+1)/2

=5(k+1)/3-2综上，命题得证。.074作业1－12给出算法BS的非递归算法，并说明算法最多需要多大的辅助空间。.作业1－12给出算法BS的非递归算法，并说明算法最多需要多大75算法SM(A,n.max,min)

SM1[初始化]max←min←A[1].

SM2[比较]

FORI=2TOnDO

//求最大和最小元素

(IFA[I]>maxTHENmax←A[I].IFA[I]<minTHENmin←A[I]).

▌.算法SM(A,n.max,min).76BS算法算法BS（A，i，j.fmax，fmin）//在数组A的第i个元素到第j个元素之间寻找最大和最//小元素，已知ij。BS1[递归出口]IFi=jTHEN（fmax←fmin←A[i].RETURN.）IFi=j1THEN

（IFA[i]<A[j]THEN（fmax←A[j].fmin←A[i]）. ELSE（fmax←A[i].fmin←A[j]）.RETURN）..BS算法算法BS（A，i，j.fmax，fmin）77BS2[取中值] mid←(i+j)/2BS3[递归调用]BS（A，i，mid.gmax，gmin）

BS（A，mid+1，j.hmax，hmin）.BS4[合并] fmax←max{gmax，hmax}. fmin←min{gmin，hmin}.■

.BS2[取中值].78完成情况做的很少SM方法；（没有体现分治思想）依次对比邻近的两个元素，找到较大较小者，不断更新全局最大最小值；依次对比，用数组存放每对的最大最小值；两个栈分别存放当前起始和终止元素下标；一个栈存储中间值，另一个存放最大最小值。（没法确定起始和终止元素的下标）.完成情况做的很少.79辅助空间：因为采用某种特殊结构，而增加占用的空间；占用空间：算法运行所需要的空间；方法3：数组；方法4：栈.辅助空间：因为采用某种特殊结构，而增加占用的空间；.80方法4基本思想：创建两个栈，一个存放起始元素的下标，一个存放终止元素的下标。每次从栈中弹出一对下标，若两者相等或相差为1，则找到最大最小值，否则找到中间下标，形成两对新的下标，压入栈内。.方法4基本思想：.81示例数组A=[3,9,21,15,8,19]16初始：压入起始和结束下标1和6；循环：弹出元素1和6；两者不相等、相差不为1；取中值(1+6)/2=3；形成两对新的下标，(1,3)和(4,6);压入栈；弹出4和6，两者不相等、相差不为1；取中值(4+6)/2=5；形成两对新的下标，(4,5)和(6,6);压入栈内；1346134566.示例数组A=[3,9,21,15,8,19]16初始：压入起82A=[3,9,21,15,8,19]134566弹出(6,6)，相等，元素值为19，则fmaxmax{fmax,19}=19，fminmin{fmin,19}=19；弹出(4,5)，相差为1，元素值为15和8，则fmaxmax{19,15,8}=19，fminmin{19,15,8}=8；13.A=[3,9,21,15,8,19]134566弹出(6,683参考答案算法f(A,i,j.fmax,fmin)f1.[初始化]fmaxfminA[i].Lstack<int>left;Lstack<int>right;//存储起始和终止下标left.push(i).right.push(j).f2.[求最大、最小值]While(!left.IsEmpty())DO(lleft.pop().rright.pop().

.参考答案算法f(A,i,j.fmax,fmin).84IFl=rTHEN//相等(fmaxmax{fmax,A[l]}.fminmin{fmin,A[l]}.)ELSE(IFr-l=1//相差为1THEN(fmaxmax{fmax,A[l],A[r]}.fminmin{fmin,A[l],A[r]}.)ELSE(mid=(i+j)/2.left.push(l).left.push(mid+1).right.push(mid).Right.push(r).))).IFl=rTHEN//85辅助空间：栈nn/2n/2n/4n/4…1log2n.辅助空间：栈nn/2n/2n/4n/4…1log2n.86作业2－1编写算法Reverse(A[],n)，将顺序存储的线性表A=(a1,a2,…,an)转换为A=(an,…,a2,a1)，要求转换过程中使用尽可能少的辅助空间。关键点：限制辅助空间的使用如果没有这个限制，则可以有多种方法：辅助数组；双下标同时向中间移动.作业2－1编写算法Reverse(A[],n)，将顺87分析只需从线性表的第一个数据元素开始，将第i个数据元素与第n-i+1个数据元素相交换即可。i的变化范围是1到n/2。a1a2…an-1ananan-1…a2a11+n2+(n-1)…(n-1)+2n+1.分析只需从线性表的第一个数据元素开始，将第i个数据元素与第n88参考答案算法Reverse（A，n.A）Reverse1.[元素互换]FORi=1TOn/2DOA[i]←→A[n-i+1].▌.参考答案算法Reverse（A，n.A）.89作业2-8在单链表类SLIST中添加一个成员函数，将单链表中元素的次序完全颠倒。.作业2-8在单链表类SLIST中添加一个成员函数，将单链表中90利用堆栈；从表头删除，插入表尾；(不推荐)换数据域的取值，p1和p2向中间移动，更换数据域的取值。…headp1p2.利用堆栈；…headp1p2.91方法4思想：从左向右，依次更换邻近结点的指针方向。初始设置，第一个元素需要被放到表尾，指向空指针，p1=null，p2=next(head)//第一个元素headp22p3345p1nullp11p26P3next(p2)next(P2)P1. //反转P1P2.P2P3..方法4思想：从左向右，依次更换邻近结点的指针方向。headp92参考答案算法Reverse(head.head)/*将指针head所指向的链表倒置*/RV1[空链表和1个节点链表]IF(next(head)=NULL)RETURN.RV2[指针初始化] //P1,P2分别指向两个连续的节点

P1NULL. P2next(head)..参考答案算法Reverse(head.head).93RV3[反转链表] WHILE(P2≠NULL)DO (P3next(p2) next(P2)P1. //反转节点指针

P1P2.P2P3.//移动3个指针 ）RV4[head指向反转链表]

next(head)P1.

▌p1p2.RV3[反转链表]p1p2.94作业2－11已知线性表中的元素以data值递增有序排列，并以单链表做存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素，同时释放被删结点空间，并分析算法的时间复杂度。链表是有序的：找到区间特殊情况的处理：表为空，元素都大于maxk(第一个元素大于maxk)；元素都小于mink(最后一个元素小于mink)。.作业2－11已知线性表中的元素以data值递增有序排列，并以95主要思想：找到大于mink的第一个元素，删除操作，直至元素大于maxk。时间复杂度：比较为基本运算最好：空，元素都大于maxk（找不到）//O(1)最坏：元素都小于mink（找不到），

元素都小于maxk，O(n)；.主要思想：.96算法LD(L,mink,maxk)LD1.[特殊情况]IF

minkmaxkTHEN(RETURN.)LD2.[初始化]p←head.prev←p.p←next(p)LD3.[找]WHILE(pNULLANDdata(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.算法LD(L,mink,maxk)LD1.[特殊情况97作业2－17对于顺序堆栈和链式堆栈s，分别编写函数SelectItem(Stack&s,intn)，要求在堆栈中查找元素n在栈中第一次出现的位置，并将该位置元素移至栈顶，同时其他元素次序不变。（注意：用int匹配堆栈的模板）.作业2－17对于顺序堆栈和链式堆栈s，分别编写函数Selec98基本思想：取栈顶元素，若不匹配，则进行弹栈操作；找到（或无法找到）后恢复原来的元素次序。关键点：记录弹出的顺序，后弹出的元素能够先被压回原来的栈，因此需要使用一个辅助堆栈。.基本思想：.99示例105112shelpStack5173n=515112105173751511210377351.示例105112shelpStack5173n=515112100参考答案intSelectItem(Stack<int>&s,intn){AStack<int>temp(100);//顺序堆栈，辅助栈

//LStack<int>temp;//链式堆栈

boolflag=false;//是否存在元素nintloc=0;//记录n所在的位置

while(!s.isEmpty()&&s.Peek()!=n

){temp.Push(s.Pop());loc++;}栈非空且当前元素不等于n.参考答案intSelectItem(Stack<int>101if(!s.isEmpty()){s.Pop();flag=true;}//弹出nwhile(!temp.isEmpty())//将辅助栈中元素压入原栈

{s.Push(temp.Pop());}if(flag)thens.Push(n)；

elseloc=-1;returnloc;}因为找到元素而跳出循环.if(!s.isEmpty())因为找到元素102作业2－25编写并实现双端队列类，双端队列是可进行如下操作的线性表。(1)push(item)－－item插入到队列的前端；(2)pop(item)－－删除前端元素且赋给item；(3)inject(item)－－item插入尾端；(4)eject(item)－－删除尾端元素且赋给item.作业2－25编写并实现双端队列类，双端队列是可进行如下操作的103结点结构SLNode：数据域和指针域；类成员：队首和队尾的SLNode类型指针、指示元素个数的整型变量；Push(item插入队列前端)

若空，则加入一个以item为数据域的结点，元素个数为1；否则，temp记录原队首指针front；

创建以item为数据域的新结点，作为新的队首，赋值给front；front的指针域指向temp，元素个数加1。.结点结构SLNode：数据域和指针域；.104Pop(删除前端元素，并赋值item)若空，则错误；否则，temp记录原队首指针front；

队首后移，即frontnext(front)；

返回temp的数据域；

删除temp结点，元素个数减1；

若大小为零，则队尾指针rear赋值为NULL。.Pop(删除前端元素，并赋值item).105Inject(item插入队尾)若空，则加入一个以item为数据域的结点，元素个数为1；否则，创建以item为数据域的新结点temp，作为新的队尾，即next(rear)temp；队尾指针后移，即rearnext(rear);元素个数加1。.Inject(item插入队尾).106Eject(删除队尾元素并赋值给item)若空，则出错；否则，

找到队尾指针的前驱指针tempfront.IF(temprear)THEN(WHILE(next(temp)rear)DO(tempnext(temp))队尾指针更新，即reartemp，

要删除结点是next(temp)，返回数据域，删除结点，元素个数减1。

若大小为零，front和rear赋值为NULL。.Eject(删除队尾元素并赋值给item).107作业3－10设稀疏矩阵Mmn中有t个非零元素，用三元组表的方式存储.请设计一个算法，计算矩阵M的转置矩阵N，且算法的时间复杂性为O(n+t).注意，书中给出的算法的复杂性为O(nt)。.作业3－10设稀疏矩阵Mmn中有t个非零元素，用三元组表的108M=500001002000000-300-605N=50100-3000000200-6000050050a[0]1010a[1]1220a[2]30-30a[3]32-60a[4]335a[5]0050b[0]0110b[1]03-30b[2]2120b[3]23-60b[4]335b[5]算法的关键是求出a中元素在b中的位置.M=50000N=5010109Bindex＝0；FORj=0TOn－1DO

FORk=0TOt－1DOIFcol(A[k])=jThen (row(B[Bindex])=j. col(B[Bindex])=row(A[k]). value(B[Bindex])=Value(A[k]).

Bindex++）a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30j=0,k=0,a[0],列坐标=0；存储j=0;k=1;a[1],列坐标=0；存储j=0;k=2;a[2],列坐标=2；j=0;k=3;a[3],列坐标=0；存储j=0;k=4;j=0;k=5;j=1;k=0005030-301010.Bindex＝0；a[0]00502120011033523110a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30005030-301010j=1,k=0,a[0],列坐标=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=jFORj=0TOn－1DO

FORk=0TOt－1DOIFcol(A[k])=jThen2201.a[0]00502120011033523-6003-300111005030-30101033532-601220a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30b[2]a[x]b[y]?y=列坐标小于col(a[x])的元素个数+

列坐标等于col(a[x])且在a[x]之前的元素个数.005030-30101033532-601220a[0]0112a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30基本思想：

数组num存储a中每列非零元素个数；数组pos存储a中每列第一个非零元素在b的三元组表中的位置；

302101230123num0335pos.a[0]00502120011033523-6003-30基113算法:TRANSPOSE(A.B)TP