數(shù)據(jù)結構習題與答案

1、第1章緒論課后習題講解課后習題講解1.填空⑴（）是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理?！窘獯稹繑?shù)據(jù)元素⑵（）是數(shù)據(jù)的最小單位，（）是討論數(shù)據(jù)結構時涉及的最小數(shù)據(jù)單位?！窘獯稹繑?shù)據(jù)項，數(shù)據(jù)元素【分析】數(shù)據(jù)結構指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關系。⑶從邏輯關系上講，數(shù)據(jù)結構主要分為（）、（）、（）和（）?！窘獯稹考?，線性結構，樹結構，圖結構⑷數(shù)據(jù)的存儲結構主要有（）和（）兩種基本方法，不論哪種存儲結構，都要存儲兩

2、方面的內容：（）和（）?！窘獯稹宽樞虼鎯Y構，鏈接存儲結構，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關系⑸算法具有五個特性，分別是（）、（）、（）、（）、（）?！窘獯稹坑辛銈€或多個輸入，有一個或多個輸出，有窮性，確定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四種，其中，（）被稱為算法語言?！窘獯稹孔匀徽Z言，程序設計語言，流程圖，偽代碼，偽代碼⑺在一般情況下，一個算法的時間復雜度是（）的函數(shù)?！窘獯稹繂栴}規(guī)模⑻設待處理問題的規(guī)模為n，若一個算

3、法的時間復雜度為一個常數(shù)，則表示成數(shù)量級的形式為（），若為nlog25n，則表示成數(shù)量級的形式為（）?！窘獯稹喀?1)，Ο(nlog2n)【分析】用大O記號表示算法的時間復雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。2.選擇題⑴順序存儲結構中數(shù)據(jù)元素之間的邏輯關系是由（）表示的，鏈接存儲結構中的數(shù)據(jù)元素之間的邏輯關系是由（）表示的。A線性結構B非線性結構C存儲位置D指針【解答】C，D【分析】順序存儲結構就是用一維數(shù)組存儲數(shù)據(jù)結構中的數(shù)

4、據(jù)元素，其邏輯關系由存儲位置（即元素在數(shù)組中的下標）表示；鏈接存儲結構中一個數(shù)據(jù)元素對應鏈表中的一個結點，元素之間的邏輯關系由結點中的指針表示。⑸基于某種邏輯結構之上的基本操作，其實現(xiàn)是唯一的。【解答】錯?；静僮鞯膶崿F(xiàn)是基于某種存儲結構設計的，因而不是唯一的。4.分析以下各程序段，并用大O記號表示其執(zhí)行時間?！窘獯稹竣呕菊Z句是k=k10i，共執(zhí)行了n2次，所以T(n)=O(n)。⑵基本語句是k=k10i，共執(zhí)行了n次，所以T(n)=

5、O(n)。⑶分析條件語句，每循環(huán)一次，ij整體加1，共循環(huán)n次，所以T(n)=O(n)。⑷設循環(huán)體共執(zhí)行T(n)次，每循環(huán)一次，循環(huán)變量y加1，最終T(n)=y，即：(T(n)1)2≤n，所以T(n)=O(n12)。⑸x是基本語句，所以5設有數(shù)據(jù)結構（D，R），其中D=123456，R=(12)(23)(24)(34)(35)(36)(45)(46)。試畫出其邏輯結構圖并指出屬于何種結構?！窘獯稹科溥壿嫿Y構圖如圖13所示，它是一種圖結構