2010年海南省数据理论摘要
- 格式：docx
- 大小：16.09 KB
- 文档页数：1
1、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量
d[1..n]前半部和后半部（注:向量d可视为循环表），其原则为，先将r[l]赋给d[1]，再从
r[2] 记录开始分二路插入。编写实现二路插入排序算法。
2、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用
递归算法。
int Similar(BiTree p,q) //判断二叉树p和q是否相似
{if(p==null && q==null) return (1);
else if(!p && q || p && !q) return (0);
else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild))
}//结束Similar
3、设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式
存储结构表示。
typedef struct node {int data; struct node *next;}lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc)
{
lklist *p,*q,*t;
for(p=ha,hc=0;p!=0;p=p->next)
{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;
if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;}
}
}
4、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={
写出G的拓扑排序的结果。
G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7
