數(shù)據(jù)結(jié)構(gòu)習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)第三章習(xí)題3.1單項(xiàng)選擇題2 .一個(gè)棧的入棧序列a,b,c,d,e,則棧的不可能的輸出序列是。A.edcbaB.DecbaC.DceabD.abcde3 .若已知一個(gè)棧的入棧序列是1,2,3,若p1=n,貝Upi為oA.i.B.n=I4 .棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是A.順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)C.鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組.n,其輸出序列為p1,p2,p3,pn,C.n-i+1D.不確定B.散鏈方式和索引方式D.線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)B.ST->top=0D.ST->top=m05 .判定一個(gè)棧ST（最多元素為m0）為空的條件是A.ST->top<>0

2、C.ST->top<>m06 .判定一個(gè)棧ST（最多元素為m0）為棧滿的條件是。A.ST->top!=0B.ST->top=0C.ST->top!=m0D.ST->top=m07 .棧的特點(diǎn)是,隊(duì)列的特點(diǎn)是。A先進(jìn)先出B.先進(jìn)后出8 .一個(gè)隊(duì)列的入棧序列是1,2,3,4,則隊(duì)列的輸出序列是A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,19 .判定一個(gè)隊(duì)列QU（最多元素為m0）為空的條件是。A.QU->rear-QU->front=m0B.QU->rear-QU->front-1=m0C.QU->fr

3、ont=QU->rearD.QU->front=QU->rear+110 .判定一個(gè)隊(duì)列QU(最多元素為m0)為滿隊(duì)列的條件是A.QU->rear-QU->front=m0B.QU->rear-QU->front-1=m0C.QU->front=QU->rearD.QU->front=QU->rear+111 .判定一個(gè)循環(huán)隊(duì)列QU(最多元素為m0)為空的條件是A. QU->front=(QU->rear+1)%m0B. QU->front!=(QU->rear+1)%m0C.QU->front=Q

4、U->rearD.QU->front!=QU->rear12 .判定一個(gè)循環(huán)隊(duì)列QU(最多元素為m0)為滿隊(duì)列的條件是A. QU->front=(QU->rear+1)%m0B. QU->front!=(QU->rear+1)%m0C.QU->front=QU->rearD.QU->front!=QU->rear+112 .向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(zhí)行。HS->next=s;A. s->next=HS->next;HS->next=s;B. s->next=HS;HS=s

5、;C. s->next=HS;HS=HS->next;13 .從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行。Ax=HS;HS=HS->next;B. x=HS->data;C. HS=HS->next;x=HS->data;D. x=HS->data;HS=HS->next;14 .在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算時(shí)。A. f->next=s;f=s;B. r->next=s;r=s;C. s->next=r;r=s;D. s->next=f;f=s;15 .

6、在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算時(shí)。A. r=f->next;B. r=r->next;C. f=f->next;D. f=r-next;3 .2填空題4 .向棧中壓入元素的操作是5 .對(duì)棧進(jìn)行退棧的操作是6 .在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的7 .從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是8 .在具有個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有個(gè)元素9 .在棧頂指針為HS的鏈棧中，判定?？盏臈l件是一。10 .在棧頂指針為HS的鏈棧中，計(jì)算該鏈站中結(jié)點(diǎn)個(gè)數(shù)的函數(shù)時(shí)。11 .在HQ的鏈隊(duì)中，判定只有一個(gè)結(jié)點(diǎn)的條件是。12 .在HQ的鏈隊(duì)中，計(jì)算該鏈隊(duì)中結(jié)點(diǎn)

7、個(gè)數(shù)的函數(shù)是。3.3順序棧習(xí)題解析給出輸入項(xiàng)A,B,C.如果輸入項(xiàng)序列由1 .對(duì)于一個(gè)棧，全部可能的輸出序列。解：本題利用棧的“后進(jìn)先出”的特點(diǎn),A進(jìn)A出B進(jìn)B出C進(jìn)C出A進(jìn)A出B進(jìn)C進(jìn)C出B出A進(jìn)B進(jìn)B出A出C進(jìn)C出A進(jìn)B進(jìn)B出C進(jìn)C出A出A進(jìn)B進(jìn)C進(jìn)C出B出A出不可能產(chǎn)生的輸出序列CABA,B,C所組成，是給出有如下幾種情況：產(chǎn)生輸出序列ABC產(chǎn)生輸出序列ACB產(chǎn)生輸出序列BAC產(chǎn)生輸出序列BCA產(chǎn)生輸出序列CBA2 .有兩個(gè)棧si和s2共享存儲(chǔ)空間c1,m,其中一個(gè)棧底設(shè)在c1處，另一個(gè)棧底設(shè)在cm0處，分別編寫si和s2的進(jìn)棧push(i,x)、退棧pop(i)和設(shè)置?？誷etnull

