......課后習(xí)題解答判斷題線性表的邏輯順序與存儲順序總是一致的?！病痢稠樞虼鎯Φ木€性表可以按序號隨機(jī)存取。〔√〕一半的元素需要移動?！病痢骋虼藢儆谕粩?shù)據(jù)對象?！病獭吃诰€性表的順序存儲構(gòu)造中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。〔×〕在線性表的鏈?zhǔn)酱鎯?gòu)造中，邏輯上相鄰的元素在物理位置上不一定相鄰?！病獭尘€性表的鏈?zhǔn)酱鎯?gòu)造優(yōu)于順序存儲構(gòu)造。〔×〕在線性表的順序存儲構(gòu)造中，插入和刪除時移動元素的個數(shù)與該元素的位置有關(guān)。〔√〕線性表的鏈?zhǔn)酱鎯?gòu)造是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的?！病獭常趩捂湵碇校〉媚硞€元素，只要知道該元素的指針即可，因此，單鏈表是隨．靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以它存取表中第i個元的時間與i無關(guān)?！病痢常€性表的特點是每個元素都有一個前驅(qū)和一個后繼。〔×〕算法設(shè)計題設(shè)線性表存放在向量A[arrsize]的前elenum 個分量中，且遞增有序。試寫一算法將x插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時間復(fù)雜度。相鄰，不一定將向量和表示線性表長度的變量封裝成一個構(gòu)造體〕，因為是順序存儲，分配的存儲空間是固定大小的， 所以首先確定是否還有存儲空間，假設(shè)有，那么根據(jù)原線性表中元的有序性，來確定插入元素的插入位置，后面的元素為它讓出位置，〔也可以從高低標(biāo)端開始一邊比擬，一邊移位〕然后插入x，最后修改表示表長的變量。intinsert(datatypeA[],int*elenum,datatypex) /*elenum{if(*elenum==arrsize-1)return0; /*表已滿，無法插入else{i=*elenum;為表的最大下標(biāo) */*/while(i>=0&&A[i]>x)/*邊找位置邊移動*/{A[i+1]=A[i];i--;}A[i+1]=x;(*elenum)++;return1;

/*插入成功*/}}時間復(fù)雜度為O(n)。/*找到的位置是插入位的下一位*/元素?！咎崾尽繉樞虮鞟，從第一個元素開場，查找其后與之值一樣的所有元素，將它們刪除；再對第二個元素做同樣處理，依此類推。voiddelete(Seqlist*A){i=0;while(i<A->last)*/{k=i+1;

/*將第i個元素以后與其值一樣的元素刪除while(k<=A->last&&A->data[i]==A->data[k]) /*kA[i]*/k++;n=k-i-1;for(j=k;j<=A->last;j++)A->data[j-n]=A->data[j];A->last=A->last-n;i++;}}A以較高的效率來實現(xiàn)。

