2、队列3.1、说明线性表、栈与队的异同点。3.2、顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？3.3、设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。参考答案1.1答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。1.2答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。1.31）O（n2）2）因为所以：为O（n2）2.1答：①顺序存储时，相邻数据元素的存放地
3、址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。2.2答：首元结
4、点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。头结点head———>datalink头指针首元结点简而言之
5、，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息首元素结点是指链表中存储线性表中第一个数据元素a1的结点。3.1、相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同，堆栈用于子
6、程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。3.2、答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三：设置一个布尔变量以区别队满还是队空；浪费一个元素的空间，用于区别队满还是队空；使用一个计数器记录队列中元素个数（即队列长度）；我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是：f=rear队满标志是：f=(r+1)%N3.3可能有14种。①全进之后再出情况
7、，只有1种：4，3，2，1②进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况，有5种，2,4,3,12,3,4,12,1,3,42,1,4,32,3,1,4④进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3
