《广东省数据结构考试基础》由会员分享,可在线阅读,更多相关《广东省数据结构考试基础(11页珍藏版)》请在金锄头文库上搜索。
1、、编写一种过程,对一种nn矩阵,通过行变换,使其每行元素的平均值按递增顺序排列。2、 连通图的生成树涉及图中的所有n个顶点和足以使图连通的n1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条目前权值最大的边后,就去测试图与否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩-1条边为止。 void Spnree (AdjLitg) /用“破圈法”求解带权连通无向图的一棵最小代价生成树。tpdef uct it i,j,wnode; /设顶点信息就是顶点编号,权是整型数 node edge; scanf( d%,&e,&n)
2、 ; /输入边数和顶点数。 for (i=1;=e;i+) /输入条边:顶点,权值。 caf(d%d%d ,&egei. ,edij ,&edgeiw); (i;i=e;i+) /按边上的权值大小,对边进行逆序排序。 edge0=gei; =i1;whil(edgej.w) /破圈,直到边数e=n-1. i (connet(k)) /删除第k条边若仍连通。 dgek.w0; g-; /测试下一条边egek,权值置0表达该边被删除k+; /下条边 /whi /算法结束。 connect()是测试图与否连通的函数,可用图的遍历实现,3、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓
3、“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一环节,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的具体算法,并用程序实现你所给出的算法。注:圈就是回路。4、证明由二叉树的中序序列和后序序列,也可以唯一拟定一棵二叉树。29 试找出满足下列条件的二叉树1)先序序列与后序序列相似 )中序序列与后序序列相似3)先序序列与中序序列相似 4)中序序列与层次遍历序列相似 、两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树,可判左右子树与否相似,采用递归算法。 t mila(BiTreep,q) /判断二叉树p和q与否相似 i(=null& q=nul) re
4、turn (1);lse i(!p& q | & !q) etur (0); ese retun(Siia(p-lcd,qlchd) & Silar(pchid,q-rchil)/结束Simiar6、 连通图的生成树涉及图中的所有n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条目前权值最大的边后,就去测试图与否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n1条边为止。 vodnTree (Ajs ) /用“破圈法”求解带权连通无向图的一棵最小代价生成树。tedef s nt i,j,wn
5、e; /设顶点信息就是顶点编号,权是整型数 node ede; scan( %d,&e,&) ; /输入边数和顶点数。 fr(i1;ie;i) /输入条边:顶点,权值。 anf(%ddd ,&edgei.i ,&edgei.j ,&dgei.); or (i=2;e;i+) /按边上的权值大小,对边进行逆序排序。 edge0=dgei; ji-1;whie (edge.wn) /破圈,直到边数e1. i (connec(k)) /删除第k条边若仍连通。 edgek.w=0;e-; /测试下一条边edgek,权值置表达该边被删除; /下条边 /whil /算法结束。 conet()是测试图与否连
6、通的函数,可用图的遍历实现,7、有一种简朴的排序算法,叫做计数排序(oun sortig)。这种排序算法对一种待排序的表(用数组表达)进行排序,并将排序成果寄存到另一种新的表中。必须注意的是,表中所有待排序的核心码互不相似,计数排序算法针对表中的每个记录,扫描待排序的表一趟,登记表中有多少个记录的核心码比该记录的核心码小,假设针对某一种记录,记录出的计数值为c,那么,这个记录在新的有序表中的合适的寄存位置即为c。 (1)(3分)给出合用于计数排序的数据表定义; () (7分)使用Psal或语言编写实现计数排序的算法; (3)(4分)对于有n个记录的表,核心码比较次数是多少? (4) (3分)与
7、简朴选择排序相比较,这种措施与否更好?为什么?8、假设以I和O分别表达入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表达为仅由I和O构成的序列,称可以操作的序列为合法序列,否则称为非法序列。(5分) (1)A和D是合法序列,B和C是非法序列。 (2)设被鉴定的操作序列已存入一维数组中。 int Jdge(chr A) /判断字符数组A中的输入输出序列与否是合法序列。如是,返回te,否则返回fale。 i=0; /为下标。 j=k0; /和k分别为I和字母O的的个数。 while(i!=0) /当未到字符数组尾就作。 swich(Ai) aseI:+; beak; /入栈次数增1。
8、 caseO: k+;i(kj)pritf(“序列非法n”);exit(0); i+;/不管Ai是I或O,指针i均后移。 if(j!k)print(“序列非法n”);eturn(fas); else prinf(“序列合法”);tun(tue); /算法结束。、二叉树的层次遍历序列的第一种结点是二叉树的根。事实上,层次遍历序列中的每个结点都是“局部根”。拟定根后,到二叉树的中序序列中,查到该结点,该结点将二叉树分为“左根右”三部分。若左、右子树均有,则层顺序列根结点的背面应是左右子树的根;若中序序列中只有左子树或只有右子树,则在层顺序列的根结点后也只有左子树的根或右子树的根。这样,定义一种全局
9、变量指针R,指向层顺序列待解决元素。算法中先解决根结点,将根结点和左右子女的信息入队列。然后,在队列不空的条件下,循环解决二叉树的结点。队列中元素的数据构造定义如下:tpedef struct itvl; /层顺序列指针,总是指向目前“根结点”在层顺序列中的位置int ,; /中序序列的下上界in ; /层顺序列中目前“根结点”的双亲结点的指针int lr; / 1双亲的左子树 2双亲的右子树qnode; iTrert(datatypei,leve,in n)/由二叉树的层顺序列leveln和中序序列inn生成二叉树。n是二叉树的结点数if (nlhild=nl; prlnul; /填写该结点
10、数据f (i=0; i; +) /在中序序列中查找根结点,然后,左右子女信息入队列 f (ini=level0) reak;i (=0) /根结点无左子树,遍历序列的n-1是右子树 -lchild=nul; s.lvl=+R; s.l=i+1; shn-1; sf=p;s.l=2; equeu(Q,); ese i (i=n-1)/根结点无右子树,遍历序列的1n-1是左子树-rhldnull; .l=+R; sl=1; si-1; sf; slr=1; enqueue(,s); lse /根结点有左子树和右子树lv=+R;s.l=0; .hi-1; s.f=p; s.l=1;eneue(Q,)
11、;/左子树有关信息入队列s.lvl=+R; s.l=1;.h=n-1;sf=p;s.lr2;nuee(Q,s);/右子树有关信息入队列while (!epty(Q)) /当队列不空,进行循环,构造二叉树的左右子树 s=dee(); father=sf; for (is.l;i=s.; i+) (ini=evels.lv)bea;p(bitetr)mallo(sizeo(inode); /申请结点空间 -data=leveslvl; p-lcild=ll;pchild=null; /填写该结点数据 if (s.r=1) fater-lhild=p; le fterchid=; /让双亲的子女指针指向该结点 if (=s.l) p-lhld=null; /解决无左子女vl=+R; sl=i+1; =p; r2; enquue(Q,s); ese if (i=s