循环队列数据结构与算法

⑴ 数据结构 第7讲 循环队列

                                                           数据结构 第7讲 循环队列

过了一段时间，小张再也受不了这种"起早贪黑"的有车生活。为了解决胡同停车问题，小张跑了无数次居委会，终于将挡在胡同口的建筑清除，这样住在胡同尽头的小张，就可以早早回家停在家门口，每天第一个开车上班去了。

现在胡同打通了，但仍然很窄，只能通过一辆车，但是可以从一端进，另一端出，画图：

小汽车是线性排列，而且只能从一端进，另一端出，这就是"队列"，队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作，先进先出（First In First Out，FIFO）。

进的一端称为队尾（rear），出的一端称为队头（front）。队列可以用顺序存储，也可以用链式存储。

1. 顺序队列

队列的顺序存储形式，可以用一个一维数组存储数据元素，用两个整型变量记录队头和队尾元素的下标。

顺序存储方式：

顺序队列的结构体定义：

2. 完美图解

接下来看看顺序队列的入队和出队情况：

假设现在顺序队列Q分配了6个空间，然后进行入队出队操作，过程如图所示：

(1)开始时为空队，Q.front=Q.rear，如图所示：

(2)元素 a 1进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：

(3)元素 a 2进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：

(4)元素 a 3， a 4， a 5分别按顺序进队，尾指针Q.rear依次后移，如图所示：

(5)元素 a 1出队，头指针Q.front（整型下标）后移一位，如图所示：

(6) 元素 a 2出队，头指针Q.front（整型下标）后移一位，如图所示：

(7)元素 a 6进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：

(8) 元素 a 7进队，此时尾指针Q.rear已经超过了数组的下标，无法再存储进队，但是我们发现前面明明有2个空间，却出现了队满的情况，这种情况称为"假溢出"。

那么如何解决该问题呢？

能否利用前面的空间继续存储入队呢？

试试看…～

上面第（7）步元素 a 6进队之后，尾指针Q.rear要后移一个位置，此时已经超过了数组的下标，即Q.rear+1=Maxsize（最大空间数6），那么如果前面有空闲，Q.rear可以转向前面0的位置，如图所示：

然后元素 a 7进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：

元素 a 8进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：

这时候虽然队列空间存满了，但是出现了一个大问题，队满时Q.front=Q.rear，这和队空的条件一模一样，无法区分队空还是队满，如何解决呢？有两种办法：一是设置一个标志，标记队空和队满；另一种办法是浪费一个空间，当尾指针Q.rear的下一个位置Q.front是时，就认为是队满。如图所示：

3. 循环队列

上述到达尾部又向前存储的队列称为循环队列，为了避免"假溢出"，我们通常采用 循环队列。

循环队列无论入队还是出队，队尾、队头加1后都要取模运算，例如入队后队尾后移一位：Q.rear =(Q.rear+1)%Maxsize。

为什么要%Maxsize呢？

主要是为了处理临界状态，即Q.rear向后移动一个位置Q.rear+1后，很有可能超出了数组的下标，这时它的下一个位置其实是0，如果将一维数组画成环形图，如图所示：

上图中最大空间Maxsize，当Q.rear=Maxsize-1时，(Q.rear+1)%Maxsize=0，而且Q.front=0，正好满足队满的条件：(Q.rear+1) %Maxsize= Q.front，此时为队满。

因此无论是front还是rear向后移动一个位置时，都要加1与最大空间Maxsize取模运算，处理临界问题。

总结：

队空 ：Q.front=Q.rear; // Q.rear和Q.front指向同一个位置

队满 ： (Q.rear+1) %Maxsize=Q.front; // Q.rear向后移一位正好是Q.front

入队 ：

Q.base[Q.rear]=x; //将元素放入Q.rear所指空间，

Q.rear =( Q.rear+1) %Maxsize; // Q.rear向后移一位

出队 ：

e= Q.base[Q.front]; //用变量记录Q.front所指元素，

Q.front=(Q.front+1) %Maxsize // Q. front向后移一位

循环队列中到底存了多少个元素呢？

因为队列是循环的，所以存在两种情况：

