1、第第 2 2 部分部分 習(xí)題解析習(xí)題解析 第 1 章緒論 1.1選擇題 1. 算法的時間復(fù)雜度取決于（C） A）問題的規(guī)模 B） 待處理數(shù)據(jù)的初態(tài) C） A和 B 【答案】C 2.計算機算法指的是解決問題的步驟序列，它必須具備（B） 這三個特性。 A）可執(zhí)行性、可移植性、可擴充性B） 可執(zhí)行性、確定性、有窮性 C） 確定性、有窮性、穩(wěn)定性D） 易讀性、穩(wěn)定性、安全性 【答案】B 5從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）兩大類。 A）動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B）順序結(jié)構(gòu)、鏈式結(jié)構(gòu) C）線性結(jié)構(gòu)、非線性結(jié)構(gòu)D）初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu) 【答案】C 6在下面的程序段中，對 x的賦值的語句頻度為（C） for(i=0

2、;in;i+) for(j=0;j=1;i-) for(j=1;jAj+1) Aj與 Aj+1對換； A. O（n）B） O(nlog2n)C） O(n3)D） O(n2) 【答案】D 1.2填空題 2. 對 于 給 定 的 n 個 元 素 , 可 以 構(gòu) 造 出 的 邏 輯 結(jié) 構(gòu) 有 _ ， _ ， _，_四種。 【答案】（1）集合 （2）線性結(jié)構(gòu) （3）樹形結(jié)構(gòu)（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 4數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是_。 【答案】算法的時間復(fù)雜度和空間復(fù)雜度。 5. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_和_，以及它們之間的相互關(guān)系，并對與這種結(jié) 構(gòu)定義相應(yīng)的_，設(shè)計出相應(yīng)的_。 【答案】（1）邏

