发布时间 : 星期日 文章数据结构 - C语言描述课后答案更新完毕开始阅读926f896627d3240c8447ef1b
8.6 试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表的平均查找长度。
（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN） [提示]：（1）由装填因子求出表长，（2）可利用字母序号设计哈希函数， （3）确定解决冲突的方法。
8.7 试编写利用折半查找确定记录所在块的分块查找算法。
8.8 试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。
[提示]：检验中序遍历序列是否递增有序？
[方法1]：用非递归中序遍历算法，设双指针pre, p 一旦pre->data > p->data 则返回假
[方法2]：用递归中序遍历算法，设全局指针pre，（参中序线索化算法） 一旦pre->data > p->data 则返回假 [方法3]：用递归（中序或后序）算法
（1）空树是（2）单根树是（3）左递归真（4）右递归真 （5）左子树的右端小于根（6）右子树的左端大于根
int last=0,flag=1;
int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0 {
if(T->lchild&&flag) Is_BSTree(T->lchild);
if(T->data
if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree
8.9 编写算法，求出指定结点在给定的二叉排序树中所在的层数。
8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结点A、B中，A是B的祖先，则认为A是A、B的最近公共祖先）。 [提示]：
（1） 假设A<=B，
（2） 从根开始，左走或右走，直到A在左（或根），B在右（或根）。
8.11 编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。 [提示]：（1）表中已经有x，（2）表中没有x 参P. 231
8.12 已知长度为12的表：
（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。
（1） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。 （2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
（3） 按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功的平均查找长度。
[提示]：画出判定树或排序树，根据P.191 ASL定义计算平均查找长度。
8.13 含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的3阶B-树中至少有多少个非叶子结点？ [提示]：叶子结点对应空指针。
8.14 写一时间复杂度为O(log2n + m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。 [提示]：
（1） p=root
（2） 如果p->key大于、等于x，则删除p->rchild和p， （3） 左走一步，转（2）
（4） 如果p->key小于x，则反复右走， （5） 转（2）
（6） 直到p==NULL
void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间 {
if(T->rchild) Delete_NLT(T->rchild,x);
if(T->data T=T->lchild; free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T) Delete_NLT(T,x); //继续在左子树中执行算法 }//Delete_NLT 8.15 在平衡二叉排序树的每个结点中增加一个lsize域，其值为它的左子树中的结点数加1。编写一时间复杂度为O(log n)的算法，确定树中第k个结点的位置。 [提示]：先画图手工求。 （1）sum=0, （2）从当前根开始沿左链找sum + lsize<=k的最大结点a， （3）沿a的右链求sum=sum + lsize，直到结点b，sum + lsize(b)>=k 重复（2）、（3），直到sum=k typedef struct { int data; int bf; int lsize; //lsize域表示该结点的左子树的结点总数加1 BlcNode *lchild,*rchild; } BlcNode,*BlcTree; //含lsize域的平衡二叉排序树类型 BTNode *Locate_BlcTree(BlcTree T,int k)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针 { if(!T) return NULL; //k小于1或大于树结点总数 if(T->lsize==k) return T; //就是这个结点 else if(T->lsize>k) return Locate_BlcTree(T->lchild,k); //在左子树中寻找 else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改k的值 }//Locate_BlcTree 第九章 内部排序 9.1 以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出（前三趟）每一趟排序结束时的关键码状态： （1）直接插入排序； （2）希尔排序（增量d[1]=5）； （3）快速排序； （4）堆排序； （5）归并排序； （6）基数排序。 9.2 一组关键字码，40，27，28，12，15，50，7，采用快速排序或堆排序，写出每趟排序结果。 9.3 不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。 n=7时在最好情况下需进行多少次比较？请说明理由。 对n=7给出一个最好情况的初始排列实例。 （保证每个基准记录都是中间记录） 9.4 假设序列由n个关键字不同的记录构成，要求不经排序而从中选出关键字从大到小顺序的前k(k< 9.5 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。 9.6 编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。 [提示]：（1）参快速排序（2）“水底”、“水面”相遇时结束。 void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法 { low=0;high=n-1; //冒泡的上下界 change=1; while(low change=0; for(i=low;i a[i]<->a[i+1]; change=1; } high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(a[i] a[i]<->a[i-1]; change=1; } low++; //修改下界 }//while }//Bubble_Sort2 9.7 编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求： 采取顺序存储结构，至多使用一个记录的辅助存储空间； 算法的时间复杂度O(n)； 讨论算法中记录的最大移动次数。 [提示]：r[0]=r[1]，以0为分界值，参快速排序划分过程，但不要求对元素排序。 void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前 { low=0;high=n-1; while(low while(low while(low }//Divide 9.8试以单链表为存储结构实现简单选择排序的算法 void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法 { for(p=L;p->next->next;p=p->next) { q=p->next;x=q->data; for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点 if(r->next->data x=r->next->data; s=r; } if(s!=q) //找到了值比q->data更小的最小结点s->next {