资源描述：
《工业工程与工程管理系_2001110111212654.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、國立清華大學工業工程與工程管理系IE5109計算方法設計與分析期中考試(April16,2003)姓名:學號:1.(10%)2.(15%)3.(10%)4.(15%)5.(15%)6.(15%)7.(10%)8.(10%)Total:10%1.Indicate,foreachpairofexpression(F(n),H(n))inthetablebelow,whetherF(n)isO,W,qofH(n)(forexample,F(n)=q(H(n)).(1-a)(1-b)(1-c)(1-d)F(n)(logn)10n1
2、00enlog(n!)22H(n)n0.1100n4nlognn215%2.(2-1)Whatisamaxheap(giveanexample)andwhatareitsadvantagesanditsapplications?(2-2)Forthefollowingsequence{30,65,35,15,75,23,45,50,70,25},buildamaxheap.(2-3)Useasuitabledatastructuretostorethemaxheapof{30,65,35,15,75,23,45,50,70
3、,25}.Isthereanyotherdatastructurewhichissuitableformaxheap?(2-4)Explainthereheapprocedureif28isinsertedinthismaxheap.Howthedatastructureischanged?(2-5)Explainthereheapprocedureif70isdeletedfromthismaxheap.Howthedatastructureischanged?((2-5)isindependentof(2-4).)10
4、%3.SolvetherecurrencerelationT(n)=8T(n-1)-15T(n-2)whereT(1)=0,T(2)=2.15%4.(4-1)Givethecontentsofthestackaftereachoperationinsequence.TSI*NG*HUA**U**IVE**RSI*T*Y.Herealettermeans"push"(theletter)and"*"means"pop".iterationoperationX(1)X(2)X(3)X(4)X(5)X(6)X(7)X(8)TOP
5、1234567891011121314151617181920(4-2)GivethecontentsofthequeueaftereachoperationsinthesequenceME#R#RY##CHR##IST#MA##S.Herealettermeans"put"(theletter)and"#"means"get".2iterationoperationX(1)X(2)X(3)X(4)X(5)X(6)X(7)FR12345678910111213141516171819202120%5.Findallthes
6、hortestpaths(a1toa2,a1toa3,anda1toa4)byusingthedynamicprogrammingmethod.(Youhavetousethestandardtableau.)3é0710+¥ùêú40+¥9C=êúê3908úêúë7+¥80û415%6.Sortthefollowingnumbersintoanincreasingsequenceofnumbersbyusingthequicksortmethod.(Useunderlinetoindicatethepivoteleme
7、nt.)Iteration數列LOWERUPPER021,15,50,84,32,18,28,36,72,5711012345678951010%7.Cuttingacirclewithstraightlines,howmanypieces,atmost,canbeobtainedwithncuts?(Hint:Solvetheproblemwithrecurrencerelation,notingthatthenewcutcanintersecteacholdcutinatmostonepoint.Referthefol
8、lowingcases.)T(1)=2T(2)=4T(3)=7T(4)=1110%8.Inthefollowinghashtable,supposethefollowingadditionalrecordsareaddedtothetable:(P,1),(Q,4),(R,4),(S,5)Here,th
