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

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

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

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

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

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