浙江大學(xué)2011–2012學(xué)年冬季學(xué)期《高級(jí)數(shù)據(jù)結(jié)構(gòu)與算法分析》課程期末考試試卷

浙江大學(xué)2011–2012學(xué)年冬季學(xué)期《高級(jí)數(shù)據(jù)結(jié)構(gòu)與算法分析》課程期末考試試卷課程號(hào)：__________，開(kāi)課學(xué)院：軟件學(xué)院、計(jì)算機(jī)學(xué)院、竺可楨學(xué)院考試試卷：√A卷、B卷（請(qǐng)?jiān)谶x定項(xiàng)上打√）考試形式：√閉、開(kāi)卷（請(qǐng)?jiān)谶x定項(xiàng)上打√），允許帶___無(wú)____入場(chǎng)考試日期：2011年1月12日,考試時(shí)間：120分鐘誠(chéng)信考試，沉著應(yīng)考，杜絕違紀(jì)。考生姓名：學(xué)號(hào)：所屬院系：_題序一二三四總分得分評(píng)卷人AnswerSheetPartI(20)1．2．3．4．5．6．7．8．9(a)．9(b)．PartII(18)1.2.PartIII(47)1.2.(1)2.(2)3.(1)3.3,6,9(2)3,6,94.5.6.PartIV(15)

NOTE:Pleasewriteyouranswersontheanswersheet.注意：請(qǐng)將答案填寫(xiě)在答題紙上。Pleasefillintheblanks(theanswerforeachblankisunique).(2pointseach)1.For

an

AVL

tree,

______

is

NOT

correct.a.

A

complete

binary

search

tree

must

be

an

AVL

treeb.

If

the

height

of

an

empty

tree

is

defined

to

be

-1,an

AVL

tree

of

height3

must

contain

exactly

7

nodesc.

In

an

AVL

tree,

the

height

of

the

left

and

right

subtrees

can

differ

by

at

most

1d.

The

left

and

right

subtrees

of

an

AVL

tree

are

also

AVL

trees2.A

B+

tree

of

order

3

with

11

numbers

has

at

most___nonleaf

nodes.a.

3 b.

5 c.

7 d.

83.Amongthefollowingstatements,______

is

true.a.

Therelationshipofskewheapstoleftistheapsisanalogoustotherelation

between

splay

trees

and

B

trees.b.

Forleftistheapsandskewheaps,theworst-caserunningtimeofasingle

insertion

are

both

O(N).c.

Withthesameoperations,theresultingskewheapisalwaysmorebalancedthantheleftist

heap.d.

None

of

the

above

is

true.4.Afterinsert1,2,3,…,14,15consequentiallyintoaninitiallyemptybinomialqueue,in

which

tree

of

this

binomial

queuethatthe

number

9

will

be?a.

B1

b.

B2

c.

B3

d.

undecidable5.Whichofthefollowingalgorithmsdoesn’tuseDivideandConquer?a.Quicksort b.Mergesort c.Bucketsort d.Binarysearch6.An

amortized

time

bound

is

_____.a.

strongerthan

average-case

time

boundb.

strongerthan

worst-case

time

boundc.

weakerthan

best-case

time

boundd.

Noneoftheabove7.WhichofthefollowingalgorithmsisNOTrelatedtothegreedyalgorithm?a.

Dijkstra

algorithm

to

find

a

shortest

path

of

a

graph.b.

Kruskal

algorithm

to

find

a

minimum

spanning

tree

of

a

weighted

graph.c.

The

algorithm

to

find

the

optimal

binary

search

tree

forstaticsearch.d.

Huffman’s

codingof

a

list

of

characters

with

given

frequencies.8.Theturnpikereconstructionproblemistoconstructapointsetfromagivensetofdistances.LetD

={1,2,2,3,3,3,5,5,6,8}bethegivensetofdistances.Assumethatthefirstpointx1

=

0.Thenthenumberofpointsandthethirdsmallestpointmaybe

_______.a.

5

and

3 b.

5

and

6 c.

10

and

3 9.Forthefollowingproblems,(a)___

isundecidableand

(b)____isNP-complete.a.

Euler

circuit

problem b.

Halting

problemc.

All-pairs

shortest

paths

problem d.

All-pairs

longest

paths

problemGiventhefunctiondescriptionsofthefollowingtwo(pseudo-code)programs,pleasefillintheblanklines.(18points)1.Thefunction

is

to

find

X

in

a

binomial

queue

H.(9points)BinTree

Find(BinQueue

H,

ElementType

X)/*

To

find

whether

X

is

in

H.

Return

the

node

pointeriffound,

otherwise

return

NULL

*/{ BinTree

T,

result=NULL;int

i,j;

for(i=0,

j=1;

j<=H->CurrentSize;

i++,①_______)

{

/*

for

each

tree

in

H

*/T=

H->TheTrees[i];if

(②____________){

/*

if

need

to

search

insidethistree

*/result=RecurFindInTree(T,

X)if

(result!=NULL)

return

result;}}}BinTree

RecurFindInTree(BinTree

T,

ElementType

X){

BinTree

result=NULL;if

(X==T->Element)

return

T;if

(T->LeftChild

!=NULL

&&

X>=T->LeftChild->Element){result=

RecurFindInTree(T->LeftChild,

X);if

(result!=Null)

return

result;}if

(=3\*GB3③__________________________________________________){result=

RecurFindInTree(T->NextSibling,

X);return

result;}}2.ThefunctionistodoasinglerotationbetweennodeK1anditsrightchildinanAVLtree.(9points)structAvlNode{ElementTypeElement;AvlTreeLeft;AvlTreeRight;intHeight;}TypedefstructAvlNode*Position;TypedefstructAvlNode*AvlTree;staticPositionSingleRotateWithRight(PositionK1){PositionK2;①______;②;=3\*GB3③________________________________;K1->Height=Max(Height(K1->Left),Height(K1->Right))+1;K2->Height=Max(Height(K2->Right),K1->Height)+1;returnK2;}Pleasewriteordrawyouranswersforthefollowingproblemsontheanswersheet.(47points)1.Given

the

keywords

and

searching

frequencies,

Pleasedrawtheoptimalbinarysearchtreein

order

to

minimize

theexpectedtotal

accesstime.(9points)keywordsforswitchdowhilefrequencies0.300.180.250.272.Pleasedrawtheresultsofinserting{42,26,8,70,102,56,2}into:(1)(5points)aninitiallyemptyAVLtree;and(2)(5points)aninitiallyemptysplaytree.(Tip:Drawingthetreesstepbystepmighthelpyougettingpartialcredits.)3,6,73,6,79,119:1919,283.Givena2-3treeasshowninthefigure.Please:(1)showtheresultofinserting4withsplittingstrategy;(3points)(2)showtheresultofdeleting19andthen7fromthetreeobtainedin(1).(3points)4.(1)PleasebrieflydescribetheDocumentdistributionarchitectureforindexconstructionandmaintenanceforfulltextsearchindistributedenvironments.(5points)(2)Pleaselisttheprosandconsofthisstrategy.(5points)5.Pleasedrawtheresultof

deletingtheminimumelementfromthegiven