第三章  栈、队列和数组

一、名词解释：

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(sq.rear== ________________return(0);

      else{ *x=sq.data[________________ ];

             return(1);

     }

25.链队在一定范围内不会出现________________的情况。当lq.front==lq.rear试，队中无元素，此时________________。

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(lq.rear==lq.front) 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行(1next=Top;Top=Top->next

24.从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤为（    ）

①x=Top->data;Top=Top->next            ②Top=Top->next;x=Top->data

③x=Top;Top=Top->next                  ④  x=Top->data           

25.在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（    ）

①f->next=c;f=s                         ②r->next=s;r=s

③s->next=r;r=s                         ④ s->next=f;f=s

26常对数组进行的两种基本操作是                                      （    ）

①建立与删除   ② 索引与修改         ③ 查找与修改        ④ 查找与索引

27．链栈与顺序栈相比，有一个比较明显的优点即                         （    ）

①插入操作更方便           ② 通常不会出现栈满的情况

③不会出现栈空的情况       ④ 删除操作更方便

28．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点                                        （    ）

①正确                ②错误

29。二为数组M[i,j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从O到4，列下标j的范围从O到5。M按行存储时元素M[3,5] 的起始地址与M按列存储时元素(    )的起始地址相同。

①M [2,4]          ② M[3,4]          ③M[3,5]          ④M[4,4]

30.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是               （    ）

  ① e d c b a          ②d e c b a          ③d c e a b       ④a b c d e

31.一个队列的人列序是1，2，3，4，则队列的输出系列是                   （    ）

  ① 4，3，2，1        ② 1，2，3，4，       ③1，4，3，2     ④ 3，2，4，1

32．设计一个判别表达式中左、右括号是否配对出线的算法，采用（     ）数据结构最佳。

  ①线性标的顺序存储结构             ②栈

③ 队列                            ④ 线性表的链式存储结构       

33．若已知一个栈的输入序列为1，2，3，...,n,其输出序列为P1、P2、...Pn。若p1=n,则P1为

  ①i           ②n=i     ③ n-i+1           ④ 不确定

34．以下说法正确的是

①顺序队和循环队的队满和队空判断条件是一样的

②栈可以作为实现过程调用的一种数据结构

③插人和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用

④在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件front=rear

35. 以下说法正确的是

①数组是同类型值的集合

②数组是一组相继的内存单元

③数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的

④使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间

四、简答及应用

1．简述顺序栈的类型定义。

2．简述链栈的类型定义。

3．简述顺序队列、循环队列的类型定义。

4．简述链队的类型定义。

5，写出基于三元组的稀疏矩阵的类型说明。

6．对于循环队列，试写出求队列长度的算法。

7．设有编号为t，2，3，4的四辆列车。顺序进入一个占世界共的展台，试写出这四两列车开出车站的所有可能的顺序。

8设有上三角矩阵(aij)n*n,将其上三角元素逐行存于数组B(1:m)中（m充分大），使得B[k]=aij,且k=f1(i)+f2(j)+c。是推导出函数f1,f2和常数c(要求f1和f2中不含常数项)。

9．设有三对角矩阵（aij）n*n,将其三条对角线上的元素逐行存于数组B(1:3n-2)中，使得B[k]=aij,求：

（1）       用i、j表示k的下标变换公式；

（2）       用k表示i、j的下标变换公式.

10.阅读下列程序，写出程序的运行结果。

# define sqstack_maxsize             40

typedef  struct sqstack

{ char data[sqstack_maxsize];

  int  top;

} SqStackTp;

main()

{ SqStackTp  sq;

  int   i;

  char  ch;

  InitStack(&sq);

  For(ch=’A’;chnext;

   While(p!=NULL)

{  Push(&lsdata);

   p=p->next;}

   p=head->next;

   While(! EmptyStack(&ls))

   {  Pop(&l,&x);  p->data=x;

  p=p-next;}

}

12，对下列函数，按照《数据结构导论》课本的图3-5失利，画出调用f(5)是引起的工作栈状态变化情况。

Int f(int I)

{  if(n==1) return(10);

     else    return(f(I-1)+2);

}

五、算法设计

1.某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类，

上渡船的有如下规定：同类车先到先上船；且每上4辆客车，才允许上一辆货车；若等待客车不足4辆，则以火车代替，若无货车等待允许客车都上船。试写一算法模拟渡口管理。

可以在一个数组中保存两个栈：一个栈以数组的第一个单元作为栈底，另一个栈以数组的最后一个单元作为栈底（如下图所示）。设S是其中一个占，是分别编写过程push(S,X)(元素X入栈)， 出栈pop(S)和取栈顶元素Top(S).题示：设其中一个栈为0，另一栈为1。

 0       1        2                               M-1          M         M+1

   ······

栈0底                       栈0顶   栈1顶                            栈1底

3．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的初始化队列、入队列和出队列算法。

4．假设以数组cycque[m](假设数组范围在0..m)存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法。

5．编写算法:按行优先存储顺序，将稀疏矩阵转换为三元组的表示形式。

6．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。

7．假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号与“{”和“}”，且这三种括号可按任意的次序嵌套试用，如（.. .[.. .{.. .}.. .[.. .].. .].. .(  .. .[.. .].. .)。试利用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法（可设表达式已存入字符型数组中）。

8．已知Ackerman函数定义如下：

akm(m,n)=

试写出递归算法。

9．设函数f(m,n)按下式定义（ m,n为）0的整数）

f(m,n)=

试写出计算函数的递归过程。

10．设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为w1,w2,.. .，wn.问能否从这n件物品中选择若干件放入此背包，使得放入的重量之和正好为S.如果存在一种符合上述要求的选择，则称此背包问题有解（或承接为真），否则此问题无解（或结为假），试用递归和非递归两种方法设计此背包问题的算法。

11．借助栈(可用栈的基本运算)来实现单链表的逆置运算。