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

單測驗(yàn)4一．判題（下各題，確的請(qǐng)前面括號(hào)內(nèi)√；錯(cuò)的╳）（√）隊(duì)是制在兩端進(jìn)行操作的線性表。（√）判斷順序隊(duì)為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一結(jié)點(diǎn)。（×）在鏈隊(duì)列上出隊(duì)操作時(shí)，會(huì)改f指的值。（√）在循環(huán)隊(duì)列中若尾指針大于頭指針front，其元素個(gè)數(shù)為r。（×）在單向循環(huán)表中，若頭指針h，那么p所結(jié)點(diǎn)為結(jié)的件是p。（√）鏈隊(duì)列在一定圍內(nèi)不會(huì)出現(xiàn)隊(duì)滿的情況。（×）在循環(huán)鏈隊(duì)中無溢出現(xiàn)象。（×）棧和隊(duì)列都順序存儲(chǔ)的線性結(jié)構(gòu)。（×）在隊(duì)列中允許刪除的端稱為隊(duì)尾。（×）順隊(duì)和循環(huán)隊(duì)關(guān)于隊(duì)滿和隊(duì)空的判斷條件是一樣的。二．填題（1）在列中存取數(shù)據(jù)應(yīng)遵循的原則是

先進(jìn)先出。（2）

隊(duì)列

是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在的另一進(jìn)行刪除運(yùn)算的線性。（3）在列中，允許插入的一端稱為（4在隊(duì)列中，允許刪除的一端稱為

隊(duì)尾。隊(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ì)空的條件為front==rear。（）鏈列LQ為空時(shí)，LQ->front->next=NULL。（）設(shè)度為的鏈列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入操作的時(shí)間復(fù)雜度為O（n）。（）設(shè)度為的鏈列用單循環(huán)鏈表表示，若只設(shè)尾指針，則出操作的時(shí)間復(fù)雜度為0（1）。（）在一個(gè)鏈隊(duì)列中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為空。79

（）設(shè)環(huán)隊(duì)列的頭指針front指隊(duì)首元素，尾針指隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為MAXLEN，則隊(duì)滿標(biāo)志為：front==(rear+1)%MAXLEN。（）在個(gè)鏈隊(duì)列中，若隊(duì)首指針為front，尾指針為rear，則斷該隊(duì)列只有一個(gè)結(jié)點(diǎn)的條為：front==rearfront!NULL。(或front==rear&&front<>NULL)（）向個(gè)循環(huán)隊(duì)列中插入元素時(shí)，首先要判斷所指的位置寫新的數(shù)據(jù)。

隊(duì)尾指針，后再向指針（17）讀隊(duì)首元素的操作

不改變（或不影響）

隊(duì)列元素個(gè)。（18）設(shè)環(huán)隊(duì)列的容量為40（序號(hào)從0到經(jīng)一系列的入和隊(duì)算，有front=11，循環(huán)隊(duì)列中還有8

個(gè)元素。（L=＋rear－front)%（40＋19）%）（19）隊(duì)列Q，經(jīng)過下列運(yùn)算：InitQueue(Q)(初始化隊(duì)列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);ReadFront(Q,x);QEmpty(Q);

后值是0。（20）隊(duì)Q經(jīng)過InitQueue(Q)(始化隊(duì)列);InQueue(Q,a);InQueue(Q,b);后x的是a。三．選題（1）列限定在（D）行操作的線性表。A．間

B．首

C．尾

D．端（2）列的元素個(gè)數(shù)是(B)。A．變的

B．變

C．意的

D．0（3）一列內(nèi)各元素的類型(A)。A．須一致

B．能致C．以不一致

D．不制（4）列一個(gè)(C)線表結(jié)構(gòu)。A．加限制的

B．廣的C．了限制的

D．非（5）利用大小為n的組順序儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最后一個(gè)元的下標(biāo)為（）A．n-2B．n-1C．nD．n+1（6）個(gè)環(huán)隊(duì)列一旦說明，其占用空間的?。ˋ）A．固定．以變動(dòng)（7循環(huán)隊(duì)列占用的空間A)。A．須連續(xù)B．必連續(xù)