/*n表示要刪除元素的個數(shù)*//*刪除多余元素*/x~y(x<=y)之間的所有元素，要求【提示】對順序表A，從前向后依次判斷當(dāng)前元素A->data[i]xynA->data[i]向前移nn用來記錄當(dāng)前已刪除元素的個數(shù)。voiddelete(Seqlist*A,intx,inty){i=0;n=0;while(i<A->last){if(A->data[i]>=x&&A->data[i]<=y)n++;/*假設(shè)A->data[i]介于x和y之間，n自增*/else A->data[i-n]=A->data[i];/*i++;}A->last-=n;}

A->data[i]*/線性表中有n個元素，每個元素是一個字符，現(xiàn)存于向量R[n]中，試寫一算法，使R中的字符按字母字符、數(shù)字字符和其它字符的順序排列。要求利用原來的存儲空間，元素移動次數(shù)最小?！咎崾尽繉€性表進(jìn)展兩次掃描，第一次將所有的字母放在前面，第二次將所有的數(shù)字放在字母之后，其它字符之前。intfch(charc){if(c>='a'&&c<='z'||c>='A'&&c<='Z')return(1);elsereturn(0);}intfnum(charc){if(c>='0'&&c<='9')return(1);

/*c*//*c*/elsereturn(0);}voidprocess(charR[n]){low=0;high=n-1;while(low<high){while(low<high&&fch(R[low]))low++;while(low<high&&!fch(R[high]))high--;if(low<high){k=R[low];R[low]=R[high];R[high]=k;

/*將字母放在前面*/}} /*將數(shù)字放在字母后面，其它字符前面*/low=low+1;high=n-1;while(low<high){while(low<high&&fnum(R[low]))low++;while(low<high&&!fnum(R[high]))high--;if(low<high){k=R[low];R[low]=R[high];R[high]=k;}}}線性表用順序存儲，設(shè)計一個算法，用盡可能少的輔助存儲空間將順序表中前 m元素和后n個元素進(jìn)展整體互換。即將線性表：〔a ,?,

〕改變?yōu)椋?,a2 m,b1,b2 nb1,b2,,nb,a1,a2,,ma〕?！咎崾尽勘葦Mm和n的大小，假設(shè)m<n，那么將表中元素依次前移后移n次。voidprocess(Seqlist*L,intm,intn){if(m<=n)for(i=1;i<=m;i++){x=L->data[0];for(k=1;k<=L->last;k++)L->data[k-1]=L->data[k];L->data[L->last]=x;

m次；否那么,將表中元素依次}elsefor(i=1;i<=n;i++){x=L->data[L->last];for(k=L->last-1;k>=0;k--)L->data[k+1]=L->data[k];L->data[0]=x;}}帶頭結(jié)點的單鏈表L中的結(jié)點是按整數(shù)值遞增排列的，試寫一算法，將值為x 的結(jié)點插入到表L中，使得L仍然遞增有序，并且分析算法的時間復(fù)雜度。LinkListinsert(LinkListL,intx) /*尋找插入位置*/{p=L; /*申請結(jié)點空間*/while(p->next&&x>p->next->data) /**/p=p->next;s=(LNode*)malloc(sizeof(LNode)); /*將結(jié)點插入到鏈表中*/s->data=x;s->next=p->next;p->next=s;return(L);}ABC不改變其排序性。LinkListCombine(LinkListA,LinkListB){C=A;rc=C;pa=A->next;/*pa指向表A的第一個結(jié)點*/pb=B->next;/*pb指向表B的第一個結(jié)點 */free(B);/*釋放B的頭結(jié)點*/while(pa&&pb)/*將pa、pb所指向結(jié)點中，值較小的一個插入到鏈表C的表尾*/if(pa->data<pb->data){rc->next=pa;rc=pa;pa=pa->next;}else{rc->next=pb;rc=pb;pb=pb->next;}if(pa)rc->next=pa;elserc->next=pb; /*ABC*/return(C);}假設(shè)長度大于1的循環(huán)單鏈表中，既無頭結(jié)點也無頭指針，p結(jié)點的指針，編寫算法刪除該結(jié)點的前驅(qū)結(jié)點。s指針可循環(huán)找到其前驅(qū)結(jié)點pp的前驅(qū)結(jié)點q，然后可刪除結(jié)點*p。vioddelepre(LNode {LNode*p,*q;p=s;while(p->next!=s){q=p;p=p->next;}q->next=s;free(p);}兩個單鏈表 A和B分別表示兩個集合，其元素遞增排列， 編寫算法求出A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲?！咎崾尽拷患傅氖莾蓚€單鏈表的元素值一樣的結(jié)點的集合，為了操作方便，

先讓單鏈表Cp

A中的當(dāng)前結(jié)點，指針

q用來B時，將其較小者跳過，繼續(xù)后面的比擬。LinkListIntersect(LinkListA,LinkListB){LNode*q,*p,*r,*s;LinkListC;C=(LNode*)malloc(sizeof(LNode));C->next=NULL;r=C;p=A;q=B;while(p&&q)if(p->data<q->data)p=p->next;elseif(p->data==q->data){s=(LNode*)malloc(sizeof(LNode));s->data=p->data;r->next=s;r=s;p=p->next;q=q->next;}else q=q->next;r->next=NULL;C=C->next;returnC;}．設(shè)有一個雙向鏈表，每個結(jié)點中除有priordatanext域外，還有一個訪問頻度freqLocata(L,x)xfreq1，并調(diào)整表中結(jié)點的次序，使其按訪問頻度的非遞增序列排列，以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一個滿足上述要求的Locata(L,x)算法。【提示】在定位操作的同時，需要調(diào)整鏈表中結(jié)點的次序：每次進(jìn)展定位操作后，查找結(jié)點的freq域，將其同前面結(jié)點的freq域進(jìn)展比擬，同時進(jìn)展結(jié)點次序的調(diào)整。typedefstructdnode{datatypedata;intfreq;structDLnode*prior,*next;}DLnode,*DLinkList;DlinkListLocate(DLinkListL,datatypex){p=L->next;while(p&&p->data!=x)p=p->next;if(!p)return(NULL);p->freq++;while(p->prior!=L&&p->prior->freq<p->freq){k=p->prior->data;p->prior->data=p->data;p->data=k;k=p->prior->freq;p->prior->freq=p->freq;p->freq=k;p=p->prior;}return(p);

/*查找值為x的結(jié)點，使p指向它*//*假設(shè)查找失敗，返回空指針*//*pfreq*//*調(diào)整結(jié)點的次序*//*返回找到的結(jié)點的地址*/}課后習(xí)題解答##選擇題ATop->next=p;C．p->next=Top;Top=p;

Top的鏈棧中插入一個 p所指結(jié)點時，其操作步驟為〔B．p->next=Top->next;Top->next=p;D．p->next=Top;Top=Top->next;

C〕。對于棧操作數(shù)據(jù)的原那么是〔B〕。A．先進(jìn)先出 B．后進(jìn)先出 C．后進(jìn)后出 D．不分順序piD〕。

1,2,3, ?，,n其輸出序列為 p1,p2,p3，?，pN,假設(shè)pN是n，A．i

B．n-i

C．n-i+1 D．不確定表達(dá)式a*(bc)d的后綴表達(dá)式是〔B〕。A．

B．a(chǎn)bc-*d+

C．a(chǎn)bc*-d+ D．+-*abcd采用順序存儲的兩個棧共享空間S[1..m]，top[i]代表第i個棧(i=1,2)的棧頂，棧 1底在S[1]，棧2的底在S[m]，那么棧滿的條件是〔 B〕。A．top[2]-top[1]|=0C．top[1]+top[2]=m6

B．top[1]+1=top[2]D．top[1]=top[2]a,b,c,d,e，那么棧的不可能的輸出序列是〔C〕。A．edcba B．decba C．dceab D．a(chǎn)bcde在一個鏈隊列中，Af->next=r;f=s;C．s->next=r;r=s;

f,r分別為隊首、隊尾指針，那么插入s所指結(jié)點的操作為〔B〕。B．r->next=s;r=s;D．s->next=f;f=s;用不帶頭結(jié)點的單鏈表存儲隊列時，在進(jìn)展刪除運算時〔D〕。A．僅修改頭指針B．僅修改尾指針C．頭、尾指針都要修改D．頭、尾指針可能都要修改

C〕的數(shù)據(jù)構(gòu)造。A．隊列 B．靜態(tài)鏈．棧和隊都是〔C〕。A．順序存儲的線性構(gòu)造C．限制存取點的線性判斷題

C．棧 D．順序表B．鏈?zhǔn)酱鎯Φ姆蔷€性構(gòu)造D．限制存取點的非線性構(gòu)造棧和隊列的存儲，既可以采用順序存儲構(gòu)造，又可以采用鏈?zhǔn)酱鎯?gòu)造?！病獭橙魏我粋€遞歸過程都可以轉(zhuǎn)換成非遞歸過程?！病獭?．假設(shè)輸入序列為1,2,3,4,5,63,2,5,6,4,1?！病獭惩ǔＪ褂藐犃衼硖幚砗瘮?shù)的調(diào)用?！病痢逞h(huán)隊列通常用指針來實現(xiàn)隊列的頭尾相接?！病痢澈喆痤}循環(huán)隊列的優(yōu)點是能夠克制“假溢滿〞現(xiàn)象。設(shè)有循環(huán)隊列sq，隊滿的判別條件為：（sq->rear+1〕%maxsize==sq->front; 或sq->num==maxsize 隊空的判別條件為：sq->rear==sq->front 。棧和隊列數(shù)據(jù)構(gòu)造各有什么特點，什么情況下用到棧，什么情況下用到隊列？棧和隊列都是操作受限的線性表，棧的運算規(guī)那么是“后進(jìn)先出〞，隊列的運算規(guī)那么是“先進(jìn)先出〞。棧的應(yīng)用如數(shù)制轉(zhuǎn)換、遞歸算法的實現(xiàn)等，隊列的應(yīng)用如樹的層次遍歷等。什么是遞歸？遞歸程序有什么優(yōu)缺點？一個函數(shù)在完畢本函數(shù)之前，直接或間接調(diào)用函數(shù)自身，稱為遞歸。例如，函數(shù)f在執(zhí)行中，又調(diào)用函數(shù)f自身，這稱為直接遞歸；假設(shè)函數(shù)f在執(zhí)行中，調(diào)用函數(shù) g，而g在執(zhí)中，又調(diào)用函數(shù)這稱為間接遞歸。在實際應(yīng)用中，多為直接遞歸，也常簡稱為遞歸。遞歸程序的優(yōu)點是程序構(gòu)造簡單、清晰，易證明其正確性。缺點是執(zhí)行中占內(nèi)存空間較多，運行效率低。設(shè)有編號為1,2,3,4車站的所有可能的順序〔每輛車可能入站，可能不入站，時間也可能不等〕。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,4321###選擇題下面關(guān)于串的表達(dá)錯誤的選項是〔C〕。A．串是字符的有限序列BC．空串是由空格構(gòu)成的串D2．串的長度是指〔B〕。A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)CD3．串S=‘a(chǎn)aab,NextA〕。A．0123B．1123C．1231D．1211二維數(shù)組M的成員是6個字符〔每個字符占一個存儲單元〕組成的串，行下標(biāo)X圍從0到8，列下標(biāo)j的X圍從 1到10，那么存放M至少需要〔D〕個字節(jié)；M的第第5行共占〔A〕個字節(jié)；假設(shè) M按行優(yōu)先方式存儲，元M[8][5]的起始地址與當(dāng) M先方式存儲時的〔C〕元素的起始地址一致。1〕A90B180C．240D．540〔2〕A．108B．114C．54D．603〕AM[0][9]i8列和按列優(yōu)

