第1章 緒論

一、基礎知識題

1。1 簡述下列術語：資料、資料元素、資料物件、資料結構、儲存結構、資料型別和抽象資料型別。

資料

（data）是對客觀事物的符號表示。在計算機科學中是指所有能輸入到計算機中並被計算機程式處理的符號的總稱。

資料元素

（data element）是資料的基本單位，在計算機程式中通常作為一個整體進行考慮和處理。

資料物件

（data object）是性質相同的資料元素的集合，是資料的一個子集。

資料結構

（data structure）是相互之間存在一種或多種特定關係的資料元素的集合。

儲存結構

（

物理結構

）是資料結構在計算機中的表示（又稱映像）。

資料型別

（data type）是一個值的集合和定義在這個值集上的一組操作的總稱。

抽象資料型別

（Abstract Data Type）是指一個數學模型以及定義在該模型上的一組操作。

1。2 試描述資料結構和抽象資料型別的概念與程式設計語言中資料型別概念的區別。

簡單地說，資料結構定義了一組按某些關係結合在一起的陣列元素。資料型別不僅定義了一組帶結構的資料元素，而且還在其上定義了一組操作。

1。3 設有資料結構（D，R），其中：D={d1，d2，d3，d4}，R={r}，r={（d1，d2），（d2，d3），（d3，d4）}。試按圖論中圖的畫法慣例畫出其邏輯結構圖。

1。4 試仿照三元組的抽象資料型別分別寫出抽象資料型別複數和有理數的定義（有理數是其分子、分母均為自然數且分母不為零的分數）。

複數定義：

ADT

Complex

//複數定義 a±bi

{

資料物件：

D

=

{

a

，

b

|

a

，

b為實數

}

資料關係：

R

=

{

<

a

，

b

>

}

基本操作：

InitComplex

（

&

C

，

re

，

im

）

操作結果：構造一個複數

C

，其實部和虛部分別為

re和im

DestroyCmoplex

（

&

C

）

操作結果：銷燬複數

C

Get

（

C

，

k

，

&

e

）

初始條件：複數

C已存在

操作結果：用

e返回複數C的第k元的值

Put

（

&

C

，

k

，

e

）

初始條件：複數

C已存在

操作結果：改變複數

C的第k元的值為e

IsAscending

（

C

）

初始條件：複數

C已存在

操作結果：如果複數

C的兩個元素按升序排列

，則返回

1

，否則返回

0

IsDescending

（

C

）

初始條件：複數

C已存在

操作結果：如果複數

C的兩個元素按降序排列

，則返回

1

，否則返回

0

Max

（

C

，

&

e

）

初始條件：複數

C已存在

操作結果：用

e返回複數C的兩個元素中值較大的一個

Min

（

C

，

&

e

）

初始條件：複數

C已存在

操作結果：用

e返回複數C的兩個元素中值較小的一個

}

ADT

Complex

有理數定義：

ADT

RationalNumber

//有理數定義

{

資料物件：

D

=

{

s

，

m

|

s

，

m為自然數

，且

m不為0

}

資料關係：

R

=

{

<

s

，

m

>

}

基本操作：

InitRationalNumber

（

&

R

，

s

，

m

）

操作結果：構造一個有理數

R

，其分子和分母分別為

s和m

DestroyRationalNumber

（

&

R

）

操作結果：銷燬有理數

R

Get

（

R

，

k

，

&

e

）

初始條件：有理數

R已存在

操作結果：用

e返回有理數R的第k元的值

Put

（

&

R

，

k

，

e

）

初始條件：有理數

R已存在

操作結果：改變有理數

R的第k元的值為e

IsAscending

（

R

）

初始條件：有理數

R已存在

操作結果：若有理數

R的兩個元素按升序排列

，則返回

1

，否則返回

0

IsDescending

（

R

）

初始條件：有理數

R已存在

操作結果：若有理數

R的兩個元素按降序排列

，則返回

1

，否則返回

0

Max

（

R

，

&

e

）

初始條件：有理數

R已存在

操作結果：用

e返回有理數R的兩個元素中值較大的一個

Min

（

R

，

&

e

）

初始條件：有理數

R已存在

操作結果：用

e返回有理數R的兩個元素中值較小的一個

}

