数据结构考试题5

“数据结构”考试试题（A）参考答案

一、单项选择题（每小题2分，共20小题，共计40分）

1. B 6. B 11. C 16. D

2. C 7. D 12. B 17. D

3. A 8. D 13. A 18. A

4. D 9. B 14. B 19. B

5. C 10. A 15. D 20. D

二、问答题（共4小题，共计35分）

1. （10分）答案：

利用普里姆算法从顶点0出发构造的最小生成树为：{(0,1)，(0,3)，(1,2)，(2,5)，(5,4)}，（5分）。

利用克鲁斯卡尔算法构造出的最小生成树为：{(0,1)，(0,3)，(1,2)，(5,4)，(2,5)} ，（5分）。

说明：顺序错误不给分。 2. （10分）答案：

（1）该二叉排序树的后序遍历序列为ACDBFIJHGE，则中序遍历序列为ABCDEFGHIJ，由后序序列和中序序列构造的二叉排序树如图2所示。（6分）

E B A C I D F G H J 图2 一棵二叉排序树

（2）ASL成功=(1×1+2×2+4×3+2×4+1×5)/10=3。（2分） （3）ASL不成功=(6×3+3×4+2×5)/11=40/11=3.64。（2分） 3. （8分）答案：

采用二路归并排序法排序的各趟结果如图3所示。（每趟2分）

排序前: 15,5, 16,2, 25,8, 20,9, 18,12 length=1:5, 15,2, 16,8, 25,9, 20,12,18 length=2:2, 5,15, 16,8, 9, 20,25,12,18 length=4:2, 5,8, 9, 15,16,20,25,12,18 length=8:2, 5,8, 9, 12,15,16,18,20,25 排序后: 2, 5,8, 9, 12,15,16,18,20,25 图3 各趟排序结果

4. （7分）答案：

（1）通常堆采用顺序存储结构。（3分）

（2）小根堆中具有最大关键字的结点只可能出现在叶子结点中。因为最小堆的最小关键字的结点必是根结点，而最大关键字的结点由偏序关系可知，只有叶子结点可能是最大关键字的结点。（4分）

三、算法设计题（共2小题，共计25分）

1. （10分）答案：

void Move(LinkNode *&L) {

LinkNode *p=L->next,*pre=L;

//跳过小于0的结点

while (p!=NULL && p->data<0) { pre=p;p=pre->next; } }

while (p!=NULL) { }

if (p->data<0) { } else { }

//若*p结点值不小于0 //pre、p同步后移一个结点

pre=p; p=p->next;

//若*p结点值小于0

//将*p结点插入到头结点之后 //p指向*pre之后结点，pre不变

pre->next=p->next; //从链表中删除*p结点 p->next=L->next; L->next=p; p=pre->next;

2. （15分）答案：

（1）（7分）

BTNode *Findx(BTNode *b,char x) //在二叉树b中查找x结点 {

BTNode *p; if (b==NULL)

return NULL;

}

else

{ if (b->data==x) }

return b;

p=Findx(b->lchild,x); if (p!=NULL)

return p;

return Findx(b->rchild,x);

算法的时间复杂度为O(n)（1分）。 （2）（7分）

void Sons(BTNode *b,char x) { }

void OutSons(BTNode *b,char x) //输出二叉树b中x结点的所有子孙结点值 { }

BNode *p= Findx(b,x); if (p!=NULL)

Sons(p,x); if (b!=NULL) { }

if (b->data!=x)

printf(\Sons(b->lchild,x); Sons(b->rchild,x);

//输出x结点的子孙，初始时b指向x结点