數(shù)據(jù)結(jié)構(gòu)課后答案

1、第1章緒論緒論1簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型。答案：數(shù)據(jù)數(shù)據(jù)：是客觀事物的符號表示，指所有能輸入到計算機中并被計算機程序處理的符號的總稱。如數(shù)學(xué)計算中用到的整數(shù)和實數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動畫等通過特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進(jìn)行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、記

2、錄等。數(shù)據(jù)元素用于完整地描述一個對象，如一個學(xué)生記錄，樹中棋盤的一個格局（狀態(tài)）、圖中的一個頂點等。數(shù)據(jù)項數(shù)據(jù)項：是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位。例如，學(xué)生基本信息表中的學(xué)號、姓名、性別等都是數(shù)據(jù)項。數(shù)據(jù)對象數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如：整數(shù)數(shù)據(jù)對象是集合N=0，1，2，…，字母字符數(shù)據(jù)對象是集合C=‘A’，‘B’，…，‘Z’，‘a(chǎn)’，‘b’，…，‘z’，學(xué)生基本信息表也可是一個數(shù)據(jù)對

3、象。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。存儲結(jié)構(gòu)：存儲結(jié)構(gòu)：數(shù)據(jù)對象在計算機中的存儲表示，也稱為物理結(jié)構(gòu)物理結(jié)構(gòu)。抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問題的數(shù)學(xué)模型，以及定

4、義在這個模型上的一組操作的總稱。具體包括三部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合和對數(shù)據(jù)對象的基本操作的集合。2試舉一個數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的含義和相互關(guān)系。答案：例如有一張學(xué)生基本信息表，包括學(xué)生的學(xué)號、姓名、性別、籍貫、專業(yè)等。每個學(xué)生基本信息記錄對應(yīng)一個數(shù)據(jù)元素，學(xué)生記錄按順序號排列，形成了學(xué)生基本信息記錄的線性序列。對于整個表來說，只有一個開始結(jié)點(它的前面無記錄)和一個終端結(jié)點(它的后面無記錄)，其他的

5、結(jié)點則各有一個也只有一個直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的邏輯結(jié)構(gòu)，即線性結(jié)構(gòu)。這些學(xué)生記錄在計算機中的存儲表示就是存儲結(jié)構(gòu)。如果用連續(xù)的存儲單元(如用數(shù)組表示)來存放這些記錄，則稱為順序存儲結(jié)構(gòu)；如果存儲單元不連續(xù)，而是隨機存放各個記錄，然后用指針進(jìn)行鏈接，則稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。即相同的邏輯結(jié)構(gòu)，可以對應(yīng)不同的存儲結(jié)構(gòu)。3簡述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。答案：（1）集合結(jié)構(gòu)數(shù)據(jù)元素之間除了“屬于同一

6、集合”的關(guān)系外，別無其他關(guān)系。例如，確定一名學(xué)生是否為班級成員，只需將班級看做一個集合結(jié)構(gòu)。（2）線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)按照其入學(xué)報到的時間先后順序進(jìn)行排列，將組成一個線性結(jié)構(gòu)。（3）樹結(jié)構(gòu)C數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)答案：D解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。（5）算法的時間復(fù)雜度取決于（

7、）。A問題的規(guī)模B待處理數(shù)據(jù)的初態(tài)C計算機的配置DA和B答案：D解釋：算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān)，還與問題的其他因素有關(guān)。如某些排序的算法，其執(zhí)行時間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時會對算法有最好、最壞以及平均時間復(fù)雜度的評價。（6）以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)A樹B字符串C隊列D棧答案：A6試分析下面各程序段的時間復(fù)雜度。（1）x=90y=100while(y0)if(x100)x=x10yelsex答案：O(

8、1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。（2）f(i=0ini)f(j=0jmj)a[i][j]=0答案：O(mn)解釋：語句a[i][j]=0的執(zhí)行次數(shù)為mn。（3）s=0fi=0ini)f(j=0jnj)s=B[i][j]sum=s答案：O(n2)解釋：語句s=B[i][j]的執(zhí)行次數(shù)為n2。（4）i=1while(i=n)i=i3答案：O(log3n)解釋：語句i=i3的執(zhí)行次數(shù)為?log3n?。（5）x=0f(i=1ini)f(j=1