算法與數(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ù)元素之間的結構以及允許施加操作的一種總體描述。每一種計算機程序設計語言都定義

2、有自己的數(shù)據(jù)類型?！皵?shù)據(jù)結構”這一術語有兩種含義，一是作為一門課程的名稱；二是作為一個科學的概念。作為科學概念，目前尚無公認定義，一般認為，討論數(shù)據(jù)結構要包括三個方面，一是數(shù)據(jù)的邏輯結構，二是數(shù)據(jù)的存儲結構，三是對數(shù)據(jù)進行的操作（運算）。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)結構，后者是前者的一種簡化情況。數(shù)據(jù)的邏輯結構反映數(shù)據(jù)元素之間的邏輯關系（即數(shù)據(jù)元素之間的關聯(lián)方式或“鄰接關系”），數(shù)據(jù)的存儲結構是數(shù)據(jù)結構在計

3、算機中的表示，包括數(shù)據(jù)元素的表示及其關系的表示。數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作，運算是定義在邏輯結構上的，和存儲結構無關，而運算的實現(xiàn)則依賴于存儲結構。數(shù)據(jù)結構在計算機中的表示稱為物理結構，又稱存儲結構。是邏輯結構在存儲器中的映像，包括數(shù)據(jù)元素的表示和關系的表示。邏輯結構與計算機無關。算法是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。一個算法應該具有下列特性：有窮性、確定性、可行性、輸入和輸出。2

4、.數(shù)據(jù)的邏輯結構分哪幾種，為什么說邏輯結構是數(shù)據(jù)組織的主要方面？【解答】數(shù)據(jù)的邏輯結構分為線性結構和非線性結構。（也可以分為集合、線性結構、樹形結構和圖形即網(wǎng)狀結構）。邏輯結構是數(shù)據(jù)組織的某種“本質(zhì)性”的東西：（1）邏輯結構與數(shù)據(jù)元素本身的形式、內(nèi)容無關。（2）邏輯結構與數(shù)據(jù)元素的相對位置無關。（3）邏輯結構與所含數(shù)據(jù)元素的個數(shù)無關。3.試舉一個數(shù)據(jù)結構的例子，敘述其邏輯結構、存儲結構、運算三方面的內(nèi)容?！窘獯稹咳鐚W生成績表，邏輯結構是

5、線性結構，可以順序存儲（也可以鏈式存儲），運算可以有插入、刪除、查詢、等等。4.簡述算法的五個特性，對算法設計的要求。8.已知輸入x，y，z三個不相等的整數(shù)，設計一個“高效”算法，使得這三個數(shù)按從小到大輸出?！案咝А钡暮x是用最少的元素比較次數(shù)、元素移動次數(shù)和輸出次數(shù)。voidBest()按序輸出三個整數(shù)的優(yōu)化算法intabctscanf(“%d%d%d”if(ab)t=aa=bb=t:a和b已正序if(bc)t=cc=bc已到位if(

6、at)b=aa=ta和b已正序elseb=tifprintf(“%d%d%dn”abc)最佳2次比較，無移動；最差3次比較，7個賦值9在數(shù)組A[n]中查找值為k的元素，若找到則輸出其位置i(1≤i≤n)，否則輸出0作為標志。設計算法求解此問題，并分析在最壞情況下的時間復雜度【題目分析】從后向前查找，若找到與k值相同的元素則返回其位置，否則返回0。intSearch(ElemTypeA[n1]ElemTypek)i=nwile(i=1)i