2012贵州省数据库入门入门

1、给出折半查找的递归算法，并给出算法时间复杂度性分析。 2、#define maxsize 栈空间容量

void InOutS(int s[maxsize])

//s是元素为整数的栈，本算法进行入栈和退栈操作。

{int top=0; //top为栈顶指针，定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。 {scanf(“%d”,&x); //从键盘读入整数序列。

if(x!=-1) // 读入的整数不等于-1时入栈。 if(top==maxsize-1){printf(“栈满\\n”);exit(0);} else s[++top]=x; //x入栈。

else //读入的整数等于-1时退栈。

{if(top==0){printf(“栈空\\n”);exit(0);}

else printf(“出栈元素是%d\\n”,s[top--])；} }

}//算法结 3、编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。 4、设有一个数组中存放了一个无序的关键序列K1、K2、?、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。

51. 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请编写出算法并简要说明算法思想。

5、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。 6、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。 #define true 1 #define false 0 typedef struct node

{datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST（BTree t,int flag）

// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if（t!=null && flag）

{ Judgebst（t->llink,flag）；// 中序遍历左子树

if（pre==null）pre=t；// 中序遍历的第一个结点不必判断

else if（pre->datadata）pre=t；//前驱指针指向当前结点 else{flag=flase；} //不是完全二叉树 Judgebst （t->rlink,flag）；// 中序遍历右子树 }//JudgeBST算法结束

7、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序

的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 (1) (3分)给出适用于计数排序的数据表定义;

(2) (7分)使用Pascal或C语言编写实现计数排序的算法； (3) (4分)对于有n个记录的表，关键码比较次数是多少?

(4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?

本文来源：https://www.bwwdw.com/article/clk7.html