《华师大数据结构期中考试试卷含答案.doc》由会员分享，可在线阅读，更多相关《华师大数据结构期中考试试卷含答案.doc（14页珍藏版）》请在三一文库上搜索。
1、华师大数据结构期中考试试卷含答案华东师范大学期中试卷200008学年第二学期课程名称：_数据结构_ 姓 名：_ 学 号：_专 业：_ 年级/班级:_课程性质：专业必修一二三四五六七八总分阅卷人签名一、 单项选择题(共18分,每题分)1. achas theprtcalled las in and fis out, then whic f the flowing dscishe propert of Queue?a)Last in ad fst otb) First iand ls outc) Fist in nd firs ou2.A list of items fm whiconlth it
2、em motrecentlyaded ca be removedis now asa ( ）a) tack b) ueue c) circular linke list d)st3.Iftefolowing fuction i calldwih avae of 2 or n, wa sthe rsltin outut? vod Qi( int） if ( ) ot 0; Qu(n- 1)； cout 1; Quz(n 1）； )0011011b）110100 )1110d)11001e)0004. heap i a tinhch eac entry containsa ey, and, for
3、 all potions iithe ist,he y at stion is tlease as lge as thekes in poton2i+2 and （ )， rovided se itins eist n theist.a） b) 2-1c) 2i-2d） 2i+15 Gventh recursi funtio it Func( * i */ ini， /* n */ i ) f （ ) if（j 0) Func（n/ ）； cot n 8; 2.iv th upt o te follwing progr. _【2】_templaevoi print(List_enr &x)cu
4、x ;void main()List mli；for(nt i=0;i5；i）mylst.insrt(i,i);cotYourlsaemylistse() elets：endl;myls.rmov(，i)；mylistemove(,i);mylit.insert(i,i);mylis.tavere（prit)；mylist.ca( );fr(i=;i3;i+)yist.isert（, i)；myisttraerse(rint);3. ad the folling rogm nd fill he lank to complete te methdtepate struct Nod / data
5、mmsNoe_entry entry;NodNodeetry*nxt;NodeNod_enry bck；/constucorNod（ ）;Noe（Nodentr item, ode *link_bc = UL, NodNode_enty*lnk_ext = L);emla void Ls：: set_poition(inoition） cons/* Pre: osition is avald position ithe is : 0 oition n .Post: Te urrede poinr rferences theNode at ostion .*if (crrent_pitio k；
6、4. Read thefooing progrman il theblank to cmlete th t.Errr_ode ecrsivebiry_(constOrred_ist &te_lit,cons Key&aret, t bottom, int to, int poiion)/* Pe: The inicsbottmt tp fin te rang in theli to earch fr the trget.Post: Ia Record i th range fom botomo tp inhe l hs ey equa ttarget, thn positn locaese s
7、uch enry, nd a code o suces is returned. Ohwise, not_peset s eturned, an piton iundefinedses: ecursibinary_2， togethr ith mths from te clasesOrdre_litad Recor. *Record daa;if (otm op） nt mid 【5】 ;tist.rieve (mid， daa);i （data =targe) 【】 ；turn sc；ele if ( arg)retrecusiv_biary_（th_ist, trget, 【7】 , to
8、p, potion);lsreturnreuriv_inary_2(thelis， taret, bom， 【8】 ,osition)；ee retur not_prsn;5.The followin pgram hedivide_omuctionofMerge Sortleasefillth lak to comlete the unction Node*de_frm (Nod *ublist) Pt: h listo nodes refereced by sb_list as been reded titsfirst hal,anda poinr to thfist nde inth se
9、codalf fthesublist sretured. f elis hs n od numrof entris, thn its frst half wll be one nr lager tan it send.*Node *ositon, traversesthe entre ist*mipont,/ ms a haf eed of postin to mdint*co_half；if （(mipon = ub_lis) = NULL） reurnNULL;/ st i emt.positi= dpoit-nxt;whie (【】 ) ove ption te r mioits onm
10、ov.ositin =psiti-nxt;f (poiion！ NUL）【10】 ；osi= posiio-ext; second_hf= 【1】 ;mipnt-next NULL；retrnseodhaf；三、 编程题(共6分)1. (1分）Aply quiksor tohe folowing list of 4 es, whre the pit in ch ublit ischosen to be () thefrt key i he sublit an （b） th as ey in e ublist. nch as，draw the tre ofrecuriv ca.Ti Dot Ev
11、a RyTom Ki Guy Amy Jon Ann Jim Kay RonJan2. （16分)Wrie he folowing ovrloadorator f stacks:1) boolSack：opertor = (cns Stack s)；2) ooStack:oprator = (onst Sack & s)；/puses the cotensof he ive stack n hs sak;3. (10分)Write te ollwigfunctio mple：Temlae clsTvoid revrse(Quee & q)；/ everses the conensof the
12、en quee;4. (8分)strut Node/ datmmersint enry;Node nxt;/ conrucNde( ）;Node(int item， de lin = ULL）;fs th ea pintr f alink list o ndsUsing rcurion, impleent tefowing fucios:1) int Max (Nod ); retun mx value n helink lis2) nt u (ode*f );/reur e nuber o hnode n the l lst3) Nde*Seach( Noe *f, intx); /Serh
13、 the fist ccrrece othx in thelink lst I ucess returns the /pointero te ode, e ets ULL.数据结构期中考卷参考答案一、 单项选择题(68)1 2 a3 4 d5 a6 b二、 填空题(21=)【1】13【】Your lis hae 5 lemns： 2 3【3】curren = currnt-next【4】urrent_pstin-【5】(bottm top)/2【6】pstion =mid【】md + 1【8】mi 1【】poiion != ULL【1】mipin =ipoitnext;【11】ipoint-n
14、ext三、 编程题(6210+18=6），a) P34 F81b)2.1)bool Stack:oeratr=（cos Stak &s)tak s1=s, s2=*ts;while (!.empty( ）i(s1.op（)!= stp( )rturnflse;es s1.pop( ); s.pop( )；2) bolSac:petor+=(cont Stc &s)Stk ss=s, s2；while (!ss.mpty( ）)s2.pus(s.top( ）;sspop（ ）;wie （！s2ept( )if(puh(s2.top() = utcome） rturnfas;s.p( );.Tat
15、e videvese (QuT & q）Stack s; aa;hile (!q.py( ） .etrive(a );s.uh( data)； qeve（ );whil(!.empt(）q.aen（s.top（);s.po( );.int Max (Nde *f ) if (f-xt = ULL ) retrn f enry;inttem ( f -e );if （f -data temp ) etunf entr;els rtun tep;tNum ( ode *f ) i (f ULL ) return 0;turn +Nu ( f-xt ）;Node Srch(Noe *f，int x ) i ( f =NUL）return NLL；else （f entr =x ) rtun f; elsereturn Searh( fnex , x）;