数据结构作业系统_第九章答案.doc

9.26 试将折半查找算法改写成递归算法。 实现下列函数：int BinSearch(SSTable s, int low, int high, KeyType k);/* Index the element which key is k */* in StaticSearchTable s. */* Return 0 if x is not found. */静态查找表的类型SSTable定义如下：typedef struct KeyType key; . . / 其他数据域 ElemType;typedef struct ElemType *elem; int length; SSTable;int BinSearch(SSTable s, int low, int high, KeyType k)/* Index the element which key is k */* in StaticSearchTable s. */* Return 0 if x is not found. */ int mid=(low+high)/2; if(lowhigh)return 0; if(s.elemmid.key=k)return mid; else if(s.elemmid.keyk)return BinSearch(s,low,mid-1,k); else return BinSearch(s,mid+1,high,k);9.31 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。实现下列函数：Status IsBSTree(BiTree t);/* 判别给定二叉树t是否为二叉排序树。*/* 若是，则返回TRUE，否则FALSE */二叉树的类型BiTree定义如下：typedef struct KeyType key; . . / 其他数据域 ElemType;typedef struct BiTNode ElemType data; BiTNode *lchild,*rchild;BiTNode, *BiTree;Status IsBSTree(BiTree t)/* 判别给定二叉树t是否为二叉排序树。*/* 若是，则返回TRUE，否则FALSE */ KeyType k; if(t=NULL)return TRUE; k=t-data.key; if(t-lchild=NULL&t-rchild=NULL)return TRUE; if(t-lchild!=NULL&t-rchild!=NULL) if(kt-lchild-data.key&krchild-data.key) if(IsBSTree(t-lchild)&IsBSTree(t-rchild) return TRUE; return FALSE; if(t-lchild!=NULL&kt-lchild-data.key) if(IsBSTree(t-lchild)return TRUE; if(t-rchild!=NULL&krchild-data.key) if(IsBSTree(t-rchild)return TRUE; return FALSE;9.33 编写递归算法，从大到小输出给定二叉排序树中所有关键字不小于x的数据元素。要求你的算法的时间复杂度为O(log2n+m)，其中n为排序树中所含结点数，m为输出的关键字个数。实现下列函数：void OrderOut(BiTree t, KeyType x, void(*visit)(TElemType);/* Output is to use visit(t-data); */二叉树的类型BiTree定义如下：typedef struct KeyType key; . . / 其他数据域 ElemType;typedef struct BiTNode ElemType data; BiTNode *lchild,*rchild;BiTNode, *BiTree;void OrderOut(BiTree t, KeyType x, void(*visit)(TElemType)/* Output is to use visit(t-data); */ if(t=NULL)return; OrderOut(t-rchild,x,visit); if(t-data.key=x) visit(t-data); OrderOut(t-lchild,x,visit); 9.44 已知某哈希表的装载因子小于1，哈希函数H(key)为关键字(标识符)的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。实现下列函数：void PrintKeys(HashTable ht, void(*print)(StrKeyType);/* 依题意用print输出关键字 */哈希表的类型HashTable定义如下：#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1typedef char StrKeyType4;typedef struct StrKeyType key; void *any; HElemType;int hashsize = 7,11,17,23,29,37,47 ;typedef struct HElemType elemMAXLEN; int count; int sizeindex; HashTable;void PrintKeys(HashTable ht, void(*print)(StrKeyType)/* 依题意用print输出关键字 */ int n,i,size; char c; size=hashsizeht.sizeindex; for(c=A;cnext) p = p-next; return SUCCESS; else return UNSUCCESS;int BuildHashTab(ChainHashTab &H, int n, HKeyType es) /* 直接调用下列函数 */* 哈希函数： */* int Hash(ChainHashTab H, HKeyType k); */* 冲突处理函数： */* int Collision(ChainHashTab H, HLink &p); */ int i=0,l,flag; HLink p,node; while(esi!=0) l=Hash(H,esi); node=(HLink)malloc(sizeof(HNode); node-data=esi; node-next=NULL; i+; if(H.eleml=NULL)H.eleml=node; els