《2022年青海数据库入门入门 .pdf》由会员分享，可在线阅读，更多相关《2022年青海数据库入门入门 .pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、青海省数据库入门入门名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 2 作者：日期：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 3 1、编程实现单链表的就地逆置。23在数组 A1.n中有 n 个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小
2、到大排列，重复的数据在链中只保存一个. 2、二路插入排序是将待排关键字序列r1.n中关键字分二路分别按序插入到辅助向量d1.n前半部和后半部（注: 向量 d 可视为循环表） ，其原则为，先将rl赋给 d1 ，再从r2 记录开始分二路插入。编写实现二路插入排序算法。3、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info ，另一个是指向下一个结点的指针域next 。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得 info域相等的结点只保留一个。#include typedef char datatype; typedef struct node datatype da
3、ta; struct node * next; listnode; typedef listnode* linklist; /*-*/ /* 删除单链表中重复的结点 */ /*-*/ linklist deletelist(linklist head) listnode *p,*s,*q; p=head-next; while(p) s=p; q=p-next; while(q) if(q-data=p-data) s-next=q-next;free(q); q=s-next; else s=q; /*找与 P结点值相同的结点*/ q=q-next; p=p-next; return hea
4、d; 4、编写一个过程， 对一个 nn 矩阵， 通过行变换， 使其每行元素的平均值按递增顺序排列。5、约瑟夫环问题（Josephus 问题）是指编号为1、2、， n 的 n（n0）个人按顺时针方向围坐成一圈，现从第s 个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - -
5、 - - - 4 #include typedef int datatype; typedef struct node datatype data; 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-
6、next!=k1) /*当循环链表中的结点个数大于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=);
7、scanf(%d,&n); printf(s=); scanf(%d,&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、数组 A和 B的元素分别有序，欲将两数组合并到C数组， 使 C仍有序， 应将 A和
8、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+ else ck+=bj-; while(i=0) ck+=bj-; 算法结束4、要求二叉树按二叉链表形式存储。15 分（1）写一个建立二叉树的算法。（2）写一个
9、判别给定的二叉树是否是完全二叉树的算法。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(“输入错误” ) ；return(bt); /结束 BiTree int JudgeComplete(BiTree bt) /判断二叉
10、树是否是完全二叉树, 如是，返回1，否则，返回 0 int tag=0; BiTree p=bt, Q; / Q是队列，元素是二叉树结点指针，容量足够大if(p=null) return (1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 6 QueueInit(Q); QueueIn(Q,p); /初始化队列，根结点指针入队while (!QueueEmpty(Q) p=QueueOut(Q); /出队 if (p-lc
11、hild & !tag) QueueIn(Q,p-lchild); /左子女入队 else if (p-lchild) return 0; /前边已有结点为空，本结点不空 else tag=1; /首次出现结点为空 if (p-rchild & !tag) QueueIn(Q,p-rchild); /右子女入队 else if (p-rchild) return 0; else tag=1; /while return 1; /JudgeComplete 7、 连通图的生成树包括图中的全部n 个顶点和足以使图连通的n-1 条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排
12、序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1 条边为止。 void SpnTree (AdjList g) /用“破圈法”求解带权连通无向图的一棵最小代价生成树。typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( %d%d,&e,&n) ; /输入边数和顶点数。 for (i=1;i=e;i+) /输入 e 条边：顶点，权值。 scanf(%d%d%d ,&edgei.i ,&edgei.j ,&edgei.w); fo
13、r (i=2;i=e;i+) /按边上的权值大小，对边进行逆序排序。 edge0=edgei; j=i-1; while (edgej.w=n) /破圈，直到边数e=n-1. if (connect(k) /删除第 k 条边若仍连通。 edgek.w=0; eg-; /测试下一条边edgek ，权值置 0 表示该边被删除k+; /下条边 /while /算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，8、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后， 到二叉树的中序序列中，查到该结点， 该结点将二叉树分为“左根
14、右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：typedef struct int lvl; /层次序列指针，总是指向当前“根结点”在层次序列中的位置名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -
15、 第 6 页，共 8 页 - - - - - - - - - 7 int l,h; /中序序列的下上界int f; /层次序列中当前“根结点”的双亲结点的指针int lr; / 1双亲的左子树 2 双亲的右子树qnode; BiTree Creat(datatype in,level,int n) / 由二叉树的层次序列leveln和中序序列inn生成二叉树。 n 是二叉树的结点数if (ndata=level0; p-lchild=null; p-rchild=null; /填写该结点数据for (i=0; ilchild=null; s.lvl=+R; s.l=i+1; s.h=n-1;
16、s.f=p; s.lr=2; enqueue(Q,s); else if (i=n-1) /根结点无右子树，遍历序列的1n-1 是左子树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)
17、 /当队列不空，进行循环，构造二叉树的左右子树 s=delqueue(Q); father=s.f; for (i=s.l; idata=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.h) p-rchild=null; /处
18、理无右子女 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); /右子树有关信息入队列名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 8 /结束 while (!em
19、pty(Q) return(p); /算法结束9、假设以 I 和 O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I 和 O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）（1）下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通过对（ 1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false （假定被判定的操作序列已存入一维数组中）。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -