算法與數(shù)據(jù)結構C語言版課后習題答案(機械工業(yè)出版社)第1章-緒論-習題參考答案課案

1、第1章 概論 習題參考答案、基礎知識題1. 簡述下列概念數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)類型，數(shù)據(jù)結構，邏輯結構，存儲結構，算法。【解答】數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計 算機中并被計算機程序識別和處理的符號的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。 在不同的條件下，數(shù)據(jù)元素又可稱為元素、結點、頂點、記錄等。數(shù)據(jù)類型是對數(shù)據(jù)的取值范圍、數(shù)據(jù)元素之間的結構以及允許施加操作的一種總 體描述。每一種計算機程序設計語言都定義有自己的數(shù)據(jù)類型。“數(shù)據(jù)結構”這一術語有兩種含義，一是作為一門課程的名稱；二是作為一個科 學的概念。作為科學概念，目前尚無公認定義，一般認為，討論數(shù)據(jù)結構要包括 三個方面

2、，一是數(shù)據(jù)的邏輯結構，二是數(shù)據(jù)的存儲結構，三是對數(shù)據(jù)進行的操作（運算）。而數(shù)據(jù)類型是值的集合和操作的集合， 可以看作是已實現(xiàn)了的數(shù)據(jù)結 構，后者是前者的一種簡化情況。數(shù)據(jù)的邏輯結構反映數(shù)據(jù)元素之間的邏輯關系（即數(shù)據(jù)元素之間的關聯(lián)方式或“鄰接關系”），數(shù)據(jù)的存儲結構是數(shù)據(jù)結構在計算機中的表示，包括數(shù)據(jù)元素 的表示及其關系的表示。數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作，運算是定義在邏 輯結構上的，和存儲結構無關，而運算的實現(xiàn)則依賴于存儲結構。數(shù)據(jù)結構在計算機中的表示稱為物理結構， 又稱存儲結構。是邏輯結構在存儲器 中的映像，包括數(shù)據(jù)元素的表示和關系的表示。邏輯結構與計算機無關。算法是對特定問題求解步驟的

3、一種描述，是指令的有限序列。其中每一條指令表 示一個或多個操作。一個算法應該具有下列特性：有窮性、確定性、可行性、輸 入和輸出。2. 數(shù)據(jù)的邏輯結構分哪幾種，為什么說邏輯結構是數(shù)據(jù)組織的主要方面？【解答】數(shù)據(jù)的邏輯結構分為線性結構和非線性結構。（也可以分為集合、線性結構、樹形結構和圖形即網狀結構）。邏輯結構是數(shù)據(jù)組織的某種“本質性”的東西：（1）邏輯結構與數(shù)據(jù)元素本身的形式、內容無關。（2）邏輯結構與數(shù)據(jù)元素的相對位置無關。（3）邏輯結構與所含數(shù)據(jù)元素的個數(shù)無關。3. 試舉一個數(shù)據(jù)結構的例子，敘述其邏輯結構、存儲結構、運算三方面的內容?！窘獯稹咳鐚W生成績表，邏輯結構是線性結構，可以順序存儲（也

4、可以鏈式存儲），運算可以有插入、刪除、查詢、等等。4. 簡述算法的五個特性，對算法設計的要求?！窘獯稹克惴ǖ奈鍌€特性是：有窮性、確定性、可行性、零至多個輸入和一 至多個輸出。對算法設計的要求：正確性，易讀性，健壯性，和高的時空間效率(運算速度快, 存儲空間小)。5. 設n是正整數(shù)，求下列程序段中帶 己號的語句的執(zhí)行次數(shù)。(1)i=1;k=0; i=1;j=0;while (in)while (i+jj)j+;else i+; x=y=0;(4)x=91;y=100;for (i=0;i0)for (j=0;j100)x+;x=x-10; y-;for (k=0;kn;k+) y+;else x

