浙江大学2010–2011学年冬季学期《高级数据结构与算法分析》课程期末考试试卷

浙江大学2010–2011学年冬季学期《高级数据结构与算法分析》课程期末考试试卷课程号：__________，开课学院：软件学院、计算机学院、竺可桢学院考试试卷：√A卷、B卷（请在选定项上打√）考试形式：√闭、开卷（请在选定项上打√），允许带___无____入场考试日期：2011年1月18日,考试时间：120分钟诚信考试，沉着应考，杜绝违纪。考生姓名：学号：所属院系：_题序一二三四总分得分评卷人AnswerSheetPartI1．c2．b3．a4．c5．c6．d7．c8．a9．b10．cPartII1.H1->Element>H2->ElementH1->Left=H2H1->Npl=H1->Right->Npl+12.H->TheTrees[i]H->TheTrees[i]=CarryPartIIIhight=42.(1)(2)2.15(3)Nodifference.3,1,24,54:-3,1,24,54:-6,78,98:-6:-3,6,9(1)(3)3,6,9(2)3,23,21,54:-6,78,98:-6:-3,1,23,1,26,76:89,84.(1)readinstringsandparsetogetwords;Usestemmingandstopwordsfiltertoobtainterms;checkdictionarywitheachterm,ifit’snotin,insertitintodictionary;getpostinglistofthetermandinsertdocumentandpositions.(2)500*10MB=5GB;1,000,000,000*10KB=10TB.(3)Anymethodthatinvolvesdistributedcomputingisfine.5.(1)(2)a:011;b:0101;c:000;d:111;e:10;f:110;g:001;h:0100(3)e

g

a

f

a

d

ePartIVForeveryi{1,…,N}andb{1,…,B},letexits(i,b)isTrueifthereexistsasubsequenceofa1…aisumminguptoexactlyb,otherwiseisFalse.QUOTETrue,thereexistsasubsequenceofa1..aClearlyexists(1,b)=Trueifb=0orb=a1,andexists(1,b)=Falseforallotherb’s.Alsoexists(i+1,b)=exists(i,b)ORexists(i,b-ai+1)Wecancomputeallvaluesexits(i,b)inO(NB).Theanswertotheoriginalquestionisgivenbyexists(N,B).InPseudocode:X=<a1,a2,…an>Y=<1,2,3…B>EXIST[N+1,B+1]MAIN(X,Y): EXIST[0,0]=trueforjfrom1toB: doEXIST[0,j]=falseEXIST[1,j]=false EXIST[1,a1]=true forifrom2toN: forjfrom1toB: if(j-ai>0): EXIST[i,j]=EXIST[i-1,j]OREXIST[i,j-ai] Else EXIST[i,j]=EXIST[i-1,j] PrintEXIST(N,B)

NOTE:Pleasewriteyouranswersontheanswersheet.注意：请将答案填写在答题纸上。Pleasefillintheblanks(theanswerforeachblankisunique).(2pointseach)1.GivenAastherootofasubtreein

an

AVL-tree.Supposethatbeforeinsertion,thebalancefactors

of

leftchildandrightchildofAare-1

and0respectively.If

inserting

a

new

node

X

tothatsubtree

willmakethetreeunbalanced,whatkindofrotationshouldbetakento

keep

the

subtreebalanced?

a.

RR

rotation

b.

LL

rotation

c.

LR

rotation

d.

RL

rotation2.Given

a

12-node

splay

tree

with

keys

1,2,...,11,and12.What

willthesplaytree

look

like

after

Find(1),Find(2),…Find(11),andFind(12)?a.

a

complete

tree

of

12nodes

b.

a

tree

with

height

11c.

a

tree

with

height

6

d.

depends

on

the

initial

tree

structure3.WhichoneofthefollowingisNOTtrueaboutB+treesandAVLtrees:theyareboth--a.balancedbinarytrees b.fitforsequentialsearchesc.fitforrandomsearches d.fitforrangesearches4.For

a

skew

heap,

whichstatement

is

NOT

correct?

a.

Skew

heap

mayormaynotbea

leftist

heap

b.

The

right

path

of

a

skew

heap

can

be

arbitrarily

long

c.

Comparing

toleftistheaps,skew

heapsarealwaysmoreefficientinrunningtimeforeverymerge

d.

Comparing

to

leftist

heaps,skew

heaps

are

always

moreefficientinspace5.Todelete

the

minimum

key

from

a

binomial

queue

H,thereare4stepstogo:Step

1:

FindMin

in

Bk;

Step

2:

Remove

Bk

from

H

and

get

H’;

Step

3:

Remove

root

from

Bk

and

get

H”;

Step

4:

Merge

(H’,

H”).

Whichstep(s)willhavetotakeO(logN)time?a.only1 b.1and2 c.3and4 d.only46.Given3

itemsand

a

knapsack

with

capacity25.The

items

have

weights

20,15and10,and

profits23,18

and11,

respectively.The

percentagesoftheitemsthatshould

be

packed

to

obtain

maximum

