2021年青海省数据概述大纲

1、2021年青海省数据概述大纲 2021年青海省数据概述大纲 1、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简洁有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧） 有向图推断回路要比无向图简单。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前消失顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。void print(

2、int v,int start ) /输出从顶点start开头的回路。for(i=1;i=n;i+)if(gvi!=0 visitedi=1 ) /若存在边（v,i），且顶点i的状态为1。printf(“%d”,v);if(i=start) printf(“n”); else print(i,start);break;/if/printvoid dfs(int v)visitedv=1;for(j=1;j=n;j+ )if (gvj!=0) /存在边(v,j)if (visitedj!=1) if (!visitedj) dfs(j); /ifelse cycle=1; print(j,j);

3、visitedv=2;/dfsvoid find_cycle() /推断是否有回路，有则输出邻接矩阵。visited数组为全局变量。for (i=1;i=n;i+) visitedi=0;for (i=1;i=n;i+ ) if (!visitedi) dfs(i);/find_cycle2、两棵空二叉树或仅有根结点的二叉树相像；对非空二叉树，可判左右子树是否相像，采纳递归算法。int similar(bitree p,q) /推断二叉树p和q是否相像if(p=null q=null) return (1);else if(!p q | p !q) return (0);else return

4、(similar(p-lchild,q-lchild) similar(p-rchild,q-rchild)/结束similar3、依据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。#define true 1#define false 0typedef struct nodedatatype data; struct node *llink,*rlink; *btree;void judgebst（btree t,int

5、flag）/ 推断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 if（t!=null flag） judgebst（t-llink,flag）；/ 中序遍历左子树if（pre=null）pre=t；/ 中序遍历的第一个结点不必推断else if（pre-datat-data）pre=t；/前驱指针指向当前结点elseflag=flase； /不是完全二叉树 judgebst （t-rlink,flag）；/ 中序遍历右子树/judgebst算法结束4、假设以i和o分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由i和o组成的序列，称可以操作

6、的序列为合法序 2021年青海省数据概述大纲 列，否则称为非法序列。（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(ai!=0) /当未到字符数组尾就作。switch(ai)casei: j+; break; /入栈次数增1。caseo: k+; if(kj)printf(“序列非法n”)；exit(0);i+; /不论ai是i或o，指针i均

7、后移。if(j!=k) printf(“序列非法n”)；return(false);else printf(“序列合法n”)；return(true);/算法结束。5、假设k1，kn是n个关键词，试解答：试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为k1，k2，kn时，用算法建立一棵以llink / rlink 链接表示的二叉查找树。6、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找胜利时的平均查找长度。7、对二叉树的某层上的结点进行运算，采纳队列结构按层次遍历最相宜

8、。int leafklevel(bitree bt, int k) /求二叉树bt 的第k(k1) 层上叶子结点个数if(bt=null | k1) return(0);bitree p=bt,q; /q是队列，元素是二叉树结点指针,容量足够大int front=0,rear=1,leaf=0; /front 和rear是队头和队尾指针, leaf是叶子结点数int last=1,level=1; q1=p; /last是二叉树同层最右结点的指针，level 是二叉树的层数while(front=rear)p=q+front;if(level=k !p-lchild !p-rchild) le

9、af+; /叶子结点if(p-lchild) q+rear=p-lchild; /左子女入队if(p-rchild) q+rear=p-rchild; /右子女入队if(front=last) level+; /二叉树同层最右结点已处理,层数增1last=rear; /last移到指向下层最右一元素if(levelk) return (leaf); /层数大于k 后退出运行/while /结束leafklevel8、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。9、4、void linklist_reverse(linklist l)/链表的就地逆置;

10、为简化算法,假设表长大于2p=l-next;q=p-next;s=q-next;p-next=null;while(s-next)q-next=p;p=q;q=s;s=s-next; /把l的元素逐个插入新表表头q-next=p;s-next=q;l-next=s;/linklist_reverse10、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的挨次连成一个单链表，表头 2021年青海省数据概述大纲 指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空简单度。 11、设一棵二叉树的结点结构为 (llink,info,rlin

11、k),root为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ancestor（root，p,q,r）,该算法找到p和q的最近共同祖先结点r。12、设有一组初始记录关键字序列（k1，k2，kn），要求设计一个算法能够在o(n)的时间简单度内将线性表划分成两部分，其中左半部分的每个关键字均小于ki，右半部分的每个关键字均大于等于ki。void quickpass(int r, int s, int t)int i=s, j=t, x=rs;while(ij)while (ij rjx) j=j-1; if (ij) ri=rj;i=i+1;while (ij

12、 rix) i=i+1; if (ij) rj=ri;j=j-1;ri=x;13、本题要求建立有序的循环链表。从头到尾扫描数组a，取出ai（0=in）,然后到链表中去查找值为ai的结点，若查找失败，则插入。linkedlist creat(elemtype a,int n)/由含n个数据的数组a生成循环链表，要求链表有序并且无值重复结点linkedlist h;h=(linkedlist)malloc(sizeof(lnode);/申请结点h-next=h; /形成空循环链表for(i=0;in;i+)pre=h;p=h-next;while(p!=h p-dataai)pre=p; p=p-

13、next; /查找ai的插入位置if(p=h | p-data!=ai) /重复数据不再输入s=(linkedlist)malloc(sizeof(lnode);s-data=ai; pre-next=s; s-next=p;/将结点s链入链表中/forreturn(h);算法结束14、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）15、设有一组初始记录关

14、键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。16、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找胜利时的平均查找长度。17、后序遍历最终访问根结点，即在递归算法中，根是压在栈底的。采纳后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中全部元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必定先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一帮助栈中。再连续遍历到结点q时，将栈中元素从栈顶

15、开头逐个到帮助栈中去匹配，第一个匹 2021年青海省数据概述大纲 配（即相等）的元素就是结点p 和q的最近公共祖先。 typedef structbitree t;int tag;/tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问stack;stack s,s1;/栈，容量够大bitree ancestor(bitree root,p,q,r)/求二叉树上结点p和q的最近的共同祖先结点r。top=0; bt=root;while(bt!=null |top0)while(bt!=null bt!=p bt!=q) /结点入栈s+top.t=bt; stop.tag=0;

16、 bt=bt-lchild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点for(i=1;i=top;i+) s1i=si; top1=top; /将栈s的元素转入帮助栈s1 保存if(bt=q) /找到q 结点。for(i=top;i0;i-)/；将栈中元素的树结点到s1去匹配pp=si.t;for (j=top1;j0;j-)if(s1j.t=pp) printf(“p 和q的最近共同的祖先已找到”)；return (pp);while(top!=0 stop.tag=1) top-; /退栈if (top!=0)stop.tag=1

17、;bt=stop.t-rchild; /沿右分枝向下遍历/结束while(bt!=null |top0)return(null);/、p无公共祖先/结束ancestor18、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数n2;只有非空左儿子的个数nl;只有非空右儿子的结点个数nr和叶子结点个数n0。n2、nl、nr、n0都是全局量，且在调用count(t)之前都置为0.typedef struct nodeint data; struct node *lchild,*rchild;node;int n2,nl,nr,n0;void

18、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 *stack20, *p；int top;if (b!=null) top=1; stacktop=b;while (top0) p=stacktop; top-;printf(“%d”,p-data);if (p-rchild!=null)(

19、1)_; (2)_;if (p-lchild!=null)(3)_; (4)_;19、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。20分void hospital(adjmatrix w,int n)/在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。for (k=1;k=n;k+) /求任意两顶点间的最短路径for (i=1;

20、i=n;i+)for (j=1;j=n;j+)if (wik+wkjwij) wij=wik+wkj;m=maxint; /设定m为机器内最大整数。for (i=1;i=n;i+) /求最长路径中最短的一条。s=0;for (j=1;j=n;j+) /求从某村 2021年青海省数据概述大纲 庄i（1=i=n）到其它村庄的最长路径。 if (wijs) s=wij;if (s=m) m=s; k=i;/在最长路径中，取最短的一条。m记最长路径，k记动身顶点的下标。printf(“医院应建在%d村庄，到医院距离为%dn”,i,m);/for/算法结束对以上实例模拟的过程略。各行中最大数依次是9，9

21、，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。1、对图1所示的连通网g，请用prim算法构造其最小生成树（每选取一条边画一个图）。20、设一棵二叉树的结点结构为 (llink,info,rlink),root为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ancestor（root，p,q,r）,该算法找到p和q的最近共同祖先结点r。21、设一棵树t中边的集合为(a，b)，(a，c)，(a，d)，(b，e)，(c，f)，(c，g)，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对

22、应的二叉树。22、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。23、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）24、设有一组初始记录关键字序列（k1，k2，kn），要求设计一个算法能够在o(n)的时间简单度内将线性表划分成两部分，其中左半部分的每个关键字均小于ki，右半部分的每个关键字均大于等于ki。voi

23、d quickpass(int r, int s, int t)int i=s, j=t, x=rs;while(ij)while (ij rjx) j=j-1; if (ij) ri=rj;i=i+1;while (ij rix) i=i+1; if (ij) rj=ri;j=j-1;ri=x;25、 将顶点放在两个集合v1和v2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。int bpgraph (adjmatrix g)/推断以邻接矩阵表示的图g是否是二部图。int s; /顶点向量，元素值表示其属于

24、那个集合（值1和2表示两个集合）int q;/q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。int f=0,r,visited; /f和r分别是队列的头尾指针,visited是访问数组for (i=1;i=n;i+) visitedi=0;si=0; /初始化，各顶点未确定属于那个集合q1=1; r=1; s1=1;/顶点1放入集合s1while(fr)v=q+f; if (sv=1 2021年青海省数据概述大纲 ) jh=2; else jh=1;/预备v的邻接点的集合号 if (!visitedv)visitedv=1; /确保对每一个顶点，都要检查与其邻接点不应在一个集合中for

25、 (j=1,j=n;j+)if (gvj=1)if (!sj) sj=jh; q+r=j; /邻接点入队列else if (sj=sv) return(0); /非二部图/if (!visitedv)/whilereturn(1); /是二部图算法争论 题目给的是连通无向图，若非连通，则算法要修改。26、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。#define max 100typedef struct nodechar info; struct

26、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; int k;if(n=0) return null;ptr-info=(1)_

27、;for(2)_ ; rposipos+n;rpos+) if(*rpos=*ppos) break;k=(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);27、4、void linklist_reverse(linklist l)/链表的就地逆置;为简化

28、算法,假设表长大于2p=l-next;q=p-next;s=q-next;p-next=null;while(s-next)q-next=p;p=q;q=s;s=s-next; /把l的元素逐个插入新表表头q-next=p;s-next=q;l-next=s;/linklist_reverse28、矩阵中元素按行和按列都已排序，要求查找时间简单度为o（m+n），因此不能采纳常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种状况：一是ai,jx， 这状况下向j 小的方向连续查找；二是ai,jx，下步应向i大的方向查找；三是ai,j=x，查找胜利。否则，若下标已超出范围，

29、则查找失败。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(aij=x) flag=1;break;else if (aijx) j-; else i+;if(flag) printf(“a%d%d=%d”,i,j,x); /假定x为整型.else printf(“矩阵a中无%d 元素”，x)；算法search结束。算法争论算法中查找x的路线从右上角开头，向下（当xai,j

30、）或向左（当xai,j）。向下最多是m，向左最多是n。最佳状况是在右上角比较一次胜利，最差是在左下角（ab,c），比较m+n次，故算法最差时间简单度 2021年青海省数据概述大纲 是o(m+n）。 29、假设k1，kn是n个关键词，试解答：试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为k1，k2，kn时，用算法建立一棵以llink / rlink 链接表示的二叉查找树。30、已知有向图g=(v,e)，其中v=v1,v2,v3,v4,v5,v6,v7，e=v1,v2,v1,v3,v1,v4,v2,v5,v3,v5,v3,v6,v4,v6,v5,v7,v6,v7写出g的拓扑排序

31、的结果。g拓扑排序的结果是：v1、v2、v4、v3、v5、v6、v731、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针r，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：typedef st

32、ruct int lvl; /层次序列指针，总是指向当前“根结点”在层次序列中的位置int l,h; /中序序列的下上界int f; /层次序列中当前“根结点”的双亲结点的指针int lr; / 1双亲的左子树 2双亲的右子树qnode;bitree creat(datatype in,level,int n)/由二叉树的层次序列leveln和中序序列inn生成二叉树。 n是二叉树的结点数if (n1) printf(“参数错误n”); exit(0);qnode s,q; /q是元素为qnode类型的队列，容量足够大init(q); int r=0; /r是层次序列指针，指向当前待处理的结点

33、bitree p=(bitree)malloc(sizeof(binode); /生成根结点p-data=level0; p-lchild=null; p-rchild=null; /填写该结点数据for (i=0; in; i+) /在中序序列中查找根结点，然后，左右子女信息入队列if (ini=level0) break;if (i=0) /根结点无左子树，遍历序列的1n-1是右子树p-lchild=null;s.lvl=+r; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(q,s);else if (i=n-1) /根结点无右子树，遍历序列的1n-1是

34、左子树p-rchild=null;s.lvl=+r; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(q,s);else /根结点有左子树和右子树s.lvl=+r; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(q,s);/左子树有关信息入队列s.lvl=+r; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(q,s);/右子树有关信息入队列while (!empty(q) /当队列不空，进行循环，构造二叉树的左右子树 s=delqueue(q); father=s.f;for (i=s.l; i=s.h;

35、 i+)if (ini=levels.lvl) break;p=(bitreptr)malloc(sizeof(binode); 2021年青海省数据概述大纲 /申请结点空间 p-data=levels.lvl; p-lchild=null; p-rchild=null; /填写该结点数据if (s.lr=1) father-lchild=p;else father-rchild=p； /让双亲的子女指针指向该结点if (i=s.l)p-lchild=null; /处理无左子女s.lvl=+r; s.l=i+1; s.f=p; s.lr=2; enqueue(q,s);else if (i=s

36、.h)p-rchild=null; /处理无右子女s.lvl=+r; s.h=i-1; s.f=p; s.lr=1; enqueue(q,s);elses.lvl=+r; s.h=i-1; s.f=p; s.lr=1; enqueue(q,s);/左子树有关信息入队列s.lvl=+r; s.l=i+1; s.f=p; s.lr=2; enqueue(q,s); /右子树有关信息入队列/结束while (!empty(q)return(p);/算法结束32、后序遍历最终访问根结点，即在递归算法中，根是压在栈底的。采纳后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中全部元素均为该结

37、点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必定先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一帮助栈中。再连续遍历到结点q时，将栈中元素从栈顶开头逐个到帮助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。typedef structbitree t;int tag;/tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问stack;stack s,s1;/栈，容量够大bitree ancestor(bitree root,p,q,r)/求二叉树上结点p和q的最近的共同祖先结点r。top=0; bt=root;

38、while(bt!=null |top0)while(bt!=null bt!=p bt!=q) /结点入栈s+top.t=bt; stop.tag=0; bt=bt-lchild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点for(i=1;i=top;i+) s1i=si; top1=top; /将栈s的元素转入帮助栈s1 保存if(bt=q) /找到q 结点。for(i=top;i0;i-)/；将栈中元素的树结点到s1去匹配pp=si.t;for (j=top1;j0;j-)if(s1j.t=pp) printf(“p 和q的最近共

39、同的祖先已找到”)；return (pp);while(top!=0 stop.tag=1) top-; /退栈if (top!=0)stop.tag=1;bt=stop.t-rchild; /沿右分枝向下遍历/结束while(bt!=null |top0)return(null);/、p无公共祖先/结束ancestor33、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开头，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组

40、结束，l即为所求。void platform (int b , int n)/求具有n个元素的整型数组b中最长平台的长度。l=1;k=0;j=0;i=0;while(in-1)while(in-1 bi=bi+1) i+;if(i-j+1l) 2021年青海省数据概述大纲 l=i-j+1;k=j; /局部最长平台 i+; j=i; /新平台起点printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k)；/ platform34、(1)p-rchild (2)p-lchild (3)p-lchild (4)addq(q,p-lchild) (5)addq(q,p-rchild)25.

41、 (1)t-rchild!=null (2)t-rchild!=null (3)n0+ (4)count(t-lchild) (5)count(t-rchild)26. .(1)top+ (2) stacktop=p-rchild (3)top+ (4)stacktop=p-lchild27. (1)*ppos / 根结点 （2）rpos=ipos (3)rposipos (4)ipos (5)ppos+135、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法

42、对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）36、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简洁有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）有向图推断回路要比无向图简单。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前消失顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输

43、出回路了。void print(int v,int start ) /输出从顶点start开头的回路。for(i=1;i=n;i+)if(gvi!=0 visitedi=1 ) /若存在边（v,i），且顶点i的状态为1。printf(“%d”,v);if(i=start) printf(“n”); else print(i,start);break;/if/printvoid dfs(int v)visitedv=1;for(j=1;j=n;j+ )if (gvj!=0) /存在边(v,j)if (visitedj!=1) if (!visitedj) dfs(j); /ifelse cycl

44、e=1; print(j,j);visitedv=2;/dfsvoid find_cycle() /推断是否有回路，有则输出邻接矩阵。visited数组为全局变量。for (i=1;i=n;i+) visitedi=0;for (i=1;i=n;i+ ) if (!visitedi) dfs(i);/find_cycle37、题目中要求矩阵两行元素的平均值按递增挨次排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，留意在排序时若有元素移动，则与之相应的行中各元素也必需做相应变动。void t

45、ranslation（float *matrix，int n）/本算法对nn的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。int i,j,k,l；float sum 2021年青海省数据概述大纲 ，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+) /用选择法

46、对数组p进行排序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;jn;j+) /交换两行中对应元素.sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;sum=pi; pi=pk; pk=sum; /交换一维数组中元素之和./if/for ifre

47、e(p); /释放p数组./ translation算法分析 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可削减比较次数,但数据移动会增多.算法时间简单度为o(n2).38、在有向图g中，假如r到g中的每个结点都有路径可达，则称结点r为g的根结点。编写一个算法完成下列功能：（1）建立有向图g的邻接表存储结构；（2）推断有向图g是否有根，若有，则打印出全部根结点的值。39、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找胜利时的平均查找长度。40、对一般二

48、叉树，仅依据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，依据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。void pretopost(elemtype pre ,post,int l1,h1,l2,h2)/将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最终结点的下标。if(h1=l1)posth2=prel1; /根结点half=(h1-l1)/2; /左或右子树的结点数pretopost(pre,post,l1+1,l1+half,l2,l2+half-1) /将左子树先序序

49、列转为后序序列pretopost(pre,post,l1+half+1,h1,l2+half,h2-1) /将右子树先序序列转为后序序列 /pretopost32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最终叶子结点的rchild为空。linkedlist head,pre=null; /全局变量linkedlist inorder(bitree bt)/中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为headif(bt)inorder(bt

50、-lchild); /中序遍历左子树if(bt-lchi 2021年青海省数据概述大纲 ld=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和pre,栈空间简单度o(n)41、矩阵中元素按行和按列都已排序，要求查找时间简单度为o（m+n），因此不能采

51、纳常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种状况：一是ai,jx， 这状况下向j 小的方向连续查找；二是ai,jx，下步应向i大的方向查找；三是ai,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(aij=x) flag=1;break;else if (aijx) j-; else i+;if(flag) printf(“a%d%d=%d”,i,j,x); /假定x为整型.else printf(“矩阵a中无%d 元素”，x)；算法search结束。算法争论算法中查找x的路线从右上角开头，向下（当xai,j）或向左（当xai,j）。向下最多是m，向左最多是n。最佳状况是在右上角比较一次胜利，最差是在左下角（ab,c），比较m+n次，故算法最差时间简单度是o(m+n）。42