數(shù)據(jù)結(jié)構(gòu)單元2練習(xí)參考答案

1、單元練習(xí)2一判斷題(下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打V;錯(cuò)誤的打 X )(X) ( 1)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)。(X) (2)鏈表的每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針域。(V) (3)在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。(X) (4)順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除效率高。(X) ( 5)線性鏈表的刪除算法簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè) 單元向前移動(dòng)。(X) (6)順序表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。(V) ( 7)線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。

2、(V) ( 8)線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。(X) (9)順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。(X) (10)插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。二填空題(1) 順序表中邏輯上相鄰的元素在物理位置上必須 相連。(2) 線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一 關(guān)系。(3) 順序表相對(duì)于鏈表的優(yōu)點(diǎn)是：節(jié)省存儲(chǔ)和隨機(jī)存取。(4) 鏈表相對(duì)于順序表的優(yōu)點(diǎn)是：插入、刪除方便。(5) 采用 順序存儲(chǔ)結(jié)構(gòu)的線性表叫順序表。(6) 順序表中訪問(wèn)任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為0(1)。(7) 鏈表相對(duì)于順序表的優(yōu)點(diǎn)是插入、

3、刪除方便；缺點(diǎn)是存儲(chǔ)密度小 。(8) 在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn) *P，其時(shí)間復(fù)雜度為 0(1)。(9) 在單鏈表中要在已知結(jié)點(diǎn) *P之前插入一個(gè)新結(jié)點(diǎn)，需找到 *P的直接前趨結(jié)點(diǎn)的地址，其查找的時(shí)間復(fù)雜度為0(n)。(10) 單鏈表中需知道 頭指針才能遍歷整個(gè)鏈表。(11) 線性表中第一個(gè)結(jié)點(diǎn)沒(méi)有直接前趨，稱為開(kāi)始 結(jié)點(diǎn)。(12) 在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素，要移動(dòng)n-i 個(gè)元素。(13) 在一個(gè)長(zhǎng)度為n的順序表中，如果要在第 i個(gè)元素前插入一個(gè)元素，要后移 n-i +1 個(gè)元 素。(14) 在無(wú)頭結(jié)點(diǎn)的單鏈表中，第一個(gè)結(jié)點(diǎn)的地址存放在頭指針中，而其它結(jié)點(diǎn)的存儲(chǔ)地址存放在前趨 結(jié)點(diǎn)

4、的指針域中。(15) 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快速度存取線性表中的元素時(shí)，應(yīng)采用 順序存儲(chǔ)結(jié)構(gòu)。(16) 在線性表的鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯關(guān)系是通過(guò)指針 決定的。(17) 在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，它們一個(gè)指向其前趨 結(jié)點(diǎn)，另一個(gè)指向其 后繼結(jié)點(diǎn)。(18) 對(duì)一個(gè)需要經(jīng)常進(jìn)行插入和刪除操作的線性表，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜。(19) 雙鏈表中，設(shè)p是指向其中待刪除的結(jié)點(diǎn)，則需要執(zhí)行的操作為：p-prior-next=p-next;p-n ext-prior =p- prior 。(20) 在如圖所示的鏈表中，若在指針P所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域

5、值為a和b的兩個(gè)結(jié)點(diǎn)，則可用下 列兩個(gè)語(yǔ) 句：S-next-next=P-next 和P-next=S 來(lái)實(shí)現(xiàn)該操 作。aPbA三選擇題S(1)在具有n個(gè)結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)(A )的操作，其算法的時(shí)間復(fù)雜度都是0 (n)。A.遍歷鏈表或求鏈表的第i個(gè)結(jié)點(diǎn)B.在地址為P的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)C.刪除開(kāi)始結(jié)點(diǎn)D 刪除地址為P的結(jié)點(diǎn)的后繼結(jié)點(diǎn)(2)設(shè)a、b、c為三個(gè)結(jié)點(diǎn)，p、10、20分別代表它們的地址，則如下的存儲(chǔ)結(jié)構(gòu)稱為(B )。a10b20cAA.循環(huán)鏈表B.單鏈表C.雙向循環(huán)鏈表D .雙向鏈表(3)單鏈表的存儲(chǔ)密度(C)。A .大于1B.等于1C.小于1D .不能確定(4 )已知一個(gè)順序存

6、儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為B,則第個(gè)結(jié)點(diǎn)的地址為( A )。A.B+(i-1)*mB . B+i*mC.B-i*mD.B+(i+1)*m(5)在有n個(gè)結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時(shí)間復(fù)雜度為(B )。A. 0( 1)B. 0 ( n)C.0 (n2)D.0( log 2 n)(6)設(shè) Llink、Rlink分別為循環(huán)雙鏈表結(jié)點(diǎn)的左指針和右指針，則指針P所指的兀素是雙循環(huán)鏈表L的尾兀素的條件是(D )。A. P= LB. P-Llink= LC.P= NULLD.P-Rlink=L(7)兩個(gè)指針P和Q,分別指向單鏈表的兩個(gè)兀素，P所指元素是Q所指元素前驅(qū)的

