浙江工商大學(xué)數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題2

PAGEPAGE21數(shù)據(jù)結(jié)構(gòu)習(xí)題集一、選擇題１．在一個(gè)長(zhǎng)度為ｎ的順序表中,向第i個(gè)元素（１≤i≤ｎ+1)之前插入一個(gè)新元素時(shí)，需向后移動(dòng)B個(gè)元素。A。n—1B。n-i＋1Ｃ2。在一個(gè)具有n個(gè)單元的順序棧中,假定以地址低端作為棧底,以tｏp作為棧頂指針，則當(dāng)做退棧處理時(shí)，top變化為C。Ａ.top不變B。top=-nC。ｔop＝ｔop-1D．top=top+1３。向順序棧中壓入元素時(shí)，是A。Ａ。先存入元素，后移動(dòng)棧頂指針Ｂ.先移動(dòng)棧頂指針，后存入元素4。在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的A．Ａ。前一個(gè)位置B。后一個(gè)位置C。隊(duì)首元素位置Ｄ。隊(duì)尾元素位置5.若進(jìn)棧序列為1,２,3，４，進(jìn)棧過(guò)程中可以出棧，則C不可能是一個(gè)出棧序列。Ａ.3，４,2,１B.2，4，3，１C。１，４，2,36。在具有ｎ個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中,假定front和reａｒ分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件是C.A。front==ｒeａr＋1B。front+1＝=rｅarＣ.front==rearＤ．front＝=0７。在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中,假定froｎt和reaｒ分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)滿的條件是D。A。rｅar％n==ｆrontB.（rear－１）%ｎ==frontC。（ｒear—1）％ｎ==rｅarD。（rｅaｒ+１)%ｎ==frｏnｔ８．從一個(gè)具有n個(gè)節(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí),在查找成功的情況下，需平均比較D個(gè)結(jié)點(diǎn)。A．ｎB。n/2C。(n—1)/２D。（n+1）／２９.在一個(gè)單鏈表中，已知*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*ｑ和＊p之間插入＊s結(jié)點(diǎn),則執(zhí)行C.A。s－〉nｅxｔ=p—〉next；p-＞ｎexｔ=ｓ;B.p—〉nｅxt＝s—〉nexｔ；ｓ－>nｅｘt＝p;C。q—>neｘt=s；s-〉next＝p;D.p—〉ｎexｔ=s;ｓ—〉next=q;10。向一個(gè)棧項(xiàng)指針為hs的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí),則執(zhí)行C。A。hs—>ｎexｔ=s；Ｂ.s—>next＝hs—〉ｎexｔ；hs—〉ｎext=ｓ;Ｃ。s-〉next=hｓ;ｈｓ＝s；Ｄ。s->ｎｅxt＝hｓ；hs=hs—＞ｎext;11。在一個(gè)鏈隊(duì)列中,假定front和rｅaｒ分別為隊(duì)首指針和隊(duì)尾指針,則進(jìn)行插入*s結(jié)點(diǎn)的操作時(shí)應(yīng)執(zhí)行Ｂ。Ａ.ｆｒont-〉next=ｓ；ｆrｏnt=s；B.reａr—>nｅxt=s;rear＝s;C.ｆront=ｆronｔ－〉next;Ｄ。frｏnｔ=rｅaｒ—>neｘt；１2。線性表是A。A。一個(gè)有限序列，可以為空B.一個(gè)有限序列，不能為空C．一個(gè)無(wú)限序列，可以為空D。一個(gè)無(wú)限序列,不能為空１3。對(duì)順序存儲(chǔ)的線性表,設(shè)其長(zhǎng)度為ｎ,在任何位置上插入或刪除操作都是等概率的,刪除一個(gè)元素時(shí)大約要移動(dòng)表中的C個(gè)元素。Ａ。n＋１B.n－1Ｃ．(ｎ－1)/214.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí),其地址D。Ａ。必須是連續(xù)的Ｂ。部分地址必須是連續(xù)的C。一定是不連續(xù)的D.連續(xù)與否均可以15。設(shè)單鏈表中指針ｐ指著結(jié)點(diǎn)（數(shù)據(jù)域?yàn)椋恚?，指針f指著將要插入的新結(jié)點(diǎn)(數(shù)據(jù)域?yàn)閤)，當(dāng)x插在結(jié)點(diǎn)m之后時(shí),只要先修改B后修改p-〉liｎｋ＝ｆ即可。Ａ.f-〉lｉnk=p;Ｂ.ｆ-〉ｌink=p—〉link;Ｃ。ｐ->link=f-〉lｉｎｋ;D。f=nil;１6．在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)需修改指針B．Ａ。(（p—〉rlｉｎk）—〉rlink）—〉ｌiｎk=ｐ;p—＞rliｎk＝（p—〉rlｉnk)—〉rｌinｋ；B。(p—>lｌｉnk)->rlｉｎk=p—＞rlink;(p—>ｒｌiｎk)—〉lliｎk=p—>ｌlｉnk;C。p—>ｌｌink=（ｐ-〉lｌink)—＞llink；（(ｐ—〉llｉnｋ）—〉ｌliｎk）—〉rlｉｎk=p；D。（(p—＞ｌlｉnk)-〉lliｎk)－＞rlink=p;p-〉llｉnk＝（ｐ－>lｌiｎk)—〉llink;17。在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)的前趨結(jié)點(diǎn)(若存在)時(shí)需修改指針Ａ。Ａ。(（p-〉ｌlinｋ)-〉ｌlink)—〉ｒlinｋ=p;ｐ—〉lｌinｋ＝（ｐ-〉llinｋ）—＞lｌink;B。(（ｐ—＞rｌｉnk）—>ｒlｉnk)—>llink=p；p—>rlｉnk=（p－〉rlinｋ)->rlｉnｋ；C.(ｐ—>ｌｌｉnｋ)—〉ｒlink=p-〉ｒlinｋ；(ｐ—〉rlink）—〉lｌink=ｐ-〉lｌiｎk；D。p—〉llink=(p—〉llink)-〉ｌｌink；（(p->llｉnk）—〉ｌlｉnk)->rlinｋ=p;18.根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表分為單鏈表和B.A。循環(huán)鏈表B．多重鏈表C。普通鏈表D。無(wú)頭結(jié)點(diǎn)鏈表1９.在數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)叫C結(jié)構(gòu)。A．存儲(chǔ)Ｂ。物理C。邏輯Ｄ。物理和存儲(chǔ)２０。二分法查找A存儲(chǔ)結(jié)構(gòu)。A。只適用于順序Ｂ。只適用于鏈?zhǔn)紺。既適用于順序也適用于鏈?zhǔn)剑?既不適合于順序也不適合于鏈?zhǔn)?1.在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,邏輯上相鄰的元素在物理位置上B.A。一定相鄰Ｂ。不一定相鄰Ｃ。有時(shí)相鄰23。假定在一棵二叉樹(shù)中,雙分支結(jié)點(diǎn)數(shù)為15個(gè),單分支結(jié)點(diǎn)數(shù)為3２個(gè),則葉子結(jié)點(diǎn)數(shù)為B.A.15B。1６Ｃ.17D。4７2４。假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18個(gè),則它的最小高度Ｂ。性質(zhì)２A。４B。5Ｃ。6D。182５.在一棵二叉樹(shù)中第五層上的結(jié)點(diǎn)數(shù)最多為C。性質(zhì)1Ａ。8B.15C。１6D。３226.在一棵具有五層的滿二叉樹(shù)中,結(jié)點(diǎn)總數(shù)為A。性質(zhì)3Ａ.31B。32C。33D.1627。已知8個(gè)數(shù)據(jù)元素為(３4、７6、45、1８、26、54、92、65）,按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)后，最后兩層上的結(jié)點(diǎn)總數(shù)為B。不理解？Ａ．１Ｂ.2C。3D。428.由分別帶權(quán)為9、２、5、７的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù),該樹(shù)的帶權(quán)路徑長(zhǎng)度為C。A。2３B.37C.44Ｄ。４６為什么不是46？29．在樹(shù)中除根結(jié)點(diǎn)外,其余結(jié)點(diǎn)分成ｍ(m≥0）個(gè)A的集合Ｔ1,Ｔ2,T3。。。Tm，每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱為Ｔi的父結(jié)點(diǎn),Ti稱為T(mén)的子結(jié)點(diǎn)(1≤ｉ≤m)。A。互不相交B。可以相交C。葉結(jié)點(diǎn)可以相交D．樹(shù)枝結(jié)點(diǎn)可以相交30。下面答案D是查找二叉樹(shù)(又稱二叉排序樹(shù)）。A。二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差的絕對(duì)值不大于1B.二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于1C。二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)是有序的Ｄ.二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的關(guān)鍵字大于其左子樹(shù)（如果存在)所有結(jié)點(diǎn)的關(guān)鍵字值,且小于其右子樹(shù)(如果存在)所有結(jié)點(diǎn)的關(guān)鍵字值。３１.如果結(jié)點(diǎn)A有三個(gè)兄弟,而且B是A的雙親，則B的出度是B。A.3Ｂ。4C。5D。１32.一個(gè)深度為L(zhǎng)的滿K叉樹(shù)有如下性質(zhì):第L層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有K棵非空子樹(shù)。如果按層次順序從１開(kāi)始對(duì)全部結(jié)點(diǎn)編號(hào),編號(hào)為n的有右兄弟的條件是Ｂ。A。(ｎ—1)%k＝=0Ｂ.(n—1)%k!＝0C。n％k==0D.n%ｋ！=033。在完全二叉樹(shù)中,當(dāng)i為奇數(shù)且不等于１時(shí)，結(jié)點(diǎn)i的左兄弟是結(jié)點(diǎn)D，否則沒(méi)有左兄弟。A。2ｉ—1B。i+1C．２i＋１D。i－13４。某二叉樹(shù)T有ｎ個(gè)結(jié)點(diǎn),設(shè)按某種遍歷順序?qū)中的每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào),編號(hào)值為1,2，…,n且有如下性質(zhì)：T中任一結(jié)點(diǎn)Ｖ,其編號(hào)等于左子樹(shù)上的最小編號(hào)減１,而V的右子樹(shù)的結(jié)點(diǎn)中,其最小編號(hào)等于V左子樹(shù)上結(jié)點(diǎn)的最大編號(hào)加1。這時(shí)按B編號(hào).A。中序遍歷序列B。前序遍歷序列C。后序遍歷序列D。層次遍歷序列3５.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的B倍.A。1/2B.1C。２Ｄ。４３６.對(duì)于一個(gè)具有ｎ個(gè)頂點(diǎn)和e條邊的無(wú)向圖,若采用鄰接表表示,則表頭向量的大小為A。A.nB。n+1C。n—1D.ｎ＋e３7．具有n個(gè)頂點(diǎn)的無(wú)向完全圖,邊的總數(shù)為D條。Ａ.n—１B．ｎＣ。ｎ＋1D。n*（ｎ—1）/2３８.設(shè)圖G有n個(gè)頂點(diǎn)和ｅ條邊,當(dāng)G是非孤立頂點(diǎn)的連通圖時(shí)有２e>=ｎ，故可推得深度優(yōu)先搜索的時(shí)間復(fù)雜度為A。Ａ．O(e)B.O(n)C．O（ne)D.O（n+e)3９。最小代價(jià)生成樹(shù)Ｄ。Ａ。是唯一的B。不是唯一的C。唯一性不確定D。唯一性與原因的邊的權(quán)數(shù)有關(guān)４0。在無(wú)向圖G的鄰接矩陣A中,若Ａ[i，j］等于1,則A［j，i］等于Ｃ.A.ｉ＋jB。i-ｊＣ.１D.０４1。圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為A。（訪問(wèn)標(biāo)志位數(shù)組空間)Ａ.O(n）B。O(e)C。O(ｎ－e）D。O(ｎ+ｅ）４2.已知一個(gè)有序表為（1２、1８、２４、35、47、５0、62、８3、90、115、134）,當(dāng)二分查找值為90的元素時(shí),Ｂ次比較后查找成功;當(dāng)二分查找值為47的元素時(shí),Ｄ次比較后查找成功。A。1B．2C。3D。44３。散列函數(shù)有一個(gè)共同性質(zhì)，即函數(shù)值應(yīng)當(dāng)以D取其值域的每個(gè)值.Ａ.最大概率B。最小概率C．平均概率D。同等概率44。設(shè)散列地址空間為0~m-1,k為關(guān)鍵字,用p去除k,將所得的余數(shù)作為k的散列地址,即H（ｋ)＝ｋ％p。為了減少發(fā)生沖突的頻率，一般取p為Ｄ.A。小于m的最大奇數(shù)B。小于m的最大偶數(shù)C。mD。小于ｍ的最大素?cái)?shù)4５。目前以比較為基礎(chǔ)的內(nèi)部排序時(shí)間復(fù)雜度T(n)的范圍是A③；其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無(wú)關(guān)的是B②。Ａ.①O（ｌoｇ2n）～O（n）②O（loｎ２n）～O(n２)③O(nlｏg2n)～Ｏ(n2）④O(ｎ)~O（ｎ2)⑤O(ｎ)~Ｏ（nｌoｇ2n)B.①插入排序②先用二分法查找,找到后插入排序③快速排序④冒泡排序４6。設(shè)關(guān)鍵字序列為:３，7，6,9，８,１,4，5，2。進(jìn)行排序的最小交換次數(shù)是A．Ａ。6B.7C.8D．204７。在歸并排序過(guò)程中，需歸并的趟數(shù)為C。A。nＢ。√nＣ.loｇ2ｎ向上取整D。log2n向下取整48。一組記錄排序碼為(４6、７9、５6、38、40、84）,則利用堆排序的方法建立的初始堆為Ｂ．A．(79、46、56、３８、4０、８０)B。（８4、7９、５6、3８、40、４6)C。(８4、79、５６、4６、４0、38)D。（84、５6、７９、４0、４6、3８)4９。一組記錄的關(guān)鍵碼為（4６、79、56、38、40、84),則利用快速排序的方法,以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為C.A。(38、40、46、56、７9、84）B。（４0、38、46、79、５６、8４)Ｃ。（４0、３8、46、56、79、8４)D．(40、38、4６、84、5６、７9）50．在平均情況下快速排序的時(shí)間復(fù)雜性為C,空間復(fù)雜性為B；在最壞情況下（如初始記錄已有序),快速排序的時(shí)間復(fù)雜性為D,空間復(fù)雜性為A。Ａ.O(ｎ）B.O(log2n)C.O(nlｏｇ2n)D．O(ｎ２）選擇題參考答案:１。B2．C3。A４。A５.C６。C７。Ｄ8.D９.C10。C11。B1２.Ａ１3。Ｃ14。D1５.B１６。B17.Ａ１８。B1９．C2０.A21。B22。Ｄ23。B24。B２5。C26.Ａ27。B2８。C29。Ａ30。D３1.B３2。Ｂ3３。D３4．B３5．B３6．A37。D3８．Ａ３9.D40.C41.Ａ42。B,D４3。D44.D45。A:③B：②46。A采用選擇排序?qū)o定的關(guān)鍵字序列進(jìn)行排序,只需６次。４7.Ｃ４8。B４9。Ｃ5０.ＣBＤA二、填空題1。在線性結(jié)構(gòu)中第一結(jié)點(diǎn)［1]無(wú)前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有[2］一個(gè)前驅(qū)結(jié)點(diǎn);最后一個(gè)結(jié)點(diǎn)［3］無(wú)后繼結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有[4]一個(gè)后繼結(jié)點(diǎn)．２.在樹(shù)型結(jié)構(gòu)中,樹(shù)根結(jié)點(diǎn)沒(méi)有[1]前趨結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且僅有［２］一個(gè)前驅(qū)結(jié)點(diǎn);樹(shù)葉結(jié)點(diǎn)沒(méi)有[３]后繼結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的[４]后繼結(jié)點(diǎn)數(shù)不受限制。3。一個(gè)數(shù)據(jù)結(jié)構(gòu)用二元組表示時(shí)，它包括［1］數(shù)據(jù)元素的集合K和K上[2]二元關(guān)系的集合Ｒ。４。對(duì)于一個(gè)二維數(shù)組A［1．．m,1。.n］,若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素A[i,j］的相對(duì)地址(即偏移地址)為[1](i－1）*n+j-１。５。對(duì)于順序存儲(chǔ)的線性表,當(dāng)隨機(jī)插入或刪除一個(gè)元素時(shí)，約需平均移動(dòng)表長(zhǎng)[１］一半的元素。６．對(duì)于長(zhǎng)度為n的順序表，插入或刪除元素的時(shí)間復(fù)雜性為［1]O(n）;對(duì)于順序?；蜿?duì)列,插入或刪除元素的時(shí)間復(fù)雜性為［2］O（1）。7。在具有n個(gè)單元、順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有[１]n—1個(gè)元素。8．從順序表中刪除第i個(gè)元素時(shí),首先把第i個(gè)元素賦給［１]變參或函數(shù)名帶回，接著從[2］鏈接指針開(kāi)始向后的所有元素均[3]前移一個(gè)位置，最后使線性表的長(zhǎng)度［４］減１。9。在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)[1]相鄰位置決定的;在線性表的鏈接存儲(chǔ)中,元素之間的邏輯關(guān)系是通過(guò)［2］鏈接指針決定的。10。一個(gè)單鏈表中刪除*p結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行如下操作:（１)q=p—〉ｎexｔ；(2)p－>datａ=p—〉ｎｅxt—〉ｄata;(3）ｐ—〉nｅxt＝[１]q-〉ｎext或p—＞next—〉next；(4）fｒee(q）；11.若要在一個(gè)單鏈表中的*ｐ結(jié)點(diǎn)之前插入一個(gè)＊s結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：（1)ｓ-〉ｎext=[１]p—〉ｎext；（２)p->neｘt=s；(３）t=ｐ—〉daｔa;(4）p->data=[２]s—〉daｔa;（5）s－>data=［3]t；１２。對(duì)于線性表的順序存儲(chǔ),需要預(yù)先分配好存儲(chǔ)空間,若分配太多則容易造成存儲(chǔ)空間的[１]浪費(fèi)，若分配太少又容易在算法中造成［2]溢出,因此適應(yīng)于數(shù)據(jù)量變化不大的情況；對(duì)于線性表的鏈接存儲(chǔ)(假定采用動(dòng)態(tài)結(jié)點(diǎn)）,不需要[3］預(yù)先分配存儲(chǔ)空間,存儲(chǔ)器中的整個(gè)［4]動(dòng)態(tài)存儲(chǔ)區(qū)都可供使用,分配和回收結(jié)點(diǎn)都非常方便,能夠有效地利用存儲(chǔ)空間，在算法中不必考慮[5］溢出的發(fā)生，因此適應(yīng)數(shù)據(jù)量變化較大的情況.13.無(wú)論對(duì)于順序存儲(chǔ)還是鏈接存儲(chǔ)的棧和隊(duì)列來(lái)說(shuō)，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜性均相同,則為[1］O（1)。┏００20┓＊*14.一個(gè)稀疏矩陣為┃3000┃,則對(duì)應(yīng)的三元組線性表為┃00-15┃（（1，3,2)，(2,1,3）,(3，3,—１),(3,4,５）).┗００00┛1５。對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，則該樹(shù)中所有結(jié)點(diǎn)的度之和為n—1.16。在一棵二叉樹(shù)中,度為0的結(jié)點(diǎn)的個(gè)數(shù)為ｎ0，度為２的結(jié)點(diǎn)的個(gè)數(shù)為n2，則:n0＝n2+１。17.在二叉樹(shù)的順序存儲(chǔ)中,對(duì)于下標(biāo)為５的結(jié)點(diǎn)，它的雙親結(jié)點(diǎn)的下標(biāo)為[1］２,若它存在左孩子，則左孩子結(jié)點(diǎn)的下標(biāo)為［2]10,若它存在右孩子，則右孩子結(jié)點(diǎn)的下標(biāo)為［3］11。１8。假定一棵二叉樹(shù)的廣義表表示為A（B(,D），C（E（Ｇ),F)),則該樹(shù)的深度為［１］４,度為0的結(jié)點(diǎn)數(shù)為[2]３,度為1的結(jié)點(diǎn)數(shù)為［3］2,度為2的結(jié)點(diǎn)數(shù)為[4]2；C結(jié)點(diǎn)是Ａ結(jié)點(diǎn)的[5]右孩子，E結(jié)點(diǎn)是Ｃ結(jié)點(diǎn)的[６］左孩子。19。在一棵二叉排序樹(shù)中,按中序遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。20。由分別帶權(quán)為３，9，6,2，５的共五個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹(shù),則帶權(quán)路徑長(zhǎng)度為55。┏━━┳━━┳━━━┓21。假定在二叉樹(shù)的鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為┃left┃ｄata┃rｉgｈt┃，其中┗━━┻━━┻━━━┛dａｔa為值域,ｌｅft和rigｈt分別為鏈接左、右孩子結(jié)點(diǎn)的指針域,請(qǐng)?jiān)谙旅嬷行虮闅v算法中畫(huà)有橫線的地方填寫(xiě)合適的語(yǔ)句。ｖoidiｎoｒｄer（bt);{ｉfｂt!=niｌ{(1)［1]inｏrder(bt-〉ｌeft)；(2)[２］pｒｉntf(ｂｔ-〉data）;（3）［3]inorder(bt—〉rｉght);}}22．在圖G的鄰接表表示中,每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù),對(duì)于無(wú)向圖來(lái)說(shuō)等于該頂點(diǎn)的[1］度數(shù),對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的［2］出度數(shù).2３．假定一個(gè)圖具有ｎ個(gè)頂點(diǎn)和e條邊,則采用鄰接矩陣表示的空間復(fù)雜性為［１］O(n2),采用鄰接表表示的空間復(fù)雜性為［２]O(n+e）.2４.已知一個(gè)無(wú)向圖的鄰接矩陣如下所示，則從頂點(diǎn)A出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為［1]ABＣDFE,按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為[2]ABCEＦD.ＡＢCDEF┏0110１0┓A┃1010１1┃B┃110100┃C┃001001┃D┃１1０001┃E┗010110┛Ｆ２５。已知一個(gè)圖如下所示,在該圖的最小生成樹(shù)中,各邊的權(quán)值之和為20。10①②1５528⑤１2③３④2６。假定在有序表A［1。。20]上進(jìn)行二分查找,則比較一次查找成功的結(jié)點(diǎn)數(shù)為[１]1，比較兩次查找成功的結(jié)點(diǎn)數(shù)為[2］２,比較三次查找成功的結(jié)點(diǎn)數(shù)為[3]4，比較四次查找成功結(jié)點(diǎn)數(shù)為[4］８,比較五次查找成功的結(jié)點(diǎn)數(shù)為[５］5,平均查找長(zhǎng)度為[6]3。7。2７。在索引查找或分塊查找中，首先查找[1]索引表，然后再查找相應(yīng)的[2]子表或塊，整個(gè)索引查找的平均查找長(zhǎng)度等于查找索引表的平均查找長(zhǎng)度與查找相應(yīng)子表的平均查找長(zhǎng)度之[3]和。28.在散列存儲(chǔ)中,裝填因子α的值越大,存取元素時(shí)發(fā)生沖突的可能性就[１]越大,當(dāng)α的值越小,存取元素時(shí)發(fā)生沖突的可能性就［2］越小.２9.給定線性表（１８,２5,6３,50，42,32,９０),用散列方式存儲(chǔ)，若選用h(K）=K%9作為散列函數(shù),則元素18的同義詞元素共有［1］２個(gè),元素２5的同義詞元素共有[2]０個(gè)，元素５0的同義詞元素共有[3]1個(gè).30。在對(duì)一組記錄(5４，38,９6,23,1５，72,6０,45，83）進(jìn)行直接選擇排序時(shí),第四次選擇和交換后，未排序記錄(即無(wú)序表)為(５４，7２，60，9６,83)。31。在對(duì)一組記錄(５4,38,96，2３，１５，7２，６０，45，３８)進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄交換的次數(shù)為[1］7，在整個(gè)冒泡排序過(guò)程中共需進(jìn)行[2］5趟后才能完成。32。在歸并排序中,若待排序記錄的個(gè)數(shù)為2０，則共需要進(jìn)行［１]5趟歸并,在第三趟歸并中，是把長(zhǎng)度為［2]4的有序表歸并為長(zhǎng)度為［3］8的有序表。３3．在直接插入和直接選擇排序中,若初始數(shù)據(jù)基本正序,則選用［1]直接插入排序，若初始數(shù)據(jù)基本反序，則選用［2］直接選擇排序。34.在堆排序、快速排序和歸并排序中,若只從節(jié)省空間考慮,則應(yīng)首先選取[１]堆排序方法,其次選取［２]快速排序方法，最后選?。?］歸并排序方法;若只從排序結(jié)果的穩(wěn)定性考慮,則應(yīng)選取[4]歸并排序；若只從平均情況下排序最快考慮，則應(yīng)選取[5］快速排序方法;若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取[6]堆排序方法。填空題參考答案1。［1]無(wú)[２]一[3]無(wú)[4］一2。[1]前趨[2］一[３］后繼[４]后繼3。［1］數(shù)據(jù)元素［2］二元關(guān)系４。［１](ｉ-１)*n+j-15.［1]一半6。[1]O（n）[2]O(1)7。［1］n-1預(yù)先8。［1]變參或函數(shù)名[2]第ｉ+1個(gè)元素[3］前移[4]減19。[１]相鄰位置[２］鏈接指針10。[1］q—〉next或p->neｘt—〉ｎｅxt11。［1]p->ｎexｔ[2]ｓ—〉ｄata[3]ｔ12．［1］浪費(fèi)[2]溢出［3]預(yù)先分配[４]動(dòng)態(tài)存儲(chǔ)區(qū)[5］溢出１3.［1］O(１）14。[1]（(１，3，２),（２,1,３)，(３,3,—１），（3,４,5））１５。[1］ｎ—1１6。[1］n2＋1１7。［1]2[2]１0[3]1118。［1]4［2］３［３]2[4]２［5]右[6］左19。[1］中序２0。［１]5５21.[1]ｉnoｒdｅr（bｔ—>ｌeft）［２]ｐrｉnｔｆ(bｔ-〉data)[３］inorｄｅr（bt—〉ｒｉｇｈt)2２。[1］度數(shù)［2]出度數(shù)23.［1]Ｏ（n2)[２］O(n＋e）２４。[1]ABCＤFE［2]ABCＥFD25。［１]2０26.［１]１[2]2[3］4［4］8［5]５[6]3。727。[１]索引表［2］子表或塊[3]和２8.[１]越大[2］越小29。[１]2［2]0［3］130.[1]（５4，７2,６０,9６,８3)31。［1]7[2］532。[1］5［2］４[3]８３３.[１]直接插入排序[2]直接選擇排序34。[１]堆排序［2］快速排序[３］歸并排序［4］歸并排序[5]快速排序[6]堆排序三、判斷題1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位(×）。2.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位(×）。3．順序存儲(chǔ)的線性表可以隨機(jī)存取（√)。4.線性表中的元素可以是各種各樣的,但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此，是屬于同一數(shù)據(jù)對(duì)象（√）。5．在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因?yàn)榭梢詮念^結(jié)點(diǎn)查找任何一個(gè)元素（×）。6．在單鏈表中，要取得某個(gè)元素,只要知道該元素的指針即可,因此,單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)(×)。7．鏈表的每個(gè)結(jié)點(diǎn)中,都恰好包含一個(gè)指針(×).**8．?dāng)?shù)組是同類型值的集合(×）。//不是集合／/＊*9．使用三元組表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)時(shí)間(√）.*＊10。線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素都是原子,則廣義表便成為線性表（√)。１1。由樹(shù)轉(zhuǎn)換成二叉樹(shù),其根結(jié)點(diǎn)的右子樹(shù)總是空的(√）。1２。后序遍歷樹(shù)和中序遍歷與該樹(shù)對(duì)應(yīng)的二叉樹(shù)，其結(jié)果不同(×)。1３.若有一個(gè)結(jié)點(diǎn)是某二叉樹(shù)子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn)(×)。１4。若一個(gè)樹(shù)葉是某子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn)(√)。15。已知二叉樹(shù)的前序遍歷和后序遍歷序列并不能唯一地確定這棵樹(shù)，因?yàn)椴恢罉?shù)的根結(jié)點(diǎn)是哪一個(gè)（×)。1６。在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同,對(duì)于這種情況應(yīng)作特殊處理(×)。１7。有回路的圖不能進(jìn)行拓?fù)渑判?√）。18.連通分量是無(wú)向圖中的極小連通子圖(×）．//極大／／19．散列法存儲(chǔ)的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址(√)。20.散列表的查找效率取決于散列表造表時(shí)選取的散列函數(shù)和處理沖突的方法（√)．21。m階B-樹(shù)每一個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)都小于或等于m(√）。２２。中序遍歷二叉排序樹(shù)的結(jié)點(diǎn)就可以得到排好序的結(jié)點(diǎn)序列(√)。23。在二叉排序樹(shù)上插入新的結(jié)點(diǎn)時(shí),不必移動(dòng)其它結(jié)點(diǎn)，僅需改動(dòng)某個(gè)結(jié)點(diǎn)的指針,由空變?yōu)榉强占纯桑ā?.24。當(dāng)待排序的元素很多時(shí),為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間,這是影響時(shí)間復(fù)雜性的主要因素(√)．25.對(duì)于n個(gè)記錄的集合進(jìn)行快速排序，所需要的平均時(shí)間是O(nlog２n）(√)。２6.對(duì)于ｎ個(gè)記錄的集合進(jìn)行歸并排序,所需要的平均時(shí)間是O(nlog2n)（√）。27.堆中所有非終端結(jié)點(diǎn)的值均小于或等于(大于或等于)左右子樹(shù)的值(√).＊＊28。磁盤(pán)上的順序文件中插入新的記錄時(shí)，必須復(fù)制整個(gè)文件（×)。＊＊２9．在索引順序文件中插入新的記錄時(shí)，必須復(fù)制整個(gè)文件(×）.**30。索引順序文件是一種特殊的順序文件,因此通常存放在磁帶上（×）。判斷題參考答案1．×２。×3。√４?！蹋?。×６?！粒贰！?。×9?！?０?！蹋?.√12．×１3.×14.√15?！?６．×1７?！蹋保??！?9?！?0?！?1?！?2。√23。√24.√25.√２6．√27?！?8.×29?！?0?！了摹⒕C合題1。線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表,二是鏈表.試問(wèn):(1）兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)？(2)如果有ｎ個(gè)線性表同時(shí)并存,并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化,線性表的總數(shù)也會(huì)自動(dòng)地改變.在此情況下,應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么?(３)若線性表的總數(shù)基本穩(wěn)定,且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素,那么,應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)?為什么？1。解答:（１）順序存儲(chǔ)是按索引(隱含的）直接存取數(shù)據(jù)元素,方便靈活，效率高，但插入、刪除操作時(shí)將引起元素移動(dòng)，因而降低效率；鏈接存儲(chǔ)內(nèi)存采用動(dòng)態(tài)分配,利用率高,但需增設(shè)指示結(jié)點(diǎn)之間有序關(guān)系的指針域,存取數(shù)據(jù)元素不如順序存儲(chǔ)方便,但結(jié)點(diǎn)的插入、刪除操作十分簡(jiǎn)單.(２)應(yīng)選用鏈接表存儲(chǔ)結(jié)構(gòu)。其理由是，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表里各元素,這里存儲(chǔ)單元可以是連續(xù)的,也可以是不連續(xù)的。這種存儲(chǔ)結(jié)構(gòu),在對(duì)元素作插入或刪除運(yùn)算時(shí)，不需要移動(dòng)元素,僅修改指針即可。所以很容易實(shí)現(xiàn)表的容量擴(kuò)充。（3)應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。其理由是，每個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號(hào)成正比的常數(shù)．由此,只要確定了起始位置,線性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。2。用線性表的順序結(jié)構(gòu)來(lái)描述一個(gè)城市的設(shè)計(jì)和規(guī)劃合適嗎？為什么？2．解答：不合適.因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及非常多的項(xiàng)目，很復(fù)雜,經(jīng)常需要修改、擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。有鑒于此,順序線性表不能很好適應(yīng)其需要，故是不合適的。3。在單鏈表和雙向表中,能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到任一結(jié)點(diǎn)？3。解答：在單鏈表中只能由當(dāng)前結(jié)點(diǎn)訪問(wèn)其后的任一結(jié)點(diǎn)，因?yàn)闆](méi)有指向其前驅(qū)結(jié)點(diǎn)的指針。而在雙向鏈表中,既有指向后繼結(jié)點(diǎn)的指針又有指向前驅(qū)結(jié)點(diǎn)的指針，故可由當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)鏈表中任一結(jié)點(diǎn)。4。試述棧的基本性質(zhì)?4。解答：由棧的定義可知,這種結(jié)構(gòu)的基本性質(zhì)綜述如下:(1)集合性。棧是由若干個(gè)元素集合而成，當(dāng)沒(méi)有元素的空集合稱為空棧;(2)線性結(jié)構(gòu)。除棧底元素和棧頂元素外，棧中任一元素均有唯一的前驅(qū)元素和后繼元素;(3)受限制的運(yùn)算。只允許在棧頂實(shí)施壓入或彈出操作，且棧頂位置由棧指針?biāo)甘?（4)數(shù)學(xué)性質(zhì)。當(dāng)多個(gè)編號(hào)元素依某種順序壓入,且可任意時(shí)刻彈出時(shí),所獲得的編號(hào)元素排列的數(shù)目,恰好滿足卡塔南數(shù)列的計(jì)算，即:Ｃn=Cｎ2n/(n+1)其中,n為編號(hào)元素的個(gè)數(shù)，Cｎ是可能的排列數(shù)目。５.何謂隊(duì)列的上溢現(xiàn)象？解決它有哪些方法，且分別簡(jiǎn)述其工作原理。5。解答:在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為froｎｔ,隊(duì)尾指針為ｒeａr,隊(duì)的容量(存儲(chǔ)空間的大小)為m。當(dāng)有元素要加入隊(duì)列時(shí)，若ｒear=ｍ(初始時(shí)reat=0）,則發(fā)生隊(duì)列的上溢現(xiàn)象,該元素不能加入隊(duì)列。這里要特別注意的是：隊(duì)列的假溢出現(xiàn)象,隊(duì)列中還有空余的空間，但元素不能進(jìn)隊(duì)列.造成這種現(xiàn)象的原因是由于隊(duì)列的操作方式所致。解決隊(duì)列的上溢有以下幾種方法：(1)建立一個(gè)足夠大的存儲(chǔ)空間,但這樣做往往會(huì)造成空間使用的效率低。(2）當(dāng)出現(xiàn)假溢出時(shí)，可采用以下幾種方法：①采用平移元素的方法.每當(dāng)隊(duì)列中加入一個(gè)元素時(shí),隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置(當(dāng)然要有空余的空間可移);②每當(dāng)刪去一個(gè)隊(duì)頭元素時(shí)，則依次序移隊(duì)中的元素，始終使ｆroｎt指針指向隊(duì)列中的第一個(gè)位置;③采用循環(huán)隊(duì)列方式。把隊(duì)頭隊(duì)尾看成是一個(gè)首尾相鄰的循環(huán)隊(duì)列，雖然物理上隊(duì)尾在隊(duì)首之前，但邏輯上隊(duì)首依然在前，作插入和刪除運(yùn)算時(shí)仍按“先進(jìn)先出"的原則.6。兩個(gè)字符串相等的充要條件是什么？6。解答：兩個(gè)字符串相等的充要條件是：兩個(gè)串的長(zhǎng)度相等，且對(duì)應(yīng)位置的字符相等.*＊7。畫(huà)出廣義表(A（B（Ｅ，F(xiàn)(Ｊ)),C,D（G（Ｋ,L),H，Ｉ）)）對(duì)應(yīng)的樹(shù)型結(jié)構(gòu)。７.解答：根據(jù)廣義表的結(jié)構(gòu)可知，該樹(shù)的根結(jié)點(diǎn)為A；而B(niǎo)、C、Ｄ為Ａ的子樹(shù),B又有兩棵子樹(shù)等等，該廣義表對(duì)應(yīng)的樹(shù)型結(jié)構(gòu)見(jiàn)下圖.ABCDEFGHＩJKＬ**８。對(duì)于二叉排序樹(shù)，當(dāng)所有結(jié)點(diǎn)的權(quán)都相等的情況下，最佳二叉排序樹(shù)有何特點(diǎn).８.解答:其特點(diǎn)是只有最下面的二層結(jié)點(diǎn)可以小于２,其它結(jié)點(diǎn)的度數(shù)必須為２。9.試證明:已知一棵二叉樹(shù)的前序序列和中序序列，則可唯一地確定一棵二叉樹(shù)．9。證明利用前序遍歷的結(jié)果序列能夠得到各子樹(shù)的根,即從左到右檢查前序遍歷序列,當(dāng)?shù)玫礁Y(jié)點(diǎn)之后,利用根結(jié)點(diǎn)在中序遍歷序列中的位置可以確定其左右子樹(shù)，這樣便可逐次確定整個(gè)二叉樹(shù).假設(shè)BT為二叉樹(shù)的根，Ｐ１,Ｐ2,…,Ｐn為前序遍歷序列,I1，I2,…，Ｉn為中序遍歷序列。由前序遍歷序列可以得到BT＝P1.在中序遍歷序列中查找等于P1的結(jié)點(diǎn),設(shè)該結(jié)點(diǎn)為Iｉ，則有Ii＝Ｐ１．根據(jù)二叉樹(shù)中序遍歷的原理,則該二叉樹(shù)可被分成左右兩棵子樹(shù):對(duì)于左子樹(shù)，在中序遍歷序列中有I1，I２，…，Ii-1，依此序列在前序遍歷序列中可以得到其左子樹(shù)為Ｐ2,P3,…，Pｉ;同理，對(duì)于右子樹(shù)有Ii＋1,Ｉｉ+２,…，IｎPｉ＋１，Ｐｉ+2,…，Pｎ對(duì)于這兩棵子樹(shù)而言，其左子樹(shù)的根為Ｐ２,其右子樹(shù)的根為Pi＋１。依此類推，用同樣的方法就可以確定整個(gè)二叉樹(shù)。1０.證明ｎ個(gè)頂點(diǎn)的無(wú)向完全圖的邊數(shù)的n（n－1)／2.10。證明方法一：用歸納法證明當(dāng)ｎ＝1時(shí),邊數(shù)為0，結(jié)論成立.當(dāng)n＝2時(shí),邊數(shù)為1，結(jié)論成立.當(dāng)n＝1,2…，ｋ時(shí)均成立，即當(dāng)ｎ=k時(shí),邊數(shù)為k(k－１）/２?，F(xiàn)證明當(dāng)ｎ＝k+１時(shí)若仍然成立,則結(jié)論正確。由前面證得，對(duì)于有k個(gè)頂點(diǎn)時(shí)，其邊數(shù)總和為k(ｋ－1)/2.當(dāng)再增加一個(gè)新頂點(diǎn)時(shí)，由于是無(wú)向完全圖,故該頂點(diǎn)到原來(lái)各個(gè)頂點(diǎn)均有一條邊，這樣就共有邊數(shù)為k（k-１)/2＋k=k（k＋1)/2＝（k+1)[(k＋1)－1]/2可知當(dāng)頂點(diǎn)數(shù)k＋1時(shí)，結(jié)論仍然成立,故具有ｎ個(gè)頂點(diǎn)的無(wú)向完全圖的這數(shù)為ｎ（ｎ－1）／２方法二:在ｎ個(gè)頂點(diǎn)的無(wú)向完全圖中,每個(gè)頂點(diǎn)與其余各頂點(diǎn)均有一條邊.第一個(gè)頂點(diǎn)到其余各頂點(diǎn)的邊數(shù)為n－１,第二個(gè)頂點(diǎn)到其余各頂點(diǎn)的邊數(shù)為n－1,但它與第一個(gè)頂點(diǎn)之間的邊已在第一個(gè)頂點(diǎn)的邊中,故第二個(gè)頂點(diǎn)到其它n-2個(gè)頂點(diǎn)的邊為n-2，…,第n-１個(gè)到余下的第n個(gè)頂點(diǎn)為邊數(shù)為1，所以總的邊數(shù)為（n-１)+（n-２)+（n-3)＋…＋2+1=n(n-1）/2所以其結(jié)論成立。11。證明一個(gè)有n個(gè)頂點(diǎn),e條邊的無(wú)向圖Ｇ,必有∑dj=2e其中dj為頂點(diǎn)j的度。11。證明由度的定義可知，頂點(diǎn)j所聯(lián)接的邊數(shù)必為dj條,另一方面，圖G中的任一條邊均關(guān)聯(lián)Ｇ中的兩個(gè)頂點(diǎn)，即一條邊均要分別計(jì)入兩個(gè)不同的ｄj和di中，故∑dj中的邊數(shù)應(yīng)為G中邊數(shù)的兩倍,即有ｎ∑ｊ＝２eｉ-11２。證明：若無(wú)向圖G的頂點(diǎn)度數(shù)的最小值大于或等于2，則G有一條回路．12。證明方法一:設(shè)G＝（Ｖ，E)，任取一頂點(diǎn)v1∈V,因V１的度大于或等于2,在v1的鄰接頂點(diǎn)中任取一個(gè)不同于v１的頂點(diǎn)作為v2.因v２的度大于或等于2,在v2的鄰接頂點(diǎn)中任取一個(gè)不同于v2的頂點(diǎn)作為ｖ3.若v１、v2、v３不構(gòu)成回路,則在再v3的鄰接頂點(diǎn)中任取一個(gè)不同于v3的的頂點(diǎn)作為ｖ4,……。因?yàn)閳D中頂點(diǎn)的集合V是有限的，當(dāng)取得某個(gè)頂點(diǎn)vi后,vｉ+1一定為v1,v2,…，vi—1之一,因而構(gòu)成回路。命題得證.方法二:設(shè)圖G有n個(gè)頂點(diǎn)，整個(gè)圖G的度數(shù)之和為N,則有N≥2n我們知道,圖中每條邊涉及二個(gè)頂點(diǎn)，也就是每條邊含有２個(gè)度,這樣一來(lái),該圖G至少有n條邊.由于一個(gè)ｎ個(gè)頂點(diǎn)的樹(shù)圖只有n-1條邊,多于ｎ-1條邊時(shí)則樹(shù)圖就不存在,圖中會(huì)出現(xiàn)回路。由前面推得，該圖至少有ｎ條邊,故會(huì)出現(xiàn)回路。13。若對(duì)大小均為n的有序的順序表和無(wú)序的順序表分別進(jìn)行順序查找,試問(wèn)在下面三種情況下，分別討論兩者在等概率時(shí)，平均查找長(zhǎng)度是否相同?(1）查找不成功,即表中沒(méi)有關(guān)鍵字等于給定值ｋ的記錄；(２)查找成功，且表中只有一個(gè)關(guān)鍵字等于給定值k的記錄;(3)查找成功,且表中有若干個(gè)關(guān)鍵字等于給定值k的記錄,一次查找要求找出所有記錄,此時(shí)的平均查找長(zhǎng)度應(yīng)考慮找到所有記錄時(shí)所用的比較次數(shù)。1３．(1）解答:不相同。對(duì)于有序的順序表而言，當(dāng)表中無(wú)此關(guān)鍵字時(shí),只要在查找過(guò)程中發(fā)現(xiàn)順序表中的某個(gè)關(guān)鍵字大于待查的關(guān)鍵字時(shí),查找過(guò)程就可以結(jié)束（假定順序表是由小到大排列的,對(duì)于由大到小排列的情況類似）,沒(méi)有必要查找到表中最后一個(gè)關(guān)鍵字才確定查找不成功。而對(duì)于非有序的順序表,只有對(duì)表中的每一個(gè)關(guān)鍵字比較完之后,才能說(shuō)明查找不成功。顯然在等概率時(shí)兩種順序的平均查找長(zhǎng)度是不相同的。有序順序表的平均長(zhǎng)度為（n＋1）／２,而無(wú)序順序表的平均查找長(zhǎng)度為n。但從數(shù)量級(jí)上兩者是相同的，即O(n)。（2）解答:相同的。其分析類似于（１).兩者在等概率下的平均長(zhǎng)度為（n+1）／2，數(shù)量級(jí)上為O(n）．(３)解答：不相同。其分析完全與（1）相同,其結(jié)論也完全相同.14。假定有n個(gè)關(guān)鍵字，它們具有相同的Hａsh函數(shù)值,用線性探測(cè)方法把這n個(gè)關(guān)鍵字存入到Haｓh地址空間中要做多少次探測(cè)？14.解答：由于線性探測(cè)的查找次數(shù)主要取決于裝載因子α,即與Haｓｈ地址空間的占用情況有關(guān).假定初始時(shí)Hasｈ地址空間為空,在此情況下連續(xù)裝入n個(gè)具有相同的Hash函數(shù)值的關(guān)鍵字所需的總探測(cè)次數(shù)為１＋2+…＋n＝n(n+1)／215。有一個(gè)200０項(xiàng)的表,欲采用等分區(qū)間順序查找方法進(jìn)行查找,問(wèn)(1)每塊的理想長(zhǎng)度是多少？(2)分成多少塊最為理想?(３）平均查找長(zhǎng)度是多少?（4）若每塊長(zhǎng)度為20,平均查找長(zhǎng)度是多少?１５。解答：(1）在給定ｎ的前提下,理想的塊長(zhǎng)d為√n=√200０≈４5(2)因查找方法為等分區(qū)間順序查找,長(zhǎng)度為n的表被分成b＝[n/d］塊,d為塊長(zhǎng),故有b＝[n/ｄ]＝［２000/４5］=4５(3）平均查找長(zhǎng)度為ASＬ=b+d/2+1＝(４5＋45）/２+1=46（4)因每塊的長(zhǎng)度為２0,所以表被分成ｂ塊,其平均查找AＳL長(zhǎng)度為b=［n/d］＝[2000/２0]＝10０AＳL=(b+d)/２＋１＝(100＋20）/２+1＝６116.在執(zhí)行某種排序算法的過(guò)程中,出現(xiàn)了排序碼朝著最終排序序列相反的方向移動(dòng),從而認(rèn)為該排序算法是不穩(wěn)定的，這種說(shuō)法對(duì)嗎？為什么?1６。解答：這種說(shuō)法不對(duì)。因?yàn)榕判虻牟环€(wěn)定性是指排序前兩個(gè)排序碼相同的元素的相對(duì)次序經(jīng)過(guò)排序后發(fā)生了變化,而題中未涉及到元素的相對(duì)次序(特別是相同排序碼的元素）的改變,只有移動(dòng)方向，所以此種說(shuō)法不對(duì)。１7。設(shè)有5000個(gè)無(wú)序的元素，希望用最快速度挑選出其中前1０個(gè)最大的元素.在以下的排序方法中，采用哪種方法最好？為什么？快速排序,堆排序，歸并排序,基數(shù)排序的Shｅll排序.17。解答:上面所列的幾種排序方法的速度都很塊,但快速排序、歸并排序、基數(shù)排序和希爾排序都是在排序結(jié)束后才能確定數(shù)據(jù)元素的全部順序，而無(wú)法知道排序過(guò)程中部分元素的有序性。而堆排序則每次輸入一個(gè)最大(或最小)的元素，然后對(duì)堆進(jìn)行調(diào)整，保證堆頂?shù)脑乜偸怯嘞略刂凶畲螅ɑ蜃钚?的。根據(jù)題意,只要選取前10個(gè)最大的元素,故采用堆排序方法是合適的。*＊１８．證明對(duì)一個(gè)長(zhǎng)度為n的任意文件進(jìn)行排序,至少需要作nlｏg2n比較。1８。證明在排序過(guò)程中，每次時(shí)行元素的比較產(chǎn)生兩種路徑．如果排序過(guò)程至少需作t次比較,則有2t條路徑．由于n個(gè)結(jié)點(diǎn)總共有n種不同的排列,因而必須有n種不同的比較路徑。于是2t≥n!即t≥log2ｎ！因?yàn)椋靜g2ｎ?。絥lｏg2ｎ-ｎ/ln2＋1/2ｌoｇ2ｎ+O（1)故有ｌoｇ2n！≈nlｏg2nt≥nlｏｇ2n證畢．１9.判斷下列序列是否是堆。若不是堆,則把它們依次調(diào)整為堆。(1）（100，８5，９8,７7,8０，60,８２,４0，2０，１０，66）;(2)(100，98，85，8２,80，7７，66,6０,4０，2０,10)（3)(10０,85,４0,77,80,60,６6,98,８２,1０,2０);(４)(１０，20,40,６0,66,77，80，８2，８5，98,１0０)；1９。解答:根據(jù)堆的定義可知堆中元素滿足下面中的某一個(gè)式子的關(guān)系,┌≤k２i┌≥k2i①kｉ或②kｉ└≤ｋ2i+１└≥k2i＋１因此（1）、(２)和（4）序列是堆。（3)不是堆。（３)調(diào)整為1０0，98，6６，85，８0，60，40,７７,8２，10,20后成為堆。＊*20。試列出文件的存儲(chǔ)結(jié)構(gòu)以及其相應(yīng)文件類型,并簡(jiǎn)略回答其特點(diǎn)。20。解答:（1)順序結(jié)構(gòu)，相應(yīng)的文件為順序文件.這種文件中的記錄按存入文件的時(shí)間先后次序順序存放．當(dāng)記錄的物理存取順序與它們的關(guān)鍵碼大小順序一致時(shí)，則物理順序和邏輯順序是一致的.順序文件適合順序存取。(2)計(jì)算尋址結(jié)構(gòu),相應(yīng)的文件為散列文件。這種文件中的記錄,在存放時(shí),是根據(jù)它的關(guān)鍵碼值經(jīng)過(guò)散列函數(shù)計(jì)算來(lái)確定其地址的，散列函數(shù)把一個(gè)記錄的關(guān)鍵碼值經(jīng)過(guò)計(jì)算轉(zhuǎn)化為該記錄所對(duì)應(yīng)的地址．散列文件適合于隨機(jī)存取。(3)帶索引的結(jié)構(gòu),相應(yīng)的文件為帶索引文件.這種文件帶有一個(gè)索引表，索引表中的每一項(xiàng)內(nèi)容包含一個(gè)關(guān)鍵碼值和對(duì)應(yīng)于該關(guān)鍵碼值的相應(yīng)地址。一般情況下，索引表本身是按關(guān)鍵碼值的大小順序排列的,而帶索引文件本身內(nèi)容的物理順序與其邏輯順序可以是一致的，也可以是不一致的.帶索引文件是以索引表的物理順序來(lái)體現(xiàn)文件的邏輯次序的，即索引表的物理順序?qū)崿F(xiàn)了文件的線性結(jié)構(gòu).由以上三種文件可以派生出其它類型的文件。21。編寫(xiě)下列算法（1)向類型有l(wèi)ist的線性表Ｌ的第i個(gè)元素(０≤i≤L。lｅn）之后插入一個(gè)新元素x。（１）解答:staｔuｓiｎsert(ＳqＬistL,inｔi,ElemTｙpｅx){／／向線性表L中第ｉ個(gè)元素之后插入值為ｘ的新元素（１）ｉf(L。len==m0)erｒｏr(’ｏｖerｆlow’);(2)iｆ（i＜0）||(ｉ>Ｌ.len)error（’ｏｕtｏｆrange＇)；（3)for(j=L．len;j>＝i＋1;—-j)L.vec[ｊ+1］=Ｌ。ｖec[j］；｝(4)L。vｅc［ｉ+１]＝x；（５)L。len=len＋１；｝（2)從類型為list的線性表Ｌ中刪除其值等于x的所有元素。(2)解答：statusｄeｌｅtｅ（L，ｘ）｛／/從線性表L中刪除其值等于x的所有元素i=1;whilｅ(i〈=L.len)ｉｆ(L。vec[i］＝＝x){（Ⅰ)for(j＝i+1;j〈＝L。len;++j)L。vec［j－1］＝Ｌ.vec[j];(Ⅱ)L。len=L.ｌen－１；}ｅlｓei=i＋1；}（3)將兩個(gè)有序表Ａ和B合并成一個(gè)有序表C,其中A，Ｂ，C均為lisｔ類型的變參。(3)解答:sｔatｕsmerge(A,B，C)｛//將兩個(gè)有序表Ａ和B合并成一個(gè)有序表C（1)if（A。ｌen+B．len〉m0）error（'overflｏw'）:(2)i=1;j＝1;k=1;//i和j分別作為掃描數(shù)組Ａ和Ｂ的指針,k指示存入數(shù)組C中元素的下標(biāo)位置(3)ｗhilｅ（i〈=A.len）&＆(j〈＝B。lｅn）ｉf(Ａ。ｖeｃ[i]＜＝B．veｃ[ｊ]）｛C。vec［ｋ]=A.veｃ［ｉ]；i=ｉ＋１；ｋ=ｋ＋1;}ｅlse｛Ｃ。vec[k]＝B。vec[j］;j=ｊ＋1;ｋ＝ｋ＋１;}}（4)whiｌe(i〈=A。len){C。vec[k]＝A。vｅc[i］;i＝i＋1;ｋ＝ｋ+1;}(５）whｉlｅ(ｊ〈＝Ｂ.lｅn){C。vec[k]=Ｂ.vec[j］;ｊ＝j(luò)+1;ｋ=K＋1;}}22.編寫(xiě)下列算法，假定單鏈表的表頭指針用HL表示,類型為linkliｓｔ.(1)將一個(gè)單鏈表中的所有結(jié)點(diǎn)按相反次序鏈接。２2。解答：（１）stａｔusｃontrary（HL）{//使HL單鏈表中的所有結(jié)點(diǎn)按相反次序鏈接p=ＨL；//p指向未被逆序的第一個(gè)結(jié)點(diǎn),初始指向原表頭結(jié)點(diǎn)HL=ｎｉl；//HＬ指向逆序后的表頭結(jié)點(diǎn)，初始值為空while（ｐ!＝ｎil）{（1）ｑ=ｐ；／／q指向?qū)⒈荒嫘蜴溄拥慕Y(jié)點(diǎn)(2)p=p^.nｅxt;(3）ｑ＾．ｎext＝HL；（4）HL＝ｑ;｝｝(２）刪除單鏈表中第ｉ個(gè)(i≥1)結(jié)點(diǎn).（2）解答:sｔａt(yī)usdeletｅ（HＬ，i){（1)if(i〈=0）ｏr(HL=nil)errｏr（'noth&＆le'）;（2）iｆ(i=1){HL=ＨL－〉ｎeｘt；ｒetｕrｎ；}(３)ｊ=1；ｐ＝HL;//p指針?biāo)赶虻慕Y(jié)點(diǎn)，是單鏈表中第ｊ個(gè)結(jié)點(diǎn)ｗhｉｌe（ｊ〈ｉ-1)＆&（ｐ＾．nexｔ！=nil）{j=j+１;p＝ｐ—〉next；｝//尋找第ｉ個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)(4)iｆ（p－〉next!＝=ｎｉl）ｐ-＞ｎｅxt=p—〉nｅxt—〉next;elseerror（’ouｔofrａnge＇)；｝(3）刪除單鏈表中由指針p所指向的結(jié)點(diǎn)。(3）解答:sｔatusdelete(HL，P,Ｘ){//刪除單鏈表HＬ中由指針p所指向的結(jié)點(diǎn)if(ｐ-〉next=nil)erｒoｒ(’notdeleｔe'）；X＝ｐ—〉dａt(yī)ａ；q=ｐ-〉ｎexｔ;p—〉data=p—>next-＞dａt(yī)a；p—>ｎｅxt＝p—>nexｔ—〉nｅxｔ;fｒee（q）；｝或者:ｓｔatusｄeｌete(ＨL,Ｐ,X）｛if（ＨＬ＝ｐ){X＝HL—〉data;HL＝HL-〉nｅxｔ；free（ｐ);}ｅｌsｅ｛(１)q＝ＨＬ;(2)ｗｈiｌe（ｑ-〉nｅｘt!=nil）＆&（q—>ｎeｘt!＝p)q＝q—>ｎeｘt;(3）ｉf(q—〉next＝p）｛X＝p—>dａt(yī)a；q—〉next=p—>nexｔ；frｅe(cuò)（p）}elseerror（’*ｐ結(jié)點(diǎn)不存在’）；}}(4)從帶有附加表頭結(jié)點(diǎn)的循環(huán)單鏈表中刪除其值等于x的第一個(gè)結(jié)點(diǎn).(４)解答：staｔusｄｅlete（HL，x）｛(１)q=HL；p=HL-＞neｘt；(2)while（p！＝HL）&&（ｐ—〉data?。絰）｛q=p；p=ｐ—>next；}(3）if（p==ＨL）erｒoｒ（’ｎｏｔfｏｕnd’)；else{ｑ—〉next=p->next;freｅ(p）;}｝（5）在單鏈表中指針ｐ所指結(jié)點(diǎn)之前插入一個(gè)值為ｘ的新結(jié)點(diǎn)。(５)解答：statusｉnserｔ(ＨＬ,p，x）{ｍaｌlｏｃ(q)；ｑ—〉ｄａt(yī)ａ＝ｐ—〉data;q—〉nexｔ=p-〉nｅxｔ;p-＞neｘt＝q;p－〉dａt(yī)ａ=x;}(6)從循環(huán)單鏈表中查找出最小值.(6）解答：ｅlemtｙｐｅmin(ＨL)｛//從循環(huán)單鏈表HL中查找出最小值if（ＨＬ==ｎil）{priｎｔf(’ＨL=ｎｉl＇）;reｔｕrn;}mｉn=HＬ—〉daｔa;p=HL—>next；wｈile（p!＝HL)｛(1）if(ｐ—>daｔａ〈min)min＝p—〉data；(2)p＝ｐ—〉next；}｝(7）根據(jù)一維數(shù)組Ａ(1:n)中順序存儲(chǔ)的具有ｎ個(gè)元素的線性表建立一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表.(7)解答:statuｓcrｅate(ＨL,A,n){（1)maｌｌoｃ（HL）;q=HＬ；//產(chǎn)生附加表頭結(jié)點(diǎn)(２）ｆｏr（i＝1；I〈=ｎ;＋+i){//完成n個(gè)元素的依次鏈接malloc(p);p-〉dａt(yī)a=Ａ（i)；q—〉neｘt＝p；q＝p;}（３)q—〉nｅxt=nil；／/把最后一個(gè)結(jié)點(diǎn)的指針域置空｝２3。請(qǐng)指出下面的過(guò)程執(zhí)行ｐ(5）和ｐ（６)時(shí)分別輸出的結(jié)果。voｉｄP(ｉｎｔｎ)；｛ifn〉0{ｐ（n—2）;pｒiｎtｆ（“%d",n)；}｝2３.解答:這是一個(gè)遞歸過(guò)程，n執(zhí)行一次就減2，當(dāng)n≤0時(shí)該過(guò)程執(zhí)行結(jié)束.因此,當(dāng)n＝5時(shí),其輸出結(jié)果為１、３、5；當(dāng)n＝６時(shí),其輸出結(jié)果為2、4、6。24.假定用一個(gè)循環(huán)單鏈表表示隊(duì)列（稱此為循環(huán)鏈隊(duì)）,該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針,不設(shè)隊(duì)首指針，試編寫(xiě)下列算法:(1)向循環(huán)鏈隊(duì)插入一個(gè)元素為x的結(jié)點(diǎn);（1）解答:ｓtaｔｕｓｉｎsert(Ｒeａｒ,x）｛//假定Rｅar為循環(huán)鏈隊(duì)的隊(duì)尾指針，x為待插入的元素(1）maｌloc(ｐ）;p－〉dａt(yī)ａ=x;//建立值為x的新結(jié)點(diǎn)p^(２）if(Ｒear＝nil){Rear＝p；Ｒｅar—>nｅxt=ｐ；}ｅlse｛p—〉neｘt=Rear—〉ｎexｔ;Rｅaｒ—〉next=p;Rear＝p；｝//若條件成立則建立循環(huán)鏈隊(duì)的第一個(gè)結(jié)點(diǎn),否則在隊(duì)尾插入p^結(jié)點(diǎn)}(2)從循環(huán)鏈隊(duì)中刪除一個(gè)結(jié)點(diǎn)(假定不需要保留被刪除結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)）。(2)解答:sｔatusdｅleｔe(Ｒeａr）{ｉｆ（Reaｒ＝nil)ｅrror（’ｕnderfｌｏｗ’)；if（Ｒear—＞neｘt==Reａｒ)Rear=ｎil;eｌsｅRear—>nexｔ＝Rear-＞nexｔ—＞neｘt；｝//Reａr^。nexｔ所指向的結(jié)點(diǎn)為循環(huán)鏈隊(duì)的隊(duì)首結(jié)點(diǎn)2５.設(shè)A(k)有如下１0個(gè)元素：2，4,６,8，10，12,1４,１6，18，2０。若對(duì)Ａ(k)分別查找x=１,3，1３,21,試跟蹤下面過(guò)程的執(zhí)行,并分析該程序段關(guān)于n的計(jì)算時(shí)間.【程序段】ｉ=1；j=n；do｛ｋ=（ｉ＋j)／2;ifA（k)<=xｉ＝k+1elsej＝k—１}while！（i〉ｊ）;25.解答(1)查找x=1,n＝10┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓┃┃i┃ｊ┃k┃A(ｋ)?X┃┃┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫┃第1次┃1┃1０┃５┃10〉1┃新j=k-１＝4┃┃第２次┃1┃4┃２┃４〉1┃新j＝k-1＝1┃┃第3次┃1┃1┃1┃2〉1┃新j=k－1=0┃┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛當(dāng)(i=1)>（j＝0）時(shí),過(guò)程終止。未找到.(2)查找ｘ=3，n＝10┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓┃┃i┃j┃k┃A(k）?x┃┃┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫┃第1次┃1┃10┃5┃1０>３┃新j＝k-1=4┃┃第2次┃１┃4┃２┃4〉3┃新ｊ=k－1=1┃┃第3次┃1┃1┃1┃2〈３┃新ｉ＝k＋1=2┃┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛當(dāng)(i＝2）>（ｊ＝1)時(shí),過(guò)程終止.未找到。（3）查找x=1３，ｎ=10┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓┃┃i┃j┃ｋ┃A（k)？x┃┃┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫┃第1次┃1┃１０┃５┃10〈13┃新i=k＋1=6┃┃第２次┃6┃１０┃8┃16>13┃新j=k－1=7┃┃第3次┃6┃7┃6┃１２〈13┃新ｉ=k+1=７┃┃第４次┃7┃７┃７┃１4>13┃新j=ｋ-１＝6┃┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛當(dāng)(ｉ＝７）〉(ｊ＝6）時(shí)，過(guò)程終止。未找到。(4)查找ｘ＝21,n＝１0┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓┃┃i┃j┃ｋ┃A(k)?ｘ┃┃┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫┃第1次┃1┃10┃5┃10〈21┃新i=ｋ+1=6┃┃第２次┃6┃1０┃８┃1６〈21┃新ｉ＝k+1＝9┃┃第3次┃9┃１0┃9┃18〈21┃新ｉ＝k+1＝10┃┃第4次┃10┃１0┃10┃２０〈21┃新ｉ=k+1＝11┃┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛當(dāng)(i＝11）〉(ｊ=10)時(shí),過(guò)程終止,未找到.該程序段的時(shí)間復(fù)雜型為O(log2n)。**26.分別寫(xiě)出對(duì)二叉樹(shù)進(jìn)行中根遍歷和先根遍歷的非遞歸算法(不允許使用轉(zhuǎn)向語(yǔ)句)．２６．解答:中根遍歷的非遞歸算法:ｓtatusiｎordｅr(bｔ){top＝０；p=bt;do{(１）wｈile（p!=nil）{ｔｏp＝top+1;ｓ［top]=p;ｐ:=ｐ—>left；//p指向左子樹(shù)}（2)if(top〉0）{p＝s［tｏp］;top＝top-1;ｐrintｆ(p-〉data)；p=p—>riｇht;/／ｐ指向右子樹(shù)}}whｉle!(（ｔoｐ＝0）&＆(ｐ＝nil));｝解答：先根遍歷的非遞歸算法:statusｐreorｄer（bｔ）{top＝0;p＝ｂtdo{(１）while(p!=nｉｌ）｛printf(p—>data）;if（ｐ->riｇht！=ｎil){top＝top+1；s［top］=ｐ—〉riｇht;}／/若右子樹(shù)非空，則把鏈接指針保存起來(lái),待訪問(wèn)過(guò)左子樹(shù)后再訪問(wèn)它p＝ｐ—〉left；//使p指向左子樹(shù)｝(2)if(tｏp〉0)｛//出棧,使p指向右子樹(shù)ｐ=s[top]top=ｔop-1；}}while!((ｔop＝0）＆&(p=nil)）；｝2７。設(shè)有一個(gè)已排序的整數(shù)數(shù)組a[1.。n］,和一個(gè)整數(shù)x,研究下面用類C所表示的折半查找的五個(gè)程序段，指出哪些是正確的．第一個(gè)：ｉ=１;j=n;dｏ｛k=(