第2章++線性表+課后習(xí)題答案

1、第2章 線性表1選擇題（1）一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）。A110 B108 C100 D120（2）在n個結(jié)點(diǎn)的順序表中，算法的時間復(fù)雜度是O(1)的操作是（ ）。A訪問第i個結(jié)點(diǎn)（1in）和求第i個結(jié)點(diǎn)的直接前驅(qū)（2in） B在第i個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)（1in）C刪除第i個結(jié)點(diǎn)（1in）D將n個結(jié)點(diǎn)從小到大排序（3） 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 的元素個數(shù)為（ ）。A8 B63.5 C63 D7（4）鏈接存儲的存儲結(jié)構(gòu)所占存儲空間（ ）。A分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)

2、點(diǎn)間關(guān)系的指針B只有一部分，存放結(jié)點(diǎn)值C只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針D分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)（5）線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（ ）。A必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以（6）線性表在（ ）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。A需經(jīng)常修改中的結(jié)點(diǎn)值 需不斷對進(jìn)行刪除插入 C中含有大量的結(jié)點(diǎn) 中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜（7）單鏈表的存儲密度（ ）。A大于1 B等于1 C小于1 D不能確定（8）將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（ ）。An B2n-1 C2n Dn-1（9）在一個

3、長度為n的順序表中，在第i個元素（1in+1）之前插入一個新元素時須向后移動（ ）個元素。An-i Bn-i+1 Cn-i-1 Di(10) 線性表L=(a1，a2,an)，下列說法正確的是（ ）。A每個元素都有一個直接前驅(qū)和一個直接后繼B線性表中至少有一個元素C表中諸元素的排列必須是由小到大或由大到小D除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼。(11) 若指定有n個元素的向量，則建立一個有序單鏈表的時間復(fù)雜性的量級是（ ）。AO(1) BO(n) CO(n2) DO(nlog2n)(12) 以下說法錯誤的是（ ）。A求表長、定位這兩種運(yùn)算在采用順序存儲結(jié)構(gòu)時

4、實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時實(shí)現(xiàn)的效率低B順序存儲的線性表可以隨機(jī)存取C由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活D線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)(13) 在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語句應(yīng)為（ ）。As->next=p+1; p->next=s;B(*p).next=s; (*s).next=(*p).next;Cs->next=p->next; p->next=s->next;Ds->next=p->next; p->next=s; (14) 在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時須修改指

5、針（ ）。Ap->next->prior=p->prior; p->prior->next=p->next;Bp->next=p->next->next; p->next->prior=p;Cp->prior->next=p; p->prior=p->prior->prior;Dp->prior=p->next->next; p->next=p->prior->prior;(15) 在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（

6、）。Ap->next=q; q->prior=p; p->next->prior=q; q->next=q;Bp->next=q; p->next->prior=q; q->prior=p; q->next=p->next;Cq->prior=p; q->next=p->next; p->next->prior=q; p->next=q;Dq->prior=p; q->next=p->next; p->next=q; p->next->prior=q;2算法

7、設(shè)計(jì)題（1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) pa=La->next; pb=Lb->next; Lc=pc=La; /用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn) while(pa && pb) if(pa->data<pb->data) pc->next=pa;pc=pa;pa=pa->next; else

8、 if(pa->data>pb->data) pc->next=pb; pc=pb; pb=pb->next; else / 相等時取La的元素，刪除Lb的元素 pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q; pc->next=pa?pa:pb; /插入剩余段 delete Lb; /釋放Lb的頭結(jié)點(diǎn) （2）將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。void union(

9、LinkList& La, LinkList& Lb, LinkList& Lc, ) pa = La->next; pb = Lb->next; / 初始化 Lc=pc=La; /用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn) Lc->next = NULL; while ( pa | pb ) if ( !pa ) q = pb; pb = pb->next; else if ( !pb ) q = pa; pa = pa->next; else if (pa->data <= pb->data ) q = pa; pa = pa-&

10、gt;next; else q = pb; pb = pb->next; q->next = Lc->next; Lc->next = q; / 插入 delete Lb; /釋放Lb的頭結(jié)點(diǎn) （3）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請?jiān)O(shè)計(jì)算法求出A與B的交集，并存放于A鏈表中。void Mix(LinkList& La, LinkList& Lb, LinkList& Lc, ) pa=la->next;pb=lb->next;設(shè)工作指針pa和pb；Lc=pc=La; /用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)while(p

11、a&&pb) if(pa->data=pb->data)交集并入結(jié)果表中。 pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next; delete u; else if(pa->data<pb->data) u=pa;pa=pa->next; delete u;else u=pb; pb=pb->next; delete u;while(pa) u=pa; pa=pa->next; delete u; 釋放結(jié)點(diǎn)空間while(pb) u=pb; pb=pb->next

