耿国华数据结构附录A样卷习题答案及B卷习题答案(3)

（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; }

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库耿国华数据结构附录A样卷习题答案及B卷习题答案(3)在线全文阅读。