大學(xué)計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)習(xí)題2VIP

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

2、 n/2C. (n-1)/2 D. (n +1)/23 .對(duì)一個(gè)具有A. O（n）n個(gè)元素的線性表，建立其單鏈表的時(shí)間復(fù)雜度為8. O（1）C. O（n2）D.(A)。O (longzn)4 .線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址 （D ）。A.必須是連續(xù)的B. 一定是不連續(xù)的C.部分地址必須連續(xù)D.連續(xù)與否均可以5.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插人一個(gè)新的結(jié)點(diǎn)，使得鏈表仍然有序，該算法的時(shí)間復(fù)雜度是（D）。A. O （long2n）6.線性表是（A ）。A. 一個(gè)有限序列,C. 一個(gè)無(wú)限序列,B. O可以為空可以為空C. O (n2)D. O (n)B. 一個(gè)有限序列，不可以為空D. 一個(gè)無(wú)限序

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

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

5、題1 .線性表（LinearList）是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表中的元素存在著一對(duì)一的相互關(guān)系。2 .線性表中有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)，表中有且僅有一個(gè)終端結(jié)點(diǎn)，除開(kāi)始結(jié)點(diǎn)外，其他每個(gè)元素有巨僅有一個(gè)直接前驅(qū)，除終端結(jié)點(diǎn)外，其他每個(gè)元素有且僅有一個(gè)直接后繼3 .線性表是n（n>=0）個(gè)數(shù)據(jù)元素的有限序列。其中n為數(shù)據(jù)元素的個(gè)數(shù)，定義為線性表的長(zhǎng)度。當(dāng)n為零時(shí)的表稱為空表。4 .所謂順序表（SequentialLISt）是線性表的順序存儲(chǔ)結(jié)構(gòu)，它是將線性表中的結(jié)點(diǎn)按其邏輯順序依次存放在內(nèi)存中一組連續(xù)的存儲(chǔ)單元中,使線性表中相鄰的結(jié)點(diǎn)存放在地址相組的存儲(chǔ)單元中。5 .單鏈表不要求邏輯

6、上相鄰的存儲(chǔ)單元在物理上也一定要相鄰。它是分配一些任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素，這些存儲(chǔ)單元可以分散在內(nèi)存中的任意的位置上,它們?cè)谖锢砩峡梢允且黄B續(xù)的存儲(chǔ)單元，也可以是不連續(xù)的。因此在表示線性表這種數(shù)據(jù)結(jié)構(gòu)時(shí)，必須在存儲(chǔ)線性表元素的同時(shí)，也存儲(chǔ)線性表的邏輯關(guān)系。6 .線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的每一個(gè)結(jié)點(diǎn)（Node）需要包括兩個(gè)部分：一部分用來(lái)存放元素的數(shù)據(jù)信息，稱為結(jié)點(diǎn)的數(shù)據(jù)蛇；另一部分用來(lái)存放元素的指向直接后繼元素的指針（即直接后繼元素的地址信息），稱為指針域或鏈域。7 .線性鏈表的邏輯關(guān)系是通過(guò)每個(gè)結(jié)點(diǎn)指針域中的指針來(lái)表示的。其邏輯順序和物理存儲(chǔ)順序不再一致，而是一種非順序存儲(chǔ)結(jié)構(gòu)

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

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

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

10、第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。(錯(cuò))3 .順序存儲(chǔ)的線性表不可以隨機(jī)存取。(錯(cuò))4 .單鏈表不是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。(對(duì))5 .順序存儲(chǔ)結(jié)構(gòu)線性表的插入和刪除運(yùn)算所移動(dòng)元素的個(gè)數(shù)與該元素的位置無(wú)關(guān)。(錯(cuò))6 .順序存儲(chǔ)結(jié)構(gòu)是動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是靜態(tài)存儲(chǔ)結(jié)構(gòu)。(錯(cuò))7 .線性表的長(zhǎng)度是線性表所占用的存儲(chǔ)空間的大小。(錯(cuò))8 .雙循環(huán)鏈表中，任意一結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。(錯(cuò))9 .線性表的惟一存儲(chǔ)形式是鏈表。(錯(cuò))四、綜合題1.編寫一個(gè)將帶頭結(jié)點(diǎn)單鏈表逆置的算法。voidreverse_list(linklist*head)-/*逆置帶頭結(jié)點(diǎn)的單鏈表*/linklist*s,*p;p=head-

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

12、指針，設(shè)計(jì)一個(gè)算法，把這兩個(gè)單鏈表合并成一個(gè)按升序排列的單鏈表,并用hc指向它的頭結(jié)點(diǎn)*/linklist*hc,*pa,*pb,*pc,*p,*q,*r;hc=(linklist*)malloc(sizeof(linklist);/*建立hc頭結(jié)點(diǎn)*/p=hc；pa=ha->next;free(ha);/*釋放ha頭結(jié)點(diǎn)*/pb=hb->next;free(hb);/*釋放hb頭結(jié)點(diǎn)*/while(pa!=NULL&&pb!=NULL)q=(linklist*)malloc(sizeof(linklist);/*產(chǎn)生新結(jié)點(diǎn)*/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;將結(jié)點(diǎn)鏈入c鏈表*/*a鏈表非空*/*)malloc(sizeof鏈表非空*/*)malloc(sizeofp->next=NULL;return(hc);/*返回*/3.有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，頭指針為head,編寫一個(gè)算法count.list()計(jì)算所有數(shù)據(jù)域?yàn)閄的結(jié)點(diǎn)的個(gè)數(shù)(不包括頭結(jié)點(diǎn))。intcount_list(linklist*head)/*在帶頭結(jié)點(diǎn)的單鏈表中計(jì)算所有數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)的個(gè)數(shù)*/linklist*p;intn;p=head->

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

16、alloc(sizeof(linklist);/*建立數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)*/s->data=x;s->next=NULL;if(head->next=NULL|x<head->next->data)/*若單鏈表為空或x小于鏈表第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域*/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 .在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，head為其頭指針，p指向鏈表中的某一個(gè)結(jié)點(diǎn)，編寫算法swapin.list(),實(shí)現(xiàn)p所指向的結(jié)點(diǎn)和p的后繼結(jié)點(diǎn)相互交換。linklist*swapin_list(linklist*head,linklist*p)/*在帶頭結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)p所指向的結(jié)點(diǎn)和p的后繼結(jié)點(diǎn)相互交換*/linklist*q,*r,*s;q=p->next;/*q為p的后繼*/if(q!=NULL)/*若p有后繼結(jié)點(diǎn)*/if(p=head)/*若p指向頭結(jié)點(diǎn)*/head=head->next;s=head->next;head

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