考試題型考試題型一、填空題二、選擇題三、簡(jiǎn)答題四、解答題五、程序閱讀題六、算法題七、設(shè)計(jì)題第一章基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)研究三方面主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)的四種基本邏輯結(jié)構(gòu)兩種基本的存儲(chǔ)表示方法算法分析的基本方法算法的時(shí)間復(fù)雜度1.20確定劃線(xiàn)語(yǔ)句的執(zhí)行次數(shù)，計(jì)算它們的漸近時(shí)間復(fù)雜度。(1) i=1;k=0; do {

k=k+10*i;i++; }while(i<=n-1)答： 劃線(xiàn)語(yǔ)句的執(zhí)行次數(shù)為n-1

漸近時(shí)間復(fù)雜度O(n)(2） i=1;x=0; do {

x++;i=2*i;

}while（i<n）;答： 劃線(xiàn)語(yǔ)句的執(zhí)行次數(shù)為

log2n。

漸近時(shí)間復(fù)雜度

O(log2n)k(循環(huán)次數(shù))2*i121<n222<nk2k<nk+1因?yàn)橐?k<n,因此k<log2n,k=log2n(3) for(inti=1;i<=n;i++) for(intj=1;j<=i;j++) for(intk=1;k<=j;k++)

x++;

答： 劃線(xiàn)語(yǔ)句的執(zhí)行次數(shù)為

n(n+1)(n+2)/6

漸近時(shí)間復(fù)雜度

O(n3)

(4） x=n;y=0; while(x>=(y+1)*(y+1))y++;

答： 劃線(xiàn)語(yǔ)句的執(zhí)行次數(shù)為(

-1)+1=

（因?yàn)閥從0開(kāi)始）

漸近時(shí)間復(fù)雜度

O()(y+1)2<=n第二章線(xiàn)性表兩種線(xiàn)性表表示方式：順序表、鏈表鏈表的四種形式：?jiǎn)捂湵?、雙向鏈表、帶表頭結(jié)點(diǎn)的鏈表、單循環(huán)鏈表在順序表/單鏈表/帶表頭結(jié)點(diǎn)的單鏈表/雙向鏈表中：查找/刪除/插入元素順序和鏈接表示的優(yōu)缺點(diǎn)比較多項(xiàng)式的算術(shù)運(yùn)算2.3類(lèi)SeqList的插入函數(shù)Insert，在表滿(mǎn)時(shí)只簡(jiǎn)單地給出提示信息“Overflow”。試重寫(xiě)該函數(shù)，在表滿(mǎn)時(shí)能使表容量加倍，并將新元素插入表中。template<classT>BoolSeqList<T>::Insert2(inti,Tx){}if(i<-1||i>n-1){cout<<“Outofbounds”<<endl;returnfalse;}if(n==maxLength)//表滿(mǎn)時(shí){}回顧線(xiàn)形表類(lèi)的數(shù)據(jù)成員和關(guān)系： LinearList：線(xiàn)性表類(lèi) (protected: intn——實(shí)際長(zhǎng)度)SeqList：順序表類(lèi)(private:intmaxLength—最大長(zhǎng)度T*elements)SingleList：?jiǎn)捂湵眍?lèi)(private:Node<T>*first)T*elem=newT[2*maxLength];maxLength=maxLength*2;for(intj=0;j<=i;j++)

//擴(kuò)充線(xiàn)性表容量的同時(shí)插入x

