文档库

最新最全的文档下载
当前位置:文档库 > 2014年广东省数据统计深入

2014年广东省数据统计深入

1、我们用l代表最长平台的长度,用k指示最长平台在数组b中的起始位置(下标)。用j记住局部平台的起始位置,用i指示扫描b数组的下标,i从0开始,依次和后续元素比较,若局部平台长度(i-j)大于l时,则修改最长平台的长度k(l=i-j)和其在b中的起始位置(k=j),直到b数组结束,l即为所求。
void Platform (int b[ ], int N)
//求具有N个元素的整型数组b中最长平台的长度。
{l=1;k=0;j=0;i=0;
while(i{while(iif(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台
i++; j=i; } //新平台起点
printf(“最长平台长度%d,在b数组中起始下标为%d”,l,k);
}// Platform

2、有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键码互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键码比该记录的关键码小,假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c。
(1) (3分)给出适用于计数排序的数据表定义;
(2) (7分)使用Pascal或C语言编写实现计数排序的算法;
(3) (4分)对于有n个记录的表,关键码比较次数是多少?
(4) (3分)与简单选择排序相比较,这种方法是否更好?为什么?

3、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={,,,,,,,,}
写出G的拓扑排序的结果。
G拓扑排序的结果是:V1、V2、V4、V3、V5、V6、V7


4、给定n个村庄之间的交通图,若村庄i和j之间有道路,则将顶点i和j用边连接,边上的Wij表示这条道路的长度,现在要从这n个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法,并应用该算法解答如图所示的实例。20分
void Hospital(AdjMatrix w,int n)
//在以邻接带权矩阵表示的n个村庄中,求医院建在何处,使离医院最远的村庄到医院的路径最短。
{for (k=1;k<=n;k++) //求任意两顶点间的最短路径
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (w[i][k]+w[k][j]m=MAXINT; //设定m为机器内最大整数。
for (i=1;i<=n;i++) //求最长路径中最短的一条。
{s=0;
for (j=1;j<=n;j++) //求从某村庄i(1<=i<=n)到其它村庄的最长路径。
if (w[i][j]>s) s=w[i][j];
if (s<=m) {m=s; k=i;}//在最长路径中,取最短的一条。m记最长路径,k记出发

顶点的下标。
Printf(“医院应建在%d村庄,到医院距离为%d\n”,i,m);
}//for
}//算法结束
对以上实例模拟的过程略。各行中最大数依次是9,9,6,7,9,9。这几个最大数中最小者为6,故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。

1、对图1所示的连通网G,请用Prim算法构造其最小生成树(每选取一条边画一个图)。

5、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n-1条边为止。
void SpnTree (AdjList g)
//用“破圈法”求解带权连通无向图的一棵最小代价生成树。
{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数
node edge[];
scanf( "%d%d",&e,&n) ; //输入边数和顶点数。
for (i=1;i<=e;i++) //输入e条边:顶点,权值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i<=e;i++) //按边上的权值大小,对边进行逆序排序。
{edge[0]=edge[i]; j=i-1;
while (edge[j].wedge[j+1]=edge[0]; }//for
k=1; eg=e;
while (eg>=n) //破圈,直到边数e=n-1.
{if (connect(k)) //删除第k条边若仍连通。
{edge[k].w=0; eg--; }//测试下一条边edge[k],权值置0表示该边被删除
k++; //下条边
}//while
}//算法结束。
connect()是测试图是否连通的函数,可用图的遍历实现,

6、设t是给定的一棵二叉树,下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量,且在调用count(t)之前都置为0.
typedef struct node
{int data; struct node *lchild,*rchild;}node;
int N2,NL,NR,N0;
void count(node *t)
{if (t->lchild!=NULL) if (1)___ N2++; else NL++;
else if (2)___ NR++; else (3)__ ;
if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;
}
26.树的先序非递归算法。
void example(b)
btree *b;
{ btree *stack[20], *p;
int top;
if (b!=null)
{ top=1; stack[top]=b;
while (top>0)
{ p=stack[top]; top--;
printf(“%d”,p->data);
if (p->rchild!=null)
{(1)___; (2)___;
}
if (p->lchild!=null)
(3)___; (4)__;
}}}}

7、本题应使用深度优先遍历,从主调函数进入dfs(v)时 ,开始记数,若退出dfs()前,已访问完有向图的全部顶点(设为n个),则有向图有根,v为根结点。将n个顶点从1到n编号,各调用一次dfs()过程,就可以求

出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题,这里只给出判断有向图是否有根的算法。
int num=0, visited[]=0 //num记访问顶点个数,访问数组visited初始化。
const n=用户定义的顶点数;
AdjList g ; //用邻接表作存储结构的有向图g。
void dfs(v)
{visited [v]=1; num++; //访问的顶点数+1
if (num==n) {printf(“%d是有向图的根。\n”,v); num=0;}//if
p=g[v].firstarc;
while (p)
{if (visied[p->adjvex]==0) dfs (p->adjvex);
p=p->next;} //while
visited[v]=0; num--; //恢复顶点v
}//dfs
void JudgeRoot()
//判断有向图是否有根,有根则输出之。
{static int i ;
for (i=1;i<=n;i++ ) //从每个顶点出发,调用dfs()各一次。
{num=0; visited[1..n]=0; dfs(i); }
 }// JudgeRoot
算法中打印根时,输出顶点在邻接表中的序号(下标),若要输出顶点信息,可使用g[i].vertex。



8、本题要求建立有序的循环链表。从头到尾扫描数组A,取出A[i](0<=iLinkedList creat(ElemType A[],int n)
//由含n个数据的数组A生成循环链表,要求链表有序并且无值重复结点
{LinkedList h;
h=(LinkedList)malloc(sizeof(LNode));//申请结点
h->next=h; //形成空循环链表
for(i=0;i{pre=h;
p=h->next;
while(p!=h && p->data{pre=p; p=p->next;} //查找A[i]的插入位置
if(p==h || p->data!=A[i]) //重复数据不再输入
{s=(LinkedList)malloc(sizeof(LNode));
s->data=A[i]; pre->next=s; s->next=p;//将结点s链入链表中
}
}//for
return(h);
}算法结束

9、设有两个集合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;}
}
}

10、设T是一棵满二叉树,编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
11、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针,p和q分别为指向该二叉树中任意两个结点的指针,试编写一算法ANCESTOR(ROOT,p,q,r),该算法找到p和q的最近共同祖先结点r。
12、设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
13、请设计一个算法,要

求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表,表头指针为head。 二叉树按二叉链表方式存储,链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。
14、冒泡排序算法是把大的元素向上移(气泡的上浮),也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中,现用双向起泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向起泡排序即相邻两趟排序向相反方向起泡)

15、假设K1,…,Kn是n个关键词,试解答:
试用二叉查找树的插入算法建立一棵二叉查找树,即当关键词的插入次序为K1,K2,…,Kn时,用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。

16、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针,p和q分别为指向该二叉树中任意两个结点的指针,试编写一算法ANCESTOR(ROOT,p,q,r),该算法找到p和q的最近共同祖先结点r。
17、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树,下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列,生成一棵用二叉链表表示的二叉树并打印出后序遍历序列,请写出程序所缺的语句。
#define MAX 100
typedef struct Node
{char info; struct Node *llink, *rlink; }TNODE;
char pred[MAX],inod[MAX];
main(int argc,int **argv)
{ TNODE *root;
if(argc<3) exit 0;
strcpy(pred,argv[1]); strcpy(inod,argv[2]);
root=restore(pred,inod,strlen(pred));
postorder(root);
}
TNODE *restore(char *ppos,char *ipos,int n)
{ TNODE *ptr; char *rpos; int k;
if(n<=0) return NULL;
ptr->info=(1)_______;
for((2)_______ ; rposk=(3)_______;
ptr->llink=restore(ppos+1, (4)_______,k );
ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);
return ptr;
}
postorder(TNODE*ptr)
{ if(ptr=NULL) return;
postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info);
}

18、设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。现要求将Kn放在将元素排序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过n。
51. 借助于快速排序的算法思想,在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功,则输出该记录在r数组中的位置及其值,否则显示“not find”信息。请编写出算法并简要说明算法思想。

19、假设K1,…,Kn是n个关键词,试解答:
试用二叉查找树的插入算法建立一棵二叉查找树,即当关键词的插入次序为K1,K2,…,Kn时,用算法建立一棵以LLINK / RLINK 链接表示的

二叉查找树。

20、设T是一棵满二叉树,编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
21、有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键码互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键码比该记录的关键码小,假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c。
(1) (3分)给出适用于计数排序的数据表定义;
(2) (7分)使用Pascal或C语言编写实现计数排序的算法;
(3) (4分)对于有n个记录的表,关键码比较次数是多少?
(4) (3分)与简单选择排序相比较,这种方法是否更好?为什么?

22、设有一组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(iwhile (ix) j=j-1; if (iwhile (i}
r[i]=x;
}

23、(1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild) (5)ADDQ(Q,p->rchild)
25. (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild)
26. .(1)top++ (2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild
27. (1)*ppos // 根结点 (2)rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1

24、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。(15分)
(1)A和D是合法序列,B和C 是非法序列。
(2)设被判定的操作序列已存入一维数组A中。
int Judge(char A[])
//判断字符数组A中的输入输出序列是否是合法序列。如是,返回true,否则返回false。
{i=0; //i为下标。
j=k=0; //j和k分别为I和字母O的的个数。
while(A[i]!=‘\0’) //当未到字符数组尾就作。
{switch(A[i])
{case‘I’: j++; break; //入栈次数增1。
case‘O’: k++; if(k>j){printf(“序列非法\n”);exit(0);}
}
i++; //不论A[i]是‘I’或‘O’,指针i均后移。}
if(j!=k) {printf(“序列非法\n”);return(false);}
else {printf(“序列合法\n”);return(true);}
}//算法结束。