2022年安徽省数据库入门大纲

第第页2022年安徽省数据库入门大纲2022年安徽省数据库入门大纲

1、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到帮助向量d[1..n]前半部和后半部〔注:向量d可视为循环表〕，其原那么为，先将r[l]赋给d[1]，再从r[2]记录开始分二路插入。编写实现二路插入排序算法。

2、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找胜利时的平均查找长度。

3、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找胜利时的平均查找长度。

4、在有向图G中，假如r到G中的每个结点都有路径可达，那么称结点r为G的根结点。编写一个算法完成以下功能：

〔1〕．建立有向图G的邻接表存储结构；

〔2〕．判断有向图G是否有根，假设有，那么打印出全部根结点的值。

5、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。

当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。

设当n=m-1时结论成立，现证明当n=m时结论成立。

设中序序列为S1，S2，，Sm,后序序列是P1,P2,，Pm。因后序序列最末一个元素Pm是根，那么在中序序列中可找到与Pm相等的结点〔设二叉树中各结点互不相同〕Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，，Si-1是左子树的中序序列，而Si+1,Si+2,,Sm是右子树的中序序列。

假设i=1，那么S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,那么{S2，S3，，Sm}和{P1，P2，，Pm-1}可以唯一确定右子树，从而也确定了二叉树。

假设i=m,那么Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，那么{S1，S2，，Sm-1}和{P1，P2，，Pm-1}唯一确定左子树，从而也确定了二叉树。

最末，当1im时，Si把中序序列分成{S1，S2，，Si-1}和{Si+1,Si+2,，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1,P2,,Pi-1}和{Pi,Pi+1,Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，，Si-1}和{P1，P2，，Pi-1}可唯一确定二叉树的左子树，由{Si+1,Si+2,，Sm}和

{Pi,Pi+1,，Pm-1}可唯一确定二叉树的右子树。

6、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否那么称为非法序列。〔15分〕

〔1〕A和D是合法序列，B和C是非法序列。

〔2〕设被判定的操作序列已存入一维数组A中。

intJudge(charA[])

//判断字符数组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(kj){printf(“序列非法\n”)；e*it(0);}}

2022年安徽省数据库入门大纲

i++;//不论A[i]是‘I’或‘O’，指针i均后移。}

if(j!=k){printf(“序列非法\n”)；return(false);}

else{printf(“序列合法\n”)；return(true);}

}//算法结束。

7、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V