算法與數據結構c語言版課后習題答案機械工業(yè)出版社第1章緒論習題參考答案

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

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

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

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

5、線性結構，可以順序存儲（也可以鏈式存儲），運算可以有插入、刪除、查詢、等等。4.簡述算法的五個特性，對算法設計的要求。8.已知輸入x，y，z三個不相等的整數，設計一個“高效”算法，使得這三個數按從小到大輸出?！案咝А钡暮x是用最少的元素比較次數、元素移動次數和輸出次數。voidBest()按序輸出三個整數的優(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在數組A[n]中查找值為k的元素，若找到則輸出其位置i(1≤i≤n)，否則輸出0作為標志。設計算法求解此問題，并分析在最壞情況下的時間復雜度【題目分析】從后向前查找，若找到與k值相同的元素則返回其位置，否則返回0。intSearch(ElemTypeA[n1]ElemTypek)i=nwile(i=1)i