5、+;【解答】(1)n-1(2)n為偶數(shù)時，均為n div 2;你為奇數(shù)時，分別為：(n div 2)+1 和n div 2(3) n+1, n(n+1), n2,(n+1)n 2, n 3(4) 100, 10006. 有實現(xiàn)同一功能的兩個算法 A1和A2,其中A1的時間復雜度為Tl=O(2n)，A2 的時間復雜度為T2=O(m，僅就時間復雜度而言，請具體分析這兩個算法哪 一個好？【解答】對算法A1和A2的時間復雜度T1和T2取對數(shù)，得nlog2和2logn。顯 然，當n4 時，算法A2好于A1。7. 選擇題：算法分析的目的是()A、找出數(shù)據(jù)結構的合理性B、研究算法中的輸入和輸出的關系C、分析

6、算法的效率以求改進D 、分析算法的易懂性和文檔特點【解答】C二、算法設計題8. 已知輸入x，y，z三個不相等的整數(shù)，設計一個“高效”算法，使得這三個 數(shù)按從小到大輸出?！案咝А钡暮x是用最少的元素比較次數(shù)、元素移動次數(shù)和輸出次數(shù)。void Best() /按序輸出三個整數(shù)的優(yōu)化算法int a,b,c,t;sca nf( “ d%d%d,&a,&b,&c);if(ab)t=a; a=b; b=t: /a和 b 已正序if(bc)t=c; c=b;/c已到位if(at) b=a; a=t; /a和 b 已正序else b=t;/ifprintf( “%d,%d,%dn ,a,b,c);/最佳2次比

7、較，無移動；最差3次比較，7個賦值9 在數(shù)組An中查找值為k的元素，若找到則輸出其位置i(1 i =1)&(Ai!=k) i-;if(i=1) return i;else return 0;當查找不成功時，總的比較次數(shù)為 n+1次，所以最壞情況下時間復雜度為 0( n)。第2章線性表習題參考答案一、基礎知識題2.1試述頭指針、頭結點、元素結點、首元結點的區(qū)別，說明頭指針和頭結點的作【解答】指向鏈表第一個結點(或為頭結點或為首元結點)的指針稱為頭指針?！邦^指針”具有標識一個鏈表的作用，所以經常用頭指針代表鏈表的名字，如鏈表L既是指鏈表的名字是L,也是指鏈表的第一個結點的地址存儲在指針變量L中，頭

8、指針為“ NULL ”則表示一個空表。有時，我們在整個線性鏈表的第一個元素結點之前加入一個結點，稱為頭結點，它的數(shù)據(jù)域可以不存儲任何信息(也可以做監(jiān)視哨或存放線性表的長度等附加信息)，指針域中存放的是第一個數(shù)據(jù)結點的地址，空表時為空?！邦^結點”的加入，使插入和刪除等操作方便統(tǒng)。元素結點即是數(shù)據(jù)結點，至少包括元素自身信息和其后繼元素的地址兩個域。首元結點是指鏈表中第一個數(shù)據(jù)元素的結點；為了操作方便，通常在鏈表的首元結點之前附設一個結點，稱為頭結點。2.2分析順序存儲結構和鏈式存儲結構的優(yōu)缺點，說明何時應該利用何種結構?！窘獯稹繌目臻g上來看，當線性表的長度變化較大，難以估計其規(guī)模時，選用動態(tài)的鏈表

9、作為存儲結構比較合適，但鏈表除了需要設置數(shù)據(jù)域外， 還要額外設置指針域，因此當線性 表長度變化不大，易于事先確定規(guī)模時，為了節(jié)約存儲空間，宜采用順序存儲結構。從時間上看，順序表具有按元素序號隨機訪問的特點，在順序表中按序號訪問數(shù)據(jù)元素的時間復雜度為 0(1);而鏈表中按序號訪問的時間復雜度為0(n)。所以如果經常按序號訪問數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此n較大時順序表的插入和刪除效率低。在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作。從 這個角度考慮顯然鏈表優(yōu)于順序表?？傊?，兩種存儲結構各有長短，選擇那一種存儲結構，由實

10、際問題中的主要因素決定。2.3分析在順序存儲結構下插入和刪除結點時平均需要移動多少個結點?！窘獯稹科骄苿颖碇写蠹s一半的結點，插入操作平均移動 個結點，刪除操作平均移動個結點。具體移動的次數(shù)取決于表長和插入、刪除的結點的位置。2.4為什么在單循環(huán)鏈表中常使用尾指針，若只設頭指針，插入元素的時間復雜度如何？【解答】單循環(huán)鏈表中無論設置尾指針還是頭指針都可以遍歷表中任一個結點。設置尾指針時，若在表尾進行插入元素或刪除第一元素，操作可在0(1)時間內完成；若只設置頭指針，表尾進行插入或刪除操作，需要遍歷整個鏈表，時間復雜度為0(n)。2.5在單鏈表、雙鏈表、單循環(huán)鏈表中，若知道指針p指向某結點，能否

11、刪除該結點，時間復雜度如何？【解答：】以上三種鏈表中，若知道指針p指向某結點，都能刪除該結點。雙鏈表刪除p所指向的結點的時間復雜度為0(1)，而單鏈表和單循環(huán)鏈表上刪除p所指向的結點的時間復雜度均為0(n)。2.6下面算法的功能是什么？Lin kedList Unknown(Lin kedList la)LNode *q ， *p;if(la & la- next)q=la; la=la-n ext; p=la; while(p-n ext) p=p-n ext;p-n ext=q; q-n ext =nu II;return la;【解答】將首元結點刪除并插入到表尾(設鏈表長度大于2.7選擇

12、題：在循環(huán)雙鏈表的*p結點之后插入*s結點的操作是(la、p-n ext=s;s-prior=p;p-n ext-prior=s;s-n ext=p-n ext;B、p-n ext=s; p-n ext-prior=s;s-prior=p;s-n ext=p-n ext;lc、s-prior=p; s-n ext=p-n ext;p-n ext:=s;p-n ext-prior=s;D、s-prior=p; sn ext=p n ext;pn ext-prior =s;p-n ext=s;【解答】D2.8選擇題：若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除 運算，則利用

13、()存儲方式最節(jié)省時間。D 單循環(huán)鏈表la.順序表B.雙鏈表lc.帶頭結點的雙循環(huán)鏈表【解答】la二、算法設計題將這兩2.9設ha和hb分別是兩個帶頭結點的非遞減有序單鏈表的頭指針，試設計算法， 個有序鏈表合并成一個非遞增有序的單鏈表。要求使用原鏈表空間，表中無重復數(shù)據(jù)?！绢}目分析】因為兩鏈表已按元素值非遞減次序排列，將其合并時，均從第一個結點起進行比較，將小的鏈入鏈表中，同時后移鏈表工作指針，若遇值相同的元素，則刪除之。該問題 要求結果鏈表按元素值非遞增次序排列，故在合并的同時，將鏈表結點逆置。Lin kedList Union(Lin kedList ha,hb)/ ha,hb分別是帶頭結

14、點的兩個單鏈表的頭指針，鏈表中的元素值按遞增序排列/本算法將兩鏈表合并成一個按元素值遞減次序排列的單鏈表，并刪除重復元素 pa=ha-n ext;pb=hb-n ext;ha-n ext=n ull;/ pa是鏈表ha的工作指針/ pb是鏈表hb的工作指針/ ha作結果鏈表的頭指針，先將結果鏈表初始化為空/當兩鏈表均不為空時作while(pa!=null & pb!=null)while(pa-n ext & pa-data=pa-n ext-data)u=pa-next; pa-next=u-next; free(u) 刪除 pa 鏈表中的重復元素while(pb-n ext & pb-da

15、ta=pb-n ext-data)u=pb-next; pb-next=u-next; free(u)/刪除 pb 鏈表中的重復元素if(pa-datadata)r=pa-n ext;pa-n ext=ha-n ext;ha-n ext=pa;/將pa的后繼結點暫存于r/將pa結點鏈于結果表中，同時逆置/恢復pa為當前待比較結點pa=r;else if(pb-datadata)/將pb的后繼結點暫存于rr=pb-n ext;pb-n ext=ha-n ext; ha-n ext=pb;pb=r;/恢復pb為當前待比較結點/將pb結點鏈于結果表中，同時逆置elseu=pb;pb=pb-next;

16、free(u) /刪除鏈表 pb 和 pa 中的重復元素/ while(pa!=null & pb!=null)if(pa) pb=pa;/避免再對pa寫下面的 while語句while(pb!=null)/將尚未到尾的表逆置到結果表中r=pb-n ext; pb-n ext=ha-n ext; ha-n ext=pb; pb=r; return ha /算法Union結束2.11 設p指向頭指針為la的單鏈表中某結點，試編寫算法，刪除結點*p的直接前驅結點。 【題目分析】設*p是單鏈表中某結點，刪除結點 *p的直接前驅結點，要找到*p的前驅結點 的前驅 *pre。進行如下操作： u=pre-

17、next; pre-next=u-next;free(u);LinkedList LinkedListDel(LinkedList la , LNode *p) /刪除單鏈表la上的結點*p的直接前驅結點，假定*p存在pre=la;if(pre-n ext=p)printf( “*p是鏈表第一結點，無前驅 n”); exit(0) ; while(pre- next-next !=p)pre=pre-n ext;u=pre-n ext; pre-n ext=u-n ext; free(u);return(la); 2.12設計一算法，將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多

18、項 式各自僅有奇次幕或偶次幕項，并要求利用原鏈表中的結點空間來構造這兩個鏈表。【題目分析】設循環(huán)鏈表表示的多項式的結點結構為：typedef struct nodeint power;幕float coef;/系數(shù)ElemType other;/其他信息struct n ode *n ext; /指向后繼的指針PNode,*PolyLi nkedList;則可以從第一個結點開始，根據(jù)結點的幕是奇數(shù)或偶數(shù)而將其插入到奇次幕或偶次幕項的鏈表中。假定用原鏈表保存偶次幕，要為奇次幕的鏈表生成一個表頭，為了保持鏈表中結點的原來順序，用一個指針指向奇次幕鏈表的表尾，注意鏈表分解時不能“斷鏈”。void P

19、olyDis(PolyLi nkedList poly)/將poly表示的多項式鏈表分解為各含奇次幕或偶次幕項的兩個循環(huán)鏈表PolyLi nkedList poly2=(PolyLi nkedList)malloc(sizeof(PNode);/ poly2表示只含奇次幕的多項式r2=poly2;/ r2是只含奇次幕的多項式鏈表的尾指針r仁poly;/ r1是只含偶次幕的多項式鏈表當前結點的前驅結點的指針p=poly-next;/鏈表帶頭結點，p指向第一個元素while(p!=poly)if(p-power % 2) / 處理奇次幕r=p-n ext;/暫存后繼r2- next=p; /結點鏈

20、入奇次幕鏈表r2=p;/尾指針后移p=r;/恢復當前待處理結點else /處理偶次幕r1- n ext=p; r1=p; p=p-n ext;r-n ext=poly2; r1- next=poly;/構成循環(huán)鏈表 / PolyDis2.14設單向鏈表的頭指針為head，試設計算法，將鏈表按遞增的順序就地排序?！绢}目分析】本題中的“就地排序”，可理解為不另辟空間，這里利用直接插入原則把鏈表整理成遞增有序鏈表。Lin kedList Lin kListI nsertSort(L in kedList head)/ head是帶頭結點的單鏈表，本算法利用直接插入原則將鏈表整理成遞增的有序鏈表if(

21、head- next!=null)/鏈表不為空表p=head-next-next; / p指向第一結點的后繼head-n ext- n ext=n ull;/直接插入原則認為第一元素有序，然后從第二元素起依次插入while(p!=null)r=p-next;/暫存p的后繼q=head;while(q-next & q-n ext-datadata)q=q-next; /查找插入位置p-next=q-next; /將 p結點鏈入鏈表q_n ext=p;p=r; 2.15已知遞增有序的三個單鏈表分別代表集合A , B和C,設計算法實現(xiàn) A=A U ( B n C),并使結果鏈表仍保持遞增。要求算法

22、的時間復雜度為O(|A|+|B|+|C|)。其中，|A|為集合A的元素個數(shù)。【題目分析】本題首先求B和C的交集，即求B和C中共有元素，再與 A求并集，同時刪除重復元素，以保持結果A遞增。Lin kedList un io n(Li nkedList A,B,C)/ A、B和C均是帶頭結點的遞增有序的單鏈表，本算法實現(xiàn)A=A U (B n C)/使結果表A保持遞增有序pa=A-n ext;pb=B-n ext;pc=C-n ext;設置三個工作指針pre=A; / pre指向結果鏈表中當前待合并結點的前驅A-data=MaxElemType; /同類型元素最大值，起監(jiān)視哨作用while(pa |

23、 pb & pc)while(pb & pc)if(pb-datadata) pb=pb-n ext;else if(pb-datapc-data) pc=pc- n ext;else break; / B表和C表有公共元素if(pb & pc)while(pa & pa-datadata) /先將 A中小于B , C公共元素部分鏈入pre _n ext=pa;pre=pa;pa=pa-n ext;if(pre-data!=pb-data)pre _n ext=pb;pre=pb;pb=pb-n ext;pc=pc- n ext;elsepb=pb-n ext;pc=pc- n ext;/若A

24、中已有B , C公共元素，則不再存入結果表 / while(pa|pb&pc)if(pa) pre_n ext=pa;else pre-next =null;/當B , C無公共元素，將 A中剩余鏈入 /算法Union結束2.16順序表la與lb非遞減有序，順序表空間足夠大。試設計一種高效算法，將lb中元素合到la中，使新的la的元素仍保持非遞減有序。高效指最大限度地避免移動元素?！绢}目分析】順序存儲結構的線性表的插入，其時間復雜度為0(n),平均移動近一半的元素。線性表la和lb合并時，若從第一個元素開始，一定會造成元素后移，這不符合本題“高效算法”的要求。應從線性表的最后一個元素開始比較，

25、大者放到最終位置上。設兩線性表的長度各為m和n ,則結果表的最后一個元素應在 m+n位置上。這樣從后向前，直到第一 個元素為止。SeqList Union( SeqList la, SeqList lb)/ la和lb是順序存儲的非遞減有序線性表，本算法將lb合并到la中，元素仍非遞減有序 m=la.last;n=lb.last; / m, n分別為線性表la和lb的長度k=m+n-1;/ k為結果線性表的工作指針(下標)i=m-1;j=n-1;/ i, j分別為線性表la和lb的工作指針(下標)while(i=0 & j=0)if(la.datai=lb.dataj) la.datak-=l

26、a.datai-;else la.datak-=lb.dataj-; while(j=0) la.datak-=lb.dataj-; la.last=m+n;return la;【算法討論】算法中數(shù)據(jù)移動是主要操作。在最佳情況下(lb的最小元素大于la的最大元素)，僅將lb的n個元素移(拷貝)到la中，時間復雜度為 O (n),最差情況，la的所有 元素都要移動，時間復雜度為O (m+n)。因數(shù)據(jù)合并到la中，所以在退出第一個while循環(huán)后，只需要一個 while循環(huán)，處理lb中剩余元素。第二個循環(huán)只有在lb有剩余元素時才執(zhí)行，而在la有剩余元素時不執(zhí)行。本算法“最大限度的避免移動元素”，是

27、“一種高效算法”。2.17已知非空線性鏈表由head指出，試寫一算法，將鏈表中數(shù)據(jù)域值最小的那個結點移到鏈表的最前面。要求：不得額外申請新的鏈結點?！绢}目分析】本題要求將鏈表中數(shù)據(jù)域值最小的結點移到鏈表的最前面。首先要查找最小值結點。將其移到鏈表最前面，實質上是將該結點從鏈表上摘下(不是刪除并回收空間)，再插入到鏈表的最前面。Lin kedListDeli nsert(L in kedListhead)/本算法將非空線性鏈表head中數(shù)據(jù)域值最小的那個結點移到鏈表的最前面p=head-next ;/ p是鏈表的工作指針pre=head ;q=p ;/ pre指向鏈表中數(shù)據(jù)域最小值結點的前驅/

