2012数据结构b卷答案

《2012数据结构b卷答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、安徽大学2011—2012学年第2学期《数据结构》考试试卷（B卷）答案（闭卷时间120分钟）一、填空题（每空2分，共30分）第3页共3页1．线性栈顶对尾队首2．push()3．444．前驱后继_5．10886．117.一半8．O(m*n)9．（（b，c））10._n-1_11._99第3页共3页二、单项选择题（每小题2分，共20分）第3页共3页1.B2．B3.C4、C5、A6、D7.A8.C9、C10.B第3页共3页三、判断题（在正确的题后括号内打P，错的则打×，每小题1分，共10分）第3页共3页

2、1.（Ö）2.(×）3.（×）4.（×）5.（Ö）6.（Ö）7．（×）8．（×）9.（×）10.（Ö）第3页共3页四、简答题（每小题分数见小题题目后，共30分。）1．（5分）不能，无法确定根节点。（5分）第3页共3页71AA2．（10分）4124DCBBDCBB63523FEFEA4717A24DCBB41635224DCBBFE635233FEA71424DCBB6352FE3注，本题可获得最小生成树的其他方法亦可酌情给分。3．散列地址为：（5分）H(45)=45%13=6H(62)=62%13

3、=10H(16)=16%13=3H(50)=50%13=11H(35)=35%13=9H(94)=94%13=3（冲突）H1=(3+1)%13=4H(25)=25%13=12H(36)=36%13=10（冲突）H1=(10+1)%13=11（冲突）H2=(10+2)%13=12（冲突）H3=(10+3)%13=0H(18)=18%13=5H(70)=70%13=5（冲突）H1=(5+1)%13=6（冲突）H2=(5+2)%13=7散列表为：（2分）0123456789101112361694184

4、57035625025ASL=（7*1+1*2+1*3+1*4）/10=16/10=1.6（3分）五、算法阅读题（5分）第3页共3页118^52L链接对一个结点1分六、算法设计（5分）typedefstructLNode{ElemTypedata；structLNode*next；}LNode，*LinkList；voidinverse(LinkList&L){//逆置带头结点的单链表Lp=L->next;L->next=NULL;（2分）while(p){（2分）succ=p->next;//s

5、ucc指向*p的后继（2分）p->next=L->next;（2分）L->next=p;//*p插入在头结点之后p=succ;（2分）}}算法设计其它可实现的算法也正确。第3页共3页