2009-2010第学期试卷B答案

数据结构A(2010年7月9日考试)答题卷A(答案与评分标准)一、填空题（前17空每1分，后面4空每空2分，共25分）(1)图（网）(2)操作(3)空间(4)“先进后出”(5)r==f(6)64(7)n(8)2e(9)(10)n2(11)p1&&p2(12)(13)last-next(14)p2(15)!p1-left&&!p2-right(16)root(17)p=root或p=p-right(18)128(19)500(20)-1,0,1,2,3(21)3二、单项选择题（10小题，每小题2分，共20分）(1)B(2)A(3)D(4)C(5)D(6)B(7)A(8)B(9)D(10)C以下三、四、两道大题请抄清题号作答。)log(2nnO三、(简答题，共35分)1．（此题5分）2.(此题5分)调整后的小根堆：6,9,28,15,30,20,72,65,40,76(4分)对应二叉树：(2分)3.(此题6分)(1)3分(2)8.24334221101ASL3分4.(此题共7分)(1)深度优先遍历结点访问次序：ACDBEF2分(2)广度优先遍历结点访问次序：ACEFBD2分(3)逆邻接表3分班级学号姓名密封装订线密封装订线密封装订线ACBDGEFH692830726540761520281572207665930640ABCDEF0123453003504255.(此题6分)6.(此题6分)第一趟：（2分）分配：0123001012133101102201202301收集：001,101,201,301,012,102,202,133第二趟：（2分）分配：0123001012133101201301102202收集：001,101,201,301,102,202,012,133第三趟：（2分）分配：0123001101201301012102202133收集：001,012,101,102,133,201,202,301四、算法设计题（2小题，每小题10分，共20分）1211963451078a123451.voiderase(LNode*h)//2分{pr=h;p=h-next;//2分while(p)//2分{if(p-data0){pr-next=p-next;deletep;}//3分p=pr-next;//1分}}2.voidtravel(BTbt)//1分{if(!bt)return;init(Q);//Q为队列enter(Q,bt);//1分while(!empty(S))//2分{p=quite(Q);visit(p);//2分if(p-left)enter(Q,p-left);//2分if(p-right)enter(Q,p-right);//2分}}