數(shù)據(jù)結(jié)構(gòu)線性表課后答案

1、第2章線性表選擇題順序表中第一個(gè)元素的存儲(chǔ)地址是100 ,每個(gè)元素的長(zhǎng)度為2,則第5個(gè) 元素的地址是()。110B. 108C. 100D. 120答案：B解釋?zhuān)喉樞虮碇械臄?shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為：100+2*4=108。在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是0(1)的操作是()。訪問(wèn)第i個(gè)結(jié)點(diǎn)(1in)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2in)在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1in)刪除第i個(gè)結(jié)點(diǎn)(1in)D .將n個(gè)結(jié)點(diǎn)從小到大排序答案：A解釋?zhuān)涸陧樞虮碇胁迦胍粋€(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度都是 O(n2)，排序的時(shí)間復(fù)雜度為 O(n2)或O(nlog2n)。順序表是一種隨機(jī)存取結(jié)構(gòu)，訪問(wèn)第 i個(gè)

2、結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直 接前驅(qū)都可以直接通過(guò)數(shù)組的下標(biāo)直接定位，時(shí)間復(fù)雜度是 0(1)。向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)的元素個(gè)數(shù)為()。8 B. 63.5C. 63 D. 7答案：B解釋?zhuān)浩骄苿?dòng)的元素個(gè)數(shù)為：n/2。鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間()。A .分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B .只有一部分，存放結(jié)點(diǎn)值C.只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針D .分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)答案：A線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址()。必須是連續(xù)的B 部分地址必須是連續(xù)的

3、C. 一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以答案：D線性表1在()情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。A .需經(jīng)常修改L中的結(jié)點(diǎn)值B.需不斷對(duì)L進(jìn)行刪除插入C.L中含有大量的結(jié)點(diǎn)D.L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜答案：B解釋?zhuān)烘湵碜畲蟮膬?yōu)點(diǎn)在于插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，直接修改指針即 可。單鏈表的存儲(chǔ)密度()。大于1B.等于1 C.小于1 D.不能確定答案：C解釋?zhuān)捍鎯?chǔ)密度是指一個(gè)結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)空間和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)空間之比，假設(shè)單鏈表一個(gè)結(jié)點(diǎn)本身所占的空間為D,指針域所占的空間為 N,則存儲(chǔ)密度為：D/(D+N), 一定小于1。將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表， 其最少的比較次數(shù)是()。A.

4、 nB. 2n-1C. 2nD. n-1答案：A解釋?zhuān)寒?dāng)?shù)谝粋€(gè)有序表中所有的元素都小于(或大于)第二個(gè)表中的元素， 只需要用第二個(gè)表中的第一個(gè)元素依次與第一個(gè)表的元素比較，總計(jì)比較n次。在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素(1inext=p+1; p-next=s;(*p).next=s; (*s).next=(*p).next;s-next=p-next; p-next=s-next;s-next=p-next; p-next=s;答案：D在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除 p所指的結(jié)點(diǎn)時(shí)須修改指針()。p-next-prior=p-prior; p-prior-next=p-next;p-nex

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

6、next=q;q-prior=p; q-next=p-next; p-next=q; p-next-prior=q;答案：C算法設(shè)計(jì)題將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原 來(lái)兩個(gè)鏈表的存儲(chǔ)空間，不另外占用其它的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。題目分析合并后的新表使用頭指針 Lc指向，pa和pb分別是鏈表La和Lb的工作指針，初始 化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘取其中較小者重新鏈接在Lc表的最后。如果兩個(gè)表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無(wú)重復(fù)的元素。 當(dāng)

7、一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表的剩余元素直接鏈接在Lc表的最后。算法描述void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)/合并鏈表La和Lb，合并后的新表使用頭指針 Lc指向pa=La-next; pb=Lb-next;/pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)Lc=pc=La; 用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)while(pa & pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;/取較小者La中的元素，將pa鏈接在pc的后面，pa指針后移 else if(

8、pa-datapb-data) pc-next=pb; pc=pb; pb=pb-next;/取較小者Lb中的元素，將pb鏈接在pc的后面，pb指針后移else /相等時(shí)取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)將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞增的有序鏈表。要求結(jié)果鏈表仍使 用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間，不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。題目分析合并后的新表使用頭指針 Lc指向，pa和pb分別是鏈表