C．能固定．態(tài)化C．能連續(xù)．以連續(xù)80

（8放循環(huán)隊(duì)列元素的數(shù)組data有10個(gè)元，data組的下標(biāo)范圍是(B)。A．0..10B．0..9

C．1..9．1..10（9）若隊(duì)的序列為：A，B，C，D，出隊(duì)的序列是（C）A．B，C，D，AC．A，B，C，D

B．A，C，B，DD．C，BD，A）四個(gè)元素按：A，B，C，D順序連續(xù)進(jìn)隊(duì)，則尾元素是（D）A．AC．C

B．BD．D（11四個(gè)元素按A，B，C，D順連續(xù)進(jìn)隊(duì)Q，行一次OutQueue(Q)操作，隊(duì)頭元素是（B）A．A．BC．C．D（12四個(gè)元素按A，B，C，D順連續(xù)進(jìn)隊(duì)Q，行四次OutQueue(Q)操作，再執(zhí)行QEmpty(Q);的值是（B）A．0．1C．2D．3（13）隊(duì)Q經(jīng)過下列運(yùn)算后x的值是（）InitQueue(Q)(ReadFront(Q,x);

初始化隊(duì)列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);A．B．bC．0D．1（14）循環(huán)隊(duì)列SQ隊(duì)的條件是(B)。A．SQ->rear==SQ->frontB．(SQ->rear+1)%MAXLEN==SQ->frontC．SQ->rear==0

D．SQ->front==0）設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)：為據(jù)域，next為指針域，且是頂指針。若想在鏈棧的棧頂插入一個(gè)指針s所的結(jié)點(diǎn)，則應(yīng)執(zhí)行下列（A）作。A．s->next=top->next；top->next=s；B．top->next=s；C．s->next=top；top=top->next；

D．s->next=top；top=s；（16）帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示圖如下，鏈隊(duì)列的隊(duì)頭元素是（A）LQ->frontHABCΛLQ->rearA．B．C．CD．81

