數(shù)據(jù)結(jié)構(gòu)(java)復(fù)習(xí)題及答案 1緒論

一、單項選擇題

（B）1.計算機(jī)算法必須具備輸入、輸出和等5個特性。

A）可行性、可移植性和可擴(kuò)充性B）可行性、確定性和有窮性

0確定性、有窮性和穩(wěn)定性D）易讀性、穩(wěn)定性和安全性

（C）2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的結(jié)構(gòu)；

A）存儲B）物理0邏輯D）物理和存儲

（C）3,算法分析的目的是：

A）找出數(shù)據(jù)結(jié)構(gòu)的合理性B）研究算法中的輸入和輸出的關(guān)系

0分析算法的效率以求改進(jìn)D）分析算法的易懂性和文檔性

（A）4.算法分析的兩個主要方面是：

A）空間復(fù)雜性和時間復(fù)雜性B）正確性和簡明性

0可讀性和文檔性D）數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

（C）5,計算機(jī)算法指的是：

A）計算方法B）排序方法C）解決問題的有限運(yùn)算序列D）調(diào)度方法

6,數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（A）和（B）以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定

義相應(yīng)的（C）,設(shè)計出相應(yīng)的（D）,從而確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)是

（E）結(jié)構(gòu)類型。

供選擇的答案

A.B:1.理想結(jié)構(gòu)2.抽象結(jié)構(gòu)3.物理結(jié)構(gòu)4邏輯結(jié)構(gòu)

C.D.E:1.運(yùn)算2.算法3.結(jié)構(gòu)4,規(guī)則5.現(xiàn)在的6.原來的解答：34126

7.（A）是描述客觀事物的數(shù)、字符以及所有能輸入到計算機(jī)中被計算機(jī)程序加工處

理的符號的結(jié)合。

CB）是數(shù)據(jù)的基本單位，即數(shù)據(jù)結(jié)合中的個體。有時一個（B）由若干個（C）組

成，在這種情況下，稱（B）為記錄。（C）是數(shù)據(jù)的最小單位。

（D）是具有相同特性的數(shù)據(jù)元素的集合。

（E）是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的結(jié)合。

被計算機(jī)加工的數(shù)據(jù)元素不是孤立無關(guān)的，它們彼此之間普通存在著某種聯(lián)系，通常將

數(shù)據(jù)元素的這種聯(lián)系關(guān)系稱為（G）。

算法的計算量和問題規(guī)模的聯(lián)系用（H）表示。

供選擇的答案：

A-F:1.數(shù)據(jù)元素2.符號3.記錄4.文件5.數(shù)據(jù)6.數(shù)據(jù)項7.數(shù)據(jù)對象

8.關(guān)鍵字9.數(shù)據(jù)結(jié)構(gòu)

G:1.規(guī)則2.集合3.結(jié)構(gòu)4.運(yùn)算

H:1.現(xiàn)實性2.難度3.復(fù)雜性4.效率

解答：5167933

二、判斷題

1,數(shù)據(jù)元素是數(shù)據(jù)的最小單位。

解答：錯，因為數(shù)據(jù)元素是數(shù)據(jù)的基本單位，通常它是由若干個數(shù)據(jù)項組成，數(shù)據(jù)項

才是數(shù)據(jù)的最小單位。

2,數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的結(jié)合。

解答：正確

3,數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項在計算機(jī)中的映像（或者表示）分別稱為存儲

結(jié)構(gòu)、結(jié)點、數(shù)據(jù)域。

解答：正確

4,數(shù)據(jù)項是數(shù)據(jù)的基本單位。

解答：錯，因為數(shù)據(jù)元素才是數(shù)據(jù)的基本單位

5,數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)之間的邏輯關(guān)系，是用戶按使用需要而建立的。

解答：正確

6,數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機(jī)內(nèi)實際的存儲形式。

解答：正確

三、簡答題

1、簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、線

性結(jié)構(gòu)、非線性結(jié)構(gòu)。

解答：

?數(shù)據(jù)：指能夠被計算機(jī)識別、存儲和加工處理的信息載體。

?數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂

點、記錄。數(shù)據(jù)元素有時可以由若干數(shù)據(jù)項組成。

?數(shù)據(jù)項是不可分割的最小單位。

?數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。普通包括三個方面的內(nèi)

容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。

?邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。

?存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)。

?線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類.它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且惟獨(dú)

一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都有且惟獨(dú)一個直接前趨和一個直接后

繼。線性表就是一個典型的線性結(jié)構(gòu)。棧、隊列、串等都是線性結(jié)構(gòu)。

