软件学院数据结构与算法分析期末试题BWord文档格式.docx

软件学院数据结构与算法分析期末试题BWord文档格式.docx

《软件学院数据结构与算法分析期末试题BWord文档格式.docx》由会员分享，可在线阅读，更多相关《软件学院数据结构与算法分析期末试题BWord文档格式.docx（8页珍藏版）》请在冰点文库上搜索。

3

4

5

6

7

卷面成绩

得分

20

10

15

阅卷教师

阅卷时间

1.Single-Choicequestions（eachquestion2scores,total20scores）

（1）Theprimarypurposeofmostcomputerprogramsis

a）toperformamathematicalcalculation.

b）tostoreandretrieveinformation.

c）tosortacollectionofrecords.

d）alloftheabove.

（2）AssumethatPcontainsnelements.ThenumberofsetsinthepowersetofPis

a）nb）n^2

c）2^nd）2^n-1

e）2^n+1

（3）Pickthegrowthratethatcorrespondstothemostefficientalgorithmasngetslarge:

a）5nb）20logn

c）2n^2d）2^n

（4）Asequencehasthefollowingproperties:

a）Mayhaveduplicates,elementhaveaposition.

b）Mayhaveduplicates,elementsdonothaveaposition.

c）Maynothaveduplicates,elementshaveaposition.

d）Maynothaveduplicates,elementsdonothaveaposition.

（5）ThecorrecttraversaltouseonaBSTtovisitthenodesinsortedorderis:

a）Preordertraversal.b）Inordertraversal.

c）Postordertraversal.

（6）Whensortingnrecords,Insertionsorthasbest-casecost:

a）O（logn）.b）O（n）.

c）O（nlogn）.d）O（n^2）

e）O（n!

）f）Noneoftheabove.

（7）Foralistoflengthn,thelinked-listimplementation'

sprev

functionrequiresworst-casetime:

a）O

（1）.

b）O（logn）.

c）O（n）.

d）O（n^2）.

（8）Theeasiestwaytorepresentageneraltreeisto:

a）converttoalist.b）converttoabinarytree.

c）converttoagraph.

（9）Depth-firstsearchisbestimplementedusing:

a）Astackorrecursion.b）Aqueue.

c）Atree.

（10）ForsetP,thenotation|P|indicates

a）ThenumberofelementsinP.b）TheinverseofP.

c）ThepowersetofP.d）Noneoftheabove.

2．（10scores）

WriteaseriesofC++statementsthatusestheListADTasfollowstocreatealistcapableofholdingtwentyelementsandwhichactuallystoresthelistwithfollowingconfiguration:

<

6,28|18,8,19>

solution:

listL1（20）;

L1.append（6）;

L1.append（28）;

L1.append（18）;

L1.append（8）;

L1.append（9）;

L1.next（）;

//Listabstractclass

template<

classElem>

classList{

public:

//Reinitializethelist.Theclientisresponsiblefor

//reclaimingthestorageusedbythelistelements.

virtualvoidclear（）=0;

//Insertanelementatthefrontoftherightpartition.

//Returntrueifsuccessful,falseifthelistisfull.

virtualboolinsert（constElem&

）=0;

//Appendanelementattheendoftherightpartition.

virtualboolappend（constElem&

//Removethefirstelementofrightpartition.Return

//trueifsuccessful,falseifrightpartitionisempty.

//Theelementremovedisreturnedintheparameter.

virtualboolremove（Elem&

//Placefenceatliststart,makingleftpartitionempty

virtualvoidsetStart（）=0;

//Placefenceatlistend,makingrightpartitionempty

virtualvoidsetEnd（）=0;

//Movefenceonestepleft;

nochangeifalreadyatstart

virtualvoidprev（）=0;

//Movefenceonestepright;

nochangeifalreadyatend

virtualvoidnext（）=0;

//Returnlengthofleftpartition

virtualintleftLength（）const=0;

//Returnlengthofrightpartition

virtualintrightLength（）const=0;

//Ifposormoreelementsareinthelist,setthesize

//ofleftpartitiontoposandreturntrue.Otherwise,

//donothingandreturnfalse.

virtualboolsetPos（intpos）=0;

//Returninfirstparameterthefirstelementofthe

//rightpartition.Returntrueifsuccessful,false

//iftherightpartitionisempty.

virtualboolgetValue（Elem&

）const=0;

//Printthecontentsofthelist

virtualvoidprint（）const=0;

};

3．（10scores）

BuildtheHuffmancodingtreeanddeterminethecodesforthefollowingsetoflettersandweights:

abcde.

135711

Huffmancodingtreeasfollows:

Herearethefinalcodes.

a11111

b1110

c110

d10

e0

4．（15scores）

Whataretheminimumandmaximumnumberofelememtsinaheapofheighth?

Theminimumnumberofelementsiscontainedintheheapwithasinglenodeatdepthh-1,foratotalof2h-1nodes.

Themaximumnumberofelementsiscontainedintheheapthathascompletelyfilleduplevelh-1,foratotalof2h-1nodes.

5．（15scores）

TheBubbleSortimplentationhasthefollowinginnerforloop:

for（intj=n–1;

j>

i;

j--）

Considertheeffectofreplacingthiswiththefollowingstaement:

0;

Wouldthenewimplementationworkcorrectly?

Wouldthechangeaffecttheasymptoticcomplexityofthealgorithm?

Howwouldthechangeaffecttherunningtimeofthealgorithm?

Therevisedalgorithmwillworkcorrectly,anditsasymptoticcomplexitywillremainΘ（n2）.However,itwilldoabouttwiceasmanycomparisons,sinceitwillcompareadjacentelementswithintheportionofthelistalreadyknowntobesorted.Theseadditionalcomparisonsareunproductive.

6．（15scores）

//Binarytreenodeabstractclass

classBinNode{

//Returnthenode'

selement

virtualElem&

val（）=0;

//Setthenode'

virtualvoidsetVal（constElem&

sleftchild

virtualBinNode*left（）const=0;

virtualvoidsetLeft（BinNode*）=0;

srightchild

virtualBinNode*right（）const=0;

virtualvoidsetRight（BinNode*）=0;

//Returntrueiffthenodeisaleaf

virtualboolisLeaf（）=0;

Writearecursivefunctionthatreturnsacountofthenumberofleafnodesinabinarytrue..

intcount（BinNode<

Elem>

*subroot）

{

if（subroot==NULL）return0;

//Emptysubtree

if（subroot->

isLeaf（））return1;

//Aleaf

return1+count（subroot->

left（））+

count（subroot->

right（））;

}

7．（15scores）

ListtheorderinwhichtheedgesofthefollowinggrapharevisitedwhenrunningKruskal’sMSTalgorithm.ShowthefinalMST.

（1,6）（6,5）（2,3）（2,4）（4,6）.

Alternatively,（1,6）（6,5）（2,3）（2,4）（1,2）.

etc