elem[j]=elements[j];elem[i+1]=x;for(j=i+1;j<n;j++) elem[j+1]=elements[j];n++;delete[]elements;elements=elem;returntrue;//n!=maxLength時(shí),即表未滿(mǎn)時(shí)for(intj=n-1;j>i;j--) elements[j+1]=elements[j];elements[i+1]=x;n++;returntrue;先擴(kuò)充線(xiàn)性表容量，然后在位置i后統(tǒng)一做該插入x的操作也可以2.4在類(lèi)SeqList中增加一個(gè)成員函數(shù)，刪除表中所有值為x的元素，直接實(shí)現(xiàn)該函數(shù)并分析其時(shí)間復(fù)雜度。template<classT>boolSeqList<T>::Del(Tx){

}if(!n)//下溢出檢查{ cout<<"UnderFlow"<<endl; returnfalse; }intflag=0;for(inti=0;i<n;i++) //刪除所有值為x的元素{ if(elements[i]==x) { for(intj=i+1;j<n;j++) elements[j-1]=elements[j]; n--; i--; flag=1; }}returnflag;時(shí)間復(fù)雜度O(n)2.6在類(lèi)SingleList中增加一個(gè)成員函數(shù)，將單鏈表逆置，直接實(shí)現(xiàn)該函數(shù)并分析其時(shí)間復(fù)雜度，要求設(shè)計(jì)的算法的空間復(fù)雜度為O(n)。template<classT>voidSingleList<T>::invert(){Node<T>*p=first,*q;first=NULL;while(p){

q=p->link;p->link=first;first=p;p=q;}}

時(shí)間復(fù)雜度O(n)2.7在類(lèi)SingleList中增加一個(gè)成員函數(shù)，刪除表中指定的元素x，并分析其時(shí)間復(fù)雜度。

template<classT>boolSingleList<T>::Del(constT&x){}while(p&&p->element!=x)//刪除的不是第一個(gè)元素{q=p;p=p->link;}if(p)//p->element==x時(shí)刪除{q->link=p->link;delete(p);n--;returntrue;}returnfalse;//否則p==NULL時(shí)失敗if(!n) //下溢判斷{ cout<<"UnderFlow!"<<endl; returnfalse;}Node<T>*p=first,*q;if(first->element==x)//若刪除的是第一個(gè)元素{ first=first->link; deletep; n--;

returntrue;}時(shí)間復(fù)雜度O(n)第三章堆棧和隊(duì)列堆?！筮M(jìn)先出(LIFO) 插入/刪除操作都在表的同一端隊(duì)列——先進(jìn)先出(FIFO)

一端插入，另一端刪除順序棧的操作：出棧/入棧循環(huán)隊(duì)列的操作：入隊(duì)/出隊(duì) 空隊(duì)列/滿(mǎn)隊(duì)列后綴表達(dá)式的計(jì)算后綴/中綴/前綴表達(dá)式間的轉(zhuǎn)換*3.1設(shè)A，B，C，D，E五個(gè)元素依次進(jìn)棧（進(jìn)棧后可立即出棧），問(wèn)能否得到下列序列。若能得到，則給出相應(yīng)的push和pop序列；若不能，則說(shuō)明理由。（1）A，B，C，D，E（2）A，C，E，B，D（3）C，A，B，D，E（4）E，D，C，B，A（1）能得到該序列。相應(yīng)的push和pop序列為：push(A);pop();push(B);pop();push(C);pop();push(D);pop();push(E);pop();（2）不能得到該序列，在E出棧時(shí)，B和D在棧中，B比D先進(jìn)棧，所以D應(yīng)比B先出棧。（3）不能得到該序列，在C出棧時(shí)，A和B在棧中，A比B先進(jìn)棧，所以B應(yīng)比A先出棧。（4）能得到該序列。相應(yīng)的push和pop序列為：push(A);push(B);push(C);push(D);push(E);pop();pop();pop();pop();pop();3.2寫(xiě)出下列表達(dá)式的后綴形式。（1）(a+b)/(c+d)（2）b^2-4*a*c（3）a*c-b/c^2（4）(a+b)*c+d/(e+f)（5）(a+b)*(c*d+e)-a*c【參考解答】（1）ab+cd+/（2）b2^4a*c*-（3）ac*bc2^/-（4）ab+c*def+/+（5）ab+cd*e+*ac*-3.13編程實(shí)現(xiàn)利用隊(duì)列將棧中元素逆置的算法?！緟⒖冀獯稹縯emplate<classT>voidSeqStack<T>::Reverse(){ SeqQueue<T>sq(maxTop+1); Ttemp;

while(!IsEmpty()){ Top(temp); Pop(); sq.EnQueue(temp); } while(!sq.IsEmpty()){ sq.Front(temp); sq.Dequeue(); Push(temp); }}第四章數(shù)組和字符串行優(yōu)先順序/列優(yōu)先順序存儲(chǔ)數(shù)組存儲(chǔ)地址的計(jì)算稀疏矩陣的存儲(chǔ)： 行三元組、列三元組稀疏矩陣的快速轉(zhuǎn)置： 行三元組，k[]、num[]數(shù)組4.2給出三維數(shù)組元素A[i][j][k]的存儲(chǔ)地址loc(A[i][j][k])。解：設(shè)0≤i≤m1,0≤j≤m2,0≤k≤m3,每個(gè)數(shù)組元素占c個(gè)存儲(chǔ)單元，則行優(yōu)先順序的存儲(chǔ)地址：4.6給出下列稀疏矩陣的行優(yōu)先和列優(yōu)先順序存儲(chǔ)的行三元組和列三元組表示?！緟⒖冀獯稹苛腥M為

