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

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構(gòu)習(xí)題與答案第1章緒論

課后習(xí)題講解

1、填空

⑴()就是數(shù)據(jù)的基本單位,在計(jì)算機(jī)程序中通常作為一個整體舉行考慮與處理。

【解答】數(shù)據(jù)元素

⑵()就是數(shù)據(jù)的最小單位,()就是研究數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。

【解答】數(shù)據(jù)項(xiàng),數(shù)據(jù)元素

【分析】數(shù)據(jù)結(jié)構(gòu)指的就是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。

⑶從規(guī)律關(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)系

⑸算法具有五個特性,分離就是()、()、()、()、()。

【解答】有零個或多個輸入,有一個或多個輸出,有窮性,確定性,可行性

⑹算法的描述辦法通常有()、()、()與()四種,其中,()被稱為算法語言。

【解答】自然語言,程序設(shè)計(jì)語言,流程圖,偽代碼,偽代碼

⑺在普通狀況下,一個算法的時光復(fù)雜度就是()的函數(shù)。

【解答】問題規(guī)模

⑻設(shè)待處理問題的規(guī)模為n,若一個算法的時光復(fù)雜度為一個常數(shù),則表示成數(shù)量級的形式為(),若為

n*log25n,則表示成數(shù)量級的形式為()。

【解答】Ο(1),Ο(nlog2n)

【分析】用大O記號表示算法的時光復(fù)雜度,需要將低次冪去掉,將最高次冪的系數(shù)去掉。

2、挑選題

⑴挨次存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的規(guī)律關(guān)系就是由()表示的,鏈接存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的規(guī)律關(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ī)律關(guān)系由存儲位置(即元素在數(shù)組中的下標(biāo))表示;鏈接存儲結(jié)構(gòu)中一個數(shù)據(jù)元素對應(yīng)鏈表中的一個結(jié)點(diǎn),元素之間的規(guī)律關(guān)系由結(jié)點(diǎn)中的指針表示。

⑵假設(shè)有如下遺產(chǎn)繼承規(guī)章:丈夫與妻子可以互相繼承遺產(chǎn);子女可以繼承父親或母親的遺產(chǎn);子女間不能互相繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)當(dāng)就是()。

A樹

B圖

C線性表

D集合

【解答】B

【分析】將丈夫、妻子與子女分離作為數(shù)據(jù)元素,按照題意畫出規(guī)律結(jié)構(gòu)圖。

⑶算法指的就是()。

A對特定問題求解步驟的一種描述,就是指令的有限序列。

B計(jì)算機(jī)程序

C解決問題的計(jì)算辦法

D數(shù)據(jù)處理

【解答】A

【分析】計(jì)算機(jī)程序就是對算法的詳細(xì)實(shí)現(xiàn);容易地說,算法就是解決問題的辦法;數(shù)據(jù)處理就是通過算法完成的。所以,惟獨(dú)A就是算法的精確?????定義。

⑷下面()不就是算法所必需具備的特性。

A有窮性

B確切性

C高效性

D可行性

【解答】C

【分析】高效性就是好算法應(yīng)具備的特性。

⑸算法分析的目的就是(),算法分析的兩個主要方面就是()。

A找出數(shù)據(jù)結(jié)構(gòu)的合理性

B討論算法中輸入與輸出的關(guān)系

C分析算法的效率以求改進(jìn)

D分析算法的易讀性與文檔性

E空間性能與時光性能

F正確性與簡明性

G可讀性與文檔性H數(shù)據(jù)復(fù)雜性與程序復(fù)雜性

【解答】C,E

3、推斷題

⑴算法的時光復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定。

【解答】錯。時光復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。

⑵每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作:插入、刪除與查找。

【解答】錯。如數(shù)組就沒有插入與刪除操作。此題注重就是每種數(shù)據(jù)結(jié)構(gòu)。

⑶所謂數(shù)據(jù)的規(guī)律結(jié)構(gòu)指的就是數(shù)據(jù)之間的規(guī)律關(guān)系。

【解答】錯。就是數(shù)據(jù)之間的規(guī)律關(guān)系的整體。

⑷規(guī)律結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容與形式無關(guān)。

【解答】對。因此規(guī)律結(jié)構(gòu)就是數(shù)據(jù)組織的主要方面。

⑸基于某種規(guī)律結(jié)構(gòu)之上的基本操作,其實(shí)現(xiàn)就是唯一的。

【解答】錯?；静僮鞯膶?shí)現(xiàn)就是基于某種存儲結(jié)構(gòu)設(shè)計(jì)的,因而不就是唯一的。

4、分析以下各程序段,并用大O記號表示其執(zhí)行時光。

【解答】⑴基本語句就是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)+1)2≤n,所以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)}。試畫出其規(guī)律結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。

【解答】其規(guī)律結(jié)構(gòu)圖如圖1-3所示,它就是一種圖結(jié)構(gòu)。

6、為整數(shù)定義一個抽象數(shù)據(jù)類型,包含整數(shù)的常見運(yùn)算,每個運(yùn)算對應(yīng)一個基本操作,每個基本操作的接口需定義前置條件、輸入、功能、輸出與后置條件。

【解答】整數(shù)的抽象數(shù)據(jù)類型定義如下:

ADTinteger

Data

整數(shù)a:可以就是正整數(shù)(1,2,3,…)、負(fù)整數(shù)(-1,-2,-3,…)與零Operation

Constructor

前置條件:整數(shù)a不存在

輸入:一個整數(shù)b

功能:構(gòu)造一個與輸入值相同的整數(shù)

輸出:無

后置條件:整數(shù)a具有輸入的值

Set

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:修改整數(shù)a的值,使之與輸入的整數(shù)值相同

輸出:無

后置條件:整數(shù)a的值發(fā)生轉(zhuǎn)變

Add

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:將整數(shù)a與輸入的整數(shù)b相加

輸出:相加后的結(jié)果

后置條件:整數(shù)a的值發(fā)生轉(zhuǎn)變

Sub

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:將整數(shù)a與輸入的整數(shù)b相減

輸出:相減的結(jié)果

后置條件:整數(shù)a的值發(fā)生轉(zhuǎn)變

Multi

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:將整數(shù)a與輸入的整數(shù)b相乘

輸出:相乘的結(jié)果

后置條件:整數(shù)a的值發(fā)生轉(zhuǎn)變

Div

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:將整數(shù)a與輸入的整數(shù)b相除

輸出:若整數(shù)b為零,則拋出除零異樣,否則輸出相除的結(jié)果

后置條件:整數(shù)a