28、q指向數(shù)據(jù)域最小值結點，初始假定是第一結點while ( p-next)if (p-next-datadata ) pre=p ; q=p-next; / 找至U新的最小值結點 p=p-next;if(q!=head- next)/若最小值是第一元素結點，則不需再操作pre-next=q-next ；/將最小值結點從鏈表上摘下q-next=head-next ;/將q結點插到鏈表最前面head-next=q; / Delinsert2.19三個帶頭結點的線性鏈表 存在兩個以上值相同的結點)表中均包含的數(shù)據(jù)元素的結點,la、lb和lc中的結點均依元素值自小至大非遞減排列(可能 ，編寫算法對la表進行如下操作：使操作后的la中僅留下三個且沒有值相同的結點， 并釋放所有無用結點。 限定算法的時間復雜度為O (m+n+p),其中m、n和p分別為三個表的長度?！绢}目分析】留下三個鏈表中公共數(shù)據(jù)，首先查找兩表la和B中公共數(shù)據(jù)，再去lc中找O (m+n+p),在查找每個鏈有無該數(shù)據(jù)。要消除重復元素，應記住前驅，要求時間復雜度 表時，指針不能回溯。LinkedList lcommon(LinkedList la , lb, lc)/本算法使la表留下la、lb和lc三個非遞減有