【正文】 (SLink *)malloc(sizeof(SLink))。B){ SLink *p=Anext,*ra,*rb。對(duì)應(yīng)的算法如下：void Split(SLink *amp。解：采用重新單鏈表的方法，由于要保持相對(duì)次序，所以采用尾插法建立新表A、B。 } return 1。 //pre、p同步后移 p=pnext。 //pre指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn) p=prenext。若有一個(gè)不成立，則整個(gè)鏈表便不是遞增的；否則是遞增的。 //未找到值為x的結(jié)點(diǎn)}（5）設(shè)計(jì)一個(gè)算法判定單鏈表L是否是遞增的。 return 1。 } if (q!=NULL) //找到值為x的結(jié)點(diǎn) { pnext=qnext。 qdata!=x) { p=q。 //p指向*q的前驅(qū)結(jié)點(diǎn) while (q!=NULL amp。對(duì)應(yīng)的算法如下：int delx(SLink *amp。（4）設(shè)計(jì)一個(gè)算法刪除單鏈表L中第一個(gè)值為x的結(jié)點(diǎn)。 //順序表長(zhǎng)度置新值}本算法是一個(gè)高效算法，其時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。 e=[i]。i++) { if ([i]!=e) //只保存不重復(fù)的元素 { [k]=[i]。 for (i=1。 //k保存不重復(fù)的元素個(gè)數(shù) ElemType e。對(duì)應(yīng)的算法如下：void delsame1(SqList amp。（3）設(shè)計(jì)一個(gè)算法從有序順序表中刪除重復(fù)的元素，并使剩余元素間的相對(duì)次序保持不變。 } } =j+1。 if (kj) //[i][0..j]中所有元素都不相同 { j++。amp。i++) { k=0。 for (i=1。對(duì)應(yīng)的算法如下：void delsame(SqList amp。解：對(duì)于順序表L，用i從1開(kāi)始遍歷其元素，[0..j]（j的初值為0）中沒(méi)有重復(fù)的元素。 }}本算法的時(shí)間復(fù)雜度為O(n)。 //[i][]交換 [i]=[]。i。 ElemType x。對(duì)應(yīng)的算法如下：void reverse(SqList amp。4. 算法設(shè)計(jì)題（1）設(shè)計(jì)一個(gè)高效算法，將順序表的所有元素逆置，要求算法空間復(fù)雜度為O(1)。在僅有尾指針的循環(huán)單鏈表中，通過(guò)該尾指針可以直接找到第一個(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é)點(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)。（5）某含有n（n1）結(jié)點(diǎn)的線性表中，最常用的操作是在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則采用以下哪種存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。對(duì)于單鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)時(shí)，需修改前一結(jié)點(diǎn)的next域，新插入結(jié)點(diǎn)的next域。（4）對(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域。（2）對(duì)于表長(zhǎng)為n的順序表，在任何位置上插入或刪除一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需要移動(dòng)的元素的平均個(gè)數(shù)為多少？刪除一個(gè)元素所需要移動(dòng)的平均個(gè)數(shù)為多少？答：插入一個(gè)元素所需要移動(dòng)的元素的平均個(gè)數(shù)為(n1)/2，刪除一個(gè)元素所需要移動(dòng)的平均個(gè)數(shù)為n/2。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。在什么情況下用順序表比鏈表好？答：順序存儲(chǔ)結(jié)構(gòu)中，相鄰數(shù)據(jù)元素的存放地址也相鄰，并要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。答：①前驅(qū)結(jié)點(diǎn)的地址 ②O(n)（8）含有n（n1）個(gè)結(jié)點(diǎn)的循環(huán)雙向鏈表中，為空的指針域數(shù)為（ ）。答：①一定 ②不一定（6）在帶頭結(jié)點(diǎn)的單鏈表中，除頭結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由（ ）指示。答：①O(1) ②隨機(jī)存?。?）順序表中邏輯上相鄰的元素的物理位置（ ① ）相鄰。答：ni+1（3）向一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1≤i≤n）時(shí)，需向前移動(dòng)（ ）個(gè)元素。 答：B（7）單鏈表的存儲(chǔ)密度（ ） 答：C2. 填空題（1）在順序表中插入或刪除一個(gè)元素時(shí)，需要平均移動(dòng)（ ① ）元素，具體移動(dòng)的元素個(gè)數(shù)與（ ② ）有關(guān)。，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針，存放結(jié)點(diǎn)值，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)答：A（5）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（ ）。（1≤i≤n）和求第i（2≤i≤n）個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)（1≤i≤n）個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）答：A（3） 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)（ ）個(gè)元素。}練習(xí)題21. 單項(xiàng)選擇題（1）數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相對(duì)順序相同并且是連續(xù)的，稱(chēng)之為（ ）。 maxs(a,n,max1,max2)。 int n=10。 } else if (a[i]max2) max2=a[i]。i++) if (a[i]max1) { max2=max1。 for (i=1。max2){ int i。對(duì)應(yīng)的程序如下：include void maxs(int a[],int n,int amp。上機(jī)實(shí)驗(yàn)題1有一個(gè)整型數(shù)組a，其中含有n個(gè)元素，設(shè)計(jì)盡可能好的算法求其中的最大元素和次大元素，并采用相關(guān)數(shù)據(jù)測(cè)試。j++) m++。i++) for (j=2*i。 for (i=1。（8）設(shè)n為問(wèn)題規(guī)模，是一個(gè)正偶數(shù)，試計(jì)算以下算法結(jié)束時(shí)m的值，并給出該算法的時(shí)間復(fù)雜度。j++) x++。i++) for (j=i+1。 for (i=1。（7）設(shè)n為問(wèn)題規(guī)模，求以下算法的時(shí)間復(fù)雜度。j) s++。i++) for (j=n。for (i=1。所以，其中循環(huán)語(yǔ)句的執(zhí)行次數(shù)為4。第4次循環(huán)：j=4，s=100。第2次循環(huán)：j=2，s=30。 sn)。} while (jn amp。do{ j=j+1。（5）分析下面程序段中循環(huán)語(yǔ)句的執(zhí)行次數(shù)。（3）設(shè)有采用二元組表示的數(shù)據(jù)邏輯結(jié)構(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)}，問(wèn)相對(duì)于關(guān)系R，哪些結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？答：該邏輯結(jié)構(gòu)為樹(shù)形結(jié)構(gòu)，其中a結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，稱(chēng)為根結(jié)點(diǎn)，b、e、g、i結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)，是終端結(jié)點(diǎn)，也稱(chēng)為葉子結(jié)點(diǎn)。（2）簡(jiǎn)述線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)的不同點(diǎn)。答：①時(shí)間 ②空間3. 簡(jiǎn)答題（1）數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型兩個(gè)概念之間有區(qū)別嗎？答：簡(jiǎn)單地說(shuō)，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素的集合。答：任意多個(gè)（7）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有四種，它們分別是 ① 、 ② 、 ③ 和 ④ 存儲(chǔ)結(jié)構(gòu)。答：①?zèng)]有 ②沒(méi)有（5）在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有 ① 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 ② 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有 ③ 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)數(shù)可以是 ④ 。答：①線性結(jié)構(gòu) ②非線性結(jié)構(gòu)（3）數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是 ① 的有限集合，R是D上的 ② 有限集合。、可移植性和可擴(kuò)充性 、確定性和有窮性、有窮性和穩(wěn)定性 、穩(wěn)定性和安全性答：B2. 填空題（1）數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 ① 、數(shù)據(jù)的 ② 和數(shù)據(jù)的 ③ 這三個(gè)方面的內(nèi)容。 答：A（5）計(jì)算機(jī)算法指的是（ ）。 答：C（3）算法分析的目的是（ ）。練習(xí)題及參考答案《數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程》練習(xí)題及參考答案練習(xí)題11. 單項(xiàng)選擇題（1）線性結(jié)構(gòu)中數(shù)據(jù)元素之間是（ ）關(guān)系。 答：D（2）數(shù)據(jù)結(jié)構(gòu)中與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。 答：C（4）算法分析的兩個(gè)主要方面是（ ）。 B. 排序方法 答：C（6）計(jì)算機(jī)算法必須具備輸入、輸出和（ ）等5個(gè)特性。答：①邏輯結(jié)構(gòu) ②存儲(chǔ)結(jié)構(gòu) ③運(yùn)算（2）數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi)，它們分別是 ① 和 ② 。答：①數(shù)據(jù)元素 ②關(guān)系（4）在線性結(jié)構(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)。答：①前驅(qū) ②1 ③后繼 ④任意多個(gè)（6）在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以是（ ）。答：①順序 ②鏈?zhǔn)?③索引 ④哈希（8）一個(gè)算法的效率可分為 ① 效率和 ② 效率。數(shù)據(jù)類(lèi)型不僅定義了一組數(shù)據(jù)元素，而且還在其上定義了一組操作。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的，樹(shù)形線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)多的，圖在結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的。（4）以下各函數(shù)是算法中語(yǔ)句的執(zhí)行頻度，n為問(wèn)題規(guī)模，給出對(duì)應(yīng)的時(shí)間復(fù)雜度：T1(n)=nlog2n1000log2nT2(n)=1000log2nT3(n)=n21000log2nT4(n)=2nlog2n1000log2n答：T1(n)=O(nlog2n)，T2(n)=O( )，T3(n)=O(n2)，T4(n)=O(nlog2n)。int j=0,s=0,n=100。 s=s+10*j。amp。答：j=0，第1次循環(huán)：j=1，s=10。第3次循環(huán)：j=3，s=60。while條件不再滿(mǎn)足。（6）執(zhí)行下面的語(yǔ)句時(shí)，語(yǔ)句s++的執(zhí)行次數(shù)為多少？int s=0。in1。j=i。答：語(yǔ)句s的執(zhí)行次數(shù)。void fun1(int n){ int x=0,i。i=n。j=n。}答：其中x++語(yǔ)句屬基本運(yùn)算語(yǔ)句，=O(n2)。void fun2(int n){ int m=0。i=n。j=n。}答：由于內(nèi)循環(huán)j的取值范圍，所以i≤n/2，則，該程序段的時(shí)間復(fù)雜度為O(n2)。解：maxs算法用于返回?cái)?shù)組a[0..n1]中的最大元素值max1和次大元素值max2，max1和max2設(shè)計(jì)為引用類(lèi)型。max1,int amp。 max1=max2=a[0]。in。 max1=a[i]。}void main(){ int a[]={1,4,10,6,8,3,5,7,9,2}。 int max1,max2。 printf(最大元素值=%d,次大元素值=%d\n,max1,max2)。 答：C（2）在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（1）的操作是（ ）。 答：B（4）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（ ）。 答：D（6）一個(gè)線性表在（ ）情況下適用于采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。答：①表中一半 ②表長(zhǎng)和該元素在表中的位置（2）向一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素（1≤i≤n+1）之前插入一個(gè)元素時(shí)，需向后移動(dòng)（ ）個(gè)元素。答：ni（4）在順序表中訪問(wèn)任意一個(gè)元素的時(shí)間復(fù)雜度均為（ ① ），因此順序表也稱(chēng)為（ ② ）的數(shù)據(jù)結(jié)構(gòu)。單鏈表中邏輯上相鄰的元素的物理位置（ ② ）相鄰。答：其前驅(qū)結(jié)點(diǎn)的鏈域的值（7）在含有n個(gè)數(shù)據(jù)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的（ ① ），其時(shí)間復(fù)雜度為（ ② ）。答：03. 簡(jiǎn)答題（1）試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。其優(yōu)點(diǎn)是存儲(chǔ)密度大，存儲(chǔ)空間利用率高；缺點(diǎn)是插入或刪除元素時(shí)不方便。其優(yōu)點(diǎn)是插入或刪除元素時(shí)很方便，使用靈活；缺點(diǎn)是存儲(chǔ)密度小，存儲(chǔ)空間利用率低。若線性表的長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表；若線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。（3）在鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：在鏈表中設(shè)置頭結(jié)點(diǎn)后，不管鏈表是否為空表，頭結(jié)點(diǎn)指針均不空，并使得對(duì)鏈表的操作（如插入和刪除）在各種情況下統(tǒng)一，從而簡(jiǎn)化了算法的實(shí)現(xiàn)過(guò)程。所以共修改4個(gè)指針。所以共修改兩個(gè)指針。①單鏈表；②僅有頭指針不帶頭結(jié)點(diǎn)的循環(huán)單鏈表；③雙鏈表；④僅有尾指針的循環(huán)單鏈表。插入結(jié)點(diǎn)需找到前驅(qū)結(jié)點(diǎn)，所以在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)，需找到尾結(jié)點(diǎn)，對(duì)應(yīng)的時(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)。因此④最節(jié)省運(yùn)算時(shí)間。解：遍歷順序表L的前半部分元素，[i]（0≤i＜），[]進(jìn)行交換。L){ int i。 for (i=0。i++) { x=[i]。 []=x。（2）設(shè)計(jì)一個(gè)算法從順序表中刪除重復(fù)的元素，并使剩余元素間的相對(duì)次序保持不變。[i]（ji），[i][0..j]中任何一個(gè)元素都不相同，[i][j+1]中。L) //L為引用型參數(shù){ int i,j=0,k。i。 while (k=j amp。 [k]!=[i]) k++。 [j]=[i]。 //順序表長(zhǎng)度置新值}本算法的時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。解：在有序順序表L中，所有重復(fù)的元素應(yīng)是相鄰存放的，用k保存不重復(fù)出