數(shù)據(jù)結(jié)構(gòu)第4版習(xí)題和實(shí)驗(yàn)參考答案解析數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料（完整版）c語言版

..數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)及深入及考試復(fù)習(xí)資料習(xí)題及實(shí)驗(yàn)參考答案見附錄結(jié)論1、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù),它與數(shù)據(jù)的存儲(chǔ)無關(guān),是獨(dú)立于計(jì)算機(jī)的。2、數(shù)據(jù)的物理結(jié)構(gòu)亦稱存儲(chǔ)結(jié)構(gòu),是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示〔或映像。它依賴于計(jì)算機(jī)。存儲(chǔ)結(jié)構(gòu)可分為4大類：順序、鏈?zhǔn)?、索引、散?、抽象數(shù)據(jù)類型：由用戶定義,用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型構(gòu)成,并包括一組相關(guān)的服務(wù)〔或稱操作。它與數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念,但其特征是使用與實(shí)現(xiàn)分離,實(shí)行封裝和信息隱蔽〔獨(dú)立于計(jì)算機(jī)。4、算法：是對(duì)特定問題求解步驟的一種描述,它是指令的有限序列,是一系列輸入轉(zhuǎn)換為輸出的計(jì)算步驟。5、在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成〔CA、動(dòng)態(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)6、算法的時(shí)間復(fù)雜度取決于〔AA、問題的規(guī)模B、待處理數(shù)據(jù)的初態(tài)C、問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)線性表1、線性表的存儲(chǔ)結(jié)構(gòu)包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種。2、表長為n的順序存儲(chǔ)的線性表,當(dāng)在任何位置上插入或刪除一個(gè)元素的概率相等時(shí),插入一個(gè)元素所需移動(dòng)元素的平均次數(shù)為〔E,刪除一個(gè)元素需要移動(dòng)的元素的個(gè)數(shù)為〔A。A、<n-1>/2B、nC、n+1D、n-1E、n/2F、<n+1>/2G、<n-2>/23、"線性表的邏輯順序與存儲(chǔ)順序總是一致的。"這個(gè)結(jié)論是〔BA、正確的B、錯(cuò)誤的C、不一定,與具體的結(jié)構(gòu)有關(guān)4、線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí),要求內(nèi)存中可用存儲(chǔ)單元的地址〔DA、必須是連續(xù)的B、部分地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)或不連續(xù)都可以5、帶頭結(jié)點(diǎn)的單鏈表為空的判定條件是〔BA、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL6、不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是〔AA、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL7、非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)P滿足〔CA、p->next==NULLB、p==NULLC、p->next==headD、p==head8、在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是〔BA、O<1>B、O<n>C、O<n2>D、O<nlog2n>9、在一個(gè)單鏈表中,若刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn),則執(zhí)行〔AA、p->next=p->next->next;B、p=p->next;p->next=p->next->next;C、p->next=p->next;D、p=p->next->next;10、在一個(gè)單鏈表中,若在p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn),則執(zhí)行〔BA、s->next=p;p->next=s;B、s->next=p->next;p->next=s;C、s->next=p->next;p=s;D、p->next=s;s->next=p;11、在一個(gè)單鏈表中,已知q是p的前趨結(jié)點(diǎn),若在q和p之間插入結(jié)點(diǎn)s,則執(zhí)行〔CA、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、q->next=s;s->next=p;D、p->next=s;s->next=q;12、在線性結(jié)構(gòu)中,第一個(gè)結(jié)點(diǎn)沒有前趨結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前趨結(jié)點(diǎn)。棧和隊(duì)列1、在棧操作中,輸入序列為〔A,B,C,D,不可能得到的輸出數(shù)列是〔DA、〔A,B,C,DB、〔D,C,B,AC、〔A,C,D,BD、〔C,A,D,B2、設(shè)棧ST用順序存儲(chǔ)結(jié)構(gòu)表示,則棧ST為空的條件〔BA、ST.top=ST.base<>0B、ST.top=ST.base==0C、ST.top=ST.base<>nD、ST.top=ST.base==n3、向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí),執(zhí)行〔CA、HS->next=s;B、s->next=HS->next;HS->next=s;C、s->next=HS;HS=S;D、s->next=HS;HS=HS->next;4、從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn),用x保存被刪結(jié)點(diǎn)的值,則執(zhí)行〔CA、x=HS;HS=HS->next;B、HS=HS->next;x=HS->data;C、x=HS->data;HS=HS->next;D、s->next=HS;HS=HS->next;5、用單鏈表表示的鏈?zhǔn)娟?duì)列的隊(duì)頭在鏈表的〔A位置。A、鏈頭B、鏈尾C、鏈中6、判定一個(gè)鏈隊(duì)列Ｑ〔最多元素個(gè)數(shù)為n為空的條件是〔AＡ、Ｑ.front==Q.rearB、Q.front!=Q.rearC、Q.front==<Q.rear+1>%nD、Q.front!=<Q.rear+1>%n7、在鏈隊(duì)列Ｑ中,插入要所指結(jié)點(diǎn)需順序執(zhí)行的指令是〔BA、Q.front->next=s;f=s;B、Q.rear->next=s;Q.rear=s;C、s->next=Q.rear;Q.rear=s;D、s->next=Q.front;Q.front=s;8、在一個(gè)鏈隊(duì)列Q中,刪除一個(gè)結(jié)點(diǎn)需要執(zhí)行的指令是〔CA、Q.rear=Q.front->next;B、Q.rear->next=Q.rear->next->next;C、Q.front->next=Q.front->next->next;D、Q.front=Q.rear->next;9、棧和隊(duì)列的共同點(diǎn)〔CA、都是先進(jìn)后出B、都是先進(jìn)先出C、只允許在端點(diǎn)處插入和刪除元素D、沒有共同點(diǎn)10、棧的特點(diǎn)是_先進(jìn)后出,隊(duì)列的特點(diǎn)是先進(jìn)先出11、線性表、棧和隊(duì)列都是線性結(jié)構(gòu),可以在線性表的任何位置插入和刪除元素；對(duì)于棧只能在棧頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入元素和在隊(duì)首刪除元素。串和數(shù)組1、設(shè)串s1=’ABCDEFG’,s2=’PQRST’,函數(shù)Concat<x,y>返回x和y串的連接串,Substr<s,I,j>返回串s從序號(hào)i開始的j個(gè)字符組成的子串,length<s>返回串s的長度,則Concat<Substr<s1,2,length<s2>,Substr<s1,length<s2>,2>>的結(jié)果串是〔DA、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF2、串是一種特殊的線性表,其特殊性體現(xiàn)在〔DA、可以順序存儲(chǔ)B、數(shù)據(jù)元素是一個(gè)字符C、可以鏈接存儲(chǔ)D、數(shù)據(jù)元素可以是多個(gè)字符3、設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作〔BA、連接B、模式匹配C、求子串聯(lián)D、求串長4、串的兩種最基本的存儲(chǔ)方式是順序存儲(chǔ)方式和鏈接存儲(chǔ)方式。樹和二叉樹1、樹最合適用來表示〔BA、有序數(shù)據(jù)元素B、元素之間具有分支層次關(guān)系的數(shù)據(jù)C、無序數(shù)據(jù)元素D、元素之間無聯(lián)系的數(shù)據(jù)2、按照二叉樹的定義,具有3個(gè)結(jié)點(diǎn)的二叉樹有〔C種。A、3B、4C、5D、63、在一棵有n個(gè)結(jié)點(diǎn)的二叉樹中,若度為2的結(jié)點(diǎn)數(shù)為n2,度為1的結(jié)點(diǎn)數(shù)為n1,度為0的結(jié)點(diǎn)數(shù)為n0,則樹的最大高度為〔E,其葉結(jié)點(diǎn)數(shù)為〔G；樹的最小高度為〔B,其葉結(jié)點(diǎn)數(shù)為〔G；若采用鏈表存儲(chǔ)結(jié)構(gòu),則有〔I個(gè)空鏈域。A、n/2B、[log2n]+1C、log2nD、nE、n0+n1+n2F、n1+n2G、n2+1H、1I、n+1J、n1K、n2L、n1+14、在一棵二叉樹上第5層的結(jié)點(diǎn)數(shù)最多為〔B?！布僭O(shè)根結(jié)點(diǎn)的層數(shù)為0A、8B、16C、15D、325、深度為5的二叉樹至多有〔C個(gè)結(jié)點(diǎn)。A、16B、32C、31D、106、在一非空二叉樹的中序遍歷序列中,根結(jié)點(diǎn)的右邊〔AA、只有右子樹上的所有結(jié)點(diǎn)B、只有右子樹上的部分結(jié)點(diǎn)C、只有左子樹上的部分結(jié)點(diǎn)D、只有左子樹上的所有結(jié)點(diǎn)7、一棵完全二叉樹按層次遍歷的序列為ABCDEFGHI,則在先序遍歷中結(jié)點(diǎn)E的直接前趨為〔D,后序遍歷中結(jié)點(diǎn)B的直接后繼是〔E。A、BB、DC、AD、IE、FF、C8、已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是〔DA、acbedB、decabC、deabcD、cedba9、在樹形結(jié)構(gòu)中,樹根結(jié)點(diǎn)沒有___前趨________結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_______1______個(gè)前趨結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有______后繼___________結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以__任意多個(gè)____。10、有一棵樹如圖所示,回答下面的問題：K1K1K7K6K5K2K3K4這棵樹的根結(jié)點(diǎn)是____K1_______,這棵樹的葉子結(jié)點(diǎn)是__K2,K5,K7,K4______；結(jié)點(diǎn)k3的度是____2________;這棵樹的度為___3_______；這棵樹的深度是_____4_________；結(jié)點(diǎn)k3的子女是______K5,K6_____；結(jié)點(diǎn)k3的父結(jié)點(diǎn)是_____K1_________.11、已知一棵二叉樹的中序遍歷序列為CDBAEGF,前序遍歷序列為ABCDEFG,試問能不能惟一確定一棵二叉樹,若能請(qǐng)畫出該二叉樹。若給定前序遍歷序列和后序遍歷序列,能否惟一確定一棵二叉樹,說明理由。答：=1\*GB2⑴由中序遍歷序列和前序遍歷序列或中序遍歷序列和后序遍歷序列可以惟一確定一棵二叉樹?；舅枷胧乔靶颉埠笮蚨ǜ?中序分左右。對(duì)于給定的前序和中序序列?？纱_定根結(jié)點(diǎn)為A,以A為根的左子樹結(jié)點(diǎn)為B,C,D,右子樹結(jié)點(diǎn)為E,F,G。進(jìn)一步可確定所有子樹的根結(jié)點(diǎn),因而也就確定了整個(gè)二叉樹。對(duì)應(yīng)的二叉樹如圖所示：FFADGFECB=2\*GB2⑵由前序遍歷和后序遍歷序列不能惟一確定一棵二叉樹。如圖所示為4棵不同的二叉樹,它們的前序遍歷序列都是ABC,而后序遍歷序列都是CBA。AACBCBAACBACB12、設(shè)二叉樹bt的存儲(chǔ)結(jié)構(gòu)如下：12345678910left00237580101datajhfdbacegiright0009400000其中bt為樹根結(jié)點(diǎn)指針,left,right分別為結(jié)點(diǎn)的左右孩子指針域,data為結(jié)點(diǎn)的數(shù)據(jù)域,請(qǐng)完成下列各題：=1\*GB2⑴畫出二叉樹bt的邏輯結(jié)構(gòu)=2\*GB2⑵寫出按前序、中序和后序遍歷二叉樹bt所得到的結(jié)點(diǎn)序列。答：=1\*GB2⑴二叉樹bt的邏輯結(jié)構(gòu)如圖所示：1212ajighfdecb=2\*GB2⑵前序遍歷：abcedfhgij中序遍歷：ecbhfdjiga后序遍歷：echfjigdba13、給定一棵以二叉鏈表存儲(chǔ)結(jié)構(gòu)表示的二叉樹,其根結(jié)點(diǎn)指針為T,試寫出求二叉樹的葉子數(shù)目的算法。intCountLeaf<BiTreeT>{//返回指針T所指二叉樹中所有葉子結(jié)點(diǎn)個(gè)數(shù)if<!T>return0;if<!T->lchild&&!T->rchild>return1;else{m=CountLeaf<T->lchild>;n=CountLeaf<T->rchild>;return<m+n>;}//else}//CountLeaf14、給定一棵以二叉鏈表存儲(chǔ)結(jié)構(gòu)表示的二叉樹,其根結(jié)點(diǎn)指針為T,試寫出求二叉樹的深度的算法。intDepth<BiTreeT>{//返回二叉樹的深度if<!T>depthval=0;else{depthLeft=Depth<T->lchild>;depthRight=Depth<T->rchild>;depthval=1+<depthLeft>depthRight?depthLeft:depthRight>;}returndepthval;}圖1、一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有〔C條邊。A、nB、n<n-1>C、n<n-1>/2D、2n2、具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有〔A條邊才能確保是一個(gè)連通圖。A、5B、6C、7D、83、存儲(chǔ)稀疏圖的數(shù)據(jù)結(jié)構(gòu)常用的是〔CA、鄰接矩陣B、三元組C、鄰接表D、十字鏈表4、在有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)中,頂點(diǎn)V在表結(jié)點(diǎn)中出現(xiàn)的次數(shù)是〔CA、頂點(diǎn)V的度B、頂點(diǎn)V的出度C、頂點(diǎn)V的入度D、依附于頂點(diǎn)V的邊數(shù)5、用DFS遍歷一個(gè)無環(huán)有向圖,并在DFS算法退棧返回時(shí),打印出相應(yīng)的頂點(diǎn),則輸出的頂點(diǎn)序列是〔AA、逆拓?fù)溆行虻腂、拓?fù)溆行虻腃、無序的6、已知一個(gè)圖如圖所示,若從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷,則可能得到的一種頂點(diǎn)序列為〔D,按廣度優(yōu)先搜索法進(jìn)行遍歷,則可能得到的一種頂點(diǎn)序列為〔B。=1\*GB2⑴A、abecdfB、acfebdC、acebfdD、acfdeb=2\*GB2⑵A、abcedfB、abcefdC、abedfcD、acfdebCCacfdeb7、采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先搜索遍歷算法類似于二叉樹的〔DA、中序遍歷B、先序遍歷C、后序遍歷D、按層遍歷8、已知一個(gè)圖如圖所示,則由該圖得到的一種拓?fù)湫蛄袨椤睞1165432A、V1,V4,V6,V2,V5,V3B、V1,V2,V3,V4,V5,V6C、V1,V4,V2,V3,V6,V5D、V1,V2,V4,V6,V3,V59、在圖形結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以___任意多個(gè)_______。10、在AOE網(wǎng)中,從源點(diǎn)到匯點(diǎn)各活動(dòng)時(shí)間總和最長的路徑稱為關(guān)鍵路徑。11、給出圖G,如圖所示：11111098765432〔1給出圖G的鄰接表〔畫圖即可〔2在你給出的鄰接表的情況下,以頂點(diǎn)V4為根,畫出圖G的深度優(yōu)先生成樹和廣度優(yōu)先生成樹?！?將你畫出的廣度優(yōu)先生成樹轉(zhuǎn)換為對(duì)應(yīng)的二叉樹。答：〔1圖的鄰接表如下圖所示：略〔2以頂點(diǎn)V4為根的深度優(yōu)先生成樹和廣度優(yōu)先生成樹如圖所示11111098765432dd1111098765432〔3廣度優(yōu)先生成樹轉(zhuǎn)換成二叉樹如下圖所示111109117863452附錄習(xí)題及實(shí)驗(yàn)參考答案習(xí)題1參考答案1.1.選擇題<1>.A.<2>.A.<3>.A.<4>.B.,C.<5>.A.<6>.A.<7>.C.<8>.C.<9>.B.<10.>A.1.2.填空題<1>.數(shù)據(jù)關(guān)系<2>.邏輯結(jié)構(gòu)物理結(jié)構(gòu)<3>.線性數(shù)據(jù)結(jié)構(gòu)樹型結(jié)構(gòu)圖結(jié)構(gòu)<4>.順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)散列表〔Hash存儲(chǔ)<5>.變量的取值范圍操作的類別<6>.數(shù)據(jù)元素間的邏輯關(guān)系數(shù)據(jù)元素存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系<7>.關(guān)系網(wǎng)狀結(jié)構(gòu)樹結(jié)構(gòu)<8>.空間復(fù)雜度和時(shí)間復(fù)雜度<9>.空間時(shí)間<10>.Ο<n>1.3名詞解釋如下：數(shù)據(jù)：數(shù)據(jù)是信息的載體,是計(jì)算機(jī)程序加工和處理的對(duì)象,包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)指不可分割的、具有獨(dú)立意義的最小數(shù)據(jù)單位,數(shù)據(jù)項(xiàng)有時(shí)也稱為字段或域。數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位,在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理,一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)就是指數(shù)據(jù)元素間的關(guān)系。數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)表示數(shù)據(jù)元素的存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系。數(shù)據(jù)類型：是指變量的取值范圍和所能夠進(jìn)行的操作的總和。算法：是對(duì)特定問題求解步驟的一種描述,是指令的有限序列。1.4語句的時(shí)間復(fù)雜度為：<1>Ο<n2><2>Ο<n2><3>Ο<n2><4>Ο<n-1><5>Ο<n3>1.5參考程序：main<>{intX,Y,Z；scanf<"%d,%d,%d",&X,&Y,Z>；if<X>=Y>if<X>=Z>if<Y>=Z>{printf<"%d,%d,%d",X,Y,Z>;}else{printf<"%d,%d,%d",X,Z,Y>;}else{printf<"%d,%d,%d",Z,X,Y>;}elseif<Z>=X>if<Y>=Z>{printf<"%d,%d,%d",Y,Z,X>;}else{printf<"%d,%d,%d",Z,Y,X>;}else{printf<"%d,%d,%d",Y,X,Z>;}}1.6參考程序：main<>{inti,n;floatx,a[],p;printf<"\nn=">;scanf<"%f",&n>;printf<"\nx=">;scanf<"%f",&x>;for<i=0;i<=n;i++>scanf<"%f",&a[i]>;p=a[0];for<i=1;i<=n;i++>{p=p+a[i]*x;x=x*x;}printf<"%f",p>’}習(xí)題2參考答案2.1選擇題<1>.C.<2>.B.<3>.B.<4>.B.5.D.6.B.7.B.8.A.9.A.10.D.2.2.填空題<1>.有限序列<2>.順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)<3>.Ｏ<n>O<n><4>.n-i+1n-i<5>.鏈?zhǔn)?lt;6>.數(shù)據(jù)指針<7>.前驅(qū)后繼<8>.Ο<1>Ο<n><9>.s->next=p->next;p->next=s;<10>.s->next2.3.解題思路：將順序表A中的元素輸入數(shù)組a,若數(shù)組a中元素個(gè)數(shù)為n,將下標(biāo)為0,1,2,…,〔n-1/2的元素依次與下標(biāo)為n,n-1,…,〔n-1/2的元素交換,輸出數(shù)組a的元素。參考程序如下：main<>{inti,n;floatt,a[];printf<"\nn=">;scanf<"%f",&n>;for<i=0;i<=n-1;i++>scanf<"%f",&a[i]>;for<i=0;i<=<n-1>/2;i++>{t=a[i];a[i]=a[n-1-i];a[n-1-i]=t;}for<i=0;i<=n-1;i++>printf<"%f",a[i]>;}2.4算法與程序：main<>{inti,n;floatt,a[];printf<"\nn=">;scanf<"%f",&n>;for<i=0;i<n;i++>scanf<"%f",&a[i]>;for<i=1;i<n;i++>if<a[i]>a[0]{t=a[i];a[i]=a[0];a[0]=t;}printf<"%f",a[0]>;for<i=2;i<n;i++>if<a[i]>a[1]{t=a[i];a[i]=a[1];a[1]=t;}printf<"%f",a[0]>;}2.5算法與程序：main<>{inti,j,k,n;floatx,t,a[];printf<"\nx=">;scanf<"%f",&x>;printf<"\nn=">;scanf<"%f",&n>;for<i=0;i<n;i++>scanf<"%f",&a[i]>;//輸入線性表中的元素for<i=0;i<n;i++>{//對(duì)線性表中的元素遞增排序k=i;for<j=i+1;j<n;j++>if<a[j]<a[k]>k=j;if<k<>j>{t=a[i];a[i]=a[k];a[k]=t;}}for<i=0;i<n;i++>//在線性表中找到合適的位置if<a[i]>x>break;for<k=n-1;k>=i;i-->//移動(dòng)線性表中元素,然后插入元素xa[k+1]=a[k];a[i]=x;for<i=0;i<=n;i++>//依次輸出線性表中的元素printf<"%f",a[i]>;}2.6算法思路：依次掃描A和B的元素,比較A、B當(dāng)前的元素的值,將較小值的元素賦給C,如此直到一個(gè)線性表掃描完畢,最后將未掃描完順序表中的余下部分賦給C即可。C的容量要能夠容納A、B兩個(gè)線性表相加的長度。有序表的合并算法：voidmerge<SeqListA,SeqListB,SeqList*C>{inti,j,k；i=0；j=0；k=0；while<i<=A.last&&j<=B.last>if<A.data[i]<=B.data[j]>C->data[k++]=A.data[i++]；elseC->data[k++]=B.data[j++]；while<i<=A.last>C->data[k++]=A.data[i++]；while<j<=B.last>C->data[k++]=B.data[j++]；C->last=k-1；}2.7算法思路：依次將A中的元素和B的元素比較,將值相等的元素賦給C,如此直到線性表掃描完畢,線性表C就是所求遞增有序線性表。算法：voidmerge<SeqListA,SeqListB,SeqList*C>{inti,j,k；i=0；j=0；k=0；while<i<=A.last>while〔j<=B.last>if<A.data[i]=B.data[j]>C->data[k++]=A.data[i++]；C->last=k-1；}習(xí)題3參考答案3.1.選擇題<1>.D<2>.C<3>.D<4>.C<5>.B<6>.C<7>.C<8>.C<9>.B<10>.AB<11>.D<12>.B<13>.D<14>.C<15>.C<16>.D<17>.B<18>.C<19>.C<20>.C3.2.填空題FILO,FIFO-1,34X*+2Y*3/-stack.top++,stack.s[stack.top]=xp>llink->rlink=p->rlink,p->rlink->llink=p->rlink<R-F+M>%Mtop1+1=top2F==Rfront==rearfront==<rear+1>%nN-13.3答：一般線性表使用數(shù)組來表示的線性表一般有插入、刪除、讀取等對(duì)于任意元素的操作而棧只是一種特殊的線性表?xiàng)Ｖ荒茉诰€性表的一端插入〔稱為入棧,push或者讀取棧頂元素或者稱為"彈出、出棧"<pop>。3.4答：相同點(diǎn)：棧和隊(duì)列都是特殊的線性表,只在端點(diǎn)處進(jìn)行插入,刪除操作。不同點(diǎn)：棧只在一端〔棧頂進(jìn)行插入,刪除操作；隊(duì)列在一端〔top刪除,一端<rear>插入。3.5答：可能序列有14種：ABCD;ACBD;ACDB;ABDC;ADCB;BACD;BADC;BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA。3.6答：不能得到4,3,5,6,1,2,最先出棧的是4,則按321的方式出,不可能得到1在2前的序列,可以得到1,3,5,4,2,6,按如下方式進(jìn)行push<1>,pop<>,push<2>,push<3>,pop<>,push<4>,push<5>,pop<>,pop<>,pop<>,push<6>,pop<>。3.7答：stack3.8非遞歸:intvonvert<intno,inta[]>//將十進(jìn)制數(shù)轉(zhuǎn)換為2進(jìn)制存放在a[],并返回位數(shù){ intr; SeStacks,*p; P=&s; Init_stack<p>; while<no> { push<p,no%2>; no/=10; } r=0; while<!empty_stack<p>> { pop<p,a+r>; r++; } returnr;} 遞歸算法:voidconvert<intno>{ if<no/2>0> { Convert<no/2>; Printf<"%d",no%2>; } else printf<"%d",no>; }3.9參考程序：voidview<SeStacks>{ SeStack*p;//假設(shè)棧元素為字符型 charc; p=&s; while<!empty_stack<p>> { c=pop<p>; printf<"%c",c>; } printf<"\n">;}3.10答：char3.11參考程序：voidout<linkqueueq>{ inte; while<q.rear!=q.front> { dequeue<q,e>; print<e>;//打印 }}習(xí)題4參考答案4.1選擇題：<1>.A<2>.D<3>.C<4>.C<5>.B<6>.B<7>.D<8>.A<9>.B<10>.D4.2填空題：串長相等且對(duì)應(yīng)位置字符相等不含任何元素的串,0所含字符均是空格,所含空格數(shù)10"helloboy"181066由零個(gè)或多個(gè)任意字符組成的字符序列串中所含不同字符的個(gè)數(shù)364.3StrLength<s>=14,StrLength<t>=4,SubStr<s,8,7>="STUDENT",SubStr<t,2,1>="O",StrIndex<s,"A">=3,StrIndex<s,t>=0,StrRep<s,"STUDENT",q>="IAMAWORKER",4.4StrRep<s,"Y","+">;StrRep<s,"+*","*Y">;4.5空串：不含任何字符；空格串：所含字符都是空格串變量和串常量:串常量在程序的執(zhí)行過程中只能引用不能改變；串變量的值在程序執(zhí)行過程中是可以改變和重新賦值的主串與子串：子串是主串的一個(gè)子集串變量的名字與串變量的值:串變量的名字表示串值的標(biāo)識(shí)符4.6intEQUAl<S,T>{ char*p,*q; p=&S; q=&T; while<*p&&*q> { if<*p!=*q> return*p-*q; p++; q++; } return*p-*q;}4.7<1>6*8*6=288<2>1000+47*6=1282<3>1000+<8+4>*6=1072<4>1000+<6*7+4>*6=12764.8iijv1121215-132144347542665187539矩陣的三元組表習(xí)題5參考答案5.1選擇〔1C〔2B〔3C〔4B〔5C〔6D〔7C〔8C〔9B〔10C〔11B〔12C〔13C〔14C〔15C5.2填空〔11〔21036；1040〔32i〔41；n;n-1;2〔52k-1；2k-1〔6ACDBGJKIHFE〔7p!=NULL〔8Huffman樹〔9其第一個(gè)孩子;下一個(gè)兄弟〔10先序遍歷；中序遍歷5.3葉子結(jié)點(diǎn):C、F、G、L、I、M、K；非終端結(jié)點(diǎn)：A、B、D、E、J；各結(jié)點(diǎn)的度：結(jié)點(diǎn)：ABCDEFGLIJKM度：430120000100樹深：45.4無序樹形態(tài)如下：二叉樹形態(tài)如下：5.5二叉鏈表如下:AABC∧D∧E∧F∧G∧∧H∧∧I∧∧J∧三叉鏈表如下:∧A∧ACBCBF∧∧G∧∧D∧EF∧∧G∧∧D∧EJ∧∧I∧∧H∧J∧∧I∧∧H∧5.6先序遍歷序列:ABDEHICFJG中序遍歷序列:DBHEIAFJCG后序遍歷序列:DHIEBJFGCA5.7 <1>先序序列和中序序列相同：空樹或缺左子樹的單支樹； <2>后序序列和中序序列相同：空樹或缺右子樹的單支樹； <3>先序序列和后序序列相同：空樹或只有根結(jié)點(diǎn)的二叉樹。5.8這棵二叉樹為:5.9先根遍歷序列:ABFGLCDIEJMK后根遍歷序列:FGLBCIDMJKEA層次遍歷序列:ABCDEFGLIJKM5.10證明：設(shè)樹中結(jié)點(diǎn)總數(shù)為n,葉子結(jié)點(diǎn)數(shù)為n0,則n=n0+n1+……+nm〔1再設(shè)樹中分支數(shù)目為B,則B=n1+2n2+3n3+……+mnm〔2因?yàn)槌Y(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支,所以有n=B+1〔3將〔1和〔2代入〔3,得n0+n1+……+nm=n1+2n2+3n3+……+mnm+1從而可得葉子結(jié)點(diǎn)數(shù)為：n0=n2+2n3+……+<m-1>nm+15.11由5.10結(jié)論得,n0=<k-1>nk+1又由n=n0+nk,得nk=n-n0,代入上式,得n0=<k-1>〔n-n0+1葉子結(jié)點(diǎn)數(shù)為：n0=n<k-1>/k5.12intNodeCount<BiTreeT>

{//計(jì)算結(jié)點(diǎn)總數(shù)

if<T>

if<T->lchild==NULL>&&<T-->rchild==NULL>

return1;

elsereturnNodeCount<T->lchild>+Node<T-->rchild>+1;

elsereturn0;

}5.13voidExchangeLR<Bitreebt>{/*將bt所指二叉樹中所有結(jié)點(diǎn)的左、右子樹相互交換*/if<bt&&<bt->lchild||bt->rchild>>{bt->lchild<->bt->rchild;Exchange-lr<bt->lchild>;Exchange-lr<bt->rchild>;}}/*ExchangeLR*/5.14intIsFullBitree<BitreeT>

{/*是則返回1,否則返回0。*/

Init_Queue<Q>;/*初始化隊(duì)列*/

flag=0;

In_Queue<Q,T>;/*根指針入隊(duì)列,按層次遍歷*/

while<!Empty_Queue<Q>>

{

Out_Queue<Q,p>;

if<!p>flag=1;/*若本次出隊(duì)列的是空指針時(shí),則修改flag值為1。若以后出隊(duì)列的指針存在非空,則可斷定不是完全二叉樹*/

elseif<flag>return0;/*斷定不是完全二叉樹*/

else

{

In_Queue<Q,p->lchild>;

In_Queue<Q,p->rchild>;/*不管孩子是否為空,都入隊(duì)列。*/

}

}/*while*/

return1;/*只有從某個(gè)孩子指針開始,之后所有孩子指針都為空,才可斷定為完全二叉樹*/

}/*IsFullBitree*/5.15轉(zhuǎn)換的二叉樹為：5.16對(duì)應(yīng)的森林分別為：CC5.17typedefcharelemtype;typedefstruct{elemtypedata;intparent;}NodeType;<1>求樹中結(jié)點(diǎn)雙親的算法:intParent<NodeTypet[],elemtypex>{/*x不存在時(shí)返回-2,否則返回x雙親的下標(biāo)<根的雙親為-1*/for<i=0;i<MAXNODE;i++>if<x==t[i].data>returnt[i].parent;return-2;}/*Parent*/<2>求樹中結(jié)點(diǎn)孩子的算法:voidChildren<NodeTypet[],elemtypex>{for<i=0;i<MAXNODE;i++>{if<x==t[i].data>break;/*找到x,退出循環(huán)*/}/*for*/if<i>=MAXNODE>printf<"x不存在\n">;else{flag=0;for<j=0;j<MAXNODE;j++>if<i==t[j].parent>{printf<"x的孩子:%c\n",t[j].data>;flag=1;}if<flag==0>printf<"x無孩子\n">;}}/*Children*/5.18typedefcharelemtype;typedefstructChildNode{intchildcode;structChildNode*nextchild;}typedefstruct{elemtypedata;structChildNode*firstchild;}NodeType;<1>求樹中結(jié)點(diǎn)雙親的算法:intParentCL<NodeTypet[],elemtypex>{/*x不存在時(shí)返回-2,否則返回x雙親的下標(biāo)*/for<i=0;i<MAXNODE;i++>if<x==t[i].data>{loc=i;/*記下x的下標(biāo)*/break;}if<i>=MAXNODE>return-2;/*x不存在*//*搜索x的雙親*/for<i=0;i<MAXNODE;i++>for<p=t[i].firstchild;p!=NULL;p=p->nextchild>if<loc==p->childcode>returni;/*返回x結(jié)點(diǎn)的雙親下標(biāo)*/}/*ParentL*/<2>求樹中結(jié)點(diǎn)孩子的算法:voidChildrenCL<NodeTypet[],elemtypex>{for<i=0;i<MAXNODE;i++>if<x==t[i].data>/*依次打印x的孩子*/{flag=0;/*x存在*/for<p=t[i].firstchild;p;p=p->nextchild>{printf<"x的孩子:%c\n",t[p->childcode].data>;flag=1;}if<flag==0>printf<"x無孩子\n">;return;}/*if*/printf<"x不存在\n">;return;}/*ChildrenL*/5.19typedefcharelemtype;typedefstructTreeNode{elemtypedata;structTreeNode*firstchild;structTreeNode*nextsibling;}NodeType;voidChildrenCSL<NodeType*t,elemtypex>{/*層次遍歷方法*/Init_Queue<Q>;/*初始化隊(duì)列*/

In_Queue<Q,t>;count=0;while<!Empty_Queue<Q>>{

Out_Queue<Q,p>;

if<p->data==x>{/*輸出x的孩子*/p=p->firstchild;if<!p>printf<"無孩子\n">;else{printf<"x的第%i個(gè)孩子:%c\n",++count,p->data>;/*輸出第一個(gè)孩子*/p=p->nextsibling;/*沿右分支*/while<p>{printf<"x的第%i個(gè)孩子:%c\n",++count,p->data>;p=p->nextsibling;}}return;}if<p->firstchild>In_Queue<Q,p->firstchild>;

if<p->nextsibling>In_Queue<Q,p->nextsibling>;}}/*ChildrenCSL*/

5.20<1>哈夫曼樹為:69692816941192210512743<2>在上述哈夫曼樹的每個(gè)左分支上標(biāo)以1,右分支上標(biāo)以0,并設(shè)這7個(gè)字母分別為A、B、C、D、E、F和H,如下圖所示：則它們的哈夫曼樹為分別為:A：1100B：1101C：10D：011E：00F：010H：111習(xí)題6參考答案6.1選擇題〔1C〔2A〔3B〔4C〔5B______條邊?！?B〔7A〔8A〔9B〔10A〔11A〔12A〔13B〔14A〔15B〔16A〔17C6.2填空〔14〔21對(duì)多;多對(duì)多〔3n-1;n〔40_〔5有向圖〔61〔7一半〔8一半〔9___第i個(gè)鏈表中邊表結(jié)點(diǎn)數(shù)___〔10___第i個(gè)鏈表中邊表結(jié)點(diǎn)數(shù)___〔11深度優(yōu)先遍歷；廣度優(yōu)先遍歷〔12O〔n2〔13___無回路6.3〔1鄰接矩陣:〔2鄰接鏈表：〔3每個(gè)頂點(diǎn)的度：頂點(diǎn)度V13V23V32V43V536.4〔1鄰接鏈表：〔2逆鄰接鏈表：〔3頂點(diǎn)入度出度V130V222V312V413V521V6236.5〔1深度優(yōu)先查找遍歷序列：V1V2V3V4V5;V1V3V5V4V2;V1V4V3V5V2〔1廣度優(yōu)先查找遍歷序列：V1V2V3V4V5;V1V3V2V4V5;V1V4V3V2V56.6有兩個(gè)連通分量：6.7頂點(diǎn)〔1〔2〔3〔4〔5LowCloseCostVexLowCloseCostVexLowCloseCostVexLowCloseCostVexLowCloseCostVexV10101010101V211010110101V31111010101V43122220202V5∞152332404U{v1}{v1,v2}{v1,v2,v3}{v1,v2,v3,v4}{v1,v2,v3,v4,v5}T{}{<v1,v2>}{<v1,v2>,<v1,v3>}{<v1,v2>,<v1,v3>,<v2,v4>}{<v1,v2>,<v1,v3>,<v2,v4>,<v4,v5>}最小生成樹的示意圖如下：6.8拓?fù)渑判蚪Y(jié)果：V3V1V4V5V2V66.9〔1建立無向圖鄰接矩陣算法：提示：參見算法6.1因?yàn)闊o向圖的鄰接矩陣是對(duì)稱的,所以有for<k=0;k<G->e;k++>/*輸入e條邊,建立無向圖鄰接矩陣*/{scanf<"\n%d,%d",&i,&j>;G->edges[i][j]=G->edges[j][i]=1;}<2>建立無向網(wǎng)鄰接矩陣算法:提示：參見算法6.1。初始化鄰接矩陣：#defineINFINITY32768/*表示極大值*/for<i=0;i<G->n;i++>for<j=0;j<G->n;j++>G->edges[i][j]=INFINITY;輸入邊的信息：不僅要輸入邊鄰接的兩個(gè)頂點(diǎn)序號(hào),還要輸入邊上的權(quán)值for<k=0;k<G->e;k++>/*輸入e條邊,建立無向網(wǎng)鄰接矩陣*/{scanf<"\n%d,%d,%d",&i,&j,&cost>;/*設(shè)權(quán)值為int型*/G->edges[i][j]=G->edges[j][i]=cost;/*對(duì)稱矩陣*/}<3>建立有向圖鄰接矩陣算法:提示：參見算法6.1。6.10<1>建立無向圖鄰接鏈表算法：typedefVertexTypechar;intCreate_NgAdjList<ALGraph*G>

