1、基礎課程教學資料淵,您及彖人身體械、萬事如意'閡彖歡樂，祝福同學付財成長，,顏5取得好成靈為祖國奉獻力*11習題二、選擇題1.在一個長度為n的順序表中刪除第i個元素（0vi<n）時，需要向前移動（A）個元迎使用本奏禮祝您身體僮射萬事如意，彖歡樂。同學們1®鼾大樂的成長。早m為祖國的崇荒昌奉獻自己的力,素。A. n-iB. n-i+1C. n-i+1D.2.從一個具有n個元素的線性表中查找其值等于x的結點時，在查找成功的情況下，需平均比較（C）個元素結點。歡迎使用本奏禮 祝您身體僮射 萬事如意，彖歡樂。同學們1®鼾大樂的成長。早m為祖國的崇荒昌奉獻自己的力,A.

2、 n/2C. (n-1)/2 D. (n +1)/23 .對一個具有A. O（n）n個元素的線性表，建立其單鏈表的時間復雜度為8. O（1）C. O（n2）D.(A)。O (longzn)4 .線性表采用鏈式存儲時，其地址 （D ）。A.必須是連續的B. 一定是不連續的C.部分地址必須連續D.連續與否均可以5.在一個具有n個結點的有序單鏈表中插人一個新的結點，使得鏈表仍然有序，該算法的時間復雜度是（D）。A. O （long2n）6.線性表是（A ）。A. 一個有限序列,C. 一個無限序列,B. O可以為空可以為空C. O (n2)D. O (n)B. 一個有限序列，不可以為空D. 一個無限序

3、列，不可以為空向第i個元素（0 1 v n+1）之前捕人一個新元素時,7.在一個長度為n的順序表中,需要向后移動（B）個元素。A . n-iB . n-i + 18.如果某鏈表中最常用的操作是取第 時間。A.單鏈表B.雙向鏈表C.n-i-1D.i+1i個結點及其前驅，則采用（D）存儲方式最節省C.單循環鏈表D.順序表9 .一個順序存儲線性表的第一個元素的存儲地址是90,每個元素的長度是2,則第6個元素的存儲地址是（B）。A.98B.100C.102D.10610 .下列排序方法中，某一趟結束后未必能選出一個元素放在其最終位置上的是（C）。A.堆排序B.冒泡排序C.直接插人排序D.快速排序11

4、.對線性表進行二分查找時，要求線性表必須（C）。A.以順序方法存儲B.以鏈接方法存儲C.以順序方法存儲，且結點接關鍵字有序排列D.以鏈接方法存儲，且結點接關鍵字有序排列12,在順序存儲的線性表（a1an）中，刪除任意一個結點所需移動結點的平均移動次數為（C）A.nB.n/2C.（n-1）/2D.（n+l）/213 .在線性表的下列存儲結構中，讀取元素花費的時間最少的是（D）。A.單鏈表B.雙鏈表C.循環鏈表D.順序表14 .若某鏈表中最常用的操作為在最后一個結點之后插入一個結點和刪除最后一個結點，則采用（D）存儲方式最節省時間。A.雙鏈表B.單鏈表C.單循環鏈表D.帶頭結點的雙循環鏈表二、填空

5、題1 .線性表（LinearList）是最簡單、最常用的一種數據結構。線性表中的元素存在著一對一的相互關系。2 .線性表中有且僅有一個開始結點，表中有且僅有一個終端結點，除開始結點外，其他每個元素有巨僅有一個直接前驅，除終端結點外，其他每個元素有且僅有一個直接后繼3 .線性表是n（n>=0）個數據元素的有限序列。其中n為數據元素的個數，定義為線性表的長度。當n為零時的表稱為空表。4 .所謂順序表（SequentialLISt）是線性表的順序存儲結構，它是將線性表中的結點按其邏輯順序依次存放在內存中一組連續的存儲單元中,使線性表中相鄰的結點存放在地址相組的存儲單元中。5 .單鏈表不要求邏輯

