2011数据结构 A卷参考答案与评分细则

《2011数据结构 A卷参考答案与评分细则》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2011计科1、2班数据结构A卷参考答案与评分细则一、选择题（每题2分，共30分）题号12345678910选项③③②②④①②③④④题号1112131415选项③④④④④二、判断题（每题1分，共10分）题号12345678910对错×××××√××√×三、填空题（每空1分，共10分）1、线性表、栈、队列、串；顺序存储结构和链式存储结构；2、2.1s->next=p->next;2.2p->next=s;3、23100CH四、应用题（第1题5分，第2题4分，第3题10分，第4题10分，第5题21分，共50分）1、（第1题5分）参考答案：ABHDCEGIF2、（第

2、2题4分）参考答案：第一趟排序后：38，49，65，76，13，27，49，97（2分）第二趟排序后：38，49，65，13，27，49，76，97（2分）3、（第3题10分）参考答案：字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:001或者其哈夫曼编码为：A：0，B：111，C：10，D：110(5分)哈夫曼树如下:（5分）331951000111、（第4题10分）参考答案：（8分）散列地址0123456789关键字140192384275520比较次数11123412平均查找长度：ASLsucc=（1+1+

3、1+2+3+4+1+2）/8=15/8（2分）2、（第5题21分）参考答案：（1）（5分）ABCDEFGHA02300000B00050000C000310000D00000400E00000030F00002006G00000001H00000000（2）（6分）全部拓扑排序如下：A->B->C->D->F->E->G->H（3分）A->C->B->D->F->E->G->H（3分）（3）（6分）事件最早时间最晚时间A00B22C33D77E1313F1111G1616H17173关键路径：（3分）ACEGH和ABDFH和ABDFEGH（4）（4分）结点A结

4、点到各点的最短距离B2C3D6E12F10G15H163