8、(i)的函數(shù)，其中i=1,2。注意：僅當(dāng)整個(gè)空間c1,m0占滿時(shí)才產(chǎn)生上溢。解：該共享?xiàng)５慕Y(jié)構(gòu)如圖2.3所示，兩棧的最多元素個(gè)數(shù)為m0,top1是棧1的棧指針，top2是棧2的棧指針，當(dāng)top2=top1+1時(shí)出現(xiàn)上溢出，當(dāng)top1=0時(shí)棧1出現(xiàn)下溢出，當(dāng)top2=m0+1時(shí)棧2出現(xiàn)下溢出。根據(jù)上述原理得到如下函數(shù)：top1top2棧1底棧1頂圖2.3共享?xiàng)?*top1,top2和m0均為已賦初值的voidpush(x,i)棧2頂棧2底int型全局變量*/a1a2anbmb2b1c的元素序號(hào)12.nm0-1m0intx,I(if(top1=top2-1)printf(上溢出！n");

9、elseif(i=1)/*對(duì)第一個(gè)棧進(jìn)行入棧操作*/(top1+;ctop1=x;)else/*對(duì)第二個(gè)棧進(jìn)行入棧操作*/(top2-;ctop2=x;)/*函數(shù)pop*/voidpop(i)inti;(if(i=1)/*對(duì)第一個(gè)棧進(jìn)行出棧操作*/if(top1=0)printf(棧1下溢出！n”)；else(pop=ctop1;top1-;)else/*對(duì)第二個(gè)棧進(jìn)行出棧操作*/if(top2=m0+1)printf(棧2下溢出！n");else(pop=ctop2;top2+;)/*函數(shù)setnull*/setnull(i)inti;(if(i=1)top1=0;elsetop2

10、=m0+1;)4.證明：有可能從初始輸入序列1,2,.n,利用一個(gè)棧得到輸出序列p1,p2,.,pn(p1,p2星n1,2,-.n的一種排列)的充分必要條件是：不存在這樣的i,j,k,滿足i<j<k同時(shí)pj<pk<pi.證明：【充分條件】如果不存在這樣的i,j,k滿足i<j<k同時(shí)pj<pk<pi,即對(duì)于輸入序列：pj,pk-pi,(pj<pk<pi)不存在這樣的輸出序列：,，pi,pj，,pk，,，(或簡(jiǎn)單地對(duì)于輸入序列1,2,3不存在輸出序列3,1,2)從中看到，pi后進(jìn)先出，是滿足棧的特點(diǎn)，因?yàn)閜i最大也就是在pj和pk之后進(jìn)入

11、，卻在輸出序列中排在pj和pk之前，同時(shí)也說明，在pk之前先進(jìn)入的pj不可能在pk之后出來，反過來說明滿足先進(jìn)后出的特點(diǎn)，所以構(gòu)成一個(gè)棧。【必要條件】如果初始輸入序列是1,2,n,假設(shè)是進(jìn)棧，又同時(shí)存在i,j,k滿足i<j<k同時(shí)pj<pk<pi,即對(duì)于輸入序列：一pj,pk-pi,(pj<pk<pi)存在這樣的輸出序列：一pi,pj-pk,從中看到，pi先進(jìn)后出，是滿足棧的特點(diǎn)，因?yàn)閜i最大也就是在pj和pk之后進(jìn)入，同時(shí)看到在pk之前先進(jìn)入的pj卻在pk之前出來，反過來說明不滿足先進(jìn)后出的特點(diǎn)，與前面的假設(shè)是棧不一致，本題即證。6.已知兩個(gè)整數(shù)集合A和B

12、,它們的元素分別依元素值遞增有序存放在兩個(gè)單鏈表HA和HB中，編寫一個(gè)函數(shù)求出這兩個(gè)集合的并集C,并要求表示集合C的鏈表的結(jié)點(diǎn)仍依元素值遞增有序存放。解：假設(shè)HA和HB的頭指針分別為ha和hb,先設(shè)置一個(gè)空的循環(huán)單鏈表HC,頭指針為hc,之后依次比較HA和HB的當(dāng)前結(jié)點(diǎn)的元素值，將較小元素值的結(jié)點(diǎn)復(fù)制一個(gè)并鏈接到HC的末尾，若相等，則將其中之一復(fù)制一個(gè)并鏈接到HC的末尾。當(dāng)HA或HB為空后，把另一個(gè)鏈表的余下結(jié)點(diǎn)都復(fù)制并鏈接到HC的末尾。實(shí)現(xiàn)本題功能的函數(shù)如下：voidunion(ha,hb,hc)node*ha,*hb,*hc;node*p,*q,*r,*s;hc=node*malloc(s

13、izeof(node);/*建立一個(gè)頭結(jié)點(diǎn)，r總是指向HC鏈表的最后一個(gè)結(jié)點(diǎn)*/r=hc;p=ha;q=hb;while(p!=NULL&&q!=NULL)if(p->data<q->data)s=(node*)malloc(sizeof(node);s->data=p->data;r->next=s;r=s;p=p->next;elseif(p->data>q->data)s=(node*)malloc(sizeof(node);s->data=q->data;r->next=s;r=s;q=q-&

14、gt;next;else/*p->data=q->data的情況/s=node*malloc(sizeof(node);q=q->next;if(p=NULL)/*把q及之后的結(jié)點(diǎn)復(fù)制到HC中*/while(q!=NULL)s=(node*)malloc(sizeof(node);s->data=p->data;r->next=s;r=s;p=p->next;r->next=NULL;s=hc;hc=hc->next;free(s);/*刪除頭結(jié)點(diǎn)*/15.假設(shè)在長(zhǎng)度大于1的循環(huán)單鏈表中，既無頭結(jié)點(diǎn)也無頭指針，p為指向該鏈表中某個(gè)結(jié)點(diǎn)的指針，編寫一個(gè)函數(shù)刪除該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。解：本題利用循環(huán)單鏈表的特點(diǎn)，通過p指針可循環(huán)找