數(shù)組A中，每個元素的存儲占 3個單元，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開場連續(xù)存放在存儲器內(nèi)， 存放該數(shù)組至少需要的單元個數(shù)是〔C〕，假設(shè)該數(shù)組按行存放，元素A[8][5]的起始地址是〔D〕，假設(shè)該數(shù)組按列存放，元素A[8][5]的起始地址〔B〕?！?〕A．80B．100 C．240D．270〔2〕A．SA+141B．SA+144 C．SA+222D．SA+225〔3〕A．SA+141B．SA+180 C．SA+117D．SA+225稀疏矩陣采用壓縮存儲，一般有〔CA．二維數(shù)組和三維數(shù)組B．三元組和散列CD．散列和十字鏈表判斷題串相等是指兩個串的長度相等?！病痢?〔√〕KMP算法的特點是在模式匹配時指示主串的指針不會變小。稀疏矩陣壓縮存儲后，必會失去隨機(jī)存取功能?！病獭硵?shù)組是線性構(gòu)造的一種推廣，因此與線性表一樣，可以對它進(jìn)展插入，刪除等操作?！病痢吃摼仃嚨霓D(zhuǎn)置運算。〔×〕假設(shè)一個廣義表的表頭為空表，那么此廣義表亦為空表?！病痢乘^取廣義表的表尾就是返回廣義表中最后一個元素?！病痢澈喆痤}KMP算法較樸素的模式匹配算法有哪些改良?KMP算法主要優(yōu)點是主串指針不回溯。當(dāng)主串很大不能一次讀入內(nèi)存且經(jīng)常發(fā)生局部匹配時，KMP算法的優(yōu)點更為突出。設(shè)字符串S=‘a(chǎn)abaabaabaac' ，P=‘a(chǎn)abaac'。1〕給出SPnextnextval值；2SPKMP算法的匹配過程?！窘獯稹浚?〕S的next與nextval值分別為012123456789 和002002002021 ，p的next與nextval值分別為012123和002003 。利用KMPaabaac(i=6,j=6)

2〕利用BF第一趟匹配：aabaabaabaacaabaac(i=6,j=6)

第一趟匹配： 匹配過程：算 aabaabaabaac法的第二趟匹配：aa(i=3,j=2)(aa)baac

aabaabaabaac 第二趟匹配：aabaabaabaac第三趟匹配：

aabaabaabaac 第三趟匹配：a(i=3,j=1)()(aa)baac第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac(成功) aabaac(i=13,j=7)假設(shè)按行優(yōu)先存儲整數(shù)數(shù)組100數(shù)占４個字節(jié)。問以下元素的存儲地址是什么？(1)a0000(2)a1111(3)a3125(4)a8247【解答】(1)LOC(a0000)=100(2)LOC(a1111)=100+(3*5*8*1+5*8*1+8*1+1)*4=776(3)LOC(a3125)=100+(3*5*8*3+5*8*1+8*2+5)*4=1784(4)LOC(a8247)=100+(3*5*8*8+5*8*2+8*4+7)*4=4816a11a12a21a22a33a34a43a44?.aij

a2m-1,2m-1a2m-1,2ma2m,2m-1a2m,2m按以下方式存儲于一維數(shù)組

B[4m]中〔m為一個整數(shù)〕：

?4m-14m0 1 2 3

5 6

k 2m-1,2m a2m,2m-1 a2m,2ma11

a

a

a22

a

a

a43

aij寫出下標(biāo)轉(zhuǎn)換函數(shù)k=f(i,j)?！窘獯稹坑深}目可知，每一行有兩個非0元素。當(dāng)i為奇數(shù)時，第i行的元素為：ai,i、ai,(i+1)，此時k=2*(i-1)+j-i=i+j-2iiai,(i-1)ak=2*(i-1)+j-I+1=i+j-1綜k=i+j-i%2-1。n×n3A3B[3][n]中，使得元B[u][v]=ai,j(u,v)的下標(biāo)變換公式?！窘獯稹縰=j-i+1v=j-1...A（1〕三元組表表示法（2〕十字鏈表法。000220-150133000000-60000000091000000028000【解答】〔1〕三元組表表示法:ijv1 14222 16-15322134233534-66519176328〔2〕十字鏈表法：0 1 2 3 4 5^022 13 23 1 ^ ^

1 422 16 -15^ ^3 4-62 ^ ^3 ^51 914 ^ ^5^^

63 28...畫出以下廣義表的頭尾表示存儲構(gòu)造示意圖。（1〕A=((a,b,c),d,(a,b,c))（2〕B=(a,(b,(c,d),e),f)（1〕111^1 1 1 ^ 1d（2〕

0 a 1 b 1 c111^0a111^0f0b 1 1 ^ 0c0c 0 d課后習(xí)題解答選擇題以下說法正確的選項是〔C〕。A．二叉樹中任何一個結(jié)點的度都為22一棵二叉樹的度可小于2D．任何一棵二叉樹中至少有一個結(jié)點的度為2的個數(shù)為〔C〕。n個結(jié)點的二叉鏈表中〔

2n>0〕，空鏈域A．2n-1 B．n-1 C．n+1 D．2n+1點A．p->lchild=NULLC．p->ltag=0

*pBB．p->ltag=1p->rtag=1p->lchild=NULLp->ltag=1A3,BA,BB〕。A．3B．4C．5D．1某二叉樹T有n個結(jié)點,設(shè)按某種順序?qū)?T中的每個結(jié)點進(jìn)展編號，編號值為1,2,...n且有如下性質(zhì):T中任意結(jié)點v,其編號等于左子樹上的最小編號減１,而v的右子樹的結(jié)點中,其最小編號等于v左子樹上結(jié)點的最大編號加１，這是按〔B〕編號的。A．中序遍歷序列B．先序遍歷序列C．后序遍歷序列D．層次順序F是一個森林，BF域為空的結(jié)點有〔C〕個。

Fn個非終端結(jié)點,B中右指針A．n-1

n n+ D．1C．

n+2...一棵完全二叉樹上500 B．501

1001個結(jié)點，其中葉子結(jié)點的個數(shù)是〔C．490 D．495

C〕。設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為 N1，N2和N3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是〔B．N1+N2 C．N2

D〕。任何一棵二叉樹的葉結(jié)點在先序、中序、后序遍歷序列中的相對次序〔 A〕。A．不發(fā)生改變B．發(fā)生改變．假設(shè)一棵二叉樹的后序遍歷序

以上都不對debac，那么先序遍歷序為為〔D〕。

dabec，中序遍歷序列為 列Acbed B．decab Cdeabc D11．假設(shè)一棵二叉樹的先序遍歷序列為 abdgcefh，中序遍歷的序列為歷的結(jié)果為〔D〕。A．gcefha B． gdbecfha C．bdgaechf D．

