北华大学计算机科学技术学院2013-2014学年第1学期数据结构期末试卷答案

出题人薛曼玲使用专业计算机科学与技术（师、工）软件工程、网络工程年级2012级第1页共3页北华大学计算机科学技术学院2013-2014学年第一学期《数据结构》课程期末考试试卷（2）参考答案与评分标准一、填空题（每空1分，共14分）1.关系操作2.n-i+13.n-14.bedca5.n-2m+16.97.37/12二、选择题（每题2分，共16分）1.C2.D3.B4.D5.B6.A7.C8.A三、应用题（1~4题每题6分，5~6题每题8分，共40分）1.答：(1)占用6×8×6=288个字节。【2分】(2)1000+(1×8+4)×6=1072【2分】(3)1000+(7×6+4)×6=1276【2分】2.答案不唯一哈夫曼编码：a：11b：101c：01d：000e：001f：1003.答：4.答：线性探测再散列解决冲突构造的哈希表【4分】1003961192028111791033ABDCEFGHI第2页共3页012345678293632122018121114ASL成功=（4×1+2+4）/6=5/3【2分】5.答：从顶点A出发的深度优先遍历的顶点序列：ABCEFD【1.5分】（答案不唯一）从顶点A出发的广度优先遍历的顶点序列：ABCDEF【1.5分】（答案不唯一）每图【1分】分（3和4的顺序可以颠倒）6.答：（1）（3分）2515402123223248(1)ABCEFD5ABCEFD56A657BCEFDABCEFD7567ABCEFD75679(2)(3)(4)(5)第3页共3页（2）查找成功的平均查找长度为：（1*1+2*2+3*3+4*1+5*1）/8=23/8（3分）查找不成功的平均查找长度为：（2*1+3*5+4*1+5*2）/8=31/9（2分）四、算法设计（每小题10分，共30分）1.答：①p-costh②p-num=p-num+m③t-num=m;④t-next=p;（注后两空顺序可以颠倒）2.答：①LT(L.r[i-dk].key,L.r[i].key)②LT(L.r[j].key,L.r[0].key)③j-=dk④L.r[j+dk]=L.r[j]3.答：voidBFSTraverse(ALGraphG，Status(*Visit)(intv)){for(v=0;vG.vexnum;v++)visited[v]=FALSE;InitQueue(Q);for(v=0;vG.vexnum;v++)if(!visited[v]){visited[v]=TRUE;Visit(v);EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue();for(w=FirstAdjVex(G,u);w=0;w=NextAdjvex(G,u,w))if(!visited[w]){visited[w]=TRUE;Visit(w);EnQueue(Q,w);}}}}