2014考研計算機(jī)數(shù)據(jù)結(jié)構(gòu)專項精講課程講義-第三部分第四章隊列

1、唯一淘寶 - 社所有，其它均為倒違法倒賣者。2014年 課程全部打折出售中！ 2015年 課程，已經(jīng)開售，歡迎 選擇題,保證淘寶更新最快最全！1. 假設(shè)以數(shù)組 Am存放循環(huán)隊列的元素,其頭尾指針分別為 front 和 rear，則當(dāng)前隊列中的元素個數(shù)為（ A）。A(rear-front+m)%m Brear-front+1C(front-rear+m)%mD(rear-front)%m2. 循環(huán)隊列A0.m-1存放其元素值，用 front 和 rear 分別表示隊頭和隊尾，則當(dāng)前隊列中的元素是( A)。A.(rear-front+m)%mB. rear-front+1C. rear-front

2、-1D. rear-front3.循環(huán)隊列在數(shù)組 A0.m中，則入隊時的操作為（D）。A. rear=rear+1C. rear=(rear+1) mod mB. rear=(rear+1) mod (m-1)D. rear=(rear+1)mod(m+1)4.若用一個大小為 6 的數(shù)組來實(shí)現(xiàn)循環(huán)隊列，且當(dāng)前 rear 和 front 的值分別為 0 和 3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear 和front 的值分別為多少？( B )A. 1 和 5B. 2 和 4C.4 和 2A）位置。 C鏈中D. 5 和 15.用單鏈表表示的鏈?zhǔn)疥犃械年狀^在鏈表的（A鏈頭B鏈尾二 1.（

3、2.3.4.5.6.7.判斷題隊列是一種與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。）通常使用隊列來處理函數(shù)或過程的調(diào)用。（ ）隊列邏輯上是一個下端和上端既能增加又能減少的線性表。（ ）循環(huán)隊列通常用指針來實(shí)現(xiàn)隊列的頭尾相接。（ ）循環(huán)隊列也存在空間溢出問題。（）隊列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。（ ）和刪除時受到了一些限制。（）棧和隊列都是線性表，只是在三1.應(yīng)用題簡要敘述循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)，并寫出其初始狀態(tài)、隊列空、隊列滿時的隊首指針與隊尾指針的值。解：typedef struct nodeelemtype elemcqm;/m 為隊列最大可能的容量。

4、front ,rear;cqnode; cqnode cq;初始狀態(tài) cq.front=cq.rear=0;隊列空 cq.front=cq.rear;隊列滿/front 和rear 分別為隊頭和隊尾指針。(cq.rear+1)%m=cq.front;2. 設(shè)一個雙端隊列，元素進(jìn)入該隊列的次序?yàn)?a，b，c，d。求既不能由輸入受限的雙端隊列得到,又不能由輸出受限的雙端隊列得到的輸出序列。答：既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是 dbca分析：4 個輸入受限有：cdba，dacb，dabd，dcab4 個輸出受限有： cdba，dacb，dbac，dcab既不

5、能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是 dbca 。若以 1、2、3、4 作為雙端隊列的輸入序列，試分別求出以下條件的輸出序列：能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端隊列得到的輸出序列；能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端隊列得到的輸出序列；既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列。答：4 個輸入受限有：4321 ，4123，4132，4312 4 個輸出受限有：4321，4123，4213，4312能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端隊列得到的輸出序列；答：4 個輸出受限有：4321 ，4

6、123，4213，43124 個輸入受限有：4321 ，4123，4132，4312既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列。答：輸出受限與輸入受限都得不到 4231。試題分析：若以 1234 作為雙端隊列的輸入序列.問:能由輸入受限的雙端隊列得到,但是不能由輸出受限的雙端隊列得到的輸出序列是什么?雙端隊列確是好像兩個棧底靠在一起的棧，但這兩個棧底又是互通的。它確是很靈活，因此不可能出現(xiàn)的出隊的序列只可能是四個車廂都已經(jīng)入隊的情況，因?yàn)槿绻犃兄兄挥?1個或 2 個或 3 個都是能調(diào)度過來的，但當(dāng) 4 個都進(jìn)去之后就受一定限制了，對于輸入受限的雙端隊列此時隊列中

7、車廂的排列必定是 1234,因此盡管兩頭都能出去，也不可能出現(xiàn)是 42*這樣的出隊序列，而對于輸出受限的雙端隊列，無論怎么進(jìn)去，在隊列中也形不成 4132 和4231 這樣的序列。假設(shè)以數(shù)組sq0.7存放循環(huán)隊列元素,變量f 指向隊頭元素的前一位置,變量r 指向隊尾元素，如用 A 和D 分別表示入隊和出隊操作，請給出：隊空的初始條件;執(zhí)行操作序列 A3D1A5D2A1D2A4 時的狀態(tài),并作必要的說明。答：（1）隊空的初始條件：f=r=0；（2）執(zhí)行操作 A3 后，r=3；/ A3 表示三次入隊操作執(zhí)行操作 D1 后，f=1；/D1 表示一次出隊操作執(zhí)行操作 A5 后，r=0；執(zhí)行操作 D2

