數(shù)據(jù)結(jié)構(gòu)作業(yè)答案教學(xué)課件

數(shù)據(jù)結(jié)構(gòu)(DataStructure)作業(yè)第1章緒論1.簡述下列術(shù)語:數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)結(jié)構(gòu)、物理結(jié)構(gòu)、數(shù)據(jù)類型。2.什么是算法?算法有哪些特性?如何判斷一個算法的好壞?3由大到小排列以下函數(shù)的復(fù)雜度:210,(3/2),(2/3)n,1og2,log2(log2n),n,n2,nl,n2/3,n3,n3/24.按照數(shù)據(jù)結(jié)構(gòu)的數(shù)學(xué)表示,畫出其圖示。B=(D,S)D={k1,k2,k3,…,k9}S={<k1,k3>,<k1,k8>,<k2,k3),<k2,k4>,<k2,k5),<k3,k9>,<k4,k7>,<k4,k6>,<k5,k6》,<k8,k9》,<k9,k7》}第1章緒論5.按照數(shù)據(jù)結(jié)構(gòu)的圖示,寫出其數(shù)學(xué)表示。第1章緒論6.求下面程序的時間復(fù)雜度。(1)s=0for(i=0;i<n;i++)for(j=0;j皿;j+)s+=B[i][j];(2)i=1while(i<en)i*=3;(3)i=s=0;while(s<n)is+=1第1章作業(yè)答案2.略3.由大到小排列以下函數(shù)的復(fù)雜度!>2)(3/2)>n3)n2n3/2n>n2/3)log2n>log2(log2n)>(2/3)n4.5.略0(m*n)0(1og3n)0(n)第2章線性表(Linearlist)1.將線性表中的元素以第一個元素的key為界劃分成兩部分,要求排在分界元素之前的元素,其key值都比分界元素小,而排在其后的元素,其key值都比分界元素大2.以鏈表的表頭元素為界把鏈表劃分成兩部分,要求鏈接在分界元素之前的元素,其key值都比分界元素小而鏈接在其后的元素,其key值都比分界元素大。第2章作業(yè)答案(1)typedefstructintKeyInfoTypeinfoRElenTvoidSqPartition(sglist&L)Iinti,j:ElemTypetempl,temp2temp1L.elem[0];//初始分界元素在下標(biāo)0的位置for(i=1;i<Llength;i++)if(Lelem[i].key<temp1.key)//小于分界元素tenp2=L.elem[i];//暫存temp2中for(j=i;j>0;j-)L.elem[j=.elem[j-1];//L.elem[i]左方的元素右移位L.elen[0]=temp2;//L->elen[i放到最左方第2章作業(yè)答案(2)voidLkPartition(LinkList&L)LNode*p,*g,*temptemp=p-head;//分界結(jié)點為初始時的鏈頭結(jié)點while(p->next)/當(dāng)鏈表未完*if(p->next->data.key<temp->data.key)//Eu結(jié)點較小q=p>next;//當(dāng)前結(jié)點暫存指針q中p->next=q>next;//從鏈表中刪去結(jié)點pq>next=L;//將結(jié)點q與鏈頭指針head鏈接L=q;/結(jié)點q做新鏈頭esep=p->next//指針后移第3章棧與隊列1.若按右圖所示的鐵路調(diào)度棧進行車廂調(diào)度(兩側(cè)鐵道均為單向行使道)請回答:出棧進棧)如果進站的車廂序列為123,則可能得到的出站車廂序列是什么?(2)如果進站的車廂序列為123456則能否得到435612和135426的出站序列,并說明不能得到或者如何得到(寫出以S表示進棧和以X表示出棧的操作序列)(3)假設(shè)調(diào)度棧入口處有節(jié)硬席車廂或軟席車廂(分別以和表示)等待調(diào)度,編寫算法,輸出對這節(jié)車廂進行調(diào)度的操作(即入棧和出棧操作)序列,以使所有的硬席車廂都被調(diào)整到軟席車廂前面。第3章棧與隊列2.計算下列表達式的值(1)前綴表達式:米*76-/821(2)中綴表達式:8*9-(16-4)/2+5(3)后綴表達式:576*82+5/—*3.進行表達式的轉(zhuǎn)換(1)前綴:/++AB凇C+DEF+(*HI,轉(zhuǎn)中綴、后綴(2)中綴:(A+B)+E/(F+A枘)4C,轉(zhuǎn)前綴、后綴(3)后綴:AC-D/EAB*+/+,轉(zhuǎn)前綴序、中綴4.編寫遞歸函數(shù)完成下面公式的計算0m=0,n>=0g(m-1,2n)+n>0,n>=0假設(shè)稱