栈、队列和数组自测试题.docx

PAGE

PAGE10

第三章 栈、队列和数组一、名词解释：

1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈

4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满

9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.

对称方阵14.上（下）三角矩阵二、填空题：

栈修改的原则是 或称 ，因此，栈又称为 线性表。在栈顶进行插入运算，被称为 或 ，在栈顶进行删除运算，被称为 或 。

栈的基本运算至少应包括 、 、

、 、 五种。

对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“ ”。

对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“ ”。

一般地，栈和线性表类似有两种实现方法，即

实现和 实现。

top=0 表示 ，此时作退栈运算，则产生“ ”；top=sqstack_maxsize表示 ，此时作进栈运算，则产生“ ”。

以下运算实现在顺序栈上的初始化，请在

处用适当的句子予以填充。

intInitStack(SqStackTp*sq)

{ sq-top=0 ;return(1);}

以下运算实现在顺序栈上的进栈，请在 处

用适当的语句予以填充。

IntPush(SqStackTp*sq,DataTypex)

{ if(sp-top==sqstack_maxsize-1}{error(“ 栈满”);return(0);}

else{ sp-top++; :

*(sp-top) =x;return(1);}

}

以下运算实现在顺序栈上的退栈，请在

用适当句子予以填充。

IntPop(SqStackTp*sq,DataType*x)

{if(sp-top==0){error(“下溢”);return(0);}else{*x=_*sp-top ;

sp-top-- ;

return(1);}

}

以下运算实现在顺序栈上判栈空，请在

处用适当句子予以填充。

IntEmptyStack(SqStackTp*sq)

{if( )return(1);elsereturn(0);

}

以下运算实现在顺序栈上取栈顶元素，请在

处用适当句子予以填充。

IntGetTop(SqStackTp*sq,DataType*x)

{if( sq-top==0 )return(0);else{*x= *sq-top ;

return(1);}

}

以下运算实现在链栈上的初始化，请在

处用请适当句子予以填充。

VoidInitStacl(LstackTp*ls){ls

=()malloc();_is-next=NULL ;}

` 以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。

VoidPush（LStackTp*ls,DataTypex）

{LstackTp*p;p=malloc(sizeof(LstackTp));

p-data=x; ;p-next=ls;

ls=p; ;

}

14．以下运算实现在链栈上的退栈，请在

处用请适当句子予以填充。//touIntPop(LstackTp*ls,DataType*x)

{LstackTp*p;if(ls!=NULL)

{p=ls;

*x= p-data; ;ls=ls-next;

free(p) ;return(1)；

}elsereturn(0);

}

以下运算实现在链栈上读栈顶元素，请在

处用请适当句子予以填充。

IntGetTop(LstackTp*ls,DataType*x)

{ if(ls!=NULL){ *x=_ls-data ;return

(1);}

}

else return(0);

必须注意，递归定义不能是“循环定义”。为此要求任何递归定义必须同时满足如下条件：

①被定义项在定义中的应用（即作为定义项的出现）具有 ；

②被定义项在最小“尺度”上的定义不是

的。

队列简称 。在队列中，新插入的结点只能添加到 ，被删除的只能是排在 的结点。

．队列以线性表为逻辑结构，至少包括

、 、

、

、五种基本运算。

．顺序队的出、入队操作会产生“ ”。

．以下运算实现在 循环队上的初始化 ，请在

处用适当句子予以填充。

VoidInitCycQueue(CycqueueTp*sq)

{ ;sq-rear=0;}

以下运算实现在