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

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

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

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

4、線性結(jié)構(gòu).在長度的順序存儲線性表的個元素(iWi呼n之前插入一個元素時需要向后移n-i+個元素.在一個長度的順序存儲的線性表中，刪除個元素(iwi今田寸需要向前移n-個元素指指向非空循環(huán)單鏈hea的尾結(jié)點，滿p->next=hea已是帶頭結(jié)點的非空單鏈表，結(jié)點既不是第一個數(shù)據(jù)結(jié)點，也不是最后一個結(jié)點，的答案中選擇合適的語句序列，實現(xiàn)刪結(jié)點的直接后繼結(jié)點的語句序列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 在線性結(jié)構(gòu)中，第一個結(jié)點無前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點。10 單鏈表是線性表的鏈式存儲表示。11 棧是限定僅在表尾進行插入或刪除操作的線性表。12 在棧頂指針為HS的鏈棧中，判定?？盏臈l件是HS=NULL。13 假設(shè)以S和X分別表示進棧和退棧操作，則對輸入序列a、b、c、d、e進行一系列棧操作SS后，得到的輸出序列為bceda。14 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過棧S,一個元素出棧后即Q。若這6個元素出隊列的順序是b、d、c、f、e、a,則棧S的容量至少應(yīng)該是

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

7、元素la.elem+k=la.elemi;/forla.length=k+1;修改表長/purge_sq2 一個頭指針為head的單鏈表，其中每個結(jié)點存放一個整數(shù)，以下算法將其拆分為兩個單鏈表head2,使headl中僅含有正整數(shù)，head2中僅含有負整數(shù)。voidseparate(LinkList&head,LinkList&head1,LinkList&head2)/將頭指針為head的單鏈表(帶頭結(jié)點)拆分為兩個單鏈表head1和head2，/使head1中僅含有正整數(shù)，head2中僅含有負整數(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è)一個長度大的循環(huán)單鏈表中，既無頭結(jié)點也無頭指針為指向該鏈表中某個結(jié)點的一個刪除該結(jié)點直接

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

10、點)所有的值元n=0pre=l/記下結(jié)*的前p=l->nextwhile(p/順序考察表中每個元while(p&&p->data!=x)pre=p;p=p->next;/在表中查詢是否存在和x相同的元素if(p)/將結(jié)點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àn)的元素x和y,并將x的所有結(jié)點全部刪除之。2voiddel

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

12、->next;free(q);/while/while3 設(shè)某個單鏈表以la為頭指針，鏈表中每個元素均為整數(shù)且無序，寫算法按遞增順序打印鏈表中方法是：反復(fù)找出鏈表中最小的元素，打印并刪除之，直至表空為止。3voidrearrange(LinkList&la)/將頭指針是la的單鏈表按遞增順序打印出來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è)有一個頭指針為head的單鏈表，每個結(jié)點存放一個整數(shù)。寫一算法將其按負整數(shù)在前部正整數(shù)在后部的次序存放(正整數(shù)與正整數(shù)之間、負整數(shù)與負整數(shù)之間不要求有序)，存儲空間仍占用原來的鏈表。4huafen(LinkList&L)/L為帶頭結(jié)點的單鏈表的頭指針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àn)的元素x和y,將x和y之間的元素逆置，逆置部分不包含x和y。若找不到相應(yīng)的x和y則給出提示信息。5voidrevert(ElemType&R,ints,intt)/本算法將數(shù)組R中下標自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)/本算法實現(xiàn)在順序中查找先后出現(xiàn)的元之間