數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案

1、數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案一、選擇題評(píng)價(jià)一個(gè)算法時(shí)間性能的主要標(biāo)準(zhǔn)是()。1.A、算法易于調(diào)試B、算法易于理解C、算法的穩(wěn)定性和正確性D、算法的時(shí)間復(fù)雜度()等五個(gè)特性。計(jì)算機(jī)算法具備有輸入、輸出、2.A、可行性、可移植性和可擴(kuò)充性B、可行性、確定性和有窮性C、確定性、有窮性和穩(wěn)定性D、xx、穩(wěn)定性和xx。帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是()3.A、 head=NULLB、 head->next=NULLC、 head->next=headD、 head！=NULL以下關(guān)于線(xiàn)性表的說(shuō)法不正確的是()。4.A、線(xiàn)性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類(lèi)型。B、線(xiàn)性表中包

2、含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。C、線(xiàn)性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。D、存在這樣的線(xiàn)性表：表中各結(jié)點(diǎn)都沒(méi)有直接前趨和直接后繼。在順序表中，只要知道()，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。5.A、基地址B、結(jié)點(diǎn)大小C、向量大小D、基地址和結(jié)點(diǎn)大小()運(yùn)算中，使用順序表比鏈表好。6.A、插入B、刪除C、根據(jù)序號(hào)查找D、根據(jù)元素值查找一個(gè)長(zhǎng)度為n的順序表中，向第i個(gè)元素之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)()個(gè)元素7.A、n-iB、 n-i+1C、 n-i-1D、 i()適合作為經(jīng)常在首尾兩端操作線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)。8.A、順序表B、單鏈表C、循環(huán)鏈表D、雙向鏈表?xiàng)：完?duì)列的共同點(diǎn)是