{/*輸入無向圖的頂點(diǎn)數(shù)、邊數(shù)、頂點(diǎn)信息和邊的信息建立鄰接表*/

scanf<"%d",&n>;if<n<0>return-1;/*頂點(diǎn)數(shù)不能為負(fù)*/

G->n=n;

scanf<"%d",&e>;if<e<0>return=1;/*邊數(shù)不能為負(fù)*/

G->e=e;for<m=0;m<G->n;m++>

G->adjlist[m].firstedge=NULL;/*置每個(gè)單鏈表為空表*/

for<m=0;m<G->n;m++>

G->adjlist[m].vertex=getchar<>;/*輸入各頂點(diǎn)的符號(hào)*/

for<m=1;m<=G->e;m++>

{

scanf<"\n%d,%d",&i,&j>;/*輸入一對(duì)鄰接頂點(diǎn)序號(hào)*/if<<i<0||j<0>return-1;

p=<EdgeNode*>malloc<sizeof<EdgeNode>>;/*在第i+1個(gè)鏈表中插入一個(gè)邊表結(jié)點(diǎn)*/p->adjvex=j;p->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=p;p=<EdgeNode*>malloc<sizeof<EdgeNode>>;/*在第j+1個(gè)鏈表中插入一個(gè)邊表結(jié)點(diǎn)*/p->adjvex=i;p->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=p;}/*for*/return0;/*成功*/}//Create_NgAdjList<2>建立有向圖逆鄰接鏈表算法：typedefVertexTypechar;intCreate_AdjList<ALGraph*G>