4.7求對(duì)題圖4-1的稀疏矩陣執(zhí)行矩陣轉(zhuǎn)置時(shí)數(shù)組num[]和k[]的值。col01234num[col]10212k[col]01134行三元組為：

第五章樹(shù)樹(shù)的基本概念——雙親、孩子、度、層次樹(shù)不能為空樹(shù)，森林可以為空森林樹(shù)和二叉樹(shù)的區(qū)別：P80二叉樹(shù)的性質(zhì)：性質(zhì)5.1——5.4滿(mǎn)二叉樹(shù)、完全二叉樹(shù)（性質(zhì)）二叉樹(shù)類(lèi)的實(shí)現(xiàn)——二叉鏈表二叉樹(shù)的遍歷——先序/后序/中序（遞歸算法）二叉樹(shù)遍歷的應(yīng)用實(shí)例

——二叉樹(shù)復(fù)制Copy

——求二叉樹(shù)結(jié)點(diǎn)數(shù)Size

——釋放一棵二叉樹(shù)所有結(jié)點(diǎn)Clear二叉樹(shù)和樹(shù)/森林的互相轉(zhuǎn)換哈夫曼樹(shù)構(gòu)造、哈夫曼編碼、加權(quán)路徑長(zhǎng)度WPL計(jì)算

5.2對(duì)于三個(gè)結(jié)點(diǎn)A，B和C，可分別組成多少不同的無(wú)序樹(shù)、有序樹(shù)和二叉樹(shù)？（1）無(wú)序樹(shù)：9棵（2）有序樹(shù)：12棵（3）二叉樹(shù)：30棵3棵6棵6棵6棵各6棵5.4高度為h的滿(mǎn)k叉樹(shù)有如下性質(zhì)：第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上的結(jié)點(diǎn)的度均為k。如果按從上到下，從左到右子樹(shù)的次序?qū)?shù)中結(jié)點(diǎn)從1開(kāi)始編號(hào)。（1）各層的結(jié)點(diǎn)數(shù)目是多少?（2）編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號(hào)是多少?（3）編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少?（4）編號(hào)為i的結(jié)點(diǎn)的有右兄弟的條件是什么?【參考解答】(1)第i層的結(jié)點(diǎn)數(shù)目為ki-1(2)編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為也即：(3)編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)編號(hào)是：(4)編號(hào)為i的結(jié)點(diǎn)有右兄弟的條件是即：，也即i-1不能被k整除。

5.5找出所有二叉樹(shù)，其結(jié)點(diǎn)在下列兩種次序下恰好都以同樣的次序出現(xiàn)。（1）先序和中序；（2）先序和后序；（3）中序和后序【參考解答】（1）空二叉樹(shù)和所有結(jié)點(diǎn)均無(wú)左孩子的二叉樹(shù)（2）空二叉樹(shù)和只有一個(gè)根的二叉樹(shù)（3）空二叉樹(shù)和所有結(jié)點(diǎn)均無(wú)右孩子的二叉樹(shù)5.6設(shè)對(duì)一棵二叉樹(shù)進(jìn)行中序遍歷和后序遍歷的結(jié)果分別為：

（1）中序遍歷（BDCE）A

（FHG）

（2）后序遍歷（DECB）（HGF）A

