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

填空題數(shù)據(jù)元素關(guān)系邏輯結(jié)構(gòu)物理結(jié)構(gòu)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)哈希存儲(chǔ)線性結(jié)構(gòu)樹圖集合數(shù)據(jù)描述操作聲名聯(lián)系圖樹數(shù)據(jù)元素?cái)?shù)據(jù)元素有窮性確定性可行性輸入輸出正確性可讀性健壯性效率與存儲(chǔ)量的要求O（n）時(shí)間空間O（n）O（m*n）O（n）時(shí)間復(fù)雜度空間復(fù)雜度選擇題1-5BACAD6-10BCCB11-15BBACB16-20BDDAA21-23ACB判斷題FT簡答題1、數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)；常用的存儲(chǔ)方式有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和哈希存儲(chǔ)2、例如有一張學(xué)生成績表，記錄了一個(gè)班的學(xué)生各門課的成績。按學(xué)生的姓名為一行記成的表。這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)記錄(有姓名，學(xué)號(hào)，成績等字段)就是一個(gè)結(jié)點(diǎn)，對(duì)于整個(gè)表來說，只有一個(gè)開始結(jié)點(diǎn)(它的前面無記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼(它的前面和后面均有且只有一個(gè)記錄)。這幾個(gè)關(guān)系就確定了這個(gè)表的邏輯結(jié)構(gòu)。那么我們?cè)鯓影堰@個(gè)表中的數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)里呢?用高級(jí)語言如何表示各結(jié)點(diǎn)之間的關(guān)系呢?是用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針進(jìn)行鏈接呢?這就是存儲(chǔ)結(jié)構(gòu)的問題，我們都是從高級(jí)語言的層次來討論這個(gè)問題的。最后，我們有了這個(gè)表(數(shù)據(jù)結(jié)構(gòu))，肯定要用它，那么就是要對(duì)這張表中的記錄進(jìn)行查詢，修改，刪除等操作，對(duì)這個(gè)表可以進(jìn)行哪些操作以及如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算問題了。3、算法是描述求特定問題而規(guī)定的一系列操作步驟集合。特性包括：有窮性、確定性、可行性、有零個(gè)或多個(gè)輸入，有一個(gè)或多個(gè)輸出。4、a—b—c—d—e—f—g—h線性結(jié)構(gòu)(2)樹形結(jié)構(gòu)dagbhef（3）圖型結(jié)構(gòu)5、解：數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。是對(duì)一般數(shù)據(jù)類型的擴(kuò)展。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ù)上所進(jìn)行的操作。在定義抽象數(shù)據(jù)類型中的數(shù)據(jù)部分和操作部分時(shí)，要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的具體實(shí)現(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個(gè)元素，并用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個(gè)位置之前插入新的元素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){/*當(dāng)前空間已滿，增加分配*/newbase=(ElemType*)realloc((*LA).elem,((*LA).listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);/*存儲(chǔ)分配失敗*/(*LA).elem=newbase;/*新基址*/(*LA).listsize+=LISTINCREMENT;}/*增加存儲(chǔ)容量*/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é)點(diǎn)成為尾結(jié)點(diǎn)。while（p!=null）{r=p->next；p->next=L；∥將p結(jié)點(diǎn)插到L結(jié)點(diǎn)前面。L=p；∥L指向新的鏈表“第一”元素結(jié)點(diǎn)。p=r；}returnL;}3、LinkListreverse(LinkList&L)//帶頭結(jié)點(diǎn)單鏈表的就地逆置{ 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ù)域?yàn)檎麛?shù)且無序的單鏈表，本算法查找最小值結(jié)點(diǎn)且打印?！稳糇钚≈到Y(jié)點(diǎn)的數(shù)值是奇數(shù)，則與后繼結(jié)點(diǎn)值交換；否則，就刪除其直接后繼結(jié)點(diǎn)。p=la->next；∥設(shè)la是頭結(jié)點(diǎn)的頭指針，p為工作指針。pre=p；∥pre指向最小值結(jié)點(diǎn)，初始假定首元結(jié)點(diǎn)值最小。while(p->next!=null){∥p->next是待比較的當(dāng)前結(jié)點(diǎn)。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é)點(diǎn)沒有后繼，則不必交換t=pre->data；pre->data=pre->next->data；pre->next->data=t；}∥交換完畢else∥處理偶數(shù)情況if(pre->next!=null){∥若最小值結(jié)點(diǎn)是最后一個(gè)結(jié)點(diǎn)，則無后繼u=pre->next；pre->next=u->next；free(u)；}∥釋放后繼結(jié)點(diǎn)空間}5、解法如下：假定鏈表結(jié)點(diǎn)類型如下;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é)點(diǎn)的兩個(gè)單鏈表的頭指針，鏈表中的元素值按遞增序排列，本算法將兩鏈表合并成一個(gè)按元素值遞減次序排列的單鏈表。pa=la->next;pb=lb->next;∥pa，pb分別是鏈表la和lb的工作指針la->next=null;∥la作結(jié)果鏈表的頭指針，先將結(jié)果鏈表初始化為空。while(pa!=null&&pb!=null)∥當(dāng)兩鏈表均不為空時(shí)作if(pa->data<=pb->data){r=pa->next;∥將pa的后繼結(jié)點(diǎn)暫存于r。pa->next=la->next;∥將pa結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置。la->next=pa;pa=r;∥恢復(fù)pa為當(dāng)前待比較結(jié)點(diǎn)。}else{r=pb->next;∥將pb的后繼結(jié)點(diǎn)暫存于r。pb->next=la->next;∥將pb結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置。la->next=pb;pb=r;∥恢復(fù)pb為當(dāng)前待比較結(jié)點(diǎn)。}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é)點(diǎn)的單鏈表，本算法刪除其最小值結(jié)點(diǎn)。

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

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

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

