(083%l1=2……2 (463)%ll=12……6 01*3)%ll=0…3 31*3)%11=8…5 (66*3)%ll=9…0 2264830546「3n工 4,7 五、算法设计题(4中选3,第1题7分必选,其余每题8分,共23分) 1.已知1个元素的有序表为(0513192137566475808892),请写出折半查找的算 法程序,查找关键字为key的数据元素(建议上机调试) 解:折半查找的C程序有很多参考资料,注意此题要求是整型量。 折半查找的一个递归算法如下,形式非常简洁1 nt search bin recursive( SSTable st, int key, int low, int high)∥折半查找的递归算法 if( low>high) return0,∥查找不到时返回0 mid=(low+high)/2 if(ST elem mid]. key==key) return mid else if(STelem(mid). key>key) eturn Search Bin Recursive(ST, key, low, mid-1); else return Search Bin Recursive(ST, key, mid+1, high) i//Search Bin Recursive 2.【严题集93④】试写一个判别给定二叉树是否为二叉排序树的算法,设此二叉树以二叉链表作存储结 构。且树中结点的关键字均不同。 解:注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别:“若一棵非空的二叉树其 左、右子树均为二叉排序树,且左子树的根的值小于根结点的值,又根结点的值不大于右子树的根的值 则是二叉排序树 (刘注:即不能只判断左右孩子的情况,还要判断左右孩子与双亲甚至根结点的比值也要遵循(左小右大) 原则)。 若要采用递归算法,建议您采用如下的函数首部: bool BisortTree( BiTree t, BiTree&PRE),其中PRE为指向当前访问结点的前驱的指针。 (或者直接存储前驱的数值,随时与当前根结点比较) 个漂亮的算法设计如下 ∥last是全局变量,用来记录前驱结点值,只要每个结点都比前驱大就行。 int Is Bs Tree( Bitree T) ∥判断二叉树T是否二叉排序树,是则返回1,否则返回0 if(T->lchild&&flag) Is BSTree(T->lchild) if(l>data<las)fag=0,∥与其中序前驱相比较,nag=0表示当前结点比直接前驱小,则立即返回7 (08*3)%11=2……2 (46*3)%11=12……6 (30*3)%11=8……2 (01*3)%11=0……3 (31*3)%11=8……5 (66*3)%11=9……0 22 66 41 8 30 53 46 1 31 0 1 2 3 4 5 6 7 8 9 10 1 3 4，7 五、算法设计题（4 中选 3，第 1 题 7 分必选，其余每题 8 分，共 23 分） 1. 已知 11 个元素的有序表为（05 13 19 21 37 56 64 75 80 88 92）, 请写出折半查找的算 法程序，查找关键字为 key 的数据元素 (建议上机调试)。 解：折半查找的 C 程序有很多参考资料，注意此题要求是整型量。 折半查找的一个递归算法如下，形式非常简洁！ int Search_Bin_Recursive(SSTable ST, int key, int low, int high) //折半查找的递归算法 { if(low>high) return 0; //查找不到时返回 0 mid=(low+high)/2; if(ST.elem[mid].key= =key) return mid; else if(ST.elem[mid].key>key) return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); } }//Search_Bin_Recursive 2. 【严题集 9.31④】试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结 构。且树中结点的关键字均不同。 解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其 左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值， 则是二叉排序树” （刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大） 原则）。 若要采用递归算法，建议您采用如下的函数首部： bool BisortTree(BiTree T, BiTree&PRE)，其中 PRE 为指向当前访问结点的前驱的指针。 （或者直接存储前驱的数值，随时与当前根结点比较） 一个漂亮的算法设计如下： int last=0, flag=1; // last 是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。 int Is_BSTree(Bitree T) //判断二叉树 T 是否二叉排序树，是则返回 1，否则返回 0 { if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->data<last) flag=0; //与其中序前驱相比较, flag=0 表示当前结点比直接前驱小，则立即返回