{/*輸入有向圖的頂點(diǎn)數(shù)、邊數(shù)、頂點(diǎn)信息和邊的信息建立逆鄰接鏈表*/

scanf<"%d",&n>;if<n<0>return-1;/*頂點(diǎn)數(shù)不能為負(fù)*/

G->n=n;

scanf<"%d",&e>;if<e<0>return=1;/*弧數(shù)不能為負(fù)*/

G->e=e;

for<m=0;m<G->n;m++>

G->adjlist[m].firstedge=NULL;/*置每個(gè)單鏈表為空表*/for<m=0;m<G->n;m++>

G->adjlist[m].vertex=getchar<>;/*輸入各頂點(diǎn)的符號(hào)*/

for<m=1;m<=G->e;m++>

{

scanf<"\n%d,%d",&t,&h>;/*輸入弧尾和弧頭序號(hào)*/if<<t<0||h<0>return-1;

p=<EdgeNode*>malloc<sizeof<EdgeNode>>;/*在第h+1個(gè)鏈表中插入一個(gè)邊表結(jié)點(diǎn)*/p->adjvex=t;p->next=G->adjlist[h].firstedge;G->adjlist[h].firstedge=p;}/*for*/return0;/*成功*/}//Create_AdjList6.11voidCreate_AdjM<ALGraph*G1,MGraph*G2>

