（2） （3） h = log2 ( n+1 ) 或 h = [ log2 n ] + 1 （方括号表示向下取整） O ( log2 ( n+1 ) ) 或 O ( log2 n )
算法题：
1. 设计一个算法,利用栈的基本运算返回指定栈中的栈底元素。 答：status Getbase(Aqstacks,int &e) {
If(s.top==s.base) Error(‘no data’) else
e =*s.base; return e; }
2. 利用一维数组A可以对N个整数进行排序，其中一种排序的算法的处理思想是：将N
个整数作为数组A的N个元素的值，每次（即第一次）从元素A[1]~A[N]中挑出最小的一个元素A[K]（1<=K<=N），然后将A[K]与A[1]换位，这样反复N次完成排序，编写实现上述算法的函数？ 答:SelectSort(sqlist &A) {
For(i=1;KA.length;++i); {
J=selectminkey(A,i); If(i=J)A.R[i]<-->A.R[J]; }
}//selectsort
3. 设计一个算法,利用栈的基本运算将指定栈中的内容进行逆转。 答：status Nizhuan(sqstacks, int a, int b, int t) {
If(s.top==s.base) error(‘no data’);
for(i=0;i a=*--top; b=*s.base; t=b;b=a;a=t; s.base++; } } 4. 在栈项指针为HS的链栈中，编写算法计算该链栈中结点个数？ 答：status sum(linked stack HS.elemtype N) { Int N=0; While(HS!=NULL); {N++; HS=HS->next; } Return(N); } 5. 修改直接选择排序,每趟从无序区中选择最大元素与当前元素进行交换.? 答：selectSort (SqList &A ) { for (i =1; i< A.length; ++i) { j =SelectMaxkey(A,i ); if (i ! = j) A.r[i]<--> A.r[j]; } }// SelectSort 6. 用不带头结点的单链表存储链栈,设计进栈和出栈的算法。 答：（1）入栈操作 【单个链栈的入栈操作】 int pushLstack(slStacktype *top,Elemtype x) {//将元素x压入链栈top中 slStacktype *p; if((p=(slStacktype*)malloc(sizeof(slStacktype)))==NULL) return FALSE; //申请一个结点 p->data=x; p->next=top; top=p; return TRUE; } （2）出栈操作 【单个链栈的出栈操作】 Elemtype popLstack(slStacktype *top) {//从链栈top中删除栈顶元素 slStacktype *p; Elemtype x; if (top= =NULL) return NULL; //空栈 p=top; top=top->next; x=p->data; free(p); return x; }