ADT

RationalNumber

1。5 試畫出與下列程式段等價的框圖。

(1)

product

=

1

；

i

=

1

；

while

（

i

<=

n

）

{

product

*=

i

；

i

++

；

}

(2)

i

=

0

；

do

{

i

++

；

}

while

（（

i

！=

n

）

&&

（

a

［

i

］

！=

x

））；

(3)

switch

{

case

x

<

y

：

z

=

y

-

x

；

break

；

case

x

==

y

：

z

=

abs

（

x

*

y

）；

break

；

default

：

z

=

（

x

-

y

）

/

abs

（

x

）

*

abs

（

y

）；

}

1。6 在程式設計中，常用下列三種不同的出錯處理方式：

（1）用exit語句終止執行並報告錯誤；

（2）以函式的返回值區別正確返回或錯誤返回；

（3）設定一個整型變數的函式引數以區別正確返回或某種錯誤返回。

試討論這三種方法各自的優缺點。

（1）exit常用於嚴重錯誤處理，它可以強行中斷程式的執行，返回作業系統。優點是可以在程式的任何地方關閉程式，缺點是隱藏了故障資訊。

（2）以函式的返回值判斷正確與否常用於子程式的測試，便於實現程式的區域性控制。

（3）用整型變數進行錯誤處理的優點是可以給出錯誤型別，便於迅速定位錯誤。

1。7 在程式設計中，可採用下列三種方法實現輸出和輸入：

（1）透過scanf和printf語句；

（2）透過函式的引數顯式傳遞；

（3）透過全域性變數隱式傳遞。

試討論這三種方法的優缺點。

（1）用scanf和printf直接進行輸入輸出的好處是形象、直觀，但缺點是需要對其進行格式控制，較為煩瑣，如果出現錯誤，則會引起整個系統的崩潰。

（2）透過函式的引數傳遞進行輸入輸出，便於實現資訊的隱蔽，減少出錯的可能。

（3）透過全域性變數的隱式傳遞進行輸入輸出最為方便，只需修改變數的值即可，但過多的全域性變數使程式的維護較為困難。

1。8 設n為正整數。試確定下列各程式段中前置以記號@的語句的頻度：

（1）

i

=

1

；

k

=

0

；

while

（

i

<=

n

-

1

）

{

@

k

+=

10

*

i

；

i

++

；

}

n-1

（2）

i

=

1

；

k

=

0

；

do

{

@

k

+=

10

*

i

；

i

++

；

}

while

（

i

<=

n

-

1

）；

n=1時，至少執行一次，即頻度為1。n>1時，執行頻度為 n-1。

（3）

i

=

1

；

k

=

0

；

while

（

i

<=

n

-

1

）

{

i

++

；

@

k

+=

10

*

i

；

}

n-1

（4）

k

=

0

；

for

（

i

=

1

；

i

<=

n

；

i

++

）

{

for

（

j

=

i

；

j

<=

n

；

j

++

）

@

k

++

；

}

（5）

for

（

i

=

1

；

i

<=

n

；

i

++

）

for

（

j

=

1

；

j

<=

i

；

j

++

）

for

（

k

=

1

；

k

<=

j

；

k

++

）

@

x

+=

1

；

（6）

i

=

1

；

j

=

0

；

while

（

i

+

j

<=

n

）

{

@

if

（

i

>

j

）

j

++

；

else

i

++

；

}

n

（7）

x

=

n

；

y

=

0

；

//n是不小於1的常數

while

（

x

>=

（

y

+

1

）

*

（

y

+

1

））

@

y

++

；

（8）

x

=

91

；

y

=

100

；

while

（

y

>

0

）

{

@

if

（

x

>

100

）

{

x

-=

10

；

y

——

；

}

else

x

++

；

}

1100

1。9 假設n為2的乘冪，並且n>2，試求下列演算法的時間複雜度及變數count的值（以n的函式形式表示）。

int

Time

（

int

n

）

{

count

=

0

；

x

=

2

；

while

（

x

<

n

/

2

）

{

x

*=

2

；

count

++

；

}

return

（

count

）

}

//

Time

時間複雜度：O（log2n） count = log2n - 2

1。10 按增長率由小至大的順序排列下列各函式：

