发布时间 : 星期日 文章数据结构练习题 第三章 栈、队列和数组 习题及答案更新完毕开始阅读
第三章 栈、队列和数组
一、名词解释：
1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵 二、填空题：
1. 栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈顶
进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。
2. 栈的基本运算至少应包括________、________、________、________、________五
种。
3. 对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。 4. 对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 5. 一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 6. top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1
表示________，此时作进栈运算，则产生“________”。
7. 以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { ________;
return(1);}
8. 以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x)
{ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x;
return(1);}
}
9. 以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x)
{if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} }
10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq)
{if(________________) return(1); else return(0); }
11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填充。
Int GetTop(SqStackTp *sq,DataType *x) {if(________________) return(0);
else{*x=________________; return(1);} }
12. 以下运算实现在链栈上的初始化，请在________________处用请适当句子予以填充。 Void InitStacl(LstackTp *ls){ ________________;}
13.` 以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。 Void Push（LStackTp *ls,DataType x）
{ LstackTp *p;p=malloc(sizeof(LstackTp)); ________________; p->next=ls;
________________; }
14．以下运算实现在链栈上的退栈，请在________________处用请适当句子予以填充。 Int Pop(LstackTp *ls,DataType *x) {LstackTp *p; if(ls!=NULL) { p=ls;
*x=________________; ls=ls->next;
________________; return(1)； }else return(0); }
15. 以下运算实现在链栈上读栈顶元素，请在________________处用请适当句子予以填充。
Int Get Top(LstackTp *ls,DataType *x)
{ if(ls!=NULL){ ________________;return(1);} else return(0); }
16.必须注意，递归定义不能是“循环定义”。为此要求任何递归定义必须同时满足如下条件：
①被定义项在定义中的应用（即作为定义项的出现）具有________________； ②被定义项在最小“尺度”上的定义不是________________的。 17．队列简称________________。在队列中，新插入的结点只能添加到________________，被删除的只能是排在________________的结点。
18．队列以线性表为逻辑结构，至少包括________________、________________、________________、________________ ________________、五种基本运算。
19．顺序队的出、入队操作会产生“________________”。 20．以下运算实现在循环队上的初始化，请在________________处用适当句子予以填充。 Void InitCycQueue(CycqueueTp *sq) { ________________;sq->rear=0;}
21. 以下运算实现在循环队上的入队列，请在________________处用请适当句子予以填充。
Int EnCycQueue(CycquereTp *sq,DataType x)
{ if((sq->rear+1)%maxsize== ________________) {error(“队满”);return(0); else{ ________________;
________________ ________________; return(1); }
22. 以下运算实现在循环队上的出队列，请在________________处用适当句子予以填充。 Int OutCycQueue(CycquereTp *sq,DataType *x)
{if(sq->front== ________________){error(“队空”);return(0)；} else{ ________________; ________________; return(1); } }
23. 以下运算实现在循环队上判队空，请在________________处用适当句子予以填充。 Int EmptyCycQueue(CycqueueTp sq)
{if(________________) return(1); else return(0); }
24. 以下运算实现在循环队上取队头，请在________________处用适当句子予以填充。 Int GetHead(CycqueueTp sq,DataType *x) { if== ________________return(0); else{ *x=[________________ ]; return(1); }
25.链队在一定范围内不会出现________________的情况。当==试，队中无元素，此时________________。
26．以下运算实现在链队上的初始化，请在________________处用适当句子予以填充。 void InitQueue(QueptrTp *lp) { LqueueTp *p;
p=(LqueueTp *)malloc(sizeof(LqueueTp))； ________________； lq->rear=p;
(lq->front)->next=________________; }
27. 以下运算实现在链队上的入队列，请在________________处用适当句子予以填充。 Void EnQueue(QueptrTp *lq,DataType x) { LqueueTp *p;
p=(LqueueTp *)malloc(sizeof(LqueueTp)); ________________=x; p->next=NULL;
(lq->rear)->next=________________; ________________;
}
28. 以下运算实现在链队上的出队列，请在________________处用适当句子予以填充。 int OutQueue(QuetrTp *lq,DataType *x) { LqueueTp *s;
if(lq->front==lq->rear){erroe(“队空”)；return(0);} else { s=(lq->front)->next;
________________=s->data;
(lq->front)->next=________________； if(s->next==NULL) lq->rear=lq->front; free(s); return(1); } }
29. 以下运算实现在链队上判队空，请在________________处用适当句子予以填充 int EmptyQueue(QueptrTp *lq)
{ if(________________) return(1)； else return(0); }
30. 以下运算实现在链队上读队头元素，请在________________处用适当句子予以填充。 Int GetHead(QueptrTp lq,DataType *x) { LqueueTp *p; if== return(0);
else{________________;
________________ =p->data; return(1); } }
31．一般地，一个n维数组可视为其数据元素为___________维数组的线性表。数组通常只有___________和___________两种基本运算。
32，通常采用___________存储结构来存放数组 。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。C语言数组用的是以___________序为主序的存储方法；FORTRAN语言用的是以___________序为主序的存储方法
33．需要压缩存储的矩阵可分为___________矩阵和___________矩阵两种。
34．对称方阵中有近半的元素重复， 若为每一对元素只分配一个存储空间 ，则可将n2个元素压缩存储到___________个元素的存储空间中。
35．假设以一维数组M（1：n(n+1)/2）作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角（包括对角线）中的元素，数组M和矩阵A间对应的关系为___________。
36．上三角矩阵中，主对角线上的第t行(1<=t<=n)有___________个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的前i-1行共有___________个元素，在第i行上， aij是该行的第___________个元素，M[k]和aij的对应关系是。 当i>j时，aij=c,c存放在M[___________]中。
37．下三角矩阵的存储和对称矩阵类似。M[K]和aij的对应关系是___________。 38．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，