習題1

1-1 什么是數據、數據元素、原子元素？它們有何區別？

1-2 什么是數據類型、原子數據類型、結構數據類型、抽象數據類型、虛擬數據類型、固有數據類型？它們之間的關系怎樣？

1-3 數據結構與軟件的關系是什么？解決實際問題時，選取（設計）數據結構的總則是什么？

1-4 如何理解數據（或抽象數據）類型及其實例？C++語言的數據類型char與boolean的值域是什么？分別定義了什么操作？

1-5 抽象數據類型（ADT）與面向對象方法有何關系？ADT的說明如何編寫？使用ADT的優點有哪些？

1-6 為什么說數據元素之間的邏輯關系是數據內部組織的主要方面？什么是隨機存取、順序存取、直接存取？

1-7 邏輯結構與存儲結構是什么關系？有何區別？

1-8 運算與運算實現是什么關系？有哪些相同點和不同點？什么是操作？

1-9 試描述數據結構的概念與高級程序設計語言中數據類型概念的區別。C++語言與Visual C++語言的區別。

1-10 舉一個數據結構的例子，敘述其邏輯結構、存儲結構和運算三方面的內容。

1-11 算法與程序有何不同？為何要引出算法的概念？如何評價算法的時間、空間復雜度及算法的好壞？

1-12 分析下列程序段的時間復雜度。

            void  odd（int n）
            {    int i,j,x=0,y=0；
                for（i=1;i<=n;i++）
                    if odd（i）
                  {  for（j=i;j<=n;j++）x++;
                      for（j=1;j<=i;j++）y++;
                  }
            }
            void  recursive（int n）
            {  if（n<=1） return 1; else  return（recursive（n-1）+recursive（n-1））;}

1-13 設n為正整數，試確定下列各程序段中帶下劃線語句的頻度。

（1）int i=1, k=0; while（i<=n-1）{ k=k+10*i; i=i+1; }

（2）int i=1, j=0; while（（i+j）<=n）if（i>j）j++; else i++;

（3）int x=91, y=100;

while（y>0）{ if（x>100）{ x=x-10; y--; } else x++; }

（4）int x=0;

for（int i=1; i<=n; i++）

for（int j=1; j<=i; j++）

for（int k=1; k<=j; k++）x++;

（5）int x=n, y=0; //n>1

while（x>=（y+1）*（y+1））y++;

1-14 考慮下列函數：f1(n)=n2，f2(n)=n2+1000n，f3(n)=n（如果n是奇數）或者f3(n)=n3（如果n是偶數），f4(n)=n（如果n≤100）或者f4(n)=n3（如果n≥100），指出對于不同的i和j（比如i, j=1, 2, 3, 4），是否存在fi(n)=O(fj(n))，fi(n)=Ω(fj(n))，Ω 的定義見習題1-17。

1-15 設有數據的邏輯結構為K=(D, S)，D={d1, d2, …, d9}，S={<d1, d2>,<d1, d8>,<d2, d3>,<d2, d4>,<d2, d5>,<d3, d9>,<d5, d6>,<d8, d9>,<d9, d7>,<d4, d7>,<d4, d6>}。試畫出這個邏輯結構的圖示。并確定對應關系集合S中哪些結點是開始結點，哪些結點是終端結點？

1-16 考慮以下函數：g1(n)=n2（當n為偶數時）或者g1(n)=n3（當n為奇數時），g2(n)=n（當0≤n≤100 時），g2(n)=n3（當n＞100 時），g3(n)=n2.5，指出gi(n)是否為O(gj(n))，以及gj(n)是否為Ω(gi(n))，i, j=1, 2, 3（O的定義見例1-7，Ω的定義見習題1-17）。

1-17 設T1(n)是Ω (f(n))，T2(n)是Ω (g(n))，問以下論斷是否正確：

① T1(n)+T2(n)是Ω{max[f(n)×g(n)]}；

② T1(n)+T2(n)是Ω{max[f(n)×g(n)]}。

（Ω 的概念定義為：若f(n)是Ω[g(n)]，則表示存在著常數n0與c＞0，使得f(n)≥c×g(n)對于一切n≥n0成立。）

1-18 指出以下算法中的錯誤和低效（費時）之處，并將它改寫成為一個既正確又高效的算法。

            int last,i,k;int a[n];      //本算法從a[0]～a[last]中刪除第i個元素起的k個元素
            if（（i<0）||（i>last）||（k<0）||（last>n-1））
            {    cerr<<“error:argument error”<<endl: exit（1）;  }
            else  for（int count=1;count<=k;count++） //刪除一個元素
                    for（int j=last;j>=i+1;j--） {  a[j-1]=a[j];last--;}

