【正文】 數(shù)據(jù)結(jié)構(gòu)（c語言版）習(xí)題集答案第1章 緒論 簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。解：數(shù)據(jù)是對客觀事物的符號表示。在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。 數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示。 數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。 抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。是對一般數(shù)據(jù)類型的擴展。 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計語言中數(shù)據(jù)類型概念的區(qū)別。解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。抽象數(shù)據(jù)類型通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進行的操作。在定義抽象數(shù)據(jù)類型中的數(shù)據(jù)部分和操作部分時，要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮數(shù)據(jù)的存儲結(jié)構(gòu)和操作的具體實現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。 設(shè)有數(shù)據(jù)結(jié)構(gòu)(D,R)，其中，試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。解： 試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復(fù)數(shù)和有理數(shù)的定義（有理數(shù)是其分子、分母均為自然數(shù)且分母不為零的分?jǐn)?shù)）。 解：ADT Complex{ 數(shù)據(jù)對象：D={r,i|r,i為實數(shù)} 數(shù)據(jù)關(guān)系：R={r,i} 基本操作： InitComplex(amp。C,re,im)操作結(jié)果：構(gòu)造一個復(fù)數(shù)C，其實部和虛部分別為re和im DestroyCmoplex(amp。C)操作結(jié)果：銷毀復(fù)數(shù)C Get(C,k,amp。e) 操作結(jié)果：用e返回復(fù)數(shù)C的第k元的值 Put(amp。C,k,e) 操作結(jié)果：改變復(fù)數(shù)C的第k元的值為e IsAscending(C) 操作結(jié)果：如果復(fù)數(shù)C的兩個元素按升序排列，則返回1，否則返回0 IsDescending(C) 操作結(jié)果：如果復(fù)數(shù)C的兩個元素按降序排列，則返回1，否則返回0 Max(C,amp。e) 操作結(jié)果：用e返回復(fù)數(shù)C的兩個元素中值較大的一個 Min(C,amp。e) 操作結(jié)果：用e返回復(fù)數(shù)C的兩個元素中值較小的一個 }ADT ComplexADT RationalNumber{ 數(shù)據(jù)對象：D={s,m|s,m為自然數(shù)，且m不為0} 數(shù)據(jù)關(guān)系：R={s,m} 基本操作： InitRationalNumber(amp。R,s,m)操作結(jié)果：構(gòu)造一個有理數(shù)R，其分子和分母分別為s和m DestroyRationalNumber(amp。R)操作結(jié)果：銷毀有理數(shù)R Get(R,k,amp。e) 操作結(jié)果：用e返回有理數(shù)R的第k元的值 Put(amp。R,k,e) 操作結(jié)果：改變有理數(shù)R的第k元的值為e IsAscending(R) 操作結(jié)果：若有理數(shù)R的兩個元素按升序排列，則返回1，否則返回0 IsDescending(R) 操作結(jié)果：若有理數(shù)R的兩個元素按降序排列，則返回1，否則返回0 Max(R,amp。e) 操作結(jié)果：用e返回有理數(shù)R的兩個元素中值較大的一個 Min(R,amp。e) 操作結(jié)果：用e返回有理數(shù)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)。 } 在程序設(shè)計中，常用下列三種不同的出錯處理方式：(1) 用exit語句終止執(zhí)行并報告錯誤；(2) 以函數(shù)的返回值區(qū)別正確返回或錯誤返回；(3) 設(shè)置一個整型變量的函數(shù)參數(shù)以區(qū)別正確返回或某種錯誤返回。試討論這三種方法各自的優(yōu)缺點。解：(1)exit常用于異常錯誤處理，它可以強行中斷程序的執(zhí)行，返回操作系統(tǒng)。 (2)以函數(shù)的返回值判斷正確與否常用于子程序的測試，便于實現(xiàn)程序的局部控制。 (3)用整型函數(shù)進行錯誤處理的優(yōu)點是可以給出錯誤類型，便于迅速確定錯誤。 在程序設(shè)計中，可采用下列三種方法實現(xiàn)輸出和輸入：(1) 通過scanf和printf語句；(2) 通過函數(shù)的參數(shù)顯式傳遞；(3) 通過全局變量隱式傳遞。試討論這三種方法的優(yōu)缺點。解：(1)用scanf和printf直接進行輸入輸出的好處是形象、直觀，但缺點是需要對其進行格式控制，較為煩瑣，如果出現(xiàn)錯誤，則會引起整個系統(tǒng)的崩潰。 (2)通過函數(shù)的參數(shù)傳遞進行輸入輸出，便于實現(xiàn)信息的隱蔽，減少出錯的可能。 (3)通過全局變量的隱式傳遞進行輸入輸出最為方便，只需修改變量的值即可，但過多的全局變量使程序的維護較為困難。 設(shè)n為正整數(shù)。試確定下列各程序段中前置以記號@的語句的頻度：(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的常數(shù) 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 假設(shè)n為2的乘冪，并且n2，試求下列算法的時間復(fù)雜度及變量count的值（以n的函數(shù)形式表示）。int Time(int n) { count = 0。 x=2。 while(xn/2) { x *= 2。 count++。 }return count。 }解：count= 已知有實現(xiàn)同一功能的兩個算法，其時間復(fù)雜度分別為和，假設(shè)現(xiàn)實計算機可連續(xù)運算的時間為秒（100多天），又每秒可執(zhí)行基本操作（根據(jù)這些操作來估算算法時間復(fù)雜度）次。試問在此條件下，這兩個算法可解問題的規(guī)模（即n值的范圍）各為多少？哪個算法更適宜？請說明理由。解： n=40 n=16 則對于同樣的循環(huán)次數(shù)n，在這個規(guī)模下，第二種算法所花費的代價要大得多。故在這個規(guī)模下，第一種算法更適宜。 設(shè)有以下三個函數(shù)： ，請判斷以下斷言正確與否：(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)錯 試設(shè)定若干n值，比較兩函數(shù)和的增長趨勢，并確定n在什么范圍內(nèi)，函數(shù)的值大于的值。解：的增長趨勢快。但在n較小的時候，的值較大。 當(dāng)n438時， 判斷下列各對函數(shù)和，當(dāng)時，哪個函數(shù)增長更快？(1) ，(2) ，(3) ，(4) ，解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 試用數(shù)學(xué)歸納法證明：(1) (2) (3) (4) 試寫一算法，自大至小依次輸出順序讀入的三個整數(shù)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項值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。解：k0為階數(shù)，n為數(shù)列的第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]。} 假設(shè)有A，B，C，D，E五個高等院校進行田徑對抗賽，各院校的單項成績均已存入計算機，并構(gòu)成一張表，表中每一行的形式為項目名稱性別校名成績得分編寫算法，處理上述表格，以統(tǒng)計各院校的男、女總分和團體總分，并輸出。解：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。} 試編寫算法，計算的值并存入數(shù)組a[0..arrsize1]的第i1個分量中(i=1,2,…,n)。假設(shè)計算機中允許的整數(shù)最大值為maxint，則當(dāng)narrsize或?qū)δ硞€，使時，應(yīng)按出錯處理。注意選擇你認(rèn)為較好的出錯處理方法。解：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。} 試編寫算法求一元多項式的值的值，并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復(fù)雜度