畫(huà)出該二叉樹(shù)。ABFCDEGH5.7寫(xiě)出下圖中二叉樹(shù)的先序、中序和后序遍歷結(jié)果先序：DEHFJGCKAB中序：HEJFGKCDAB后序：HJKCGFEBADDEAFJGBCHK5.9設(shè)二叉樹(shù)以二叉鏈表存儲(chǔ)，試編寫(xiě)求解下列問(wèn)題的遞歸算法

（1）完成刪除一棵二叉樹(shù)，并釋放所有的結(jié)點(diǎn)空間template<classT>voidBinaryTree<T>::Clear()//public{ Clear(root);}template<classT>voidBinaryTree<T>::Clear(BTNode<T>*t)//private{

if(t){

Clear(t->lChild); Clear(t->rChild); deletet; }}（2）求一棵二叉樹(shù)中的度為1的結(jié)點(diǎn)個(gè)數(shù)；template<classT>intBinaryTree<T>::CountDegree1()//public{returnCountDegree1(root); }template<classT>intBinaryTree<T>::CountDegree1(BTNode<T>*t)//private{if(t){if(t->lChild&&!t->rChild||!t->lChild&&t->rChild)

returnCountDegree1(t->lChild)+CountDegree1(t->rChild)+1; elseif(t->lChild&&t->rChild) returnCountDegree1(t->lChild)+CountDegree1(t->rChild); elsereturn0;}elsereturn0;}（3）設(shè)計(jì)算法，交換一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)。template<classT>voidBinaryTree<T>::Exchange()

//public{ Exchange(root);}template<classT>voidBinaryTree<T>::Exchange(BTNode<T>*t)

//private{ if(t){

BTNode<T>*q=t->lChild; t->lChild=t->rChild; t->rChild=q; Exchange(t->lChild); Exchange(t->rChild); }}補(bǔ)充：P89-90

（1）Size()函數(shù)求二叉樹(shù)結(jié)點(diǎn)數(shù)

（2）Copy()函數(shù)實(shí)現(xiàn)二叉樹(shù)復(fù)制

（3）Clear()函數(shù)舉例：Clear函數(shù)template<classT>voidBinaryTree<T>::Clear(BTNode<T>*t){if(t){Clear(t->lChild);Clear(t->rChild);cout<<"delete"<<t->element<<"..."<<endl;deletet;}}5.14將上圖中的樹(shù)轉(zhuǎn)換成二叉樹(shù)，并將下圖中的二叉樹(shù)轉(zhuǎn)換成森林。5.19設(shè)S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，對(duì)字符集合進(jìn)行哈夫曼編碼，W為各字符的頻率

（1）畫(huà)出哈夫曼樹(shù)

（2）計(jì)算帶權(quán)路徑長(zhǎng)度

（3）求各字符的編碼A: 1010B: 1011C: 100D: 00E: 01F: 11加權(quán)路徑長(zhǎng)度：WPL=(2+3)×4+5×3+(7+9+12)×2=91

第六章集合與搜索順序搜索算法 搜索有序表/無(wú)序表，順序存儲(chǔ)/鏈接存儲(chǔ)二分搜索算法

適用于順序存儲(chǔ)的有序表。二叉判定樹(shù)平均搜索長(zhǎng)度的計(jì)算方法6.5設(shè)計(jì)一個(gè)遞歸算法，實(shí)現(xiàn)對(duì)一個(gè)有序表的順序搜索template<classT>intSeqList<T>::Search4(constT&x)const{elements[length]=1000;returnSch4(x,0);}template<classT>intSeqList<T>::Sch4(constT&x,inti)const{if(x<elements[i])return0;elseif(x==elements[i])return++i; elsereturnSch4(x,i+1);}6.6設(shè)有序表用單鏈表表示，設(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)對(duì)有序表的順序搜索。template<classT>ResultCodeListSet<T>::Search(T&x){ Node<T>*p=first; while(p&&p->element<x) p=p->link; if(p&&p->element==x) returnSuccess; else returnNotPresenst;}6.10畫(huà)出對(duì)長(zhǎng)度為12的有序表進(jìn)行對(duì)半搜索的二叉判定樹(shù)，并求等概率搜索時(shí)，成功搜索情況下的平均搜索長(zhǎng)度。ASL成功=1/12（1*1+2*2+3*4+4*5）=37/12ASL失敗=1/13（3*3+4*10）=49/1352803610147119-125013468791011第七章搜索樹(shù)二叉搜索樹(shù)——中序遍歷二叉搜索樹(shù)可得遞增排序有序序列二叉搜索樹(shù)的插入、刪除操作時(shí)間復(fù)雜度分析