7、條件是(BA. P-next=Q-next B . P-next= QC.Q_n ext= PD.P= Q(8)用鏈表存儲(chǔ)的線性表，其優(yōu)點(diǎn)是( C )。A.便于隨機(jī)存取B.花費(fèi)的存儲(chǔ)空間比順序表少C.便于插入和刪除D.數(shù)據(jù)兀素的物理順序與邏輯順序相冋(9)在單鏈表中，增加頭結(jié)點(diǎn)的目的是(C )。A.使單鏈表至少有一個(gè)結(jié)點(diǎn)B.標(biāo)志表中首結(jié)點(diǎn)的位置C.方便運(yùn)算的實(shí)現(xiàn)D.說(shuō)明該單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(10)下面關(guān)于線性表的敘述中，錯(cuò)誤的是(D )關(guān)系。A.順序表必須占一片地址連續(xù)的存儲(chǔ)單元B.順序表可以隨機(jī)存取任一元素C.鏈表不必占用一片地址連續(xù)的存儲(chǔ)單元D .鏈表可以隨機(jī)存取任一元素(11)

8、 L 是線性表，已知 LengthList ( L)的值是 5,經(jīng) DelList ( L , 2)運(yùn)算后，LengthList (L) 的 值是(C )oA. 2B. 3C. 4D. 5(12 )單鏈表的示意圖如下：Lc.-指向鏈表Q結(jié)點(diǎn)的前趨的指針是(B )。A. LB. PC. QD. R(13) 設(shè)p為指向單循環(huán)鏈表上某結(jié)點(diǎn)的指針，則*p的直接前驅(qū)( C )。A. 找不到B.查找時(shí)間復(fù)雜度為0( 1)C.查找時(shí)間復(fù)雜度為0 ( n)D .查找結(jié)點(diǎn)的次數(shù)約為n(14) 等概率情況下，在有n個(gè)結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)運(yùn)算，需平均移動(dòng)結(jié)點(diǎn)的數(shù)目為(C )。A. nB . (n-1)/2C.

9、n/2D. (n+1)/2(15) 在下列鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到其余各結(jié)點(diǎn)的是(C )。A.雙向鏈表B .單循環(huán)鏈表C .單鏈表D.雙向循環(huán)鏈表(16) 在順序表中，只要知道( D ),就可以求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A.基地址B.結(jié)點(diǎn)大小C.向量大小D.基地址和結(jié)點(diǎn)大小(17)在雙鏈表中做插入運(yùn)算的時(shí)間復(fù)雜度為(A )oA. 0( 1)B. 0 (n)C20 (n )D. 0 (log 2n)(18)鏈表不具備的特點(diǎn)是(A )oA.隨機(jī)訪問(wèn)B.不必事先估計(jì)存儲(chǔ)空間C.插入刪除時(shí)不需移動(dòng)兀素D.所需空間與線性表成正比(19 )以下關(guān)于線性表的論述，不正確的為(C)。A. 線性表中的元素可

10、以是數(shù)字、字符、記錄等不同類型B. 線性順序表中包含的元素個(gè)數(shù)不是任意的C. 線性表中的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)直接前趨和一個(gè)直接后繼D. 存在這樣的線性表，即表中沒(méi)有任何結(jié)點(diǎn)(20 )在(B )的運(yùn)算中，使用順序表比鏈表好。D .根據(jù)元素查找A.插入B.根據(jù)序號(hào)查找C.刪除四. 下述算法的功能是什么？(1)ListNode *Demo1(LinkList L,ListNode *p) / L是有頭結(jié)點(diǎn)的單鏈表ListNode *q=L-n ext;While (q & q- next!=p) q=q_n ext;if (q)return q;elseError( “*p not in L ”

11、);解：(1) 返回結(jié)點(diǎn)*p的直接前趨結(jié)點(diǎn)地址。(2) 交換結(jié)點(diǎn)*p和結(jié)點(diǎn)*q ( p和q 的(2)void Demo2(ListNode *p,ListNode*q) / p,*q是鏈表中的兩個(gè)結(jié)點(diǎn)DataType temp; temp=p-data; p_data=q_data; q-data=temp;五. 程序填空1 已知線性表中的元素是無(wú)序的，并以帶表頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)。試寫一算法，刪除表中所有大 于min,小于max的元素，試完成下列程序填空。Void delete (lklist head; datatype min, max) q=head-n ext;while (p!=N

12、ULL) if (p-datadata=max )q=p; p= p- next ; else q_n ext=p_next ;delete (p);p= q_next ; 2. 在帶頭結(jié)點(diǎn)head的單鏈表的結(jié)點(diǎn)a之后插入新元素x,試完成下列程序填空。struct node elemtype data;node * n ext;void lki nsert (node *head, elemtype x) node *s, * p;s= new node;s-data= x;p=head-n ext;while (p!=NULL) & ( p-data!=a )_p=p_next;if (p=

13、NULL)coutnext=p-next pnext=s六. 程序設(shè)計(jì)題1. 寫一個(gè)對(duì)單循環(huán)鏈表進(jìn)行遍歷（打印每個(gè)結(jié)點(diǎn)的值） 的算法，已知鏈表中任意結(jié)點(diǎn)的地址為P。2. 對(duì)給定的帶頭結(jié)點(diǎn)的單鏈表L,編寫一個(gè)刪除L中值為x的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)的算法。3. 將一個(gè)順序表中從第i個(gè)結(jié)點(diǎn)開(kāi)始的k個(gè)結(jié)點(diǎn)刪除。4. 已知一個(gè)單鏈表，編寫一個(gè)函數(shù)從單鏈表中刪除自第i個(gè)結(jié)點(diǎn)起的k個(gè)結(jié)點(diǎn)。5. 有一個(gè)單鏈表（不同結(jié)點(diǎn)的數(shù)據(jù)域值可能相同），其頭指針為head，編寫一個(gè)函數(shù)計(jì)算值域?yàn)閤的結(jié)點(diǎn)個(gè)數(shù)。6. 有兩個(gè)循環(huán)單鏈表，鏈頭指針?lè)謩e為head1和head2,編寫一個(gè)函數(shù)將鏈表head1鏈接到鏈表head2,鏈接后的

