數(shù)據(jù)結(jié)構(gòu)(C語言版)第一二章習題答案

1、只要你有能力去做的事就一定要去做，不要給自己留下任何遺憾，人生最重要的不是所站的位置，而是所朝的方向。第1章 緒論習題1簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型2試舉一個數(shù)據(jù)結(jié)構(gòu)的例子敘述其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的含義和相互關(guān)系3簡述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖4存儲結(jié)構(gòu)由哪兩種基本的存儲方法實現(xiàn)？5選擇題（1）在數(shù)據(jù)結(jié)構(gòu)中從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ） A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（ ） A存儲結(jié)構(gòu) B存

2、儲實現(xiàn) C邏輯結(jié)構(gòu) D運算實現(xiàn)（3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性這意味著（ ） A數(shù)據(jù)具有同一特點 B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同而且對應(yīng)數(shù)據(jù)項的類型要一致 C每個數(shù)據(jù)元素都一樣 D數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等（4）以下說法正確的是（ ）A數(shù)據(jù)元素是數(shù)據(jù)的最小單位B數(shù)據(jù)項是數(shù)據(jù)的基本單位C數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)（5）以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（ ）A順序隊列 B. 鏈表 C. 有序表 D. 鏈棧（6）以下數(shù)據(jù)結(jié)構(gòu)中（ ）是非線性數(shù)據(jù)結(jié)構(gòu)A樹 B字符串 C隊 D棧6試分析下面各程序段的時間復(fù)雜度

3、（1）x=90; y=100; while(y0)if(x100) x=x-10;y-;else x+;（2）for (i=0; in; i+) for (j=0; jm; j+) aij=0;（3）s=0; for i=0; in; i+) for(j=0; jn; j+) s+=Bij; sum=s;（4）i=1; while(i=n) i=i*3;（5）x=0; for(i=1; in; i+) for (j=1; j1 y=0; while(x(y+1)* (y+1) y+;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因為x+共執(zhí)行了n-1+n-2+.1

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

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

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

7、的效率不比采用鏈式存儲結(jié)構(gòu)時實現(xiàn)的效率低B順序存儲的線性表可以隨機存取C由于順序存儲要求連續(xù)的存儲區(qū)域所以在存儲管理上不夠靈活D線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)(13) 在單鏈表中要將s所指結(jié)點插入到p所指結(jié)點之后其語句應(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é)點時須修改指針（ ）Ap-next-prior=p-prior; p-prior-next=p-n

8、ext;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指針所指的結(jié)點后插入q所指向的新結(jié)點其修改指針的操作是（ ）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-

9、prior=q; p-next=q;Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;2算法設(shè)計題（1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間 不另外占用其它的存儲空間表中不允許有重復(fù)的數(shù)據(jù)void MergeList_L(LinkList &LaLinkList &LbLinkList &Lc) pa=La-next; pb=Lb-next; Lc=pc=La; /用La的頭結(jié)點作為Lc的頭結(jié)點 while(pa & pb) if(pa-datadata) pc-next=pa;pc=pa;p

10、a=pa-next; else if(pa-datapb-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é)點 （2）將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間 不另外占用其它的存儲空間表中允許有重復(fù)的數(shù)據(jù)void union(LinkList& La LinkList& Lb

11、LinkList& Lc ) pa = La-next; pb = Lb-next; / 初始化 Lc=pc=La; /用La的頭結(jié)點作為Lc的頭結(jié)點 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 data ) q = pa; pa = pa-next; else q = pb; pb = pb-next; q-next = Lc-next; Lc-next = q; / 插入 delete Lb;

12、 /釋放Lb的頭結(jié)點 （3）已知兩個鏈表A和B分別表示兩個集合其元素遞增排列請設(shè)計算法求出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é)點作為Lc的頭結(jié)點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=pa;pa=pa-nex

13、t; delete u;else u=pb; pb=pb-next; delete u; while(pa) u=pa; pa=pa-next; delete u; 釋放結(jié)點空間 while(pb) u=pb; pb=pb-next; delete u;釋放結(jié)點空間 pc-next=null;置鏈表尾標記 delete Lb; 注： 本算法中也可對B表不作釋放空間的處理（4）已知兩個鏈表A和B分別表示兩個集合其元素遞增排列請設(shè)計算法求出兩個集合A和B 的差集（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合）并以同樣的形式存儲同時返回該集合的元素個數(shù)void Difference（Linked

14、List AB*n）A和B均是帶頭結(jié)點的遞增有序的單鏈表分別存儲了一個集合本算法求兩集合的差集存儲于單鏈表A中*n是結(jié)果集合中元素個數(shù)調(diào)用時為0p=A-next； p和q分別是鏈表A和B的工作指針 q=B-next； pre=A； pre為A中p所指結(jié)點的前驅(qū)結(jié)點的指針 while（p!=null & q!=null）if（p-datadata）pre=p；p=p-next；*n+； A鏈表中當前結(jié)點指針后移else if（p-dataq-data）q=q-next； B鏈表中當前結(jié)點指針后移else pre-next=p-next； 處理AB中元素值相同的結(jié)點應(yīng)刪除 u=p； p=p-nex

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

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

17、nt mink int maxk) p=L-next; /首元結(jié)點 while (p & p-datanext; /查找第一個值mink的結(jié)點 if (p) while (p & p-datanext; / 查找第一個值 maxk 的結(jié)點 q=pre-next; pre-next=p; / 修改指針 while (q!=p) s=q-next; delete q; q=s; / 釋放結(jié)點空間 /if（9）已知p指向雙向循環(huán)鏈表中的一個結(jié)點其結(jié)點結(jié)構(gòu)為data、prior、next三個域?qū)懗鏊惴╟hange(p)交換p所指向的結(jié)點和它的前綴結(jié)點的順序知道雙向循環(huán)鏈表中的一個結(jié)點與前驅(qū)交換涉及到四

18、個結(jié)點（p結(jié)點前驅(qū)結(jié)點前驅(qū)的前驅(qū)結(jié)點后繼結(jié)點）六條鏈void Exchange（LinkedList p）p是雙向循環(huán)鏈表中的一個結(jié)點本算法將p所指結(jié)點與其前驅(qū)結(jié)點交換q=p-llink； q-llink-rlink=p； p的前驅(qū)的前驅(qū)之后繼為p p-llink=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è)頭尾兩個指針