9、La和Lb的工作指針，初始 化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘取其中較小者重新鏈接在Lc表的表頭結(jié)點(diǎn)之后，如果兩個(gè)表中的元素相等，只摘取La表中的元素，保留Lb表中的元素。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為 空時(shí)，將非空表的剩余元素依次摘取，鏈接在Lc表的表頭結(jié)點(diǎn)之后。算法描述void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc,)/合并鏈表La和Lb，合并后的新表使用頭指針 Lc指向pa=La-next; pb=Lb-next;/pa和pb分別是鏈表La和Lb的工作指針，初始化為相

10、應(yīng)鏈表的第一個(gè)結(jié)點(diǎn) Lc=pc=La; /用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn) Lc-next=NULL;while(pa|pb )/只要存在一個(gè)非空表，用q指向待摘取的元素if(!pa) q=pb; pb=pb-next;/La表為空，用q指向pb，pb指針后移else if(!pb) q=pa; pa=pa-next;/Lb表為空，用q指向pa，pa指針后移else if(pa-datadata) q=pa; pa=pa-next;/取較小者(包括相等)La中的元素，用q指向pa，pa指針后移else q=pb; pb=pb-next;取較小者Lb中的元素，用q指向pb，pb指針后移q-next

11、 = Lc-next; Lc-next = q;/將q指向的結(jié)點(diǎn)插在Lc表的表頭結(jié)點(diǎn)之后delete Lb;/釋放Lb的頭結(jié)點(diǎn)已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。請(qǐng)?jiān)O(shè)計(jì)算法求出A與B的交集，并存放于A鏈表中。題目分析只有同時(shí)出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中，合并后的新表使用頭指針 Lc指向。pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第 一個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表 La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果兩個(gè)表中相等 的元素時(shí)，摘取La表中的元素，刪除Lb表中的元素；如果其中一個(gè)表中的元素較小時(shí)， 刪除此表中較小的元素，此表的工作指針后移。當(dāng)鏈

12、表 La和Lb有一個(gè)到達(dá)表尾結(jié)點(diǎn)， 為空時(shí)，依次刪除另一個(gè)非空表中的所有元素。算法描述void Mix(LinkList& La, LinkList& Lb, LinkList& Lc) pa=La-next;pb=Lb-next;pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)Lc=pc=La; /用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)while(pa&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-datadata) u=p

13、a;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; delete u ;/ 釋放結(jié)點(diǎn)空間pc- next=null;/置鏈表尾標(biāo)記。delete Lb; /釋放Lb的頭結(jié)點(diǎn)已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。請(qǐng)?jiān)O(shè)計(jì)算法求出兩個(gè)集合A和B的差集(即僅由在 A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合)， 并以同樣的形式存儲(chǔ)，同時(shí)返回該集合的元素個(gè)數(shù)。題目分析求兩個(gè)集合A和B的差集是指

14、在A中刪除A和B中共有的元素，即刪除鏈表中的 相應(yīng)結(jié)點(diǎn)，所以要保存待刪除結(jié)點(diǎn)的前驅(qū)，使用指針pre指向前驅(qū)結(jié)點(diǎn)。pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行 比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果 La表中的元素小于Lb表中的 元素，pre置為L(zhǎng)a表的工作指針pa刪除Lb表中的元素；如果其中一個(gè)表中的元素較La和Lb有一個(gè)為空時(shí)，小時(shí)，刪除此表中較小的元素，此表的工作指針后移。當(dāng)鏈表 依次刪除另一個(gè)非空表中的所有元素。算法描述void Difference (LinkList& La, LinkList& Lb,int *n )/差集