（1）Q.rear>= Q.front，如下图所示：

这种情况队列中元素个数为：Q.rear-Q.front=4-1=3。

（2）Q.rear< Q.front，如下图所示：

此时，Q.rear=4，Q.front=Maxsize-2，Q.rear-Q.front=6-Maxsize。但是我们可以看到循环队列中的元素实际上为6个，那怎么办呢？当两者之差为负数时，可以将差值+Maxsize计算元素个数，即：Q.rear-Q.front+Maxsize=6-Maxsize+Maxsize =6，元素个数为6。

那么在计算元素个数时，可以分两种情况判断：

Q.rear>= Q.front：元素个数为Q.rear-Q.front；

Q.rear<Q.front：元素个数为Q.rear-Q.front+ Maxsize；

也可以采用取模的方法把两种情况统一为一个语句：

队列中元素个数 ：(Q.rear-Q.front+Maxsize)% Maxsize

当Q.rear-Q.front为负数时，加上Maxsize再取余正好是元素个数，如(-2+6)%6=4；当Q.rear-Q.front为正数时，加上Maxsize超过了最大空间数，取余后正好是元素个数，如(3+6)%6=3。

4. 队列的基本操作

队列的基本操作包括初始化、入队、出队、取队头元素、求队列长度。

(1)初始化

bool InitQueue(SqQueue &Q)//注意使用引用参数，否则出了函数，其改变无效  

{  

        Q.base=new int[Maxsize];//分配空间  

       if(!Q.base) return false;  

        Q.front=Q.rear=0;//头指针和尾指针置为零，队列为空  

         return true;  

}  

(2)入队

bool EnQueue(SqQueue &Q,int e)//将元素e放入Q的队尾  

{  

         if((Q.rear+1)%Maxsize==Q.front) //尾指针后移一位等于头指针，表明队满  

                 return false;  

       Q.base [Q.rear]=e;//新元素插入队尾  

       Q.rear=(Q.rear+1)%Maxsize;//队尾指针后移一位  

      return true;  

}  

(3)出队

bool DeQueue(SqQueue &Q, int &e) //删除Q的队头元素，用e返回其值  

{  

    if (Q.front==Q.rear)  

          return false; //队空  

    e=Q.base[Q.front];//保存队头元素  

    Q.front=(Q.front+1)%Maxsize;//队头指针后移一位  

   return true;  

}  

(4)取队头元素

int GetHead(SqQueue Q)//返回Q的队头元素，不修改队头指针  

{  

           if (Q.front!=Q.rear) //队列非空  

                 return Q.base[Q.front];  

            return -1;  

}  

(5)循环队列的长度

int QueueLength(SqQueue Q)  

{  

      return (Q.rear-Q.front+Maxsize)%Maxsize;  

}  

⑵ python-数据结构 循环队列的实现 设计循环队列

Leet Code 原题链接
Leet Code 原题动画演示视频
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Your implementation should support the following operations:

我们仔细研究一下 Leet Code 原题动画演示视频 这一个视频，发现来判断队空和队满的条件。假定我们有两个指针，分别为头指针head和尾指针tail。

⑶ 数据结构与算法-队列

同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。

线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为 。

与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为 。

可有时想想，为什么出队列时一定要全部移动呢，如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。也就是说，队头不需要一定在下标为0的位置，

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

假设是长度为5的数组，初始状态，空队列列如图所示，front与rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4，front指针依然指向下标为0位置，而rear指针指向下标为4的位置。

出队a1、a2，则front指针指向下标为2的位置，rear不变，如图4-12-5的左图所示，再入队a5，此时front指针不变，rear指针移动到数组之外。嗯？数组之外，那将是哪里？如下图的右图所示。

假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。

所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

如果将rear的指针指向下标为0的位置，那么就不会出现指针指向不明的问题了，如下图所示。

接着入队a6，将它放置于下标为0处，rear指针指向下标为1处，如下图的左图所示。若再入队a7，则rear指针就与front指针重合，同时指向下标为2的位置，如下图的右图所示。

由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。

