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

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

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

3、列的共同點是()A、都是先進后出B、都是先進先出C、只允許在端點處插入和刪除元素D沒有共同點10 . 一個隊列的入列序列是1 2 3 4 ,則隊列的輸出序列是()A 4 3 2 1B、1 2 3 4C、1 4 3 2D 3 2 4 111 .隊列與一般的線性表的區(qū)別在于()。A、數(shù)據(jù)元素的類型不同B、運算是否受限制C、數(shù)據(jù)元素的個數(shù)不同D邏輯結(jié)構(gòu)不同12 . “假上溢”現(xiàn)象會出現(xiàn)在()中。A、循環(huán)隊列B、隊列D順序隊列、填空題1 .數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖結(jié)構(gòu)2 .數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和用狀結(jié)構(gòu)。3 .下面程序段的時間復雜度是 O (n) |。

4、i=s=0;while (s<n) i+；s+； 4 .樹型結(jié)構(gòu)和圖形結(jié)構(gòu)合稱是非花性結(jié)構(gòu)。5 .在長度為n的順序存儲線性表的第i個元素(1&i & n)之前插入一個元素時,需要向后移動n-i+1個元素6 .在一個長度為n的順序存儲的線性表中，刪除第i個元素(1&i &n)時,7 .指針p指向非空循環(huán)單鏈表head的尾結(jié)點，則p滿足p->next=head,8 .已知L是帶頭結(jié)點的非空單鏈表，且 P結(jié)點既不是第一個數(shù)據(jù)結(jié)點，也不是最后一個結(jié)點,試 的答案中選擇合適的語句序列，實現(xiàn)刪除 P結(jié)點的直接后繼結(jié)點的語句序列是 J1_c P->next

5、= P->next ->next; P=P->next->next; while (P->next!=Q) P=P->next; while (P->next->next=Q) P=P->next; Q=P; Q=P->next; P=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 .假設以S和X

6、分別表示進棧和退棧操作，則對輸入序列 a、b、c、d、e進行一系列棧操作SS 后，得到的輸出序列為bcedk14 .設棧S和隊列Q的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過棧S, 一個元素出棧后即 若這6個元素出隊列的順序是b、d、c、f、e、a,則棧S的容量至少應該是3。三、算法填空1 .已知一個順序表中的元素按關(guān)鍵字值非遞減有序，下列算法刪除順序表中關(guān)鍵字相同的多余元 關(guān)鍵字不同的元素在表中只保留一個。void purge_sq(SqList &la)/刪除順序表la中關(guān)鍵字相同的多余元素，即使操作之后的順序表中只保留操作之前表中所有按 不相同的元素k= -1;/k指示新表

7、的表尾for (i=0;i<La.length;+i) /順序考察表中每個元素j=0；while (j<=k &&la.elemj!=la.elem(i)+j;| /在新表中查詢是否存在和la.elemi相同的元素if (k= = -1|j>k) /k= -1表明當前考察的是第一個元素la.elem+k= la.elemi;/forla.length=k+1; / 修改表長purge_sqhea2 .一個頭指針為head的單鏈表，其中每個結(jié)點存放一個整數(shù)，以下算法將其拆分為兩個單鏈表 使head 1中僅含有正整數(shù)，head 2中僅含有負整數(shù)。void sepa

8、rate(LinkList &head, LinkList &head1,LinkList &head2)將頭指針為head的單鏈表(帶頭結(jié)點)拆分為兩個單鏈表head1和head2,/使head1中僅含有正整數(shù)，head2中僅含有負整數(shù)head1=(LinkList)malloc(sizeof(Lnode); head1->next=NULL;head2=(LinkList)malloc(sizeof(Lnode) ; head2->next=NULL;p=head->next;while(p) q=p->next;if(p->data&

9、gt;=0)p->next=head1->next;head1->next=p;else p->next=head2->next;head2->next=p;p=q; /whilefree(head);/seperate3 .設一個長度大于1的循環(huán)單鏈表中，既無頭結(jié)點也無頭指針，p為指向該鏈表中某個結(jié)點的指 一個刪除該結(jié)點直接前驅(qū)結(jié)點的算法。void delete(LinkList p)/在一個既無頭結(jié)點也無頭指針的長度大于一的循環(huán)鏈表中，/刪除指針p所指的某個結(jié)點的直接前驅(qū)結(jié)點q二|p; 查找p結(jié)點的前驅(qū)結(jié)點qwhile(q->next!=p)q=q

10、>next;r=q; /查找q結(jié)點的前驅(qū)結(jié)點rwhile(r->next!=q)r=r->next;r->next=p;free(q)；J四、計算題1.設有頭指針為head的單鏈表。寫算法要求在鏈表中查找元素值等于x的結(jié)點，若找到則刪除之復，直至所有值為x的元素全部刪除為止；若一個也找不到則給出相應提示信息。1. void elemdelete_x(LinkList &l,ElemType x)/刪除頭指針為head的單鏈表中(帶頭結(jié)點)所有的值為 x的元素n=0; pre=l; /記下結(jié)點*p的前驅(qū)p=l->next;while(p) 順序考察表中每個元

11、素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( “ Notfound x n” );/elemdelete_x2 有頭指針為head的單鏈表，寫算法在鏈表中查找出所有按先后順序出現(xiàn)的元素x和y,并將的所有結(jié)點全部刪除之。3 void delete (LinkList &head , ElemType

12、x, ElemType y)/在頭指針為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); / 沒找到相應的ywhile(p->next!=r)q=p-next;p->next=q->next;free(

13、q);/while/while3設某個單鏈表以la 為頭指針，鏈表中每個元素均為整數(shù)且無序，寫算法按遞增順序打印鏈表中方法是：反復找出鏈表中最小的元素，打印并刪除之，直至表空為止。4 void rearrange(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->next;/

14、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.設有一個頭指針為head的單鏈表，每個結(jié)點存放一個整數(shù)。寫一算法將其按負整數(shù)在前部正整數(shù)在后部的次序存放(正整數(shù)與正整數(shù)之間、負整數(shù)與負整數(shù)之間不要求有序)，存儲空間仍占用原來的鏈表。5 huafen(LinkList &L)/L 為帶頭結(jié)點的單鏈表的頭指針p=L->next

15、;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)p0=p; p=p->next;else 2 分p0->next=p->next;s=p; p=p->next;pt->next=s; s->next=NULL;pt=s;/huafen 3 分6 設有一順序表a,寫算法在表中查找先后出現(xiàn)的元素x和y,將x和y之間的元素逆置,逆置部分不包含x和y0若找不到相應的x和y則給出提示信息。5 void revert(ElemType &R, int s,int t)/本算法將數(shù)組R中下標自s到t的元素逆置/ 即將(R,R+i,R-i, R)改變?yōu)?R R-i,R+i,R)for (k=s;k<=(s+t)/2;k+)w=Rk;Rk=Rt-k+s;Rt-k+s=w;/for/revertvoid exchange (SqList &a,ElemType x,ElemType y)本算法實現(xiàn)在順序表a中查找先后出現(xiàn)的元素x和y之間的元素逆置,/逆置部