profit

is

_______

a.

0,

100%,

100%

b.

100%,

33.33%,0

c.

100%,0,50%

d.

50%,

100%,

07.WhichoneofthefollowingstructureshasthepropertythatanyMconsecutiveinsertionsstartingfromemptyonetakeatmostO(MlogN)timeandasingleinsertiontakesatmostO(logN)time?a.Splaytree b.Skewheap c.Leftistheap d.BinomialQueue8.TosolveaproblemwithinputsizeNbydivideandconqueralgorithm,amongthefollowingmethods,istheworst.a.divideinto3sub-problemsofequalcomplexityN/2andconquerinO(N)b.divideinto3sub-problemsofequalcomplexityN/3andconquerinO(NlogN)c.divideinto2sub-problemsofequalcomplexityN/3andconquerinO(N)d.divideinto2sub-problemsofequalcomplexityN/3andconquerinO(NlogN)9.Theproblemof“Nqueens”istoplaceNqueensonanNNchessboardsuchthatnotwoqueensattack.If

the

problem

is

to

be

solved

by

backtrackingmethod,weneedtocheck_____edgesof

the

game

treewithN=3toseethatthereisnosolution.a.9 b.11 c.13 d.1510.WhichofthefollowingstatementsisNOTcorrect?a.UndirectedHamiltonCircuitandsatisfiabilityproblemareNP-complete.b.AlthoughanondeterministicTuringMachinecanalwayschoosethecorrectsteptosolveproblems,wecannotuseittosolveundecidableproblems.c.TheproblemofdeterminingwhetheragraphdoesnothaveaHamiltoniancycleisinNP-class.d.IfwecansolveanyNP-completeprobleminpolynomialtime,thenwewillbeabletosolve,inpolynomialtime,alltheproblemsinNP.Giventhefunctiondescriptionsofthefollowingtwo(pseudo-code)programs,pleasefillintheblanklines.(15points)1.ThefunctionistomergetwoleftistheapsH1andH2.(9points)PriorityQueueMerge(PriorityQueueH1,PriorityQueueH2){if(H1==NULL)returnH2;if(H2==NULL)returnH1;if() swap(H1,H2);//swapH1andH2 if(H1->Left==NULL) ②; else{ H1->Right=Merge(H1->Right,H2); if(H1->Left->Npl<H1->Right->Npl) SwapChildren(H1);//swaptheleftchildandrightchildofH1 =3\*GB3③; } returnH1;}2.ThefunctionistoinsertXintoabinomialqueueH.(6points)BinQueueInsert(ElementTypeX,BinQueueH){ BinTreeCarry; inti; H->CurrentSize++; Carry=malloc(sizeof(structBinNode)); Carry->Element=X; Carry->LeftChild=Carry->NextSibling=NULL; i=0; while(H->TheTrees[i]){ Carry=CombineTrees(Carry,①);//combinetwoequal-sizedtrees H->TheTrees[i++]=NULL; } ②; returnH;}Pleasewriteordrawyouranswersforthefollowingproblemsontheanswersheet.(50points)What

is

the

height

of

thehighest

AVL-tree

of

12nodes?(3points)Pleasedrawthe

highestAVL-treewithkeys

1,2,…,12,and

atthemeantime,keep

the

tree

as

aleftist-treeaswell.(5points)2.Given

the

keywords

and

searching

frequencies,

in

order

to

minimize

theexpectedtotal

accesstime,thereis

a

greedy

way

to

construct

the

binarysearch

tree:firstarrangeallthe

keywords

in

descendentorderoffrequencies;andtheninsert

thekeywordsin

thatorder

to

aninitially

emptyAVL-tree.

Giventhefollowingkeywordsandtheirfrequencies:keywordsbreakcasechardoreturnswitchvoidfrequencies22182052528Please:

(1)

show

the

AVL-tree

obtainedbytheabovegreedymethod;

and(5points)(2)give

the

totalsearch

cost

of

the

constructed

search

tree.(4points)3,1,24,54:66,9,8(3)ComparethisAVL-treewiththeoptimalbinarysearchtreeandtellthedifference.(3,1,24,54:66,9,83.Givena2-3treeasshowninthefigure.Please:(1)showtheresultofinserting7withsplittingstrategy;(2points)(2)showtheresultofdeleting4andthen5fromthetreeobtainedin(1);(2points)and(3)showtheresultofdeleting1,2,8andthen7fromthetreeobtainedin(2).(2points)4.(1)Pleasebrieflydescribetheprocessofbuildinganinvertedfileindex.(4points)(2)Given1billionfilesof10KBeach,andwith500milliondistinctterms.Supposethatthepostinglistofeachtermisalinkedlistwiththestructure:DocID(4bytes)TermPosition(2bytes)NextPointer(4bytes)Howmanybytesarerequiredtostoretheindex?Howaboutthefiles?(2points)(3)Ifyouonlyhavesomepersonalcomputerswith1GBmemoryand10GBharddisks,howwouldyouhandlethisindexingproblem?(4po