14、鏈表仍是循環(huán)鏈表。1. 解：void Show(ListNode *P) ListNode *t=P; do printf (”c,t-data); t=t-rear;while (t!=P);2. 解：void delete(ListNode *L) ListNode *p=L,*q;if (L-n ext-data=X) printf ( “值為x的結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)，沒(méi)有直接前趨結(jié)點(diǎn)可以刪除”);return;for (;p-next-data!=X; q=p; p=p-next); II刪除指針 p 所指向的結(jié)點(diǎn)q_n ext=p-n ext;delete p;解void Del(Seq

15、List *L,int i,int k) int j=i-1+k;for (j=0;jdatai-1+j=L-datai+k-2+j;if (i+k-2+jL-last)break;void Del(SeqList *L,int i,int k) int j=i-1+k;if (jL-last) printf(“超出范圍 ! ” )return;for (j=0;jlast-i;j+)L-datai-1+j=L-datai+k-2+j; 4解：void Del(node *head,int i,int k)node *p,*q;int j;if (i=1)for (j=1;jnext;dele

16、te p;elsep=head;for (j=1;jnext; / pfor (j=1;jnext; / q p-next=q-next; delete q;刪除前 k 個(gè)元素指向要?jiǎng)h除的結(jié)點(diǎn)指向要?jiǎng)h除的結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)指向要?jiǎng)h除的結(jié)點(diǎn)5 解：本題是遍歷單鏈表的每個(gè)結(jié)點(diǎn)，每遇到一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)個(gè)數(shù)加1，結(jié)點(diǎn)個(gè)數(shù)存儲(chǔ)在變量 n中。實(shí)現(xiàn)本題功能的函數(shù)如下：int counter(head) node *head ； node *p;int n=0;p=head ； while (p!=NULL) if (p-data=x) n+； p=p-next; return(n);6解：本題的算法思想是：先找

17、到兩鏈表的尾指針，將第一個(gè)鏈表的尾指針與第二個(gè)鏈表的頭結(jié)點(diǎn) 鏈接起來(lái)，使之成為循環(huán)的。函數(shù)如下：node *link (node *head1, *head2) node *p,*q;p=head1;while (p-next!=head1) p=p-next;q=head2;while (q-next!=head2) q=q-next;p-next=head2; q-next=head1;return (head1);模擬考題1在順序存儲(chǔ)的線性表第 i個(gè)位置插入新結(jié)點(diǎn)x，試完成下列程序填空。(或 L-last= L-last +1typedef struct/datatype dataMAX

18、LEN;/ MAXLENin t last;SeqList;int In sList(SeqList *L,i nt i,datatype x) int j;if (L-last= =MAXLEN-1) cout 順序表已滿！; return(-1);if( iL-last+2 )/ coutlast;j=i-1;j-)IIL-dataj+1=L-datajL-Latai-1=x ;IIL-last +將data和last圭寸裝在一個(gè)結(jié)構(gòu)體 為線性表的最大長(zhǎng)度II 插入結(jié)點(diǎn)函數(shù)檢查插入位置的正確性結(jié)點(diǎn)移動(dòng)新結(jié)點(diǎn)插入)return(1);2. 一個(gè)帶頭指針的單鏈表，寫出在值為x的結(jié)點(diǎn)之后插入 m個(gè)結(jié)點(diǎn)的算法。void in sertm (lklist head; int m) p=head-n ext;while (p!=NULL) & ( p-data!=x )p=p_n ext;if ( p-data=x ) q=p-n ext;for ( i=0; im ; i+ )II找到x,在其后插入 m個(gè)結(jié)點(diǎn) s=new (no de);cindata=a ;p_n ext=s;p=s; p_n ext=q;3. 有