1-4章习题答案

};

ElemType *stack; int top;

void Push(struct StackSq* S, ElemType x) { }

问题1:根据此算法定义的数据结构的类型,此算法的功能是 向顺序栈中推入一个元素 。

问题2:if语句中的条件应为: B. 。 A. S.top= =S.MaxSize B. S.top= =S.MaxSize-11 算法5:

ElemType OutQueue(struct QueueSq *Q) { }

问题1、算法适用的数据结构 ? 问题2、算法功能? 问题3、算法返回?

问题4、算法有无健壮性?若有,是哪(些)语句? 问题5、算法的关键语句是哪(些)语句? 问题6、算法的时间复杂度大O()?

9

if( ) againMalloc(S); S->top++;

S->stack[S->top]=x;

if(Q->front==Q->rear) { }

Q->front=(Q->front+1)%Q->MaxSize; return Q->queue[Q->front];

printf(\exit(1);

七、分析题

1、有一个顺序存储的栈,最大存储空间MaxSize=5,栈顶指针top,现有A、B、C、D四个元素。

要求1:写出顺序存储栈结构定义。 要求2:画出 初始化状态。

要求3:画出以上四个元素依次进栈后的状态。

要求4:在要求3的基础上,画出三个元素出栈后,又有E、F二个元素进栈,画出队首、队尾指针位置。

要求5:以下是从栈中删除元素,并将被删除的元素值由函数返回的算法,请填写算法中缺失的语句。 答1:

typedef char ElemType; struct Stack{

ElemType *stack[ ]; int top; int MaxSize; }; 答2:

0

Top=-1

答3:

0

答4: 0

10

1 2 3 4

1 A 2 B 3 C 4 D

top

1 2 3 4 D 5 E 6 F 7 8 9

top

答5:

ElemType Pop(Stack& S) { }

2、有一个顺序存储的循环队列,最大存储空间为5,假设队首指针指向队首元素的前一个位置,队尾指针指向队尾元素,现队列中已有A、B、C、三个元素。 要求1:已有顺序存储队列结构的定义,请填写定义中缺失的语句。 要求2:填写出初始化算法语句。

要求3:画出经初始化后,以上三个元素依次进队后,队首、队尾指针位置。 要求4:画出以上三个元素依次出队后,元素D、E依次进队后队首、队尾指针位置。 要求5:以下是向队列中插入元素的算法,在不考虑扩充空间的前提下,请填写算法中缺失的语句或语句缺失的部分。 答1:

Typedef int ElemType; struct Queue{

int MaxSize; int front , rear; ElemType *queue; }; 答2:

void InitQueue(Queue& Q)

11

if(S.top==-1){ }

ElemType temp=S.stack[S.top]; S.top--; return temp;

cerr<<\exit(1);

{ } 答3:

0

答4: 0 E rear 答5:

void QInsert(Queue& Q, const ElemType& item) { }

八、写出下列中缀表达式的后缀表达式和栈的变化,并写出求值过程栈的变化。 1、35+6×(27-6)+6/2

2、16+5×27+8-5×4

12

Q.front = Q.rear =0 ;

1 2 A 3 B 4 C

front

rear

1 2 3 4 D

Front

int k=(Q.rear+1)%QueueMaxSize; if(k= =Q.front) { } Q.rear=k; Q.queue[k]=item;

cerr<<\exit(1);

联系客服:779662525#qq.com(#替换为@)