数据结构习题讲解

习题讲解3&3.1MF1232104赵垠兰

习题31Swaptwoadjacentelementsbyadjustingonlythelinks(andnotthedata)using:SinglylinkedlistsDoublylinkedlistsExercise1Singlylinkedlistabcd①a.next=b.next③a.next.next=bb.next=a.next.next②Exercise1Doublylinkedlistab①②④⑥⑤③1.a.left.right=b；2.a.right=b.right；3.b.right.left=a；4.b.right=a;5.b.left=a.left;6.a.left=b;2GiventwosortedlistsL1andL2,writeaproceduretocomputeL1∩L2,usingonlythebasiclistoperations

publicLinkedListintersection(LinkedListL1,LinkedListL2){

LinkedListItritr1=L1.first(); LinkedListItritr2=L2.first(); LinkedListL=newLinkedList(); LinkedListItritr=L.zeroth();

while(!itr1.isPastEnd()&&!itr2.isPastEnd()){ if(itr1.retrive()==itr2.retrive()){ L.insert(itr1.current,itr); itr1.advance(); itr2.advance(); }elseif(itr1.retrive()<itr2.retrive()) itr1.advance(); else itr2.advance(); } } returnL;}3Giventwosorted

lists,L1andL2,writeaproceduretocomputeL1∪L2,usingonlythebasiclistoperations

publicLinkedListunion(LinkedListL1,LinkedListL2){ LinkedListItritr1=L1.first(); LinkedListItritr2=L2.first(); LinkedListL=newLinkedList(); LinkedListItritr=L.zeroth(); while(!itr1.isPastEnd()&&!itr2.isPastEnd()){ if(itr1.retrive()==itr2.retrive()){ L.insert(itr1.current,itr); itr1.advance(); itr2.advance(); }elseif(itr1.retrive()<itr2.retrive()){ L.insert(itr1.current,itr); itr1.advance();}else{ L.insert(itr2.current,itr); itr2.advance(); } }//如果L1没有结束，将L1剩余元素添加到L中

for(;!itr1.isPastEnd();itr1.advance()){ L.insert(itr1.current,itr); }

//如果L2没有结束，将L2剩余元素添加到L中

for(;!itr2.isPastEnd();itr2.advance()) { L.insert(itr2.current,itr); } returnL;}Writeanonrecursivemethodtoreverseasinglylinked,ListinO(N)time

public

LinkedListreverseList(ListNodefirst){

ListNodepa,pc,tmp;

pa=pc=first;//pc永远指向第一个结点

while

(pa!=

null

&&pa.next

!=

null){

tmp=pa.

next;

pa.

next

=tmp.

next;

tmp.

next

=pc;

pc=tmp;

}

return

new

LinkedList(pc);

}习题3.113分）设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P（0﹤P﹤n）个位置，即将R中的数据由（X0X1……Xn-1）变换为（XpXp+1……Xn-1

X0

X1…Xp-1)（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度1）算法分析，把问题看做是数组ab转化成数组ba（a代表前p个元素b代表后n-p个元素）,假设a的逆置是Ta,b的逆置是Tb,而(TaTb)的逆为ba,故算法设计过程如下：reverse(0,p-1)reverse(p,n-1)reverse(0,n-1)3）空间复杂度为O(1),时间复杂度为（2n）voidreverse(int[]r,intlow,inthigh){inttemp;for(inti=0;i<(high-low)/2;i++){temp=r[low+i];r[low+i]=r[high-i];r[high-i]=temp;}}voidconverse(int[]r,intn,intp){reverse(r,0,p-1);reverse(r,p,n-1);reverse(r,0,n-1);}1.2009年考研统考题:

1)为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据.该缓冲区的逻辑结构应该是

A.栈B.队列C.树D.图

2)设栈S和队列Q的初始状态为空,元素a,b,c,d,e,f,g依次进入栈S.若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是A.

1

B.

2

C.

3

D.

4

入栈顺序：a,b,c,d,e,f,g出栈顺序：b,d,c,f,e,a,gabbcddceffeagg栈的最小容量2.Supposethatasinglylistisimplementedwithbothaheaderandtailnode.Describecontant-timealgorithmstoa.Insertitemxbeforepositionp(givenbyaniterator).b.Removetheitemstoredatpositionp(givenbyaniterator)

InsertpheadtailXYZheadtailXYZpYheadtailXXZpY1.在p后插入新节点2.交换p节点和新节点中元素的值publicvoidinsert(LinkedListItritr,Objectx){ ListNodep=itr.current; if(p!=head){ /*在p后插入一新节点*/ListNodeaddnode=newListNode(p.element,p.next);p.next=addnode;p.element=x;/*p指向节点的元素值用x替换*/} }RemoveheadtailXYZpheadtailXYpheadtailXYptail指向p所在的位置。tail.next＝nullPublicvoidremove(LinkedListItritr){ListNodep=itr.current;if(p!=head&&p!=tail){

/*如果p是最后一个节点*/if(p.next==tail){ tail=p; tail.next=null;}else{ p.element=p.next.element; p.next=p.next.next;}}}3.假设以数组Q[m]存放循环队列中的元素，同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数：

1）求队列中第一个元素的实际位置。

2）给出该循环队列的队空条件和队满条件，并写出相应的插入(enqueue)和删除(dlqueue)元素的操作算法。……^^rearfrontfront=rear-length+1情况1：……^^frontrearfront=rear+m-length+1情况2：(rear-length+1+m)%m合并：边界情况：length==0front=-1rear=-1队空情况length==0publicbooleanisEmpty(){/*是否空*/ returnlength==0;}队满情况length==mpublicbooleanisFull(){/*是否满*/ returnlength==m;}publicvoidenqueue(Objectx)throwsOverflow{ if(isFull