2013年全国数据整理加强(4)
时间:2025-04-08
时间:2025-04-08
2013年全国数据整理加强
eComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是,返回1,否则,返回0
{int tag=0; BiTree p=bt, Q[]; // Q是队列,元素是二叉树结点指针,容量足够大
if(p==null) return (1);
QueueInit(Q); QueueIn(Q,p); //初始化队列,根结点指针入队
while (!QueueEmpty(Q))
{p=QueueOut(Q); //出队
if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队
else {if (p->lchild) return 0; //前边已有结点为空,本结点不空
else tag=1; //首次出现结点为空
if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队
else if (p->rchild) return 0; else tag=1;
} //while
return 1; } //JudgeComplete
9、设有一组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(i<j){
while (i<j && r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;}
while (i<j && r[i]<x) i=i+1; if (i<j) {r[j]=r[i];j=j-1;}
}
r[i]=x;
}
10、数组A和B的元素分别有序,欲将两数组合并到C数组,使C仍有序,应将A和B拷贝到C,只要注意A和B数组指针的使用,以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。
void union(int A[],B[],C[],m,n)
//整型数组A和B各有m和n个元素,前者递增有序,后者递减有序,本算法将A和B归并为递增有序的数组C。
{i=0; j=n-1; k=0;// i,j,k分别是数组A,B和C的下标,因用C描述,下标从0开始
while(i<m && j>=0)
if(a[i]<b[j]) c[k++]=a[i++] else c[k++]=b[j--];
while(i<m) c[k++]=a[i++];
while(j>=0) c[k++]=b[j--];
}算法结束
4、要求二叉树按二叉链表形式存储。15分
(1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。
BiTree Creat() //建立二叉树的二叉链表形式的存储结构
{ElemType x;BiTree bt;
scanf(“%d”,&x); //本题假定结点数据域为整型
if(x==0) bt=null;
else if(x>0)
{bt=(BiNode *)malloc(sizeof(BiNode));
bt->data=x; bt->lchild=creat(); bt->rchild=creat();
}
else error(“输入错误”);
return(bt);
}//结束 BiTree
int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是,返回1,否则,返回0
{int tag=0; BiTree p=bt, Q[]; // Q是队列,元素是二叉树结点指针,容量足够大
if(p==null) return (1);
QueueInit(Q); QueueIn(Q,p); //初始化队列,根结点指针入队
while (!QueueEmpty(Q))
{p=QueueOut(Q);
//出队
if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队
else {if (p->lchild) return 0; //前边已有结点为空,本结点不空
上一篇:电气照明设计中的节能措施
下一篇:商业银行的公司治理