3、()9.A、都是先進(jìn)后出B、都是先進(jìn)先出C、只允許在端點(diǎn)處插入和刪除元素D、沒(méi)有共同點(diǎn)一個(gè)隊(duì)列的入列序列是1234，則隊(duì)列的輸出序列是()。10.A、 4321B、 1234C、 1432D、 3241隊(duì)列與一般的線(xiàn)性表的區(qū)別在于()。11.A、數(shù)據(jù)元素的類(lèi)型不同B、運(yùn)算是否受限制C、數(shù)據(jù)元素的個(gè)數(shù)不同D、邏輯結(jié)構(gòu)不同“假上溢”現(xiàn)象會(huì)出現(xiàn)在()中。12.A、循環(huán)隊(duì)列B、隊(duì)列C、鏈隊(duì)列、順序隊(duì)列D二、填空數(shù)據(jù)的邏輯結(jié)構(gòu)被分集合、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)F面程序段的時(shí)間復(fù)雜度i=s=0whil(s<ni+s+;樹(shù)型結(jié)構(gòu)和圖形結(jié)構(gòu)合稱(chēng)是非

4、線(xiàn)性結(jié)構(gòu).在長(zhǎng)度的順序存儲(chǔ)線(xiàn)性表的個(gè)元素(iWi呼n之前插入一個(gè)元素時(shí)需要向后移n-i+個(gè)元素.在一個(gè)長(zhǎng)度的順序存儲(chǔ)的線(xiàn)性表中，刪除個(gè)元素(iwi今田寸需要向前移n-個(gè)元素指指向非空循環(huán)單鏈hea的尾結(jié)點(diǎn)，滿(mǎn)p->next=hea已是帶頭結(jié)點(diǎn)的非空單鏈表，結(jié)點(diǎn)既不是第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，也不是最后一個(gè)結(jié)點(diǎn)，的答案中選擇合適的語(yǔ)句序列，實(shí)現(xiàn)刪結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列P->nexP->nex->nextP=P->next->nextwhil(P->next!=QP=P->nextwhil(P->next->next=QP=P->nex

5、tQ=PQ=P->nextP=L L=L->next; free(Q);9 在線(xiàn)性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)。10 單鏈表是線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)表示。11 棧是限定僅在表尾進(jìn)行插入或刪除操作的線(xiàn)性表。12 在棧頂指針為HS的鏈棧中，判定?？盏臈l件是HS=NULL。13 假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對(duì)輸入序列a、b、c、d、e進(jìn)行一系列棧操作SS后，得到的輸出序列為bceda。14 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過(guò)棧S,一個(gè)元素出棧后即Q。若這6個(gè)元素出隊(duì)列的順序是b、d、c、f、e、a,則棧S的容量至少應(yīng)該是

6、3。三、算法填空1 已知一個(gè)順序表中的元素按關(guān)鍵字值非遞減有序，下列算法刪除順序表中關(guān)鍵字相同的多余元關(guān)鍵字不同的元素在表中只保留一個(gè)。voidpurge_sq(SqList&la)/刪除順序表la中關(guān)鍵字相同的多余元素，即使操作之后的順序表中只保留操作之前表中所有按不相同的元素k=-1;/k指示新表的表尾for(i=0;i<La.length;+i)/順序考察表中每個(gè)元素j=0;while(j<=k&&la.elemj!=la.elemi)+j;/在新表中查詢(xún)是否存在和la.elemi相同的元素if(k=-1|j>k)/k=-1表明當(dāng)前考察的是第一個(gè)

7、元素la.elem+k=la.elemi;/forla.length=k+1;修改表長(zhǎng)/purge_sq2 一個(gè)頭指針為head的單鏈表，其中每個(gè)結(jié)點(diǎn)存放一個(gè)整數(shù)，以下算法將其拆分為兩個(gè)單鏈表head2,使headl中僅含有正整數(shù)，head2中僅含有負(fù)整數(shù)。voidseparate(LinkList&head,LinkList&head1,LinkList&head2)/將頭指針為head的單鏈表(帶頭結(jié)點(diǎn))拆分為兩個(gè)單鏈表head1和head2，/使head1中僅含有正整數(shù)，head2中僅含有負(fù)整數(shù)head1=(LinkList)malloc(sizeof(Lnode

8、);head1->next=NULL;head2=(LinkList)malloc(sizeof(Lnode);head2->next=NULL;p=head->next;while(p)q=p->next;if(p->data>=0)p->next=head1->next;head1->next=p;elsep->next=head2->next;head2->next=p;p=q;/whilefree(head);/seperat設(shè)一個(gè)長(zhǎng)度大的循環(huán)單鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針為指向該鏈表中某個(gè)結(jié)點(diǎn)的一個(gè)刪除該結(jié)點(diǎn)直接

9、前驅(qū)結(jié)點(diǎn)的算法voidelete(LinkLisp/在一個(gè)既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針的長(zhǎng)度大于一的循環(huán)鏈表中/刪除指所指的某個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)q=p/查結(jié)點(diǎn)的前驅(qū)結(jié)while(q->next!=pq=q->nextr=q/查結(jié)點(diǎn)的前驅(qū)結(jié)while(r->next!=qr=r->nextr->next=pfree(q)四、計(jì)算設(shè)有頭指針hea的單鏈表寫(xiě)算法要求在鏈表中查找元素值等的結(jié)點(diǎn)若找到則刪除復(fù)，直至所有值的元素全部刪除為止；若一個(gè)也找不到則給出相應(yīng)提示信息voielemdelete_x(LinkLis&l,ElemTypx/刪除頭指針hea的單鏈表中(帶頭結(jié)

10、點(diǎn))所有的值元n=0pre=l/記下結(jié)*的前p=l->nextwhile(p/順序考察表中每個(gè)元while(p&&p->data!=x)pre=p;p=p->next;/在表中查詢(xún)是否存在和x相同的元素if(p)/將結(jié)點(diǎn)p插入到新的表中pre->next=p->next;q=p;p=p->next;free(q);n+;/if/whileif(n=0)printf(“Notfno”un)d;x/elemdelete_x2有頭指針為head的單鏈表，寫(xiě)算法在鏈表中查找出所有按先后順序出現(xiàn)的元素x和y,并將x的所有結(jié)點(diǎn)全部刪除之。2voiddel

11、ete(LinkList&head,ElemTypex,ElemTypey)/在頭指針為head的單鏈表中查找出所有按先后順序出現(xiàn)的元素x和y，/并將x和y之間的所有結(jié)點(diǎn)全部刪除p=head->next;while(p)while(p&&p->data!=x)p=p->next;if(!p)exit(1);/沒(méi)找到xr=p->next;while(r&&r->data!=y)r=r->next;if(!r)exit(1);/沒(méi)找到相應(yīng)的ywhile(p->next!=r)q=p-next;p->next=q

12、->next;free(q);/while/while3 設(shè)某個(gè)單鏈表以la為頭指針，鏈表中每個(gè)元素均為整數(shù)且無(wú)序，寫(xiě)算法按遞增順序打印鏈表中方法是：反復(fù)找出鏈表中最小的元素，打印并刪除之，直至表空為止。3voidrearrange(LinkList&la)/將頭指針是la的單鏈表按遞增順序打印出來(lái)p=la->next;p1=la;while(p->next!=NULL)a=p->data;q1=p;q=p->next;while(q!=NULL)if(a>q->data)a=q->data;p1=q1;/ifq1=q;q=q->n

13、ext;/whiles=p1->next;printf(s->data);p1->next=p1->next->next;free(s);p1=la;p=la->next;/whileprintf(p->data);free(p);free(la);/rearrange4 設(shè)有一個(gè)頭指針為head的單鏈表，每個(gè)結(jié)點(diǎn)存放一個(gè)整數(shù)。寫(xiě)一算法將其按負(fù)整數(shù)在前部正整數(shù)在后部的次序存放(正整數(shù)與正整數(shù)之間、負(fù)整數(shù)與負(fù)整數(shù)之間不要求有序)，存儲(chǔ)空間仍占用原來(lái)的鏈表。4huafen(LinkList&L)/L為帶頭結(jié)點(diǎn)的單鏈表的頭指針10 / 12p=L-&

14、gt;next;while(p->next)p=p->next;pt=p;pr=p;p0=L;p=p0->next;3分while(p!=pr)if(p->data>='0'&&p->data<='9')p=p->next;p0=p;else2分p0->next=p->next;s=p;p=p->next;pt->next=s;s->next=NULL;pt=s;/huafen3分5 .設(shè)有一順序表a,寫(xiě)算法在表中查找先后出現(xiàn)的元素x和y,將x和y之間的元素逆置，逆置部分不包含x和y。若找不到相應(yīng)的x和y則給出提示信息。5voidrevert(ElemType&R,ints,intt)/本算法將數(shù)組R中下標(biāo)自s到t的元素逆置/即將(RRRR改變?yōu)?RRRRst,s+1,t-S,s+1,1,-1,t,tfor(k=s;k<=(s+t)/2;k+)w=Rk;Rk=Rt-k+s;Rt-k+s=w;/for/revertvoidexchange(SqList&a,ElemTypex,ElemTypey)/本算法實(shí)現(xiàn)在順序中查找先后出現(xiàn)的元之間