數據結構課后習題部分參考答案(已修改)

　

【正文】 數據結構課后習題部分參考答案第一章一、選擇題1．C 2．C 　3．A 　 4．D 　5．B二、判斷題1．╳ 2．╳ 3．╳ 4．╳ 　5．∨三、簡答題1． 常見邏輯結構： 集合結構，數據元素之間的關系僅僅是屬于同一個集合。 線性結構，除第一個元素只有一個直接后繼、最后一個元素只有一個直接前驅，其余元素有且只有唯一一個直接前驅、有且只有唯一一個直接后繼，數據元素之間存在一對一的關系。 樹形結構，樹中只有唯一一個根元素，除根元素之外，其余元素只有一個直接前驅，但可以有多個直接后繼元素，數據元素之間存在一對多的關系。 圖形結構，元素之間關系任意，數據元素之間存在多對多的關系。常用的存儲結構： 順序存儲，把邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中，由此得到的存儲表示稱為順序存儲結構。通常用數組實現。 鏈式存儲，對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關系通過附加的指針字段來表示，由此得到的存儲表示稱為鏈式存儲結構。通常用指針來實現。除上述兩種方法外，有時為了查找方便還采用索引存儲方法和散列存儲方法。索引存儲：在存儲結點信息的同時，還建立附加的索引表來標識結點的地址。散列存儲：根據元素的關鍵碼確定元素存儲位置的存儲方式。2． 算法與程序的區別： 程序不一定滿足有窮性(如操作系統)； 程序中的指令必須是機器可執行的，算法中的指令則無此限制； 算法代表了對問題的解，程序則是算法在計算機上的特定的實現(一個算法若用程序設計語言來描述，它才是一個程序)。數據結構+算法=程序。3．例如有一張學生成績表，記錄了一個班的學生各門課的成績。按學生的姓名為一行記成的表。這個表就是一個數據結構。每個記錄就是一個結點，對于整個表來說，只有一個開始結點和一個終端結點，其他的結點則各有一個也只有一個直接前趨和直接后繼。這幾個關系就確定了這個表的邏輯結構——線形結構。那么我們怎樣把這個表中的數據存儲到里呢? 用高級語言如何表示各結點之間的關系呢? 是用一片連續的內存單元來存放這些記錄（順序存儲）還是隨機存放各結點數據再用指針進行鏈接（鏈式存儲）呢? 這就是存儲結構的問題，我們都是從高級語言的層次來討論這個問題的。最后，我們有了這個表，肯定要用它，那么就是要對這張表中的記錄進行查詢，修改，刪除等操作，對這個表可以進行哪些操作以及如何實現這些操作就是數據的運算問題了。4．例如棧和隊列，兩個數據結構的邏輯結構和存儲方式完全相同，只是對于運算（如插入、刪除）的定義不同，兩個結構具有顯著不同的特性。5．語句頻度（1）n1 （2）1 （3）n(n+1)/2 （4）n/21 （5）100 6．時間復雜度（1）O(log3n) （2）O(n2) （3）O(n2)7．算法思想： P (x，n)=(…((anx+an1)x+an2)x+…+a1)x+a0 語句： y=0 。 for (i=n。i=0。i) y=y*x+ ai 。 函數：void p( ){float x,y。int n,i,a。scanf(%f,amp。x)。scanf(%d,amp。n)。y=0。 for (i=n。i=0。i) {scanf(%d,amp。a)。y=y*x+a。 } printf(x=%,y=%,x,y)。}第二章一、選擇題1．A 2．A 　3．D 　 4．C 　5．D6．B 7．C 　8．B 　 9．A 　10．D11．B 12．D二、判斷題1．╳ 2．∨ 3．╳ 4．∨ 　 5．╳ 　　6．∨ 　 7．╳ 8．∨ 　 9．∨ 　 10．╳ 11．╳ 　 12．╳三、算法設計題1．第一種方法（從后往前比較）： 因已知順序表L是遞增有序表，所以只要從順序表終端結點（設為i位置元素）開始向前尋找到第一個小于或等于x的元素位置i后，插入該位置后面即可。　　在尋找過程中，由于大于x的元素都應放在x之后，所以可邊尋找，邊后移元素，當找到第一個小于或等于x的元素位置i時，插入x的位置i+1也空出來了。　　算法如下：void InsertIncreaseList1(seqlist *L,datatype x){int i。 if (Lelemnum==maxsize) printf(overflow)。 // Lelemnum 中存放當前順序表中的元素個數 for (i=Lelemnum1。i=0 amp。amp。 Ldata[i]x。i) Ldata[i+1]=Ldata[i]。 //從后往前比較并移動元素 Ldata[i+1]=x。 Lelemnum++。}第二種方法（從前往后比較）：void InsertIncreaseList2(seqlist *L,datatype x){int i,j。 if (Lelemnum==maxsize) printf(overflow)。 i=0。 while((i=Lelemnum1)amp。amp。(Ldata[i]x)) i++。 //從前往后比較尋找插入位置 for(j=Lelemnum1。j=i。j) Ldata[j+1]=Ldata[j]。 //騰位置 Ldata[i]=x。 //插入 Lelemnum++。}　　　2（思路同算法216）6（同1類似，最好也做一下。1是順序存儲，6是鏈式存儲。做完同1比較一下）7（看算法217,尾插實現）第三章一、選擇題1．C 2．B 　3．D 　 4．B 　5．B6．C 7．B 　8．D 　 9．C 　10．C二、判斷題1．∨ 2．∨ 3．∨ 4．╳ 　 5．╳ 　　三、簡答題1循環隊列的優點是：它可以克服順序隊列的假上溢現象，能夠使存儲隊列的向量空間得到充分的利用。 判別循環隊列的空或滿通常有兩種方法：（1）另設一個變量num記錄當前隊列中的元素個數,當num==0時隊空， num==maxsize時隊滿。（2）少用一個存儲單元(即少存一個元素), 隊空條件為front == rear，隊滿條件為(rear + 1) % maxsize == front 。2．棧的特點是先進后出，隊列的特點是先進先出。 先進后出用棧；先進先出用隊列。3．一個直接調用自己或通過一系列調用間接調用自己的過程稱為遞歸。 遞歸程序結構清晰，可讀性強，而且容易用數學歸納法來證明程序的正確性。 遞歸程序運行效率低，不論是耗費的計算時間還是占用的存儲空間都比非遞歸程序要多。4．1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321（十四種可能）四、算法設計題1．思想：將一半字符入棧) 算法為：　//以下為順序棧的存儲結構定義　define StackSize 100 //假定預分配的棧空間最多為100個元素　typedef char DataType。//假定棧元素的數據類型為字符　typedef struct{　　DataType data[StackSize]。　　int top。　}SeqStack。　int IsHuiwen( char *t)　　{//判斷t字符向量是否為回文，若是，返回1，否則返回0