文档库

最新最全的文档下载
当前位置:文档库 > 2014年湖北省学习数据库要领

2014年湖北省学习数据库要领

1、设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A 的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。

2、设有一组初始记录关键字序列(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

while (ix) j=j-1; if (i

while (i

}

r[i]=x;

}

3、矩阵中元素按行和按列都已排序,要求查找时间复杂度为O(m+n),因此不能采用常规的二层循环的查找。可以先从右上角(i=a,j=d)元素与x比较,只有三种情况:一是A[i,j]>x,这情况下向j 小的方向继续查找;二是A[i,j]

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