{/*通過無向圖的鄰接鏈表G1生成無向圖的鄰接矩陣G2*/G2->n=G1->n;G2->e=G1->e;for<i=0;i<G2->n;i++>/*置G2每個(gè)元素為0*/for<j=0;j<G2->n;j++>G2->edges[i][j]=0;for<m=0;m<G1->n;m++>G2->vexs[m]=G1->adjlist[m].vertex;/*復(fù)制頂點(diǎn)信息*/num=〔G1->n/2==0?G1->n/2:G1->n/2+1;/*只要搜索前n/2個(gè)單鏈表即可*/for<m=0;m<num;m++>{p=G1->adjlist[m].firstedge;while<p>{/*無向圖的存儲(chǔ)具有對(duì)稱性*/G2->edges[m][p->adjvex]=G2->edges[p->adjvex][m]=1;p==p->next;}}/*for*/}/*Create_AdjM*/6.12voidCreate_AdjL<ALGraph*G1,MGraph*G2>

{/*通過無向圖的鄰接矩陣G1,生成無向圖的鄰接鏈表G2*/G2->n=G1->n;G2->e=G1->e;for<i=0;i<G1->n;i++>/*建立每個(gè)單鏈表*/{G2->vexs[i]=G1->adjlist[i].vertex;G2->adjlist[i].firstedge=NULL；for<j=i;j<G1->n;j++>/*對(duì)稱矩陣,只要搜索主對(duì)角以上的元素即可*/{if<G1->edges[i][j]==1>{p=<EdgeNode*>malloc<sizeof<EdgeNode>>;/*在第i+1個(gè)鏈表中插入一個(gè)邊表結(jié)點(diǎn)*/p->adjvex=j;p->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=p;p=<EdgeNode*>malloc<sizeof<EdgeNode>>;/*在第j+1個(gè)鏈表中插入一個(gè)邊表結(jié)點(diǎn)*/p->adjvex=i;p->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=p;}/*if*/}/*for*/}/*for*/}/*Create_AdjL*/6.13<1>鄰接矩陣中1的個(gè)數(shù)的一半;<2>若位于[i-1,j-1]或[j-1,i-1]位置的元素值等于1,則有邊相連,否則沒有。<3>頂點(diǎn)i的度等于第i-1行中或第i-1列中1的個(gè)數(shù)。6.14<1>鄰接鏈表中邊表結(jié)點(diǎn)的個(gè)數(shù)的一半;<2>若第i-1〔或j-1個(gè)單鏈表中存在adjvex域值等于j-1〔或i-1的邊表結(jié)點(diǎn),則有邊相連,否則沒有。<3>頂點(diǎn)i的度等于第i-1個(gè)單鏈表中邊表結(jié)點(diǎn)的個(gè)數(shù)。6.15提示：參見算法6.2和6.3。習(xí)題7參考答案7.1選擇題〔1C<2>C<3>C<4>B<5>A<6>A<7>D<8>B<9>D<10>B<11>B<12>A<13>C<14>C<15>A<16>D<17>C<18>B,C<19>B<20>A7.2填空題O<n>,O<log2n>1,2,4,8,5,log2<n+1>-1小于,大于增序序列,m-170;34,20,55n/m開放地址法,鏈地址法產(chǎn)生沖突的可能性就越大,產(chǎn)生沖突的可能性就越小關(guān)鍵碼直接②,①,⑦16,16,8,21直接定址法,數(shù)字分析法,平方取中法,折疊法,除留余數(shù)法,隨機(jī)數(shù)法開放地址法,再哈希法,鏈地址法,建立一個(gè)公共溢出區(qū)裝滿程度索引,快哈希函數(shù),裝填因子一個(gè)結(jié)點(diǎn)中序等于7.3一棵二叉排序樹<又稱二叉查找樹>或者是一棵空樹,或者是一棵同時(shí)滿足下列條件的二叉樹：<1>若它的左子樹不空,則左子樹上所有結(jié)點(diǎn)的鍵值均小于它根結(jié)點(diǎn)鍵值。<2>若它的右子樹不空,則右子樹上所有結(jié)點(diǎn)的鍵值均大于它根結(jié)點(diǎn)鍵值。<3>它的左、右子樹也分別為二叉排序樹。7.4對(duì)地址單元d=H<K>,如發(fā)生沖突,以d為中心在左右兩邊交替進(jìn)行探測(cè)。按照二次探測(cè)法,鍵值K的散列地址序列為：do=H<K>,d1=<d0+12>modm,d2=<d0-12>modm,d3=<d0+22>modm,d4=<d0-12>modm,……7.5衡量算法的標(biāo)準(zhǔn)有很多,時(shí)間復(fù)雜度只是其中之一。盡管有些算法時(shí)間性能很好,但是其他方面可能就存在著不足。比如散列查找的時(shí)間性能很優(yōu)越,但是需要關(guān)注如何合理地構(gòu)造散列函數(shù)問題,而且總存在著沖突等現(xiàn)象,為了解決沖突,還得采用其他方法。二分查找也是有代價(jià)的,因?yàn)槭孪缺仨殞?duì)整個(gè)查找區(qū)間進(jìn)行排序,而排序也是費(fèi)時(shí)的,所以常應(yīng)用于頻繁查找的場(chǎng)合。對(duì)于順序查找,盡管效率不高,但卻比較簡(jiǎn)單,常用于查找范圍較小或偶而進(jìn)行查找的情況。7.6此法要求設(shè)立多個(gè)散列函數(shù)Hi,i=1,…,k。當(dāng)給定值K與閉散列表中的某個(gè)鍵值是相對(duì)于某個(gè)散列函數(shù)Hi的同義詞因而發(fā)生沖突時(shí),繼續(xù)計(jì)算該給定值K在下一個(gè)散列函數(shù)Hi+1下的散列地址,直到不再產(chǎn)生沖突為止。7.7散列表由兩個(gè)一維數(shù)組組成。一個(gè)稱為基本表,另一個(gè)稱為溢出表。插入首先在基本表上進(jìn)行；假如發(fā)生沖突,則將同義詞存人溢出表。7.8結(jié)點(diǎn)個(gè)數(shù)為n時(shí),高度最小的樹的高度為1,有兩層,它有n-1個(gè)葉結(jié)點(diǎn),1個(gè)分支結(jié)點(diǎn)；高度最大的樹的高度為n-l,有n層,它有1個(gè)葉結(jié)點(diǎn),n-1個(gè)分支結(jié)點(diǎn)。7.9設(shè)順序查找以h為表頭指針的有序鏈表,若查找成功則返回結(jié)點(diǎn)指針p,查找失敗則返回null值。pointersqesrearch<pointerh,intx,pointerp>{p=null；while<h>if<x>h->key>h=h->link；else{if<x==h->key>p=h；return<p>；}}雖然鏈表中的結(jié)點(diǎn)是按從小到大的順序排列的,但是其存儲(chǔ)結(jié)構(gòu)為單鏈表,查找結(jié)點(diǎn)時(shí)只能從頭指針開始逐步進(jìn)行搜索,故不能用折半<二分>查找。7.10分析：對(duì)二叉排序樹來講,其中根遍歷序列為一個(gè)遞增有序序列。因此,對(duì)給定的二叉樹進(jìn)行中根遍歷,如果始終能保證前一個(gè)值比后一個(gè)值小,則說明該二叉樹是二叉排序樹。intbsbtr<bitreptrT>／*predt記錄當(dāng)前結(jié)點(diǎn)前趨值,初值為-∞*／{if<T==NULL>return<1>；else{b1=bsbtr<T->lchild>；／*判斷左子樹*／if<!b1||<predt>=T->data>>return<0>；*當(dāng)前結(jié)點(diǎn)和前趨比較*／predt=T->data；／*修改當(dāng)前結(jié)點(diǎn)的前趨值*／return<bsbtr<T->rchild>>；／*判斷右子樹并返回最終結(jié)果*／}}7.11<1>使用線性探查再散列法來構(gòu)造散列表如表下所示。散列表───────────────────────────────地址012345678910───────────────────────────────數(shù)據(jù)331131234382722───────────────────────────────〔2使用鏈地址法來構(gòu)造散列表,如下圖<3>裝填因子a=8／11。使用線性探查再散列法查找成功所需的平均查找次數(shù)為Snl=0．5<1+1／<1-a>>=0．5*<1+1／<1-8／11>>=7／3使用線性探查再散列法查找不成功所需的平均查找次數(shù)為：Unl=0．5<1+1／<1-a>2>=0．5*<1+1／<1-8／11>2>=65／9使用鏈地址法查找成功所需的平均查找次數(shù)為：Snc=l+a／2=1+8／22=15／11使用鏈地址法查找不成功所需的平均查找次數(shù)為：‘Unl=a+e-a=8／1l+e-8／117.12分析：在等查區(qū)間的上、下界處設(shè)兩個(gè)指針,由此計(jì)算出中間元素的序號(hào),當(dāng)中間元素大于給定值X時(shí),接下來到其低端區(qū)間去查找；當(dāng)中間元素小于給定值X時(shí),接下來到其高端區(qū)間去查找；當(dāng)中間元素等于給定值X時(shí),表示查找成功,輸出其序號(hào)。Intbinlist<sqtableA,ints,t,keytypeX>／*t、s分別為查找區(qū)間的上、下界*／{if<s<t>return<0>；／*查找失敗*／else{mid=<S+t>／2；switCh<mid>{casex<A.item[midJ.key：return<binlist<A,s,mid-l,X>>；／*在低端區(qū)間上遞歸*／casex==A.item[mid].key：return<mid>；／+查找成功*／casex>A.item[mid].key：return<a,mid+l,t,X>>；／*在高端區(qū)間上遞歸*／}}}7.13intsqsearch0<sqtableA,keytypeX>/*數(shù)組有元素n個(gè)*／{i=l；A.item[n+1].key=X；／t設(shè)置哨兵*／while<A.item[n+1].key!=X>i++；return<i%<n／1>>；／*找不到返回0,找到返回其下標(biāo)*／}查找成功平均查找長度為：<1+2+3+…+n>／n：<1+n>／2。查找不成功平均查找長度為：n+1。7.14散列函數(shù)：H<key>=100+<key個(gè)位數(shù)+key十位數(shù)>modl0；形成的散列表：100101102103104105106107108109987563464979615317查找成功時(shí)的平均長度為：<1+2+1+1+5+1+1+5+5+3>/10=2.5次。由于長度為10的哈希表已滿,因此在插人第11個(gè)記錄時(shí)所需作的比較次數(shù)的期望值為10,查找不成功時(shí)的平均長度為10。習(xí)題8參考答案8．1選擇題〔1B<2>A<3>D<4>C<5>B<6>A<7>B<8>C<9>A<10>C<11>D<12>C<13>C〔14D〔15C<16>B<17>D〔18C〔19B〔20D8.2填空題快速,歸并O〔log2n,O<nlog2n>歸并向上,根結(jié)點(diǎn)19,18,16,20,30,22〔6192318162030192318162030〔749,13,27,50,76,38,65,97〔88,8〔9插入,選擇〔每次選擇最大的〔10快速,歸并<11>O<1>,O<nlog2n><12>穩(wěn)定<13>3<14><15,20,50,40><15>O<log2n><16>O<n2><17>冒泡排序,快速排序<18>完全二叉樹,n/2<19>穩(wěn)定,不穩(wěn)定<20>2,4,<20,40,15>8.3.假定給定含有n個(gè)記錄的文件<r1,f2,…,rn>,其相應(yīng)的關(guān)鍵字為<k1,k2,…,kn>,則排序就是確定文件的一個(gè)序列rr,r2,,…,rn,,使得k1'≤k2'≤…≤kn',從而使得文件中n個(gè)記錄按其對(duì)應(yīng)關(guān)鍵字有序排列。如果整個(gè)排序過程在內(nèi)存中進(jìn)行,則排序叫內(nèi)部排序。假設(shè)在待排序的文件中存在兩個(gè)或兩個(gè)以上的記錄具有相同的關(guān)鍵字,若采用某種排序方法后,使得這些具有相同關(guān)鍵字的記錄在排序前后相對(duì)次序依然保持不變,則認(rèn)為該排序方法是穩(wěn)定的,否則就認(rèn)為排序方法是不穩(wěn)定的。8.4．穩(wěn)定的有：直接插入排序、二分法插入排序、起泡排序、歸并排序和直接選擇排序。8.5．初始記錄序列按關(guān)鍵字有序或基本有序時(shí),比較次數(shù)為最多。8.6．設(shè)5個(gè)元素分別用a,b,c,d,e表示,取a與b、c與d進(jìn)行比較。若a>b,c>d<也可能是a<b,c<d,此時(shí)情況類似>,顯然此時(shí)進(jìn)行了兩次比較,取b與d再比較,若b>d則a>b>d,若b<d,則有c>d>b,此時(shí)已進(jìn)行了3次比較,要使排序比較最多7次,可把另外兩個(gè)元素按折半檢索排序插入到上面所得的有序序列中,此時(shí)共需要4次比較。從而可得算法,共只需7次比較。8.7．題目中所說的幾種排序方法中,其排序速度都很快,但快速排序、歸并排序、基數(shù)排序和Shell排序都是在排序結(jié)束后才能確定數(shù)據(jù)元素的全部序列,而排序過程中無法知道部分連續(xù)位置上的最終元素。而堆排序則是每次輸出一個(gè)堆頂元素<即最大或最少值的元素>,然后對(duì)堆進(jìn)行再調(diào)整,保證堆頂元素總是當(dāng)前剩下元素的最大或最小的,從而可知,欲在一個(gè)大量數(shù)據(jù)的文件中,如含有15000個(gè)元素的記錄文件中選取前10個(gè)最大的元素,可采用堆排序進(jìn)行。8.8．二分法排序。8.9．voidinsertsort<seqlistr> ；{／／對(duì)順序表中記錄R[0一N—1>按遞增序進(jìn)行插入排序&NBSP；inti,j； ；for<i=n-2；i>=0;i-->／／在有序區(qū)中依次插入r[n-2]．．r[0] ；if<r[i].key>r[i+1].key>／／若不是這樣則r[i]原位不動(dòng) ；{ ；r[n]=r[i]；j=i+l；／／r[n]是哨兵 ；do{／／從左向右在有序區(qū)中查找插入位置 ；r[j-1]=r[j]；／／將關(guān)鍵字小于r[i]．key的記錄向右移 ；j++； ；}whle<r[j].keyr[j-1]=r[n]；／／將引i>插入到正確位置上 ；}／／endif ；}／／insertsort． ；8.10．建立初始堆：[9376948632654387517421290753011]&NBSP；&NBSP；第一次排序重建堆：[863694751765438301742129075]9378.11．在排序過程中,每次比較會(huì)有兩種情況出現(xiàn),若整個(gè)排序過程至少需作t次比較,則顯然會(huì)有2^t個(gè)情況,由于n個(gè)結(jié)點(diǎn)總共有n!種不同的排列,因而必須有n!種不同的比較路徑,于是：2t≥n!即t≥log2n!因?yàn)閘og2nl=nlog2n-n／ln2+log2n／2+O<1>故有l(wèi)og2n!≈nlog2n從而t≧nlog2n得證。8.12．依據(jù)堆定義可知：序列<1>、<2>、<4>是堆,<3>不是堆,從而可對(duì)其調(diào)整使之為如下的大根堆<100,95,80,60,40,95,82,10,20>。8.13．第一趟：[265301][129751][863937][694742][076438]&NBSP；&NBSP；第二趟：[129265301751][694742863937][076438]&NBSP；&NBSP；第三趟：[129265301694742751863937][076438]&NBSP；&NBSP；第四趟：[076129265301438694742751863937]&NBSP；8.14．<1>歸并排序：<18,29><25,47><12,58><10,51><18,25,29,47><10,12,51,58><10,12,18,25,29,47,51,58><2>快速排序：<10,18,25,12,29,58,51,47><10,18,25,12,29,47,51,58><10,12,18,25,29,47,51,58><3>堆排序：初始堆<大頂堆>：<58,47,51,29,18,12,25,10>第一次調(diào)整：<51,47,25,29,18,12,10><58>第二次調(diào)整：<47,29,25,10,18,12><51,58>第三次調(diào)整：<29,18,25,10,12><47,51,58>第四次調(diào)整：<25,18,12,10><29,47,51,58>第五次調(diào)整：<18,10,12><25,29,47,51,58>第六次調(diào)整：<12,10><18,25,29,47,51,58>第七次調(diào)整：<10,12,18,25,29,47,51,58>8.15．<1>直接插入排序。序號(hào)1234567891011