《2014年宁夏回族自治区数据整理大纲.docx》由会员分享，可在线阅读，更多相关《2014年宁夏回族自治区数据整理大纲.docx（5页珍藏版）》请在三一文库上搜索。
1、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(in-1)while(il) l=i-j+1;k=j; /局部最长平台 i+; j=i; /新平台起点p
2、rintf(“最长平台长度%d，在 b 数组中起始下标为%d”，l，k)；/ Platform2、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。void PreToPost(ElemType pre ,post,int l1,h1,l2,h2)/将满二叉树的先序序列转为后序序列，l1,h1,l2,h2 是序列初始和最后结点的下标。if(h1=l1)posth2=prel1;/根结点half=(h1-l1)/2;/左或右子树的结点数Pr
3、eToPost(pre,post,l1+1,l1+half,l2,l2+half-1) /将左子树先序序列转为后序序列 PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) /将右子树先序序列转为后序序列 /PreToPost32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针 pre，初始为空。第一个叶子结点由指针 head 指向，遍历到叶子结点时，就将它前驱的 rchild 指针指向它，最后叶子结点的 rchild 为空。LinkedList head,pre=null;/全局变量LinkedList InOrder(BiTr
4、ee bt)/中序遍历二叉树 bt，将叶子结点从左到右链成一个单链表，表头指针为 headif(bt)InOrder(bt-lchild); /中序遍历左子树 if(bt-lchild=null & bt-rchild=null) /叶子结点 if(pre=null) head=bt; pre=bt; /处理第一个叶子结点 elsepre-rchild=bt; pre=bt; /将叶子结点链入链表 InOrder(bt-rchild); /中序遍历左子树 pre-rchild=null; /设置链表尾return(head); /InOrder时间复杂度为 O(n),辅助变量使用 head 和
5、 pre,栈空间复杂度 O(n)3、数组 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=0)if(aibj) ck+=ai+ els
6、e ck+=bj-;while(i=0) ck+=bj-;算法结束4、要求二叉树按二叉链表形式存储。15 分（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。BiTree Creat()/建立二叉树的二叉链表形式的存储结构ElemType x；BiTree bt;scanf(“%d”,&x);/本题假定结点数据域为整型if(x=0) bt=null;else if(x0)bt=(BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat(); bt-rchild=creat();else error(“输入
7、错误”)；return(bt);/结束 BiTreeint JudgeComplete(BiTree bt) /判断二叉树是否是完全二叉树,如是，返回 1，否则，返回 0int 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) ret
8、urn 0;else tag=1;if (p-rchild & !tag) QueueIn(Q,p-rchild);else if (p-rchild) return 0; else tag=1; /whilereturn 1; /JudgeComplete/出队/左子女入队/前边已有结点为空，本结点不空/首次出现结点为空/右子女入队4、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。
9、void Translation（float *matrix，int n）/本算法对 nn 的矩阵 matrix，通过行变换，使其各行元素的平均值按递增排列。 int i,j,k,l；float sum，min；/sum 暂存各行元素之和float *p, *pi, *pk;for(i=0; in; i+)sum=0.0; pk=matrix+i*n;/pk 指向矩阵各行第 1 个元素.for (j=0; jn; j+)sum+=*(pk); pk+;/求一行元素之和.*(p+i)=sum;/将一行元素之和存入一维数组./for ifor(i=0; in-1; i+)/用选择法对数组 p 进行
10、排序min=*(p+i); k=i;/初始设第 i 行元素之和最小.for(j=i+1;jn;j+) if(pjmin) k=j; min=pj;/记新的最小值及行号.if(i!=k) /若最小行不是当前行,要进行交换(行元素及行元素之和) pk=matrix+n*k; /pk 指向第 k 行第 1 个元素. pi=matrix+n*i; /pi 指向第 i 行第 1 个元素. for(j=0;j0）个人按顺时针方向围坐成一圈，现从第 s 个人开始按顺时针方向报数，数到第 m 个人出列，然后从出列的下一个人重新开始报数，数到第 m 的人又出列，如此重复直到所有的人全部出列为止。现要求采用循环链
11、表结构设计一个算法，模拟此过程。#includetypedef int datatype;typedef struct nodedatatypedata;struct node *next;listnode;typedef listnode *linklist;void jose(linklist head,int s,int m)linklist k1,pre,p;int count=1;pre=NULL;k1=head;/*k1 为报数的起点*/while (count!=s)/*找初始报数起点*/pre=k1;k1=k1-next;count+;while(k1-next!=k1)/*当
12、循环链表中的结点个数大于 1 时*/p=k1;/*从 k1 开始报数*/count=1;while (count!=m)/*连续数 m 个结点*/ pre=p;p=p-next;count+;pre-next=p-next;/*输出该结点，并删除该结点*/printf(%4d,p-data);free(p);k1=pre-next;/*新的报数起点*/printf(%4d,k1-data); /*输出最后一个结点*/ free(k1);main()linklist head,p,r;int n,s,m,i;printf(n=);scanf(%d,&n);printf(s=);scanf(%d,
13、&s);printf(m=,&m);scanf(%d,&m);if (n1) printf(ndata=n;r=head;for (i=n-1;i0;i-) /*建立剩余 n-1 个结点*/ p=(linklist)malloc(sizeof(listnode);p-data=i;p-next=head;head=p;r-next=head;/*生成循环链表*/jose(head,s,m);/*调用函数*/6、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语
14、句。#defineMAX 100typedef struct Nodechar info; struct Node *llink, *rlink; TNODE; char predMAX,inodMAX;main(int argc,int *argv) TNODE*root;if(argc3) exit 0;strcpy(pred,argv1); strcpy(inod,argv2);root=restore(pred,inod,strlen(pred);postorder(root);TNODE *restore(char *ppos,char *ipos,int n) TNODE*ptr； char *rpos;intk;if(ninfo=(1)_;for(2)_ ; rposllink=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);7、设 T 是一棵满二叉树，编写一个将 T 的先序遍历序列转换为后序遍历序列的递归算法。