...wd......wd......wd...?數(shù)據(jù)構(gòu)造簡(jiǎn)明教程?練習(xí)題及參考答案練習(xí)題11.單項(xiàng)選擇題〔1〕線性構(gòu)造中數(shù)據(jù)元素之間是〔〕關(guān)系。A.一對(duì)多B.多對(duì)多C.多對(duì)一D.一對(duì)一答：D〔2〕數(shù)據(jù)構(gòu)造中與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的〔〕構(gòu)造。A.存儲(chǔ)B.物理C.邏輯D.物理和存儲(chǔ)答：C〔3〕算法分析的目的是〔〕。A.找出數(shù)據(jù)構(gòu)造的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性答：C〔4〕算法分析的兩個(gè)主要方面是〔〕。A.空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡(jiǎn)明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性答：A〔5〕計(jì)算機(jī)算法指的是〔〕。A.計(jì)算方法B.排序方法C.求解問題的有限運(yùn)算序列D.調(diào)度方法答：C〔6〕計(jì)算機(jī)算法必須具備輸入、輸出和〔〕等5個(gè)特性。A.可行性、可移植性和可擴(kuò)大性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性答：B2.填空題〔1〕數(shù)據(jù)構(gòu)造包括數(shù)據(jù)的①、數(shù)據(jù)的②和數(shù)據(jù)的③這三個(gè)方面的內(nèi)容。答：①邏輯構(gòu)造②存儲(chǔ)構(gòu)造③運(yùn)算〔2〕數(shù)據(jù)構(gòu)造按邏輯構(gòu)造可分為兩大類，它們分別是①和②。答：①線性構(gòu)造②非線性構(gòu)造〔3〕數(shù)據(jù)構(gòu)造被形式地定義為〔D,R〕，其中D是①的有限集合，R是D上的②有限集合。答：①數(shù)據(jù)元素②關(guān)系〔4〕在線性構(gòu)造中，第一個(gè)結(jié)點(diǎn)①前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)②后繼結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后繼結(jié)點(diǎn)。答：①?zèng)]有②沒有〔5〕在樹形構(gòu)造中，樹根結(jié)點(diǎn)沒有①結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有②個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有③結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)數(shù)可以是④。答：①前驅(qū)②1③后繼④任意多個(gè)〔6〕在圖形構(gòu)造中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以是〔〕。答：任意多個(gè)〔7〕數(shù)據(jù)的存儲(chǔ)構(gòu)造主要有四種，它們分別是①、②、③和④存儲(chǔ)構(gòu)造。答：①順序②鏈?zhǔn)舰鬯饕芄！?〕一個(gè)算法的效率可分為①效率和②效率。答：①時(shí)間②空間3.簡(jiǎn)答題〔1〕數(shù)據(jù)構(gòu)造和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎答：簡(jiǎn)單地說，數(shù)據(jù)構(gòu)造定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素的集合。數(shù)據(jù)類型不僅定義了一組數(shù)據(jù)元素，而且還在其上定義了一組操作?！?〕簡(jiǎn)述線性構(gòu)造、樹形構(gòu)造和圖形構(gòu)造的不同點(diǎn)。答：線性構(gòu)造反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的，樹形線性構(gòu)造反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)多的，圖在構(gòu)造反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的?！?〕設(shè)有采用二元組表示的數(shù)據(jù)邏輯構(gòu)造S=(D,R)，其中D={a,b,…,i}，R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)}，問相對(duì)于關(guān)系R，哪些結(jié)點(diǎn)是開場(chǎng)結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)答：該邏輯構(gòu)造為樹形構(gòu)造，其中a結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，b、e、g、i結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，是終端結(jié)點(diǎn)，也稱為葉子結(jié)點(diǎn)?！?〕以下各函數(shù)是算法中語句的執(zhí)行頻度，n為問題規(guī)模，給出對(duì)應(yīng)的時(shí)間復(fù)雜度：T1(n)=nlog2n-1000log2nT2(n)=-1000log2nT3(n)=n2-1000log2nT4(n)=2nlog2n-1000log2n答：T1(n)=O(nlog2n)，T2(n)=O()，T3(n)=O(n2)，T4(n)=O(nlog2n)?！?〕分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。intj=0,s=0,n=100;do{ j=j+1; s=s+10*j;}while(j<n&&s<n);答：j=0，第1次循環(huán)：j=1，s=10。第2次循環(huán)：j=2，s=30。第3次循環(huán)：j=3，s=60。第4次循環(huán)：j=4，s=100。while條件不再滿足。所以，其中循環(huán)語句的執(zhí)行次數(shù)為4?！?〕執(zhí)行下面的語句時(shí)，語句s++的執(zhí)行次數(shù)為多少ints=0;for(i=1;i<n-1;i++) for(j=n;j>=i;j--)s++;答：語句s的執(zhí)行次數(shù)?！?〕設(shè)n為問題規(guī)模，求以下算法的時(shí)間復(fù)雜度。voidfun1(intn){ intx=0,i; for(i=1;i<=n;i++) for(j=i+1;j<=n;j++)x++;}答：其中x++語句屬基本運(yùn)算語句，=O(n2)?！?〕設(shè)n為問題規(guī)模，是一個(gè)正偶數(shù)，試計(jì)算以下算法完畢時(shí)m的值，并給出該算法的時(shí)間復(fù)雜度。voidfun2(intn){ intm=0;for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m++;}答：由，該程序段的時(shí)間復(fù)雜度為O(n2)。上機(jī)實(shí)驗(yàn)題1有一個(gè)整型數(shù)組a，其中含有n個(gè)元素，設(shè)計(jì)盡可能好的算法求其中的最大元素和次大元素，并采用相關(guān)數(shù)據(jù)測(cè)試。解：maxs算法用于返回?cái)?shù)組a[0..n-1]中的最大元素值max1和次大元素值max2，max1和max2設(shè)計(jì)為引用類型。對(duì)應(yīng)的程序如下：#include<stdio.h>voidmaxs(inta[],intn,int&max1,int&max2){ inti; max1=max2=a[0]; for(i=1;i<n;i++) if(a[i]>max1) { max2=max1; max1=a[i]; } elseif(a[i]>max2) max2=a[i];}voidmain(){ inta[]={1,4,10,6,8,3,5,7,9,2}; intn=10; intmax1,max2;maxs(a,n,max1,max2); printf("最大元素值=%d,次大元素值=%d\n",max1,max2);}練習(xí)題21.單項(xiàng)選擇題〔1〕數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相對(duì)順序一樣并且是連續(xù)的，稱之為〔〕。A.存儲(chǔ)構(gòu)造B.邏輯構(gòu)造C.順序存儲(chǔ)構(gòu)造D.鏈?zhǔn)酱鎯?chǔ)構(gòu)造答：C〔2〕在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O〔1〕的操作是〔〕。A.訪問第i個(gè)結(jié)點(diǎn)〔1≤i≤n〕和求第i〔2≤i≤n〕個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)B.在第i〔1≤i≤n〕個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C.刪除第i個(gè)結(jié)點(diǎn)〔1≤i≤n〕D.將n個(gè)結(jié)點(diǎn)從小到大排序答：A〔3〕向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)〔〕個(gè)元素。A.8B.63.5C.63D.7答：B〔4〕鏈?zhǔn)酱鎯?chǔ)構(gòu)造所占存儲(chǔ)空間〔〕。A.分兩局部，一局部存放結(jié)點(diǎn)值，另一局部存放表示結(jié)點(diǎn)間關(guān)系的指針B.只有一局部，存放結(jié)點(diǎn)值C.只有一局部，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針D.分兩局部，一局部存放結(jié)點(diǎn)值，另一局部存放結(jié)點(diǎn)所占單元數(shù)答：A〔5〕線性表假設(shè)采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址〔〕。A.必須是連續(xù)的B.局部地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以答：D〔6〕一個(gè)線性表在〔〕情況下適用于采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造。A.需經(jīng)常修改其中的結(jié)點(diǎn)值B.需不斷對(duì)其進(jìn)展刪除插入C.其中含有大量的結(jié)點(diǎn)D.其中結(jié)點(diǎn)構(gòu)造復(fù)雜答：B〔7〕單鏈表的存儲(chǔ)密度〔〕A.大于1B.等于1C.小于1D.不能確定答：C2.填空題〔1〕在順序表中插入或刪除一個(gè)元素時(shí)，需要平均移動(dòng)〔①〕元素，具體移動(dòng)的元素個(gè)數(shù)與〔②〕有關(guān)。答：①表中一半②表長(zhǎng)和該元素在表中的位置〔2〕向一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素〔1≤i≤n+1〕之前插入一個(gè)元素時(shí)，需向后移動(dòng)〔〕個(gè)元素。答：n-i+1〔3〕向一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素〔1≤i≤n〕時(shí)，需向前移動(dòng)〔〕個(gè)元素。答：n-i〔4〕在順序表中訪問任意一個(gè)元素的時(shí)間復(fù)雜度均為〔①〕，因此順序表也稱為〔②〕的數(shù)據(jù)構(gòu)造。答：①O(1)②隨機(jī)存取〔5〕順序表中邏輯上相鄰的元素的物理位置〔①〕相鄰。單鏈表中邏輯上相鄰的元素的物理位置〔②〕相鄰。答：①一定②不一定〔6〕在帶頭結(jié)點(diǎn)的單鏈表中，除頭結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由〔〕指示。答：其前驅(qū)結(jié)點(diǎn)的鏈域的值〔7〕在含有n個(gè)數(shù)據(jù)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除結(jié)點(diǎn)*p，需找到它的〔①〕，其時(shí)間復(fù)雜度為〔②〕。答：①前驅(qū)結(jié)點(diǎn)的地址②O(n)〔8〕含有n〔n>1〕個(gè)結(jié)點(diǎn)的循環(huán)雙向鏈表中，為空的指針域數(shù)為〔〕。答：03.簡(jiǎn)答題〔1〕試比較順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好答：順序存儲(chǔ)構(gòu)造中，相鄰數(shù)據(jù)元素的存放地址也相鄰，并要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。其優(yōu)點(diǎn)是存儲(chǔ)密度大，存儲(chǔ)空間利用率高；缺點(diǎn)是插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯?chǔ)構(gòu)造中，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩局部，一局部存放結(jié)點(diǎn)值，另一局部存放表示結(jié)點(diǎn)間關(guān)系的指針。其優(yōu)點(diǎn)是插入或刪除元素時(shí)很方便，使用靈活；缺點(diǎn)是存儲(chǔ)密度小，存儲(chǔ)空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。假設(shè)線性表的長(zhǎng)度變化不大，且其主要操作是查找，那么采用順序表；假設(shè)線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，那么采用鏈表。〔2〕對(duì)于表長(zhǎng)為n的順序表，在任何位置上插入或刪除一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需要移動(dòng)的元素的平均個(gè)數(shù)為多少刪除一個(gè)元素所需要移動(dòng)的平均個(gè)數(shù)為多少答：插入一個(gè)元素所需要移動(dòng)的元素的平均個(gè)數(shù)為(n-1)/2，刪除一個(gè)元素所需要移動(dòng)的平均個(gè)數(shù)為n/2?！?〕在鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么答：在鏈表中設(shè)置頭結(jié)點(diǎn)后，不管鏈表是否為空表，頭結(jié)點(diǎn)指針均不空，并使得對(duì)鏈表的操作〔如插入和刪除〕在各種情況下統(tǒng)一，從而簡(jiǎn)化了算法的實(shí)現(xiàn)過程?！?〕對(duì)于雙鏈表和單鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)時(shí)需修改的指針各為多少個(gè)答：對(duì)于雙鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)時(shí)，需修改前驅(qū)結(jié)點(diǎn)的next域、后繼結(jié)點(diǎn)的prior域和新插入結(jié)點(diǎn)的next、prior域。所以共修改4個(gè)指針。對(duì)于單鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)時(shí)，需修改前一結(jié)點(diǎn)的next域，新插入結(jié)點(diǎn)的next域。所以共修改兩個(gè)指針?！?〕某含有n〔n>1〕結(jié)點(diǎn)的線性表中，最常用的操作是在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，那么采用以下哪種存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。①單鏈表；②僅有頭指針不帶頭結(jié)點(diǎn)的循環(huán)單鏈表；③雙鏈表；④僅有尾指針的循環(huán)單鏈表。答：在單鏈表中，刪除第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)。插入結(jié)點(diǎn)需找到前驅(qū)結(jié)點(diǎn)，所以在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)，需找到尾結(jié)點(diǎn)，對(duì)應(yīng)的時(shí)間復(fù)雜度為O(n)。在僅有頭指針不帶頭結(jié)點(diǎn)的循環(huán)單鏈表中，刪除第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度O(n)，因?yàn)閯h除第一個(gè)結(jié)點(diǎn)后還要將其改為循環(huán)單鏈表；在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度也為O(n)。在雙鏈表中，刪除第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)；在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)，也需找到尾結(jié)點(diǎn)，對(duì)應(yīng)的時(shí)間復(fù)雜度為O(n)。在僅有尾指針的循環(huán)單鏈表中，通過該尾指針可以直接找到第一個(gè)結(jié)點(diǎn)，所以刪除第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)；在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)也就是在尾指針?biāo)附Y(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)，時(shí)間復(fù)雜度也為O(1)。因此④最節(jié)省運(yùn)算時(shí)間。4.算法設(shè)計(jì)題〔1〕設(shè)計(jì)一個(gè)高效算法，將順序表的所有元素逆置，要求算法空間復(fù)雜度為O(1)。解：遍歷順序表L的前半局部元素，對(duì)于元素L.data[i]〔0≤i＜L.length/2〕，將其與后半局部對(duì)應(yīng)元素L.data[L.length-i-1]進(jìn)展交換。對(duì)應(yīng)的算法如下：voidreverse(SqList&L){ inti; ElemTypex; for(i=0;i<L.length/2;i++) { x=L.data[i]; //L.data[i]與L.data[L.length-i-1]交換L.data[i]=L.data[L.length-i-1]; L.data[L.length-i-1]=x;}}本算法的時(shí)間復(fù)雜度為O(n)?！?〕設(shè)計(jì)一個(gè)算法從順序表中刪除重復(fù)的元素，并使剩余元素間的相對(duì)次序保持不變。解：對(duì)于順序表L，用i從1開場(chǎng)遍歷其元素，設(shè)L.data[0..j]〔j的初值為0〕中沒有重復(fù)的元素。檢測(cè)L.data[i]〔j<i<L.length〕，假設(shè)L.data[i]和L.data[0..j]中任何一個(gè)元素都不一樣，那么將L.data[i]存入L.data[j+1]中。對(duì)應(yīng)的算法如下：voiddelsame(SqList&L)//L為引用型參數(shù){ inti,j=0,k; for(i=1;i<L.length;i++){ k=0; while(k<=j&&L.data[k]!=L.data[i]) k++; if(k>j) //表示L.data[i]和L.data[0..j]中所有元素都不一樣{ j++; L.data[j]=L.data[i]; }}L.length=j+1;//順序表長(zhǎng)度置新值}本算法的時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)?！?〕設(shè)計(jì)一個(gè)算法從有序順序表中刪除重復(fù)的元素，并使剩余元素間的相對(duì)次序保持不變。解：在有序順序表L中，所有重復(fù)的元素應(yīng)是相鄰存放的，用k保存不重復(fù)出現(xiàn)的元素個(gè)數(shù)，先將不重復(fù)的有序區(qū)看成是L.data[0..0]，置e=L.data[0]，用i從1開場(chǎng)遍歷L的所有元素：當(dāng)L.data[i]≠e時(shí)，將它放在L.data[k]中，k增1，置e=L.data[i]，最后將L的length置為k。對(duì)應(yīng)的算法如下：voiddelsame1(SqList&L) //L為引用型參數(shù){ inti,k=1; //k保存不重復(fù)的元素個(gè)數(shù) ElemTypee;e=L.data[0]; for(i=1;i<L.length;i++){ if(L.data[i]!=e) //只保存不重復(fù)的元素{ L.data[k]=L.data[i];k++; e=L.data[i]; } } L.length=k; //順序表長(zhǎng)度置新值}本算法是一個(gè)高效算法，其時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。如果每次遇到重復(fù)的元素，都通過移動(dòng)其后所有元素來刪除它，這樣的時(shí)間復(fù)雜度會(huì)變成O(n2)。〔4〕設(shè)計(jì)一個(gè)算法刪除單鏈表L中第一個(gè)值為x的結(jié)點(diǎn)。解：用p、q遍歷整個(gè)單鏈表，p指向*q的前驅(qū)結(jié)點(diǎn)，q用于查找第一個(gè)值為x的結(jié)點(diǎn)，當(dāng)找到后將*q結(jié)點(diǎn)刪除，返回1；否那么返回0。對(duì)應(yīng)的算法如下：intdelx(SLink*&L,ElemTypex){ SLink*p=L,*q=p->next; //p指向*q的前驅(qū)結(jié)點(diǎn) while(q!=NULL&&q->data!=x) { p=q; q=q->next; } if(q!=NULL) //找到值為x的結(jié)點(diǎn) { p->next=q->next; free(q); return1; } elsereturn0; //未找到值為x的結(jié)點(diǎn)}〔5〕設(shè)計(jì)一個(gè)算法判定單鏈表L是否是遞增的。解：判定鏈表L從第2個(gè)結(jié)點(diǎn)開場(chǎng)的每個(gè)結(jié)點(diǎn)的值是否比其前驅(qū)的值大。假設(shè)有一個(gè)不成立，那么整個(gè)鏈表便不是遞增的；否那么是遞增的。對(duì)應(yīng)的算法如下：intincrease(SLink*L){ SLink*pre=L->next,*p; //pre指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn) p=pre->next; //p指向*pre結(jié)點(diǎn)的后繼結(jié)點(diǎn) while(p!=NULL) { if(p->data>=pre->data) //假設(shè)正序那么繼續(xù)判斷下一個(gè)結(jié)點(diǎn) { pre=p; //pre、p同步后移 p=p->next; } elsereturn0; } return1;}〔6〕有一個(gè)整數(shù)元素建設(shè)的單鏈表A，設(shè)計(jì)一個(gè)算法，將其拆分成兩個(gè)單鏈表A和B，使得A單鏈表中含有所有的偶數(shù)結(jié)點(diǎn)，B單鏈表中所有的奇數(shù)結(jié)點(diǎn)，且保持原來的相對(duì)次序。解：采用重新單鏈表的方法，由于要保持相對(duì)次序，所以采用尾插法建設(shè)新表A、B。用p遍歷原單鏈表A的所有數(shù)據(jù)結(jié)點(diǎn)，假設(shè)為偶數(shù)結(jié)點(diǎn)，將其鏈到A中，假設(shè)為奇數(shù)結(jié)點(diǎn)，將其鏈到B中。對(duì)應(yīng)的算法如下：voidSplit(SLink*&A,SLink*&B){SLink*p=A->next,*ra,*rb; ra=A; B=(SLink*)malloc(sizeof(SLink)); //建設(shè)頭結(jié)點(diǎn) rb=B; //r總是指向B鏈表的尾結(jié)點(diǎn) while(p!=NULL) { if(p->data%2==0) //偶數(shù)結(jié)點(diǎn) { ra->next=p; //將*p結(jié)點(diǎn)鏈到A中 ra=p; p=p->next; } else //奇數(shù)結(jié)點(diǎn) { rb->next=p; //將*p結(jié)點(diǎn)鏈到B中 rb=p; p=p->next; } } ra->next=rb->next=NULL;}本算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)?！?〕有一個(gè)有序單鏈表〔從小到大排列〕，表頭指針為L(zhǎng)，設(shè)計(jì)一個(gè)算法向該單鏈表中插入一個(gè)元素為x的結(jié)點(diǎn)，使插入后該鏈表仍然有序。解：先建設(shè)一個(gè)待插入的結(jié)點(diǎn)，然后依次與鏈表中的各結(jié)點(diǎn)的數(shù)據(jù)域比較大小，找到插入該結(jié)點(diǎn)的位置，最后插入該結(jié)點(diǎn)。對(duì)應(yīng)的算法如下：voidinorderList(SLink*&L,ElemTypex){ SLink*s,*p,*q; s=(SLink*)malloc(sizeof(SLink));//建設(shè)一個(gè)待插入的結(jié)點(diǎn) s->data=x;s->next=NULL; if(L==NULL||x<L->data) //假設(shè)單鏈表為空或x小于第1個(gè)結(jié)點(diǎn)date域 { s->next=L; //把*s結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后L=s; } else { q=L; //尋找插入位置,p指向待比較的結(jié)點(diǎn),q指向p的前驅(qū)結(jié)點(diǎn) p=q->next; while(p!=NULL&&x>p->data) //假設(shè)x小于p所指結(jié)點(diǎn)的data域值 if(x>p->data) { q=p; p=p->next; } s->next=p; //將s結(jié)點(diǎn)插入到*q和*p之間 q->next=s;}}〔8〕有一個(gè)單鏈表L，其中可能出現(xiàn)值域重復(fù)的結(jié)點(diǎn)，設(shè)計(jì)一個(gè)算法刪除值域重復(fù)的結(jié)點(diǎn)。并分析算法的時(shí)間復(fù)雜度。解：用p遍歷單鏈表，用r遍歷*p結(jié)點(diǎn)之后的結(jié)點(diǎn)，q始終指向*r結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，假設(shè)r->data==p->data，那么刪除*r結(jié)點(diǎn)，否那么q、r同步后移一個(gè)結(jié)點(diǎn)。對(duì)應(yīng)的算法如下：voiddels1(SLink*&L){ SLink*p=L->next,*q,*r,*t; while(p!=NULL) { q=p; r=q->next; while(r!=NULL) { if(r->data==p->data) //r指向被刪結(jié)點(diǎn) { t=r->next; q->next=t;free(r); r=t; } else { q=r;r=r->next; } } p=p->next; }}本算法的時(shí)間復(fù)雜度為O(n2)?！?〕有一個(gè)遞增有序單鏈表〔允許出現(xiàn)值域重復(fù)的結(jié)點(diǎn)〕，設(shè)計(jì)一個(gè)算法刪除值域重復(fù)的結(jié)點(diǎn)。并分析算法的時(shí)間復(fù)雜度。解：由于是有序表，所以一樣值域的結(jié)點(diǎn)都是相鄰的。用p遍歷遞增單鏈表，假設(shè)*p結(jié)點(diǎn)的值域等于其后結(jié)點(diǎn)的值域，那么刪除后者。對(duì)應(yīng)的算法如下：voiddels(SLink*&L){ SLink*p=L->next,*q; while(p->next!=NULL) { if(p->data==p->next->data) //找到重復(fù)值的結(jié)點(diǎn) { q=p->next; //q指向這個(gè)重復(fù)值的結(jié)點(diǎn) p->next=q->next; //刪除*q結(jié)點(diǎn) free(q); } elsep=p->next; }}本算法的時(shí)間復(fù)雜度為O(n)?！?0〕有一個(gè)雙鏈表L，設(shè)計(jì)一個(gè)算法查找第一個(gè)元素值為x的結(jié)點(diǎn)，將其與后繼結(jié)點(diǎn)進(jìn)展交換。解：先找到第一個(gè)元素值為x的結(jié)點(diǎn)*p，q指向其后繼結(jié)點(diǎn)，此題是將*p結(jié)點(diǎn)移到*q結(jié)點(diǎn)之后，實(shí)現(xiàn)過程是：刪除*p結(jié)點(diǎn)，再將其插入到*q結(jié)點(diǎn)之后。對(duì)應(yīng)的算法如下：intswap(DLink*L,ElemTypex){ DLink*p=L->next,*q; while(p!=NULL&&p->data!=x) p=p->next; if(p==NULL) //未找到值為x的結(jié)點(diǎn) return0; else //找到值為x的結(jié)點(diǎn)*p { q=p->next; //q指向*p的后繼結(jié)點(diǎn) if(q!=NULL) //*p結(jié)點(diǎn)不是尾結(jié)點(diǎn) { p->prior->next=q; //先刪除*p結(jié)點(diǎn) q->prior=p->prior; p->next=q->next; //將*p結(jié)點(diǎn)插入到*q結(jié)點(diǎn)之后 if(q->next!=NULL) q->next->prior=p; q->next=p; p->prior=q; return1; } else //*p結(jié)點(diǎn)是尾結(jié)點(diǎn) return0; //無法與后繼結(jié)點(diǎn)交換，返回0 }}〔11〕對(duì)于有n〔n≥1〕個(gè)數(shù)據(jù)結(jié)點(diǎn)的循環(huán)單鏈表L，設(shè)計(jì)一個(gè)算法將所有結(jié)點(diǎn)逆置。解：采用頭插法重建循環(huán)單鏈表L的思路，先建設(shè)一個(gè)空的循環(huán)單鏈表，用p遍歷所有數(shù)據(jù)結(jié)點(diǎn)，每次將*p結(jié)點(diǎn)插入到前端。對(duì)應(yīng)的算法如下：voidReverse(SLink*&L){ SLink*p=L->next,*q; L->next=L; //建設(shè)一個(gè)空循環(huán)單鏈表 while(p!=L) { q=p->next; p->next=L->next; //將*p結(jié)點(diǎn)插入到前端 L->next=p; p=q; }}上機(jī)實(shí)驗(yàn)題2有兩個(gè)整數(shù)集合采用有序單鏈表存儲(chǔ)，設(shè)計(jì)盡可能高效的算法求兩個(gè)集合的并集、交集和差集。并用相關(guān)數(shù)據(jù)進(jìn)展測(cè)試。#include<stdio.h>#include"SLink.h"voidUnion(SLink*L1,SLink*L2,SLink*&L3) //求并集{ SLink*p,*q,*s,*tc; L3=(SLink*)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next; while(p!=NULL&&q!=NULL) { if(p->data<q->data) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } elseif(p->data>q->data) { s=(SLink*)malloc(sizeof(SLink)); s->data=q->data; tc->next=s; tc=s; q=q->next; } else { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; q=q->next; } } while(p!=NULL) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } while(q!=NULL) { s=(SLink*)malloc(sizeof(SLink)); s->data=q->data; tc->next=s; tc=s; q=q->next; } tc->next=NULL;}voidInterSection(SLink*L1,SLink*L2,SLink*&L3) //求交集{ SLink*p,*q,*s,*tc; L3=(SLink*)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next; while(p!=NULL&&q!=NULL) { if(p->data<q->data) p=p->next; elseif(p->data>q->data) q=q->next; else //p->data=q->data { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; q=q->next; } } tc->next=NULL;}voidSubs(SLink*L1,SLink*L2,SLink*&L3) //求差集{ SLink*p,*q,*s,*tc; L3=(SLink*)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next; while(p!=NULL&&q!=NULL) { if(p->data<q->data) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } elseif(p->data>q->data) q=q->next; else //p->data=q->data { p=p->next; q=q->next; } } while(p!=NULL) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } tc->next=NULL;}voidmain(){ SLink*A,*B,*C,*D,*E; ElemTypea[]={1,3,6,8,10,20}; CreateListR(A,a,6); //尾插法建表 printf("集合A:");DispList(A); ElemTypeb[]={2,5,6,10,16,20,30}; CreateListR(B,b,7); //尾插法建表 printf("集合B:");DispList(B); printf("求A、B并集C\n"); Union(A,B,C); //求A、B并集C printf("集合C:");DispList(C); printf("求A、B交集C\n"); InterSection(A,B,D); //求A、B并集D printf("集合D:");DispList(D); printf("求A、B差集E\n"); Subs(A,B,E); //求A、B差集E printf("集合E:");DispList(E); DestroyList(A); DestroyList(B); DestroyList(C); DestroyList(D); DestroyList(E);}練習(xí)題31.單項(xiàng)選擇題〔1〕棧中元素的進(jìn)出原那么是〔〕。A.先進(jìn)先出 B.后進(jìn)先出C.?？漳敲催M(jìn)D.棧滿那么出答：B〔2〕設(shè)一個(gè)棧的進(jìn)棧序列是A、B、C、D〔即元素A～D依次通過該?！常敲唇柚摋Ｋ玫降妮敵鲂蛄胁豢赡苁恰病?。A.A,B,C,D B.D,C,B,AC.A,C,D,B D.D,A,B,C答：D〔3〕一個(gè)棧的進(jìn)棧序列是a、b、c、d、e，那么棧的不可能的輸出序列是〔〕。A.edcba B.decba C.dceab D.abcde答：C〔4〕一個(gè)棧的進(jìn)棧序列是1，2，3，…，n，其輸出序列的第一個(gè)元素是i〔1≤i≤n〕那么第j〔1≤j≤n〕個(gè)出棧元素是〔〕。A.i B.n-iC.j-i+1D.不確定答：D〔5〕設(shè)順序棧st的棧頂指針top的初始時(shí)為-1，?？臻g大小為MaxSize，那么判定st棧為棧空的條件為〔〕。A.st.top==-1 B.st.top!=-1C.st.top!=MaxSize D.st.top==MaxSize答：A〔6〕設(shè)順序棧st的棧頂指針top的初始時(shí)為-1，棧空間大小為MaxSize，那么判定st棧為棧滿的條件是。A.st.top!=-1B.st.top==-1C.st.top!=MaxSize-1 D.st.top==MaxSize-1答：D〔7〕隊(duì)列中元素的進(jìn)出原那么是〔〕。A.先進(jìn)先出B.后進(jìn)先出C.?？漳敲催M(jìn)D.棧滿那么出答：A〔8〕元素A、B、C、D順序連續(xù)進(jìn)入隊(duì)列qu后，隊(duì)頭元素是〔①〕，隊(duì)尾元素是〔②〕。A.A B.BC.C D.D答：①A②D。〔9〕一個(gè)隊(duì)列的入列序列為1234，那么隊(duì)列可能的輸出序列是〔〕。A.4321 B.1234C.1432 D.3241答：B〔10〕循環(huán)隊(duì)列qu〔隊(duì)頭指針front指向隊(duì)首元素的前一位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置〕的隊(duì)滿條件是〔〕。A.(qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB.(qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontA.qu.rear==qu.front答：C〔11〕循環(huán)隊(duì)列qu〔隊(duì)頭指針front指向隊(duì)首元素的前一位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置〕的隊(duì)空條件是〔〕。A.(qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB.(qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontD.qu.rear==qu.front答：D〔12〕設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)是0～N-1，其頭尾指針分別為f和r〔隊(duì)頭指針f指向隊(duì)首元素的前一位置，隊(duì)尾指針r指向隊(duì)尾元素的位置〕，那么其元素個(gè)數(shù)為〔〕。A.r-f B.r-f-1C.(r-f)％N+1 D.(r-f+N)％N答：D〔13〕設(shè)有4個(gè)數(shù)據(jù)元素a、b、c和d，對(duì)其分別進(jìn)展棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按a、b、c、d次序每次進(jìn)入一個(gè)元素。假設(shè)?；蜿?duì)的初始狀態(tài)都是空?，F(xiàn)要進(jìn)展的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是〔①〕，第二次出棧得到的元素是〔②〕；類似地，考慮對(duì)這4個(gè)數(shù)據(jù)元素進(jìn)展的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是〔③〕，第二次出隊(duì)得到的元素是〔④〕。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有〔⑤〕個(gè)。①～④：A.a B.b C.c D.d⑤： A.1 B.2 C.3 D.0答：①B②D③A④B⑤B〔14〕設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1～e6依次通過棧S，一個(gè)元素出后即進(jìn)隊(duì)列Q，假設(shè)6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5、e1，那么棧S的容量至少應(yīng)該是〔〕。A.5 B.4 C.3 D.2答：C2.填空題〔1〕棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為〔①〕。不允許插入和刪除運(yùn)算的一端稱為〔②〕。答：①棧頂②棧底〔2〕一個(gè)棧的輸入序列是12345，的輸出序列為12345，其進(jìn)棧出棧的操作為〔〕。答：1進(jìn)棧，1出棧，2進(jìn)棧，2出棧，3進(jìn)棧，3出棧，4進(jìn)棧，4出棧，5進(jìn)棧，5出棧。〔3〕有5個(gè)元素，其進(jìn)棧次序?yàn)锳、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先出?！布碈第一個(gè)且D第二個(gè)出?！车拇涡蛴小病场４穑篊DBAE、CDEBA、CDBEA?！?〕順序棧用data[0..n-1]存儲(chǔ)數(shù)據(jù)，棧頂指針為top，其初始值為0，那么元素x進(jìn)棧的操作是〔〕。答：data[top]=x;top++;〔5〕順序棧用data[0..n-1]存儲(chǔ)數(shù)據(jù)，棧頂指針為top，其初始值為0，那么出棧元素x的操作是〔〕。答：top--;x=data[top];〔6〕〔〕是被限定為只能在表的一端進(jìn)展插入運(yùn)算，在表的另一端進(jìn)展刪除運(yùn)算的線性表。答：隊(duì)列〔7〕設(shè)有數(shù)組A[0..m]作為循環(huán)隊(duì)列的存儲(chǔ)空間，front為隊(duì)頭指針〔它指向隊(duì)首元素的前一位置〕，rear為隊(duì)尾指針〔它指向隊(duì)尾元素的位置〕，那么元素x執(zhí)行入隊(duì)的操作是〔〕。答：rear=(rear+1)%(m+1);A[rear]=x;〔8〕設(shè)有數(shù)組A[0..m]作為循環(huán)隊(duì)列的存儲(chǔ)空間，front為隊(duì)頭指針〔它指向隊(duì)首元素的前一位置〕，rear為隊(duì)尾指針〔它指向隊(duì)尾元素的位置〕，那么元素出隊(duì)并保存到x中的操作是〔〕。答：front=(front+1)%(m+1);x=A[rear];3.簡(jiǎn)答題〔1〕簡(jiǎn)要說明線性表、棧與隊(duì)的異同點(diǎn)。答：一樣點(diǎn)：都屬地線性構(gòu)造，都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：①運(yùn)算規(guī)那么不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)展插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)展插入、另一端進(jìn)展刪除運(yùn)算，因而是先進(jìn)先出表FIFO。②用途不同，棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)等，隊(duì)列用于多道作業(yè)處理、指令存放及其他運(yùn)算等等。〔2〕順序隊(duì)的“假溢出〞是怎樣產(chǎn)生的如何知道循環(huán)隊(duì)列是空還是滿答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有進(jìn)隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出〞。采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決循環(huán)隊(duì)列是空還是滿的方法如下：①設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；②浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。③使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)〔即隊(duì)列長(zhǎng)度〕。通常采用法②，讓隊(duì)頭指針front指向隊(duì)首元素的前一位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置，這樣判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是：front=rear，隊(duì)滿標(biāo)志是：(rear+1)%MaxSize=front。4.算法設(shè)計(jì)題〔1〕假設(shè)采用順序棧存儲(chǔ)構(gòu)造，設(shè)計(jì)一個(gè)算法，利用棧的基本運(yùn)算返回指定棧中棧底元素，要求仍保持棧中元素不變。這里只能使用棧st的基本運(yùn)算來完成，不能直接用st.data[0]來得到棧底元素。解：假定采用順序棧構(gòu)造。先退棧st中所有元素，利用一個(gè)臨時(shí)棧tmpst存放從st棧中退棧的元素，最后的一個(gè)元素即為所求，然后將臨時(shí)棧tmpst中的元素逐一出棧并進(jìn)棧到st中，這樣恢復(fù)st棧中原來的元素。對(duì)應(yīng)算法如下：intGetBottom(SqStackst,ElemType&x){ ElemTypee;SqStacktmpst; //定義臨時(shí)棧 InitStack(tmpst); //初始化臨時(shí)棧 if(StackEmpty(st)) //空棧返回0 return0; while(!StackEmpty(st)) //臨時(shí)棧tmpst中包含st棧中逆轉(zhuǎn)元素 { Pop(st,x); Push(tmpst,x); } while(!StackEmpty(tmpst)) //恢復(fù)st棧中原來的內(nèi)容 { Pop(tmpst,e); Push(st,e); } return1; //返回1表示成功}〔2〕設(shè)計(jì)一個(gè)算法，采用一個(gè)順序棧逆向輸出單鏈表L中所有元素。解：此題并不需要改變單鏈表L的構(gòu)造。設(shè)置一個(gè)順序棧st，先遍歷單鏈表并將所有元素進(jìn)棧，然后棧不空循環(huán)并輸出棧中所有元素。對(duì)應(yīng)算法如下：voidReverseDisp(SLink*L){ ElemTypex; structnode { ElemTypedata[MaxSize]; inttop; }st; //定義一個(gè)順序棧 st.top=-1;SLink*p=L->next; while(p!=NULL) //遍歷單鏈表，將所有元素進(jìn)棧 { st.top++; st.data[st.top]=p->data; p=p->next; } while(st.top!=-1) //棧不空循環(huán)，輸出棧中所有元素 { x=st.data[st.top]; st.top--; printf("%d",x); } printf("\n");}〔3〕設(shè)計(jì)一個(gè)循環(huán)隊(duì)列，用front和rear分別作為隊(duì)頭和隊(duì)尾指針，另外用一個(gè)標(biāo)志tag標(biāo)識(shí)隊(duì)列可能空〔0〕或可能滿〔1〕，這樣加上front==rear可以作為隊(duì)空或隊(duì)滿的條件。要求設(shè)計(jì)隊(duì)列的相關(guān)基本運(yùn)算算法。解：設(shè)計(jì)的隊(duì)列的類型如下：typedefstruct{ ElemTypedata[MaxSize]; intfront,rear; //隊(duì)頭和隊(duì)尾指針 inttag; //為0表示隊(duì)空,為1時(shí)表示不空}QueueType;初始時(shí)tag=0，進(jìn)展成功的插入操作后tag=1，進(jìn)展成功的刪除操作后tag=0；因?yàn)橹挥性诓迦氩僮骱箨?duì)列才有可能滿，只有在刪除操作后隊(duì)列才有可能空，因此，這樣的隊(duì)列的基本要素如下：初始時(shí)：tag=0，front=rear隊(duì)空條件：qu.front==qu.rear&&qu.tag==0隊(duì)滿條件：qu.front==qu.rear&&qu.tag==1對(duì)應(yīng)的算法如下：//-----初始化隊(duì)列算法-----voidInitQueue1(QueueType&qu){ qu.front=qu.rear=0; qu.tag=0; //為0表示隊(duì)空可能為空}//-----判隊(duì)空算法-----intQueueEmpty1(QueueTypequ){ return(qu.front==qu.rear&&qu.tag==0);}//-----判隊(duì)滿算法-----intQueueFull1(QueueTypequ){ return(qu.tag==1&&qu.front==qu.rear);}//-----進(jìn)隊(duì)算法-----intenQueue1(QueueType&qu,ElemTypex){ if(QueueFull1(qu)==1) //隊(duì)滿 return0; qu.rear=(qu.rear+1)%MaxSize;qu.data[qu.rear]=x;qu.tag=1; //至少有一個(gè)元素,可能滿 return1;}//-----出隊(duì)算法-----intdeQueue1(QueueType&qu,ElemType&x)//出隊(duì){ if(QueueEmpty1(qu)==1) //隊(duì)空 return0; qu.front=(qu.front+1)%MaxSize;x=qu.data[qu.front];qu.tag=0; //出隊(duì)一個(gè)元素,可能空 return1;}〔4〕假設(shè)用一個(gè)循環(huán)單鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針rear指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，設(shè)計(jì)出相應(yīng)的隊(duì)初始化、進(jìn)隊(duì)、出隊(duì)和判隊(duì)空的算法。解：假設(shè)鏈隊(duì)是不帶頭結(jié)點(diǎn)的循環(huán)單鏈表，其示意圖如圖3.1所示。隊(duì)空條件：rear==NULL；進(jìn)隊(duì)操作：在*rear結(jié)點(diǎn)之后插入結(jié)點(diǎn)并讓rear指向該結(jié)點(diǎn)；出隊(duì)操作：刪除*rear結(jié)點(diǎn)之后的一個(gè)結(jié)點(diǎn)。對(duì)應(yīng)的算法如下：圖3.1不帶頭結(jié)點(diǎn)的循環(huán)單鏈表表示隊(duì)列typedefstructnode{ ElemTypedata; structnode*next;}QNode; //鏈隊(duì)結(jié)點(diǎn)類型//-----初始化隊(duì)列-----voidInitQueue(QNode*&rear){ rear=NULL;}//-----進(jìn)隊(duì)算法-----voidEnQueue(QNode*&rear,ElemTypex){ QNode*s; s=(QNode*)malloc(sizeof(QNode));//創(chuàng)立新結(jié)點(diǎn) s->data=x; if(rear==NULL) //原鏈隊(duì)為空 { s->next=s; //構(gòu)成循環(huán)鏈表 rear=s; } else { s->next=rear->next; //將*s結(jié)點(diǎn)插入到*rear結(jié)點(diǎn)之后 rear->next=s; rear=s; //讓rear指向這個(gè)新插入的結(jié)點(diǎn) }}//-----出隊(duì)算法-----intDeQueue(QNode*&rear,ElemType&x){ QNode*q; if(rear==NULL) //隊(duì)空 return0; elseif(rear->next==rear) //原隊(duì)中只有一個(gè)結(jié)點(diǎn) { x=rear->data; free(rear); rear=NULL; } else //原隊(duì)中有兩個(gè)或以上的結(jié)點(diǎn) { q=rear->next; x=q->data; rear->next=q->next; free(q); } return1;}//-----判隊(duì)空算法-----intQueueEmpty(QNode*rear){ return(rear==NULL);}上機(jī)實(shí)驗(yàn)題3假設(shè)以I和O字符分別表示進(jìn)棧和出棧操作，棧的初態(tài)和終棧均為空，進(jìn)棧和出棧的操作序列可表示為僅由I和O組成的序列。如IOIIOIOO序列是合法的，而IOOIOIIO序列是不合法的。設(shè)計(jì)一個(gè)算法判定所給的操作序列是否合法。假設(shè)合法返回1；否那么返回0?！布僭O(shè)被判定的操作序列已存入一維數(shù)組中〕。并用相關(guān)數(shù)據(jù)進(jìn)展測(cè)試。解：采用一個(gè)鏈棧來判斷操作序列是否合法，其中str為存放操作序列的字符數(shù)組，n為該數(shù)組的元素個(gè)數(shù)〔這里的ElemType類型設(shè)定為char〕。對(duì)應(yīng)的算法如下：#include<stdio.h>#include<malloc.h>typedefstructnode{ chardata; structnode*next;}LStack; //鏈棧結(jié)點(diǎn)類型voidInitStack(LStack*&ls) //初始化棧運(yùn)算算法{ ls=NULL;}voidDestroyStack(LStack*&ls) //銷毀棧運(yùn)算算法{ LStack*pre=ls,*p; if(pre==NULL)return; //考慮空棧的情況 p=pre->next; while(p!=NULL) { free(pre); //釋放*pre結(jié)點(diǎn) pre=p;p=p->next; //pre、p同步后移 } free(pre); //釋放尾結(jié)點(diǎn)}voidPush(LStack*&ls,charx) //進(jìn)棧運(yùn)算算法{ LStack*p; p=(LStack*)malloc(sizeof(LStack)); p->data=x; //創(chuàng)立結(jié)點(diǎn)*p用于存放x p->next=ls; //插入*p結(jié)點(diǎn)作為棧頂結(jié)點(diǎn) ls=p;}intPop(LStack*&ls,char&x) //出棧運(yùn)算算法{ LStack*p; if(ls==NULL) //?？?下溢出返回0 return0; else //棧不空時(shí)出棧元素x并返回1 { p=ls; //p指向棧頂結(jié)點(diǎn) x=p->data; //取棧頂元素x ls=p->next; //刪除結(jié)點(diǎn)*p free(p); //釋放*p結(jié)點(diǎn) return1; }}intStackEmpty(LStack*ls) //判斷?？者\(yùn)算算法{ if(ls==NULL)return1; elsereturn0;}intjudge(charstr[],intn) //判斷str序列的合法性{ inti,tag;charx;LStack*ls; InitStack(ls); //鏈棧ls初始化 for(i=0;i<n;i++) { if(str[i]=='I') //為I時(shí)進(jìn)棧 Push(ls,str[i]); elseif(str[i]=='O') //為O時(shí)出棧 { if(StackEmpty(ls)) { DestroyStack(ls); return0; //棧空時(shí)返回0 } elsePop(ls,x); } else { DestroyStack(ls); return0; //其他值無效退出 } } tag=StackEmpty(ls); DestroyStack(ls); returntag; //棧為空時(shí)返回1,否那么返回0}voidmain(){ charstr1[]="IOIIOIOO"; charstr2[]="IOOIOIIO"; charstr3[]="IIIOIOIO"; charstr4[]="IIIOOIOO"; printf("各序列判斷結(jié)果如下:\n"); printf("%s序列%s合法的\n",str1,judge(str1,8)?"是":"不是"); printf("%s序列%s合法的\n",str2,judge(str2,8)?"是":"不是"); printf("%s序列%s合法的\n",str3,judge(str3,8)?"是":"不是"); printf("%s序列%s合法的\n",str4,judge(str4,8)?"是":"不是");}練習(xí)題41.單項(xiàng)選擇題〔1〕串是一種特殊的線性表，其特殊性表達(dá)在〔〕。A.可以順序存儲(chǔ) B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符答：B〔2〕以下〔〕是"abcd321ABCD"串的子串。A.abcd B.321AB C."abcABC" D."21AB"答：D〔3〕兩個(gè)串相等必有串長(zhǎng)度相等且〔〕。A.串的各位置字符任意 B.串中各對(duì)應(yīng)位置字符均相等C.兩個(gè)串含有一樣的字符 D.兩個(gè)所含字符任意答：B2.填空題〔1〕空串是指〔①〕，空白串是指〔②〕。答：①不包含任何字符〔長(zhǎng)度為0〕的串②由一個(gè)或多個(gè)空格〔僅由空格符〕組成的串〔2〕對(duì)于帶頭結(jié)點(diǎn)的鏈串s，串為空的條件是〔〕。答：s->next==NULL?！?〕對(duì)于一個(gè)含有n個(gè)字符的鏈串s，查找第i個(gè)元素的算法的時(shí)間復(fù)雜度為〔〕。答：O(n)3.簡(jiǎn)答題〔1〕設(shè)s為一個(gè)長(zhǎng)度為n的串，其中的字符各不一樣，那么s中的互異的非平凡子串〔非空且不同于s本身〕的個(gè)數(shù)是多少答：由串s的特性可知，1個(gè)字符的子串有n個(gè)，2個(gè)字符的子串有n-1個(gè)，3個(gè)字符的子串有n-2個(gè)，…，n-2個(gè)字符的子串有3個(gè)，n-1個(gè)字符的子串有2個(gè)。所以，非平凡子串的個(gè)數(shù)=n+(n-1)+(n-2)+…+2=?！?〕假設(shè)s1和s2為串，給出使s1//s2=s2//s1成立的所有可能的條件〔其中，“//〞表示兩個(gè)串連接運(yùn)算符〕。答：所有可能的條件為：〔1〕s1和s2為空串〔2〕s1或s2其中之一為空串〔3〕s1和s2為一樣的串〔4〕假設(shè)兩串長(zhǎng)度不等，那么長(zhǎng)串由整數(shù)個(gè)短串組成。4.算法設(shè)計(jì)題〔1〕設(shè)計(jì)一個(gè)算法RepChar(s,x,y)，將順序串s中所有字符x替換成字符y。要求空間復(fù)雜度為O(1)。解：因要求算法空間復(fù)雜度為O(1)，所以只能對(duì)串s直接替換。從頭開場(chǎng)遍歷串s，一旦找到字符x便將其替換成y。對(duì)應(yīng)算法如下：voidRepStr(SqString&s,charx,chary){ inti; for(i=0;i<s.length;i++) if(s.data[i]==x) s.data[i]=y;}〔2〕設(shè)計(jì)一個(gè)算法，判斷鏈串s中所有元素是否為遞增排列的。解：用p和q指向鏈串s的兩個(gè)連續(xù)結(jié)點(diǎn)，p先指向開場(chǎng)結(jié)點(diǎn)，當(dāng)q->data≥p->data時(shí)，p和q同步后移一個(gè)結(jié)點(diǎn)；否那么返回0。當(dāng)所有元素是遞增排列時(shí)返回1。對(duì)應(yīng)算法如下：intincrease(LinkString*s){ LinkString*p=s->next,*q; if(p!=NULL) { while(p->next!=NULL) { q=p->next; //q指向*p的后續(xù)結(jié)點(diǎn) if(q->data>=p->data) p=q; else //逆序時(shí)返回0 return0; } } return1;}〔3〕假設(shè)以鏈?zhǔn)綐?gòu)造存儲(chǔ)一個(gè)串s，設(shè)計(jì)一個(gè)算法求串s中最長(zhǎng)等值子串。解：假設(shè)串用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)串s。用max存放最大平臺(tái)長(zhǎng)度，掃描串s，計(jì)算一個(gè)平臺(tái)的長(zhǎng)度n，假設(shè)n大于max，那么置max為n。對(duì)應(yīng)的算法如下：intmaxlength(LinkString*s){ intn,max=0;LinkString*p=s->next,*q; while(p!=NULL) { n=1; q=p;p=p->next; while(p!=NULL&&p->data==q->data) { n++; p=p->next; } if(n>max)max=n; } returnmax;}上機(jī)實(shí)驗(yàn)題4兩個(gè)非空串s和t采用順序存儲(chǔ)構(gòu)造存儲(chǔ)，設(shè)計(jì)一個(gè)算法求這兩個(gè)串最大公共子串，并用相關(guān)數(shù)據(jù)進(jìn)展測(cè)試。解：采用Index算法思路設(shè)計(jì)由順序串s、t產(chǎn)生最大公共子串str。對(duì)應(yīng)的程序如下：#include<stdio.h>#include"SqString.h" //包含順序串的基本運(yùn)算函數(shù)SqStringmaxcomstr(SqStrings,SqStringt){ SqStringstr; intmidx=0,mlen=0,tlen,i=0,j,k; //用(midx,mlen)保存最大公共子串 while(i<s.length) //用i掃描串s { j=0; //用j掃描串t while(j<t.length) { if(s.data[i]==t.data[j]) //找一子串,在s中下標(biāo)為i,長(zhǎng)度為tlen { tlen=1; for(k=1;i+k<s.length&&j+k<t.length &&s.data[i+k]==t.data[j+k];k++) tlen++; if(tlen>mlen) //將較大長(zhǎng)度者賦給midx與mlen { midx=i; mlen=tlen; } j+=tlen; //繼續(xù)掃描t中第j+tlen字符之后的字符 } elsej++; } i++; //繼續(xù)掃描s中第i字符之后的字符 } for(i=0;i<mlen;i++) //將最大公共子串復(fù)制到str中 str.data[i]=s.data[midx+i]; str.length=mlen; returnstr; //返回最大公共子串}voidmain(){ SqStrings,t,str; Assign(s,"aababcabcdabcde"); Assign(t,"aabcd"); printf("s:");DispStr(s); printf("t:");DispStr(t); printf("求s、t的最大公共子串str\n"); str=maxcomstr(s,t); printf("str:");DispStr(str);}練習(xí)題51.單項(xiàng)選擇題〔1〕假設(shè)有60行70列的二維數(shù)組a[1..60,1..70]〔數(shù)組下標(biāo)從1開場(chǎng)〕以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a[32,58]的存儲(chǔ)地址為〔〕。A.16902 B.16904 C.14454D.以上都不對(duì)答：A〔2〕對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了〔〕。A.表達(dá)變得簡(jiǎn)單 B.對(duì)矩陣元素的存取變得簡(jiǎn)單C.去掉矩陣中的多余元素 D.減少不必要的存儲(chǔ)空間答：D〔3〕一個(gè)n×n的對(duì)稱矩陣，如果采用壓縮存儲(chǔ)以行或列為主序放入內(nèi)存，那么壓縮存儲(chǔ)的容量是〔〕。A.n2 B.n2/2 C.n(n+1)/2 D.(n+1)2/2答：C〔4〕設(shè)矩陣a是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角局部按行序存放在一維數(shù)組b[1..n(n-1)/2]中〔數(shù)組下標(biāo)均從1開場(chǎng)〕，對(duì)下三角局部中任一元素ai,j〔i≤j〕在一維數(shù)組b中下標(biāo)k的值是〔〕。A.i(i-1)/2+j-1 B.i(i-1)/2+j C.i(i+1)/2+j-1 D.i(i+1)/2+j答：B〔5〕有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是0～8，列下標(biāo)的范圍是1～5，每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址。假設(shè)存儲(chǔ)數(shù)組元素A[0,1]的第一個(gè)字節(jié)的地址是0。存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是〔①〕。假設(shè)按行存儲(chǔ)，那么A[3,5]和A[5,3]的第一個(gè)字節(jié)的地址分別是〔②〕和〔③〕。假設(shè)按列存儲(chǔ)，那么A[7,1]和A[2,4]的第一個(gè)字節(jié)的地址分別是〔④〕和〔⑤〕。A.28B.44C.76D.92E.108F.116G.132H.176I.184J.188答：①H②C③E④A⑤F〔6〕有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1～6，列下標(biāo)的范圍是0～7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是〔①〕個(gè)字節(jié)。假設(shè)存儲(chǔ)數(shù)組元素A[1,0]的第一個(gè)字節(jié)的地址是0，那么存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是〔②〕。假設(shè)按行存儲(chǔ)，那么A[2,4]的第一個(gè)字節(jié)的地址是〔③〕。假設(shè)按列存儲(chǔ)，那么A[5,7]的第一個(gè)字節(jié)的地址是〔④〕。A.12 B.66 C.72 D.96 E.114 F.120G.156 H.234I.276J.282K.283L.288答：①L②J③C④I〔7〕稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即〔〕。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表答：C2.填空題〔1〕三維數(shù)組A[c1..d1,c2..d2,c3..d3]〔c1≤d1，c2≤d2，c3≤d3〕共含有〔〕個(gè)元素。答：(d1-c1+1)×(d2-c2+1)×(d3-c3+1)?！?〕二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A[0][0])，那么A[i][j]的地址是〔〕。答：LOC(A[0][0])+(n×i+j)×k?！?〕二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且A[0][0]的存儲(chǔ)地址是200，那么A[6][12]的地址是〔〕。答：326〔4〕二維數(shù)組A[10..20][5..10]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A[10][5]的存儲(chǔ)地址是1000，那么A[18][9]的地址是〔〕。答：1208〔5〕有一個(gè)10階對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式〔以行序?yàn)橹鞔鎯?chǔ)下三角局部，且A[0][0]存放在B[1]中〕，那么A[8][5]在B中的地址是〔〕。答：42〔6〕設(shè)n階下三角矩陣A[1..n][1..n]已壓縮到一維數(shù)組S[1..n(n+1)/2]中，假設(shè)按行序?yàn)橹鞔鎯?chǔ)，那么A[i][j]對(duì)應(yīng)的S中的存儲(chǔ)位置是〔〕。答：i(i-1)/2+j?！?〕稀疏矩陣的三元組表示中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的〔〕。答：行下標(biāo)、列下標(biāo)和元素值3.算法設(shè)計(jì)題〔1〕假定數(shù)組A[0..n-1]的n個(gè)元素中有多個(gè)零元素，設(shè)計(jì)一個(gè)算法將A中所有的非零元素依次移到A的前端。解：從前向后找為零的元素A[i]，從后向前找非零的元素A[j]，將A[i]和A[j]進(jìn)展交換。對(duì)應(yīng)的算法如下：voidmove(ElemTypeA[],intn){ inti=0,j=n-1; ElemTypetmp;while(i<j) { while(A[i]!=0)i++; while(A[j]==0)j--; if(i<j) { tmp=A[i]; A[i]=A[j]; A[j]=tmp; } }}〔2〕一個(gè)n×n矩陣B按行優(yōu)先存于一個(gè)一維數(shù)組A[0..n(n-1)]中，試給出一個(gè)就地算法將原矩陣轉(zhuǎn)置后仍存于數(shù)組A中。解：矩陣轉(zhuǎn)置是將矩陣中第i行第j列的元素與第j行第i列的元素互換位置。因此先應(yīng)確定矩陣與一維數(shù)組的映射關(guān)系：bi,j在一維數(shù)組A中的下標(biāo)為i～n+j，bj,i在一維數(shù)組A中的下標(biāo)為j×n+i。對(duì)應(yīng)的算法如下：voidtrans(ElemTypeA[],intn){ inti,j; ElemTypetmp; for(i=0;i<n;i++) for(j=0;j<i;j++) { tmp=A[i*n+j];A[i*n+j]=A[j*n+i]; A[j*n+i]=tmp;}}〔3〕如果矩陣A中存在這樣的一個(gè)元素A[i][j]滿足條件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，那么稱之為該矩陣的一個(gè)馬鞍點(diǎn)。設(shè)計(jì)一個(gè)算法求出m×n的矩陣A的所有馬鞍點(diǎn)。解：先求出每行的最小值元素，放入min[m]之中，再求出每列的最大值元素，放入max[n]之中，假設(shè)某元素既在min[i]中，又在max[j]中，那么該元素A[i][j]便是馬鞍點(diǎn)，找出所有這樣的元素，即找到了所有馬鞍點(diǎn)。實(shí)現(xiàn)程序如下：#include<stdio.h>#definem3#definen4voidminmax(intA[m][n]){ inti,j,have=0;intmin[m],max[n]; for(i=0;i<m;i++) //計(jì)算出每行的最小值元素，放入min[m]之中 { min[i]=A[i][0]; for(j=1;j<n;j++) if(A[i][j]<min[i]) min[i]=A[i][j]; } for(j=0;j<n;j++) //計(jì)算出每列的最大值元素，放入max[1..n]之中{ max[j]=A[0][j]; for(i=1;i<m;i++) if(A[i][j]>max[j]) max[j]=A[i][j]; } for(i=0;i<m;i++) //判定是否為馬鞍點(diǎn) for(j=0;j<n;j++) if(min[i]==max[j]) { printf("(%d,%d):%d\n",i,j,A[i][j]);//顯示馬鞍點(diǎn) have=1; } if(!have) printf("沒有鞍點(diǎn)\n");}voidmain(){ inta[m][n]; inti,j; for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); minmax(a); //調(diào)用minmax()找馬鞍點(diǎn)}〔4〕設(shè)有二維數(shù)組A[m][n]，其元素為整數(shù)，每行每列都按從小到大有序，試給出一個(gè)算法求數(shù)組中值為x的元素的行號(hào)i和列號(hào)j。設(shè)值x在A中存在，要求比較次數(shù)不多于m+n次。解：由于算法要求比較次數(shù)不多于m+n次，因此不能按行掃描數(shù)組的每一元素，否那么比較次數(shù)在最壞情況下可達(dá)m×n次。根據(jù)該數(shù)組的特點(diǎn)可從矩陣右上角按副對(duì)角線方向向左下角查找，算法如下：intfind(inta[M][N],intx,intm,intn){ inti=0,j=n-1,flag=0;while(i<m&&j>=0) if(a[i][j]!=x) if(a[i][j]>x)j--; //修改列號(hào) elsei++; //修改行號(hào) else //a[i][j]==x { flag=1; break; } returnflag;}上機(jī)實(shí)驗(yàn)題5采用一維動(dòng)態(tài)數(shù)組模擬二維數(shù)組的操作，即將一個(gè)二維數(shù)組的元素存放在一個(gè)一維數(shù)組中，一維數(shù)組的空間根據(jù)二維數(shù)組的大小動(dòng)態(tài)分配。設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)兩個(gè)二維數(shù)組的相加運(yùn)算。并用相關(guān)數(shù)據(jù)進(jìn)展測(cè)試。解：對(duì)應(yīng)的程序如下：#include<stdio.h>#include<malloc.h>typedefintElemType;typedefstruct{ ElemType*p; //存放二維數(shù)組元素 intm,n; //存放二維數(shù)組的行數(shù)和列數(shù)}Mat2;voidInitMat(Mat2&M,intx,inty) //初始化二維數(shù)組M{ M.m=x;M.n=y; M.p=(ElemType*)malloc(x*y*sizeof(ElemType));}intSetij(Mat2&M,inti,intj,ElemTypex) //置二維數(shù)組(i,j)位置值為x{ intk; if(i>=0&&i<M.m&&j>=0&&j<M.n) { k=i*M.n+j; M.p[k]=x; return1; //成功賦值返回1 } elsereturn0; //參數(shù)錯(cuò)誤返回0}intGetij(Mat2M,inti,intj,ElemType&x) //取二維數(shù)組(i,j)位置值并賦給x{ intk; if(i>=0&&i<M.m&&j>=0&&j<M.n) { k=i*M.n+j;x=M.p[k]; return1; //成功取值返回1 } elsereturn0; //參數(shù)錯(cuò)誤返回0}voidDispMat(Mat2M) //輸出二維數(shù)組{ inti,j,k; for(i=0;i<M.m;i++){ for(j=0;j<M.n;j++) { k=i*M.n+j; printf("%3d",M.p[k]); } printf("\n"); }}intAddMat(Mat2A,Mat2B,Mat2&C) //兩個(gè)二維數(shù)組相加運(yùn)算{ inti,j;ElemTypex,y; if(A.m!=B.m||A.n!=B.n) return0; //兩數(shù)組行列數(shù)不同返回0 for(i=0;i<A.m;i++) for(j=0;j<A.n;j++) { Getij(A,i,j,x);Getij(B,i,j,y); Setij(C,i,j,x+y);} return1;}voidDestroyMat(Mat2M) //銷毀二維數(shù)組M{ free(M.p);}voidmain(){ Mat2A,B,C; InitMat(A,2,3); Setij(A,0,0,1);Setij(A,0,1,1);Setij(A,0,2,1); Setij(A,1,0,1);Setij(A,1,1,1);Setij(A,1,2,1);printf("A:\n");DispMat(A);InitMat(B,2,3); Setij(B,0,0,2);Setij(B,0,1,2);Setij(B,0,2,2); Setij(B,1,0,2);Setij(B,1,1,2);Setij(B,1,2,2);printf("B:\n");DispMat(B); InitMat(C,2,3);printf("C=A+B\n");AddMat(A,B,C); printf("C:\n");DispMat(C); DestroyMat(A); DestroyMat(B); DestroyMat(C);}練習(xí)題61.單項(xiàng)選擇題〔1〕樹最適合用來表示〔〕。A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素C.元素之間具有層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)答：C〔2〕樹是結(jié)點(diǎn)的有限集合，它〔①〕根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m〔m≥0〕個(gè)〔②〕的集合T1、T2、…、Tm，每個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為Ti的雙親結(jié)點(diǎn)，Ti稱為T的子樹〔1≤i≤m〕。一個(gè)結(jié)點(diǎn)的子