6、上相鄰的存儲單元在物理上也一定要相鄰。它是分配一些任意的存儲單元來存儲線性表中的數據元素，這些存儲單元可以分散在內存中的任意的位置上,它們在物理上可以是一片連續的存儲單元，也可以是不連續的。因此在表示線性表這種數據結構時，必須在存儲線性表元素的同時，也存儲線性表的邏輯關系。6 .線性表的鏈式存儲結構的每一個結點（Node）需要包括兩個部分：一部分用來存放元素的數據信息，稱為結點的數據蛇；另一部分用來存放元素的指向直接后繼元素的指針（即直接后繼元素的地址信息），稱為指針域或鏈域。7 .線性鏈表的邏輯關系是通過每個結點指針域中的指針來表示的。其邏輯順序和物理存儲順序不再一致，而是一種非順序存儲結構

7、,又稱為非順序映像。8 .如果將單鏈表最后一個結點的指針域改為存放鏈表中的頭結點的地址值，這樣就構成了循環鏈表9 .為了能夠快速地查找到線性表元素的直接前驅，可在每一個元素的結點中再增加一個指向其前驅的指針域，這樣就構成了雙向鏈表。10 .雙向鏈表某結點的指針P,它所指向結點的后繼的前驅與前驅的后繼都是p所指向的結點本身。11 .在單鏈表中，刪除指針P所指結點的后繼結點的語句是P->next=p->next->nextO12 .在雙循環鏈表中，刪除指針P所指結點的語句序列是P->prior->next=p->next及P->next->prior

8、=P->prior_。13 .單鏈表是線性表的鏈接存儲表示。14 .可以使用雙鏈表表示樹形結構。15 .向一個長度為n的向量的第i個元素（lwiWn+1）之前插人一個元素時，需向后移動n-i+1個元素。16 .刪除一個長度為n的向量的第i個元素（lwiwn）時，需向前移動n-i個元素。17 .在單鏈表中，在指針P所指結點的后面插人一個結點S的語句序列是S->next=P->next;P->next=S18 .在雙循環鏈表中，在指針P所指結點前插人指針S所指的結點，需執行語句p->prior->next=S;s->prior=p->prior;p-