8、后，f=3；執(zhí)行操作 A1 后，r=1；執(zhí)行操作 D2 后，f=5；執(zhí)行操作 A4 后，按溢出處理。因?yàn)閳?zhí)行 A3 后，r=4，這時隊滿，若再執(zhí)行 A 操作，則出錯。四、算法設(shè)計題1. 假設(shè)以結(jié)點(diǎn)的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點(diǎn)，但不設(shè)頭指針，請寫出相應(yīng)的入隊列和出隊列算法答：本題用類 C 語言編寫入隊和出隊算法。（1）void EnQueue (LinkedList rear, ElemType x)/ rear 是結(jié)點(diǎn)的循環(huán)鏈隊列的尾指針，本算法將元素 x到隊尾。 s= (LinkedList) malloc (sizeof(LNode); /申請結(jié)點(diǎn)空間s-data=x;

9、 s-next=rear-next;rear-next=s; rear=s;/將 s 結(jié)點(diǎn)鏈入隊尾/rear 指向新隊尾（2）void DeQueue (LinkedList rear)/ rear 是結(jié)點(diǎn)的循環(huán)鏈隊列的尾指針，本算法執(zhí)行出隊操作，操作成功輸出隊頭元素；否則給出出錯信息。 if (rear-next=rear) pr s=rear-next-next;rear-next-next=s-next;f(“隊空n”); exit(0);/s 指向隊頭元素，/隊頭元素出隊。prf (“出隊元素是”，s-data); if (s=rear) rear=rear-next; free(s)

10、;/空隊列2. 如果允許在循環(huán)隊列的兩端都可以進(jìn)行和刪除操作。要求：（1）寫出循環(huán)隊列的類型定義；（2）寫出“從隊尾刪除”和“從隊頭”的算法。答：題目分析 用一維數(shù)組 v0.M-1實(shí)現(xiàn)循環(huán)隊列，其中 M 是隊列長度。設(shè)隊頭指針 front 和隊尾指針 rear，約定 front 指向隊頭元素的前一位置，rear 指向隊尾元素。定義 front=rear 時為隊空，(rear+1)%m=front 為隊滿。約定隊頭端入隊向下標(biāo)大的方向發(fā)展，隊尾端入隊向下標(biāo)大的方向發(fā)展。#define M 隊列可能達(dá)到的最大長度 typedef struct elemtp dataM;front,rear; cy

11、cqueue;elemtp delqueue ( cycqueue Q)/Q 是如上定義的循環(huán)隊列，本算法實(shí)現(xiàn)從隊尾刪除，若刪除成功，返回被刪除元素，否則給出出錯信息。 if (Q.front=Q.rear)prQ.rear=(Q.rear-1+M)%M;f(“隊列空”); exit(0);/修改隊尾指針。return(Q.data(Q.rear+1+M)%M); /返回出隊元素。/從隊尾刪除算法結(jié)束void enqueue (cycqueue Q, elemtp x)/ Q 是順序的循環(huán)隊列，本算法實(shí)現(xiàn)“從隊頭”元素 x。if (Q.rear=(Q.front-1+M)%M) prf(“隊滿

12、”; exit(0);)Q.dataQ.front=x;Q.front=(Q.front+1+M)%M;/x 入隊列/修改隊頭指針。/ 結(jié)束從隊頭算法。3、已知 Q 是一個非空隊列，S 是一個空棧。僅用隊列和棧的 ADT 函數(shù)和少量工作變量，使用 Pascal 或C 語言編寫一個算法，將隊列 Q 中的所有元素逆置。棧的 ADT 函數(shù)有： makeEmpty(s:stack); push(s:stack;value:da pop(s:stack):daype; isEmpty(s:stack):隊列的 ADT 函數(shù)有：置空棧新元素 value 進(jìn)棧出棧，返回棧頂值判?？辗駓pe);enqueue( deQueue(isEmpty(ueue:value:daype);元素 value 進(jìn)隊出隊列，返回隊頭值判隊列空否ueue):daueue):ype;答：題目分析根據(jù)隊列先進(jìn)先出和棧后進(jìn)先出的性質(zhì)，先將非空隊列中的元素出隊，并壓入初始為空的棧中。這時棧頂元素是隊列中最后出隊的元素。然后將棧中元素出棧，依次到初始為空的隊列中。棧中第一個退棧的元素成為隊列中第一個元素，最后退棧的元素（出隊時第一個元素）成了最隊的元素，從而實(shí)現(xiàn)了原隊列的逆置。void Invert(queue Q)/Q 是一個非空隊列，本算法利用空棧 S 和