1.C 2.D 3.C 4.C 5.A 6.B 7.D 8.C 9.B 10.C
三、应用题ห้องสมุดไป่ตู้每题10分，共40分）
1.a,b,c,d,e出现的频率分别是：14/55,7/55,10/55,3/55,21/55
2.插入关键字B，L，F，P，Q，R后的三阶B_树为：
3.（1）用第一元素中的值6作为枢轴，快速排序第一次分割后A中的结果是：
break;
case 1:
hb->next=qb->next;
qb->next=qa; ha->next=qb;
ha=qb; qb=hb->next;
break;
}
}
if (!Empty(qb)) ha->next=qb;
free(hb);
}
1.statusSearch_Updata(LinkList L, ElemType a, ElemType b)
{
if (!L) return ERROR;
p=L;
while(p->next){
if (p->data==a ) p->data=b;
p=p->next;
}
return OK
}
2.void AddPolyn(polynomial &Pa,polynomial &Pb)
{
case -1:
ha=qa;
qa=qa->next;
break;
case 0:
sum=a.coef+b.coef;
if (sum!=0.0){ qa.coef=sum; ha=qa; }
else {ha->next =qa->next; Free(qa); }
qa=qa->next;hb->next=qb->next; free(qb);qb=hb->next;
0，2，5，4，3，6，8，7，9
（2）不是堆。调整为大顶堆后结果为：9，7，8，5，3，6，4，2，0
4.证明：由满k叉树的定义可知树中分支的个数为：n0+n1-1
另，分支的个数还可表示为：k*n1
因此得：n0+n1-1= k*n1
推导上式得：n0=(k-1)n1+1
证毕。
四、算法设计题（1+20分＝30分）
山东科技大学
《数据结构》模拟试卷（A卷）答案
班级姓名学号
题号
一
二
三
四
五
总得分
评卷人
审核人
得分
一、填空题（每空1分，共10分）
1. 100 2.P->next=Q;3.study4. 000041 5. 3064 6.( )
7. 4 8.网中存在回路（或网中存在环） 9. 低1层 10. 11
二、单项选择题（每题2分，共20分）
//用带表头结点的链表Pa和Pb分别表示两个多项式
{
ha=Pa; hb=Pb;
qa=ha->next; qb=hb->next;
while (!Empty(qa)&&!Empty(qb))
{
a=GetCurElem(qa); b=GetCurElem(qb);//获取结点中的指数项
swich(*cmp(a,b))