數(shù)據(jù)結(jié)構(gòu)單元4練習(xí)參考答案

1、精品好資料學(xué)習(xí)推薦單元測驗4一判斷題（下列各題，正確的請在前面的括號內(nèi)打；錯誤的打）（）（1）隊列是限制在兩端進(jìn)行操作的線性表。（）（2）判斷順序隊列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一個結(jié)點。（）（3）在鏈隊列上做出隊操作時，會改變front指針的值。（）（4）在循環(huán)隊列中，若尾指針rear大于頭指針front，其元素個數(shù)為rear- front。（）（5）在單向循環(huán)鏈表中，若頭指針為h，那么p所指結(jié)點為尾結(jié)點的條件是p=h。（）（6）鏈隊列在一定范圍內(nèi)不會出現(xiàn)隊滿的情況。（）（7）在循環(huán)鏈隊列中無溢出現(xiàn)象。（）（8）棧和隊列都是順序存儲的線性結(jié)構(gòu)。（）（9）在隊列中允許刪除的一端稱為隊尾。

2、（）（10）順序隊和循環(huán)隊關(guān)于隊滿和隊空的判斷條件是一樣的。二填空題（1） 在隊列中存取數(shù)據(jù)應(yīng)遵循的原則是先進(jìn)先出。（2） 隊列 是被限定為只能在表的一端進(jìn)行插入運算，在表的另一端進(jìn)行刪除運算的線性表。（3） 在隊列中，允許插入的一端稱為隊尾。（4） 在隊列中，允許刪除的一端稱為隊首（或隊頭）。（5） 隊列在進(jìn)行出隊操作時，首先要判斷隊列是否為 空。（6） 順序隊列在進(jìn)行入隊操作時，首先要判斷隊列是否為 滿。（7） 順序隊列初始化后，front=rear= -1 。（8） 解決順序隊列“假溢出”的方法是采用循環(huán)隊列。（9） 循環(huán)隊列的隊首指針為front，隊尾指針為rear，則隊空的條件為 f

3、ront = rear 。（10） 鏈隊列LQ為空時，LQ-front-next= NULL 。（11） 設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊操作的時間復(fù)雜度為 O（n）。（12） 設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)尾指針，則出隊操作的時間復(fù)雜度為 0（1）。（13） 在一個鏈隊列中，若隊首指針與隊尾指針的值相同，則表示該隊列為空。（14） 設(shè)循環(huán)隊列的頭指針front指向隊首元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN，則隊滿標(biāo)志為：front=(rear+1)%MAXLEN 。（15） 在一個鏈隊列中，若隊首指針為front，隊

