數(shù)據(jù)結(jié)構(gòu)與算法緒論答案-

1、第 1 章 緒 論(2005-07-14 -第 1 章 緒 論課后習(xí)題講解1. 填空( 是數(shù)據(jù)的基本單位,在計算機程序中通常作為一個整體進行考慮和處理。【解答】數(shù)據(jù)元素( 是數(shù)據(jù)的最小單位,( 是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位?！窘獯稹繑?shù)據(jù)項,數(shù)據(jù)元素【分析】數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。 從邏輯關(guān)系上講,數(shù)據(jù)結(jié)構(gòu)主要分為( 、( 、( 和( ?！窘獯稹考?線性結(jié)構(gòu),樹結(jié)構(gòu),圖結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)主要有( 和( 兩種基本方法,不論哪種存儲結(jié)構(gòu),都要存儲兩方面的內(nèi)容:( 和( 。【解答】順序存儲結(jié)構(gòu),鏈接存儲結(jié)構(gòu),數(shù)據(jù)元素,數(shù)據(jù)元素之間的關(guān)系 算法具有五個特性,分別是( 、(

2、 、( 、( 、( ?！窘獯稹坑辛銈€或多個輸入,有一個或多個輸出,有窮性,確定性,可行性 算法的描述方法通常有( 、( 、( 和( 四種,其中,( 被稱為算法語言?！窘獯稹孔匀徽Z言,程序設(shè)計語言,流程圖,偽代碼,偽代碼 在一般情況下,一個算法的時間復(fù)雜度是( 的函數(shù)。【解答】問題規(guī)模 設(shè)待處理問題的規(guī)模為n,若一個算法的時間復(fù)雜度為一個常數(shù),則表示成數(shù)量級的形式為( ,若為n*log25n,則表示成數(shù)量級的形式為( ?！窘獯稹?1,(nlog2n【分析】用大O記號表示算法的時間復(fù)雜度,需要將低次冪去掉,將最高次冪的系數(shù)去掉。2. 選擇題 順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由( 表示的,鏈接

3、存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由( 表示的。A 線性結(jié)構(gòu)B 非線性結(jié)構(gòu)C 存儲位置D 指針【解答】C,D【分析】順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素,其邏輯關(guān)系由存儲位置(即元素在數(shù)組中的下標(biāo)表示;鏈接存儲結(jié)構(gòu)中一個數(shù)據(jù)元素對應(yīng)鏈表中的一個結(jié)點,元素之間的邏輯關(guān)系由結(jié)點中的指針表示。 假設(shè)有如下遺產(chǎn)繼承規(guī)則:丈夫和妻子可以相互繼承遺產(chǎn);子女可以繼承父親或母親的遺產(chǎn);子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是( 。A 樹B 圖C 線性表D 集合【解答】B【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素,根據(jù)題意畫出邏輯結(jié)構(gòu)圖。 算法指的是( 。A 對特定問題求

4、解步驟的一種描述,是指令的有限序列。B 計算機程序C 解決問題的計算方法D 數(shù)據(jù)處理【解答】A【分析】計算機程序是對算法的具體實現(xiàn);簡單地說,算法是解決問題的方法;數(shù)據(jù)處理是通過算法完成的。所以,只有A是算法的準(zhǔn)確定義。 下面( 不是算法所必須具備的特性。A 有窮性B 確切性C 高效性D 可行性【解答】C【分析】高效性是好算法應(yīng)具備的特性。 算法分析的目的是( ,算法分析的兩個主要方面是( 。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性B 研究算法中輸入和輸出的關(guān)系C 分析算法的效率以求改進D 分析算法的易讀性和文檔性E 空間性能和時間性能F 正確性和簡明性G 可讀性和文檔性 H 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性【解答】C

5、,E3. 判斷題 算法的時間復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定?！窘獯稹垮e。時間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作:插入、刪除和查找。【解答】錯。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系?！窘獯稹垮e。是數(shù)據(jù)之間的邏輯關(guān)系的整體。 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)?！窘獯稹繉?。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。 基于某種邏輯結(jié)構(gòu)之上的基本操作,其實現(xiàn)是唯一的?！窘獯稹垮e?；静僮鞯膶崿F(xiàn)是基于某種存儲結(jié)構(gòu)設(shè)計的,因而不是唯一的。4. 分析以下各程序段,并用大O記號表示其執(zhí)行時間

6、?！窘獯稹?基本語句是k=k+10*i,共執(zhí)行了n-2次,所以T(n=O(n。 基本語句是k=k+10*i,共執(zhí)行了n次,所以T(n=O(n。 分析條件語句,每循環(huán)一次,i+j 整體加1,共循環(huán)n次,所以T(n=O(n。 設(shè)循環(huán)體共執(zhí)行T(n次,每循環(huán)一次,循環(huán)變量y加1,最終T(n=y,即:(T(n+12n,所以T(n=O(n1/2。 x+是基本語句,所以5.設(shè)有數(shù)據(jù)結(jié)構(gòu)(D,R,其中D=1, 2, 3, 4, 5,6,R=(1,2,(2,3,(2,4,(3,4,(3,5,(3,6,(4,5,(4,6。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)?！窘獯稹科溥壿嫿Y(jié)構(gòu)圖如圖1-3所示,它是一種圖結(jié)構(gòu)。

7、6. 為整數(shù)定義一個抽象數(shù)據(jù)類型,包含整數(shù)的常見運算,每個運算對應(yīng)一個基本操作,每個基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件。【解答】整數(shù)的抽象數(shù)據(jù)類型定義如下:ADT integerData整數(shù)a:可以是正整數(shù)(1, 2, 3, 、負(fù)整數(shù)(-1, -2, -3, 和零OperationConstructor前置條件:整數(shù)a不存在輸入:一個整數(shù)b功能:構(gòu)造一個與輸入值相同的整數(shù)輸出:無后置條件:整數(shù)a具有輸入的值Set前置條件:存在一個整數(shù)a輸入:一個整數(shù)b功能:修改整數(shù)a的值,使之與輸入的整數(shù)值相同輸出:無后置條件:整數(shù)a的值發(fā)生改變Add前置條件:存在一個整數(shù)a輸入:一個整

8、數(shù)b功能:將整數(shù)a與輸入的整數(shù)b相加輸出:相加后的結(jié)果后置條件:整數(shù)a的值發(fā)生改變Sub前置條件:存在一個整數(shù)a輸入:一個整數(shù)b功能:將整數(shù)a與輸入的整數(shù)b相減輸出:相減的結(jié)果后置條件:整數(shù)a的值發(fā)生改變Multi前置條件:存在一個整數(shù)a輸入:一個整數(shù)b功能:將整數(shù)a與輸入的整數(shù)b相乘輸出:相乘的結(jié)果后置條件:整數(shù)a的值發(fā)生改變Div前置條件:存在一個整數(shù)a輸入:一個整數(shù)b功能:將整數(shù)a與輸入的整數(shù)b相除輸出:若整數(shù)b為零,則拋出除零異常,否則輸出相除的結(jié)果后置條件:整數(shù)a的值發(fā)生改變Mod前置條件:存在一個整數(shù)a輸入:一個整數(shù)b功能:求當(dāng)前整數(shù)與輸入整數(shù)的模,即正的余數(shù)輸出:若整數(shù)b為零,則

9、拋出除零異常,否則輸出取模的結(jié)果后置條件:整數(shù)a的值發(fā)生改變Equal前置條件:存在一個整數(shù)a輸入:一個整數(shù)b功能:判斷整數(shù)a與輸入的整數(shù)b是否相等輸出:若相等返回1,否則返回0后置條件:整數(shù)a的值不發(fā)生改變endADT7. 求多項式A(x的算法可根據(jù)下列兩個公式之一來設(shè)計: A(x=anxn+an-1xn-1+a1x+a0 A(x=(anx+an-1x+a1x+a0根據(jù)算法的時間復(fù)雜度分析比較這兩種算法的優(yōu)劣?！窘獯稹康诙N算法的時間性能要好些。第一種算法需執(zhí)行大量的乘法運算,而第二種算法進行了優(yōu)化,減少了不必要的乘法運算。8. 算法設(shè)計(要求:算法用偽代碼和C+描述,并分析最壞情況下的時間

10、復(fù)雜度 對一個整型數(shù)組An設(shè)計一個排序算法?！窘獯稹肯旅媸呛唵芜x擇排序算法的偽代碼描述。下面是簡單選擇排序算法的C+描述。The Home of jetmambo - 第 1 章 緒 論 分析算法，有兩層嵌套的for循環(huán)，所以， 。 找出整型數(shù)組An中元素的最大值和次最大值。 【解答】算法的偽代碼描述如下： 算法的C+描述如下： 分析算法，只有一層循環(huán)，共執(zhí)行n-2次，所以，T(n=O(n。 學(xué)習(xí)自測及答案 1順序存儲結(jié)構(gòu)的特點是（ ），鏈接存儲結(jié)構(gòu)的特點是（ ）。 【解答】用元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，用指示元素存儲地址的指針表示數(shù)據(jù)元 素之間的邏輯關(guān)系。 2. 算

11、法在發(fā)生非法操作時可以作出處理的特性稱為（ ）。 【解答】健壯性 3. 常見的算法時間復(fù)雜度用大記號表示為：常數(shù)階( 、對數(shù)階( 、線性階 ( 、平方階( 和指數(shù)階( 。 【解答】(1，(log2n，(n，(n2，(2n 4將下列函數(shù)按它們在n 時的無窮大階數(shù)，從小到大排列。 n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2n, n!, n2+log2n 【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2n, n! page: 6 The Home o

12、f jetmambo - 第 1 章 緒 論 5試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計語言中數(shù)據(jù)類型概念的區(qū)別。 【解答】數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。而抽象數(shù)據(jù)類型是指一個數(shù)據(jù)結(jié)構(gòu)以及定義在 該結(jié)構(gòu)上的一組操作。程序設(shè)計語言中的數(shù)據(jù)類型是一個值的集合和定義在這個值集上一組操作的總稱。抽象數(shù) 據(jù)類型可以看成是對數(shù)據(jù)類型的一種抽象。 6. 對下列用二元組表示的數(shù)據(jù)結(jié)構(gòu),試分別畫出對應(yīng)的邏輯結(jié)構(gòu)圖，并指出屬于何種結(jié)構(gòu)。 A=(D，R， 其中D=a1, a2, a3, a4，R= B=(D，R， 其中D=a, b, c, d, e, f，R=, C=( D，R，其中D=a，b，c，d，e，f，R=, D=(D，R， 其中D=1, 2, 3, 4, 5, 6， R=(1, 2，(1, 4，(2, 3，(2, 4，(3, 4，(3, 5，(3