3、輯結(jié)構(gòu)（2）物理結(jié)構(gòu)（3）操作（運算）（4）算法。 6一個算法具有 5 個特性：_、_、_，有零個或多個輸入、 有一個或多個輸出。 【答案】（1）有窮性（2）確定性（3）可行性。 9已知如下程序段 for(i=n;i0;i-)語句 1 x=x+1;語句 2 for(j=n;j=i;j-)語句 3 y=y+1;語句 4 語句 1 執(zhí)行的頻度為_；語句 2 執(zhí)行的頻度為_；語句 3 執(zhí)行的頻度為 _；語句 4 執(zhí)行的頻度為_。 【答案】（1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2 10在下面的程序段中，對的賦值語句的頻度為_（表示為 n 的函數(shù)） for(i=0;in;i

4、+) for(j=0;ji;j+) for(k=0;kj;k+) =+delta; 數(shù)據(jù)結(jié)構(gòu)上機實驗與習(xí)題解析亱店打烊 oO 【答案】1+（1+2）+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 ， O(n3) 11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是_。 i=1; while(in) i=i*2; 【答案】log2n 12. 計算機執(zhí)行下面的語句時，語句 s的執(zhí)行次數(shù)為_。 for(i=l;i=i;j-) s; 【答案】(n+3)(n-2)/2 13. 下面程序段的時間復(fù)雜度為_。(n1) sum=1; for (i=0;sumprior=q; q-next=p;

5、p-prior-next=q; q-prior=p-prior; B） q-prior=p-prior; p-prior-next=q; q-next=p; p-prior=q-next; C） q-next=p; p-next=q; p-prior-next=q; q-next=p; D） p-prior-next=q; q-next=p; q-prior=p-prior; p-prior=q; 【答案】D 4在一個具有 n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復(fù)雜度是（ ） A）O(nlog2n）B） O(1）C） O(n）D） O(n2） 【答案】C 5 在一個以 h

6、為頭指針的單循環(huán)鏈中，p 指針指向鏈尾結(jié)點的條件是（ ） A）p-next=NULLB） p-next=h C）p-next-next=hD） p-data=-1 【答案】B 6對于一個具有 n 個結(jié)點的線性表，建立其單鏈表的時間復(fù)雜度是（） A）O(n) B） O(1) C）O(nlog2n) D） O(n2) 【答案】A 8在雙向鏈表存儲結(jié)構(gòu)中，刪除 p 所指的結(jié)點時須修改指針（） A）p-prior-next=p-nextp-next-prior=p-prior; B）p-prior=p-prior-priorp-prior-next=p; C）p-next-prior=pp-next=

7、p-next-next D）p-next=p-prior-priorp-prior=p-next-next; 【答案】A 9線性表采用鏈式存儲時，其元素地址（） A）必須是連續(xù)的B）一定是不連續(xù)的 C）部分地址是連續(xù)的D）連續(xù)與否均可 【答案】D 2.2填空題 1線性表 L=（a1，a2，an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素 - 2 - 第 2 部分 習(xí)題解析亱店打烊 oO 平均需要移動元素的個數(shù)是_。 【答案】（n-1）/2 2在單鏈表中設(shè)置頭結(jié)點的作用是_。 【答案】主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入元素和刪除第一個結(jié)點不必另作判 斷。另外，不論

8、鏈表是否為空，鏈表頭指針不變。 3線性表的順序存儲是通過 _來反應(yīng)元素之間的邏輯關(guān)系，而鏈式存儲結(jié)構(gòu)是通過 _來反應(yīng)元素之間的邏輯關(guān)系。 【答案】（1）數(shù)據(jù)元素的前后順序 （2）元素中的指針 4當對一個線性表經(jīng)常進行的是存取操作，而很少進行插入和刪除操作時，則采用_存 儲結(jié)構(gòu)最節(jié)省時間，相反當經(jīng)常進行插入和刪除操作時，則采用_存儲結(jié)構(gòu)最節(jié)省時間。 【答案】（1）順序 （2）鏈式 5對于 一個 具有 n 個結(jié)點 的單鏈 表， 在已 知的 結(jié)點 *p 后插入一個 新結(jié) 點的 時間 復(fù)雜度為 _，在給定值為 x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為_。 【答案】（1）O(1)（2）O(n) 7. 對于

9、雙向鏈表，在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共_個，單鏈表為 _個。 【答案】（1）4 （2）2 8. 循環(huán)單鏈表的最大優(yōu)點是_。 【答案】從任一結(jié)點出發(fā)都可訪問到鏈表中每一個元素。 9若要在一個不帶頭結(jié)點的單鏈表的首結(jié)點*p結(jié)點之前插入一個*s結(jié)點時，可執(zhí)行下列操作： s-next=_; p-next=s; t=p-data; p-data= _; s-data=_; 【答案】（1）p-next（2）s-data（3） t 10某線性表采用順序存儲結(jié)構(gòu)，每個元素占據(jù) 4 個存儲單元，首地址為 100，則下標為 11 的（第 12 個）元素的存儲地址為_。 【答案】144 11帶頭結(jié)點的

10、雙循環(huán)鏈表 L中只有一個元素結(jié)點的條件是_。 【答案】L-next-next=L 2.3判斷題 1取線性表的第 i 個元素的時間同 i 的大小有關(guān)（） 【答案】 2線性表的特點是每個元素都有一個前驅(qū)和一個后繼（） 【答案】 3 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高（） 【答案】 4線性表采用鏈表存儲時，結(jié)點的存儲空間可以是不連續(xù)的（） 【答案】 5鏈表是采用鏈式存儲結(jié)構(gòu)的線性表，進行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構(gòu)中效率 高（） 【答案】 6順序存儲方式只能用于存儲線性結(jié)構(gòu)（） 【答案】 【解析】線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖狀結(jié)構(gòu)均可用順序存儲表示。 9順序存儲結(jié)構(gòu)的主要

11、缺點是不利于插入或刪除操作（） 【答案】 10順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好（） 【答案】 2.4程序設(shè)計題 1設(shè)順序表 va 中的數(shù)據(jù)元素遞增有序。試設(shè)計一個算法，將 x 插入到順序表的適當位置上，以保持 - 3 - 數(shù)據(jù)結(jié)構(gòu)上機實驗與習(xí)題解析亱店打烊 oO 該表的有序性。 【算法源代碼】 void Insert_SqList(SqList va,int x)/*把 x插入遞增有序表 va 中*/ int i; if(va.length MAXSIZE) return; for(i=va.length-1;va.elemixi-) va.elemi+1=va.el

12、emi; va.elemi+1=x; va.length+; /*Insert_SqList*/ 2設(shè) A=（a1，a2，am） 和 B=（b1，b2，bn）均為順序表，試設(shè)計一個比較 A，B 大小的算 法（請注意：在算法中，不要破壞原表 A和 B）。 【算法分析】比較順序表 A和 B，并用返回值表示結(jié)果，值為 1，表示 AB；值為-1，表示 AB；值 為 0，表示 A=B。 1）當兩個順序表可以互相比較時，若對應(yīng)元素不等，則返回值為 1 或-1； 2）當兩個順序表可以互相比較的部分完全相同時，若表長也相同，則返回值為0；否則，哪個較 長，哪個就較大 【算法源代碼】 int ListComp(

13、SqList A,SqList B) for(i=1;i=A.length if(A.length=B.length) return 0; return A.lengthB.length?1:-1; /*當兩個順序表可以互相比較的部分完全相同時，哪個較長，哪個就較大*/ /*ListComp */ 3已知指針 ha 和 hb 分別指向兩個單鏈表的頭結(jié)點，并且已知兩個鏈表的長度分別為 m 和 n。試設(shè) 計一個算法將這兩個鏈表連接在一起（即令其中一個表的首元結(jié)點連在另一個表的最后一個結(jié)點之后）， 假設(shè)指針 hc 指向連接后的鏈表的頭結(jié)點，并要求算法以盡可能短的時間完成連接運算。 【算法分析】 1）

14、單鏈表 ha 的頭結(jié)點作為連接后的鏈表的頭結(jié)點，即 hc=ha； 2）查找單鏈表 ha 的最后一個結(jié)點，由指針 p 指向，即 p-next=NULL； 3）將單鏈表 hb的首元結(jié)點（非頭結(jié)點）連接在 p 之后，即 p-next=hb-next； 4）回收單鏈表 hb的頭結(jié)點空間 【算法源代碼】 void ListConcat(LinkList ha,LinkList hb,LinkList *hc) /*把鏈表 hb 接在 ha 后面形成鏈表 hc*/ *hc=ha; p=ha;/*由指針 p 指向 ha 的尾元結(jié)點*/ p=p-next; p-next=hb-next; free(hb);

15、/*ListConcat */ 4試設(shè)計一個算法，在無頭結(jié)點的動態(tài)單鏈表上實現(xiàn)線性表操作 INSERT（L，i，b），并和在帶頭 結(jié)點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進行比較。 【算法分析】 1）生成新結(jié)點存放元素 b，由指針 new指向； 2）將 new 插入在單鏈表的第 i 個元素的位置上：若 i=1，new 插在鏈表首部；否則查找第 i-1 個結(jié) 點，由指針 p 指向，然后將 new插在 p 之后。 【算法源代碼】 void Insert(LinkList *L,int i,int b) LinkList new; - 4 - 第 2 部分 習(xí)題解析亱店打烊 oO new=(LinkLi

16、st*)malloc(sizeof(LNode); new-data=b; if(i=1) /*插入在鏈表頭部*/ New-next=*L; *L=new; else /*插入在第 i 個元素的位置*/ p=*L; while(-i1) p=p-next; new-next=p-next;p-next=new; /*Insert */ 5已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試設(shè)計一個高效的算法，刪除 表中所有值大于 mink 且小于 maxk 的元素（若表中存在這樣的元素），同時釋放被刪結(jié)點空間（注意： mink和 maxk是給定的兩個參變量。它們的值可以和表中的元素相同

17、，也可以不同）。 【算法分析】 1）查找最后一個不大于 mink的元素結(jié)點，由指針 p 指向； 2）如果還有比 mink更大的元素，查找第一個不小于 maxk 的元素，由指針 q 指向； 3）p-next=q，即刪除表中所有值大于 mink且小于 maxk的元素。 【算法源代碼】 void Delete_Between(LinkList *L,int mink,int maxk) p=*L; while(p-next-datanext; /*p是最后一個不大于 mink的元素*/ if(p-next) /*如果還有比 mink更大的元素*/ q=p-next; while(q-datanext

18、; /*q是第一個不小于 maxk的元素*/ p-next=q; /*Delete_Between */ 6已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試設(shè)計一個高效的算法，刪除 表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），同時釋放被刪結(jié)點空間。 【算法分析】 1）初始化指針 p 和 q，分別指向鏈表中相鄰的兩個元素； 2）當 p-next 不為空時，做如下處理： 若相鄰兩元素不相等時，p 和 q 都向后推一步； 否則，當相鄰元素相等時，刪除多余元素。 【算法源代碼】 void Delete_Equal(LinkList *L) p=(*L)-next;

19、q=p-next; /*p 和 q 指向相鄰的兩個元素*/ while(p-next) if(p-data!=q-data) /*若相鄰兩元素不相等時，p 和 q 都向后推一步*/ p=p-next; q=p-next; else while(q-data=p-data) /*當相鄰元素相等時刪除多余元素*/ - 5 - 數(shù)據(jù)結(jié)構(gòu)上機實驗與習(xí)題解析亱店打烊 oO r=q; q=q-next; free(r); p-next=q;p=q;q=p-next; /*else*/ /*while*/ /*Delete_Equal */ 7試設(shè)計一個算法，對帶頭結(jié)點的單鏈表實現(xiàn)就地逆置。 【算法分析】

20、1）空表或長度為 1 的表，不做任何處理； 2）表長大于 2 時，做如下處理： 首先將整個鏈表一分為二，即從鏈表的第一元素結(jié)點處斷開； 逐個地把剩余鏈表的當前元素 q 插入到鏈表的頭部。 【算法源代碼】 void LinkList_reverse(LinkList L) if(!L-next|!L-next-next) return; p=L-next; q=p-next; s=q-next; p-next=NULL; /*從鏈表的第一元素結(jié)點處斷開*/ while(s-next) q-next=p;p=q; q=s;s=s-next; /*把 L的元素逐個插入新表表頭*/ q-next=p;

21、s-next=q;L-next=s; /*LinkList_reverse*/ 8設(shè)線性表 A=（a1，a2，am） 和 B=（b1，b2，bn），試設(shè)計一個按下列規(guī)則合并 A，B 為 線性表 C的算法，即使得 C=（a1，b1，am，bm，bm+1，bn）當 mn 時； 或者 C=（a1，b1，an，bn，an+1，am）當 mn 時。 線性表 A，B 和 C 均以單鏈表作存儲結(jié)構(gòu)，且 C 表利用 A 表和 B 表中的結(jié)點空間構(gòu)成。注意：單鏈 表的長度值 m和 n 均未顯式存儲。 【算法分析】 1）初始化指針 p 指向鏈表 A的當前元素，指針 q 指向鏈表 B的當前元素； 2）當鏈表 A和

22、B均為結(jié)束時，做如下處理： 將 B的元素插入 若 A非空，將 A的元素插入 指針 p 和 q 同時后移 【算法源代碼】 void merge1(LinkList A,LinkList B,LinkList *C) p=A-next;q=B-next;*C=A; while(pp-next=q; /*將 B 的元素插入*/ if(s) t=q-next; q-next=s; /*若 A非空，將 A的元素插入*/ p=s;q=t; /*指針 p 和 q 同時后移*/ /*while*/ /*merge1 */ 9假設(shè)有兩個按元素值遞增有序排列的線性表 A 和 B，均以單鏈表作存儲結(jié)構(gòu)，請設(shè)計一個算

23、法將 A 表和 B 表歸并成一個按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表 C，并要求利用原表（即 A表和 B 表）的結(jié)點空間構(gòu)造 C 表。 【算法分析】按從小到大的順序依次把 A和 B 的元素插入新表的頭部 pc 處，最后處理 A或 B的剩余 - 6 - 第 2 部分 習(xí)題解析亱店打烊 oO 元素。 【算法源代碼】 void reverse_merge(LinkList A,LinkList B,LinkList *C) LinkList pa,pb,pre; pa=A-next;pb=B-next; /*pa 和 pb 分別指向 A和 B 的當前元素*/ pre

24、=NULL; while(pa|pb) if(pa-datadata|!pb) /*將 A的元素插入新表*/ pc=pa;q=pa-next;pa-next=pre;pa=q; else /*將 B的元素插入新表*/ pc=pb;q=pb-next;pb-next=pre;pb=q; pre=pc; *C=A; A-next=pc; /*構(gòu)造新表頭*/ /*reverse_merge*/ 10已知 A，B 和 C 為三個遞增有序的線性表，現(xiàn)要求對 A 表作如下操作：刪去那些既在 B 表中出 現(xiàn)又在 C 表中出現(xiàn)的元素。試對順序表編寫實現(xiàn)上述操作的算法，并分析你的算法的時間復(fù)雜度（注意： 題中沒

25、有特別指明同一表中的元素值各不相同）。 【算法分析】先從 B 和 C 中找出共有元素，記為 same，再在 A 中從當前位置開始， 凡小于 same 的 元素均保留(存到新的位置)，等于 same的就跳過，到大于 same時就再找下一個 same。 【算法源代碼】 void SqList_Intersect_Delete(SqList *A,SqList B,SqList C) i=0;j=0;k=0;m=0;/*i指示 A中元素原來的位置，m為移動后的位置*/ while(i(*A).length else same=B.elemj;/*找到了相同元素 same*/ while(B.elem

26、j=same) j+; while(C.elemk=same) k+;/*j和 k后移到新的元素*/ while(i(*A).length/*需保留的元素移動到新位置*/ while(i(*A).length /*跳過相同的元素*/ /*while*/ while(inext!=NULL) /*鏈表不為空表*/ p=la-next-next; /*p 指向第一結(jié)點的后繼*/ la-next-next=NULL; /*直接插入原則認為第一元素有序，然后從第二元素起依次插入*/ while(p!=NULL) r=p-next;/*暫存 p 的后繼*/ q=la; while(q-next!=NUL

27、L/*查找插入位置*/ - 7 - 數(shù)據(jù)結(jié)構(gòu)上機實驗與習(xí)題解析亱店打烊 oO p-next=q-next;/*將 p 結(jié)點鏈入鏈表*/ q-next=p; p=r; 12設(shè)有一個雙向循環(huán)鏈表，每個結(jié)點中除有 prior，data 和 next 三個域外，還增設(shè)了一個訪問頻度 域 freq。在鏈表被起用之前，頻度域 freq的值均初始化為零，而每當對鏈表進行一次 LOCATE（L，X）的 操作后，被訪問的結(jié)點（元素值等于 X 的結(jié)點）中的頻度域 freq 的值便增 1，同時調(diào)整鏈表中結(jié)點之間的 次序，使其按訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結(jié)點總是靠近表頭結(jié)點。試編 寫符合上

28、述要求的 LOCATE操作的算法。 【算法分析】 1）在雙向鏈表中查找數(shù)據(jù)值為 x的結(jié)點，由指針 p 指向，若找不到，直接返回，否則執(zhí)行第 2 步； 2）修改 x結(jié)點的訪問頻度 freq，并將結(jié)點從鏈表上摘下； 3）順結(jié)點的前驅(qū)鏈查找該結(jié)點的位置，即找到一個結(jié)點的訪問頻度大于 x 結(jié)點的訪問頻度，由指針 q 指向；若 q 和 p 不是相鄰結(jié)點，調(diào)整位置，把 p 插在 q 之后。 【算法源代碼】 DuLNode * Locate_DuList(DuLinkList *L,int x) p=(*L)-next; while(p.data!=x if(p=(*L) return NULL; /*沒找

29、到 x結(jié)點*/ p-freq+; p-pre-next=p-next;p-next-pre=p-pre; /*將 x結(jié)點從鏈表上摘下*/ q=p-pre; while(q-freqfreq /*查找插入位置*/ if(q!=p-pre)/*將 x結(jié)點插入*/ q-next-pre=p;p-next=q-next; q-next=p;p-pre=q; /*調(diào)整位置*/ return p; /*Locate_DuList */ 13已知三個帶頭結(jié)點的線性鏈表 A、B 和 C 中的結(jié)點均依元素值自小至大非遞減排列（可能存在兩 個以上值相同的結(jié)點），編寫算法對 A表進行如下操作：使操作后的鏈表 A中僅

30、留下三個表中均包含的數(shù) 據(jù)元素的結(jié)點，且沒有值相同的結(jié)點，并釋放所有無用結(jié)點。限定算法的時間復(fù)雜度為O（m+n+p），其 中 m、n 和 p 分別為三個表的長度。 【算法分析】留下三個鏈表中公共數(shù)據(jù)，首先查找兩表 A 和 B 中公共數(shù)據(jù)，再去 C 中找有無該數(shù) 據(jù)。要消除重復(fù)元素，應(yīng)記住前驅(qū)，要求時間復(fù)雜度 O（m+n+p），在查找每個鏈表時，指針不能回溯。 【算法源代碼】 LinkList Common(LinkList A, LinkList B, LinkList C) pa=A-next;pb=B-next; pc=C-next; /*pa，pb 和 pc 是工作指針*/ pre=A;

31、 while(pa pa=pa-next;free(u); else if(pa-data pb-data)pb=pb-next; else if (pa if(pc) if(pc-datapa-data) /*處理 pa 結(jié)點，后移指針*/ u=pa;pa=pa-next;free(u); else if(pre=A)/*結(jié)果表中第一個結(jié)點*/ pre-next=pa;pre=pa;pa=pa-next else if(pre-data=pa-data) /*重復(fù)結(jié)點不鏈入 A表*/ u=pa;pa=pa-next;free(u); - 8 - 第 2 部分 習(xí)題解析亱店打烊 oO else

32、 pre-next=pa;pre=pa;pa=pa-next;/*將新結(jié)點鏈入 A表 */ pb=pb-next;pc=pc-next; /* 鏈表的工作指針后移*/ else if(pa=NULL)pre-next=NULL; /*若 A表已結(jié)束，置 A表表尾*/ else /*處理原 A表未到尾而 B或 C 到尾的情況*/ pre-next=NULL; /*置 A表表尾標記*/ while(pa!=NULL) /*刪除原 A表剩余元素。*/ u=pa;pa=pa-next;free(u); 14設(shè) head 為一單鏈表的頭指針，單鏈表的每個結(jié)點由一個整數(shù)域 data 和指針域 next 組

33、成，整數(shù)在 單鏈表中是無序的。編一函數(shù)，將 head 鏈中結(jié)點分成一個奇數(shù)鏈和一個偶數(shù)鏈，分別由 p，q 指向，每個 鏈中的數(shù)據(jù)按由小到大排列。程序中不得使用 malloc申請空間。 【算法分析】本題要求將一個鏈表分解成兩個鏈表，兩個鏈表都要有序，兩鏈表建立過程中不得使用 malloc申請空間，這就是要利用原鏈表空間，隨著原鏈表的分解，新建鏈表隨之排序。 【算法源代碼】 discreat(LinkList p, LinkList q, LinkList head) p=NULL; q=NULL;/*p和 q 鏈表初始化為空表*/ s=head; while(s!=NULL) r=s-next;

34、 /*暫存 s的后繼*/ if(s-data%2=0) /*處理偶數(shù)*/ if (p=NULL) p=s;p-next=NULL; /*第一個偶數(shù)結(jié)點*/ else pre=p; if(pre-datas-data) s-next=pre;p=s;/*插入當前最小值結(jié)點*/ else while (pre-next!=NULL) if (pre-next-datadata) pre=pre-next;/*查找插入位置*/ s-next=pre-next; /*鏈入結(jié)點*/ pre-next=s; else/*處理奇數(shù)鏈 if (q=NULL) q=s;q-next=NULL; /*第一奇數(shù)結(jié)點

35、*/ else pre=q; if (pre-datas-data) s-next=pre; q=s;/*修改頭指針*/ else while (pre-next!=NULL)/*查找插入位置*/ if (pre-next-datadata) pre=pre-next; s-next=pre-next;/*鏈入結(jié)點*/ pre-next=s; /*結(jié)束奇數(shù)鏈結(jié)點*/ s=r; /*s指向新的待排序結(jié)點*/ - 9 - 第 3 章 桟和隊列 3.1選擇題 1一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第 i（1in）個元素是 （） A）不確定 B）n-i+1 C）i D）n-i

36、【答案】B 【解析】根據(jù)棧的性質(zhì)（LIFO），若輸出的第一個元素是 n，則表明所有的元素已經(jīng)入棧，則出棧順 序為 n，n-1， ，3，2，1。 2設(shè)棧 S 和隊列 Q的初始狀態(tài)為空，元素 e1，e2，e3，e4，e5 和 e6 依次通過棧 S，一個元素出棧后 即進隊列 Q，若 6 個元素出隊的序列是 e2，e4，e3，e6，e5，e1 則棧 S 的容量至少應(yīng)該是（） A）6 B）4 C）3 D）2 【答案】C 【解析】根據(jù)棧的性質(zhì)（LIFO）得，e2 出棧前，棧中存有 e1 和 e2 兩個元素，e4 出棧前，棧中存有 e1、e3 和 e4 三個元素，e4 和 e3 出棧以后，e5 和 e6 入

37、棧，棧中同樣存在 e1、e5 和 e6 三個元素，然后三個 元素依次出棧，所以棧的容量至少應(yīng)該為 3。 3若一個棧以向量 V1.n存儲，初始棧頂指針 top 為 n+1，則下面 x進棧的正確操作是（） A）top=top+1; Vtop=x B）Vtop=x; top=top+1 C）top=top-1; Vtop=x D）Vtop=x; top=top-1 【答案】C 【解析】棧式運算受限的線性表，只允許在棧頂進行插入和刪除操作。本題中棧頂指針為 n+1，該數(shù) 組將棧頂放在了下標大的一端，所以在進行入棧操作時 top 指針應(yīng)該進行減一操作。通常元素進棧的操作 為：先移動棧頂指針后存入元素。

38、4如果我們用數(shù)組 A1.100來實現(xiàn)一個大小為 100 的棧，并且用變量 top 來指示棧頂，top 的初值為 0，表示?？?。請問在 top 為 100 時，再進行入棧操作，會產(chǎn)生（ ） A）正常動作 B）溢出 C）下溢 D）同步 【答案】B 【解析】當 top 為 100 時，表示棧已經(jīng)滿了，此時再進行入棧操作，則會造成溢出。 5棧在（）中應(yīng)用。 A）遞歸調(diào)用 B）子程序調(diào)用 C）表達式求值 D）A， 【答案】D 6表達式 3* 2(4+2*2-6*3)-5 求值過程中當掃描到 6 時，對象棧和算符棧為（），其中為乘 冪 。 A）3,2,4,1,1；(*(+*- B)3,2,8；(*- C）

39、3,2,4,2,2；(*(- D)3,2,8；(*(- 【答案】D 【解析】根據(jù)表達式求值的基本思想，在掃描表達式時，依次讀入表達式的每個字符，若是操作數(shù)則 進對象棧，若為運算符則和運算符棧的棧頂運算符比較優(yōu)先級后做相應(yīng)的操作。 7用鏈接方式存儲的隊列，在進行刪除運算時（） A）僅修改頭指針 B）僅修改尾指針 C）頭、尾指針都要修改 D）頭、尾指針可能都要修改 【答案】D 【解析】若隊列中的元素多于一個，刪除隊列中的隊尾元素，只需修改隊尾指針；若隊列中只有一個 元素，刪除該元素后，隊頭隊尾指針都需要修改。 8循環(huán)隊列 A0.m-1存放其元素值，用 front 和 rear 分別表示隊頭和隊尾，

40、則當前隊列中的元素 數(shù)是( ) A）(rear-front+m)%mB）rear-front+1 C）rear-front-1D）rear-front 【答案】A 【解析】循環(huán)隊列是解決假溢出的問題，通常把一維數(shù)組看成首尾相接。在循環(huán)意義下的求元素個數(shù) 的運算可以利用求模運算。 9若用一個大小為 6 的數(shù)組來實現(xiàn)循環(huán)隊列，且當前 rear 和 front 的值分別為 0 和 3，當從隊列中 刪除一個元素，再加入兩個元素后，rear 和 front 的值分別為多少？( ) 數(shù)據(jù)結(jié)構(gòu)上機實驗與習(xí)題解析亱店打烊 oO A）1 和 5 B）2 和 4 C）4 和 2 D）5 和 1 【答案】B 【解析

41、】循環(huán)隊列是解決假溢出的問題，通常把一維數(shù)組看成首尾相接。在循環(huán)意義下的加 1 運算通 常用求模運算來實現(xiàn)。所以入隊和出隊時的操作分別為：rear=(rear+1)%m，front=(front+1)%m。 10棧和隊列的共同點是（） A）都是先進先出 B）都是先進后出 C）只允許在端點處插入和刪除元素 D）沒有共同點 【答案】C 【解析】棧和隊列都是運算受限的線性表，只允許在表端點處進行操作。 11在一個鏈隊列中，假定 front和 rear分別為隊頭和隊尾指針，則插入*s結(jié)點的操作為（） A）front-next=s;front=s; B）s-next=rear;rear=s; C）rea

42、r-next=s;rear=s; D）s-next=front;front=s; 【答案】C 【解析】隊列是運算受限的線性表（FIFO），插入元素只能插在隊尾，所以需修改隊尾指針。 12判定一個棧 S（元素個數(shù)最多為 MAXSIZE）為空和滿的條件分別為（） A）S-top!=-1 S-top!=MAXSIZE-1 B）S-top=-1 S-top=MAXSIZE-1 C）S-top=-1 S-top!=MAXSIZE-1 D）S-top!=-1 S-top=MAXSIZE-1 【答案】B 13循環(huán)順序隊列中是否可以插入下一個元素（） A）與隊頭指針和隊尾指針的值有關(guān) B）只與隊尾指針的值有關(guān)

43、，與隊頭指針的值無關(guān) C）只與數(shù)組大小有關(guān)，而與隊頭指針和隊尾指針的值無關(guān) D）與曾經(jīng)進行過多少次插入操作有關(guān) 【答案】A 【解析】在循環(huán)隊列中判斷隊滿的條件為：(q.rear+1)%m=q.front 是否為真，從中可以看出，與隊頭 指針和隊尾指針的值有關(guān)。 14最不適合用作鏈隊的鏈表是（） A）只帶隊頭指針的非循環(huán)雙鏈表 B）只帶隊頭指針的循環(huán)雙鏈表 C）只帶隊尾指針的非循環(huán)雙鏈表 D）只帶隊尾指針的循環(huán)單鏈表 【答案】A 【解析】鏈隊是在鏈表的兩端進行操作，而在 A中查找鏈表最后一個結(jié)點的時間復(fù)雜度為 O(n)。 15下列哪中數(shù)據(jù)結(jié)構(gòu)常用于系統(tǒng)程序的作業(yè)調(diào)度（） A）棧 B）隊列 C）鏈

44、表 D）數(shù)組 【答案】B 【解析】作業(yè)調(diào)度采用先到先服務(wù)的方式，因此最適合的數(shù)據(jù)結(jié)構(gòu)為隊列。 3.2填空題 1棧是_的線性表，其運算遵循_的原則。 【答案】（1）操作受限（或限定僅在表尾進行插入和刪除操作） （2）后進先出 2設(shè)有 一個空 棧，棧頂指針為 1000H(十六進制 )，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之 后 ， 輸 出 序 列 是 _ ， 而 棧 頂 指 針 值 是 _H。設(shè)棧為順序棧，每個元素占 4 個字節(jié)。 【答案】（1）23 （2）100CH 【解析】PUSH 為入棧操作，POP 為出棧操作。根據(jù)棧的性

45、質(zhì)，經(jīng)過 PUSH,PUSH,POP 運算之后，棧 中存在元素 1，輸出數(shù)據(jù)為 2，然后經(jīng)過 PUSH,POP，3 入棧，3 出棧，然后經(jīng)過 PUSH,PUSH 之后 4，5 入 棧，此時出棧序列為2，3，棧中元素為1，4，5；每個元素占4 個字節(jié)，所以棧頂指針的值為 1000H+3*4=100CH（十六進制數(shù)） 3循環(huán)隊列的引入，目的是為了克服_。 【答案】假溢出時大量移動數(shù)據(jù)元素。 4隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是_。 2 第 2 部分 習(xí)題解析亱店打烊 oO 【答案】先進先出 5已知鏈隊列的頭尾指針分別是 f和 r，則將值 x入隊的操作序列是_。

46、【答案】 s=(LinkList)malloc(sizeof(LNode); s-data=x; s-next=r-next; r-next=s; r=s; 【解析】根據(jù)隊列的性質(zhì)，新插入的元素永遠插在隊尾。 6區(qū)分循環(huán)隊列的滿與空，只有兩種方法，它們是_和_。 【答案】（1）犧牲一個存儲單元 （2）設(shè)標記 7表達式 23+(12*3-2)/4+34*5/7)+108/9 的后綴表達式是_。 【答案】23.12.3*2-4/34.5*7/+108.9/+（注：表達式中的點(.)表示將數(shù)隔開，如 23.12.3 是三個數(shù)） 【解析】表達式的后綴表達式是將表達式中的運算符寫在兩個操作數(shù)之后。轉(zhuǎn)換原

47、則如下： （1）從左到右掃描表達式，若讀到的是操作數(shù)，則直接把它輸出 （2）若讀到的是運算符： 該運算符為左括號“（”，則直接入棧 該運算符為右括號“）”，則輸出棧中運算符，直到遇到左括號為止 該運算符為非括號運算符，則與棧頂元素做優(yōu)先級比較：若比棧頂元素的優(yōu)先級高或相等， 則直接入棧；若比棧頂元素的優(yōu)先級低，則輸出棧頂元素。 （3）當表達式掃描完后棧中還有運算符，則依次輸出運算符，直到棧空。 8用下標 0 開始的 N 元數(shù)組實現(xiàn)循環(huán)隊列時，為實現(xiàn)下標變量 M 加 1 后在數(shù)組有效下標范圍內(nèi)循 環(huán)，可采用的表達式是：M=_。 【答案】(M+1)% N； 【解析】循環(huán)隊列是解決假溢出的問題，通常

48、把一維數(shù)組看成首尾相接。在循環(huán)意義下的加 1 運算通 常用求模運算來實現(xiàn)。 9當兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組 stack1.n表示，兩棧頂指針為 top1與 top2，則當 棧 1 空時，top1為_，棧 2 空時，top2為_，棧滿時為_。 【答案】（1）0 （2）n+1 （3）top1+1=top2 【解析】為了增加內(nèi)存空間的利用率和減少溢出的可能性 ,由兩個棧共享一片連續(xù)的內(nèi)存空間時 ,應(yīng)將 兩棧的棧頂分別設(shè)在這片內(nèi)存空間的兩端 ,這樣,當兩個棧的棧頂在?？臻g的某一位置相遇時，才產(chǎn)生上 溢，即 top1+1=top2。 10 在 作 進 棧 運 算 時 應(yīng) 先判 別 棧 是 否

49、_ ； 在 作 退 棧 運 算 時 應(yīng) 先 判 別 棧 是 否 _；當棧中元素為 n 個，作進棧運算時發(fā)生上溢，則說明該棧的最大容量為_。 為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的空間時，應(yīng)將兩棧的 _分別設(shè)在內(nèi)存空間的兩端，這樣只有當_時才產(chǎn)生溢出。 【答案】（1）滿 （2）空 （3）n （4）棧底 （5）兩棧頂指針相鄰 11在 Q的鏈隊列中，判斷只有一個結(jié)點的條件是_。 【答案】Q-front!=NULL (注：算法中可調(diào)用棧操作的基本算法。) 【算法分析】判斷表達式中括號是否匹配，可通過棧，簡單說是左括號時進棧，右括號時退棧。退棧 時，若棧頂元素是左括號，則新讀

50、入的右括號與棧頂左括號就可消去。如此下去，輸入表達式結(jié)束時，棧 為空則正確，否則括號不匹配。 【算法源代碼】 int EXYX (char E) /*E存放字符串表達式，以#結(jié)束*/ char s30; /*s是一維數(shù)組，容量足夠大，用作存放括號的棧*/ int top=0,i; /*top用作棧頂指針*/ stop=#; /*#先入棧，用于和表達式結(jié)束符號#匹配*/ i=0; /*字符數(shù)組 E 的工作指針*/ while(Ei!=#) /*逐字符處理字符表達式的數(shù)組*/ switch (Ei) case (: s+top= (; i+ ; break ; case ): if(stop=()

51、top-; i+; break; elseprintf(括號不配對);exit(0); case #: if(stop=#)printf(括號配對n);return (1); else printf( 括號不配對n);return (0); /*括號不配對*/ default : i+; /*讀入其它字符，不作處理*/ /*算法結(jié)束*/ 2假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，但不設(shè)頭指針，請寫出 相應(yīng)的入隊列和出隊列算法。 【算法分析】 根據(jù)隊列的先進先出的性質(zhì)，隊列的入隊操作在隊尾進行，出隊操作在隊頭進行。而題目所采用的數(shù) 據(jù)結(jié)構(gòu)是只設(shè)一個尾指針的循環(huán)鏈表。我們可

52、以根據(jù)循環(huán)鏈表的特點找到頭指針。 【算法源代碼 1】 void EnQueue (LinkList rear, ElemType x) /* rear是帶頭結(jié)點的循環(huán)鏈隊列的尾指針，本算法將元素 x插入到隊尾*/ s=(LinkList)malloc(sizeof(LNode); /*申請結(jié)點空間*/ s-data=x; s-next=rear-next; /*將 s結(jié)點鏈入隊尾*/ rear-next=s; rear=s; /*rear指向新隊尾*/ 【算法源代碼 2】 void DeQueue (LinkList rear) /* rear是帶頭結(jié)點的循環(huán)鏈隊列的尾指針，本算法執(zhí)行出隊操作

53、，操作成功輸出隊頭元 素；否則給出出錯信息*/ if(rear-next=rear) printf(隊空n); exit(0); s=rear-next-next; /*s 指向隊頭元素*/ rear-next-next=s-next; /*隊頭元素出隊*/ printf (出隊元素是:%d,s-data); if(s=rear) rear=rear-next; /*空隊列*/ 5 數(shù)據(jù)結(jié)構(gòu)上機實驗與習(xí)題解析亱店打烊 oO free(s); 3設(shè)整數(shù)序列 a1，a2，an，給出求解最大值的遞歸程序。 【算法分析】根據(jù)題意，本題的函數(shù)定義為： a1 n=1 maxvalue(a,n)= anan

54、maxvalue(a,n-1) maxvalue(a,n-1) anMaxValue(a,n-1) max=an; else max=MaxValue(a,n-1); return(max); 4試將下列遞歸函數(shù)改寫為非遞歸函數(shù)。 void test(int *sum) int x; scanf(%d, if(x=0) *sum=0 ; else test( (*sum)+=x; printf(%5d,*sum); 【算法分析】 該函數(shù)是以讀入數(shù)據(jù)的順序為相反順序進行累加問題，可將讀入數(shù)據(jù)放入棧中，等輸入結(jié)束時，將棧 中數(shù)據(jù)退出進行累加。累加的初值為 0。 【算法源代碼】 int test() int x,sum=0,top=0,s30; scanf(%d, while (x!=0) s+top=a; scanf(%d, printf(%5d,sum); while (top) sum+=stop-; printf(%5d,sum); 5編寫一個算法，利用棧的基本運算將指定棧中的內(nèi)容進行逆轉(zhuǎn)。