——平均情況下,O(log2n)

——最壞情況下“退化”樹(shù)形，O(n)由搜索結(jié)果可反向推得二叉搜索樹(shù)B樹(shù)m階B-樹(shù)的定義：P147B-樹(shù)的性質(zhì)B-樹(shù)的插入、刪除操作7.1建立以37，45，91，25，14，76，56，65為輸入的二叉搜索樹(shù)，再?gòu)脑摌?shù)上依次刪除76，45，畫(huà)出結(jié)果。37254591147656653725911456657.3已知對(duì)一棵二叉搜索樹(shù)進(jìn)行先序遍歷的結(jié)果是：28，25，36，33，35，34，43，請(qǐng)畫(huà)出此二叉搜索樹(shù)。282536353334437.55階B_樹(shù)的高度為2時(shí)，樹(shù)中元素個(gè)數(shù)最少為多少？至少有5個(gè)元素7.16(1)

從空樹(shù)開(kāi)始，以關(guān)鍵字序列 a,g,f,b,k,d,h,m,j,e,s,i,r,x,

建立一棵4階B_樹(shù)。7.17從上題的B_樹(shù)中刪除a,e,f,h1）刪除afdebhkrgijmsx2)刪除efdbhkrgijmsxfbdkrgijmsxh3)刪除f4)刪除hdkrgijmsxhbdkrgmsxibj第八章跳表和散列表散列函數(shù)與沖突除留余數(shù)法散列函數(shù)解決沖突的兩種開(kāi)地址法：

——拉鏈法

——開(kāi)地址法（線(xiàn)性探查法、二次探查法、雙散列法）8.3設(shè)有散列表ht[11]，散列函數(shù)為h(key)=key%11，采用線(xiàn)性探測(cè)和二次探測(cè)法處理沖突，試用關(guān)鍵字序列70，25，80，35，60，45，50，55分別建立散列表。線(xiàn)性探查法：Keyh(Key)7042538033526054515065500551452353254705806607508910Keyh(Key)7042538033526054515065500551452353254705806607508910二次探查法Keyh(Key)70425380335260545150655004513528032547056065075589108.3設(shè)有散列表ht[11]，散列函數(shù)為h(key)=key%11，采用線(xiàn)性探測(cè)和二次探測(cè)法處理沖突，試用關(guān)鍵字序列70，25，80，35，60，45，50，55分別建立散列表。8.4對(duì)上題的例子，若采用雙散列法，試以散列函數(shù)h1(key)=keymod11，h2(key)=keymod9+1建立散列表。雙散列法Keyh1(Key)7042538033526054515065500551802353254705606457508910Keyh2(Key)7025809356045150655第九章圖圖的基本概念——有向圖、無(wú)向圖、頂點(diǎn)、邊、連通分量、強(qiáng)連通分量、出/入度、生成樹(shù)、網(wǎng)圖的兩種表示方法：鄰接矩陣、鄰接表鄰接表的構(gòu)建和實(shí)現(xiàn)已知鄰接表，計(jì)算各頂點(diǎn)的入度（9.4題）圖的遍歷算法

——深度優(yōu)先搜索DFS

——寬度優(yōu)先搜索BFS拓?fù)渑判蛩惴ˋOV網(wǎng)拓?fù)渑判虿襟E拓?fù)湫蛄凶钚〈鷥r(jià)生成樹(shù)Prim算法9.1對(duì)如圖所示的有向圖，求：

(1)每個(gè)頂點(diǎn)的入度和出度；

(2)強(qiáng)連通分量；

