數(shù)據(jù)結(jié)構(gòu)習(xí)題講解

習(xí)題講解3&3.1MF1232104趙垠蘭

習(xí)題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沒有結(jié)束，將L1剩余元素添加到L中

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

//如果L2沒有結(jié)束，將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永遠(yuǎn)指向第一個結(jié)點

while

(pa!=

null

&&pa.next

!=

null){

tmp=pa.

next;

pa.

next

=tmp.

next;

tmp.

next

=pc;

pc=tmp;

}

return

new

LinkedList(pc);

}習(xí)題3.113分）設(shè)將n(n,1)個整數(shù)存放到一維數(shù)組R中，試設(shè)計一個在時間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P（0﹤P﹤n）個位置，即將R中的數(shù)據(jù)由（X0X1……Xn-1）變換為（XpXp+1……Xn-1

X0

X1…Xp-1)（1）給出算法的基本設(shè)計思想。（2）根據(jù)設(shè)計思想，采用C或C++或JAVA語言表述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度1）算法分析，把問題看做是數(shù)組ab轉(zhuǎn)化成數(shù)組ba（a代表前p個元素b代表后n-p個元素）,假設(shè)a的逆置是Ta,b的逆置是Tb,而(TaTb)的逆為ba,故算法設(shè)計過程如下：reverse(0,p-1)reverse(p,n-1)reverse(0,n-1)3）空間復(fù)雜度為O(1),時間復(fù)雜度為（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年考研統(tǒng)考題:

1)為解決計算機主機與打印機之間速度不匹配問題,通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū),主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū),而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù).該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是

A.棧B.隊列C.樹D.圖

2)設(shè)棧S和隊列Q的初始狀態(tài)為空,元素a,b,c,d,e,f,g依次進(jìn)入棧S.若每個元素出棧后立即進(jìn)入隊列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后插入新節(jié)點2.交換p節(jié)點和新節(jié)點中元素的值publicvoidinsert(LinkedListItritr,Objectx){ ListNodep=itr.current; if(p!=head){ /*在p后插入一新節(jié)點*/ListNodeaddnode=newListNode(p.element,p.next);p.next=addnode;p.element=x;/*p指向節(jié)點的元素值用x替換*/} }RemoveheadtailXYZpheadtailXYpheadtailXYptail指向p所在的位置。tail.next＝nullPublicvoidremove(LinkedListItritr){ListNodep=itr.current;if(p!=head&&p!=tail){

/*如果p是最后一個節(jié)點*/if(p.next==tail){ tail=p; tail.next=null;}else{ p.element=p.next.element; p.next=p.next.next;}}}3.假設(shè)以數(shù)組Q[m]存放循環(huán)隊列中的元素，同時以rear和length分別指示環(huán)形隊列中的隊尾位置和隊列中所含元素的個數(shù)：

1）求隊列中第一個元素的實際位置。

2）給出該循環(huán)隊列的隊空條件和隊滿條件，并寫出相應(yīng)的插入(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