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

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

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

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

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

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

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

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

8、;AaBbC0D1（14）循環(huán)隊(duì)列SQ隊(duì)滿的條件是( B )。ASQ-rear=SQ-front B(SQ-rear+1)% MAXLEN =SQ-frontCSQ-rear=0 DSQ-front=0（15）設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針。若想在鏈棧的棧頂插入一個(gè)由指針s所指的結(jié)點(diǎn)，則應(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é)點(diǎn)的鏈隊(duì)列LQ示意圖如下，鏈隊(duì)列的隊(duì)頭元素是（ A ）L

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

10、b);OutQueue(Q,x);ReadQueue(Q,x);AaBbC0 D1（20）若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，front和rear的值分別為( B )。A5和1B4和2 C2和4 D1和5四 寫(xiě)出程序運(yùn)行的結(jié)果寫(xiě)出下列程序段的輸出結(jié)果（隊(duì)列中的元素類(lèi)型為char）。void main( )Queue Q; InitQueue (Q);/ 初始化隊(duì)列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假定用一個(gè)循環(huán)單鏈表表示一個(gè)循環(huán)隊(duì)列，該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針rear，試填空完成向循環(huán)隊(duì)列中插入一個(gè)元素為x的結(jié)點(diǎn)的函數(shù)。typedef struct queuenode / 定義隊(duì)列的存儲(chǔ)結(jié)構(gòu)int data;struct queuenode *next;qu;InQueue(rear,x) / 向隊(duì)列插入元素為x的函數(shù)qu *rear；int x； qu

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

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

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

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

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