15、的結(jié)果存儲(chǔ)于單鏈表 La中，*n是結(jié)果集合中元素個(gè)數(shù)，調(diào)用時(shí)為0pa=La-next; pb=Lb-next;II pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn) pre=La;II pre為L(zhǎng)a中pa所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針while (pa&pb )if (pa-datadata ) pre=pa;pa=pa-next;*n+;II A鏈表中當(dāng)前結(jié)點(diǎn)指針后移else if (pa-dataq-data ) q=q-next; IIB 鏈表中當(dāng)前結(jié)點(diǎn)指針后移else pre-next=pa-next;II處理A，B中元素值相同的結(jié)點(diǎn)，應(yīng)刪除u=pa; pa=pa-ne

16、xt; delete u; II刪除結(jié)點(diǎn)設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表 A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表 B、C， 其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)(鏈 表A中的元素為非零整數(shù)，要求 B、C表利用A表的結(jié)點(diǎn))。題目分析B表的頭結(jié)點(diǎn)使用原來(lái)A表的頭結(jié)點(diǎn)，為C表新申請(qǐng)一個(gè)頭結(jié)點(diǎn)。從A表的第一個(gè) 結(jié)點(diǎn)開(kāi)始，依次取其每個(gè)結(jié)點(diǎn) p，判斷結(jié)點(diǎn)p的值是否小于0,利用前插法，將小于 0 的結(jié)點(diǎn)插入B表，大于等于。的結(jié)點(diǎn)插入C表。算法描述void DisCompose(LinkedList A) B=A;B-next= NULL; II B 表初始化C=new LNode;

17、/為C申請(qǐng)結(jié)點(diǎn)空間C-next=NULL;II C初始化為空表p=A-next;II p為工作指針while(p!= NULL) r=p-next; II暫存p的后繼if(p-datanext=B-next; B- next=p; /將小于 。的結(jié)點(diǎn)鏈入B表,前插法else p-next=C-next; C-next=p; /將大于等于 0 的結(jié)點(diǎn)鏈入 C 表, 前插法p=r;/p指向新的待處理結(jié)點(diǎn)。設(shè)計(jì)一個(gè)算法，通過(guò)一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。題目分析假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值，依次與下一個(gè)元素比較，若其小于下一個(gè)元素，則設(shè)其下一個(gè)元素為最大值，反復(fù)進(jìn)行比較，直到遍歷完該鏈表。算

18、法描述ElemType Max (LinkList L )if(L-next=NULL) return NULL;pmax=L-next; /假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值p=L-next-next;while(p != NULL )/如果下一個(gè)結(jié)點(diǎn)存在if(p-data pmax-data) pmax=p;/ 如果 p 的值大于 pmax 的值，則 重新賦值p=p-next;/遍歷鏈表return pmax-data;設(shè)計(jì)一個(gè)算法，通過(guò)遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用 原表的存儲(chǔ)空間。題目分析從首元結(jié)點(diǎn)開(kāi)始，逐個(gè)地把鏈表 L的當(dāng)前結(jié)點(diǎn)？插入新的鏈表頭部。算法描述void in

19、verse(LinkList &L)/逆置帶頭結(jié)點(diǎn)的單鏈表 Lp=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;設(shè)計(jì)一個(gè)算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素(mink和maxk是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同)。題目分析分別查找第一個(gè)值mink的結(jié)點(diǎn)和第一個(gè)值 maxk的結(jié)點(diǎn)，再修改指針，刪除 值大于mink且小于maxk的所有元素。算法描述void delete(LinkList &L, int mink,

20、int maxk) p=L-next; /首元結(jié)點(diǎn)while (p & p-datanext; / 查找第一個(gè)值 mink 的結(jié)點(diǎn)if (p)while (p & p-datanext;/查找第一個(gè)值 maxk的結(jié)點(diǎn)q=pre-next; pre-next=p; / 修改指針while (q!=p) s=q-next; delete q; q=s; / 釋放結(jié)點(diǎn)空間/if已知p指向雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data、prior、next三個(gè)域，寫(xiě)出算法change(p),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。題目分析知道雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，與前驅(qū)交換涉及到四個(gè)結(jié)點(diǎn)(p結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn))六條鏈。算法描述void Exchange (LinkedList p )q=p-llink ;q-llink-rlink