Ch2習(xí)題參考答案

第二章習(xí)題參照答案一、判斷題1．線性表的邏輯次序與存儲(chǔ)次序總是一致的。(ERROR)2．次序存儲(chǔ)的線性表可以按序號(hào)隨機(jī)存取。(OK)3．次序表的插入和刪除一種數(shù)據(jù)元素，由于每次操作平均只有近二分之一的元素需要移動(dòng)。（OK）4．線性表中的元素可以是多種各樣的，但同一線性表中的數(shù)據(jù)元素具有相似的特性，因此是屬于同一數(shù)據(jù)對(duì)象。（OK）5．在線性表的次序存儲(chǔ)構(gòu)造中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。（ERROR）6．在線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造中，邏輯上相鄰的元素在物理位置上不一定相鄰。（OK）7．線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造優(yōu)于次序存儲(chǔ)構(gòu)造。（ERROR）8．在線性表的次序存儲(chǔ)構(gòu)造中，插入和刪除時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。（OK）9．線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造是用一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中數(shù)據(jù)元素的。（OK）10．在單鏈表中，要獲得某個(gè)元素，只要懂得該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)構(gòu)造。（ERROR）二、單項(xiàng)選擇題、(請(qǐng)從下列A，B，C，D選項(xiàng)中選擇一項(xiàng))11．線性表是(A)。(A)一種有限序列，可認(rèn)為空；(B)一種有限序列，不能為空；(C)一種無(wú)限序列，可認(rèn)為空；(D)一種無(wú)序序列，不能為空。12．對(duì)次序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作都是等概率的。插入一種元素時(shí)平均要移動(dòng)表中的（A）個(gè)元素。(A)n/2(B)(n+1)/2(C)(n–1)/2(D)n13．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址(D)。(A)必須是持續(xù)的；(B)部分地址必須是持續(xù)的；(C)一定是不持續(xù)的；(D)持續(xù)與否均可以。14．用鏈表表達(dá)線性表的長(zhǎng)處是（C）。(A)便于隨機(jī)存取(B)花費(fèi)的存儲(chǔ)空間較次序存儲(chǔ)少(C)便于插入和刪除(D)數(shù)據(jù)元素的物理次序與邏輯次序相似15.某鏈表中最常用的操作是在最終一種元素之后插入一種元素和刪除最終一種元素，則采用(D)存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。(A)單鏈表(B)雙鏈表(C)單循環(huán)鏈表(D)帶頭結(jié)點(diǎn)的雙循環(huán)鏈表16.循環(huán)鏈表的重要長(zhǎng)處是(D)。(A)不再需要頭指針了(B)已知某個(gè)結(jié)點(diǎn)的位置后，可以輕易找到他的直接前趨(C)在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不停開(kāi)(D)從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表17.下面有關(guān)線性表的論述錯(cuò)誤的是(B)。線性表采用次序存儲(chǔ)，必須占用一片地址持續(xù)的單元；線性表采用次序存儲(chǔ)，便于進(jìn)行插入和刪除操作；線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片地址持續(xù)的單元；線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作；18.單鏈表中，增長(zhǎng)一種頭結(jié)點(diǎn)的目的是為了（C）。(A)使單鏈表至少有一種結(jié)點(diǎn)(B)標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置（C）以便運(yùn)算的實(shí)現(xiàn)(D)闡明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)19.若某線性表中最常用的操作是在最終一種元素之后插入一種元素和刪除第一種元素，則采用（D）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。(A)單鏈表(B)僅有頭指針的單循環(huán)鏈表(C)雙鏈表(D)僅有尾指針的單循環(huán)鏈表20.若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間（B）。(A)單鏈表(B)次序表(C)雙鏈表(D)單循環(huán)鏈表21.一種向量(一種次序表)第一種元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是_______。A.110B.108C.100D.120答：B[第5個(gè)元素的地址=100+2*(5-1)=108]22.不帶頭結(jié)點(diǎn)的單鏈表head為空的鑒定條件是______。A.head==NULL;B.head->next==NULL;C.head->next==head;D.head!=NULL;答：A23.帶頭結(jié)點(diǎn)的單鏈表head為空的鑒定條件是______。A.head==NULL;B.head->next==NULL;C.head->next==head;D.head!=NULL;答：B24.在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是_____。A.p->right=s;s->left=p;p->right->left=s;s=->right=p->right;B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;答：D25.在一種單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行______。A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;答：C26.從一種具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的狀況下，需平均比較_____個(gè)結(jié)點(diǎn)。(參見(jiàn)網(wǎng)上講義：1.4.2例1_5)A.n;B.n/2;C.(n-1)/2;D.(n+1)/2;答：D27.給定有n個(gè)結(jié)點(diǎn)的向量，建立一種有序單鏈表的時(shí)間復(fù)雜度_______。A.O(1);B.O(n);C.O(n);D.O(nlogn);答：C三、填空題28.在一種長(zhǎng)度為n的向量中的第i個(gè)元素(1≤i≤n)之前插入一種元素時(shí)，需向后移動(dòng)_____個(gè)元素。答：n-i+129.在一種長(zhǎng)度為n的向量中刪除第i個(gè)元素(1≤i≤n)時(shí)，需向前移動(dòng)_____個(gè)元素。答：n-i30．在一種單鏈表中p所指結(jié)點(diǎn)之前插入一種由指針s所指結(jié)點(diǎn)，可執(zhí)行如下操作：s->next=__p->next_____;p->next=s;t=p->data;p->data=___s->data________;s->data=___t________;四、算法設(shè)計(jì)題：31.有一種單鏈表（不一樣結(jié)點(diǎn)的數(shù)據(jù)域值也許相似），其頭指針為head，編寫(xiě)一種函數(shù)計(jì)算數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)個(gè)數(shù)。解：本題是遍歷通過(guò)該鏈表的每個(gè)結(jié)點(diǎn)，每碰到一種結(jié)點(diǎn)，結(jié)點(diǎn)個(gè)數(shù)加1，結(jié)點(diǎn)個(gè)數(shù)存儲(chǔ)在變量n中。實(shí)現(xiàn)本題功能的函數(shù)如下：intcount(head,x)node*head;ElemTypex;{/*本題中head為鏈頭指針，不含頭結(jié)點(diǎn)*/node*p;intn=0;p=head;while(p!=NULL){if(p->data==x)n++;p=p->next;}return(n);}32.有一種有序單鏈表（從小到大排序），表頭指針為head，編寫(xiě)一種函數(shù)向該單鏈表中插入一種元素為x的結(jié)點(diǎn)，使插入后該鏈表仍然有序。解：本題算法的思想是先建立一種待插入的結(jié)點(diǎn)，然后依次與鏈表中的各結(jié)點(diǎn)的數(shù)據(jù)域比較大小，找出該結(jié)點(diǎn)的位置，最終插入該結(jié)點(diǎn)。實(shí)現(xiàn)本題功能的函數(shù)如下：node*insertorder(head,x)node*head;ElemTypex;{/*本題中head為鏈頭指針，不含頭結(jié)點(diǎn)*/node*s,*p,*q;s=(node*)malloc(sizeof(node));/*建立一種待插入的結(jié)點(diǎn)*/s->data=x;s->next=NULL;if(head==NULL‖x<head->data)/*若單鏈表為空或x不不小于第一種結(jié)點(diǎn)的data域*/{s->next=head;/*則把s結(jié)點(diǎn)插入到表頭背面*/head=s;}else{q=head;/*為s結(jié)點(diǎn)尋找插入位置,p指向待比較的結(jié)點(diǎn),q指向p的前驅(qū)結(jié)點(diǎn)*/p=q->next;while(p!=NULL&&x>p->data)/*若x不不小于p所指向的data域值*/if(x>p->data){q=p;p=p->next;}s->next=p;/*將s結(jié)點(diǎn)插入到q和p之間*/q->next=s;}return(head);}33．編寫(xiě)一種函數(shù)將一種頭指針為a的單鏈表A分解成兩個(gè)單鏈表A和B，其頭指針?lè)謩e為a和b，使得A鏈表中具有原鏈表A中序號(hào)為奇數(shù)的元素，而B(niǎo)鏈表中具有原鏈表A中序號(hào)為偶數(shù)的元素，且保持本來(lái)的相對(duì)次序。解：其函數(shù)是將單鏈表A中的所有偶數(shù)序號(hào)的結(jié)點(diǎn)刪除，并在刪除時(shí)把這些結(jié)點(diǎn)鏈接起來(lái)構(gòu)成單鏈表B。實(shí)現(xiàn)本題功能的函數(shù)如下：voiddisa(a,b)node*a,*b;{/*本題中a、b為鏈頭指針，不含頭結(jié)點(diǎn)*/node*r,*p,*q;p=a;b=a->next;r=b;while(p!=NULL&&p->next!=NULL){q=p->next;/*q指向偶數(shù)序號(hào)的結(jié)點(diǎn)*/p->next=q->next;/*將q從原A中刪除掉*/r->next=q;/*將q結(jié)點(diǎn)鏈接到B鏈表的末尾*/r=q/*r總是指向B鏈表的最終一種結(jié)點(diǎn)*/p=p->next;/*p指向原鏈表A中的奇數(shù)序號(hào)的結(jié)點(diǎn)*/}r->next=NULL;/*將生成B鏈表中的最終一種結(jié)點(diǎn)的next域置空*/}34.假設(shè)有兩個(gè)已排序的單鏈表A和B，編寫(xiě)一種函數(shù)將它們合并成一種鏈表C而不變化其排序性。解：這里采用鏈表合并的措施，設(shè)原兩鏈表的頭指針?lè)謩e為p和q，每次比較p->data和q->data的值，把值較小的結(jié)點(diǎn)作為新鏈表的結(jié)點(diǎn)，這一過(guò)程直到一種鏈表為空為止。當(dāng)一種鏈表為空而另一種鏈表不為空時(shí)，只要將不空的鏈表指針賦給新鏈表中最終一種結(jié)點(diǎn)的指針即可。實(shí)現(xiàn)本題功能的函數(shù)如下：node*mergelink(p,q)node*p,*q;{/*本題中p、q為鏈頭指針，不含頭結(jié)點(diǎn)。*//*但為操作以便，過(guò)程中要為鏈表C建立一種臨時(shí)頭結(jié)點(diǎn)。*/node*h,*r;h=(node*)malloc(sizeof(node));/*建立頭結(jié)點(diǎn)*/h->next=NULL;r=h;while(p!=NULL&&q!=NULL)if(p->data<=q->data){r->next=p;r=p;p=p->next;}else{r->next=q;r=q;q=q->next;}if(p==NULL)/*若A鏈表的結(jié)點(diǎn)已取完，則把B的所有余下的結(jié)點(diǎn)鏈接C中*/r->next=q;if(q==NULL)/*若A鏈表的結(jié)點(diǎn)已取完，則把B的所有余下的結(jié)點(diǎn)鏈接C中*/r->next=p;/*下面三句要去掉鏈表C的頭結(jié)點(diǎn)，假如不想去掉，則不要這三句*/p=h->next;h=h->next;free(p);returnh;}35．設(shè)A=（a,…,a）和B=（b,…,bn）均為次序表，A’和B’分別為A和B中除去最大共同前綴后的子表（例如，A=（x，y，y，z，x，z），B=（x，y，y，z，y，x，x，z），則兩者中最大的共同前綴為（x,y,y,z），在A’=B’=空表，則A=B；若A’=空表，而B(niǎo)’<>空表，或者兩者均不為空表，且A’的首元不不小于B’的首元，則A<B；否則A>B。（詞典次序）試寫(xiě)一種比較A，B大小的算法（在算法中，不要破壞原表A和B，并且不一定先求得A’和B’才進(jìn)行比較）。36.設(shè)有一種用向量表達(dá)的線性表L，規(guī)定寫(xiě)出一種將該表逆置的過(guò)程，并容許在原表的存儲(chǔ)空間外再增長(zhǎng)一種附加的工作單元。(朱儒榮,C語(yǔ)言版數(shù)據(jù)構(gòu)造考研例題)解：用數(shù)據(jù)類(lèi)型描述Seqlist次序存儲(chǔ)構(gòu)造：voldconverts(seqlistL){k=L.length;m=k/2;for(i=0;i<m;i++){x=L.element[i];L.element[i]=L.element[k-i-1];L.element[k-i-1]=x;}}//converts討論：這個(gè)算法過(guò)程只須進(jìn)行數(shù)據(jù)元素的互換操作，其重要時(shí)間花費(fèi)在for循環(huán)上，整個(gè)算法的時(shí)間復(fù)雜度為O(k)。37.已知兩個(gè)整數(shù)集合A和B，它們的元素分別依元素值遞增有序寄存在兩個(gè)單鏈表HA和HB中，編寫(xiě)一種函數(shù)求出這兩個(gè)集合的并集C,并規(guī)定集合C的鏈表的結(jié)點(diǎn)仍依元素值遞增有序寄存。(提醒：求并集不是歸并!)38．已知兩個(gè)次序表A和B分別表達(dá)兩個(gè)集合，其元素遞增排列，編寫(xiě)一種函數(shù)求出A和B的交集C，規(guī)定C同樣以元素遞增的次