數據結構題集答案(已修改)

　

【正文】 第1章 緒論 簡述下列術語：數據，數據元素、數據對象、數據結構、存儲結構、數據類型和抽象數據類型。解：數據是對客觀事物的符號表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。 數據元素是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。 數據對象是性質相同的數據元素的集合，是數據的一個子集。 數據結構是相互之間存在一種或多種特定關系的數據元素的集合。 存儲結構是數據結構在計算機中的表示。 數據類型是一個值的集合和定義在這個值集上的一組操作的總稱。 抽象數據類型是指一個數學模型以及定義在該模型上的一組操作。是對一般數據類型的擴展。 試描述數據結構和抽象數據類型的概念與程序設計語言中數據類型概念的區別。解：抽象數據類型包含一般數據類型的概念，但含義比一般數據類型更廣、更抽象。一般數據類型由具體語言系統內部定義，直接提供給編程者定義用戶數據，因此稱它們為預定義數據類型。抽象數據類型通常由編程者定義，包括定義它所使用的數據和在這些數據上所進行的操作。在定義抽象數據類型中的數據部分和操作部分時，要求只定義到數據的邏輯結構和操作說明，不考慮數據的存儲結構和操作的具體實現，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。 設有數據結構(D,R)，其中，試按圖論中圖的畫法慣例畫出其邏輯結構圖。解： 試仿照三元組的抽象數據類型分別寫出抽象數據類型復數和有理數的定義（有理數是其分子、分母均為自然數且分母不為零的分數）。 解：ADT Complex{ 數據對象：D={r,i|r,i為實數} 數據關系：R={r,i} 基本操作： InitComplex(amp。C,re,im)操作結果：構造一個復數C，其實部和虛部分別為re和im DestroyCmoplex(amp。C)操作結果：銷毀復數C Get(C,k,amp。e) 操作結果：用e返回復數C的第k元的值 Put(amp。C,k,e) 操作結果：改變復數C的第k元的值為e IsAscending(C) 操作結果：如果復數C的兩個元素按升序排列，則返回1，否則返回0 IsDescending(C) 操作結果：如果復數C的兩個元素按降序排列，則返回1，否則返回0 Max(C,amp。e) 操作結果：用e返回復數C的兩個元素中值較大的一個 Min(C,amp。e) 操作結果：用e返回復數C的兩個元素中值較小的一個 }ADT ComplexADT RationalNumber{ 數據對象：D={s,m|s,m為自然數，且m不為0} 數據關系：R={s,m} 基本操作： InitRationalNumber(amp。R,s,m)操作結果：構造一個有理數R，其分子和分母分別為s和m DestroyRationalNumber(amp。R)操作結果：銷毀有理數R Get(R,k,amp。e) 操作結果：用e返回有理數R的第k元的值 Put(amp。R,k,e) 操作結果：改變有理數R的第k元的值為e IsAscending(R) 操作結果：若有理數R的兩個元素按升序排列，則返回1，否則返回0 IsDescending(R) 操作結果：若有理數R的兩個元素按降序排列，則返回1，否則返回0 Max(R,amp。e) 操作結果：用e返回有理數R的兩個元素中值較大的一個 Min(R,amp。e) 操作結果：用e返回有理數R的兩個元素中值較小的一個 }ADT RationalNumber 試畫出與下列程序段等價的框圖。(1) product=1。 i=1。 while(i=n){ product *= i。 i++。 }(2) i=0。 do { i++。 } while((i!=n) amp。amp。 (a[i]!=x))。(3) switch { case xy: z=yx。 break。 case x=y: z=abs(x*y)。 break。 default: z=(xy)/abs(x)*abs(y)。 } 在程序設計中，常用下列三種不同的出錯處理方式：(1) 用exit語句終止執行并報告錯誤；(2) 以函數的返回值區別正確返回或錯誤返回；(3) 設置一個整型變量的函數參數以區別正確返回或某種錯誤返回。試討論這三種方法各自的優缺點。解：(1)exit常用于異常錯誤處理，它可以強行中斷程序的執行，返回操作系統。 (2)以函數的返回值判斷正確與否常用于子程序的測試，便于實現程序的局部控制。 (3)用整型函數進行錯誤處理的優點是可以給出錯誤類型，便于迅速確定錯誤。 在程序設計中，可采用下列三種方法實現輸出和輸入：(1) 通過scanf和printf語句；(2) 通過函數的參數顯式傳遞；(3) 通過全局變量隱式傳遞。試討論這三種方法的優缺點。解：(1)用scanf和printf直接進行輸入輸出的好處是形象、直觀，但缺點是需要對其進行格式控制，較為煩瑣，如果出現錯誤，則會引起整個系統的崩潰。 (2)通過函數的參數傳遞進行輸入輸出，便于實現信息的隱蔽，減少出錯的可能。 (3)通過全局變量的隱式傳遞進行輸入輸出最為方便，只需修改變量的值即可，但過多的全局變量使程序的維護較為困難。 設n為正整數。試確定下列各程序段中前置以記號@的語句的頻度：(1) i=1。 k=0。 while(i=n1){ @ k += 10*i。 i++。 }(2) i=1。 k=0。 do { @ k += 10*i。 i++。 } while(i=n1)。(3) i=1。 k=0。 while (i=n1) { i++。 @ k += 10*i。 }(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 += delta。 }(6) i=1。 j=0。 while(i+j=n) { @ if(ij) j++。 else i++。 }(7) x=n。 y=0。 // n是不小于1的常數 while(x=(y+1)*(y+1)) { @ y++。 }(8) x=91。 y=100。 while(y0) { @ if(x100) { x = 10。 y。 } else x++。 }解：(1) n1 (2) n1 (3) n1 (4) n+(n1)+(n2)+...+1= (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)= = = (6) n (7) 向下取整 (8) 1100 假設n為2的乘冪，并且n2，試求下列算法的時間復雜度及變量count的值（以n的函數形式表示）。int Time(int n) { count = 0。 x=2。 while(xn/2) { x *= 2。 count++。 }return count。 }解：count= 已知有實現同一功能的兩個算法，其時間復雜度分別為和，假設現實計算機可連續運算的時間為秒（100多天），又每秒可執行基本操作（根據這些操作來估算算法時間復雜度）次。試問在此條件下，這兩個算法可解問題的規模（即n值的范圍）各為多少？哪個算法更適宜？請說明理由。解： n=40 n=16 則對于同樣的循環次數n，在這個規模下，第二種算法所花費的代價要大得多。故在這個規模下，第一種算法更適宜。 設有以下三個函數： ，請判斷以下斷言正確與否：(1) f(n)是O(g(n))(2) h(n)是O(f(n))(3) g(n)是O(h(n))(4) h(n)是O()(5) h(n)是O(nlogn)解：(1)對 (2)錯 (3)錯 (4)對 (5)錯 試設定若干n值，比較兩函數和的增長趨勢，并確定n在什么范圍內，函數的值大于的值。解：的增長趨勢快。但在n較小的時候，的值較大。 當n438時， 判斷下列各對函數和，當時，哪個函數增長更快？(1) ，(2) ，(3) ，(4) ，解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 試用數學歸納法證明：(1) (2) (3) (4) 試寫一算法，自大至小依次輸出順序讀入的三個整數X，Y和Z的值解：int max3(int x,int y,int z){ if(xy) if(xz) return x。 else return z。 else if(yz) return y。 else return z。} 已知k階斐波那契序列的定義為 ，…，； ， 試編寫求k階斐波那契序列的第m項值的函數算法，k和m均以值調用的形式在函數參數表中出現。解：k0為階數，n為數列的第n項int Fibonacci(int k,int n){ if(k1) exit(OVERFLOW)。int *p,x。 p=new int[k+1]。 if(!p) exit(OVERFLOW)。 int i,j。 for(i=0。ik+1。i++){ if(ik1) p[i]=0。 else p[i]=1。 } for(i=k+1。in+1。i++){ x=p[0]。 for(j=0。jk。j++) p[j]=p[j+1]。 p[k]=2*p[k1]x。 } return p[k]。} 假設有A，B，C，D，E五個高等院校進行田徑對抗賽，各院校的單項成績均已存入計算機，并構成一張表，表中每一行的形式為項目名稱性別校名成績得分編寫算法，處理上述表格，以統計各院校的男、女總分和團體總分，并輸出。解：typedef enum{A,B,C,D,E} SchoolName。typedef enum{Female,Male} SexType。typedef struct{ char event[3]。 //項目 SexType sex。 SchoolName school。 int score。} Component。typedef struct{ int MaleSum。 //男團總分 int FemaleSum。 //女團總分 int TotalSum。 //團體總分} Sum。Sum SumScore(SchoolName sn,Component a[],int n){ Sum temp。 =0。 =0。 =0。 int i。 for(i=0。in。i++){ if(a[i].school==sn){ if(a[i].sex==Male) +=a[i].score。 if(a[i].sex==Female) +=a[i].score。 } } =+。 return temp。} 試編寫算法，計算的值并存入數組a[0..arrsize1]的第i1個分量中(i=1,2,…,n)。假設計算機中允許的整數最大值為maxint，則當narrsize或對某個，使時，應按出錯處理。注意選擇你認為較好的出錯處理方法。解：includeincludedefine MAXINT 65535define ArrSize 100int fun(int i)。int main(){ int i,k。 int a[ArrSize]。 coutEnter k:。 cink。 if(kArrSize1) exit(0)。 for(i=0。i=k。i++){ if(i==0) a[i]=1。 else{ if(2*i*a[i1]MAXINT) exit(0)。 else a[i]=2*i*a[i1]。 } } for(i=0。i=k。i++){ if(a[i]MAXINT) exit(0)。 else couta[i] 。 } return 0。} 試編寫算法求一元多項式的值的值，并確定算法中每一語句的執行次數和整個算法的時間復雜度。注意選擇你認為較好的輸入和輸出方