數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用筆記含答案緒論

1、第一章緒論一、填空題1、數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素 的集合。2、數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu) 和存儲結(jié)構(gòu)兩個層次。3、數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素；二是 關(guān)系 。4、算法 是為了解決某類問題而規(guī)定的一個有限長的操作序列。5、一個算法必須滿足五個重要特性：有窮性、確定性、可行性、輸入、輸出 。6、一個算法的優(yōu)劣從 正確性、可讀性、健壯性和高效性四個方面來評價。7、一條語句的重復執(zhí)行次數(shù)稱作語句頻度。8、根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特征，通常由四類基本結(jié)構(gòu)：集合結(jié)構(gòu)、 線性Z構(gòu)、樹結(jié)構(gòu)和 圖結(jié)構(gòu)（或網(wǎng)狀結(jié)構(gòu)） 。9、數(shù)據(jù)元素之間的關(guān)系在計算機中有兩種不同的表示方法：順序存儲結(jié)構(gòu) 和一鏈式存儲結(jié)

2、構(gòu)。二、判斷題1、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系。（X ）2、順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（X ）3、數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的次序關(guān)系，它依賴于數(shù)據(jù)的存儲結(jié)構(gòu)。（X ）4、算法的優(yōu)劣與描述算法的語言無關(guān)，但與所用計算機的性能有關(guān)。（X ）5、算法必須有輸出，但可以沒有輸入。（V ）三、單項選擇題1、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ C ）。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ù)的（C ）。A.存儲結(jié)構(gòu)B,存儲實現(xiàn)C.邏輯結(jié)

3、構(gòu)D.運算實現(xiàn)3、通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（B ）。A.數(shù)據(jù)具有同一特點B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致C.每個數(shù)據(jù)元素都一樣D.數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等4、以下說法正確的是（D ）。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)解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。5、算法的時間復雜度取決于（ D ）。A.問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.計算機的配置D. A

4、和B解釋：算法的時間復雜度不僅與問題的規(guī)模有關(guān)，還與問題的其他因素有關(guān)。 如某些排序的算法，其執(zhí)行時間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時會對算法有最好、最壞以及平均時間復雜度的評價。6、以下數(shù)據(jù)結(jié)構(gòu)中，（A ）是非線性數(shù)據(jù)結(jié)構(gòu)A.樹B.字符串C.隊列D.棧四、簡答題（若地方不夠請寫到背面）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ù)學計算中用到的整數(shù)和實數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動畫等通過特殊編碼定義后的數(shù)據(jù)。

5、數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、 結(jié)點、記錄等。數(shù)據(jù)元素用于完整地描述一個對象，如一個學生記錄，樹中棋盤的一個格局（狀態(tài)）、圖中的一個頂點等。數(shù)據(jù)項：是組成數(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' , 

6、9;b',， 'z' ,學生基本信息表也可是一個數(shù)據(jù)對象。數(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)：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。因此，數(shù)據(jù) 的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學模型。存儲結(jié)構(gòu)：數(shù)據(jù)對象在計算機中的存儲表示，也稱為 物理結(jié)構(gòu)。抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問題的數(shù)學模型，以及定義在這個模型上的一組操作的總稱。具體包括三部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合和對數(shù)據(jù)對象的基本操作的集合。2、試舉一個數(shù)據(jù)

7、結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的含義和相互關(guān)系。答案：例如有一張學生基本信息表，包括學生的學號、姓名、性別、籍貫、專業(yè)等。每個學生基本信息記錄對應(yīng)一個數(shù)據(jù)元素，學生記錄按順序號排列，形成了學生基本信息記錄的線性序列。對于整個表來說，只有一個開始結(jié)點（它的前面無記錄）和一個終端結(jié)點（它的后面無記錄），其他的 結(jié)點則各有一個也只有一個直接前趨和直接后繼。學生記錄之間的這種關(guān)系就確定了學生表的邏輯結(jié)構(gòu)，即線性結(jié)構(gòu)。這些學生記錄在計算機中的存儲表示就是存儲結(jié)構(gòu)。如果用連續(xù)的存儲單元（如用數(shù)組表示）來存放這些記錄，則稱為順序存儲結(jié)構(gòu)；如果存儲單元不連續(xù)，而是隨機存放各個記錄，然后用指針進行鏈

8、接，則稱為鏈式存儲結(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ù)元素之間除了 “屬于同一集合”的關(guān)系外，別無其他關(guān)系。例如，確定一名學生是否為 班級成員，只需將班級看做一個集合結(jié)構(gòu)。(2)線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對一的關(guān)系。例如，將學生信息數(shù)據(jù)按照其入學報到的時間先后順序進行排列，將組成一個線性結(jié)構(gòu)。(3)樹結(jié)構(gòu)數(shù)據(jù)元素之間存在一對多的關(guān)系。例如，在班級的管理體系中，班長管理多個組長， 每位組長管理多名組員，從而構(gòu)成樹形結(jié)構(gòu)。(4)圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)元素之間存在多對多的關(guān)系。例如，多位同學之間的朋友關(guān)系，任何兩位

