數(shù)據(jù)結(jié)構(gòu)C語言版第版課后習(xí)題答案

數(shù)據(jù)結(jié)構(gòu)C語言版第版課后習(xí)題答案數(shù)據(jù)結(jié)構(gòu)C語言版第版課后習(xí)題答案數(shù)據(jù)結(jié)構(gòu)C語言版第版課后習(xí)題答案數(shù)據(jù)結(jié)構(gòu)C語言版第版課后習(xí)題答案編制僅供參考審核批準生效日期地址：電話：傳真:郵編:數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版） 課后習(xí)題答案 李冬梅

目錄第1章緒論1．簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型。答案：數(shù)據(jù)：是客觀事物的符號表示，指所有能輸入到計算機中并被計算機程序處理的符號的總稱。如數(shù)學(xué)計算中用到的整數(shù)和實數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動畫等通過特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、記錄等。數(shù)據(jù)元素用于完整地描述一個對象，如一個學(xué)生記錄，樹中棋盤的一個格局（狀態(tài)）、圖中的一個頂點等。數(shù)據(jù)項：是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位。例如，學(xué)生基本信息表中的學(xué)號、姓名、性別等都是數(shù)據(jù)項。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如：整數(shù)數(shù)據(jù)對象是集合N={0，±1，±2，…}，字母字符數(shù)據(jù)對象是集合C={‘A’，‘B’，…，‘Z’，‘a(chǎn)’，‘b’，…，‘z’}，學(xué)生基本信息表也可是一個數(shù)據(jù)對象。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。邏輯結(jié)構(gòu)：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。存儲結(jié)構(gòu)：數(shù)據(jù)對象在計算機中的存儲表示，也稱為物理結(jié)構(gòu)。抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問題的數(shù)學(xué)模型，以及定義在這個模型上的一組操作的總稱。具體包括三部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合和對數(shù)據(jù)對象的基本操作的集合。2．試舉一個數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的含義和相互關(guān)系。答案：例如有一張學(xué)生基本信息表，包括學(xué)生的學(xué)號、姓名、性別、籍貫、專業(yè)等。每個學(xué)生基本信息記錄對應(yīng)一個數(shù)據(jù)元素，學(xué)生記錄按順序號排列，形成了學(xué)生基本信息記錄的線性序列。對于整個表來說，只有一個開始結(jié)點(它的前面無記錄)和一個終端結(jié)點(它的后面無記錄)，其他的結(jié)點則各有一個也只有一個直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的邏輯結(jié)構(gòu)，即線性結(jié)構(gòu)。這些學(xué)生記錄在計算機中的存儲表示就是存儲結(jié)構(gòu)。如果用連續(xù)的存儲單元(如用數(shù)組表示)來存放這些記錄，則稱為順序存儲結(jié)構(gòu)；如果存儲單元不連續(xù)，而是隨機存放各個記錄，然后用指針進行鏈接，則稱為鏈式存儲結(jié)構(gòu)。即相同的邏輯結(jié)構(gòu)，可以對應(yīng)不同的存儲結(jié)構(gòu)。3．簡述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。答案：（1）集合結(jié)構(gòu)數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系外，別無其他關(guān)系。例如，確定一名學(xué)生是否為班級成員，只需將班級看做一個集合結(jié)構(gòu)。（2）線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)按照其入學(xué)報到的時間先后順序進行排列，將組成一個線性結(jié)構(gòu)。（3）樹結(jié)構(gòu)數(shù)據(jù)元素之間存在一對多的關(guān)系。例如，在班級的管理體系中，班長管理多個組長，每位組長管理多名組員，從而構(gòu)成樹形結(jié)構(gòu)。（4）圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)元素之間存在多對多的關(guān)系。例如，多位同學(xué)之間的朋友關(guān)系，任何兩位同學(xué)都可以是朋友，從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。其中樹結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。四類基本邏輯結(jié)構(gòu)關(guān)系圖4．存儲結(jié)構(gòu)由哪兩種基本的存儲方法實現(xiàn)答案：（1）順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助程序設(shè)計語言的數(shù)組類型來描述。（2）鏈式存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲空間中，而鏈式存儲結(jié)構(gòu)，無需占用一整塊存儲空間。但為了表示結(jié)點之間的關(guān)系，需要給每個結(jié)點附加指針字段，用于存放后繼元素的存儲地址。所以鏈式存儲結(jié)構(gòu)通常借助于程序設(shè)計語言的指針類型來描述。5．選擇題（1）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。A．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C．線性結(jié)構(gòu)和非線性結(jié)構(gòu)D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)答案：C（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（）。A．存儲結(jié)構(gòu)B．存儲實現(xiàn)C．邏輯結(jié)構(gòu)D．運算實現(xiàn)答案：C（3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（）。A．?dāng)?shù)據(jù)具有同一特點B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致C．每個數(shù)據(jù)元素都一樣D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等答案：B（4）以下說法正確的是（）。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位B．?dāng)?shù)據(jù)項是數(shù)據(jù)的基本單位C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)答案：D解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。（5）算法的時間復(fù)雜度取決于（）。A．問題的規(guī)模 B．待處理數(shù)據(jù)的初態(tài)C．計算機的配置 D．A和B答案：D解釋：算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān)，還與問題的其他因素有關(guān)。如某些排序的算法，其執(zhí)行時間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時會對算法有最好、最壞以及平均時間復(fù)雜度的評價。（6）以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)A．樹B．字符串C．隊列D．棧答案：A6．試分析下面各程序段的時間復(fù)雜度。（1）x=90;y=100;while(y>0)if(x>100){x=x-10;y--;}elsex++;答案：O(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。（2）for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;答案：O(m*n)解釋：語句a[i][j]=0;的執(zhí)行次數(shù)為m*n。（3）s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;答案：O(n2)解釋：語句s+=B[i][j];的執(zhí)行次數(shù)為n2。（4）i=1;while(i<=n)i=i*3;答案：O(log3n)解釋：語句i=i*3;的執(zhí)行次數(shù)為log3n。（5）x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;答案：O(n2)解釋：語句x++;的執(zhí)行次數(shù)為n-1+n-2+……＋1=n(n-1)/2。（6）x=n;ext=s;(*s).next=(*p).next;C．s->next=p->next;p->next=s->next;D．s->next=p->next;p->next=s;答案：D(14)在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（）。A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;C．p->prior->next=p;p->prior=p->prior->prior;D．p->prior=p->next->next;p->next=p->prior->prior;答案：A(15)在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點后插入q所指向的新結(jié)點，其修改指針的操作是（）。A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;答案：C2．算法設(shè)計題（1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間,不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。[題目分析]合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進行比較，當(dāng)兩個鏈表La和Lb均為到達表尾結(jié)點時，依次摘取其中較小者重新鏈接在Lc表的最后。如果兩個表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無重復(fù)的元素。當(dāng)一個表到達表尾結(jié)點，為空時，將非空表的剩余元素直接鏈接在Lc表的最后。[算法描述]voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc){想摘除棧頂結(jié)點，并將刪除結(jié)點的值保存到x中,則應(yīng)執(zhí)行操作（）。A．x=top->data;top=top->link； B．top=top->link;x=top->link；C．x=top;top=top->link； D．x=top->link；答案：A解釋：x=top->data將結(jié)點的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)點，即摘除棧頂結(jié)點。（5）設(shè)有一個遞歸算法如下intfact(intn){n]存儲，初始棧頂指針top設(shè)為n+1，則元素x進棧的正確操作是()。A．top++;V[top]=x; B．V[top]=x;top++;C．top--;V[top]=x; D．V[top]=x;top--;答案：C解釋：初始棧頂指針top為n+1，說明元素從數(shù)組向量的高端地址進棧，又因為元素存儲在向量空間V[1..n]中，所以進棧時top指針先下移變?yōu)閚，之后將元素x存儲在V[n]。（10）設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A．線性表的順序存儲結(jié)構(gòu)B．隊列C.線性表的鏈式存儲結(jié)構(gòu)D.棧答案：D解釋：利用棧的后進先出原則。（11）用鏈接方式存儲的隊列，在進行刪除運算時（）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改答案：D解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。（12）循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)答案：D解釋：數(shù)組A[0..m]中共含有m+1個元素，故在求模運算時應(yīng)除以m+1。（13）最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。A.(rear+1)%n==frontB.rear==frontC．rear+1==frontD.(rear-l)%n==front答案：B解釋：最大容量為n的循環(huán)隊列，隊滿條件是(rear+1)%n==front，隊空條件是rear==front。（14）棧和隊列的共同點是（）。A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點答案：C解釋：棧只允許在棧頂處進行插入和刪除元素，隊列只允許在隊尾插入元素和在隊頭刪除元素。（15）一個遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分答案：B2．算法設(shè)計題（1）將編號為0和1的兩個棧存放于一個數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號棧的棧頂指針top[0]等于-1時該棧為空，當(dāng)?shù)?號棧的棧頂指針top[1]等于m時該棧為空。兩個棧均從兩端向中間增長。試編寫雙棧初始化，判斷?？?、棧滿、進棧和出棧等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：Typedefstruct{inttop[2],bot[2]; IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO=2\*GB3②通過對=1\*GB3①的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。答案：=1\*GB3①A和D是合法序列，B和C是非法序列。=2\*GB3②設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge(charA[])M-1]實現(xiàn)循環(huán)隊列，其中M是隊列長度。設(shè)隊頭指針front和隊尾指針rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。定義front=rear時為隊空，(rear+1)%m=front為隊滿。約定隊頭端入隊向下標(biāo)小的方向發(fā)展，隊尾端入隊向下標(biāo)大的方向發(fā)展。[算法描述]=1\*GB3①#defineM隊列可能達到的最大長度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;=2\*GB3②elemtpdelqueue(cycqueueQ)100,1..100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[5,5]=（）。A．808B．818C．1010D．1020答案：B解釋：以行序為主，則LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。（7）設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A[5,8]的存儲首地址為（）。A．BA+141B．BA+180C．BA+222D．BA+225答案：B解釋：以列序為主，則LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。（8）設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（）。A．13B．32C．33D．40答案：C（9）若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij（i<j）的位置k的關(guān)系為（）。A．i*(i-1)/2+jB．j*(j-1)/2+iC．i*(i+1)/2+jD．j*(j+1)/2+i答案：B（10）二維數(shù)組A的每個元素是由10個字符組成的串，其行下標(biāo)i=0,1,…,8,列下標(biāo)j=1,2,…,10。若A按行先存儲，元素A[8,5]的起始地址與當(dāng)A按列先存儲時的元素（）的起始地址相同。設(shè)每個字符占一個字節(jié)。A．A[8,5]B．A[3,10]C.A[5,8]D．A[0,9]答案：B解釋：設(shè)數(shù)組從內(nèi)存首地址M開始順序存放，若數(shù)組按行先存儲，元素A[8,5]的起始地址為：M+[（8-0）*10+（5-1）]*1=M+84；若數(shù)組按列先存儲，易計算出元素A[3,10]的起始地址為：M+[（10-1）*9+（3-0）]*1=M+84。故選B。（11）設(shè)二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為（）。A．(i-1)*n+jB．(i-1)*n+j-1C．i*(j-1)D．j*m+i-1答案：A解釋：特殊值法。取i=j=1，易知A[1,1]的的下標(biāo)為1，四個選項中僅有A選項能確定的值為1，故選A。（12）數(shù)組A[0..4,-1..-3,5..7]中含有元素的個數(shù)（）。A．55B．45C．36D．16答案：B解釋：共有5*3*3=45個元素。（13）廣義表A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))的值為（）。A．(g)B．(d)C．cD．d答案：D解釋：Tail(A)=(b,(c,d),(e,(f,g)))；Tail(Tail(A))=((c,d),(e,(f,g)))；Head(Tail(Tail(A)))=(c,d)；Tail(Head(Tail(Tail(A))))=(d)；Head(Tail(Head(Tail(Tail(A)))))=d。（14）廣義表((a,b,c,d))的表頭是（），表尾是（）。A．a(chǎn)B．()C．(a,b,c,d)D．(b,c,d)答案：C、B解釋：表頭為非空廣義表的第一個元素，可以是一個單原子，也可以是一個子表，((a,b,c,d))的表頭為一個子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個廣義表，((a,b,c,d))的表尾為空表()。（15）設(shè)廣義表L=((a,b,c))，則L的長度和深度分別為（）。A．1和1B．1和3C．1和2D．2和3答案：C解釋：廣義表的深度是指廣義表中展開后所含括號的層數(shù)，廣義表的長度是指廣義表中所含元素的個數(shù)。根據(jù)定義易知L的長度為1，深度為2。2．應(yīng)用題（1）已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個字符對應(yīng)的next和nextval函數(shù)值。答案：模式串t的next和nextval值如下：j123456789101112t串a(chǎn)bcaabbabcabnext[j]011122312345nextval[j]011021301105（2）設(shè)目標(biāo)為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa”=1\*GB3①計算模式p的naxtval函數(shù)值；=2\*GB3②不寫出算法,只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。答案：=1\*GB3①p的nextval函數(shù)值為0110132。（p的next函數(shù)值為0111232）。=2\*GB3②利用KMP(改進的nextval)算法，每趟匹配過程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)（3）數(shù)組A中，每個元素A[i,j]的長度均為32個二進位,行下標(biāo)從-1到9，列下標(biāo)從1到11，從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求：=1\*GB3①存放該數(shù)組所需多少單元=2\*GB3②存放數(shù)組第4列所有元素至少需多少單元=3\*GB3③數(shù)組按行存放時，元素A[7,4]的起始地址是多少=4\*GB3④數(shù)組按列存放時，元素A[4,7]的起始地址是多少答案：每個元素32個二進制位，主存字長16位，故每個元素占2個字長，行下標(biāo)可平移至1到11。（1）242（2）22（3）s+182（4）s+142(4)請將香蕉banana用工具H()—Head()，T()—Tail()從L中取出。L=(apple,(orange,(strawberry,(banana)),peach),pear)答案：H（H（T（H（T（H（T（L）））））））3．算法設(shè)計題（1）寫一個算法統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A-Z這26個字母和0-9這10個數(shù)字）。[題目分析]由于字母共26個，加上數(shù)字符號10個共36個，所以設(shè)一長36的整型數(shù)組，前10個分量存放數(shù)字字符出現(xiàn)的次數(shù)，余下存放字母出現(xiàn)的次數(shù)。從字符串中讀出數(shù)字字符時，字符的ASCII代碼值減去數(shù)字字符‘0’的ASCII代碼值，得出其數(shù)值(0..9)，字母的ASCII代碼值減去字符‘A’的ASCII代碼值加上10，存入其數(shù)組的對應(yīng)下標(biāo)分量中。遇其它符號不作處理，直至輸入字符串結(jié)束。[算法描述]voidCount（）是字符串輸入結(jié)束標(biāo)志 {InvertStore(A); A[i++]=ch;m,1..n]含有m*n個整數(shù)。=1\*GB3①寫一個算法判斷a中所有元素是否互不相同輸出相關(guān)信息(yes/no)；=2\*GB3②試分析算法的時間復(fù)雜度。=1\*GB3①[題目分析]判斷二維數(shù)組中元素是否互不相同，只有逐個比較,找到一對相等的元素，就可結(jié)論為不是互不相同。如何達到每個元素同其它元素比較一次且只一次在當(dāng)前行，每個元素要同本行后面的元素比較一次（下面第一個循環(huán)控制變量p的for循環(huán)），然后同第i+1行及以后各行元素比較一次，這就是循環(huán)控制變量k和p的二層for循環(huán)。[算法描述]intJudgEqual(inga[m][n],intm,n)[算法討論]對數(shù)組中元素各比較一次，比較次數(shù)為n。最佳情況(已排好,正數(shù)在前,負數(shù)在后)不發(fā)生交換，最差情況(負數(shù)均在正數(shù)前面)發(fā)生n/2次交換。用類c編寫，數(shù)組界偶是0..n-1?？臻g復(fù)雜度為O(1).第5章樹和二叉樹A．Ｂ．C．有多種，但根結(jié)點都沒有左孩子Ｄ．有多種，但根結(jié)點都沒有右孩子答案：A解釋：因為二叉樹有左孩子、右孩子之分，故由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹（）A．2B．3C．4D．5答案：D一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）A．250B．500C．254D．501答案：D解釋：設(shè)度為0結(jié)點（葉子結(jié)點）個數(shù)為A，度為1的結(jié)點個數(shù)為B，度為2的結(jié)點個數(shù)為C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉樹的性質(zhì)可得B=0或1，又因為C為整數(shù)，所以B=0，C=500，A=501，即有501個葉子結(jié)點。一個具有1025個結(jié)點的二叉樹的高h為（）A．11B．10C．11至1025之間D．10至1024之間答案：C解釋：若每層僅有一個結(jié)點，則樹高h為1025；且其最小樹高為log21025+1=11，即h在11至1025之間。深度為h的滿m叉樹的第k層有（）個結(jié)點。(1=<k=<h)A．mk-1B．mk-1C．mh-1D．mh-1答案：A解釋：深度為h的滿m叉樹共有mh-1個結(jié)點，第k層有mk-1個結(jié)點。利用二叉鏈表存儲樹，則根結(jié)點的右指針是（）A．指向最左孩子B．指向最右孩子C．空D．非空答案：C解釋：利用二叉鏈表存儲樹時，右指針指向兄弟結(jié)點，因為根節(jié)點沒有兄弟結(jié)點，故根節(jié)點的右指針指向空。對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（）遍歷實現(xiàn)編號。A．先序B.中序C.后序D.從根開始按層次遍歷答案：C解釋：根據(jù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點的順序遍歷二叉樹，即后序遍歷二叉樹。若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用（）遍歷方法最合適。A．前序B．中序C．后序D．按層次答案：C解釋：后續(xù)遍歷和層次遍歷均可實現(xiàn)左右子樹的交換，不過層次遍歷的實現(xiàn)消耗比后續(xù)大，后序遍歷方法最合適。在下列存儲形式中，（）不是樹的存儲形式A．雙親表示法B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲表示法答案：D解釋：樹的存儲結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉(zhuǎn)換為二叉樹進行存儲。一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）A．所有的結(jié)點均無左孩子B．所有的結(jié)點均無右孩子C．只有一個葉子結(jié)點D．是任意一棵二叉樹答案：C解釋：因為先序遍歷結(jié)果是“中左右”，后序遍歷結(jié)果是“左右中”，當(dāng)沒有左子樹時，就是“中右”和“右中”；當(dāng)沒有右子樹時，就是“中左”和“左中”。則所有的結(jié)點均無左孩子或所有的結(jié)點均無右孩子均可，所以A、B不能選，又所有的結(jié)點均無左孩子與所有的結(jié)點均無右孩子時，均只有一個葉子結(jié)點，故選C。（11）設(shè)哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（）個葉子結(jié)點。A．99 B．100C．101 D．102答案：B解釋：在哈夫曼樹中沒有度為1的結(jié)點，只有度為0（葉子結(jié)點）和度為2的結(jié)點。設(shè)葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，由二叉樹的性質(zhì)n0=n2+1，則總結(jié)點數(shù)n=n0+n2=2*n0-1，得到n0=100。若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則X的前驅(qū)為（）A．X的雙親B．X的右子樹中最左的結(jié)點C．X的左子樹中最右結(jié)點D．X的左子樹中最右葉結(jié)點答案：C引入二叉線索樹的目的是（）A．加快查找結(jié)點的前驅(qū)或后繼的速度B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結(jié)果唯一答案：A（14）設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有（）個。A．n1 B．n C．n+1 D．n+2答案：C（15）n（n≥2）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（）。A．該樹一定是一棵完全二叉樹B．樹中一定沒有度為1的結(jié)點C．樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D．樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值答案：A解釋：哈夫曼樹的構(gòu)造過程是每次都選取權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，所以樹中一定沒有度為1的結(jié)點、兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點、任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值。2．應(yīng)用題1試找出滿足下列條件的二叉樹=1\*GB3①先序序列與后序序列相同=2\*GB3②中序序列與后序序列相同=3\*GB3③先序序列與中序序列相同=4\*GB3④中序序列與層次遍歷序列相同先序遍歷二叉樹的順序是“根—左子樹—右子樹”，中序遍歷“左子樹—根—右子樹”，后序遍歷順序是：“左子樹—右子樹―根＂，根據(jù)以上原則有=1\*GB3①或為空樹，或為只有根結(jié)點的二叉樹=2\*GB3②或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹．=3\*GB3③或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹．=4\*GB3④或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹2設(shè)一棵二叉樹的先序序列：ABDFCEGH，中序序列：BFDAGEHC=1\*GB3①畫出這棵二叉樹。=2\*GB3②畫出這棵二叉樹的后序線索樹。=3\*GB3③將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。答案：AABFD=3\*GB3③CEHG=1\*GB3①=2\*GB3②3假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為，，，，，，，。=1\*GB3①試為這8個字母設(shè)計赫夫曼編碼。=2\*GB3②試設(shè)計另一種由二進制表示的等長編碼方案。=3\*GB3③對于上述實例，比較兩種方案的優(yōu)缺點。答案：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則：【[（2,3），6],(7,10)】,……19,21,32（100）（40）（60）192132（28）（17）（11）7106（5）2301010101213210101106123方案比較：字母編號對應(yīng)編碼字母編號對應(yīng)編碼出現(xiàn)頻率10002001301040115100610171108111字母編號對應(yīng)編碼出現(xiàn)頻率111002003111104111051061111170181101方案1的WPL＝2+++4+++5+=++=方案2的WPL＝3+++++++=3結(jié)論：哈夫曼編碼優(yōu)于等長二進制編碼4已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫出其對應(yīng)哈夫曼樹HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。答案：初態(tài):weightparentlchildrchild13000212000370004400052000680007110008000900010000110001200013000終態(tài)：weightparentlchildrchild138002121200371000449005280068100071111008595199114810151236112013971227132101347011123．算法設(shè)計題編寫以下算法：（1）統(tǒng)計二叉樹的葉結(jié)點個數(shù)。[題目分析]如果二叉樹為空，返回0，如果二叉樹不為空且左右子樹為空，返回1，如果二叉樹不為空，且左右子樹不同時為空，返回左子樹中葉子節(jié)點個數(shù)加上右子樹中葉子節(jié)點個數(shù)。[算法描述]intLeafNodeCount(BiTreeT){ if(T==NULL) return0;c;}圖的BFS生成樹的樹高比DFS生成樹的樹高A．小B．相等C．小或相等D．大或相等對于一些特殊的圖，比如只有一個頂點的圖，其BFS生成樹的樹高和DFS生成樹的樹高相等。一般的圖，根據(jù)圖的BFS生成樹和DFS樹的算法思想，BFS生成樹的樹高比DFS生成樹的樹高小。（13）已知圖的鄰接矩陣如圖所示，則從頂點v0出發(fā)按深度優(yōu)先遍歷的結(jié)果是（）。圖鄰接矩陣（14）已知圖的鄰接表如圖所示，則從頂點v0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（），按深度優(yōu)先遍歷的結(jié)果是（）。圖鄰接表A．0132 B．0231 C．0321 D．0123下面方法可以判斷出一個有向圖是否有環(huán)。A．深度優(yōu)先遍歷B．拓撲排序C．求最短路徑D．求關(guān)鍵路徑2．應(yīng)用題（1）已知圖所示的有向圖，請給出：=1\*GB3①每個頂點的入度和出度；=2\*GB3②鄰接矩陣；=3\*GB3③鄰接表；=4\*GB3④逆鄰接表。圖有向圖圖無向網(wǎng)答案：（2）已知如圖所示的無向網(wǎng)，請給出：=1\*GB3①鄰接矩陣；=2\*GB3②鄰接表；=3\*GB3③最小生成樹答案：=1\*GB3①=3\*GB3③=2\*GB3②a→b4→c3b→a4→c5→d5→e9c→a3→b5→d5→h5d→b5→c5→e7→f6→g5→h4e→b9→d7→f3f→d6→e3→g2g→d5→f2→h6（3）已知圖的鄰接矩陣如圖所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖鄰接矩陣圖鄰接矩陣（4）有向網(wǎng)如圖所示，試用迪杰斯特拉算法求出從頂點a到其他各頂點間的最短路徑，完成表。圖鄰接矩陣圖有向網(wǎng)表D終點i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e∞10(a,c,e)10(a,c,e)f∞6(a,c,f)g∞∞16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S終點集{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,f,e,d,g,b}（5）試對圖所示的AOE-網(wǎng)：=1\*GB3①求這個工程最早可能在什么時間結(jié)束；=2\*GB3②求每個活動的最早開始時間和最遲開始時間；=3\*GB3③確定哪些活動是關(guān)鍵活動圖AOE-網(wǎng)圖AOE-網(wǎng)答案：按拓撲有序的順序計算各個頂點的最早可能開始時間Ve和最遲允許開始時間Vl。然后再計算各個活動的最早可能開始時間e和最遲允許開始時間l，根據(jù)l-e=0來確定關(guān)鍵活動，從而確定關(guān)鍵路徑。123456Ve01915293843Vl019153738