2014年湖南省数据理论入门

  • 格式:rtf
  • 大小:55.06 KB
  • 文档页数:1

1、根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历结点与其前驱结
点值比较,即可得出结论,为此设全局指针变量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算法结束

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、有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序
的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所
有待排序的关键码互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统
计表中有多少个记录的关键码比该记录的关键码小,假设针对某一个记录,统计出的计数值
为c,那么,这个记录在新的有序表中的合适的存放位置即为c。
(1) (3分)给出适用于计数排序的数据表定义;
(2) (7分)使用Pascal或C语言编写实现计数排序的算法;
(3) (4分)对于有n个记录的表,关键码比较次数是多少?
(4) (3分)与简单选择排序相比较,这种方法是否更好?为什么?