2100，（3/2）n，（2/3）n，（4/3）n，nn，n3/2，n2/3，√n，n！，n，log2n，n/log2n，log22n，log2（log2n），nlog2n，nlog2n

各函式的排列次序如下：

注：習題集中給出的第12個函式為n/logn2，這應當是筆誤，實際為n/log2n

1。11 已知有實現同一功能的兩個演算法，其時間複雜度分別為O（2n）和O（n10），假設現實計算機可連續運算的時間為107秒（100多天），又每秒可執行基本操作（根據這些操作來估算演算法時間複雜度）105次。試問在此條件下，這兩個演算法可解問題的規模（即n值的範圍）各為多少？哪個演算法更適宜？請說明理由。

2n=1012，求得n=40

n10=1012，求得n=16

故第一種演算法較適宜。因為在同樣的算力下，第一種演算法可解的n值較大。

由此可見，雖然一般情況下多項式階的演算法優於指數階的演算法，但高次多項式的演算法在n的很大範圍內不如某些指數階的演算法。

1。12 設有以下三個函式：

f（n）=21n4+n2+1000，g（n）=15n4+500n2，h（n）=5000n3。5+nlogn

請判斷以下斷言正確與否：

（1）f（n）是O（g（n））

（2）h（n）是O（f（n））

（3）g（n）是O（h（n））

（4）h（n）是O（n3。5）

（5）h（n）是O（nlogn）

（1） 對 （2） 錯 （3） 錯 （4） 對 （5） 錯

1。13 試設定若干n值，比較兩函式n2和50nlog2n的增長趨勢，並確定n在什麼範圍內時n2的值大於50nlog2n。

大約在n>450時 ，函式n2的值才大於函式50nlog2n的值。

1。14 判斷下列各對函式f（n）和g（n），當n→∞時，哪個函式增長更快？

（1） g（n）快 （2） g（n）快 （3） f（n）快 （4） f（n）快

1。15 試用數學歸納法證明：

二、演算法設計題

1。16 試寫一演算法，自大到小依次輸出順序讀入的三個整數X，Y和Z的值。

1。17 已知k階斐波那契序列的定義為

f0=0， f1=0， …， fk-2=0， fk-1=1；

fn=fn-1+fn-2+…+fn-k， n=k，k+1，…

試編寫求k階斐波那契序列的第m項值的函式演算法，k和m均以值呼叫的形式在函式引數表中出現。

1。18 假設有A、B、C、D、E五個高等院校進行田徑對抗賽，各院校的單項成績均已存入計算機，並構成一張表，表中每一行的形式為：

|專案名稱|性別|校名|成績|得分|

編寫演算法，處理上述表格，以統計各院校的男、女總分和團體總分，並輸出。

typedef

enum

{

A

，

B

，

C

，

D

，

E

}

SchoolName

；

typedef

enum

{

FEMALE

，

MALE

}

SexType

；

typedef

enum

{

X

，

Y

，

Z

}

Event

；

typedef

struct

{

Event

e

；

//專案名稱

SexType

sex

；

//性別

SchoolName

school

；

//校名

int

score

；

//得分

}

Component

；

typedef

struct

{

int

malesum

；

//男團總分

int

femalesum

；

//女團總分

int

totalsum

；

//團體總分

}

Sum

；

Component

report

［

n

］；

//n條記錄

Sum

result

［

5

］；

//演算法過程體中主要結構

for

（

i

=

0

；

i

<

n

；

i

++

）

{

//對result［report［i］。school］進行處理

}

for

（

s

=

A

；

s

<=

E

；

s

++

）

{

//printf（。。。）；

}

1。19 試編寫演算法，計算i！

2i的值並存入陣列a［0。。arrsize-1］的第i-1個分量中（i=1，2，…，n）。假設計算機中允許的整數最大值為maxint，則當n>arrsize或對某個k（1≤k≤n）使k！

2k>maxint時，應按出錯處理。注意選擇你認為較好的出錯處理方法。

1。20 試編寫演算法求一元多項式：

的值Pn（x），並確定演算法中每一語句的執行次數和整個演算法的時間複雜度。注意選擇你認為較好的輸入和輸出方法。本題的輸入為ai（i=0，1，…，n），x0和n，輸出為Pn（x0）。