習(xí)題精練第2章線性表

1、單項(xiàng)選擇題(120.0 分) C一個(gè)無限序列，可以為D單項(xiàng)選擇題(120.0 分) C一個(gè)無限序列，可以為D一個(gè)無限序列，可以為【：n（n0）n=02.在個(gè)結(jié)點(diǎn)的順序表，算法的時(shí)間復(fù)雜度是 O(1)的操作i 個(gè)結(jié)點(diǎn)(1in)i 個(gè)結(jié)點(diǎn)的直接前驅(qū)B在第i 個(gè)結(jié)點(diǎn)后C刪除第i 個(gè)結(jié)點(diǎn)(1in)D順序查找與給定值x 相等的元： 【i O(n)O(n)3.若長度為n Cn-Dn-i-i ：性表的第i 個(gè)位【一個(gè)新的數(shù)據(jù)前需要先將線性表的第i 個(gè)數(shù)據(jù)元素至第n 個(gè)數(shù)1 n-i+1 4.將兩個(gè)各有n1 和n2 個(gè)元素的有序表（遞增）：【7、83 5.將長度為n m 【：n m m O（m6.L 是p p

2、【：A O（m6.L 是p p 【：A p B p C D p p （priordatanextApnext=s；sprior=p；pnextprior=s；snext=pnext； Bpnext=s；pnextprior=s；sprior=p；snext=pnext； Csprior=p；snext=pnext；pnext=s；Dsprior=p；snext=pnext；pnextprior=s；所：8.結(jié)點(diǎn)除自身信息外還包括指針域，因密度小于順邏輯上相鄰的結(jié)點(diǎn)物理上不必相C可以通過計(jì)算直接確定第i 個(gè)結(jié)點(diǎn)【的：】選項(xiàng)C 錯(cuò)誤的原因是鏈結(jié)構(gòu)的地址不一定是連續(xù)的，所以不能通過計(jì)算直接確定第單鏈