while（p->next!=null）

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

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

}

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

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

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

typedefstructqueuenode

{

Datatypedata;

structqueuenode*next;

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

typedefstruct

{

queuenoderear;

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

voidInitQueue(LinkQueue&Q)

{

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

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

QueueNode*s;

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

while(Q->rear!=Q->rear->next)//當(dāng)隊(duì)列非空，將隊(duì)中元素逐個(gè)出隊(duì)

{

s=Q->rear->next;

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

free(s);

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

}

intEmptyQueue(LinkQueue&Q)

{//判隊(duì)空

//當(dāng)頭結(jié)點(diǎn)的next指針指向自己時(shí)為空隊(duì)

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

}

voidEnQueue(LinkQueue&Q,Datatypex)

{//入隊(duì)

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

QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申請(qǐng)新結(jié)點(diǎn)

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

Q-rear->next=p;

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

}

DatatypeDeQueue(LinkQueue&Q,Datatype&x)

{

//出隊(duì),把頭結(jié)點(diǎn)之后的元素摘下

Datatypet;

QueueNode*p;

if(EmptyQueue(Q))

Error("Queueunderflow");

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

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

if(p==Q->rear)

{//當(dāng)隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí)，p結(jié)點(diǎn)出隊(duì)后，要將隊(duì)尾指針指向頭結(jié)點(diǎn)

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

}

else

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

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

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、解：因?yàn)檩斎胄蛄惺菑男〉酱笈帕械?，所以若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ù)表達(dá)式中最多字符個(gè)數(shù)*/3.decpair(exp,flag)4.charexp［m0］;5.intflag;//flag用于標(biāo)識(shí)是否匹配，flag=0標(biāo)識(shí)不匹配，flag＝1標(biāo)識(shí)匹配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ù)處理，否則以不配對(duì)返回*/20.if(st［top］=='(')top--;21.elseflag=0;22.if(exp［i］=='］')/*遇到')'，若棧頂是'［'，23.則繼續(xù)處理，否則以不配對(duì)返回*/24.if(st［top］=='［')top--;25.elseflag=0;26.if(exp［i］=='}')/*遇到')'，若棧頂是'{'，27.則繼續(xù)處理，否則以不配對(duì)返回*/28.if(st［top］=='{')top--;29.elseflag=0;30.i++;31.}32.if(top>0)flag=0;/*若棧不空，則不配對(duì)*/33.}6、解：假設(shè)隊(duì)列為循環(huán)順序隊(duì)列。建立一個(gè)臨時(shí)隊(duì)列，將指定隊(duì)列中所有元素出隊(duì)并入隊(duì)到臨時(shí)隊(duì)列中，這樣指定隊(duì)列為空，再將臨時(shí)隊(duì)列中所有元素出隊(duì)并入隊(duì)到指定隊(duì)列(因?yàn)椴荒芷茐脑?duì)列結(jié)構(gòu)，所以需要恢復(fù)元素)，最后一個(gè)元素即為所求。具體算法如下：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、解：隊(duì)列為空：count==0

隊(duì)列為滿：count=MAXLEN

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

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

const

MAXLEN=100;

int

queue[MAXLEN];

int

front,count;

//

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

（1）初始化隊(duì)列

void

init()

{

front=1;

count=0;

}

（2）判定隊(duì)空

int

QEmpty()

{

if

(count==0)

return(1);

else

return(0);}

（3）讀隊(duì)頭元素

void

ReadFront(int

queue[],x)

{

if

(count==0)

printf("

下溢出\n");

else

{

front=(front+1)%MAXLEN;

x=queue[front];

}

}（4）入隊(duì)操作

void

InQueue(int

queue[],int

x)

{

int

place;

if

(count==MAXLEN)

printf("

上溢出\n");

else

{

count++;

place=(front+count)%MAXLEN;

queue[MAXLEN]=x;

}

}

（5）出隊(duì)操作

void

OutQueue(int

queue[])

//

刪除隊(duì)列頭元素

{

if

(count==0)

printf("

隊(duì)列下溢出\n");

else

{

front=(front+1)%MAXLEN;

count--;

}

}

8、解析：定義本題隊(duì)列類型如下：typedefstruct{linklist*rear;}Queue2(1)隊(duì)列中人隊(duì)操作是在隊(duì)尾進(jìn)行，即在鏈尾插入一個(gè)新結(jié)點(diǎn)。voidenqueue(Queue2*Q，datatypex){linklist*s；s＝(linklist*)malloe(sizeof(linklist))；//建立新結(jié)點(diǎn)s—>datda=x；s—>next=Q—>rear—>next；//將新結(jié)點(diǎn)插入隊(duì)尾q—>rear—>next=s；q—>rear=s；}(2)隊(duì)列中出隊(duì)操作是在隊(duì)頭進(jìn)行，即刪除鏈表第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。datatypedequeue(Queue2*Q){datatypex；linklist*p；if(Q—>rear—>next==Q—>rear)//隊(duì)列為空returnNULL；p＝Q一>rear一>next一>next；//p指向隊(duì)頭結(jié)點(diǎn)x=p一>data；Q一>rear一>next一>next＝p一>next//刪除*p結(jié)點(diǎn)free(p)returnx；//返回原隊(duì)頭元素}串選擇題A2.C3.C4.D5.D6.D7.B8.D9.A10.C11.D12.D填空題長度為零的串字符串元素只有空格的串子串主串簡答題1.答：長度為0的串稱為空串；由一個(gè)或多個(gè)空格組成的串稱為空格串?？崭褚彩谴淖址现械囊粋€(gè)元素。2.答：雖然串是由字符組成的，但串和字符是兩個(gè)不同的概念。串是長度不確定的字符序列，兒子富只是一個(gè)字符，即使是長度為1的串也與字符不同。例如，串“a”和字符‘a(chǎn)’就是兩個(gè)不同的概念，因?yàn)樵趫?zhí)行時(shí)串的結(jié)尾通常加上串結(jié)束標(biāo)志“\0”。答：串的順序存儲(chǔ)結(jié)構(gòu)是用一維數(shù)組存放串中的字符，用靜態(tài)內(nèi)存分配的方法定義數(shù)組，數(shù)組元素在編譯時(shí)是確定的，在運(yùn)行時(shí)是不可改變的稱為靜態(tài)順序存儲(chǔ)，用動(dòng)態(tài)內(nèi)存分配方法定義數(shù)組，數(shù)組元素個(gè)數(shù)是在程序運(yùn)行時(shí)用戶申請(qǐng)確定的稱為動(dòng)態(tài)順序存儲(chǔ)。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.對(duì)稱上三角（下三角）矩陣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ù)組存儲(chǔ)時(shí)，要把它的元素映像存儲(chǔ)在一維存儲(chǔ)器中，存儲(chǔ)時(shí)若按先行后列的順序存儲(chǔ)，叫做二維數(shù)組的行序優(yōu)先存儲(chǔ)。若按先列后行的順序存儲(chǔ)，叫做二維數(shù)組的列序優(yōu)先存儲(chǔ)。元素分布特殊的矩陣，列如三角矩陣，對(duì)稱矩陣，帶狀矩陣，稀疏矩陣等，叫做特殊矩陣。特殊矩陣壓縮存儲(chǔ)的基本思想是壓縮存儲(chǔ)，即值相同的元素只分配一個(gè)存儲(chǔ)空間，零元素不分配存儲(chǔ)空間。設(shè)m*n矩陣中有t個(gè)非零元素且t<<m*n,這樣的矩陣叫做稀疏矩陣。系數(shù)矩陣存儲(chǔ)時(shí)可只存儲(chǔ)非零元素，由于非零元素的分布一般是沒有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須存儲(chǔ)非零元素所在的行號(hào)、列號(hào)，才能迅速確定一個(gè)非零元素是矩陣中的哪一個(gè)元素。ije001042204215436(((a,b,()),(),a,(b)),())6.程序設(shè)計(jì)題1.1.intgenlistDepth(BSLinkListlist){/*list存放廣義鏈表的首地址，該算法返回廣義鏈表的深度*/BSLinkListstack1[M],p;/*stack1用來記錄子表的起始位置*//*stack2用來記錄子表當(dāng)前的深度，depth用來表示當(dāng)前所求子表的深度，maxdep用來記錄當(dāng)前已求出的那些子表的最大深度,stack1和stack2共用一個(gè)棧頂指針*/intstack2[M],depth=0,maxdep=0,top=-1;p=list->pointer;/*將p指針指向廣義鏈表的第一個(gè)元素所在的鏈接點(diǎn)*/if(p!=NULL){do{while(p!=NULL){stack1[++top]=p;/*記錄當(dāng)前子表的起始位置*/stack2[top]=depth;/*記錄當(dāng)前所求子表的深度*/if(p->flag==1){/*當(dāng)前鏈接點(diǎn)元素是子表*/depth++;/*當(dāng)前層次數(shù)加1*/p=p->pointer;/*移動(dòng)到下一層*/}elsep=NULL;}if(maxdep<depth){maxdep=depth;/*記錄當(dāng)前已求得的最大層次數(shù)*/}p=stack1[top];/*退回到上一層，移動(dòng)到下一個(gè)元素，查看是否有子表*/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個(gè)角的重復(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];/*求第一列對(duì)角線之和*/for(i=0;i<n;i++)s=s+A[n-i-1][i];/*累加第二條對(duì)角線之和*/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é)點(diǎn)：A葉子節(jié)點(diǎn)：CEFHIJKMN非終端節(jié)點(diǎn)：ABDGL（2）深度：5各節(jié)點(diǎn)層數(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對(duì)應(yīng)的二叉樹后序遍歷為：bdeca456帶權(quán)路徑長度WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=131樹的結(jié)點(diǎn)總數(shù)137(1)哈夫曼樹：給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffmantree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近。(2)哈夫曼樹為：哈弗曼編碼：a:1110b:1111c:110d:00e:01f:10(4)長度：244四、算法設(shè)計(jì)題設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)的算法。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è)計(jì)判斷兩個(gè)二叉樹是否相同的算法。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è)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }4.設(shè)計(jì)求二叉樹中值為x的結(jié)點(diǎn)所在的層號(hào)的算法。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é)點(diǎn)：A葉子節(jié)點(diǎn)：CEFHIJKMN非終端節(jié)點(diǎn)：ABDGL（2）深度：5各節(jié)點(diǎn)層數(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對(duì)應(yīng)的二叉樹后序遍歷為：bdeca456帶權(quán)路徑長度WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=131樹的結(jié)點(diǎn)總數(shù)137(1)哈夫曼樹：給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffmantree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近。(2)哈夫曼樹為：哈弗曼編碼：a:1110b:1111c:110d:00e:01f:10(4)長度：244四、算法設(shè)計(jì)題設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)的算法。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è)計(jì)判斷兩個(gè)二叉樹是否相同的算法。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è)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }4.設(shè)計(jì)求二叉樹中值為x的結(jié)點(diǎn)所在的層號(hào)的算法。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對(duì)對(duì)錯(cuò)對(duì)對(duì)對(duì)錯(cuò)三、填空題（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ù)列、后綴表達(dá)式（11）┌m/2┐-1、m-1、O(n)、O(nlog2n)、O(n)（12）減少一層（13）如何構(gòu)造哈希函數(shù)、如何處理沖突（14）發(fā)生沖突的可能性越大、發(fā)生沖突的可能性越小（15）開放定址法、拉鏈法四、簡答題1.靜態(tài)查找表：如果一個(gè)查找表的操作只涉及查詢和檢索某個(gè)特定的數(shù)據(jù)元素的操作，無需動(dòng)態(tài)的修改查找表，此類查找表稱之為靜態(tài)查找表。動(dòng)態(tài)查找表：需要?jiǎng)討B(tài)的插入或刪除操作的查找表稱之為動(dòng)態(tài)查找表。適合靜態(tài)查找的存儲(chǔ)結(jié)構(gòu)有：順序存儲(chǔ)，散列存儲(chǔ)。適合動(dòng)態(tài)查找的存儲(chǔ)結(jié)構(gòu)有：順序存儲(chǔ)，散列存儲(chǔ)。2.平均查找長度：在查找過程中，一次查找的長度是指需要比較的關(guān)鍵字的次數(shù)，而平均查找長度則是所有查找過程中進(jìn)行關(guān)鍵字的比較次數(shù)的平均值。其數(shù)學(xué)定義為ASL=∑PiCi(i=1,2,3,…,n),其中：Pi為查找表中第i個(gè)數(shù)據(jù)元素的概率，Ci為找到第i個(gè)數(shù)據(jù)元素時(shí)已經(jīng)比較過的次數(shù)。3.（1）53/\1766/\/\12255870/\\566087（2）中序遍歷二叉排序樹可得到一個(gè)從小到大的有序序列。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線性探測(cè)法：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)