?非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個結(jié)點可能有多個直接

前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。

2、按增長率由小至大的順序羅列下列各函數(shù)：

2100,(3/2)\(2/3)n,n,nJ5,n!,2n,Ign,mgn,n(3/2)

解答：

常見的時間復(fù)雜度按數(shù)量級遞增羅列，挨次為:常數(shù)階0(1)、對數(shù)階0(logn)、線

性階0(n)、線性對數(shù)階0(nlogn)、平方階0(n“、立方階0(m)、k次”方階0

(m)、指數(shù)階0(2”

先將題中的函數(shù)分成如下幾類：常數(shù)階：2⑼對數(shù)階：Ign

K次方階：n°\n<3/a

指數(shù)階(按指數(shù)由小到大排)：mA(3/2)\2\n!、n”

注意：(2/3)5由于底數(shù)小于1,所以是一個遞減函數(shù)，其數(shù)量級應(yīng)小于常數(shù)階。

根據(jù)以上分析按增長率由小至大的順序可羅列如下:

(2/3)”<2ioo<Ign<no's<n"<i*n<(3/2)“<2n<n!〈n"

n

3、試舉一個數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運(yùn)算三個方面的內(nèi)容。

解答:略

4、常用的存儲表示方法有哪兒種？

解答:順序和鏈?zhǔn)剑÷?00字

5、設(shè)有兩個算法在同一機(jī)器上運(yùn)行，其執(zhí)行時間分別為100/和2”，要使前者快于后

者，n至少要多大？

解答：

6、算法的時間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎？

解答：是

第一章作業(yè)

1.任何計算機(jī)系統(tǒng)的主存可以看做是一個一維數(shù)組，多維數(shù)組實際存儲仍是一組連續(xù)單元。

請從數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的角度分析？

答：通過一個下標(biāo)計算公式將二維數(shù)組的下標(biāo)（i,j）映成一維數(shù)組的下標(biāo)。例圖b,下標(biāo)

=4x（J—1）十I

1234167

1

2

3

4

（a）從用戶的觀點看數(shù)組

列I2367

行1234123412323412341234

（b）從計算機(jī)的角度按列看數(shù)組

行I24

列1234567123445671234567

（c）從計算機(jī)的角度按行看數(shù)組

2.選擇解決某種問題的最佳數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？

1）算法所需要的時間；

%1程序運(yùn)行時所需輸入的數(shù)據(jù)總量；

%1對源程序進(jìn)行編譯所需的時間；

%1計算機(jī)執(zhí)行每條指令所需的時間；

%!程序中的指令重復(fù)執(zhí)行的次數(shù)（數(shù)據(jù)結(jié)構(gòu)中討論算法時的重點）

2）所需的存儲空間量。

3.有一疊撲克脾，在計算機(jī)中存儲這一疊撲克牌的內(nèi)容（信息）

答：用一個結(jié)點表示一張牌，每張撲克牌的內(nèi)容包括牌的正反面（0、1）、花色（梅花1、

方塊2、紅心3、黑桃4）、點數(shù)、名稱、下一張牌

邏輯結(jié)構(gòu)是線性表；存儲結(jié)構(gòu)可以用鏈

圖13撲克牌的存儲

表或者順序表表示

圖L2撲克牌的邏輯結(jié)構(gòu)

4、語句S的執(zhí)行次數(shù)(B)

(1)for(i=1;i<=n-1;i++)

for(j=n;j>=i;j-)

1=1執(zhí)行n次

S：1=2執(zhí)行n-1次

(A)n(n+2)/2(B)(n-l)(n+2)/2息Cj)執(zhí)必/次牌(D)(n-l)(n+2)

⑵1=0；(A)n+(n-1)+2

1=0j0~n執(zhí)行n+l

Do(

1=1,j2旅行n次

J=l；

Do{l=n,n-執(zhí)行1次

j(n+l)n,

S；1

J++;+-

}while(j<=n);

I++；

}while(i<=n);

(A)(n+2)(n+l)/2(B)n(n-l)/2(C)n!(D)成

5、計算下面程序的時間復(fù)雜度

C1)for(i=1;i<=m;i++)(C)

for(j=l;jv=n;j++)

A[i][j]=i*j；

(A)0(012)(B)O(H2)(C)O(m*n)(D)

0(m+n)

(2)1=0;(A)S=1+2+n

3oooooooouX—

s=0;X為執(zhí)行次數(shù)x(x+1)

while(s<=n){

I++；

x2+=0

S+=l;}

-