算法與數(shù)據(jù)結(jié)構(gòu)c語言版課后習(xí)題答案機械工業(yè)出版社第1章緒論習(xí)題參考答案

1、第1章概論概論習(xí)題參考答案習(xí)題參考答案一、一、基礎(chǔ)知識題1.簡述下列概念數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)類型，數(shù)據(jù)結(jié)構(gòu)，邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)，算法?！窘獯稹繑?shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計算機中并被計算機程序識別和處理的符號的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等。數(shù)據(jù)類型是對數(shù)據(jù)的取值范圍、數(shù)據(jù)元素之間的結(jié)構(gòu)以及允許施加操作的一種總體描述。每一種計算機程序設(shè)計語言都定義

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

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

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

5、線性結(jié)構(gòu)，可以順序存儲（也可以鏈式存儲），運算可以有插入、刪除、查詢、等等。4.簡述算法的五個特性，對算法設(shè)計的要求。8.已知輸入x，y，z三個不相等的整數(shù)，設(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作為標志。設(shè)計算法求解此問題，并分析在最壞情況下的時間復(fù)雜度【題目分析】從后向前查找，若找到與k值相同的元素則返回其位置，否則返回0。intSearch(ElemTypeA[n1]ElemTypek)i=nwile(i=1)i