所以若队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1)%QueueSize==front（取模“%”的目的就是为了整合rear与front大小为一圈问题）。比如上面这个例子，QueueSize=5，上图的左图中front=0，而rear=4，(4+1)%5=0，所以此时队列满。

再比如图下图中的，front=2而rear=1。(1+1)%5=2，所以此时队列也是满的。

而对于下图，front=2而rear=0，(0+1)%5=1，1≠2，所以此时队列并没有满。

另外，当rear>front时，此时队列的长度为rear-front。

但当rear<front时，，队列长度分为两段，一段是QueueSize-front，另一段是0+rear，加在一起，队列长度为rear-front+QueueSize。因此通用的计算队列满队公式为：

单是顺序存储，若不是循环队列，算法的时间性能是不高的，但循环队列又面临着数组可能会溢出的问题，所以我们还需要研究一下不需要担心队列长度的链式存储结构。

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。

空队列时，front和rear都指向头结点。

链队列的结构为：

初始化一个空队列

入队操作时，其实就是在链表尾部插入结点，如图所示。

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点，如图所示。

对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

栈和队列也都可以通过链式存储结构来实现，实现原则上与线性表基本相同如图所示。

⑷ 数据结构—队列

队列 (queue)是一种先进先出的线性表。它只允许在表的一端进行插入，在另一端进行删除，这如同我们日常生活中的排列是一致的，最早入队的元素最早离开。

队尾 (rear)是队列中允许插入的一端， 队头 (front)是队列中允许删除的一端。

队列如同栈一样，也同样有两种存储表示，分别是顺序表示和链式表示。

和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到对列尾的元素之外，需要设置两个指针front和rear分别指示队列头元素和尾元素的位置。

队列的顺序存储结构表示如下：

为方便C语言描述起见，约定：初始化建空队列时，front=rear=0,每当插入新元素至队尾时，“尾指针增一”，每当删除头元素时，“头指针增一”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队尾元素的下一个位置。

循环对列 是将顺序队列变成一个环状的空间，用这种方法可以解决队列“假溢出”问题。

“假溢出” 是指队列实际可用空间没有占满，但是不能向队列中添加新的队尾元素，否则会出现溢出的现象的情况。

在循环队列中，头尾指针以及队列元素之间的关系不发生改变，只是在循环队列中头尾指针“依次循环增一”的操作可用模运算实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。

循环队列的基本操作算法描述：

链队是指采用链式存储结构实现的队列。通常链队用单链表来表示，一个链队显然需要两个分别指示对头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。为了操作方便，同线性表的单链表一样，为链队添加头结点，并规定头指针始终指向头结点。

链队列存储结构表示如下：

链队操作即为单链表插入和删除操作的特殊情况，只是需要进一步修改尾指针或头指针。

链队列的基本操作算法描述：

⑸ 数据结构与算法06——队列之循环队列

与栈不同，他就是现实中排队一样，讲究先来后到，即 先进先出 。

打个比方，你告诉朋友我们做地铁去西湖，你输入 " s-u-b ", 如果按照栈 先入后出后入先出 的方式，朋友会收到 b-u-s , what？有地铁，我们干嘛做两个小时的汽车？？？ 队列就可以让朋友按你输入的顺序依次收到 s-u-b 。

简单的看一下队列，是线性结构，想到什么？非常熟悉的 线性表 ，有两种存储结构， 顺序存储和链式存储 。
我们今天先讲一讲队列的顺序存储结构—— 循环队列

但是，，，如果如下图，出队到只剩最后一个元素，front和rear又都指向了一个同元素，而且仅在队尾，又要认为队列为空？不可能啊，明明最后一块存储单元还有一个元素，而且却不能继续入队新元素，超出了存储范围，如果要继续利用前面出队的空余空间，又该怎么用？

如果 我们把队列设计成下面这样：

哈哈，循环了。队尾rear指向下一个位置，而不是当前的队尾元素。

这就是循环队列的工作流程

将上面的过程做一下整理：

指定队列最大存储5个单元，方便观看

⑹ 循环队列 数据结构题 【求一完整程序 ！】编写实现该循环队列的入队和出队操作的算法。

(VC6下编译通过)
#include <stdio.h>

