(完整word版)哈工大深圳算法设计与分析试卷-师兄只能帮你到这啦(额外再加8道保命题)-何震宇

UsingfiguretoillustratetheoperationofRADIX-SORTonthefollowinglistofEnglishwords:COW,DOG,SEA,RUG,ROW,MOB,BOX,TAB.

Pleasewriteinorder,preorderandpostordertreewalksofthefollowingbinarysearchtree.

Pleasewritedowntheelementsofdynamicprogramming.

UsingarecursiontreetogiveanasymptoticallytightsolutiontotherecurrenceT(n)=T(n/3)+T(2n/3)+cn.

PleasegiveanoptimalHuffmancodeforthefollowingsetoffrequencies.

abcdef

Frequency5916121345

Convertingthefollowinglinearprogramintostandardform:

Minimize

Subjectto

SolvethefollowinglinearprogramusingSIMPLEX:

maximize

Subjectto

SupposeA1amatrix,A2amatrix,A3amatrix,A4amatrix,A5amatrix,A6amatrix.Pleasegiveanoptimalparenthesizationofamatrix-chainA1A2A3A4A5A6.

UsingarecursiontreetogiveanasymptoticallytightsolutiontotherecurrenceT(n)=T(n/4)+T(n/2)+n2.

UsingfiguretoillustratetheoperationofCOUNTING-SORTonthearrayA=<6,0,2,0,1,3,4,6,1,3,2>

UsingfiguretoillustratetheoperationofRADIX-SORTonthefollowinglistofEnglishwords:COW,DOG,SEA,RUG,ROW,MOB,BOX,TAB.

Pleasewriteinorder,preorderandpostordertreewalksofthefollowingbinarysearchtree.

X=<A,E,B,D,B,C,A,E>,Y=<E,F,B,A,C,A,F,E>.PleaseillustratethewholeprocedureforfindingthelongestcommonsequenceofXandYusingdynamicprogramming.

PleasegiveanoptimalHuffmancodeforthefollowingsetoffrequencies.

PleasedrawtheresultaftertheoperationLeft-Rotate(9)

.

X=<A,E,B,D,B,C,A,E>,Y=<E,F,B,A,C,A,F,E>.PleaseillustratethewholeprocedureforfindingthelongestcommonsequenceofXandYusingdynamicprogramming.

PleasegiveanoptimalHuffmancodeforthefollowingsetoffrequencies.

abcdef

Frequenc/p>

Ared-blacktree(RBtree)isabinarysearchtreewithoneextrabitofstoragepernode:itscolor,whichcanbeeitherREDorBLACK,andthered-blackisanearlybalancedtree.Pleaseproven-nodeRBtreehasheight

SolvethefollowinglinearprogramusingSIMPLEX:

maximize

Subjectto

Intheactivity-selectionproblem,representstheactivitiesthatstartafteranactivityfinishesandfinishbeforeoneactivitystarts.Here,anactivityoccursduringperiod,andactivitiesaresortedbymonotonicallyincreasingfinishtime.Let,andletbe