正确答案：while|else

9.假设一棵平衡二叉树的每个结点都表明了平衡因子b，试设计一个算法，求平衡二叉树的高度。

正确答案：int Height（BSTree t） // 求平衡二叉树t的高度 {level=0；p=t； while（p） {level++； // 树的高度增1 if（p->bf<0）p=p->rchild；//bf=-1 沿右分枝向下 //bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存储定义 else p=p->lchild； //bf>=0 沿左分枝向下 }//while return （level）；//平衡二叉树的高度 } //算法结束

10.有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。

正确答案：typedef struct node { ElemType data； struct node *prior，*next； }node，*DLinkedList； void TwoWayBubbleSort（DLinkedList la） //对存储在带头结点的双向链表la中的元素进行双向起泡排序。 {int exchange=1； // 设标记 DLinkedList p，temp，tail； head=la //双向链表头，算法过程中是向下起泡的开始结点 tail=null； //双向链表尾，算法过程中是向上起泡的开始结点 while （exchange） {p=head->next； //p是工作指针，指向当前结点 exchange=0； //假定本趟无交换 while （p->next!=tail） // 向下（右）起泡，一趟有一最大元素沉底 if （p->data>p->next->data） //交换两结点指针，涉及6条链 {temp=p->next； exchange=1；//有交换 p->next=temp->next；temp->next->prior=p //先将结点从链表上摘下 temp->next=p； p->prior->next=temp； //将temp插到p结点前 temp->prior=p->prior； p->prior=temp； } else p=p->next； //无交换，指针后移 tail=p； //准备向上起泡 p=tail->prior； while （exchange &；&； p->prior!=head） //向上（左）起泡，一趟有一最小元素冒出 if （p->dataprior->data） //交换两结点指针，涉及6条链 {temp=p->prior； exchange=1； //有交换 p->prior=temp->prior；temp->prior->next=p； //先将temp结点从链表上摘下 temp->prior=p； p->next->prior=temp； //将temp插到p结点后（右） temp->next=p->next； p->next=temp； } else p=p->prior； //无交换，指针前移 head=p； //准备向下起泡 }// while （exchange） } //算法结束

11.试以单链表为存储结构，实现简单选择排序算法

正确答案：void LinkedListSelectSort（LinkedList head） //本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换；若要交换指针，则须记下 //当前结点和最小结点的前驱指针 p=head->next； while（p!=null） {q=p->next； r=p； //设r是指向关键字最小的结点的指针 while （q!=null） {if（q->datadata） r=q； q：=q->next； } if（r!=p） r->data<-->p->data； p=p->next； }

12.m阶B-树的非叶结点至少有m/2 （m为偶数）或m/2+1（m为奇数）棵子树。