main()
{
int a[1000],top,tail;
int i,n=1;
do
{
switch (n)
{
case 1:top=tail=0;break;
case 2:printf("输入要插入的元素：");scanf("%d",&a[++top]);break;
case 3:if (tail<top) tail++;break;
case 4:printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n队头为： %d\n",a[top]);break;
case 5:printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");if (tail==top) printf("空队列\n"); else printf("非空队列.\n");
}
if (n!=5&&n!=4)
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
printf("队列现在状态：");
for (i=tail+1;i<=top;i++)
printf(" %d",a[i]);
if (tail==top)
printf("空队列");
printf("\n");
printf("\n1队列初始化\n2入队操作\n3出队操作\n4输出队头元素\n5判断队列是否为空\n0退出\n请输入代码：");
scanf("%d",&n);

} while (n!=0);
}

⑺ 循环队列中入队与出队算法

如果循环队列每个元素有两个指针，一个指向其前面的元素pPre，一个指向后面的元素pNext，出对和入队就是修改一下指针啊。
比如指向要出队的元素的指针是 pDel,那么出队就应该是：
pDel->pPre->pNext = pDel->pNext;
pDel->pNext->pPre = pDel->pPre;

如果循环队列每个元素只有一个指向其后元素的指针pNext，那么需要遍历整个队列，找到要出队元素的前一个元素，然后就和上面的算法差不多了。

如果经常要进行出队操作，在设计数据结构的时候还是建议每个元素使用两个指针。

⑻ 数据结构循环队列问题

网络版本是对的。你没理解“队列非空时front和rear分别指向队头元素和队尾元索”，根据这句话当队列只有一个元素时，front==rear；当队为空时，front==(rear+1)%n；进队的操作为：rear = (rear + 1) % n ;Queue[rear] = elem ;元素正好在下标为0的位置，此时front==rear==0。“队列非空时front和rear分别指向队头元素和队尾元索”意思就是front和rear都是“实指”，而你的理解中front是“虚指”，不同教材采用的方法不一样，一般题目中会说明

⑼ 求循环队列的元素个数算法，已知front 和 rear，还有容量数，怎么求队列中的循环元素个数

如果是用数组实现的 用队尾减队头再模数组长度；如果是链表 就要有个计数变量了。

front为对头指针，rear为对尾指针，n为队列最大元素个数。队列元素个数=(rear-front+1+n)%n %是求余数。

循环队列的元素个数计算公式：

如果rear<front结果是rear-front+maxsize；

如果rear>front结果是rear-front；

为了用一个表达式同时表达两者，用(rear-front+maxsize)%maxsize；

假设maxsize=10；

rear=1 front=9，那么结果是2；

rear=9 front=1，那么结果是8。

(9)循环队列数据结构与算法扩展阅读

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。

解决这个问题的方法至少有两种：

① 另设一布尔变量以区别队列的空和满；

②另一种方式就是数据结构常用的： 队满时：(rear+1)%n==front，n为队列长度（所用数组大小），由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。

队已满，但是rear（5）+1=6！=front（0），对空间长度求余，作用就在此6%6=0=front（0）。

⑽ 19年3月二级C--数据结构与算法

1.假设线性表的长度为n，则最坏情况下:

冒泡排序: 需要经过n/2遍的从前往后扫描和n/2遍从后往前扫描，需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。

快速排序: 比较次数也是n(n-1)/2。总的时间复杂度为O(n的平方)。

直接插入排序: 所需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。

希尔排序所需要比较的次数为O(n的1.5次方)。(时间复杂度小于以上三种)

堆排序: 最坏情况下，其时间复杂度为O(nlogn)。(小于O(n的平方))。

2.根据数据结构中各元素之间前后关系的复杂程度，一般数据结构分为两大类: 线性结构和非线性结构。

如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点 ②每个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。

3.算法时间复杂度与空间复杂度没有关系。

4.所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

为了能够比较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所用的计算机程序设计语言，以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。

5.同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。

算法分析的目的在于选择合适算法和改进算法。

6.堆排序在平均情况下的时间复杂度与最坏情况下的时间复杂度都是O(nlogn)。