dgbaechf遍12．一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，那么該二叉樹一定滿足〔B〕。A．所有的結(jié)點均無左孩子B．所有的結(jié)點均無右孩子CD．是一棵滿二叉樹13〕。A．加快查找結(jié)點的前驅(qū)或后繼的速度B．為了能在二叉樹中方便的進(jìn)展插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結(jié)果唯一．設(shè)高度為h那么此類二叉樹中所包含的結(jié)B〕。A．2*hB．2*h-1C．2*h+1D．h+1．一個具有567個結(jié)點的二叉樹的高h(yuǎn)D〕。A．9B．10C．9566之間D．10567之間．給一個整數(shù)集合{35679}B〕。A．B．C．D．9395 79 676 67673 35 57 9 3 5判斷題二叉樹是樹的特殊形式?！病獭秤蓸滢D(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的?！病獭诚雀闅v一棵樹和先序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不同?！病痢?..先根遍歷森林和先序遍歷與該森林對應(yīng)的二叉樹，其結(jié)果不同?！病痢惩耆鏄渲校僭O(shè)一個結(jié)點沒有左孩子，那么它必是葉子。〔√〕對于有N個結(jié)點的二叉樹，其高度為log2N1。〔×〕假設(shè)一個結(jié)點是某二叉樹子樹的中序遍歷序列中的最后一個結(jié)點，那么它必是該子樹的...先序遍歷序列中的最后一個結(jié)點。 〔√〕樹的后序遍歷序列中的第一個結(jié)點。〔√〕不使用遞歸也可實現(xiàn)二叉樹的先序、中序和后序遍歷?！病獭常刃虮闅v二叉樹的序列中，任何結(jié)點的子樹的所有結(jié)點不一定跟在該結(jié)點之后。〔×〕．先序和中序遍歷用線索樹方式存儲的二叉樹，不必使用棧。〔×〕．在后序線索二叉樹中，在任何情況下都能夠很方便地找到任意結(jié)點的后繼?！病痢常蚵鼧涫菐?quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。〔√〕．在哈夫曼編碼中，出現(xiàn)頻率一樣的字符編碼長度也一定一樣。〔×〕．用一維數(shù)組存放二叉樹時，總是以先序遍歷存儲結(jié)點?！病痢常畬σ豢枚鏄溥M(jìn)展層次遍歷時，應(yīng)借助于一個棧。〔×〕．完全二叉樹可采用順序存儲構(gòu)造實現(xiàn)存儲，非完全二叉樹那么不能。〔×〕．滿二叉樹一定是完全二叉樹，反之未必。〔√〕簡答題2的樹與一棵二叉樹有何區(qū)別？樹與二叉樹之間有何區(qū)別？【解答】22個結(jié)點最多有兩棵子樹，樹是無序樹，且每個結(jié)點可以有多棵子樹。A對于圖1所示二叉樹，試給出：1〕它的順序存儲構(gòu)造示意圖；B C2〕它的二叉鏈表存儲構(gòu)造示意圖；3〕它的三叉鏈表存儲構(gòu)造示意圖?！窘獯稹?D E F〔1〕順序存儲構(gòu)造示意圖：AB C D E F ^ ^ ^ G ^ ^ H (1)HG〔2〕二叉鏈表存儲構(gòu)造示意圖：〔3〕三叉鏈表存儲構(gòu)造示意圖：A A ^B C^^ D ^ E^^F^ G ^ ^ H

B C^^ D^ E^ ^ F2所示的樹，試給出：

^ G^ ^ H^（1〕雙親數(shù)組表示法示意圖； GFEDI（2〕孩子鏈表表示法示意圖； HJ圖2)（3〕孩子兄弟鏈表表示法示意圖?！窘獯稹浚?〕雙親數(shù)組表示法示意圖：〔2〕孩子鏈表表示法示意圖：ABC...2 ^648^10 ^0A0A-10A1B01B2C02C3D23D4E24E5F15F6G16G7H57H8I28I9J49J10K410K11M311M12N812N5311 ^97 ^3〕孩子兄弟鏈表表示法示意圖：ABC^ GFED^H^J^K^

12 ^I3在二叉樹中是葉子。AFJBCDGEHI(圖3)...【解答】ABFECGJDHI...在二叉樹中某結(jié)點所對應(yīng)的森林中結(jié)點為葉子結(jié)點的條件是該結(jié)點在森林中既沒有孩子也沒有右兄弟結(jié)點。將題5圖所示的二叉樹轉(zhuǎn)換成相應(yīng)的森林。ABCDEFG H【解答】森林：

(題5圖)CAFB E HDG11的結(jié)點。證明：由哈夫曼樹的構(gòu)造過程可知，哈夫曼樹的每一分支結(jié)點都是由兩棵子樹合并產(chǎn)生的新結(jié)點，其度必為2，所以哈夫曼樹中不存在度為1的結(jié)點。n個葉結(jié)點，需經(jīng)2n-1個結(jié)點。

n個葉結(jié)點，那么樹中共有2n－1個結(jié)點。n-1次合并形成哈夫曼樹，而每次合并產(chǎn)生一個分支結(jié)點，所證明：由二叉樹的前序序列和中序序列可以唯一地確定一棵二叉樹。證明：給定二叉樹結(jié)點的前序序列和對稱序〔中序〕序列，可以唯一確定該二叉樹。因為前序序列的第一個元素是根結(jié)點，該元素將二叉樹中序序列分成兩局部，左邊〔設(shè) l個元r個元素〕是右子樹，假設(shè)素〕表示左子樹，假設(shè)左邊無元素，那么說明左子樹為空；右邊〔設(shè) 空，那么右子樹為空。根據(jù)前序遍歷中“根 —左子樹—右子樹〞的順序，那么由從第二元素開場的l個結(jié)點序列和中序序列根左邊的 l個結(jié)點序列構(gòu)造左子樹，由前序序列最后 r個元素序列與中序序列根右邊的一棵度為

r個元素序列構(gòu)造右子樹。m的樹中有n1個度為1的結(jié)點，n2個度為 2的結(jié)點，??，nm個度mnn0個葉結(jié)點，那么n=n0+n1+?+nm

(1)樹中除根結(jié)點外，每個結(jié)點對應(yīng)著一個分支，而度為n=n1+2*n2+?+m*nm+1 由(1)(2)n0=n2+2*n3+3*n4++(m-1)*nm+1

k的結(jié)點發(fā)出k個分支，所以：．在具有n〔n>1〕個結(jié)點的樹中，深度最小的那棵樹其深度是多少？它共有多少2;n-1;1;n;1,n-1．設(shè)高度為h的二叉樹上只有度2h-12h-1

和度為2...．求表達(dá)式：波蘭式：-+a*

ab*(cd)e/f的波蘭式〔前綴式〕和逆波蘭式〔后綴式〕。d/ef 逆波蘭式：abcd-*+ef/-．畫出和以下序列對應(yīng)的樹

T：GFKDAIEBCHJ ；樹的后根訪問次序為：

DIAEKFCJHBG ?！窘獯稹繉?yīng)的二叉樹和樹分別如下左、右圖所示：G GF F BBK K C HCD D A E JA HIJI E．畫出和以下序列對應(yīng)的森林

F：ABCDEFGHIJKL 森林的后根訪問次序為：

CBEFDGAJIKLH 。A HDE

G I K LJ．畫出和以下序列對應(yīng)的樹

T：ABCDEFGHIJ；DBGEHJACIF?！窘獯稹緼B CD E FG H IJ按層次遍歷，第一個結(jié)點〔假設(shè)樹不空〕為根，該結(jié)點在中序序列中把序列分成左右兩局部—左子樹和右子樹。假設(shè)左子樹不空，層次序列中第二個結(jié)點左子樹的根；假設(shè)左子樹為空，右每個結(jié)點或是當(dāng)前情況下子樹的根或是葉子。{a,b,c,d,e,f,g}中的字母構(gòu)成。它們在電文中出現(xiàn)的{0.31,0.16,0.10,0.08,0.11,0.20,0.04},〔1〕為這7個字母設(shè)計哈夫曼編碼。...〔27總長壓縮多少？〔1〕哈夫曼樹：

1.00 1a：10 0.41 0.59b：110

0 1 0 1c：010

0.20 0.21 0.31 0.28d：1110

