數(shù)據(jù)結(jié)構(gòu)課后答案鄒嵐

填空題數(shù)據(jù)元素關(guān)系邏輯結(jié)構(gòu)物理結(jié)構(gòu)順序存儲鏈式存儲索引存儲哈希存儲線性結(jié)構(gòu)樹圖集合數(shù)據(jù)描述操作聲名聯(lián)系圖樹數(shù)據(jù)元素數(shù)據(jù)元素有窮性確定性可行性輸入輸出正確性可讀性健壯性效率與存儲量的要求O（n）時間空間O（n）O（m*n）O（n）時間復(fù)雜度空間復(fù)雜度選擇題1-5BACAD6-10BCCB11-15BBACB16-20BDDAA21-23ACB判斷題FT簡答題1、數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)；常用的存儲方式有順序存儲、鏈式存儲、索引存儲和哈希存儲2、例如有一張學(xué)生成績表，記錄了一個班的學(xué)生各門課的成績。按學(xué)生的姓名為一行記成的表。這個表就是一個數(shù)據(jù)結(jié)構(gòu)。每個記錄(有姓名，學(xué)號，成績等字段)就是一個結(jié)點，對于整個表來說，只有一個開始結(jié)點(它的前面無記錄)和一個終端結(jié)點(它的后面無記錄)，其他的結(jié)點則各有一個也只有一個直接前趨和直接后繼(它的前面和后面均有且只有一個記錄)。這幾個關(guān)系就確定了這個表的邏輯結(jié)構(gòu)。那么我們怎樣把這個表中的數(shù)據(jù)存儲到計算機里呢?用高級語言如何表示各結(jié)點之間的關(guān)系呢?是用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機存放各結(jié)點數(shù)據(jù)再用指針進行鏈接呢?這就是存儲結(jié)構(gòu)的問題，我們都是從高級語言的層次來討論這個問題的。最后，我們有了這個表(數(shù)據(jù)結(jié)構(gòu))，肯定要用它，那么就是要對這張表中的記錄進行查詢，修改，刪除等操作，對這個表可以進行哪些操作以及如何實現(xiàn)這些操作就是數(shù)據(jù)的運算問題了。3、算法是描述求特定問題而規(guī)定的一系列操作步驟集合。特性包括：有窮性、確定性、可行性、有零個或多個輸入，有一個或多個輸出。4、a—b—c—d—e—f—g—h線性結(jié)構(gòu)(2)樹形結(jié)構(gòu)dagbhef（3）圖型結(jié)構(gòu)5、解：數(shù)據(jù)是對客觀事物的符號表示。在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示。數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。是對一般數(shù)據(jù)類型的擴展。6、解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。抽象數(shù)據(jù)類型通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進行的操作。在定義抽象數(shù)據(jù)類型中的數(shù)據(jù)部分和操作部分時，要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮數(shù)據(jù)的存儲結(jié)構(gòu)和操作的具體實現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。7、解：8、解：(1)n-1(2)n-1(3)n-1(4)n+(n-1)+(n-2)+...+1=(5)1+(1+2)+(1+2+3)+...+(1+2+3+...+n)===(6)n(7)向下取整(8)1100程序算法題（1）O(n)（2）O(n)（3）O(1)2、解：intmax3(intx,inty,intz){ if(x>y) if(x>z)returnx; elsereturnz; else if(y>z)returny; elsereturnz;}選擇題1-5CBABA6-10CACCC11-15ACBCC16-20ABBDD21-25DCADC26-30BBDDA31C判斷題1-5FFFFF6-10FFTFT11-15TTFFF16F三綜合應(yīng)用題1、(1)EmemtypeDelete(Elemtypea[],int&Length){Elemtypetag=0;Elemtypemin;if(Length==0)returnERROR;for(inti=1;i<Length-1;i++){if(a[tag]>a[i])tag=i;}min=a[tag];a[tag]=a[Length-1];Length--;returnmin;}(2)StatusListDelete_Sq(SqList*LA,inti,ElemType*e){/*在順序線性表L中刪除第i個元素，并用e返回其值//i的合法值為1≤i≤Listlength_Sq(L)*/ElemType*q,*p;intn=0;/*定義局部變量*/if((i<1)||(i>(*LA).length))returnERROR;/*i值不合法*/p=&((*LA).elem[i-1]);/*p為被刪除元素的位置*/*e=*p;/*被刪除元素的值賦給e*/q=(*LA).elem+(*LA).length-1;/*表尾元素的位置*/for(++p;p<=q;++p){*(p-1)=*p;++n;}/*被刪除元素之后的元素左移*/printf("n=%d\n",n);--(*LA).length;/*表長減1*/returnOK;}(3)StatusListInsert_Sq(SqList*LA,inti,ElemTypee){/*在順序線性表L中第i個位置之前插入新的元素e,//i的合法值為1≤i≤Listlength_Sq(L)+1*/ElemType*newbase,*q,*p;intn=0;/*定義局部變量*/if(i<1||i>(*LA).length+1)returnERROR;/*值不合法*/if((*LA).length>=(*LA).listsize){/*當前空間已滿，增加分配*/newbase=(ElemType*)realloc((*LA).elem,((*LA).listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);/*存儲分配失敗*/(*LA).elem=newbase;/*新基址*/(*LA).listsize+=LISTINCREMENT;}/*增加存儲容量*/q=&((*LA).elem[i-1]);/*q為插入位置*/for(p=&((*LA).elem[(*LA).length-1]);p>=q;--p){*(p+1)=*p;++n;}/*插入位置及之后的元素右移*/printf("n=%d\n",n);*q=e;/*插入e*/++(*LA).length;returnOK;}4、voiddel_x(Sqlist&L,Elemtypex){ intk=0; for(i=0;i<L.length;i++) if(L.data[i]!=x) { L.data[k]=L.data[i]; k++; } L.length=k;}（5）boolDel_s_t(sqList&L,Elemtypes,Elemtypet){ inti,k=0; if(L.length==0||s>=t) returnfalse; for(i=0;i<L.length;i++) { if(L.data[i]>=s&&L.data[i]<=t) k++; else L.data[i-k]=L.data[i]; } L.length-=k; returntrue;}（6）boolDel_s_t(sqList&L,Elemtypes,Elemtypet){ inti,j; if(L.length==0||s>=t) returnfalse; for(i=0;i<L.length&&L.data[i]<s;i++); if(i>=L.length) returnfalse; for(j=i;j<L.length&&L.data[j]<=t;j++); for(;j<L.length;i++,j++) L.data[i]=L.data[j] L.length=i; returntrue;}（7）boolMerge(SqListA,SqListb,SqList&c){ if(A.length+B.length>C.maxSize) returnfalse; inti=0,j=0,k=0; while(i<A.length&&j<B.length) { if(A.data[i]<=B.data[j]) C.data[k++]=A.data[i++]; else C.data[k++]=B.data[j++]; } while(i<A.length) C.data[k++]=A.data[i++]; while(j<B.length) C.data[k++]=B.data[j++]; C.length=k; returntrue;}（8）boolDelete_Same(SqList&L){ if(L.length==0) returnfalse; inti,j; for(i=0,j=1;j<L.length;j++) if(L.data[i]<L.data[j]) L.data[++i]=L.data[j]; L.length=i+1;}2、LinkedListinvert(LinkedListL){p=L->next；∥p為工作指針。L->next=null；∥第一結(jié)點成為尾結(jié)點。while（p!=null）{r=p->next；p->next=L；∥將p結(jié)點插到L結(jié)點前面。L=p；∥L指向新的鏈表“第一”元素結(jié)點。p=r；}returnL;}3、LinkListreverse(LinkList&L)//帶頭結(jié)點單鏈表的就地逆置{ p=L->next; L->next=null; while(p!=NULL) { r=p->next; p->next=L->next; L->next=p; p=r; } returnL;}4、voidMiniValue(LinkedListla){∥la是數(shù)據(jù)域為正整數(shù)且無序的單鏈表，本算法查找最小值結(jié)點且打印?！稳糇钚≈到Y(jié)點的數(shù)值是奇數(shù)，則與后繼結(jié)點值交換；否則，就刪除其直接后繼結(jié)點。p=la->next；∥設(shè)la是頭結(jié)點的頭指針，p為工作指針。pre=p；∥pre指向最小值結(jié)點，初始假定首元結(jié)點值最小。while(p->next!=null){∥p->next是待比較的當前結(jié)點。if（p->next->data<pre->data）pre=p->next；p=p->next；∥后移指針}printf(“最小值=%d\n”,pre->data)；if(pre->data%2!=0)∥處理奇數(shù)if(pre->next!=null){∥若該結(jié)點沒有后繼，則不必交換t=pre->data；pre->data=pre->next->data；pre->next->data=t；}∥交換完畢else∥處理偶數(shù)情況if(pre->next!=null){∥若最小值結(jié)點是最后一個結(jié)點，則無后繼u=pre->next；pre->next=u->next；free(u)；}∥釋放后繼結(jié)點空間}5、解法如下：假定鏈表結(jié)點類型如下;structnode{ intdata; node*next;};voidsort(node*head){ node*p=head->next; while(p) { node*q=p->next; while(q) { if(q->data<p->data)//把小的選出來放在前面 { head->data=p->data; p->data=q->data; q->data=head->data; } q=q->next; } p=p->next; }}6、LinkedListUnion(LinkedListla,LinkedListlb){∥la,lb分別是帶頭結(jié)點的兩個單鏈表的頭指針，鏈表中的元素值按遞增序排列，本算法將兩鏈表合并成一個按元素值遞減次序排列的單鏈表。pa=la->next;pb=lb->next;∥pa，pb分別是鏈表la和lb的工作指針la->next=null;∥la作結(jié)果鏈表的頭指針，先將結(jié)果鏈表初始化為空。while(pa!=null&&pb!=null)∥當兩鏈表均不為空時作if(pa->data<=pb->data){r=pa->next;∥將pa的后繼結(jié)點暫存于r。pa->next=la->next;∥將pa結(jié)點鏈于結(jié)果表中，同時逆置。la->next=pa;pa=r;∥恢復(fù)pa為當前待比較結(jié)點。}else{r=pb->next;∥將pb的后繼結(jié)點暫存于r。pb->next=la->next;∥將pb結(jié)點鏈于結(jié)果表中，同時逆置。la->next=pb;pb=r;∥恢復(fù)pb為當前待比較結(jié)點。}while(pa!=null){∥將la表的剩余部分鏈入結(jié)果表，并逆置。r=pa->next;pa->next=la->next;la->next=pa;pa=r;}while(pb!=null){r=pb->next;pb->next=la->next;la->next=pb;pb=r;}returnla;}7、voidDel_Same(LinkList&L){ LNode*p=L->next,*q; while(p->next!=null) { q=p->next; if(p->data==q->data) { p->next=q->next; free(q); } else p=p->next; }}8、LinkedListDelete（LinkedListL）

∥L是帶頭結(jié)點的單鏈表，本算法刪除其最小值結(jié)點。

{p=L->next；∥p為工作指針。指向待處理的結(jié)點。假定鏈表非空。

pre=L；∥pre指向最小值結(jié)點的前驅(qū)。

q=p；∥q指向最小值結(jié)點，初始假定第一元素結(jié)點是最小值結(jié)點。

while（p->next!=null）

{if（p->next->data<q->data）{pre=p；q=p->next；}∥查最小值結(jié)點

p=p->next；∥指針后移。

}

pre->next=q->next；∥從鏈表上刪除最小值結(jié)點

free（q）；∥釋放最小值結(jié)點空間

}∥結(jié)束算法delete。9、voidFun(Node**heada,Node**headb,inti,intj,intlen)

{

Node*p,*q,*r;

p=*heada;

q=*heada;

intn=1;

while(n++<i)

p=p->next;

q=p->next;

n=0;

while(n++<len&&q)

q=q->next;

r=p->next;

p->next=q->next;

q->next=NULL;

n=1;

p=*headb;

while(n++<j)

p=p->next;

q->next=p->next;

p->next=r;

}10、LinkedListdelinsert(LinkedListlist)

{

p=list->link;

pre=list;

q=p;

while(p->link!=null)

{

if(p->link->data<q->data)

{

pre=p;q=p->link;

}

if(q!=list->link)

{

pre->link=q->link;

q->link=list->link;

list->link=q;

}

}

}11、LinkedListUnion(LinkedListha,hb)//線性表A和B代表兩個集合，以鏈式存儲結(jié)構(gòu)存儲，元素遞增有序。ha和hb分別是其鏈表的頭指針。本算法求A和B的并集//AuB,仍用線性表表示，結(jié)果鏈表元素也是遞增有序{pa=ha->next;pb=hb->next;//設(shè)工作指針pa和pb pc=ha;//pb為結(jié)果鏈表當前結(jié)點的前驅(qū)指針while(pa&&pb) if(pa->data<pb->data) {pc->next=pa;pc=pa;pa=pa->next;} elseif(pa->data>pb->data) { pc->next=pb;pc=pb;pb=pb->next; } else//處理pa->data=pb->data {pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;free(u);} if(pa) pc->next=pa;//若ha表未空，則鏈入結(jié)果表。 elsepc->next=pb;//若hb表未空，則鏈入結(jié)果表 free(hb);//釋放hb頭結(jié)點 return(ha);}12、LinkedListUnion(LinkedListla,LinkedListlb){pa=la->next;pb=lb->next;∥設(shè)工作指針pa和pb；pc=la;∥結(jié)果表中當前合并結(jié)點的前驅(qū)的指針。while(pa&&pb){if(pa->data==pb->data){∥交集并入結(jié)果表中。pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;free(u);}elseif(pa->data<pb->data){u=pa;pa=pa->next;free(u);}else{u=pb;pb=pb->next;free(u);}}while(pa){u=pa;pa=pa->next;free(u);∥釋放結(jié)點空間}while(pb){u=pb;pb=pb->next;free(u);∥釋放結(jié)點空間}pc->next=null;∥置鏈表尾標記。free(lb);∥注：本算法中也可對B表不作釋放空間的處理returnla;}13、算法的基本設(shè)計思想：對兩個鏈表進行歸并，但當A的一個元素，不是B中的一個元素時，才將其加入到新鏈表C中。算法的代碼：NODE*difference(NODE*A,NODE*B){NODE*C,*last；C=last=(NODE*)malloc(sizeof(NODE))；while(A!=null&&B!=null){∥兩均未空時循環(huán)if(A->element<B->element){last=append(last,A->element)；A=A->link；}elseif(A->element==B->element){∥兩表中相等元素不作結(jié)果元素A=A->link；B=B->link；}elseB=B->link；∥向后移動B表指針}while(A!=null){last=append(last,A->element)；A=A->link；}last->link=null；∥置鏈表尾last=C；C=C->link；free(last)；returnC；}14、LinkedListLinkListInsertSort(LinkedListla){∥la是帶頭結(jié)點的單鏈表，其數(shù)據(jù)域是正整數(shù)。本算法利用直接插入原則將鏈表整理成遞增的有序鏈表。if(la->next!=null){∥鏈表不為空表。p=la->next->next;∥p指向第一結(jié)點的后繼。la->next->next=null;∥直接插入原則認為第一元素有序，從第二元素起依次插入。while(p!=null){r=p->next;∥暫存p的后繼。q=la;while(q->next!=null&&q->next->data<p->data)∥查找插入位置。q=q->next;p->next=q->next;∥將p結(jié)點鏈入鏈表。q->next=p;p=r;}}returnla;}15、LinkedListDisCreat(LinkedListA)∥A是帶頭結(jié)點的單鏈表，鏈表中結(jié)點的數(shù)據(jù)類型為整型。本算法將A分解成兩個單鏈表B和C，B中結(jié)點的數(shù)據(jù)小于零，C中結(jié)點的數(shù)據(jù)大于零。處理之后，B表的頭指針即為A表頭指針，只需返回C表頭指針即可。{B=A;C=(LinkedList)malloc(sizeof(LNode));∥為C申請結(jié)點空間。C->next=null∥C初始化為空表。p=A->next;∥p為工作指針。B->next=null;∥B表初始化。while(p!=null){r=p->next;∥暫存p的后繼。if(p->data<0){∥小于0的放入B表。p->next=B->next;B->next=p;∥將小于0的結(jié)點鏈入B表}else{p->next=C->next;C->next=p;}p=r;∥p指向新的待處理結(jié)點。}returnC;}16、LinkedListDisCreat(LinkedListA){∥A是帶頭結(jié)點的單鏈表，本算法將其分解成兩個帶頭結(jié)點的單鏈表，A表中含原表中序號∥為奇數(shù)的結(jié)點，B表中含原表中序號為偶數(shù)的結(jié)點。鏈表中結(jié)點的相對順序同原鏈表。i=0;∥i記鏈表中結(jié)點的序號。B=(LinkedList)malloc(sizeof(LNode);∥創(chuàng)建B表表頭。B->next=null;∥B表的初始化。LinkedListra,rb;∥ra和rb將分別指向?qū)?chuàng)建的A表和B表的尾結(jié)點。ra=A;rb=B;p=A->next;∥p為鏈表工作指針，指向待分解的結(jié)點。A->next=null;∥置空新的A表while(p!=null){r=p->next;∥暫存p的后繼。i++;if(i%2==0){∥處理原序號為偶數(shù)的鏈表結(jié)點。p->next=null;∥在B表尾插入新結(jié)點；rb->next=p;rb=p;∥rb指向新的尾結(jié)點；}else{∥處理原序號為奇數(shù)的結(jié)點。p->next=ra->next;ra->next=p;ra=p;}p=r;∥將p恢復(fù)為指向新的待處理結(jié)點。}returnB;}17、intPattern(LinkedListA，LinkedListB){∥A和B分別是數(shù)據(jù)域為整數(shù)的單鏈表，本算法判斷B是否是A的子序列。如是，返回1；∥否則，返回0表示不是。p=A；∥p為A鏈表的工作指針，本題假定A和B均無頭結(jié)點。pre=p；∥pre記住每趟比較中A鏈表的開始結(jié)點。q=B；∥q是B鏈表的工作指針。while(p&&q)if(p->data==q->data){p=p->next；q=q->next；}else{pre=pre->next；p=pre；∥A鏈表新的開始比較結(jié)點。q=B；}∥q從B鏈表第一結(jié)點開始。if(q==null)return1；∥B是A的子序列。elsereturn0；∥B不是A的子序列。}18、voidRearrange(SeqLista;intn){∥a是具有n個元素的線性表，以順序存儲結(jié)構(gòu)存儲，線性表的元素是整數(shù)。本算法重排線∥性表a，使所有值為負數(shù)的元素移到所有值為正數(shù)的數(shù)的前面。i=0;j=n-1;∥i,j為工作指針（下標），初始指向線性表a的第1個和第n個元素。t=a[0];∥暫存樞軸元素。while(i<j){while(i<j&&a[j]>=0)j--;∥若當前元素為大于等于零，則指針前移。if(i<j){∥將負數(shù)前移a[i]=a[j];i++;}while(i<j&&a[i]<0)∥當前元素為負數(shù)時指針后移。i++;if(i<j)a[j--]=a[i];∥正數(shù)后移。}a[i]=t;∥將原第一元素放到最終位置。此樞紐是為了減少交換次數(shù)，正負皆可。}19、voidderivative(ha){q=ha;pa=ha->next;while(pa!=null){∥遍歷到鏈表結(jié)束if(pa->exp==0){∥若指數(shù)為0，即本項為常數(shù)項q->next=pa->next;∥刪常數(shù)項free(pa);pa=q;}else{pa->coef=(pa->coef)*(pa->exp);pa->exp--;∥指數(shù)項減1q=pa;}∥前驅(qū)后移,或q->nextpa=pa->next;∥取下一元素}}20、voidAdjust(DLinkListL){DLinkListtail=L->prior,p=L->next；inti=0;while(p!=tail){i++;q=p->next;if(i%2==0){p->prior->next=q;q->prior=p->prior;tail->next->prior=p;p->next=tail->next;p->prior=tail;tail->next=p;}p=q;}}21、DLinkListlocate(DLinkListL，ElemTypex){∥L是帶頭結(jié)點的按訪問頻度遞減的雙向鏈表，本算法先查找數(shù)據(jù)x，∥查找成功時結(jié)點的訪問頻度域增1，最后將該結(jié)點按頻度遞減插入鏈表中適當位置。DLinkListp=L->next,q;∥p為L表的工作指針，q為p的前驅(qū)，用于查找插入位置。while(p&&p->data!=x)∥查找值為x的結(jié)點。p=p->next;if(!p){printf(“不存在值為x的結(jié)點\n”);returnNULL;}else{p->freq++;∥令元素值為x的結(jié)點的freq域加1。p->next->pred=p->pred;∥將p結(jié)點從鏈表上摘下。p->pred->next=p->next;q=p->pred;∥以下查找p結(jié)點的插入位置while(q!=L&&q->freq<p->freq)q=q->pred;p->next=q->next;q->next->pred=p;∥將p結(jié)點插入p->pred=q;q->next=p；}returnp;∥返回值為x的結(jié)點的指針}選擇題1-5CCCCB6-10DCDCB11-15CCBCA16-20BBBCC21-25CCBAD填空題兩端受限棧頂p->next=HS,HS=pHS=HS->next線性任何棧頂對頭隊尾棧頂棧底先進后出先進先出top==15O（1）ab+c*ef*h-qr+/+3+-134X*+2Y*3/-判斷題1-5TTTFF6-10TTTTT11T簡答題1、相同點是都屬于線性結(jié)構(gòu)，都是兩端受限的線性表，不同點是棧只能在棧頂進行插入和刪除操作，又稱為先進后出表，而隊列是在隊頭刪除，隊尾插入的線性結(jié)構(gòu)又稱先進先出表。2、真溢出是指存儲空間已滿的情況下繼續(xù)進行插入操作，假溢出指有存儲空間而不能進行插入操作。采用循環(huán)隊列結(jié)構(gòu)就是為了避免假溢出減少浪費空間。3、stack4、(1）棧中的數(shù)據(jù)元素逆置（2）如果棧中存在元素e，將其從棧中清除五、程序算法題1、typedefintDatatype;

typedefstructqueuenode

{

Datatypedata;

structqueuenode*next;

}QueueNode;//以上是結(jié)點類型的定義

typedefstruct

{

queuenoderear;

}LinkQueue;//只設(shè)一個指向隊尾元素的指針

voidInitQueue(LinkQueue&Q)

{

//置空隊：就是使頭結(jié)點成為隊尾元素

Q.rear=(queuenode*)malloc(sizeof(queuenode))

QueueNode*s;

Q->rear=Q->rear->next;//將隊尾指針指向頭結(jié)點

while(Q->rear!=Q->rear->next)//當隊列非空，將隊中元素逐個出隊

{

s=Q->rear->next;

Q->rear->next=s->next;

free(s);

}//回收結(jié)點空間

}

intEmptyQueue(LinkQueue&Q)

{//判隊空

//當頭結(jié)點的next指針指向自己時為空隊

returnQ->rear->next->next==Q->rear->next;

}

voidEnQueue(LinkQueue&Q,Datatypex)

{//入隊

//也就是在尾結(jié)點處插入元素

QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申請新結(jié)點

p->data=x;p->next=Q->rear->next;//初始化新結(jié)點并鏈入

Q-rear->next=p;

Q->rear=p;//將尾指針移至新結(jié)點

}

DatatypeDeQueue(LinkQueue&Q,Datatype&x)

{

//出隊,把頭結(jié)點之后的元素摘下

Datatypet;

QueueNode*p;

if(EmptyQueue(Q))

Error("Queueunderflow");

p=Q->rear->next->next;//p指向?qū)⒁碌慕Y(jié)點

x=p->data;//保存結(jié)點中數(shù)據(jù)

if(p==Q->rear)

{//當隊列中只有一個結(jié)點時，p結(jié)點出隊后，要將隊尾指針指向頭結(jié)點

Q->rear=Q->rear->next;Q->rear->next=p->next;

}

else

Q->rear->next->next=p->next;//摘下結(jié)點p

free(p);//釋放被刪結(jié)點

returnx;

}2、#include"stdio.h"

voidout(intnum)

{inti=0;

if(num==1)

{

printf("%d",num);

}

else

{

for(i=1;i<=num;i++)

{

printf("%d",num);

}

printf("\n");

out(--num);

}

}

voidmain()

{

out(9);

getch();}3、解：因為輸入序列是從小到大排列的，所以若pj<pk<pi，則可以理解為通過輸入序列pjpkpi可以得到輸出序列pipjpk，顯然通過序列123是無法得到312的，所以不可能存在著i<j<k使pj<pk<pi。4、解：BC=GG/D=HA-H=IE^F=JI+J=K步驟OPTR棧OPND棧輸入字符主要操作1#A-B*C/D+E^F#PUSH(OPND,A)2#A-B*C/D+E^F#PUSH(OPTR,-)3#-AB*C/D+E^F#PUSH(OPND,B)4#-AB*C/D+E^F#PUSH(OPTR,*)5#-*ABC/D+E^F#PUSH(OPND,C)6#-*ABC/D+E^F#Operate(B,*,C)7#-AG/D+E^F#PUSH(OPTR,/)8#-/AGD+E^F#PUSH(OPND,D)9#-/AGD+E^F#Operate(G,/,D)10#-AH+E^F#Operate(A,-,H)11#I+E^F#PUSH(OPTR,+)12#+IE^F#PUSH(OPND,E)13#+IE^F#PUSH(OPTR,^)14#+^IEF#PUSH(OPND,F)15#+^IEF#Operate(E,^,F)16#+IJ#Operate(I,+,J)17#K#RETURN5、解答1.#definem01002./*m0為算術(shù)表達式中最多字符個數(shù)*/3.decpair(exp,flag)4.charexp［m0］;5.intflag;//flag用于標識是否匹配，flag=0標識不匹配，flag＝1標識匹配6.{7.charst［m0］;8.inttop=0,i=1;9.flag=1;10.while(i<=m0&&tag)11.{12.if(exp［i］=='('‖exp［i］=='［'‖exp［i］=='{'13./*遇到'('、'［'或'{'，則將其入棧*/14.{15.top++;16.st［top］=exp［i］;17.}18.if(exp［i］==')')/*遇到')'，若棧頂是'('，19.則繼續(xù)處理，否則以不配對返回*/20.if(st［top］=='(')top--;21.elseflag=0;22.if(exp［i］=='］')/*遇到')'，若棧頂是'［'，23.則繼續(xù)處理，否則以不配對返回*/24.if(st［top］=='［')top--;25.elseflag=0;26.if(exp［i］=='}')/*遇到')'，若棧頂是'{'，27.則繼續(xù)處理，否則以不配對返回*/28.if(st［top］=='{')top--;29.elseflag=0;30.i++;31.}32.if(top>0)flag=0;/*若棧不空，則不配對*/33.}6、解：假設(shè)隊列為循環(huán)順序隊列。建立一個臨時隊列，將指定隊列中所有元素出隊并入隊到臨時隊列中，這樣指定隊列為空，再將臨時隊列中所有元素出隊并入隊到指定隊列(因為不能破壞原隊列結(jié)構(gòu)，所以需要恢復(fù)元素)，最后一個元素即為所求。具體算法如下：datatypelastelem(queue*Q){datatypex；queuetmpQ；initqueue(&tmpQ)while(!emty(Q))//將Q中元素放入tmpQ{x=dequeue(Q)enqueue(&tmpQ，x)；}while(!empty(&tmpQ))//將tmpQ中元素恢復(fù)回Q{x=dequeue(&tmpQ)；enqueue(Q，x)；}returnx；}7、解：隊列為空：count==0

隊列為滿：count=MAXLEN

隊尾第一個元素位置==(front+count)%MAXLEN

隊首第一個元素位置==(front+1)%MAXLEN

const

MAXLEN=100;

int

queue[MAXLEN];

int

front,count;

//

定義隊頭和計數(shù)器count

（1）初始化隊列

void

init()

{

front=1;

count=0;

}

（2）判定隊空

int

QEmpty()

{

if

(count==0)

return(1);

else

return(0);}

（3）讀隊頭元素

void

ReadFront(int

queue[],x)

{

if

(count==0)

printf("

下溢出\n");

else

{

front=(front+1)%MAXLEN;

x=queue[front];

}

}（4）入隊操作

void

InQueue(int

queue[],int

x)

{

int

place;

if

(count==MAXLEN)

printf("

上溢出\n");

else

{

count++;

place=(front+count)%MAXLEN;

queue[MAXLEN]=x;

}

}

（5）出隊操作

void

OutQueue(int

queue[])

//

刪除隊列頭元素

{

if

(count==0)

printf("

隊列下溢出\n");

else

{

front=(front+1)%MAXLEN;

count--;

}

}

8、解析：定義本題隊列類型如下：typedefstruct{linklist*rear;}Queue2(1)隊列中人隊操作是在隊尾進行，即在鏈尾插入一個新結(jié)點。voidenqueue(Queue2*Q，datatypex){linklist*s；s＝(linklist*)malloe(sizeof(linklist))；//建立新結(jié)點s—>datda=x；s—>next=Q—>rear—>next；//將新結(jié)點插入隊尾q—>rear—>next=s；q—>rear=s；}(2)隊列中出隊操作是在隊頭進行，即刪除鏈表第一個數(shù)據(jù)結(jié)點。datatypedequeue(Queue2*Q){datatypex；linklist*p；if(Q—>rear—>next==Q—>rear)//隊列為空returnNULL；p＝Q一>rear一>next一>next；//p指向隊頭結(jié)點x=p一>data；Q一>rear一>next一>next＝p一>next//刪除*p結(jié)點free(p)returnx；//返回原隊頭元素}串選擇題A2.C3.C4.D5.D6.D7.B8.D9.A10.C11.D12.D填空題長度為零的串字符串元素只有空格的串子串主串簡答題1.答：長度為0的串稱為空串；由一個或多個空格組成的串稱為空格串?？崭褚彩谴淖址现械囊粋€元素。2.答：雖然串是由字符組成的，但串和字符是兩個不同的概念。串是長度不確定的字符序列，兒子富只是一個字符，即使是長度為1的串也與字符不同。例如，串“a”和字符‘a(chǎn)’就是兩個不同的概念，因為在執(zhí)行時串的結(jié)尾通常加上串結(jié)束標志“\0”。答：串的順序存儲結(jié)構(gòu)是用一維數(shù)組存放串中的字符，用靜態(tài)內(nèi)存分配的方法定義數(shù)組，數(shù)組元素在編譯時是確定的，在運行時是不可改變的稱為靜態(tài)順序存儲，用動態(tài)內(nèi)存分配方法定義數(shù)組，數(shù)組元素個數(shù)是在程序運行時用戶申請確定的稱為動態(tài)順序存儲。4.StatusStrDelete(String&S,inti,intj){intlen;len=j-i+1;if(i<1||i>s[0]||j>s[0])returnERROR;S[pos..S[0]-len]=S[pos+len..S[0]];S[0]=S[0]-len;ReturnOK;}一．選擇題1.B2.A3.C4.B5.D6.D7.C8.D9.C10.B11.C12.D13.A14.C15.D16.D17.C18.D19.B20.C21.A22.B23.B24.C25.D二．填空題1.i(i+1)/2+j2.1741393.4.對稱上三角（下三角）矩陣5.d6.表頭表尾7.（2,3,5）8.行列9.3310.O(n)11.O(n2)12.行列13.（）((),(()))3314.(a)((b),((c)))三．判斷題1.√2.√3.√4.√5.×6.×7.√8.√9.√10.√四、簡答題二維數(shù)組存儲時，要把它的元素映像存儲在一維存儲器中，存儲時若按先行后列的順序存儲，叫做二維數(shù)組的行序優(yōu)先存儲。若按先列后行的順序存儲，叫做二維數(shù)組的列序優(yōu)先存儲。元素分布特殊的矩陣，列如三角矩陣，對稱矩陣，帶狀矩陣，稀疏矩陣等，叫做特殊矩陣。特殊矩陣壓縮存儲的基本思想是壓縮存儲，即值相同的元素只分配一個存儲空間，零元素不分配存儲空間。設(shè)m*n矩陣中有t個非零元素且t<<m*n,這樣的矩陣叫做稀疏矩陣。系數(shù)矩陣存儲時可只存儲非零元素，由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須存儲非零元素所在的行號、列號，才能迅速確定一個非零元素是矩陣中的哪一個元素。ije001042204215436(((a,b,()),(),a,(b)),())6.程序設(shè)計題1.1.intgenlistDepth(BSLinkListlist){/*list存放廣義鏈表的首地址，該算法返回廣義鏈表的深度*/BSLinkListstack1[M],p;/*stack1用來記錄子表的起始位置*//*stack2用來記錄子表當前的深度，depth用來表示當前所求子表的深度，maxdep用來記錄當前已求出的那些子表的最大深度,stack1和stack2共用一個棧頂指針*/intstack2[M],depth=0,maxdep=0,top=-1;p=list->pointer;/*將p指針指向廣義鏈表的第一個元素所在的鏈接點*/if(p!=NULL){do{while(p!=NULL){stack1[++top]=p;/*記錄當前子表的起始位置*/stack2[top]=depth;/*記錄當前所求子表的深度*/if(p->flag==1){/*當前鏈接點元素是子表*/depth++;/*當前層次數(shù)加1*/p=p->pointer;/*移動到下一層*/}elsep=NULL;}if(maxdep<depth){maxdep=depth;/*記錄當前已求得的最大層次數(shù)*/}p=stack1[top];/*退回到上一層，移動到下一個元素，查看是否有子表*/depth=stack2[top--];p=p->link;}(p!=NULL&&top!=-1);}returnmaxdep+1;}2.#include<stdio.h>

#include<string.h>

main()

{

inta[100][100],m;

intn,i,j,k,max,flat=0,l;

scanf("%d,%d",&n,&l);

for(i=0;i<n;i++)

for(j=0;j<l;j++)

scanf("%d",&a[i][j]);

for(i=0;i<n;i++)

{

m=a[i][0];

for(j=0;j<l;j++)

if(a[i][j]>m)

{

m=a[i][j];

max=j;

}

for(k=0;k<n;k++)

if(a[k][max]<m)

{printf("No\n");

flat++;

break;

}

if(flat==0)

printf("%c\n",m);

}

}3.（1）#include<stdio.h>voidproc1(matrixA){ints=0,i,j;for(i=0;i<m;i++)/*第一列*/s=s+A[i][1];for(i=0;i<m;i++)/*最后一列*/s=s+A[i][n];for(j=0;j<n;j++)/*第一行*/s=s+A[1][j];for(j=0;j<m;j++)/*最后一行*/s=s+A[m][j];s=s-A[0][0]-A[0][n-1]-A[m-1][0]-A[m-1][n-1];/*減去4個角的重復(fù)元素值*/printf("s=%d\n",s);}（2）voidproc2(matrixA){ints=0,i,j;i=0;while(i<m){j=0;while(j<n){s=s+A[i][j];j=j+2;/*跳過一列*/}i=i+2;/*跳過一行*/}printf("s=%d\n",s);}（3）voidproc3(matrixA){inti,s;if(m!=n)printf("m!=n");else{s=0;for(i=0;i<m;i++)s=s+A[i][i];/*求第一列對角線之和*/for(i=0;i<n;i++)s=s+A[n-i-1][i];/*累加第二條對角線之和*/printf("s=%d\n",s);}}voidmain(){intm,n,i,j;matrixA;printf("m,n:");scanf("%d%d",&m,&n);printf("元素值:\n");for(i=0;i<m;i++)/*建立數(shù)組*/for(j=0;j<n;j++)scanf("%d",&A[i][j]);proc1(A);/*調(diào)用proc1()*/proc2(A);/*調(diào)用proc2()*/proc3(A);/*調(diào)用proc3()*/}樹答案一選擇題1-5ABBDC6-10CACBD11-15BCADB16-20BAAAA21-22CA二填空題n2+137單分支完全二叉樹12764312+12-11多129P->lchild==null&&p->rchild==null哈夫曼樹41601656316、6三綜合應(yīng)用題1（1）根節(jié)點：A葉子節(jié)點：CEFHIJKMN非終端節(jié)點：ABDGL（2）深度：5各節(jié)點層數(shù)A：1；B、C、D：2；E、F、G、H、I、J：3；K、L、M：4；N：5雙親：D祖先：AD孩子：KLM子孫：KLMN兄弟：HIJ堂兄弟：EF2先序遍歷：ABCDEFGHIJ中序遍歷：BCDAFEHJIG后序遍歷：DCBFJIHGEA3對應(yīng)的二叉樹后序遍歷為：bdeca456帶權(quán)路徑長度WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=131樹的結(jié)點總數(shù)137(1)哈夫曼樹：給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffmantree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。(2)哈夫曼樹為：哈弗曼編碼：a:1110b:1111c:110d:00e:01f:10(4)長度：244四、算法設(shè)計題設(shè)計一個求結(jié)點x在二叉樹中的雙親結(jié)點的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}

設(shè)計判斷兩個二叉樹是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}

設(shè)計計算二叉樹中所有結(jié)點值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }4.設(shè)計求二叉樹中值為x的結(jié)點所在的層號的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if(bt!=0){lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}}樹答案一選擇題1-5ABBDC6-10CACBD11-15BCADB16-20BAAAA21-22CA二填空題n2+137單分支完全二叉樹12764312+12-11多129P->lchild==null&&p->rchild==null哈夫曼樹41601656316、6三綜合應(yīng)用題1（1）根節(jié)點：A葉子節(jié)點：CEFHIJKMN非終端節(jié)點：ABDGL（2）深度：5各節(jié)點層數(shù)A：1；B、C、D：2；E、F、G、H、I、J：3；K、L、M：4；N：5雙親：D祖先：AD孩子：KLM子孫：KLMN兄弟：HIJ堂兄弟：EF2先序遍歷：ABCDEFGHIJ中序遍歷：BCDAFEHJIG后序遍歷：DCBFJIHGEA3對應(yīng)的二叉樹后序遍歷為：bdeca456帶權(quán)路徑長度WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=131樹的結(jié)點總數(shù)137(1)哈夫曼樹：給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffmantree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。(2)哈夫曼樹為：哈弗曼編碼：a:1110b:1111c:110d:00e:01f:10(4)長度：244四、算法設(shè)計題設(shè)計一個求結(jié)點x在二叉樹中的雙親結(jié)點的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}

設(shè)計判斷兩個二叉樹是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}