7.二叉链表: 以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和第一个孩子下的一个兄弟结点。

  循环链表是链式存储结构，循环队列是线性存储结构。( 【×】循环链表是循环队列的链式存储结构)

  双向链表也叫双链表，是链表的一种，它的每个数据结点都有两个指针，分别指向直接后继和直接前驱，所以从双链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。

8.数据的逻辑结构由两个要素: 一是数据元素的集合，通常记为D。二是D上的关系，它反映了D中各元素之间的前后件关系，通常记为R。

即一个数据结构可以表示成B=(D,R)，其中B表示数据结构，为了反映D中各元素之间的前后件关系，一般用二元组来表示。例如，假如a与b是D中的两个数据，则二元组表示a是b的前件，b是a的后件。

  线性结构用图形表示更加直观。例如: R=｛(5,1)，(7,9)，(1,7)，(9,3)｝，结构为: 5→1→7→9→3

9.快速排序法是一种互换类的排序方法，但由于比冒泡排序的速度快，因此称为快速排序。

其基本思想是从线性表中选择一个元素设为t，将线性表后面小于t的元素移到前面，而前面大于t的元素移到后面，结果就将线性表分成了两部分，t插入到分界线的位置处，这个过程称为线性表的分割。

  简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。

  冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换，逐步将线性表变为有序。

  后两种元素的移动过程中不会产生新的逆序。

10.程序可作为算法的一种描述。

11.为了降低算法的空间复杂度，要求算法尽量采用原地工作，所谓的原地工作是指执行算法时所使用的额外空间固定。

  一个算法的空间复杂度一般是指执行这个算法所需要的内存空间，一个算法所占用的存储空间包括程序所占的空间，输入的初始数据所占的空间以及算法执行过程中所需要的额外空间。

12.能从任意一个结点开始没有重复的扫描到所有结点的数据结构是循环链表。

13.循环队列是队列的一种存储结构

14.算法的设计要求包括效率与低存储量，即要考虑算法的时间复杂度与空间复杂度。

  算法的复杂度包括时间复杂度和空间复杂度。

  时间复杂度: 是指执行算法所需要的计算工作量。

  空间复杂度: 一般是指执行这个算法所需要的内存空间。

15.栈是一种特殊的线性表。链式结构把每一个存储结点分为数据域与指针域，带链的栈可以通过指针域的变化改变原有的栈的组织数据原则; 而顺序栈的栈底指针不变，栈顶指针改变。

16.堆排序在最坏的情况下需要比较nlogn次。

  快速排序，在最坏情况下需要比较n(n-1)/2次。

  顺序查找，在最坏情况下需要比较n次。

  最坏情况下，二分查找需要log2n(小于n-1)

  在长度为n的顺序表中寻找最大项/最小项时，比较次数最少为1，最多为n-1。

17.如果一个非空的数据结构满足下列两个条件，①有且只有一个根节点 ②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称为非线性结构。

18.带链栈空的条件是 top=bottom=NULL

19.满二叉树也是完全二叉树，完全二叉树不一定是满二叉树。对于满二叉树和完全二叉树来说，可以按照程序进行顺序存储，不仅节省了空间，又能方便地确定每一个结点的父结点等于左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。

20.带链栈队头指针与队尾指针相同，且不为空时，队列元素个数为1; 若为空时，队列元素个数为0。

带链栈的栈底指针是随栈的操作而动态变化的。

21.二叉树的链式存储结构，也称为二叉链表。在二叉树中，由于每一个元素可以有两个后件，因此用于存储二叉树的存储结点的指针域有两个，所以二叉链表属于非线性结构。

22.线性表由一组元素数据元素构成，各元素的数据类型必须相同，矩阵是一个比较复杂的线性表，线性表除了插入和删除运算之外，还可以查找，排序，分解，合并等。数组是长度固定的线性表。

23.冒泡排序中，在互换两个相邻元素时，只能消除一个逆序; 快速排序及希尔排序中，一次交换可以消除多个逆序。

24.二分法检索的效率比较高，设线性表有n个元素，则最多的比较次数为log2n，最少检索次数为1。