9、同學都可以是朋友，從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。其中樹結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。00-00-0四類基本邏輯結(jié)構(gòu)關(guān)系圖4、存儲結(jié)構(gòu)由哪兩種基本的存儲方法實現(xiàn)？ 答案：(1)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助程序設(shè)計語言的數(shù)組類型來描述。(2)鏈式存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲空間中，而鏈式存儲結(jié)構(gòu)，無需占用一整塊存儲空間。但為了表示結(jié)點之間的關(guān)系， 需要給每個結(jié)點附加指針字段， 用于存放后繼元素 的存儲地址。所以鏈式存儲結(jié)構(gòu)通常借助于程序設(shè)計語言的指針類型來描述。5、簡述算法和程序的區(qū)別。答案：(僅供參考)算

10、法是為了解決某類問題而規(guī)定的一個有限長的操作序列。算法是解決問題的步驟；程序是算法的代碼實現(xiàn)算法要依靠程序來完成功能；程序需要算法作為靈魂五、分析題(寫在程序右側(cè)空白處)1、分析下列程序段中帶“ #”的標記語句的執(zhí)行頻度(n為正整數(shù))1 )j=1 ; k=0while(j<=n-1) j+；k+=j;/*#*/ n-1)2 )i=0;s=0;n=100doi+；s+=10*i;/*#*/ 1while(!(i<n&&s<n);3 )k=0;for(i=0;i<n;i+)for(j=i;j<n;j+)k+;/*#*/ n(n+ 1)/24 )a=1;

11、b=0;while (a+b<=n)if(a<b)a+;/*#*/ nelseb+;5 )x=91;y=100;while(y>0)if(x>100)x-=10;y-;/*#*/ 100elsex+;2、寫出下列各程序段關(guān)于n的時間復雜度1 )a=1;m=1;while(a<n)m+=a;a*=3;O(n)2 ) 設(shè)n是偶數(shù)for(i=1,s=0;i<=n;i+) for(j=2*i;j<=n;j+) s+;3 )for(i=1;i<=n-1; i+)k=i;for(j=i+1;j<=n;j+)if(Rj>Rj+1)k=j;t=Rk;

12、Rk = Ri;Ri = t;)3、試分析下面各程序段的時間復雜度。1) x=90; y=100;while(y>0)if(x>100)x=x-10;y-;else x+;答案：0(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。2) for (i=0; i<n; i+)for (j=0; j<m; j+)aiU=O；答案：0(m*n)解釋：語句aij=O; 的執(zhí)行次數(shù)為m*n。3) s=0;for i=0; i<n; i+)forQ=0; j<n; j+)s+=BiU；sum=s;答案：OS?)解釋：語句s+=Bij; 的執(zhí)行次數(shù)為n2o4) i=1;while(i<=n)i=i*3;答案：O(log 3n)解釋：語句i=i*3;的執(zhí)行次