0 1 0 1e：01100g：1111〔2〕對這7

0.10 0.11 0.16 0.120 10.80 0.403位二進(jìn)制數(shù)。等長編碼的平均長度：0.31*3+0.16*3+0.10*3+0.08*3+0.11*3+0.20*3+0.04*3=3哈夫曼編碼：0.31*2+0.16*3+0.10*3+0.08*4+0.11*3+0.20*2+0.04*4=2.54哈夫曼編碼比等長編碼使電文總長壓縮了： 1-2.54/3=15.33%算法設(shè)計題root，試寫出求二叉樹結(jié)點的數(shù)目的算法。【提示】采用遞歸算法實現(xiàn)。二叉樹結(jié)點的數(shù)目＝

0當(dāng)二叉樹為空左子樹結(jié)點數(shù)目＋右子樹結(jié)點數(shù)目＋1當(dāng)二叉樹非空intcount(BiTreeroot){if(root==NULL)return(0);elsereturn(count(root->lchild)+count(root->rchild)+1);}請設(shè)計一個算法，要求該算法把二叉樹的葉結(jié)點按從左至右的順序鏈成一個單鏈表。二叉樹按lchild-rchild 方式存儲，時用葉結(jié)點的【提示】這是一個非常典型的基于二叉樹遍歷算法，

rchild域存放鏈指針。通過遍歷找到各個葉子結(jié)點， 因為不管前序遍歷、中序遍歷和后序遍歷，訪問葉子結(jié)點的相對順序都是一樣的，即都是從左至右。而題目要求是將二叉樹中的葉子結(jié)點按從左至右順序建立一個單鏈表，遍歷中的任意一種方法遍歷。這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點指針第一個葉子結(jié)點由指針 head 指向，遍歷到葉子結(jié)點時，就將它前驅(qū)

因此，可以采用三種pre，初始為空。rchild指針指向它，最后葉子結(jié)點的rchild為空。LinkListhead,pre=NULL;LinkListInOrder(BiTreeT)

