文档库

最新最全的文档下载
当前位置:文档库 > 2012年陕西省C#语言章程

2012年陕西省C#语言章程

1、假设K1,…,Kn是n个关键词,试解答:

试用二叉查找树的插入算法建立一棵二叉查找树,即当关键词的插入次序为K1,K2,…,Kn 时,用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。

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

3、矩阵中元素按行和按列都已排序,要求查找时间复杂度为O(m+n),因此不能采用常规的二层循环的查找。可以先从右上角(i=a,j=d)元素与x比较,只有三种情况:一是A[i,j]>x,这情况下向j 小的方向继续查找;二是A[i,j]

void search(datatype A[ ][ ], int a,b,c,d, datatype x)

//n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中.

{i=a; j=d; flag=0; //flag是成功查到x的标志

while(i<=b && j>=c)

if(A[i][j]==x) {flag=1;break;}

else if (A[i][j]>x) j--; else i++;

if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型.

else printf(“矩阵A中无%d 元素”,x);

}算法search结束。

[算法讨论]算法中查找x的路线从右上角开始,向下(当x>A[i,j])或向左(当x