12、; delete u;釋放結(jié)點(diǎn)空間pc->next=null;置鏈表尾標(biāo)記。delete Lb; 注： 本算法中也可對B表不作釋放空間的處理（4）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請?jiān)O(shè)計(jì)算法求出兩個集合A和B 的差集（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合），并以同樣的形式存儲，同時返回該集合的元素個數(shù)。void Difference（LinkedList A，B，*n）A和B均是帶頭結(jié)點(diǎn)的遞增有序的單鏈表，分別存儲了一個集合，本算法求兩集合的差集，存儲于單鏈表A中，*n是結(jié)果集合中元素個數(shù)，調(diào)用時為0p=A->next； p和q分別是鏈表A和B的工作指

13、針。 q=B->next； pre=A； pre為A中p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針。 while（p!=null && q!=null）if（p->data<q->data）pre=p；p=p->next；*n+； A鏈表中當(dāng)前結(jié)點(diǎn)指針后移。else if（p->data>q->data）q=q->next； B鏈表中當(dāng)前結(jié)點(diǎn)指針后移。else pre->next=p->next； 處理A，B中元素值相同的結(jié)點(diǎn)，應(yīng)刪除。 u=p； p=p->next； delete u； 刪除結(jié)點(diǎn)（5）設(shè)計(jì)算法將一個帶頭結(jié)點(diǎn)

14、的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)（鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點(diǎn)）。（6）設(shè)計(jì)一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。ElemType Max (LinkList L )if(L->next=NULL) return NULL;pmax=L->next; /假定第一個結(jié)點(diǎn)中數(shù)據(jù)具有最大值p=L->next->next;while(p != NULL )/如果下一個結(jié)點(diǎn)存在if(p->data > pmax->data) pmax=p;p=

15、p->next;return pmax->data;（7）設(shè)計(jì)一個算法，通過遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲空間。void inverse(LinkList &L) / 逆置帶頭結(jié)點(diǎn)的單鏈表 L p=L->next; L->next=NULL; while ( p) q=p->next; / q指向*p的后繼 p->next=L->next; L->next=p; / *p插入在頭結(jié)點(diǎn)之后 p = q; （8）設(shè)計(jì)一個算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個參

16、數(shù)，其值可以和表中的元素相同，也可以不同 ）。void delete(LinkList &L, int mink, int maxk) p=L->next; /首元結(jié)點(diǎn) while (p && p->data<=mink) pre=p; p=p->next; /查找第一個值>mink的結(jié)點(diǎn) if (p) while (p && p->data<maxk) p=p->next; / 查找第一個值 maxk 的結(jié)點(diǎn) q=pre->next; pre->next=p; / 修改指針 while (q!

17、=p) s=q->next; delete q; q=s; / 釋放結(jié)點(diǎn)空間 /if（9）已知p指向雙向循環(huán)鏈表中的一個結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data、prior、next三個域，寫出算法change(p),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。知道雙向循環(huán)鏈表中的一個結(jié)點(diǎn)，與前驅(qū)交換涉及到四個結(jié)點(diǎn)（p結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn)）六條鏈。void Exchange（LinkedList p）p是雙向循環(huán)鏈表中的一個結(jié)點(diǎn)，本算法將p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。q=p->llink； q->llink->rlink=p； p的前驅(qū)的前驅(qū)之后繼為p p->ll

18、ink=q->llink； p的前驅(qū)指向其前驅(qū)的前驅(qū)。 q->rlink=p->rlink； p的前驅(qū)的后繼為p的后繼。 q->llink=p； p與其前驅(qū)交換 p->rlink->llink=q； p的后繼的前驅(qū)指向原p的前驅(qū) p->rlink=q； p的后繼指向其原來的前驅(qū)算法exchange結(jié)束。（10）已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，請寫一時間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。題目分析 在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動（刪第i個元素，第i+1至第n個元素要依次前移）。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對位置不變。因此可以考慮設(shè)頭尾兩個指針（i=1，j=n），從兩端向中間移動，凡遇到值item的數(shù)據(jù)元素時，直接將右端元素左移至值為item的數(shù)據(jù)元素位