設(shè)計計算二叉樹中所有結(jié)點值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }4.設(shè)計求二叉樹中值為x的結(jié)點所在的層號的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if(bt!=0){lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}}第八章答案選擇題1~5CCCCD6~10BACBD11~15BAAAA16~20CBCBB21~25CB⑧①③④DB26~31CBDBCA二、選擇題1~9對對錯對對對錯三、填空題（1）2.9（2）2.1（3）1、2（4）7（5）1、2、4、8、5、3.7（6）O(n)、O(log2n)（7）3（8）增高一層（9）h（10）遞增數(shù)列、后綴表達式（11）┌m/2┐-1、m-1、O(n)、O(nlog2n)、O(n)（12）減少一層（13）如何構(gòu)造哈希函數(shù)、如何處理沖突（14）發(fā)生沖突的可能性越大、發(fā)生沖突的可能性越?。?5）開放定址法、拉鏈法四、簡答題1.靜態(tài)查找表：如果一個查找表的操作只涉及查詢和檢索某個特定的數(shù)據(jù)元素的操作，無需動態(tài)的修改查找表，此類查找表稱之為靜態(tài)查找表。動態(tài)查找表：需要動態(tài)的插入或刪除操作的查找表稱之為動態(tài)查找表。適合靜態(tài)查找的存儲結(jié)構(gòu)有：順序存儲，散列存儲。適合動態(tài)查找的存儲結(jié)構(gòu)有：順序存儲，散列存儲。2.平均查找長度：在查找過程中，一次查找的長度是指需要比較的關(guān)鍵字的次數(shù)，而平均查找長度則是所有查找過程中進行關(guān)鍵字的比較次數(shù)的平均值。其數(shù)學(xué)定義為ASL=∑PiCi(i=1,2,3,…,n),其中：Pi為查找表中第i個數(shù)據(jù)元素的概率，Ci為找到第i個數(shù)據(jù)元素時已經(jīng)比較過的次數(shù)。3.（1）53/\1766/\/\12255870/\\566087（2）中序遍歷二叉排序樹可得到一個從小到大的有序序列。4.5.（1）（2）ASL=(4+2*3+3*2+4)/9=20/96.7.8.H(25)=25mod7=4H(31)=31mod7=3H(8)=8mod7=1H(27)=27mod7=6H(13)=13mod7=6H(68)=68mod7=5線性探測法：ASL=(5*1+2)/6=7/6鏈地址法：ASL=(5*1+1*2)/6=7/69.H(105)=105mod13=1H(97)=97mod13=6H(28)=28mod13=2H(52)=52mod13=0H(37)=37mod13=11H(22)=22mod13=9H(16)=16mod13=3H(90)=90mod13=12H(45)=45mod13=6H(76)=76mod13=11H(59)=59mod13=7H(74)=74mod13=9（1）散列地址0123456789101112131415關(guān)鍵字5210528169745592274379076沖突次數(shù)111112212113（2）散列地址0123456789101112131415關(guān)鍵字5210528169745592276379074沖突次數(shù)11111221311510.H(11)=(5*11)