1-19 已知k階Fibonacci序列定義為F0=0, F1=0, …, Fk-2=0, Fk-1=1, Fn=Fn-1+Fn-2+…+Fn-k, n=k, k+1, …，試編寫求任意k階Fibonacci序列的算法（要求序列計算時，Fn的值不大于105），并分析算法時間復雜度。

1-20 設計求解下列問題的C++語言算法，并分析其最壞情況時間復雜度及其數量級。①在數組A[1…n]中查找值為k的元素，若找到，則輸出其位置i（1≤i≤n），否則輸出0 作為標志。② 找出數組A[1…n]中元素的最大值和次最大值（本題以數組元素的比較為標準操作）。

1-21 試采取逐步求精的方法用C++語言編寫求最大公因子的算法，并分析算法的時間復雜度。

1-22 試編寫一個求多項式Pn(x)=anxn +an-1xn-1+…+a1x +a0的值Pn(x0)的算法，要求所用的乘法次數最小，并確定算法中每一個語句的頻度及整個算法的時間復雜度。

1-23 要求將整數1～100 的平方根分成兩組，每組各50個數，使得一組中的各數之和盡可能接近另一組的各數之和。如果只有兩分鐘的機時可用來解決這個問題，那么應進行什么運算？

1-24 設下面過程的參數n取值為2的正方冪，亦即n=2, 4, 8, 16, …。當過程終止時，變量count的值作為n的函數應如何表示？

            int n; int x=2,count=0; while（x<n） {  x=x*2; count++;}

1-25 設A是一個整數數組，函數max(i, n)可求出A中從i到i+n-1的單元中的最大整數。為簡便起見，可假設n是2的方冪。

            int  max（int i, int n）
            {    int m1,m2;
                if（n==1）return A[i];
                else   {   m1=max（i,n/2）;m2=max（i+n/2,n/2）;
                        if（m1<m2） return m2;else  return m1;}
            }

（1）設max在最壞情況下的運行時間函數為T(n)，這里的n是max的第二個參數，表示要在n個整數中尋找最大的整數。試列出T(n)滿足的遞歸方程，也即用若干常數及若干項T(j)（j<n）代表程序max中各語句的運行時間，并用它們表示整個程序的運行時間T(n)。

（2）在大O意義下給出T(n)的一個“精確”上界，即它也可作為大Ω意義下的下界。要求所給出的表達式盡可能簡單。

1-26 某單位每個職工都有一張職工登記表。設想在任何組合的已知條件下（如只知道姓名、知道姓名和單位、知道姓名和性別，等等），如何存放這些登記表，以便能用最快的速度找到某個人的登記表。

1-27 某班本學期開設政治、數學、英語、數據結構和計算機原理5 門課程。n個學生平均成績分優、良、及格和不及格4個等級：90分以上為優，80分至90分為良，60分至79分為及格，60分以下為不及格。用C++語言寫出統計分析算法，并分析算法的時間復雜度。

1-28 已知有實現同一功能的兩個等法，其時間復雜度分別為O(2n)及O(n10)。假設計算機可連續運行107秒，每秒可執行C++基本語句105次。試問：在此條件下，可解問題的規模是多大，即n的范圍約為多少？用什么算法好，并說明理由是什么。

1-29 對下列4 種折半查找程序進行比較，這4個程序哪些是正確的？哪些效率更高？假定下列變量，以及常量n＞0。

程序A：

            void  binsearchA（int a[n], int x, int &k）
            {    int i=0,j=n-1;
                while（i<=j）
                {  k=（i+j）/2;if（a[k]==x）return;if（x>a[k]）i=k+1;else  j=k-1;}
            }

程序B：

            void  binsearchB（int a[n],int x,int &k）
            {    int i=0,j=n-1;
                while（i<j）
                {  k=（i+j）/2;if（a[k]==x） return;if（x>a[k]）i=k;  else  j=k; }
            }

程序C：

            void  binsearchC（int a[n],int x,int &k）
            {   int i=0,j=n-1;
                while（i<=j） {  k=（i+j）/2;if（x<=a[k]）j=k-1;  if（x>=a[k]  i=k+1; }
            }

程序D：

            void  binsearchD（int a[n], int x, int &k）
            {   int i=0,j=n-1;
            while（i<j） {  k=（i+j）/2; if（x<a[k]）j=k;  else i=k+1;  }
            }

（提示：若所查找的元素存在，則程序必須終止于a[k]=x；若不存在具有值x的元素，則程序必須終止于a[k]≠x。）