2013年全国数据整理加强(5)
时间:2025-04-08
时间:2025-04-08
2013年全国数据整理加强
else tag=1; //首次出现结点为空
if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队
else if (p->rchild) return 0; else tag=1;
} //while
return 1; } //JudgeComplete
11、设T是一棵满二叉树,编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
12、设有两个集合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;}
}
}
13、设T是一棵满二叉树,编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
14、设有一组初始记录关键字序列(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;
}
15、矩阵中元素按行和按列都已排序,要求查找时间复杂度为O(m+n),因此不能采用常规的二层循环的查找。可以先从右上角(i=a,j=d)元素与x比较,只有三种情况:一是A[i,j]>x, 这情况下向j 小的方向继续查找;二是A[i,j]<x,下步应向i大的方向查找;三是A[i,j]=x,查找成功。否则,若下标已超出范围,则查找失败。
void search(datatype A[ ][ ], int a,b,c,d, datatype x)
//n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中.
{i=a; j=d; flag=0; //flag是成功查到x的标志
while(i<=b && j>=c)
if(A[i][j]==x) {flag=1;break;}
else if (A[i][j]>x) j--; else i++;
if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型.
else printf(“矩阵A中无%d 元素”,x);
}算法search结束。
[算法讨论]算法中查找x的路线从右上角开始,向下(当x>A[i,j])或向左(当x<A[i,j])。向下最多是m,向左最多是n。最佳情况是在右上角比较一次成功,最差是在左下角(A[b,c]),比较m+n次,故算法最差时间复杂度是O(m+n)。
16、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT
为指向该二叉树根结点的指针,p和q分别为指向该二叉树中任意两个结点的指针,试编写一算法ANCESTOR(ROOT,p,q,r),该算法找到p和q的最近共同祖先结点r。
17、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中的每个结点都是“局部根”。确定根后,到二叉
上一篇:电气照明设计中的节能措施
下一篇:商业银行的公司治理