4、尾指針為rear，則判斷該隊列只有一個結(jié)點的條件為： front=rear & front !NULL 。(或 front=rear & front NULL )（16） 向一個循環(huán)隊列中插入元素時，首先要判斷隊尾指針，然后再向指針?biāo)傅奈恢脤懭胄碌臄?shù)據(jù)。（17） 讀隊首元素的操作 不改變（或不影響） 隊列元素的個數(shù)。 （18） 設(shè)循環(huán)隊列的容量為40（序號從0到39），現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有 front=11，rear=19，則循環(huán)隊列中還有 8 個元素。（L= (Nrearfront)% N=（401911）% 40=8）（19）隊列Q，經(jīng)過下列運算：InitQueue(Q)(

5、初始化隊列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是0 。（20）隊列Q經(jīng)過InitQueue(Q)(初始化隊列);InQueue(Q,a);InQueue(Q,b); ReadFront(Q,x)后，x的值是 a 。三選擇題（1）隊列是限定在（D）進(jìn)行操作的線性表。 A中間 B隊首 C隊尾 D端點（2）隊列中的元素個數(shù)是( B )。A不變的 B可變的 C任意的 D0（3）同一隊列內(nèi)各元素的類型( A )。A必須一致 B不能一致 C可以不一致 D不限制（4）隊列是一個( C )線性表結(jié)構(gòu)。A

6、不加限制的B推廣了的 C加了限制的 D非（5）當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最后一個元素的下標(biāo)為（ B ）。 An-2 Bn-1CnDn+1（6）一個循環(huán)隊列一旦說明，其占用空間的大?。ˋ）。 A已固定B可以變動 C不能固定D動態(tài)變化（7）循環(huán)隊列占用的空間( A )。A必須連續(xù) B不必連續(xù) C不能連續(xù)D可以不連續(xù)（8）存放循環(huán)隊列元素的數(shù)組data有10個元素，則data數(shù)組的下標(biāo)范圍是( B )。A0.10 B0.9 C1.9D1.10（9）若進(jìn)隊的序列為：A，B，C，D，則出隊的序列是（ C ）。 AB，C，D，A BA，C，B，DCA，B，C，D DC，B，D，A（1

7、0）四個元素按：A，B，C，D順序連續(xù)進(jìn)隊Q，則隊尾元素是（ D ）。 A AB BC CD D（11）四個元素按：A，B，C，D順序連續(xù)進(jìn)隊Q，執(zhí)行一次OutQueue(Q)操作后，隊頭元素是（ B ）。 A AB BC C D D（12）四個元素按：A，B，C，D順序連續(xù)進(jìn)隊Q，執(zhí)行四次OutQueue(Q)操作后，再執(zhí)行QEmpty(Q);后的值是（ B ）。 A 0B 1 C 2 D 3（13）隊列Q，經(jīng)過下列運算后，x 的值是（B）。InitQueue(Q)(初始化隊列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x);ReadFront (Q,x)

8、;AaBbC0D1（14）循環(huán)隊列SQ隊滿的條件是( B )。ASQ-rear=SQ-front B(SQ-rear+1)% MAXLEN =SQ-frontCSQ-rear=0 DSQ-front=0（15）設(shè)鏈棧中結(jié)點的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針。若想在鏈棧的棧頂插入一個由指針s所指的結(jié)點，則應(yīng)執(zhí)行下列（ A ）操作。 As-next=top-next；top-next=s； Btop-next=s；Cs-next=top；top=top-next； Ds-next=top；top=s；（16）帶頭結(jié)點的鏈隊列LQ示意圖如下，鏈隊列的隊頭元素是（ A ）L

9、Q-frontHABCDLQ-rearAA BB CCDD（17）帶頭結(jié)點的鏈隊列LQ示意圖如下，指向鏈隊列的隊頭指針是（ C ）LQ-frontHABCDLQ-rearALQ-front BLQ-rearCLQ-front-next DLQ-rear-next（18）帶頭結(jié)點的鏈隊列LQ示意圖如下，在進(jìn)行進(jìn)隊運算時指針LQ-front（ A ） LQ-frontHABCDLQ-rearA始終不改變B有時改變C進(jìn)隊時改變 D出隊時改變（19）隊列Q，經(jīng)過下列運算后，再執(zhí)行QEmpty(Q) 的值是（C）。InitQueue(Q) (初始化隊列);InQueue(Q,a); InQueue(Q,

10、b);OutQueue(Q,x);ReadQueue(Q,x);AaBbC0 D1（20）若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為( B )。A5和1B4和2 C2和4 D1和5四 寫出程序運行的結(jié)果寫出下列程序段的輸出結(jié)果（隊列中的元素類型為char）。void main( )Queue Q; InitQueue (Q);/ 初始化隊列char x=E; y=C;InQueue (Q, H);InQueue (Q, R);InQueue (Q, y);OutQueue (Q,x)

11、; InQueue (Q,x); OutQueue (Q,x); InQueue (Q, A); while(!QEmpty(Q)OutQueue (Q,y);printf(y); ;printf(x);答：輸出為“CHAR”。五程序填空1假定用一個循環(huán)單鏈表表示一個循環(huán)隊列，該隊列只設(shè)一個隊尾指針rear，試填空完成向循環(huán)隊列中插入一個元素為x的結(jié)點的函數(shù)。typedef struct queuenode / 定義隊列的存儲結(jié)構(gòu)int data;struct queuenode *next;qu;InQueue(rear,x) / 向隊列插入元素為x的函數(shù)qu *rear；int x； qu

12、 *head,*s; s= new qu ; s-data= x ; if (rear=NULL) / 循環(huán)隊列為空，則建立一個結(jié)點的循環(huán)隊列 rear=s; rear-next; else head= rear-next ; / 循環(huán)隊列非空，則將s插到后面rear-next= s ;rear=s;rear-next =head;六. 算法設(shè)計題1設(shè)一個循環(huán)隊列Queue，只有頭指針front，不設(shè)尾指針，另設(shè)一個含有元素個數(shù)的記數(shù)器cont，試寫出相應(yīng)的入隊算法和出隊算法。2用一個循環(huán)數(shù)組Q0.MAXLEN-1表示隊列時，該隊列只有一個頭指針front，不設(shè)尾指針，而改置一個記數(shù)器coun

13、t用以記錄隊列中結(jié)點的個數(shù)。試編寫一個能實現(xiàn)：初始化隊列、判隊空、讀隊頭元素、入隊操作和出隊操作的算法。3一個用單鏈表組成的循環(huán)隊列，只設(shè)一個尾指針rear，不設(shè)頭指針，請編寫他如下算法：（1） 向循環(huán)隊列中插入一個元素為x的結(jié)點；（2） 從循環(huán)隊列中刪除一個結(jié)點。1 解：用一個循環(huán)數(shù)組Queue0，n-1表示該循環(huán)隊列，頭指針為front，計數(shù)器count用來記錄隊列中結(jié)點的個數(shù)。（1）入隊算法： void inqueqe(int x) int temp;if (count=n) printf(隊列上溢出n);else count+ temp=(front+count)%n; Queuete

14、mp=x （2）出隊算法： int outqueue() int temp;if (count=0) printf(隊列下溢出n);else temp=Queuefront; front=(front+1)%n; count-; return temp; 2解：隊列為空：count=0隊列為滿：count=MAXLEN隊尾第一個元素位置=(front+count)%MAXLEN隊首第一個元素位置=(front+1)%MAXLENconst MAXLEN=100;int queueMAXLEN;int front,count; / 定義隊頭和計數(shù)器count（1）初始化隊列void init()

15、 front=1; count=0;（2）判定隊空int QEmpty() if (count=0)return(1); else return(0); （3）讀隊頭元素void ReadFront(int queue,x) if (count=0) printf(下溢出n); else front=(front+1)%MAXLEN;x=queuefront; （4）入隊操作 void InQueue(int queue,int x) int place; if (count=MAXLEN)printf(上溢出n); else count+;place=(front+count)%MAXLEN

16、;queueMAXLEN=x; （5）出隊操作 void OutQueue(int queue) / 刪除隊列頭元素 if (count=0) printf(隊列下溢出n); else front=(front+1)%MAXLEN;count-; 3（1）解：定義本題隊列的結(jié)點類型如下：typedef struct linknode int data; struct linknode *next; qu; qu *rear;inqueue(int x) / 向隊列插入結(jié)點x qu *head, *s; s=(qu *) new qu; / 創(chuàng)建一個新結(jié)點 s-data=x; if (rear=NUlL) / 若隊空,則建立一個循環(huán)隊列 rears; rear-nexts; else / 若不為空，則將s插到后面 head=