杭州电子工业学院学生考试卷（A）卷
考试课程数据结构与算法考试日期年月日成绩班级2000软件姓名学号
1.(8分)Imaginewehavetwoemptystacksofintegers,s1ands2.drawapictureofeachstackafterthefollowingoperations:
PushStack(s1,3);
PushStack(s1,-5);
PushStack(s1,7);
PushStack(s1,-9);
PushStack(s1,11);
PushStack(s1,-13);
while(notemptyStack(s1)){
popStack(s1,x);
if(x0){
pushStack(s2,x);
}
}//while
2.(8分)Usingmanualtransformation,changethefollowingpostfixorprefixexpressionstoinfixform.
a.ABC+D-b.-A+BCD
3.(8分)whatwouldbethecontentsofqueueQ1afterthefollowingcodeisexecutedandthefollowingdataareentered?
Q1=CreateQueue
S1=CreateStack
loop(notendoffile)
readnumber
if(numbernot0)
pushStack(S1,number)
else
popStack(S1,x)
popStack(S1,x)
loop(notemptyStack(S1))
popStack(S1,x)
enqueue(Q1,x)
endloop
endif
endloop
Thedataare5,7,12,4,0,4,6,8,67,34,23,5,0,44,33,22,6,0.
4.(8分)CreateaAVLtreeusingthefollowingdataenteredasasequentialset:
7,10,14,23,33,56,66,70,80,90.
5.(8分)Showtheresultingheapafter33,22,and8areaddedtothefollowingheap:
50,30,40,20,10,25,35,10,5.
6.(8分)Aftertwopassesofasortingalgorithm,thefollowarray:
48,5,29,36,7,61,88
hasbeenrearrangedasshownbelow:5,7,48,29,36,61,88
whichsortingalgorithmisbeingused(straightselection,bubble,straightinsertion)?Defendyouranswer.
7.(8分)Agraphcanbeusedtoshowrelationships,forexample,fromthefollowinglistofpeoplebelongingtothesameclub(vertices)andtheirfriendships(edges).
People={George,Jim,Jean,Frank,Fred,John,Susan}
FriendShip={(George,Jean),(Frank,Fred),
(George,John),(Jim,Fred),(Jim,Frank),
(Jim,Susan),(Susan,Frank)}
Givetheadjacencylistrepresentationofthisgraph.
AlgorithmDesign1.(11分)Writeanalgorithmthattraversesalinkedlistanddeletesallnodeswhosekeysarenegative.
2.(11分)Writeanalgorithmthatcountsthenumberofleavesinabinarytree.
3.(11分)WriteanalgorithmcalledQueueToStackthatcreatesastackfromaqueue.Attheendofthealgorithm,thequeueshouldbeunchanged;thefrontofthequeueshouldbethetopofthestack;andtherearofthequeueshouldbethebaseofthestack.
4.(11分)Developanon-recursiveBST(BinarySearchTree)searchalgorithmSearchBST.
标签：数据结构,试题,英文
