文档库

最新最全的文档下载
当前位置:文档库 > 2012年广东省数据分析入门

2012年广东省数据分析入门

1、在有向图G中,如果r到G中的每个结点都有路径可达,则称结点r为G的根结点。编写一个算法完成下列功能:
(1).建立有向图G的邻接表存储结构;
(2).判断有向图G是否有根,若有,则打印出所有根结点的值。

2、设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
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
4、设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。