習 題 1

1-1 選擇題

（1）順序存儲結構中數據元素之間的邏輯關系是由（ ）表示的，鏈接存儲結構中的數據元素之間的邏輯關系是由（ ）表示的。

A.線性結構

B.非線性結構

C.存儲位置

D.指針

（2）假設有如下遺產繼承規則：丈夫和妻子可以相互繼承遺產；子女可以繼承父親或母親的遺產；子女間不能相互繼承。則表示該遺產繼承關系的數據結構應該是（ ）。

A.樹

B.圖

C.線性表

D.集合

（3）計算機所處理的數據一般具有某種內在聯系，這是指（ ）。

A.數據和數據之間存在某種關系

B.元素和元素之間存在某種關系

C.元素內部具有某種結構

D.數據項和數據項之間存在某種關系

（4）對于數據結構的描述，下列說法中不正確的是（ ）。

A.相同的邏輯結構對應的存儲結構也必相同

B.數據結構由邏輯結構、存儲結構和基本操作三方面組成

C.對數據結構基本操作的實現與存儲結構有關

D.數據的存儲結構是數據的邏輯結構的機內實現

（5）算法指的是（ ）。

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

B.計算機程序

C.解決問題的計算方法

D.數據處理

（6）下面（ ）不是算法所必須具備的特性。

A.有窮性

B.確切性

C.高效性

D.可行性

（7）算法分析的目的是（ ），算法分析的兩個主要方面是（ ）。

A.找出數據結構的合理性

B.研究算法中輸入和輸出的關系

C.分析算法的效率以求改進

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

E.空間性能和時間性能

F.正確性和簡明性

G.可讀性和文檔性

H.數據復雜性和程序復雜性

（8）假設時間復雜度為O（n2）的算法在有200個元素的數組上運行需要3.1毫秒，則在有400個元素的數組上運行需要（ ）毫秒。

A.3.1

B.6.2

C.12.4

D.9.61

（9）下列程序段加下劃線的語句執行（ ）次。

            for（m=0，i=1；i＜=n；i++）
              for（j=1；j＜=2*i；j++）

                m=m+1；

A.n2

B.3n

C.n（n+1）

D.n3

1-2 分析以下各程序段，并用大O記號表示其執行時間。

      （1）i=1；k=0；
            while（i＜=n）
            {
              k=k+10*i；
              i++；
            }

                                        （2）i=1；k=0；
                                            do
                                            {
                                              k=k+10*i；
                                              i++；
                                            }while（i＜=n）；

      （3）i=1；j=0；
            while（i+j＜=n）
              if（i＞j）j++；
              elsei++；

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

      （5）for（i=1；i＜=n；i++）
              for（j=1；j＜=i；j++）
                for（k=1；k＜=j；k++）
                  x++；

                                        （6）for（i=1；i＜=n；i++）
                                              if（2*i＜=n）
                                                for（j=2*i；j＜=n；j++）
                                                  y=y+i*j；

1-3 解答下列問題

（1）假設有數據結構（D，R），其中D={1，2，3，4，5，6}，R={（1，2），（1，4），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（5，6）}。試畫出其邏輯結構圖并指出屬于何種結構。

（2）為整數定義一個抽象數據類型，包含整數的常見運算，每個運算對應一個基本操作，每個基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件。

（3）求多項式A（x）的算法可根據下列兩個公式之一來設計：

① A（x）=anxn+an-1xn-1+…+a1x+a0

② A（x）=（…（anx+an-1）x+…+a1）x+a0

根據算法的時間復雜度分析比較這兩種算法的優劣。

1-4 算法設計（要求：用偽代碼和類C語言描述兩種方法描述算法，并分析時間復雜度）

（1）找出整型數組A[n]中的最大值和次最大值。

（2）對一個整型數組A[n]設計一個排序算法。

（3）判斷給定字符串是否是回文。所謂回文是正讀和反讀均相同的字符串，例如＂abcba＂或＂abba＂是回文，而＂abcda＂不是回文。

（4）已知數組A[n]中的元素為整型，設計算法將其調整為左右兩部分，左邊所有元素為奇數，右邊所有元素為偶數，并要求算法的時間復雜度為O（n）。

（5）荷蘭國旗問題。要求重新排列一個由字符R，W，B（R代表紅色，W代表白色，B代表蘭色，這都是荷蘭國旗的顏色）構成的數組，使得所有的R都排在最前面，W排在其次，B排在最后。為荷蘭國旗問題設計一個算法，其時間性能是O（n）。