F T

第六章

作業(yè)題參考答案

3．畫出下列偽碼程序的程序流程圖和盒圖：

START

IF p THEN

WHILE q DO

f

END DO

ELSE

BLOCK

g

n

END BLOCK

END IF

STOP

答：（1）流程圖如圖

6-1

所示：

開始

p

g q循環(huán)WHILE

p

n f

q循環(huán)

停止

圖

6-1

從偽碼變成的程序流程圖

（2）該程序的盒圖如圖

6-2

所示：

P

q

g

f

n

圖

6-2

從偽碼變成的程序盒圖

4．下圖給出的程序流程圖代表一個(gè)非結(jié)構(gòu)化的程序，請(qǐng)問：

（1）為什么說它是非結(jié)構(gòu)化的？

（2）設(shè)計(jì)一個(gè)等價(jià)的結(jié)構(gòu)化程序。

（3）在（2）題的設(shè)計(jì)中你使用附加的標(biāo)志變量

flag

嗎？若沒用，請(qǐng)?jiān)僭O(shè)計(jì)一個(gè)使用

flag

的程序；若用了，再設(shè)計(jì)一個(gè)不用

flag

的程序。

（

答：

1）通常所說的結(jié)構(gòu)化程序，是按照狹義的結(jié)構(gòu)程序的定義衡量，符合定義規(guī)定的程序。

圖示的程序的循環(huán)控制結(jié)構(gòu)有兩個(gè)出口

，顯然不符合狹義的結(jié)構(gòu)程序的定義，因此是非結(jié)

構(gòu)化的程序。

（2）使用附加的標(biāo)志變量

flag，至少有兩種方法可以把該程序改造為等價(jià)的結(jié)構(gòu)化程序，

圖

6-3

描繪了等價(jià)的結(jié)構(gòu)化程序的盒圖。

F

flag=TRUE

p

AND

flag

g

q

flag=FALSE

T

flag=TRUE

p

F

T

g

flag=FALSE

(NOT

q)OR(NOT

flag)

（a）解法

1 （b）解法

2

圖

6-3

與該圖等價(jià)的結(jié)構(gòu)化程序（用

flag）

（3）不使用

flag

把該程序改造為等價(jià)的結(jié)構(gòu)化程序的方法如圖

6-4

所示。

p

F T

g

(NOT

q)OR(NOT

flag)

圖

6-4

與該圖等價(jià)的結(jié)構(gòu)化程序（不用

flag）

8．畫出下列偽碼程序的流圖，計(jì)算它的環(huán)形復(fù)雜度。你覺得這個(gè)程序的邏輯有什么問題嗎？

C EXAMPLE

LOOP:DO

WHILE X>0

A=B+1

IF

A>10

THEN

X=A

ELSE

Y=Z

END

IF

IF

Y<5

THEN

PRINT

X,Y

ELSE

IF

Y=2

THEN

GOTO

LOOP

ELSE

C=3

END

IF

END

IF

G=H+R

END

DO

IF

F>0

THEN

PRINT

G

ELSE

PRINT

K

END

IF

STOP

答：（1）該偽碼的流程圖如圖

6-8

所示：

開始

N

Z>0?

Y

A=B+1

N

Y

A>10?

Y=Z X=A

N

Y

Y<5?

Y

Y=2?

N

C=3

Print

X,Y

N

G<=H+R

F>0？

Y

Print

K

Print

G

結(jié)束

圖

6-8

程序流程圖

根據(jù)該程序流程圖，可得該程序流圖如圖

6-9

所示：

1

2

3

4 5

6

8

7

9

10

11

12 13

14

圖

6-9

程序流圖

環(huán)形復(fù)雜度

V(G)=流圖中的區(qū)域數(shù)

=流圖中判定結(jié)點(diǎn)數(shù)目+1=6+1=7 （判定結(jié)點(diǎn)為：1、3、6、8、10、11）

（2）該算法問題在于控制最外層循環(huán)的變量

Z

不僅沒有經(jīng)過初始化，并且在該循環(huán)內(nèi)部沒

有任何有可能該變

Z

的語句。因此，該段代碼中的WHILE

循環(huán)部分代碼要么不會(huì)執(zhí)行，要

么可能出現(xiàn)死循環(huán)。

【補(bǔ)充題】用

Jackson

圖描述下述一列火車的構(gòu)成：

一列火車最多有兩個(gè)車頭。一列火車最多有兩個(gè)車頭。只有一個(gè)火車頭時(shí)則位于列

車最前面，若還有第二個(gè)車頭時(shí)，則第二個(gè)車頭位于列車最后面。火車頭既可能是內(nèi)燃機(jī)

車也可能是