（17）帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示圖如下，指向鏈隊(duì)列的隊(duì)頭指針是（C）LQ->frontHABCΛLQ->rearA．LQ->frontBLQ->rearC．LQ->front->nextD．LQ->rear->next（18頭結(jié)點(diǎn)的鏈列LQ示意圖如下，在行進(jìn)隊(duì)運(yùn)算時(shí)指針LQ->front（A）LQ->frontHABCΛLQ->rearA．終不改變B．時(shí)改變C．隊(duì)時(shí)改變D．隊(duì)時(shí)改變（19）隊(duì)Q，經(jīng)過下列算后，再執(zhí)QEmpty(Q)的值（C）InitQueue(Q)(ReadQueue(Q,x);

初始化隊(duì)列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);A．BbC．D．1（20）若用個(gè)大小6的組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)front和rear的分別為3和0，從隊(duì)列中刪除一個(gè)元素，加入兩個(gè)元素后，front和ear的分別(B)。A．5和1B4和2C．2和4D．1和5四．寫程序運(yùn)的結(jié)果寫出下列程序段的輸出結(jié)果（隊(duì)列中的元素類型charvoidmain(){QueueQ;InitQueuecharx="E";InQueue(Q,"H");InQueue(Q,"R");InQueue(Q,y);OutQueue(Q,x);InQueue(Q,x);OutQueue(Q,x);InQueue(Q,"A");

//始化隊(duì)列82

while(!QEmpty(Q)){OutQueue(Q,y);printf(y);};printf(x);}答：輸出為五．程填空．假定用一個(gè)循環(huán)單鏈表表示一個(gè)循環(huán)隊(duì)列，該隊(duì)列只設(shè)一個(gè)隊(duì)尾指rear，試填空完成向循環(huán)隊(duì)列中插入一個(gè)元為的點(diǎn)的函數(shù)。typedefstructqueuenode{intdata;structqueuenode*next;}qu;InQueue(rear,x){qu*rear；int；{qu*head,*s;s=newqu;s->data=x;if(rear==NULL){rear=s;rear->next;}else{head=rear->next;rear->next=s;rear=s;rear->next=head;}}

//定義隊(duì)列的存儲(chǔ)結(jié)構(gòu)//向隊(duì)列插入元素x的函數(shù)//環(huán)隊(duì)列為空，則建立一個(gè)結(jié)點(diǎn)的循環(huán)隊(duì)列//環(huán)隊(duì)列非空，則s到后面六.算法設(shè)計(jì)題1．一循環(huán)隊(duì)列Queue只有頭指針front，不尾指針，另設(shè)一個(gè)含有元個(gè)數(shù)的記數(shù)器，寫出相應(yīng)的入隊(duì)算法和出隊(duì)算法。2．用一個(gè)循環(huán)數(shù)組Q[0..MAXLEN-1]表隊(duì)時(shí)，該隊(duì)列只有一個(gè)指針front，不設(shè)尾指針，而改置一個(gè)記器count用以記錄隊(duì)列中結(jié)點(diǎn)的個(gè)數(shù)。試寫一個(gè)實(shí)現(xiàn)：初始化隊(duì)列、判隊(duì)空讀隊(duì)頭元素、入隊(duì)操作和出隊(duì)操作的算法。83

3．個(gè)單鏈表組成的循環(huán)隊(duì)列，只設(shè)一尾指針rear，設(shè)頭指針，請(qǐng)編寫他如下算法：（1）向循隊(duì)列中插入個(gè)元素為x的點(diǎn)；（2）從循隊(duì)列中刪除個(gè)結(jié)點(diǎn)。1．解用一個(gè)環(huán)數(shù)組Queue[0，表該循環(huán)隊(duì)列，頭指針為front，計(jì)數(shù)器count用來記錄隊(duì)列中結(jié)點(diǎn)的個(gè)數(shù)。（1）隊(duì)法：voidinqueqe(intx){inttemp;if(count==n)printf("隊(duì)上溢出\n");else{count++temp=(front+count)%n;Queue[temp]=x}}（2）隊(duì)法：intoutqueue(){inttemp;if(count==0)printf("隊(duì)下溢出\n");else{temp=Queue[front];front=(front+1)%n;count--;returntemp;}}2．解：隊(duì)列為空：count==0隊(duì)列為滿：count=MAXLEN隊(duì)尾第一個(gè)元位置==(front+count)%MAXLEN隊(duì)首第一個(gè)元位置==(front+1)%MAXLENconstMAXLEN=100;intqueue[MAXLEN];intfront,count;（1）始隊(duì)列voidinit(){front=1;count=0;}

//義隊(duì)頭和計(jì)數(shù)count84

（2）定空intQEmpty(){if(count==0)return(1);elsereturn(0);}（3讀隊(duì)頭元素voidReadFront(intqueue[],x){if(count==0)printf("下溢出\n");else{front=(front+1)%MAXLEN;x=queue[front];}}（4）隊(duì)作voidInQueue(intqueue[],intx){intplace;if(count==MAXLEN)printf("上溢出\n");else{count++;place=(front+count)%MAXLEN;queue[MAXLEN]=x;}}（5）隊(duì)作voidOutQueue(int{if(count==0)printf("隊(duì)列下溢出\n");else{front=(front+1)%MAXLEN;count--;}}

//刪除隊(duì)列頭元素3．85

（1）：義本題隊(duì)列的結(jié)點(diǎn)類型如下：typedefstructlinknode{intdata;structlinknode}qu;qu*rear;inqueue(intx){qu*head,*s;s=(qu*)newqu;s->data=x;if(rear==NUlL){rear＝s;rear->next＝}else{head=rear->next；rear->next＝rear=s;rear->next＝head;}}解voiddelque