數(shù)據(jù)結(jié)構(gòu)習(xí)題與答案

1、第1章緒論課后習(xí)題講解課后習(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)，都要存儲兩

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

3、法的時間復(fù)雜度為一個常數(shù)，則表示成數(shù)量級的形式為（），若為nlog25n，則表示成數(shù)量級的形式為（）?！窘獯稹喀?1)，Ο(nlog2n)【分析】用大O記號表示算法的時間復(fù)雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。2.選擇題⑴順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的，鏈接存儲結(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ù)

4、據(jù)元素，其邏輯關(guān)系由存儲位置（即元素在數(shù)組中的下標）表示；鏈接存儲結(jié)構(gòu)中一個數(shù)據(jù)元素對應(yīng)鏈表中的一個結(jié)點，元素之間的邏輯關(guān)系由結(jié)點中的指針表示。⑸基于某種邏輯結(jié)構(gòu)之上的基本操作，其實現(xiàn)是唯一的。【解答】錯?；静僮鞯膶崿F(xiàn)是基于某種存儲結(jié)構(gòu)設(shè)計的，因而不是唯一的。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)。⑷設(shè)循環(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è)有數(shù)據(jù)結(jié)構(gòu)（D，R），其中D=123456，R=(12)(23)(24)(34)(35)(36)(45)(46)。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。【解答】其邏輯結(jié)構(gòu)圖如圖13所示，它是一種圖結(jié)構(gòu)