1第三章栈、队列和数组2一、名词解释：31.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、4队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩5阵13.对称方阵14.上（下）三角矩阵6二、填空题：71.栈修改的原则是_________或称________，因此，栈又称为8________线性表。
在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。
9102.栈的基本运算至少应包括________、________、________、11________、________五种。
123.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产13生“________”。
144.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。
15165.一般地，栈和线性表类似有两种实现方法，即________实现和17________实现。
6.top=0表示________，此时作退栈运算，则产生“________”；1819top=sqstack_maxsize-1表示________，此时作进栈运算，则产生20“________”。
7.以下运算实现在顺序栈上的初始化，请在________处用适当的句2122子予以填充。
23int InitStack(SqStackTp *sq)24{ ________;25return(1);}268.以下运算实现在顺序栈上的进栈，请在________处用适当的语句27予以填充。
28Int Push(SqStackTp *sq,DataType x)29{ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} 30else{________________:31________________=x;32return(1);}3334}359.以下运算实现在顺序栈上的退栈，请在________________用适当36句子予以填充。
37Int Pop(SqStackTp *sq,DataType *x)38{if(sp->top==0){error(“下溢”);return(0);}39else{*x=________________;40________________;41return(1);}42}4310. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予44以填充。
45Int EmptyStack(SqStackTp *sq)46{if(________________) return(1);47else return(0);48}4911.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句50子予以填充。
51Int GetTop(SqStackTp *sq,DataType *x){if(________________) return(0);5253else{*x=________________;54return(1);}}555612. 以下运算实现在链栈上的初始化，请在________________处用请适当句子57予以填充。
58Void InitStacl(LstackTp *ls){ ________________;}5913.` 以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。
60Void Push（LStackTp *ls,DataType x）61{ LstackTp *p;p=malloc(sizeof(LstackTp));62________________;63p->next=ls;64________________;65}6614．以下运算实现在链栈上的退栈，请在________________处用请适当句子予67以填充。
68Int Pop(LstackTp *ls,DataType *x)69{LstackTp *p;70if(ls!=NULL){ p=ls;7172*x=________________;73ls=ls->next;________________;7475return(1)；76}else return(0);77}7815. 以下运算实现在链栈上读栈顶元素，请在________________处用请适当句79子予以填充。
Int Get Top(LstackTp *ls,DataType *x)8081{ if(ls!=NULL){ ________________;return(1);}82else return(0);}838416.必须注意，递归定义不能是“循环定义”。
为此要求任何递归定义必须同时85满足如下条件：86①被定义项在定义中的应用（即作为定义项的出现）具有________________；87②被定义项在最小“尺度”上的定义不是________________的。
8817．队列简称________________。
在队列中，新插入的结点只能添加到89________________，被删除的只能是排在________________的结点。
9018．队列以线性表为逻辑结构，至少包括________________、91________________、________________、________________ ________________、92五种基本运算。
9319．顺序队的出、入队操作会产生“________________”。
9420．以下运算实现在循环队上的初始化，请在________________处用适当句子95予以填充。
96Void InitCycQueue(CycqueueTp *sq)97{ ________________;sq->rear=0;}21. 以下运算实现在循环队上的入队列，请在________________处用请适当句9899子予以填充。
100Int EnCycQueue(CycquereTp *sq,DataType x)101{ if((sq->rear+1)%maxsize== ________________)102{error(“队满”);return(0);103else{ ________________;104________________ ________________;105return(1);106}10722. 以下运算实现在循环队上的出队列，请在________________处用适当句子108予以填充。
109Int OutCycQueue(CycquereTp *sq,DataType *x){if(sq->front== ________________){error(“队空”);return(0)；} 110111else{ ________________;112________________;return(1);113114}115}11623. 以下运算实现在循环队上判队空，请在________________处用适当句子予117以填充。
118Int EmptyCycQueue(CycqueueTp sq)119{if(________________) return(1);120else return(0);121}12224. 以下运算实现在循环队上取队头，请在________________处用适当句子予123以填充。
124Int GetHead(CycqueueTp sq,DataType *x)125{ if(sq.rear== ________________return(0);126else{ *x=sq.data[________________ ];127return(1);128}25.链队在一定范围内不会出现________________的情况。
当129130lq.front==lq.rear试，队中无元素，此时________________。
13126．以下运算实现在链队上的初始化，请在________________处用适当句子予以填充。
132133void InitQueue(QueptrTp *lp)134{ LqueueTp *p;135p=(LqueueTp *)malloc(sizeof(LqueueTp))；136________________；137lq->rear=p;138(lq->front)->next=________________;139}14027. 以下运算实现在链队上的入队列，请在________________处用适当句子予141以填充。
142Void EnQueue(QueptrTp *lq,DataType x)143{ LqueueTp *p;144p=(LqueueTp *)malloc(sizeof(LqueueTp));145________________=x;146p->next=NULL;147(lq->rear)->next=________________;________________;148149}15028. 以下运算实现在链队上的出队列，请在________________处用适当句子予以填充。
151152int OutQueue(QuetrTp *lq,DataType *x)153{ LqueueTp *s;154if(lq->front==lq->rear){erroe(“队空”)；return(0);}155else { s=(lq->front)->next;156________________=s->data;157(lq->front)->next=________________；158if(s->next==NULL) lq->rear=lq->front;159free(s);160return(1);161}162}16329. 以下运算实现在链队上判队空，请在________________处用适当句子予以164填充165int EmptyQueue(QueptrTp *lq)166{ if(________________) return(1)；else return(0);167168}16930. 以下运算实现在链队上读队头元素，请在________________处用适当句子予以填充。