9、>prior=s;19 .取出廣義表A=(x,(a,b,c,d)中原子c的函數是head(tail(tail(head(tail(head(A)。20 .在一個具有n個結點的有序單鏈表中插人一個新結點并使之仍然有序的時間復雜度為On_。21 .寫出帶頭結點的雙向循環鏈表L為空表的條件(L=L->Next)&&(L=L->Prior)22 .線性表、棧和隊列都是線性結構。23 .向棧中插人元素的操作是先移動棧地針，再存人元素。三、判斷題1 .線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續的。(錯)2 .在具有頭結點的鏈式存儲結構中，頭指針指向鏈表中的

10、第一個數據結點。(錯)3 .順序存儲的線性表不可以隨機存取。(錯)4 .單鏈表不是一種隨機存儲結構。(對)5 .順序存儲結構線性表的插入和刪除運算所移動元素的個數與該元素的位置無關。(錯)6 .順序存儲結構是動態存儲結構，鏈式存儲結構是靜態存儲結構。(錯)7 .線性表的長度是線性表所占用的存儲空間的大小。(錯)8 .雙循環鏈表中，任意一結點的后繼指針均指向其邏輯后繼。(錯)9 .線性表的惟一存儲形式是鏈表。(錯)四、綜合題1.編寫一個將帶頭結點單鏈表逆置的算法。voidreverse_list(linklist*head)-/*逆置帶頭結點的單鏈表*/linklist*s,*p;p=head-

11、>next;/*p指向線性表的第一個元素*/head->next=NULL;/*初始空表*/while(p!=NULL)s=p；p=p->next;s->next=head->next;head->next=s;/*將s結點插入逆表*/*reverse_list*/2.ha和hb分別是兩個按升序排列的、帶頭結點的單鏈表的頭指針，設計一個算法，把這兩個單鏈表合并成一個按升序排列的單鏈表，并用hC指向它的頭結點。linklist*combine_list(linklist*ha,linklist*hb)/*ha,hb分別是兩個按升序排列的,帶有頭結點的單鏈表的頭

12、指針，設計一個算法，把這兩個單鏈表合并成一個按升序排列的單鏈表,并用hc指向它的頭結點*/linklist*hc,*pa,*pb,*pc,*p,*q,*r;hc=(linklist*)malloc(sizeof(linklist);/*建立hc頭結點*/p=hc；pa=ha->next;free(ha);/*釋放ha頭結點*/pb=hb->next;free(hb);/*釋放hb頭結點*/while(pa!=NULL&&pb!=NULL)q=(linklist*)malloc(sizeof(linklist);/*產生新結點*/if(pb->data<p

13、a->data)q->data=pb->data;pb=pb->next;elseq->data=pa->data;pa=pa->next;if(pa->data=pb->data)/*將相同的元素刪除*/r=pb;pb=pb->next;free(r);p->next=q;/*p=q;while(pa!=NULL)q=(linklist(linklist);q->data=pa->data;pa=pa->next;p->next=q;p=q;while(pb!=NULL)/*bq=(linklist(l

14、inklist);q->data=pb->data;pb=pb->next;p->next=q;p=q;將結點鏈入c鏈表*/*a鏈表非空*/*)malloc(sizeof鏈表非空*/*)malloc(sizeofp->next=NULL;return(hc);/*返回*/3.有一個帶頭結點的單鏈表，頭指針為head,編寫一個算法count.list()計算所有數據域為X的結點的個數(不包括頭結點)。intcount_list(linklist*head)/*在帶頭結點的單鏈表中計算所有數據域為x的結點的個數*/linklist*p;intn;p=head->

15、next;/*p指向鏈表的第一個結點*/n=0;while(p!=NULL)if(p->data=x)n+;p=p->next;return(n);/*返回結點個數*/*count_list*/4 .在一個帶頭結點的單鏈表中，頭指針為head,它的數據域的類型為整型，而且按由小到大的順序排列，編寫一個算法insertx_list(),在該鏈表中插人值為x的元素，并使該鏈表仍然有序linklist*insertx_list(linklist*head,intx)/*在帶頭結點的單鏈表中插入值為x的元素，使該鏈表仍然有序*/linklist*s,*p,*q;s=(linklist*)m

16、alloc(sizeof(linklist);/*建立數據域為x的結點*/s->data=x;s->next=NULL;if(head->next=NULL|x<head->next->data)/*若單鏈表為空或x小于鏈表第一個結點的數據域*/s->next=head->next;head->next=s;elseq=head->next;p=q->next;while(p!=NULL&&x>p->data)q=p；p=p->next;s->next=p;q->next=s;/*i

17、f*/*insertx_list*/o5 .在一個帶頭結點的單鏈表中，head為其頭指針，p指向鏈表中的某一個結點，編寫算法swapin.list(),實現p所指向的結點和p的后繼結點相互交換。linklist*swapin_list(linklist*head,linklist*p)/*在帶頭結點的單鏈表中，實現p所指向的結點和p的后繼結點相互交換*/linklist*q,*r,*s;q=p->next;/*q為p的后繼*/if(q!=NULL)/*若p有后繼結點*/if(p=head)/*若p指向頭結點*/head=head->next;s=head->next;head

18、->next=p;p->next=s;else/*p不指向頭結點*/r=head;/*定位p所指向結點的前驅*/while(r->next!=p)r=r->next;r->next=q;/*交換p和q所指向的結點*/p->next=q->next;q->next=p;return(head);else/*p不存在后繼*/return(NULL);/*swapin_list*/6有一個帶頭結點的單鏈表，所有元素值以非遞減有序排列，head為其頭指針，編寫算法deldy.list()將linklist*deldy_list(linklist*head)/*在帶頭結點的非遞減有序單鏈表，將該鏈表中多余的元素值相同的結點刪除*/linklist*q;if(head->next!=NULL)/*判斷鏈表是否為空*/p=head->next;while(p->next!=NULL)if(p->data!=p->next->data)p=p->next;elseq=p->next;/*q指向p的后繼*/p->next=q->next;/*刪除q所指向的結點*/free(q);/*釋放結點空間*/*while*/牛*/ret