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