25.循环链表的结构具有以下两个特点。一，在循环链表中，增加了一个表头结点，其数据域为任意或者根据需要来设置指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。二、循环链表中最后一个节点的指针域不是空，而是指向表头结点，即在循环链表中所有的结点指针构成一个环状链。

26.二叉树的存储结构是非线性结构，而完全二叉树是特殊形态的二叉树。采用顺序存储的完全二叉树属于非线性结构。

27.时间复杂度和计算机运行速度以及存储空间无关。

算法的空间复杂度和存储结构无关。

数据处理效率与数据的存储结构有关。

28.线性表，向量，栈，队列都属于线性结构的顺序存储。

29.循环队列是队列的存储结构。

  循环链表是另一种形式的念式存储结构。

  (✘循环链表是循环队列的链式存储结构。✘)

30.完全二叉树的总结点为奇数时，叶子结点是总结点加一再除以二。

31.在实际处理中，可以用一位数组来存储堆序列中的元素，也可以用完全二叉树来直观的表示堆的结构。在用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左，右子树的根结点值，因为堆顶元素必须为序列的n个元素的最大项，因此其中序并不是有序序列。

  多重链表指表中每个结点由两个或两个以上的指针域的链表。如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点，②每个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构，所以多重链表不一定是非线性结构。

  在计算机中二叉树通常采用链式存储结构，对于满二叉树和完全二叉树来说，可以按层次进行顺序存储。

  排序二叉树的中序遍历序列是有序序列。

32.对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。

33.在线性表中寻找最大项时，平均情况下和最坏情况下比较次数都是n-1。

34.在长度为n的顺序表中查找一 个元素， 假没需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相

同的。则在平均情况下需要比较的次数大约为_

A.3n/4    B.n    C.n/2  D.n/4

本题的考查知识点是顺序表的存储结构。

因为需要查找的元素有一半机会在表中，所以二分之一的情况下平均比较次数为n/2，另二分之一的情况下平均比较次数为n。总的平均比较次数为(n/2+n) /2-3n/4。

故本题答案为A。

35.设数据结构B=(D, R)，其中

D={a,b,c,d，e，f}

R={(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f,a)}该数据结构为

A.线性结构    B.循环队列

C.循环链表    D.非线性结构

本题的考查知识点是数据结构。

如果一个非控的数据结构满足下列两个条件: 1) 有且只有一个根节点; 2) 每一一个结点最多有一一个前件，也最多有一一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。

数据结构B=(D, R)中， 每一个结点均有一个前件，不符合“有且只有一个根节点”的条件，所以为非线性结构。故本题答案选D。

36.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。 该队列中的元素个数为_

A.1    B.0    C.1或0    D.不确定

本题的考查知识点是带链队列。

在初始状态为front=rear=NULL的带链队列入队时，如果插入的结点既是队首结点又是队尾结点，则rear和front同时指向这个结点;否则在循环队列的队尾加入一一个新元素，rear指向新增结点的数据域，rear+1, front不变。 退队时，在循环队列的排头位置退出一个元素并赋给指定的变量，front指向第二个结点的数据域，front+1, rear不变。当front=rear=10时， front和rear同时指向这个唯一 元素，所以该队列中的元素个数为1。

故本题答案为A。

37.若二叉树没有叶子结点，则为空二叉树。

38.某带链栈的初始状态为top=bottom=NULL, 经过一系列正 常的入栈与退栈操作后，top=10, bottom=20。 该栈中的元素个数为_____。

A.不确定    B. 10    C.1    D.0

本题考查的知识点是栈。

带链的栈是具有栈属性的链表，线性链表的存储单元是不连续的，为把存储空间中一-些离散的空闲存 储结点利用起来，把所有空闲的结点组织成一个带链的栈，称为可利用栈。

线性链表执行删除操作运算时， 被删除的结点可以”回收到可利用栈，对应于可利用栈的入栈运算;线性链表执行插入运算时，需要一个新的结点，可以在可利用栈中取栈顶结点，对应于可利用栈的退栈运算。

可利用栈的入栈运算和退栈运算只需要改动top指针即可。因为是不连续的存储空间，所以top指针将不会有规律地连续变化，因此无法据此判断栈中的元素个数。

所以本题答案为A。