3、D僅有尾指針的單循環(huán)鏈后【：】本題顯然應(yīng)在選項(xiàng)B D 和刪除第一各自的尾結(jié)各【：】本題顯然應(yīng)在選項(xiàng)B D 和刪除第一各自的尾結(jié)各自的第一個(gè)元素結(jié)一個(gè)表的頭結(jié)點(diǎn)，另一個(gè)表的尾結(jié)【：、R211. typedef emType k ik+1 個(gè)結(jié)點(diǎn)的數(shù)據(jù)是（【： 個(gè)結(jié)點(diǎn)是 SSk.cur，其包含的數(shù)據(jù)是 SSk.cur.data12.A 和B m nA+B 運(yùn)算時(shí)最好情況下的時(shí)間復(fù)BO(n)（當(dāng)m ：】當(dāng)兩個(gè)多項(xiàng)式單鏈表以指數(shù)有序排列時(shí)，實(shí)現(xiàn)相加運(yùn)算時(shí)所花時(shí)間最少，為 O(m+n)【簡答題(90.0分13.線性表（a1，a2，a3 ，an）采用順序采用C C+JAVA 簡答題(90.0分13.線性表

4、（a1，a2，a3 ，an）采用順序采用C C+JAVA ：n （1）C n)i=0j=n-1; i,j 為工作指針（下標(biāo)a 1n t=a0; 暫存樞軸元素。while(i=0)j-; if(ij) 負(fù)數(shù)前while(ij &ai0i+; if(ij) 正數(shù)后 （2）說明算法的復(fù)雜性：上述算法時(shí)間復(fù)雜度為O（n，算法的空間復(fù)雜度為 O(1)：【分析】假設(shè)原數(shù)組序列為 abcd1234，要求變換成的數(shù)組序列為 1234abcd，即循環(huán)左移了 4 位。比較之后，不難看出，其中有兩段的順序是不變的：1234abcdp 位的過程就是把數(shù)組的兩部分abcd1234 前n-p 個(gè)數(shù)逆序排列：4321dcb

5、a1234后p 1234dcba1234abcd。n x0,x1,xp,xn-1xn-1,xp,xp-1,x0R n-p 個(gè)數(shù)和后p xp,xp+1,xn-1,x0,x1,xp-1n x0,x1,xp,xn-1xn-1,xp,xp-1,x0R n-p 個(gè)數(shù)和后p xp,xp+1,xn-1,x0,x1,xp-1（2）用C voidreversek=left,j=right,temp;k left，j right while (k0&reverse (R,0,n-1); /將全部數(shù)據(jù)逆置 reverseR,0,n-p-1n-p 個(gè)元素逆置 reverse (R,n-p,n-1); /將后p 個(gè)元素

6、逆置（3）說明算法的復(fù)雜性：上述算法的時(shí)間復(fù)雜度為 O(n)，算法的空間復(fù)雜度為 O(1)結(jié)點(diǎn)的單鏈表中刪除（一個(gè)）最小值結(jié)點(diǎn)。要求（1）給出算法的基本設(shè)C C+JAVA ：（2）用C voidinklistLNode*p=L-next假定鏈表非空，p 為工作指針，指向待處理的結(jié)點(diǎn)LNode*pre=Lpre 指向最小值結(jié)點(diǎn)的前LNode*q=pq 指向最小值結(jié)點(diǎn)，初始假定第一元素結(jié)點(diǎn)是最小值結(jié)while（p-if（p-next-datadata） 查最小值結(jié)p=p-nextpre-next=q-next； 從鏈表上刪除最小值結(jié)freeq；（1）。（2）C C+JAVA ：結(jié)點(diǎn)，將其移到鏈表最

7、前面，實(shí)質(zhì)上是將該結(jié)點(diǎn)從鏈表上摘下（不是刪除并回收空間（2）C C+JAVA ：結(jié)點(diǎn)，將其移到鏈表最前面，實(shí)質(zhì)上是將該結(jié)點(diǎn)從鏈表上摘下（不是刪除并回收空間（2）用C voiddelinsert(LinkListLNode*p=L-next/p 是鏈表的工作指LNode *pre=L; /pre 指向鏈表中數(shù)據(jù)域最小值結(jié)點(diǎn)的前驅(qū) LNode*q=p;q 指向數(shù)據(jù)域最小值結(jié)點(diǎn)，初始假定是第一結(jié)點(diǎn) while (p-next!=NULL) if(p-next-datadata找到新的最小值結(jié)點(diǎn) if(q!=L-next若最小值是第一元素結(jié)點(diǎn)，則不需再操作 pre-next=q-next; /將最小值

8、結(jié)點(diǎn)從鏈表上摘下q-next=L-next; /q L-表歸到ha 表中,且歸并后ha 仍遞增序,在歸并中對于ha 表中已有的數(shù)據(jù)若hb 中也有,則hb ha 中,hb 的鏈表在算法中不允許破壞。hb hb 的結(jié)點(diǎn)合并到結(jié)果鏈表時(shí)，要生成新結(jié)點(diǎn)。：hb hb 的結(jié)點(diǎn)合并到結(jié)果鏈表時(shí)，要生成新結(jié)點(diǎn)。C 語言算法描述如下： voidUnion(LinkList&haLinkListhb) LinkList la; LNode *pa=ha; pa ha 鏈表的工作指針 LNode *pb=hb; pb hb 鏈表的工作指針 LNode*pre=la; pre 指向當(dāng)前待合并結(jié)點(diǎn)的前驅(qū) while

9、(pa&pb)if(pa-datadata) 處理ha 中數(shù)elseif(pa-datapb-data) hb 中數(shù)據(jù)。 r=(LinkList)malloc(sizeof(LNode); 申請空間 pre-pre=r; 將新結(jié)點(diǎn)鏈入結(jié)果鏈pb=pb-next; elseif(pa-datapb-data) hb 中數(shù)據(jù)。 r=(LinkList)malloc(sizeof(LNode); 申請空間 pre-pre=r; 將新結(jié)點(diǎn)鏈入結(jié)果鏈pb=pb-next; hb else pa-data=pb-data; pa=pa-next; ha pb=pb-next; hb if(pa!=NULL

10、pre-next=pa; elsepre-freela; 頭結(jié)點(diǎn)，ha、hb 18.結(jié)點(diǎn)的線性鏈表 list，請寫一算法，將該鏈表按結(jié)點(diǎn)數(shù)據(jù)域的：C LinkListLinkListSort(LinkList&list)/list LNode*p=list-next; p 是工作指針，指向待排序的當(dāng)前元list-next=NULL; whiler=p-next; r p 的后if(q-datap-data) 處理待排序結(jié)點(diǎn)p 比第一個(gè)元素結(jié)點(diǎn)小的情p-list=p; else while(q-next!=NULL&q-next-datanext=q-next; 將當(dāng)前排序結(jié)點(diǎn)鏈入有序鏈表p=r

11、; p 1i-i i-1 list list 是頭結(jié)點(diǎn)的指針，則相應(yīng)處理要簡單些，其算法如下：LinkListLinkListSort(LinkList&list)/list 結(jié)點(diǎn)的線性鏈LNode*p=list-next; p 指向第一元素list list 是頭結(jié)點(diǎn)的指針，則相應(yīng)處理要簡單些，其算法如下：LinkListLinkListSort(LinkList&list)/list 結(jié)點(diǎn)的線性鏈LNode*p=list-next; p 指向第一元素結(jié)點(diǎn) list-next=NULL; 有序鏈表初始化為空 while(p!=NULL) r=p-next; 保存后while(q-next!=

12、NULL & q-next-datanextp 是鏈表的工作指針，指向待處理的當(dāng)前元素for（i=1；inext；若n 是奇數(shù)，后移過中心結(jié)點(diǎn) while（p!=NULL& si= =p-data）測試是否中心對稱 if（p=NULL）return1鏈表中心對elsereturn0算法中先將“鏈表的前一半”元素（字符）n 結(jié)點(diǎn)的循環(huán)雙鏈表，所有元素值均為整數(shù)，設(shè)計(jì)一個(gè)算法輸出其倒數(shù)第k 個(gè)結(jié)點(diǎn)的值。k ：prior C findk (DuLinkList L,DuLNode *p=L-prior; /p 指向尾結(jié)點(diǎn)，i 1 whilep!=L&結(jié)點(diǎn)的循環(huán)雙鏈表，所有元素值均為整數(shù)，設(shè)計(jì)一個(gè)算法

13、輸出其倒數(shù)第k 個(gè)結(jié)點(diǎn)的值。k ：prior C findk (DuLinkList L,DuLNode *p=L-prior; /p 指向尾結(jié)點(diǎn)，i 1 whilep!=L&ik)p idata);return域向前查找k-1k 21.A B,heada 和headbA ilen 個(gè)元素，然后將單鏈表B j i 個(gè)元素起的共len 1i len i-1i+len A i 個(gè)起的len A B A B j A i，len 和j 。：i 個(gè)元素起的共len 1 i 個(gè)時(shí)開始數(shù)len i-1 i+len A i len A B A B j A 表之和刪除中應(yīng)注意前驅(qū)后繼關(guān)系，不能使鏈表“斷鏈。另外，算法中應(yīng)判斷i，len 和j 。C 語言算法描述如下： LinkListDelInsert（LinkListheada，headb， if（i1 | len1 | j1）f“n；exit（0p=heada/*p 為鏈表A A i 個(gè)元素時(shí)，p 指向i-1 個(gè)元素*/k=0while（p!=NULL&knextq A wh