(3)鄰接矩陣。324150(1)各個(gè)頂點(diǎn)的入度和出度頂點(diǎn) 入度出度0 3 01 2 22 1 23 1 14 2 35 1 22415(2)強(qiáng)連通分量(3)鄰接矩陣00 00 0010 00 0001 00 1010 00 0011 01 0000 10 10309.2從只有6個(gè)頂點(diǎn)沒(méi)有邊的圖開(kāi)始，以邊<1,0>,<1,3>,<2,1>,<2,4>,<3,2>,<3,4>,<4,0>,<4,1>,<4,5>,<5,0>的次序建立鄰接表結(jié)構(gòu)。畫(huà)出鄰接表。52413005012345034402110123459.4已知有向圖的鄰接表，寫(xiě)出計(jì)算各個(gè)頂點(diǎn)的入度的算法。template<classT>voidLinkedGraph<T>::Degree(){int*d=newint[n];inti;Enode<T>*p;

for(i=0;i<n;i++)d[i]=0;

for(i=0;i<n;i++) for(p=a[i];p;p=p->nextArc) d[p->adjVex]++;for(i=0;i<n;i++)cout<<“d[“<<i<<“]=“<<d[i]; }9.6在題9.2所建立的鄰接表上進(jìn)行以頂點(diǎn)2為起點(diǎn)頂點(diǎn)的深度優(yōu)先搜索和寬度優(yōu)先搜索。分別畫(huà)出遍歷所得到的深度優(yōu)先搜索和寬度優(yōu)先搜索的生成森林（或生成樹(shù)）。在題9.2所建立的鄰接表對(duì)應(yīng)的圖為：5241300501234503440211012345以頂點(diǎn)2為起點(diǎn)頂點(diǎn)的深度優(yōu)先搜索所得到深度優(yōu)先搜索生成樹(shù)：0501234503440211012345524130以頂點(diǎn)2為起點(diǎn)頂點(diǎn)的寬度優(yōu)先搜索所得到寬度優(yōu)先搜索生成樹(shù)：52413005012345034402110123459.13設(shè)有邊集合：<0,1>，<1,2>，<4,1>，<4,5>，<5,3>，<2,3>，（1）求此圖的所有可能的拓?fù)湫蛄?；?）此圖的所有可能的拓?fù)湫蛄校?412530415230451234012534015234051234501235241309.13設(shè)有邊集合：<0,1>，<1,2>，<4,1>，<4,5>，<5,3>，<2,3>，（2）若以此為順序通過(guò)加入邊的方式建立鄰接表，則在該鄰接表上執(zhí)行教材給定的拓?fù)渑帕兴惴ǎ═opoSort），將得到何種拓?fù)湫蛄?？?）得到拓?fù)湫蛄校?412532501234531310123459.17使用普里姆算法，以1為源點(diǎn)，畫(huà)出下面無(wú)向圖的最小代價(jià)生成樹(shù)。2134507612312544333解：構(gòu)造最小代價(jià)生成樹(shù)的過(guò)程如下：1212210232130233213502323213450231232134507123123213450761231243第10章內(nèi)排序三種簡(jiǎn)單排序算法快速排序兩路合并排序算法的：過(guò)程時(shí)間復(fù)雜度穩(wěn)定性最好情況平均情況最壞情況穩(wěn)定性簡(jiǎn)單選擇排序O(n2)O(n2)O(n2)不穩(wěn)定冒泡排序

O(n)O(n2)O(n2)穩(wěn)定直接插入排序O(n)O(n2)O(n2)穩(wěn)定快速排序

O(nlog2n)O(nlog2n)O(n2)不穩(wěn)定兩路合并排序O(nlog2n)O(nlog2n)O(nlog2n)穩(wěn)定10.1五種內(nèi)排序算法的排序過(guò)程

（1）簡(jiǎn)單選擇排序——每趟確定一個(gè)最小元素位置，最好/最壞/平均情況時(shí)間復(fù)雜度一樣

（2）直接插入排序——排序結(jié)束前，都不能確定任何一個(gè)元素位置，偏愛(ài)有序序列

（3）冒泡排序——某趟沒(méi)有交換元素時(shí)可停止，偏愛(ài)有序序列。

