Ch2習(xí)題參考答案

第二章習(xí)題參考答案一、判斷題1．線性表的邏輯次序與存儲(chǔ)次序總是一致的。(ERROR)2．次序存儲(chǔ)的線性表能夠按序號(hào)隨機(jī)存取。(OK)3．次序表的插入和刪除一種數(shù)據(jù)元素，由于每次操作平均只有近二分之一的元素需要移動(dòng)。（OK）4．線性表中的元素能夠是多個(gè)各樣的，但同一線性表中的數(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ǔ)單元來存儲(chǔ)線性表中數(shù)據(jù)元素的。（OK）10．在單鏈表中，要獲得某個(gè)元素，只要懂得該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)構(gòu)造。（ERROR）二、單選題、(請(qǐng)從下列A，B，C，D選項(xiàng)中選擇一項(xiàng))11．線性表是(A)。(A)一種有限序列，可覺得空；(B)一種有限序列，不能為空；(C)一種無限序列，可覺得空；(D)一種無序序列，不能為空。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á)線性表的優(yōu)點(diǎn)是（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)鏈表的重要優(yōu)點(diǎn)是(D)。(A)不再需要頭指針了(B)已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到他的直接前趨(C)在進(jìn)行插入、刪除運(yùn)算時(shí)，能更加好的確保鏈表不停開(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.單鏈表中，增加一種頭結(jié)點(diǎn)的目的是為了（C）。(A)使單鏈表最少有一種結(jié)點(diǎn)(B)標(biāo)記表結(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)。(參見網(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，編寫一種函數(shù)計(jì)算數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)個(gè)數(shù)。解：本題是遍歷通過該鏈表的每個(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，編寫一種函數(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．編寫一種函數(shù)將一種頭指針為a的單鏈表A分解成兩個(gè)單鏈表A和B，其頭指針分別為a和b，使得A鏈表中含有原鏈表A中序號(hào)為奇數(shù)的元素，而B鏈表中含有原鏈表A中序號(hào)為偶數(shù)的元素，且保持原來的相對(duì)次序。解：其函數(shù)是將單鏈表A中的全部偶數(shù)序號(hào)的結(jié)點(diǎn)刪除，并在刪除時(shí)把這些結(jié)點(diǎn)鏈接起來構(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，編寫一種函數(shù)將它們合并成一種鏈表C而不變化其排序性。解：這里采用鏈表合并的辦法，設(shè)原兩鏈表的頭指針分別為p和q，每次比較p->data和q->data的值，把值較小的結(jié)點(diǎn)作為新鏈表的結(jié)點(diǎn)，這一過程直到一種鏈表為空為止。當(dāng)一種鏈表為空而另一種鏈表不為空時(shí)，只要將不空的鏈表指針賦給新鏈表中最后一種結(jié)點(diǎn)的指針即可。實(shí)現(xiàn)本題功效的函數(shù)以下：node*mergelink(p,q)node*p,*q;{/*本題中p、q為鏈頭指針，不含頭結(jié)點(diǎn)。*//*但為操作方便，過程中要為鏈表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’<>空表，或者兩者均不為空表，且A’的首元不大于B’的首元，則A<B；否則A>B。（詞典次序）試寫一種比較A，B大小的算法（在算法中，不要破壞原表A和B，并且不一定先求得A’和B’才進(jìn)行比較）。36.設(shè)有一種用向量表達(dá)的線性表L，規(guī)定寫出一種將該表逆置的過程，并允許在原表的存儲(chǔ)空間外再增加一種附加的工作單元。(朱儒榮,C語言版數(shù)據(jù)構(gòu)造考研例題)解：用數(shù)據(jù)類型描述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è)算法過程只須進(jìn)行數(shù)據(jù)元素的交換操作，其重要時(shí)間耗費(fèi)在for循環(huán)上，整個(gè)算法的時(shí)間復(fù)雜度為O(k)。37.已知兩個(gè)整數(shù)集合A和B，它們的元素分別依元素值遞增有序寄存在兩個(gè)單鏈表HA和HB中，編寫一種函數(shù)求出這兩個(gè)集合的并集C,并規(guī)定集合C的鏈表的結(jié)點(diǎn)仍依元素值遞增有序寄存。(提示：求并集不是歸并!)38．已知兩個(gè)次序表A和B分別表達(dá)兩個(gè)集合，其元素遞增排列，編寫一種函數(shù)求出A和B的交集C，規(guī)定C同樣以元素遞增的次