習題1

1-1什么是數據、數據元素、數據項？三者之間是怎樣的關系？

1-2什么是數據結構？數據結構的概念包括哪三部分？

1-3數據結構與數據類型的概念有什么區別？為什么要將數據結構設計成抽象數據類型？

1-4數據的邏輯結構主要有哪三種？各有何特點？三者之間存在怎樣的聯系？

1-5數據的存儲結構有哪兩種？各有何特點？

1-6什么是算法？怎樣描述算法？怎樣衡量算法的性能？

1-7下列函數的功能是什么？

            void binary（int n）
            {
                whiIe（n>0）
                {   cout<<n<<",";
                  n/=2;
                }
            }

1-8確定下列算法中語句的執行次數，并給出算法的時間復雜度。

            int n=10, count=0;
            for（int i=1; i<=n; i++）
                for（int j=1; j<=i; j++）
                  for（int k=1; k<=j; k++）
                      count++;

實驗1 算法設計與分析

1.實驗目的

了解數據結構課程的目的、性質和主要內容，理解數據結構和算法的基本概念，熟悉算法的描述方法、算法時間復雜度和空間復雜度的分析和計算方法。

要求熟練使用Visual C++ 6.0集成開發環境進行C++程序的編輯、編譯和運行，程序必須運行通過并獲得正確結果，詳見第11章。

2.實驗內容

（1）實現以下對數組的操作，并給出算法的時間復雜度和空間復雜度。

            T max（T tabIe[],int n）                        //返回數組中的最大值
            T min（T tabIe[],int n）                        //返回數組中的最小值
            booI repIace（T tabIe[],int n,int x,int y）     //將n個元素的數組中值為x的元素替換為y值
            booI repIaceAII（T tabIe[],int n,int x,int y）  //將數組中所有值為x的元素替換為y值
            booI isSorted（T tabIe[],int n）                //判斷數組元素是否已按升序排序
            void reverse（T tabIe[],int n）                 //將數組元素a0,a1,…,an-1逆置為an-1,…,a1,a0

（2）用C++的類實現復數抽象數據類型。

（3）實現十進制、二進制、八進制和十六進制的相互轉換。

（4）螺旋方陣。

螺旋方陣將從1開始的自然數由方陣的最外圈向內螺旋方式地順序排列。例如，4階的螺旋方陣排列形式如下：

（5）楊輝三角。

中國南宋數學家楊輝在其《詳解九章算法》（1261年）中給出以下三角形（后世稱為楊輝三角），表中任何一個數字等于它肩膀上的兩個數字之和。n=5的楊輝三角如下：

楊輝三角的重要意義在于，其各行是二項式（a+b）n（n=0，1，2，…）展開式的系數表。n=2和n=3的展開式如下：

（a+b）2=a2+2ab+b 2（a+b）3=a3+3a2b+3ab2+b 3

要求分別采用一維數組、二維數組輸出楊輝三角。

（6）下標和相等的數字方陣。

（7）輸出n個元素的全排列。

如n=3時，數據序列{1, 2, 3}的全排列為：123，132，213，231，312，321。

（8）設計一個矩陣類，構造n階矩陣，實現矩陣加、乘、轉置等運算，并求各算法的時間復雜度。

（9）實現直接選擇排序。

（10）幻方。

n階幻方（magic square）是指將自然數1～n2排列成n×n階方陣，其各行、各列及各對角線上的數字之和相等，和數S=n（n2+1）/2。洛書（傳說大禹治水時洛水神龜所獻）上的3階幻方和楊輝的4階幻方如圖1.11所示，3階幻方的和數為15，4階幻方的和數為34。

幻方有許多構造方法。楊輝在《續古算法摘奇》（1275年）中給出解法，“九子斜排，上下對易，左右相更，四維挺出”，如圖1.12所示。

連續擺數法（也稱暹羅法）適用于構造奇數階幻方，構造過程如圖1.13所示。

連續擺數法構造規律說明如下：

① 約定初始位置為第1行中間，放置1。

② 向當前位置的右上方順序放置下一個數。將幻方陣沿行、列方向看成環形。

③ 若當前放置數為n的倍數，即一條對角線已滿，則下一個數的位置是本列的下一行。

④ 輸出幻方陣。

要求采用連續擺數法構造并輸出指定奇數階的幻方陣。