數(shù)據(jù)結構（c語言版）程海英-習題答案

1、第1章習題1.解釋下列術語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結構、存儲結構、線性結構、算法、抽象數(shù)據(jù)類型。略。2.試舉一個數(shù)據(jù)結構的例子，敘述其邏輯結構、存儲結構及運算3方面的內(nèi)容。當你拿起一本厚厚的漢語字典查找某一個漢字時，你首先必須知道你使用的字典的編碼方法，然后才能按照偏傍部首、四角號碼或者拼音等相應的編碼方法較快地查到你所需要查找的漢字。3.選擇題1）在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（）。A動態(tài)結構和靜態(tài)結構B緊湊結構和非

2、緊湊結構C線性結構和非線性結構D內(nèi)部結構和外部結構2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關的是數(shù)據(jù)的（）。A存儲結構B存儲實現(xiàn)C邏輯結構D運算實現(xiàn)3）通常要求同一邏輯結構中的所有數(shù)據(jù)元素具有相同的特性，這意味著（）。A數(shù)據(jù)具有同一特點B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應數(shù)據(jù)項的類型要一致C每個數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等4）以下說法正確的是（）。A數(shù)據(jù)元素是數(shù)據(jù)的最小單位B數(shù)據(jù)項是數(shù)據(jù)的基本

3、單位C數(shù)據(jù)結構是帶有結構的各數(shù)據(jù)項的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結構5）以下數(shù)據(jù)結構中，（）是非線性數(shù)據(jù)結構A樹B字符串C隊D棧4.填空題1）數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象及它們之間的關系和運算等的學科。2）數(shù)據(jù)結構被形式定義為（DR），其中D是數(shù)據(jù)元素的有限集合，R是D上的關系有限集合。3）數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構和數(shù)據(jù)的運算這三個方面的內(nèi)容。第2章習題1.線性表有兩種

4、存儲結構，分別是順序表和鏈表。試問：兩種存儲結構各有哪些主要優(yōu)缺點①順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點：存儲密度大，存儲空間利用率高。缺點：插入或刪除元素時不方便。②鏈式存儲時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針優(yōu)點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度?。?），存儲空間利用率低。順序表適宜

5、于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。2.試分析線性表的特征并舉例說明。線性表是有限元素（a0a1...an1）的有序序列，該線性表的第一個元素是a0，第二個元素是a1，...an1，稱ai1是ai的直接前驅(qū)元素，ai1是ai的直接后繼元素。每個元素只有一個直接前驅(qū)，僅有一個直接后繼元素。例如

6、，有一組實驗數(shù)據(jù)（41213453627175817645），它是一個線性表，它們之間有著一定的順序。這個線性表有10個元素，即表長為10，元素34的直接前驅(qū)元素是21，而直接后繼元素是53。3.選擇題1）在一個長度為n的順序存儲的線性表中，向第i個元素（1≤i≤n1）位置插入一個新元素時，需要從后向前依次后移（）個元素。AniBni1Cni1Di2）在一個長度為n的順序存儲的線性表中，刪除第i個元素（1≤i≤n）時，需要從前向后依次前