/*全局變量*//*中序遍歷二叉樹T，將葉子結(jié)點從左到右鏈成一個單鏈表，表頭指針為head*/{ if(T){InOrder(T->lchild);/*中序遍歷左子樹 */if(T->lchild==NULL&&當(dāng)前是葉子結(jié)點 */if(pre==NULL){head=T;pre=T;}/*處理第一個葉子結(jié)點 */else{pre->rchild=T;...pre=T;}InOrder(T->rchild);

/*將葉子結(jié)點鏈入鏈表*//*中序遍歷右子樹*/pre->rchild=NULLreturn(head);}

; /*設(shè)置鏈表尾結(jié)點*/給定一棵用二叉鏈表表示的二叉樹，其根指針為 root，試寫出求二叉樹的深度的算法?！咎崾尽坎扇∵f歸算法。intHeight(BiTree{inthl,hr;

root)if(root==NULL)return(0);else{hl=Height(root->lchild);hr=Height(root->rchild);if(hl>hr)return(hl+1);elsereturn(hr+1);}}【提示】采用先序遞歸遍歷算法實現(xiàn)。

root，試求二叉樹各結(jié)點的層數(shù)。二叉樹結(jié)點的層次數(shù)＝

1其雙親結(jié)點的層次數(shù)＋

當(dāng)結(jié)點為根結(jié)點當(dāng)結(jié)點非根結(jié)點void fun(BiTree root,intn){ if(t==NULL) return;else{ printf(―%d‖,n);fun(root->lchild,n+1);fun(root->rchild,n+1);}}給定一棵用二叉鏈表表示的二叉樹，其根指針為root右子樹相互交換的算法?！咎崾尽吭O(shè)root 為一棵用二叉鏈表存儲的二叉樹，那么交換各結(jié)點的左右子樹的運算可基于后序遍歷實現(xiàn)：交換左子樹上各結(jié)點的左右子樹；交換左子樹上各結(jié)點的左右子樹；再交換根結(jié)點的左右子樹。void Exchange(BiTreeroot){BiTNode*p;if(root)Exchange(root->rchild);p=root->lchild;root->lchild=root->rchild;root->rchild=p;}}.........n序遍歷。【提示】二叉樹的順序存儲是按完全二叉樹的順序存儲格式按層次存儲的，雙親結(jié)點與子女結(jié)點的下標(biāo)間有確定的關(guān)系。 對順序存儲構(gòu)造的二叉樹進(jìn)展先序遍歷，與二叉鏈表存放二n0〔一般二叉樹中的“虛結(jié)點〞〕。void PreOrder(datatype data[n+1]){intstack[n];inttop;if(n<1)return;t=1;top=0;while(t<=n||top>0){while(t<=n&&data[t]!=0){Visite(data[t]);stack[top]=t;top++;t=t*2;}if(top<=0)return;else {top--;t=stack[top];t=t*2+1;}

/*0號單元未用*/}}z7．二叉樹中查找值為 x的結(jié)點，試設(shè)計打印值為x的結(jié)點的所有祖先結(jié)點算法。xx的結(jié)點時，棧中存放的就是其祖先結(jié)點，依次打印各結(jié)點的值。void

PrintNode(BiTreeT,datatypex)

/*初始化空棧*/{Init_Stack(S);p=T;while(p||!Empty_Stack(S))

/*假設(shè)p非空，或棧非空*/{while(p){ if(p->data==x){while(!Empty_Stack(S)){Pop(S,q);printf(q->data);}

/*假設(shè)當(dāng)前結(jié)點值為 x，依次輸出棧中元素的值*/return;}

/*假設(shè)當(dāng)前結(jié)點值不是x，壓棧*/else{ Push_Stack(S,p);}p=p->lchild;}if(!Empty_Stack(S)){p=r->rchild;}elsereturn;

/*當(dāng)棧非空，棧頂元素出棧，進(jìn)入右子樹*/}}一棵二叉樹的后序遍歷序列和中序遍歷序列，寫出可以確定這棵二叉樹的算法。【提示】根據(jù)后序遍歷和中序遍歷的特點，采用遞歸算法實現(xiàn)。void InPost(charin[],charpost[],intil,intir,intpl,intpr, BiTreet)/*數(shù)組in和數(shù)組post中存放著二叉樹的中序遍歷序列和后序遍歷序列，il和ir表示中序遍歷序列的左右端*//*plprt*/{t=(BiTNode*)malloc(sizeof(BiTNode));t->data=post[pr];m=il;while(in[m]!=post[pr])m++;if(m==il)t->lchild=NULL;else InPost(in,post,il,m-1,pl,pl+m-1-il,t->lchild);if(m==ir)t->rchild=NULL;else InPost(in,post,m+1,ir,pr-ir+m,pr-1,t->rchild);}編寫算法判斷一棵二叉鏈表表示的二叉樹是否是完全二叉樹?！咎崾尽扛鶕?jù)完全二叉樹的定義可知，對完全二叉樹按照從上到下，從左到右的次序遍歷應(yīng)后繼一定無孩子。因此，可采用按層次遍歷二叉樹的方法依次對每個結(jié)點進(jìn)展判斷。這里增加一個標(biāo)志以表示所有已掃描過的結(jié)點均有左、右孩子，將局部判斷結(jié)果存入CM中，CM表示整個二叉樹是否是完全二叉樹，B1表示到目前為止所有結(jié)點均有左右孩子。intCompleteBT(BiTreeT){Init_Queue(Q);B=1;CM=1;if (T!=NULL){In_Queue(Q,T);while(!Empty_Queue(Q)){ p=Out_Queue(Q);if(p->lchild==NULL){B=0;if(rchild!=NULL)CM=0;}else{CM=B;In_Queue(Q,p->lchild);elseIn_Queue(Q,p->rchild);}}

/*初始化隊列Q*//*當(dāng)隊列不為空時執(zhí)行循環(huán)*//*B=0表示缺少左、右孩子 *//*CM=0表示不是完全二叉樹*//*左孩子入隊列*//*右孩子入隊列*/return(CM);}}n個結(jié)點的完全二叉樹存放在一維數(shù)組A[1..n]中，試據(jù)此建立一棵用二叉鏈表表示的二叉樹。BiTreeCreate(dataypeA[],int i)/*n個結(jié)點的完全二叉樹存于一維數(shù)組A中，據(jù)此建立以二叉鏈表表示的完全二叉樹,初始調(diào)用時,i=1*/{BiTreeT;if(i<=n){T=(BiTree)malloc(sizeof(BiTNode));T->data=A[i];if(2*i>n)T->lchild=NULL;elseT->lchild=Create(A,2*i);if(2*i+1>n)elseT->rchild=Create(A,2*i+1);}return(T);}．編寫算法判定兩棵二叉樹是否相似。所謂兩棵二叉樹st相似，即要么它們都為空或都只有一個結(jié)點，要么它們的左右子樹都相似?！咎崾尽績煽每斩鏄浠騼H有根結(jié)點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，采用遞歸算法。intSimilar(BiTrees,BiTreet){if(s==NULL&&q==NULL)return(1);elseif(!s&&t||s&&!t)return(0);elsereturn(Similar(s->lchild,t->lchild)&&Similar(s->rchild,t->rchild))}．寫出用逆轉(zhuǎn)鏈方法對二叉樹進(jìn)展先序遍歷的算法?！咎崾尽坑媚孓D(zhuǎn)鏈的方法遍歷二叉樹，不需要附加的?？臻g，而是在遍歷過程中沿結(jié)點的左右子樹下降時，臨時改變結(jié)點lchild或者rchild的值，使之指向雙親，從而為以后的上升提供路徑，上升時再將結(jié)點的lchild或者rchild恢復(fù)。typedef structtnode{datatypedata;inttag;/*tag的值初始為0，進(jìn)入左子樹時置structtnode*lchild,*rchild;}Bnode,*Btree;void PreOrder(Btree bt){ Bnode *r,*p,指向當(dāng)前結(jié)點，rpif(bt==NULL)return;p=bt;r=NULL:while(p){ Visit(p);if(p->lchild)

1，從左子樹回來時，再恢復(fù)為q指向要訪問的下一結(jié)點*//*p*//*下降進(jìn)入左子樹*/{p->tag=1;q=p->lchild;q=p->lchild=r;r=p;p=q;}

0*//*下降進(jìn)入右子樹*/else if(p->rchild){q=p->rchild;p->rchild=r;r=p;p=q;}else{/*上升*/whle((r&&t->tag==0)||(r&&t->tag==1&&r->rchild==NULL)){if(r&&t->tag==0){q=r->rchild;r->rchild=p;p=r;r=q;} /*從右子樹回來*/else {r->tag=0;q=r->lchild;r->lchild=p;p=r;r=q;} /*從左子樹回來*/if(r==NULL)return;else {r->tag=0;q=r->rchild;r->rchild=r->lchild;r->lchild=p;p=q;} /*從左子樹回來，準(zhǔn)備進(jìn)入右子樹*/}}}}．對以孩子－兄弟鏈表表示的樹編寫計算樹的深度的算法?！咎崾尽坎捎眠f歸算法實現(xiàn)。樹的深度＝

0假設(shè)樹為空Max〔第一棵子樹的深度＋ 1，兄弟子樹的深度〕假設(shè)樹非空inthigh(CSTreeT){if(T==NULL)return(0);/*假設(shè)樹為空，返回 0*/else{ h1=high(t->lchild);/**h1T的第一棵子樹的深度*/h2=high(t->nextsibling);/*h2為t的兄弟子樹的深度 */return(max(h1+1,h2));}}．對以孩子鏈表表示的樹編寫計算樹的深度的算法。【提示】

采用遞歸算法實現(xiàn)。1假設(shè)根結(jié)點沒有子樹樹的深度＝

max(所有子樹的深度)1假設(shè)根結(jié)點有子樹#defineMAXNODE樹中結(jié)點的最大個數(shù)inthigh(SNodet[MAXNODE],intj){ if(t[j].firstchild==NULL)return(1); /*假設(shè)根結(jié)點沒有子樹*/else{p=t[i].firstchild;max=high(t,p->data);p=p->nextchild;while(p){h=high(t,p->data);if(h>max)max=h;...p=p->nextchild;}return(max+1);}}．對以雙親鏈表表示的樹編寫計算樹的深度的算法。【提示】從每一個結(jié)點開場，從下向上搜索至根結(jié)點，記錄結(jié)點的層次數(shù)，其中的最大值就是樹的深度。inthigh(PNodet[],intn){ maxh=0;for(i=0;i<n;i++){if(t[i].parent==-1)h=1;else{s=i;h=1;while(t[s].parent!=-1){s=t[s].parent;h++;}

/*求有n個結(jié)點的樹t的深度*/}if (h>maxh)maxh=h;}return(maxh);}選擇題n條邊的無向圖的鄰接表的存儲中，邊結(jié)點的個數(shù)有〔 〕。A．n

B．

C．

D．n*nn條邊的無向圖的鄰接多重表的存儲中，邊結(jié)點的個數(shù)有〔 A〕。A．n

B．

C．

D．n*nA

B．無向圖

C．AOV網(wǎng) D．AOE網(wǎng)最短路徑的生成算法可用〔C〕。A

B．克魯斯卡爾算法 C．迪杰斯特拉算

D．哈夫曼算法一個無向圖的鄰接表如以下圖所示：序號 vertex firstedge

1 3 ∧0 2 3∧1 ∧

0 1 ∧1〕從頂點v0出發(fā)進(jìn)展深度優(yōu)先搜索，經(jīng)歷的結(jié)點順序為〔B〕。...A．v0,v3,v2,v1

B．v0,v1,v2,v3

C．v0,v2,v1,v3

D．v0,v1,v3,v22V0

D〕。A．v0,v3,v2,v1

B．v0,v1,v2,v3

C．v0,v2,v1,v3

D．v0,v1,v3,v2設(shè)有向圖n個頂點和e條邊，進(jìn)展拓?fù)渑判驎r，總的計算時間為〔 D〕。A．O(nlog2e)

B．O(en

C．O(elog2n)

D．O(n+e)含有n個頂點eA〕。

Kruskal算法生成最小生成樹，其時間復(fù)A．O(elog2e)

B．O(en

C．O(elog2n)

D．O(nlog2n)關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中〔A〕。A．從源點到匯點的最長路徑 B．從源點到匯點的最短路徑C．最長的回路 D．最短的回9．下面關(guān)于求關(guān)鍵路徑的說法不正確的選項是〔 〕。A．求關(guān)鍵路徑是以拓?fù)渑判驗楦椎腂．一個事件的最早開場時間與以該事件為尾的弧的活動最早開場時間一樣C時間的差D．關(guān)鍵活動一定位于關(guān)鍵路徑上1010B〕條邊才能確保其是連通圖。A．8B．9C．10D．11判斷題求最小生成樹的Prim

〔×〕

〔√〕用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。 〔√〕

〔×〕任何有向網(wǎng)絡(luò)〔AOV-

〔×〕有回路的圖不能進(jìn)展拓?fù)渑判颉?/p>

