思考與練習(xí)

一、單項(xiàng)選擇題

1. 數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值計(jì)算問題中的數(shù)據(jù)對(duì)象以及它們之間的（　）和操作算法的學(xué)科。

A. 結(jié)構(gòu)

B. 關(guān)系

C. 運(yùn)算

D. 算法

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

A. 存儲(chǔ)

B. 物理

C. 邏輯

D. 物理和存儲(chǔ)

3. 以下數(shù)據(jù)結(jié)構(gòu)中，（　）是非線性數(shù)據(jù)結(jié)構(gòu)。

A. 集合

B. 線性表

C. 數(shù)組

D. 樹

4. 計(jì)算機(jī)算法是指（　）。

A. 計(jì)算方法

B. 排序方法

C. 解決問題的有限運(yùn)算序列

D. 調(diào)度方法

5. 算法分析的目的是（　）。

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

B. 研究算法中的輸入和輸出的關(guān)系

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

D. 分析算法的易懂性和文檔性

6. 某個(gè)算法的時(shí)間復(fù)雜度為O（n²），表明該算法的（　）。

A. 問題規(guī)模是n²

B. 問題規(guī)模與n²成正比

C. 執(zhí)行時(shí)間是n²

D. 執(zhí)行時(shí)間與n²成正比

二、填空題

1. 根據(jù)數(shù)據(jù)元素間存在的邏輯關(guān)系不同，數(shù)據(jù)的邏輯結(jié)構(gòu)分為__________、__________、__________和__________；在計(jì)算機(jī)內(nèi)采用不同方式表示這些邏輯關(guān)系，因而存儲(chǔ)結(jié)構(gòu)有__________和__________兩種。

2. 算法的5個(gè)重要特性是__________、__________、__________、輸入、輸出。

3. 算法健壯性是指____________________。

4. 已知如下程序段

其中，語句1的執(zhí)行次數(shù)為__________；語句2的執(zhí)行次數(shù)為__________。

三、簡答

1. 簡述數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型的區(qū)別與聯(lián)系。

2. 簡述程序與算法的區(qū)別與聯(lián)系。

3. 算法具有什么特性？評(píng)價(jià)算法好壞的指標(biāo)有哪些？

4. 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)分別有哪些種類？

5. 何謂抽象數(shù)據(jù)類型？請(qǐng)你談?wù)剬?duì)它的理解。

6. 分析以下各程序段的時(shí)間復(fù)雜度。

（1）i=1；s=0；

while（i＜n）

{s=s+10*i；

i++；

}

（2）i=1；j=0；

while（i+j＜n）

if（i＞j）j++；

else i++

（3）y=1；

while（y*y＜=n） y=y+1；

（4）i=n；

while（i＞0）i=i/2；

（5）for（i=1；i＜=n；i++）

for（j=1；j＜=n；j++）

for（k=1；k＜=n；k++）

s++；

（6）for（i=1；i＜=n；i++）

for（j=1；j＜=i；j++）

s++；

（7）設(shè)n是偶數(shù)，運(yùn)行下面的程序段后，計(jì)算語句m=m+1的次數(shù)，并給出該程序段的時(shí)間復(fù)雜度。

7. 對(duì)下列用二元組表示的數(shù)據(jù)結(jié)構(gòu)，試分別畫出對(duì)應(yīng)的邏輯結(jié)構(gòu)圖，并指出屬于何種結(jié)構(gòu)。

（1）A=（D，R），其中D={x，y，z，p}，R={}；

（2）B=（D，R），其中D={a，b，c，d，e}，R={（a，b），（b，e），（e，d），（d，c）}；

（3）G=（D，R），其中D={a，b，c，d，e}，R={（a，d），（c，e），（b，e），（a，b），（b，c），（d，e）}；

（4）T=（D，R），其中D={1，2，3，4，5，6}，R={（6，5），（6，2），（2，3），（2，4），（2，1）}；