（4）快速排序——”哨兵“，偏愛(ài)基本無(wú)序序列

（5）兩路合并排序——必須借助一個(gè)與原序列等大小的輔助數(shù)組實(shí)現(xiàn)，輔助存儲(chǔ)空間O(n)。10.1元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，寫(xiě)給出各趟排序結(jié)果。（1）簡(jiǎn)單選擇排序初始序列61871203087097755326第1趟（03）871261087097755326第2趟（0308）1261877097755326第3趟（030812）61877097755326第4趟（03081226）877097755361第5趟（0308122653）7097758761第6趟（030812265361）97758770第7趟（03081226536170）758797第8趟（0308122653617075）8797第9趟（030812265361707587）9710.1元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，寫(xiě)給出各趟排序結(jié)果。（2）冒泡排序（注意冒泡排序只排了7趟）初始序列(61871203087097755326)第1趟61120308708775532697第2趟12030861707553268797第3趟03081261705326758797第4趟03081261532670758797第5趟03081253266170758797第6趟03081226536170758797第7趟03081226536170758797（3）直接插入排序初始序列（61）871203087097755326第1趟（6187）1203087097755326第2趟（126187）03087097755326第3趟（03126187）087097755326第4趟（0308126187）7097755326第5趟（030812617087）97755326第6趟（03081261708797）755326第7趟（0308126170758797）5326第8趟（030812536170758797）26第9趟（03081226536170758797）10.1元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，寫(xiě)給出各趟排序結(jié)果。（4）快速排序初始序列61871203087097755326第1趟(53261238)61(97757087)第2趟(826123)5361(97757087)第3趟(3)8(1226)5361(97757087)第4趟3812(26)5361(97757087)第5趟3812265361(877570)97第6趟3812265361(7075)8797第7趟381226536170(75)879710.1元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，寫(xiě)給出各趟排序結(jié)果。（5）兩路合并排序初始序列（61)(87)(12)(03)(08)(70)(97)(75)(53)(26)第1趟(6187)(0312)(0870)(7597)(2653)第2趟(03126187)(08707597)(2653)第3趟(0308126170758797)(2653)第4趟(03081226536170758797)10.1元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，寫(xiě)給出各趟排序結(jié)果。（1）最好、最壞和平均情況下的時(shí)間復(fù)雜度：簡(jiǎn)單選擇排序:三種情況下的時(shí)間復(fù)雜度都為O(n2)。直接插入排序：最好情況下為O(n)；平均和最壞情況下為O(n2)。冒泡排序：最好情況為O(n)；最壞和平均情況下為O(n2)。快速排序：最好和平均情況下為O(nlog2n)；最壞情況下時(shí)間復(fù)雜度為O(n2)。兩路合并排序：三種情況下，均為O(nlog2n)10.2從以下幾個(gè)方面比較上題各種排序算法。（1）最好、最壞和平均情況下的時(shí)間復(fù)雜度；（2）空間復(fù)雜度；（3）穩(wěn)定性（對(duì)不穩(wěn)定的算法給出一個(gè)簡(jiǎn)單的實(shí)例）；（4）指出第一趟排序結(jié)束后就能確定某個(gè)元素最終位置的算法。（2）空間復(fù)雜度：簡(jiǎn)單選擇排序、直接插入排序和冒泡排序都是O(1)快速排序：最好情況，空間復(fù)雜度為O(log2n)；最壞情況，空間復(fù)雜度為O(n)兩路合并排序:均為O(n)10.2從以下幾個(gè)方面比較上題各種排序算法。（1）最好、最壞和平均情況下的時(shí)間復(fù)雜度；（2）空間復(fù)雜度；（3）穩(wěn)定性（對(duì)不穩(wěn)定的算法給出一個(gè)簡(jiǎn)單的實(shí)例）；（4）指出第一趟排序結(jié)束后就能確定某個(gè)元素最終位置的算法。（3）穩(wěn)定性：不穩(wěn)定的是簡(jiǎn)單選擇排序和快速排序兩種，其它是穩(wěn)定的。實(shí)例：331簡(jiǎn)單選擇排序過(guò)后變成了133，

343快速排序之后變成了33410.2從