循環隊列數據結構與演算法

⑴ 數據結構 第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。