〔√〕故只存儲鄰接矩陣的下

(或上)三角局部即可?！病獭橙魏螣o向圖都存在生成樹。〔×〕

〔×〕．假設(shè)一個有向圖的鄰接矩陣對角線以下元素均〔√〕．連通分量是無向圖中的極小連通子圖?！病痢?/p>

那么該圖的拓?fù)溆行蛐蛄斜囟ù嬖凇＃畯?qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖．用鄰接矩陣A表示圖，判定任意兩個結(jié)點

〔√〕vj之間是否有長度為m的路徑相連，那么只要檢查Am的第i行第j列的元素是否為0即可?！病獭常s短關(guān)鍵路徑上活動的工期一定能夠縮短整個工程的工期。 〔×〕AOE網(wǎng)中一定只有一條關(guān)鍵路徑。〔×〕簡答題對于如圖1所示的有向圖，試給出： ① ④〔1〕每個頂點的入度和出度； ⑤2〕鄰接矩陣；〔3〕鄰接表； ⑥② ③1〕...（4〕逆鄰接表；（5〕強(qiáng)連通分量?！窘獯稹浚?1〔2122231，3〕、頂43，0523612〕。（2〕鄰接矩陣：00010001001010000001110000001101000100103^02^345^0 11 22 334^4 55 6

0 1 3^1 4 ^〔4〕逆鄰接表：0114^1245^231^34024^4525^5 6 2 ^〔5〕強(qiáng)連通分量：51 4 62 3設(shè)無向圖G2所示，試給出：〔1〕該圖的鄰接矩陣；〔2〕該圖的鄰接表；〔3〕該圖的多重鄰接表；

v2 v5v1 v4 v74〕從出發(fā)的“深度優(yōu)先〞遍歷序列；5〕從出發(fā)的“廣度優(yōu)先〞遍歷序列。

v3 v62〕...【解答】〔1〕該圖的鄰接矩陣：0110000101000010010000110110000100100010010000110〔2〕該圖的鄰接表：0v112^1v202^2v302^3v43245^4v536^5v636^6v745^〔3〕該圖的多重鄰接表：v1010^2v4v531^32^343^5v6v764^6^5^〔4〕從v1出發(fā)的“深度優(yōu)先〞遍歷序列： v1v2v4v3v5v7v6〔5v1

v1v2v3v4v5v6v7用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關(guān)？與邊的條數(shù)是否有關(guān)？【解答】n(n0)n2個數(shù)與圖的邊數(shù)無關(guān)。設(shè)有向圖G3列。

G的十字鏈表構(gòu)造，并寫出圖G的兩個拓?fù)湫騰2 v5v1 v3 v6圖3...【解答】1〕G的十字鏈表構(gòu)造：0v1^0102^^1v21415^^2v325^v4v5^43^5v653^54^^2〕G的兩個拓?fù)湫蛄校簐1v2v3v6v5v4;5．如圖4AOE網(wǎng)：（1（2

v1v3v2v6v5v4（3〕找出該AOE網(wǎng)中的關(guān)鍵路徑，并答復(fù)完成該工程需要的最短時間。a1=3

Ba

Ea5=9

a9=5Aa

3a4=7C

Da

a6=10a

F Ha10=3a11=2G圖4〔1〕ve(A)=0 ve(B)=ve(A)+3=3 ve(C)=ve(A)+5=5ve(D)=max(ve(B)+6,ve(C)+7)=12

ve(E)=ve(D)+9=21

ve(G)=ve(D)+8=20ve(F)=max(ve(D)+10,ve(G)+6)=26 ve(H)=max(ve(E)+E,ve(G)+2,ve(F)+3)=29vl(H)=29

vl(E)=vl(H)

vl(F)=vl(H)–3=26vl(G)=min(vl(H)–2,vl(F) –6)=20 vl(D)=min(vl(E)–9,vl(F)–10,vl(G)–8)=12...vl(B)=vl(D)–6=6vl(C)=vl(B)=vl(D)–6=6vl(C)=vl(D)–7=5vl(A)=min(vl(B) –3,vl(C)–5)=0〔2〕e(a1)=0e(a7)=12e(a2)=0e(a8)=20e(a3)=3e(a9)=21e(a4)=5 e(a5)=12e(a10)=26 e(a11)=20e(a6)=12l(a1)=3(a7)=12l(a2)=0l(a8)=20l(a3)=6l(a9)=24l(a4)=5l(a10)=26l(a5)=15l(a11)=27l(a6)=16間： 29A D F a10=3a4=7 a8=6a2=5 a7=8C G課后習(xí)題解答(P152)選擇題靜態(tài)查找表與動態(tài)查找表的根本區(qū)別在于〔〕A．它們的邏輯構(gòu)造不一樣B．施加在其上的操作不一樣C．所包含的數(shù)據(jù)元素類型不一樣D．存儲實現(xiàn)不一樣在表長為nA．nB．1C．n+1D．n-1

