【正文】 數(shù)據(jù)結構（C語言版）（第2版） 課后習題答案 李冬梅 目 錄第1章 緒論 1第2章 線性表 5第3章 棧和隊列 13第4章 串、數(shù)組和廣義表 26第5章 樹和二叉樹 33第6章 圖 43第7章 查找 54第8章 排序 6573第1章 緒論1．簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結構、邏輯結構、存儲結構、抽象數(shù)據(jù)類型。答案：數(shù)據(jù)：是客觀事物的符號表示，指所有能輸入到計算機中并被計算機程序處理的符號的總稱。如數(shù)學計算中用到的整數(shù)和實數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動畫等通過特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結點、記錄等。數(shù)據(jù)元素用于完整地描述一個對象，如一個學生記錄，樹中棋盤的一個格局（狀態(tài)）、圖中的一個頂點等。數(shù)據(jù)項：是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位。例如，學生基本信息表中的學號、姓名、性別等都是數(shù)據(jù)項。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如：整數(shù)數(shù)據(jù)對象是集合N={0，177。1，177。2，…}，字母字符數(shù)據(jù)對象是集合C={‘A’，‘B’，…，‘Z’， ‘a(chǎn)’，‘b’，…，‘z’}，學生基本信息表也可是一個數(shù)據(jù)對象。數(shù)據(jù)結構：是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結構是帶“結構”的數(shù)據(jù)元素的集合，“結構”就是指數(shù)據(jù)元素之間存在的關系。邏輯結構：從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結構可以看作是從具體問題抽象出來的數(shù)學模型。存儲結構：數(shù)據(jù)對象在計算機中的存儲表示，也稱為物理結構。抽象數(shù)據(jù)類型：由用戶定義的，表示應用問題的數(shù)學模型，以及定義在這個模型上的一組操作的總稱。具體包括三部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關系的集合和對數(shù)據(jù)對象的基本操作的集合。2．試舉一個數(shù)據(jù)結構的例子，敘述其邏輯結構和存儲結構兩方面的含義和相互關系。答案：例如有一張學生基本信息表，包括學生的學號、姓名、性別、籍貫、專業(yè)等。每個學生基本信息記錄對應一個數(shù)據(jù)元素，學生記錄按順序號排列，形成了學生基本信息記錄的線性序列。對于整個表來說，只有一個開始結點(它的前面無記錄)和一個終端結點(它的后面無記錄)，其他的結點則各有一個也只有一個直接前趨和直接后繼。學生記錄之間的這種關系就確定了學生表的邏輯結構，即線性結構。這些學生記錄在計算機中的存儲表示就是存儲結構。如果用連續(xù)的存儲單元(如用數(shù)組表示)來存放這些記錄，則稱為順序存儲結構；如果存儲單元不連續(xù)，而是隨機存放各個記錄，然后用指針進行鏈接，則稱為鏈式存儲結構。即相同的邏輯結構，可以對應不同的存儲結構。3．簡述邏輯結構的四種基本關系并畫出它們的關系圖。答案：（1）集合結構數(shù)據(jù)元素之間除了“屬于同一集合”的關系外，別無其他關系。例如，確定一名學生是否為班級成員，只需將班級看做一個集合結構。（2）線性結構數(shù)據(jù)元素之間存在一對一的關系。例如，將學生信息數(shù)據(jù)按照其入學報到的時間先后順序進行排列，將組成一個線性結構。（3）樹結構數(shù)據(jù)元素之間存在一對多的關系。例如，在班級的管理體系中，班長管理多個組長，每位組長管理多名組員，從而構成樹形結構。（4）圖結構或網(wǎng)狀結構數(shù)據(jù)元素之間存在多對多的關系。例如，多位同學之間的朋友關系，任何兩位同學都可以是朋友，從而構成圖形結構或網(wǎng)狀結構。其中樹結構和圖結構都屬于非線性結構。 四類基本邏輯結構關系圖4．存儲結構由哪兩種基本的存儲方法實現(xiàn)？答案：（1）順序存儲結構順序存儲結構是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系，通常借助程序設計語言的數(shù)組類型來描述。（2）鏈式存儲結構順序存儲結構要求所有的元素依次存放在一片連續(xù)的存儲空間中，而鏈式存儲結構，無需占用一整塊存儲空間。但為了表示結點之間的關系，需要給每個結點附加指針字段，用于存放后繼元素的存儲地址。所以鏈式存儲結構通常借助于程序設計語言的指針類型來描述。5．選擇題（1）在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（ ）。A．動態(tài)結構和靜態(tài)結構 B．緊湊結構和非緊湊結構C．線性結構和非線性結構 D．內(nèi)部結構和外部結構答案：C（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關的是數(shù)據(jù)的（ ）。A．存儲結構 B．存儲實現(xiàn)C．邏輯結構 D．運算實現(xiàn)答案：C（3）通常要求同一邏輯結構中的所有數(shù)據(jù)元素具有相同的特性，這意味著（ ）。 A．數(shù)據(jù)具有同一特點B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應數(shù)據(jù)項的類型要一致C．每個數(shù)據(jù)元素都一樣D．數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等答案：B（4）以下說法正確的是（ ）。A．數(shù)據(jù)元素是數(shù)據(jù)的最小單位B．數(shù)據(jù)項是數(shù)據(jù)的基本單位C．數(shù)據(jù)結構是帶有結構的各數(shù)據(jù)項的集合D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結構答案：D解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位，數(shù)據(jù)結構是帶有結構的各數(shù)據(jù)元素的集合。（5）算法的時間復雜度取決于（ ）。A．問題的規(guī)模 B．待處理數(shù)據(jù)的初態(tài)C．計算機的配置 D．A和B答案：D解釋：算法的時間復雜度不僅與問題的規(guī)模有關，還與問題的其他因素有關。如某些排序的算法，其執(zhí)行時間與待排序記錄的初始狀態(tài)有關。為此，有時會對算法有最好、最壞以及平均時間復雜度的評價。（6）以下數(shù)據(jù)結構中，（ ）是非線性數(shù)據(jù)結構A．樹 B．字符串 C．隊列 D．棧答案：A6．試分析下面各程序段的時間復雜度。（1）x=90。 y=100。while(y0)if(x100) {x=x10。y。}else x++。答案：O(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。（2）for (i=0。 in。 i++)for (j=0。 jm。 j++)a[i][j]=0。答案：O(m*n)解釋：語句a[i][j]=0。的執(zhí)行次數(shù)為m*n。（3）s=0。 for i=0。 in。 i++)for(j=0。 jn。 j++) s+=B[i][j]。sum=s。答案：O(n2)解釋：語句s+=B[i][j]。的執(zhí)行次數(shù)為n2。（4）i=1。 while(i=n) i=i*3。答案：O(log3n) 解釋：語句i=i*3。的執(zhí)行次數(shù)為235。log3n（5）x=0。for(i=1。 in。 i++) for (j=1。 j=ni。 j++)x++。答案：O(n2)解釋：語句x++。的執(zhí)行次數(shù)為n1+n2+……＋1= n(n1)/2。（6）x=n。 //n1y=0。while(x≥(y+1)* (y+1)) y++。答案：O()解釋：語句y++。的執(zhí)行次數(shù)為235。第2章 線性表1．選擇題（1）順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）。A．110 B．108 C．100 D．120答案：B解釋：順序表中的數(shù)據(jù)連續(xù)存儲，所以第5個元素的地址為：100+2*4=108。（2）在n個結點的順序表中，算法的時間復雜度是O(1)的操作是（ ）。A．訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅(qū)（2≤i≤n） B．在第i個結點后插入一個新結點（1≤i≤n）C．刪除第i個結點（1≤i≤n）D．將n個結點從小到大排序答案：A解釋：在順序表中插入一個結點的時間復雜度都是O(n2)，排序的時間復雜度為O(n2)或O(nlog2n)。順序表是一種隨機存取結構，訪問第i個結點和求第i個結點的直接前驅(qū)都可以直接通過數(shù)組的下標直接定位，時間復雜度是O(1)。（3） 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 的元素個數(shù)為（ ）。A．8 B． C．63 D．7答案：B解釋：平均要移動的元素個數(shù)為：n/2。（4）鏈接存儲的存儲結構所占存儲空間（ ）。A．分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B．只有一部分，存放結點值C．只有一部分，存儲表示結點間關系的指針D．分兩部分，一部分存放結點值，另一部分存放結點所占單元數(shù)答案：A（5）線性表若采用鏈式存儲結構時，要求內(nèi)存中可用存儲單元的地址（ ）。A．必須是連續(xù)的 B．部分地址必須是連續(xù)的C．一定是不連續(xù)的 D．連續(xù)或不連續(xù)都可以答案：D（6）線性表Ｌ在（ ）情況下適用于使用鏈式結構實現(xiàn)。A．需經(jīng)常修改Ｌ中的結點值 Ｂ．需不斷對Ｌ進行刪除插入 C．Ｌ中含有大量的結點 Ｄ．Ｌ中結點結構復雜答案：B解釋：鏈表最大的優(yōu)點在于插入和刪除時不需要移動數(shù)據(jù)，直接修改指針即可。（7）單鏈表的存儲密度（ ）。A．大于1 B．等于1 C．小于1 D．不能確定答案：C解釋：存儲密度是指一個結點數(shù)據(jù)本身所占的存儲空間和整個結點所占的存儲空間之比，假設單鏈表一個結點本身所占的空間為D，指針域所占的空間為N，則存儲密度為：D/(D+N)，一定小于1。（8）將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（ ）。A．n B．2n1 C．2n D．n1答案：A解釋：當?shù)谝粋€有序表中所有的元素都小于（或大于）第二個表中的元素，只需要用第二個表中的第一個元素依次與第一個表的元素比較，總計比較n次。（9）在一個長度為n的順序表中，在第i個元素（1≤i≤n+1）之前插入一個新元素時須向后移動（ ）個元素。A．ni B．ni+1 C．ni1 D．I答案：B(10) 線性表L=(a1，a2,……an)，下列說法正確的是（ ）。A．每個元素都有一個直接前驅(qū)和一個直接后繼B．線性表中至少有一個元素C．表中諸元素的排列必須是由小到大或由大到小D．除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼。答案：D(11) 創(chuàng)建一個包括n個結點的有序單鏈表的時間復雜度是（ ）。A．O(1) B．O(n) C．O(n2) D．O(nlog2n)答案：C解釋：單鏈表創(chuàng)建的時間復雜度是O(n)，而要建立一個有序的單鏈表，則每生成一個新結點時需要和已有的結點進行比較，確定合適的插入位置，所以時間復雜度是O(n2)。(12) 以下說法錯誤的是（ ）。 A．求表長、定位這兩種運算在采用順序存儲結構時實現(xiàn)的效率不比采用鏈式存儲結構時實現(xiàn)的效率低B．順序存儲的線性表可以隨機存取C．由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活D．線性表的鏈式存儲結構優(yōu)于順序存儲結構 答案：D解釋：鏈式存儲結構和順序存儲結構各有優(yōu)缺點，有不同的適用場合。(13) 在單鏈表中，要將s所指結點插入到p所指結點之后，其語句應為（ ）。A．snext=p+1。 pnext=s。B．(*p).next=s。 (*s).next=(*p).next。C．snext=pnext。 pnext=snext。D．snext=pnext。 pnext=s。 答案：D (14) 在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針（ ）。A．pnextprior=pprior。 ppriornext=pnext。B．pnext=pnextnext。 pnextprior=p。C．ppriornext=p。 pprior=ppriorprior。D．pprior=pnextnext。 pnext=ppriorprior。答案：A(15) 在雙向循環(huán)鏈表中，在p指針所指的結點后插入q所指向的新結點，其修改指針的操作是（ ）。A．pnext=q。 qprior=p。 pnextprior=q。 qnext=q。B．pnext=q。 pnextprior=q。 qprior=p。 qnext=pnext。C．qprior=p。 qnext=pnext。 pnextprior=q。 pnext=q。D．qprior=p。 qnext=pnext。 pnext=q。 pnextprior=q。答案：C2．算法設計題（1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復的數(shù)據(jù)。[題目分析]合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點，從第一個結點開始進行比較，當兩個鏈表La和Lb均為到達表尾結點時，依次摘取其中較小者重新鏈接在Lc表的最后。如果兩個表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無重復的元素。當一個表到達表尾結點，為空時，將非空表的剩余元素直接鏈接在Lc表的最后。[算法描述]void MergeList(LinkList am