〔A〕。順序查找適用于存儲構(gòu)造為〔CA．哈希存儲B．壓縮存儲CD．索引存儲２ ２ 用順序查找法對具有 n個結(jié)點的線性表查找一個結(jié)點的時間復(fù)雜度為〔 C〕A．O(log n2) B．O(nlog n) C．O(n) D．２ ２ 適用于折半查找的表的存儲方式及元素排列要求為〔 D〕。A．方式存儲，元素?zé)o序 B．方式存儲，元素有序C．順序方式存儲，元素?zé)o序 D．順序方式存儲，元素有有一個長度為12的有序表，按折半查找法對該表進(jìn)展查找， 在表內(nèi)各元素等概率況下查找成功所需的平均比擬次數(shù)為〔 B〕。A．35/12B．37/12 C．39/12 43/127{1391232416275778295，100}上進(jìn)展折半查找關(guān)鍵82C〕次。A．1B．2C．4D．5設(shè)哈希表長為14，哈希函數(shù)為H(key)=key%11 。當(dāng)前表中已有 4個結(jié)點：addr(15)=4 ，addr(38)=5 ，addr(61)=6 ，addr(84)=7 。如用二次探測再散列處理沖突， 那么關(guān)鍵字為49的結(jié)點的地址是〔D〕。A．8 B．3 C．5 D．9散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以〔〕取其值域的每個值。A．最大概率B．最小概率C．平均概率D．同等概率 至．假定有k個關(guān)鍵字互為同義詞，假設(shè)用線性探測法把這k個關(guān)鍵字存入散列表中，.........少要進(jìn)展多少次探測？(DAk-1次Bk次H(k)=kmA．奇數(shù)B．偶數(shù)C．k+1次中，一般來講，C．素數(shù)Dkk+1/2mC〕。D．充分大的數(shù)在．在采用線性探測法處理沖突所構(gòu)成的哈希表上進(jìn)展查找，查找成功的情況下，所探測到的這些位置上的鍵值〔B〕可能要探測多個位置，A．一定是同義詞B．一定不是同義詞C．都一樣D．不一定都是同義詞625個元素，查找每個元素的概率一樣，假設(shè)采用順序查找來確定結(jié)點所在的塊，每塊應(yīng)分〔B〕個結(jié)點最正確。．25C．6D．625．以下關(guān)于mB樹的說法錯誤的選項是〔D〕。A．根結(jié)點至多有m棵子樹B．所有葉子都在同一層次上C．非葉結(jié)點至少有 m/2(m為偶數(shù))或m/2+1〔m為奇數(shù)〕棵子樹D．根結(jié)點中的數(shù)據(jù)是有序的15mBBA．m叉排序樹 B．m叉平衡排序樹C．m-1叉平衡排序樹 D．m+1叉平衡排序樹判斷題順序查找可以在順序表上進(jìn)展，不能在單鏈表上進(jìn)展?！病痢痴郯氩檎抑荒茉谟行虻捻樞虮砩线M(jìn)展。〔√〕二叉排序樹是一樣的?！病痢滁c必定無右孩子?！病獭吃诙媾判驑渲?，最大值結(jié)點和最小值結(jié)點一定是葉子結(jié)點?！病獭硨⒍媾判驑?T1的先序遍歷序列依次插入初始為空的樹中，所得到的二叉排序T2T1對二叉排序樹進(jìn)展中序遍歷得到的序列是由小到大有序的?！病獭承∮谟液⒆拥闹??！病痢砄(log2n)，時間性能一樣?！病痢常捎谜郯氩檎曳▽τ行虮磉M(jìn)展查找總比采用順序查找法對其進(jìn)展查找要快?！病痢常捎镁€性探測法處理沖突時，當(dāng)從哈希表中刪除一個記錄時，不應(yīng)將這個記錄的所在位置置為空，因為這將會影響以后的查找。〔√〕mBm?！病獭常１淼牟檎倚手饕Q于構(gòu)造哈希表時選取的哈希函數(shù)和處理沖突的方法?！病獭常７ù鎯Φ母舅枷胧怯申P(guān)鍵碼的值決定數(shù)據(jù)的存儲地址。〔√〕．當(dāng)負(fù)載因子α1時，那么向哈希表中插入元素時不會引起沖突。〔×〕．查找表中數(shù)據(jù)元素的任何數(shù)據(jù)項都可以作為關(guān)鍵字?！病痢砿B樹的任何一個結(jié)點的所有子樹的高度都相等?！病獭常诙媾判驑渖蟿h除一個結(jié)點時，不必移動其他結(jié)點，只要將該結(jié)點相應(yīng)的指針域置空即可?！病痢常诠４鎯Ψ绞街校?fù)載因子的值越大，存取元素時發(fā)生沖突的可能性就越大。．對兩棵具有一樣關(guān)鍵字集合而形狀不同的二叉排序樹，按中序遍歷它們得到的序列

〔√〕的順序是一樣的?！病獭澈喆痤}畫出對長度為 18的有序的順序表進(jìn)展折半查找時的判定樹并指出在等概率時查成功的平均查找長度，以及查找失敗時所需的最多的關(guān)鍵字比擬次數(shù)。【解答】〔1〕判定樹為：94 142 6 11 161 3 5 7 10 12 15 17813 18（2〕平均查找長度為 1/18(1+2*2+3*4+4*8+5*3)=32/9查找最多比擬5次。12的關(guān)鍵字有序的表：{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}（1〕試按表中元素的順序依次插入到一棵初始為空的二叉排序樹，畫出插入完成后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。（2〕假設(shè)對表中元素先進(jìn)展排序構(gòu)成有序表，求在等概率的情況下查找成功的平均查找長度。（3〕按表中元素的順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度?！窘獯稹浚?〕按關(guān)鍵字的順序構(gòu)造的二叉排序樹：JanApr

Feb

JunMay

MarAug July

SepDec OctNov〔2〕根據(jù)構(gòu)造的二叉排序樹，求查找成功時的平均查找長度：ASLSUCC=(1*1+2*2+3*3+4*3+5*2+6*1)/12=3.5（3〕假設(shè)對表中元素先進(jìn)展排序構(gòu)成有序表再構(gòu)造二叉排序樹，那么構(gòu)造的二叉排序樹是一棵單支樹，在等概率的情況下查找成功的平均查找長度那么為：ASLSUCC=(1+2+?+12)/12=6.5這種情況就退化成為順序查找。12個結(jié)點的平衡二叉樹的最大深度，并畫出一棵這樣的樹。令Fk表示含有最少結(jié)點的深度為k的平衡二叉樹的結(jié)點數(shù)目。那么,可知道F1=1,F2=2,.....Fn=Fn-2+Fn-1+1.12個結(jié)點的平衡二叉樹的最大深度為５．例如：...AB CD E F G含有9個葉子結(jié)點的3階B樹中至少有多少個非葉子結(jié)點？含有 10個葉子結(jié)點的3H I J K階B樹中至少有多少個非葉子結(jié)點？7個。L試從空樹開場，畫出按以下次序向 3 階B樹中插入關(guān)鍵碼的建樹過程：20，30，50，52，60，68，70。如果此后刪除50和68，畫出每一步執(zhí)行后 3階B樹的狀態(tài)。5230 68 52 68 5220 50 60 70 20 30 60 70 20 30 60 700～16的散列區(qū)中，對以下關(guān)鍵字序列構(gòu)造兩個哈希表：{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}（1〕用線性探測開放定址法處理沖突；（2〕用鏈地址法處理沖突。H(key)=i/2,i為關(guān)鍵字中第一個字母在字母表中的序號。【解答】平均查找長度為（2〕平均查找長度為（2〕:31/120AprAug^1^2Dec^3Feb^4^5JanJune6MarMay^7OctNov^8^9Sep^10^11^12^13^14^15^16^012345678910111213141516AprAugDecFebJanMarMayJuneJulySepOctNovJuly ^...平均查找長度為:3/2哈希函數(shù)H(key)=(3*key)%11 。用開放定址法處理沖突。試

0～10的散列地址空間中對關(guān)鍵字序列〔

22，41，53，46，30，13，01，67〕構(gòu)造哈希表，并求等概率情況下查找成功時的平均查找長度。0123456789102267413053461301平均查找長度為:17/8畫出依次插入zvoqwy到以下圖所示的5B樹的過程。jc f m rd e a

ghi k

np st xz【解答】 jc f mrud e ab ghi k l np st xzjc f mrude ab ghi k

np s

uxzjc f mrud e ab gh

k l nop s

uxzjc f mrud e ab gh

k l nopq s

uxzjcf mrud e abcf

ghi jk l nopqmrux

st uwxzd e ab ghi k

nopq

s t uw y z...課后習(xí)題解答選擇題在待排序的元素序列根本有序的前提下，效率最高的排序方法是〔 〕。A．插入排序 B．選擇排序 C．快速排序 D．歸并排序設(shè)有1000C〕排序法。

10個最大的元素，最好A

B．快速排序

C．堆排序

D．基數(shù)排序具有12個記錄的序列，采用冒泡排序最少的比擬次數(shù)是〔 C〕。A．1 B．

C．

D．66以下四種排序方法中，要求內(nèi)存容量最大的是〔 D〕。A

B．選擇排序

C．快速排序

D．歸并排序初始序列已經(jīng)按鍵值有序時，用直接插入算法進(jìn)展排序，需要比擬的次數(shù)為〔 D〕。A．n2

B．nlog2n C．log

D．n-1C〕。A．直接插入排序和快速排序B．快速排序和歸并排序C．直接選擇排序和歸并排序D．直接插入排序和歸并排序46，79，56，3