計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)部分真題解析講義_第1頁
計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)部分真題解析講義_第2頁
計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)部分真題解析講義_第3頁
計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)部分真題解析講義_第4頁
計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)部分真題解析講義_第5頁
已閱讀5頁,還剩43頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

《《數(shù)據(jù)結(jié)構(gòu)》408及歷年名校真題精考試點(diǎn)考試點(diǎn)(www.kaoshidian.com)名師精品課電話:4006885第一 線性線性表是一種最簡單的數(shù)據(jù)結(jié)構(gòu),在線性表方面,主要考查線性表的定義和基本操作、線性表的實(shí)現(xiàn)。在線性表實(shí)現(xiàn)方面,要掌握的是線性表的存儲結(jié)構(gòu),包括順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu),特別是鏈?zhǔn)酱鎯Y(jié)構(gòu),是考查的重點(diǎn)。另外,還要掌握線性表的基本應(yīng)用。線性表這一章里面的知識點(diǎn)不多,但要做到深刻理解,能夠應(yīng)用相關(guān)知識點(diǎn)解決實(shí)際問題。鏈表上插入、刪除節(jié)點(diǎn)時(shí)的指針操作是選擇題的一個(gè)??键c(diǎn),諸如雙向鏈表等一些相對復(fù)雜的鏈表上的操作也是可以出現(xiàn)在綜合應(yīng)用題當(dāng)中的。※【大綱解讀通過對歷年計(jì)算機(jī)考研中數(shù)據(jù)結(jié)構(gòu)部分考試大綱的分析不難看出,最近幾年計(jì)算機(jī)考研中針對數(shù)據(jù)結(jié)構(gòu)第一部分線性表的考點(diǎn)、試題類型及側(cè)重點(diǎn)幾乎沒有改變。依然保持的是最初的要求:(一)線性表的定義及基本操(二)線性表的實(shí)現(xiàn)1.順序存儲2.鏈?zhǔn)酱妫常€性表的應(yīng)其中,在2009年綜合題第42題中考查了線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的應(yīng)用【考點(diǎn)歸納作為線性結(jié)構(gòu)的開篇章節(jié),線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中,其作用都是不可低估的。在這一章,第一次系統(tǒng)性地引入鏈?zhǔn)酱鎯Φ母拍?,鏈?zhǔn)酱鎯Ω拍顚⑹钦麄€(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的重中之重,無論哪一章都涉及到了這個(gè)概念??傮w來說,線性表一章可供考查的重要考點(diǎn)有以下幾個(gè)方面1.線性表的相關(guān)基本概念,如:前驅(qū)、后繼、表長、空表、首元結(jié)點(diǎn),頭結(jié)點(diǎn),頭指針等概念。12.線性表的結(jié)構(gòu)特點(diǎn),主要是指:除第一及最后一個(gè)元素外,每個(gè)結(jié)點(diǎn)都只有一個(gè)前趨和只有一個(gè)后繼。3.線性表的順序存儲方式及其在具體語言環(huán)境下的兩種不同實(shí)現(xiàn):表空間的靜態(tài)分配和動(dòng)態(tài)分配。靜態(tài)鏈表與順序表的相似及不同之處。4.線性表的鏈?zhǔn)酱鎯Ψ绞郊耙韵聨追N常用鏈表的特點(diǎn)和運(yùn)算:單鏈表、循環(huán)鏈表,雙向鏈表,雙向循環(huán)鏈表。其中,單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見的考查方式。此外,近年來在不少學(xué)校中還多次出現(xiàn)要求用遞歸算法實(shí)現(xiàn)單鏈表輸出(可能是順序也可能是倒序)的問題。在鏈表的小題型中,經(jīng)??嫉揭恍┲T如:判表空的題。在不同的鏈表中,其判表空的方式是不一樣的,請大家注意。5.線性表的順序存儲及鏈?zhǔn)酱鎯η闆r下,其不同的優(yōu)缺點(diǎn)比較,即其各自適用的場合。單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以及索引存儲結(jié)構(gòu)的各自好處。※及典型題精講精例題精【例1】(200942綜合應(yīng)用題)已知一個(gè)帶有頭結(jié)點(diǎn)的單鏈表,結(jié)點(diǎn)結(jié)構(gòu)圖1 單鏈表結(jié)點(diǎn)結(jié)假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下,請?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法,查找鏈表中倒數(shù)第K個(gè)位置上的結(jié)點(diǎn)(k為正整數(shù))。若查找成功,算法輸出該結(jié)點(diǎn)的data值,并返回1;否則,只返回0。要求:(1)描述算法的基本設(shè)計(jì)思想(2)描述算法的詳細(xì)實(shí)現(xiàn)步驟(3)根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟,采用程序設(shè)計(jì)語言描述算法(使用C或C++或JAVA語言實(shí)現(xiàn)),關(guān)鍵之處請給出簡要注釋??键c(diǎn)還原 對單鏈表進(jìn)行查找的思路為:對單鏈表的結(jié)點(diǎn)依次掃描,檢測其數(shù)據(jù)域是否是我們所要查找的值,若是返回該結(jié)點(diǎn)的指針,否則返回null。因?yàn)樵趩捂湵淼逆溣蛑邪撕罄^結(jié)點(diǎn)的存儲地址,所以當(dāng)我們實(shí)現(xiàn)的時(shí)候,只2知道該單鏈表的頭指針,即可依次對每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域進(jìn)行檢測【例2】(201042綜合應(yīng)用題)設(shè)將n(n,1)個(gè)整數(shù)存放到一維數(shù)組R中,試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能有效的算法,將R中保有的序列循環(huán)左移P(0<P<n)個(gè)位置,即將R中的數(shù)據(jù)由(X1,X2,…,Xn)變換為(Xp,Xp+1,,Xn,X1,…,Xp1)。要求:(1)給出算法的基本設(shè)計(jì)思想(2)根據(jù)設(shè)計(jì)思想,采用C或C++或JAVA語言表述算法,關(guān)鍵之處給出注釋(3)說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度【例3 ( 42綜合應(yīng)用題)一個(gè)長度為L(L =1)的升序序列S,處在「L/2」個(gè)位置的數(shù)稱 S的中位數(shù)例如,若序列S1=(11,13,15,17,19),則S1的中位數(shù)是15。兩個(gè)序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如,若S2=(2,4,6,8,20),則S1和S2的中位數(shù)是11?,F(xiàn)有兩個(gè)等長升序序列A和B,試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法,找出兩個(gè)序列A和B的中位數(shù)。要求:(1)給出算法的基本設(shè)計(jì)思想(2)根據(jù)設(shè)計(jì)思想,采 C或C++或JAVA語言描述算法,關(guān)鍵之處給出注釋(3)說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度考點(diǎn)還原 所謂的中位數(shù)是指:將數(shù)據(jù)按大小順序排列起來,形成一個(gè)數(shù)列,居于數(shù)列中間位置的數(shù)叫中位數(shù),且要分奇數(shù)與偶數(shù)兩種情況來分析。1:如果總數(shù)個(gè)數(shù)是奇數(shù),按從小到大的順序,取中間的那個(gè)2:如果總數(shù)個(gè)數(shù)是偶數(shù),按從小到大的順序,取中間那兩個(gè)數(shù)的平均數(shù)例:數(shù)列:1、9、11中位數(shù):9,而數(shù)列:1、9、11、39,則是(9+11)/2=10思考過程1:由于中位數(shù)是位于中間位置,所以容易想到的思路就是,設(shè)計(jì)一種以中位數(shù)隔開,維護(hù)左右兩邊的數(shù)列,左邊都是小于中位數(shù)的,右邊都是大于中位數(shù)的數(shù)據(jù)結(jié)構(gòu)思考過程如何建立左右兩邊的數(shù)據(jù)結(jié)構(gòu),才能易于與中位數(shù)比較,又易于插入刪除顯然,中位數(shù)的計(jì)算方式是,若數(shù)列為偶數(shù),是左邊的最大值和右邊的最小值除2;若不是,也要維護(hù)這左右的最大值和右邊的最大值,原因是,經(jīng)常插入或刪除,數(shù)據(jù)的總數(shù),時(shí)常在奇數(shù)和偶數(shù)之間變換。3所以,對于左邊的數(shù)列,我們試圖是設(shè)計(jì)出容易找到最小值的數(shù)據(jù)結(jié)構(gòu),同理,右邊也一樣,所以自然而然,就想到堆。即大頂堆和小頂堆。得出簡單結(jié)論:可以利用大堆和小堆來解決這個(gè)問題,大致過程如下:1:用一個(gè)大頂堆存儲數(shù)列中不大于中位數(shù)的元素2:用一個(gè)小頂堆存儲數(shù)列中不小于中位數(shù)的元習(xí)題精—、選擇1.某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素,則采用 存儲方式最節(jié)省運(yùn)算時(shí)間。【南開大學(xué)2000一、3(2分)】A.單鏈 B.僅有頭指針的單循環(huán)鏈C.雙鏈表 D.僅有尾指針的單循環(huán)鏈表2.下面的敘述不正確的是 ?!灸暇├砉ご髮W(xué)1996一、10(2分)】A.表性在鏈?zhǔn)酱鎯r(shí),找第i元素的時(shí)間同i值成正B.性表在鏈?zhǔn)酱鎯r(shí),找第i元素的時(shí)間同i值無關(guān)C.性表在順序存儲時(shí),找第i元素的時(shí)間同i值成正D.性表在順序存儲時(shí),找第i元素的時(shí)間同i值無關(guān)3.在雙向鏈表存儲結(jié)構(gòu)中,刪除p所指的結(jié)點(diǎn)時(shí)需修改指針 ?!疚靼搽娮涌萍即髮W(xué)1998一、1(2分)】A.(p^.Llink)^.Rlink:=p^.Rlink(p^.Rlink)^.Llink:=p^.Llink;B.p^.Llink:=(p^.Llink)^.Llink(p^.Llink)^.Rlink:=p;C.(p^.Rlink)^.Llink:= p^.Rlink:=(p^.Rlink)^.D.p^.Rlink:=(p^.Llink)^.Llink p^.Llink:=(p^.Rlink)^.Rlink;二、判斷題1.線性表采用鏈表存儲時(shí),結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。 【北京郵電大學(xué)1998一、2(2分)2.順序存儲方式插入和刪除時(shí)效率太低,因此它不如鏈?zhǔn)酱鎯Ψ绞胶?。?)【北京郵電大學(xué)2002一、2(1分)】3.為了很方便的插入和刪除數(shù)據(jù),可以使用雙向鏈表存放數(shù)據(jù)。( 學(xué)院1995一、1(1分)】【上海海運(yùn)學(xué)院1997一、2(1分)】三、填空1.對于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表,在已知的結(jié) p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間4雜度為 ,在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 。【哈爾濱工業(yè)大學(xué)2001一、1(2分)】2.下面程序段是逆轉(zhuǎn)單向循環(huán)鏈表的方法,p0是原鏈表頭指針,逆轉(zhuǎn)后鏈表頭指針仍為p0。(可以根據(jù)需要增加標(biāo)識符)p:=p0;q0:=NULL; ( ( ( ( ( p^.next:=q0;p0^.next:=p;p0:=p;【中國人民大學(xué)2000二、1(4分)3.對單鏈表中元素按插入方法排序的C語言描述算法如下,其中L為鏈表頭結(jié)點(diǎn)指針。請?zhí)畛渌惴ㄖ袠?biāo)出的空白處,完成其功能。typedefstruct{intdata;structnode}linknode,link;voidInsertsort(linkL){linkp,q,r,p=L >next; (1) (2) {r=L;q= > (3) &&q >data<=p >data){r=q;q=q >next;}u=p >next; (4) (5) ;p=u;}}【北京科技大學(xué)2001二 四、應(yīng)用題1.試述頭結(jié)點(diǎn),首元結(jié)點(diǎn),頭指針這三個(gè)概念的區(qū)別.【武漢交通科技大學(xué)1996二、2(3分)】【西安電子科技大學(xué)2001計(jì)應(yīng)用 二、1(5分)】2.已知有如下定義的靜態(tài)鏈表:TYPEcomponent=RECORDdata:eetpnext:0..maxsizeEND stalist:ARRAY[0..zeOFpnnt5以及三個(gè)指針:av指向頭結(jié)點(diǎn),p指向當(dāng)前結(jié)點(diǎn),pre指向前驅(qū)結(jié)點(diǎn),現(xiàn)要求修改靜態(tài)鏈表中next域中的內(nèi)容,使得該靜態(tài)鏈表有雙向鏈表的功能,從當(dāng)前結(jié)點(diǎn)p既能往后查找,也能往前查找:(1)定義next域中的內(nèi)容。(用老的next域中的值表示)(2)如何得到當(dāng)前結(jié)點(diǎn)p的前驅(qū)(pre)的前驅(qū),給出計(jì)算式(3)如何得到p的后繼,給出計(jì)算式;【中科院計(jì)算所2000四(10分)3.已知L是一個(gè)數(shù)據(jù)類型linkedlist的單循環(huán)鏈表,pa和pb是指向L中結(jié)點(diǎn)的指針。簡述下列程序段的功能?!旧綎|科技大學(xué)2001一、2(5分)】TYPElinkedlist=↑enode=data:datatype;next:linkedlist ppa,pb:linkedlist); subp(s,q:linkedlist)p:=WILEpnext<>qDO p:=p↑next;p↑next:=ssubp(pa,pb);subp(pb,pa);五、算法設(shè)計(jì)1.假設(shè)有兩個(gè)按元素值遞增次序排列的線性表,均以單鏈表形式存儲。請編寫算法將這兩個(gè)單鏈表歸并為一個(gè)按元素值遞減次序排列的單鏈表,并要求利用原來兩個(gè)單鏈表的結(jié)點(diǎn)存放歸并后的單鏈表。【北京大學(xué)1998三、1(5分)】類似本題的另外敘述有(1)設(shè)有兩個(gè)無頭結(jié)點(diǎn)的單鏈表,頭指針分別為ha,hb,鏈中有數(shù)據(jù)域data,鏈域next,兩鏈表的數(shù)據(jù)都按遞增序存放,現(xiàn)要求將hb表歸到ha表中,且歸并后ha仍遞增序,歸并中ha表中已有的數(shù)據(jù)若hb中也有,則hb中的數(shù)據(jù)不歸并到ha中,hb的鏈表在算法中不允許破壞。【南京理工大學(xué)1997四、3(15分)】 ergeha,hb)6(2)已知頭指針分別為la和lb的帶頭結(jié)點(diǎn)的單鏈表中,結(jié)點(diǎn)按元素值非遞減有序排列。寫出將la和lb兩鏈表歸并成一個(gè)結(jié)點(diǎn)按元素值非遞減有序排列的單鏈表(其頭指針為lc),并計(jì)算算法的時(shí)間復(fù)雜度?!狙嗌酱髮W(xué)1998五(20分)】2.設(shè)Listhead為一單鏈表的頭指針,單鏈表的每個(gè)結(jié)點(diǎn)由一個(gè)整數(shù)域DATA和指針域NEXT組成,整數(shù)在單鏈表中是無序的。編一PASCAL過程,將Listhead鏈中結(jié)點(diǎn)分成一個(gè)奇數(shù)鏈和一個(gè)偶數(shù)鏈,分別由P,Q指向,每個(gè)鏈中的數(shù)據(jù)按由小到大排列。程序中不得使用NEW過程申請空間?!旧綎|大學(xué)1993六(15分)】類似本題的另外敘述有(1)設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表B、C,其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn),而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)(鏈表A的元素類型為整型,要求B、C表利用A表的結(jié)點(diǎn))?!颈本├砉ご髮W(xué)2000四、2(4分)】(2)設(shè)L為一單鏈表的頭指針,單鏈表的每個(gè)結(jié)點(diǎn)由一個(gè)整數(shù)域data和指針域NEXT組成,整數(shù)在單鏈表中是無序的。設(shè)計(jì)算法,將鏈表中結(jié)點(diǎn)分成一個(gè)奇數(shù)鏈和一個(gè)偶數(shù)鏈,分別由P,Q指向,每個(gè)鏈中的數(shù)據(jù)按由小到大排列,算法中不得申請新的結(jié)點(diǎn)空間?!厩鄭u海洋大學(xué)1999三(12分)】(3)將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表A和B,使得A表中含有原表中序號為奇數(shù)的元素,而B表中含有原表中序號為偶數(shù)的元素,且保持其相對順序不變。1)寫出其類型定義2)寫出算法?!旧綎|大學(xué)1998 (9分)】【山東工業(yè)大學(xué)2000九(9分)3.設(shè)有一頭指針為L的帶有表頭結(jié)點(diǎn)的非循環(huán)雙向鏈表,其每個(gè)結(jié)點(diǎn)中除有(前驅(qū)指針),data(數(shù)據(jù))和(后繼指針)域外,還有一個(gè)訪問頻度域freq。在鏈表被起用前,其值均初始化為零。每當(dāng)在鏈表中進(jìn)行一次Locate(L,x)運(yùn)算時(shí),令元素值為x的結(jié)點(diǎn)中freq域的值增1,并使此鏈表中結(jié)點(diǎn)保持按訪問頻度非增(遞減)的順序排列,同時(shí)最近訪問的結(jié)點(diǎn)排在頻度相同的結(jié)點(diǎn)的最后,以便使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。試編寫符合上述要求的Locate(L,x)運(yùn)算的算法,該運(yùn)算為函數(shù)過程,返回找到結(jié)點(diǎn)的地址,類型為指針型?!厩迦A大學(xué)1997二(10分)】7第二 棧、隊(duì)列和數(shù)棧和隊(duì)列是兩種特殊的線性表,在這方面,要求我們掌握棧和隊(duì)列的基本概念,以及他們之間的區(qū)別。對于棧和隊(duì)列的存儲結(jié)構(gòu)(包括順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu))要有較深的理解,對于棧和隊(duì)列的應(yīng)用,例如,排隊(duì)問題、子程序調(diào)用問題、表達(dá)式問題等,要搞清楚。—維數(shù)組屬于線性表范疇,但多維數(shù)組不屬于線性表。在這方面,主要掌握數(shù)組的存儲結(jié)構(gòu),例如按行優(yōu)先、按列優(yōu)先等,某個(gè)元素存在的地址是什么。對于特殊矩陣(二維數(shù)組)的壓縮存儲原理也要搞清楚。棧、隊(duì)列和數(shù)組可以考查的知識點(diǎn)相比鏈表來說要多一些。最基本的,是棧與隊(duì)列FILO和FIFO的特點(diǎn)。比如針對棧FILO的特點(diǎn),進(jìn)棧出棧序列的問題常出現(xiàn)在選擇題中。其次,是棧和隊(duì)列的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu),這里一個(gè)常考點(diǎn)是不同存儲結(jié)構(gòu)下棧頂指針、隊(duì)首指針以及隊(duì)尾指針的操作,特別是循環(huán)隊(duì)列判滿和判空的2種判斷方法。再次,是特殊矩陣的壓縮存儲,這個(gè)考點(diǎn)復(fù)習(xí)的重點(diǎn)可以放在二維矩陣與一維數(shù)組相互轉(zhuǎn)換時(shí),下標(biāo)的計(jì)算方法,比如與對角線平行的若干行上數(shù)據(jù)非零的矩陣存放在一維數(shù)組后,各個(gè)數(shù)據(jù)點(diǎn)相應(yīng)的下標(biāo)的計(jì)算。這一章可能的大題點(diǎn),在于利用堆棧或隊(duì)列的特性,將它們作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu),支持實(shí)際問題求解算法的設(shè)計(jì),例如用棧解決遞歸問題,用隊(duì)列解決圖的遍歷問題等等。※【大綱解讀通過對歷年計(jì)算機(jī)考研中數(shù)據(jù)結(jié)構(gòu)部分考試大綱的分析不難看出,最近幾年計(jì)算機(jī)考研中針對數(shù)據(jù)結(jié)構(gòu)第二部分棧、隊(duì)列和數(shù)組的考點(diǎn)、試題類型及側(cè)重點(diǎn)幾乎沒有改變。依然保持的是最初的要求:(一)棧和隊(duì)列的基本概(二)棧和隊(duì)列的順序存儲結(jié)(三)棧和隊(duì)列的鏈?zhǔn)酱鎯Y(jié)(四)棧和隊(duì)列的應(yīng)(五)特殊矩陣的壓縮存8【考點(diǎn)歸納棧與隊(duì)列,是很多學(xué)習(xí)DS的同學(xué)遇到第一只攔路虎,很多人從這一章開始坐暈車,一直暈到現(xiàn)在。所以,理解棧與隊(duì)列,是走向DS高手的一條必由之路。學(xué)習(xí)此章前,你可以問一下自己是不是已經(jīng)知道了以下幾點(diǎn):1.棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念,包括:順序棧,鏈棧,共享?xiàng)?,循環(huán)隊(duì)列,鏈隊(duì)等。棧與隊(duì)列存取數(shù)據(jù)(請注意包括:存和取兩部分)的特點(diǎn)。2.遞歸算法。棧與遞歸的關(guān)系,以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法:n!階乘問題,fib數(shù)列問題,Hanoi問題,背包問題,二叉樹的遞歸和非遞歸遍歷問題,圖的深度遍歷與棧的關(guān)系等。其中,涉及到樹與圖的問題,多半會在樹與圖的相關(guān)章節(jié)中進(jìn)行考查。3.棧的應(yīng)用:數(shù)值表達(dá)式的求解,括號的配對等的原理,只作原理性了解,具體要求考查此為題目的算法設(shè)計(jì)題不多。4.循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿條件,循環(huán)隊(duì)列中入隊(duì)與出隊(duì)算法。如果你已經(jīng)對上面的幾點(diǎn)了如指掌,棧與隊(duì)列一章可以不看書了。注意,我說的是可以不看書,并不是可以不作題哦?!暗湫皖}精講精例題精【例1】(20091)為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題,通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū),而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是 A. B.隊(duì) C. D.【例2】(20092)設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空,元素abcdefg依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q,且7個(gè)元素出隊(duì)的順序是bdcfeag,則棧S的容量至少是 A. B. C. D.【例3】 (2010 1)若元素a,b,c,d,e,f依次進(jìn)棧,允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作,則不可能得到的出棧序列是 A. B. C. D.【例4 ( 2)某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作,但僅允許在一端進(jìn)行出9操作,則不可能得到的順序 A. B. C. D.【例5】(20112)元素a,b,c,d,e依次進(jìn)入初始非空的棧中。若元素進(jìn)棧后可以停留,可以出棧,直到所有元素都出棧,則在所有的可能的出棧序列中,以元素d開頭的序列的個(gè)數(shù)為 A. B. C. D.【例6】(20113)一直循環(huán)隊(duì)列存儲在一維數(shù)組A[0…n1]中,且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭和隊(duì)尾。若初始時(shí)隊(duì)列為空,且要求第一個(gè)進(jìn)入隊(duì)列的元素在A[0]處,則初始時(shí)front和rear的值分別為 A.0, B.0.n C.n1, D.n1,n【例7】(20123)已知操作符包括‘+’,‘’,‘’,‘/’,‘(’和‘)’,將中綴表達(dá)式a+ba×((c+d)/ef)+g轉(zhuǎn)化為等價(jià)的后綴表達(dá)式ab+acd+e/f×g+時(shí),用棧來存放暫時(shí)還不能確定的運(yùn)算次序的操作符,若棧初始時(shí)為空,則轉(zhuǎn)換過程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是 A. B. C. D.習(xí)題精—、選擇1.一個(gè)棧的輸入序列為 12345,則下列序列中不可能是棧的輸出序列的是( )。A.2341 B.5413 C.2314 D.1543【南開大學(xué)2000一、1】【山東大學(xué)2001二、4(1分)】【北京理工大學(xué)2000一、2(分)2.設(shè)計(jì)一個(gè)判別表達(dá)式中左,右括號是否配對出現(xiàn)的算法,采用 )數(shù)據(jù)結(jié)最佳A.線性表的順序存儲結(jié) B.隊(duì)C.線性表的鏈?zhǔn)酱鎯Y(jié) D.【西安電子科技大學(xué)1996一、6(2分)3.用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的 )位置?!厩迦A大學(xué)1998一、1(分)

A.鏈 B.鏈 C.鏈二、判斷1.消除遞歸不一定需要使用棧,此說法 )?!局锌圃河?jì)算所1998二、2(2分)【中國科技大學(xué)1998二、2(2分)2.棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。 )【中科院軟件所1999六、(5)(分)3.隊(duì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。 )【上海交大學(xué)1998一、2】三、填空題1.設(shè)有一個(gè)空棧,棧頂指針為0H十六進(jìn)制),現(xiàn)有輸入序列為1,2,3,4,5,經(jīng)過HHPOP,HPOP,HPUSH之后,輸出序列是 ,而棧頂指針值 H。設(shè)棧為順序棧,每個(gè)元素占4個(gè)字節(jié)?!疚靼搽娮涌萍即髮W(xué)1998二、1(4分)】2.在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否(1);在作退棧運(yùn)算時(shí)應(yīng)先判別棧是(2);當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說明該棧的最大容量為(3)。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的空間時(shí),應(yīng)將兩棧的(4)分別設(shè)在內(nèi)存空間的兩端,這樣只有當(dāng)(5)時(shí)才產(chǎn)生溢出。【山東工業(yè)大學(xué)1994一、1(5分)】3.算術(shù)表達(dá)式求值的流程,其中OPTR為算術(shù)符棧,OPND為操作數(shù)棧,precede(oper1,oper2)是比較運(yùn)算符優(yōu)先級別的函數(shù),operate(opnd1,oper,opnd2)為兩操作數(shù)的運(yùn)算結(jié)果函數(shù)。(#表示運(yùn)算起始和終止符號)【西北工業(yè)大學(xué)1999六、2(7分)】 expreduced:operandtype;INITSTACK(OPTR);HOPTR"#");WL NOT((w='?!粒危模ǎ牵牛裕裕希校ǎ希校裕遥剑В#В模希桑疲危希裕鳎椋睿铮穑裕龋牛危龋希校危?,w);ELSECASEprecede(GETTOP(OPTR),w)'<':[( ;read(w);'=':[( ;read(w);]'>':[theta:=POP(OPTR);b:=POP(OPND);a:=POP(OPND)( ;RETURN(GETTOP(OPND));四、應(yīng)用1.假設(shè)以S和X分別表示入棧和出棧操作,則對初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示(如SXSX)。(1)試指出判別給定序列是否合法的一般規(guī)則(2)兩個(gè)不同合法序列(對同一輸入序列)能否得到相同的輸出元素序列?如能得到,請舉列說明。【東南大學(xué)1992二(10分)】2.試證明:若借助棧由輸入序列1,2,…,n得到輸出序列為P1,P2,…,Pn(它是輸入序列的一個(gè)排列),則在輸出序列中不可能出現(xiàn)這樣的情形:存在著i<j<k,使Pj<Pk<Pi?!旧虾=煌ù髮W(xué)1998二(15分)】3.對下面過程寫出調(diào)用P(3)的運(yùn)行結(jié)果。PROCEDUREp(w:integer);IFw>0p( 1)writeln(w);{輸出Wp(w END;【西北大學(xué)2001三、74.一個(gè)循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)描述如下:TYPEsequeuetp=RECORDelem:ARRAY[1..MAXSIZEOFletpfront,rear:0..MAXSE給出循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷條件,并且分析一下該條件對隊(duì)列實(shí)際存儲空間大小的影響,如果為了不損失存儲空間,你如何改進(jìn)循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷條件【西北工業(yè)大學(xué)1999 (8分)5.順序隊(duì)列一般應(yīng)該組織成為環(huán)狀隊(duì)列的形式,而且一般隊(duì)列頭或尾其中之一應(yīng)該特殊處理。例如,隊(duì)列為listarray[0..n1],隊(duì)列頭指針 front,隊(duì)列尾指針為則listarray[rear]表示下一個(gè)可以插入隊(duì)列的位置。請解釋其原因?!颈本┐髮W(xué)—、3(20/3分)五、算法設(shè)計(jì)1.設(shè)有兩個(gè)棧S1,S2都采用順序棧方式,并且共享一個(gè)存儲區(qū)[O..maxsize1],為了盡量利用空間,減少溢出的可能,可采用棧頂相向,迎面增長的存儲方式。試設(shè)計(jì)S1,S2有關(guān)入棧和出棧的操作算法?!竟枮I工業(yè)大學(xué)2001七(12分)】【北京科技大學(xué)2001九、1(10分)】2.請利用兩個(gè)棧S1和S2來模擬一個(gè)隊(duì)列。已知棧的三個(gè)運(yùn)算定義如下:(ST,x):元素x入ST棧;POP(ST,x):ST棧頂元素出棧,賦給變量x;ptyST):判ST棧是否為空。那么如何利用棧的運(yùn)算來實(shí)現(xiàn)該隊(duì)列的三個(gè)運(yùn)算:enqueue:插入一個(gè)元素入隊(duì)列;dequeue:刪除一個(gè)元素出隊(duì)列;queueepty:判隊(duì)列為空。(請寫明算法的思想及必要的注釋)【西安電子科技大學(xué)2001軟件 五(10分)】【上海交通大學(xué)1999二(12分)】【河海大學(xué)1998三(12分)】類似本題的另外敘述有(1)有兩個(gè)長度相同的棧S1,S2,已知以下入棧、出棧、判棧滿和判棧空操作: push(Stack:Stacktype;x:Datatype);FUNCTIONPop(Stack:Stacktype):Datatype;FUNCTIONFull(Stack:Stacktype):Boolean;FUNCTIONEpty(Stack:Stacktype)Boolean;現(xiàn)用此二棧構(gòu)成一個(gè)隊(duì)列,試寫出下面入隊(duì)列、出隊(duì)列操作算法: EnQueue(x:Datatype);FUNCTIONDeQueue:【北京郵電大學(xué)2000六(10分)3.已知Q是一個(gè)非空隊(duì)列,S是一個(gè)空棧。僅用隊(duì)列和棧的ADT函數(shù)和少量工作變量,使用Pascal或C語言編寫一個(gè)算法,將隊(duì)列Q中的所有元素逆置。棧的ADT函數(shù)有:keEptys:stack);//置空push(s:stack;value:datatype);//新元素value進(jìn)棧pop(s:stack):datatype; //出棧,返回棧頂值isEptys:stack):Boolean;//判??辗耜?duì)列的ADT函數(shù)有enqueue(q:queue:value:datatype);//元素value進(jìn)隊(duì)deQueue(q:queue):datatype;//出隊(duì)列,返回隊(duì)頭值pyq:queue):boolean;//判隊(duì)列空否【清華大學(xué)2000六(12分)第三 樹與二叉二叉樹和樹是兩種不同的概念,這一點(diǎn)是必須要搞清楚的。在這個(gè)部分,我們要掌握樹的定義、二叉樹的定義及主要特征(特殊的二叉樹、二叉樹的性質(zhì))。在二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)方面,特別是鏈?zhǔn)酱鎯Y(jié)構(gòu),因?yàn)楹芏鄳?yīng)用都是建立在鏈?zhǔn)酱鎯A(chǔ)上,例如,二叉樹的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應(yīng)用。在特殊的二叉樹中,完全二叉樹的概念是必須要搞清楚的,其次,線索二叉樹的基本概念和構(gòu)造、二叉排序樹、平衡二叉樹的基本概念和應(yīng)用,特別是二叉排序樹的基本性質(zhì)和特點(diǎn)要能很好地理解。多棵獨(dú)立的樹就組成了森林,樹的存儲結(jié)構(gòu)和遍歷、森林的遍歷、樹和二叉樹的轉(zhuǎn)換、森林和二叉樹的轉(zhuǎn)換等知識,也要有了了解。最后就是樹的應(yīng)用,通常會作為綜合應(yīng)用類試題出現(xiàn),包括等價(jià)類問題、哈夫(uffan樹和哈夫曼編碼等※【大綱解讀通過對歷年計(jì)算機(jī)考研中數(shù)據(jù)結(jié)構(gòu)部分考試大綱的分析不難看出,最近幾年計(jì)算機(jī)考研中針對數(shù)據(jù)結(jié)構(gòu)第一部分線性表的考點(diǎn)、試題類型及側(cè)重點(diǎn)幾乎沒有改變。依然保持的是最初的要求:(一)樹的概(二)二叉1.二叉樹的定義及其主要特2.二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)3.二叉樹的遍歷4.線索二叉樹的基本概念和構(gòu)造5.二叉排序樹6.平衡二叉(三)樹、森1.書的存儲結(jié)2.森林與二叉樹的轉(zhuǎn)換3.樹和森林的遍歷1.等價(jià)類問2.哈夫曼(uffan樹和哈夫曼編【考點(diǎn)歸納從對線性結(jié)構(gòu)的研究過度到對樹形結(jié)構(gòu)的研究,是數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的一次躍變,此次躍變完成的好壞,將直接關(guān)系到你到實(shí)際的考試中是否可以拿到高分,而這所有的一切,將最終影響你的專業(yè)課總分。所以,樹這一章的重要性,已經(jīng)不說自明了??傮w來說,樹一章的知識點(diǎn)包括二叉樹的概念、性質(zhì)和存儲結(jié)構(gòu),二叉樹遍歷的三種算法(遞歸與非遞歸),在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹的其它算法,線索二叉樹的概念和線索化算法以及線索化后的查找算法,最優(yōu)二叉樹的概念、構(gòu)成和應(yīng)用,樹的概念和存儲形式,樹與森林的遍歷算法及其與二叉樹遍歷算法的聯(lián)系,樹與森林和二叉樹的轉(zhuǎn)換?!暗湫皖}精講精例題精【例1】(20093)給定二叉樹如圖所示。設(shè)N代表二叉樹的根,L代表根結(jié)點(diǎn)的左子樹,R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3,1.7,5,6,2,4,則其遍歷方式是?A. B. C. D.【例2】( 4)下列二叉排序樹中,滿足平衡二叉樹定義的 【例3】(2009 5)已知一棵完全二叉樹的第6層(設(shè)根為第l層)有8個(gè)葉結(jié)點(diǎn),則完全結(jié)點(diǎn)個(gè)數(shù)最多是 A. B. C. D.【例4】(20096)將森林轉(zhuǎn)換為對應(yīng)的二叉樹,若在二叉樹中,結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn),則在原來的森林中,u和v可能具有的關(guān)系是 父子關(guān)兄弟關(guān)的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)A.只有 B.Ⅰ和 C.Ⅰ和 D.Ⅰ、Ⅱ和【例5】(2010 3)下列線索二叉樹中(用虛線表示線索),符合后序線索樹定義的 【例6】(4)在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹,在新平衡二叉樹中,關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是A.13, B.24, C.24, D.24,【例7】(20105)在一棵度為4的樹T中,若有20個(gè)度為4的結(jié)點(diǎn),10個(gè)度為3的結(jié)點(diǎn),1個(gè)度為2的結(jié)點(diǎn),10個(gè)度為1的結(jié)點(diǎn),則樹T的葉結(jié)點(diǎn)個(gè)數(shù)是 A. B. C. D.【例8】(20106)對n(n大于等于2)個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹,關(guān)于該樹的敘述中,錯(cuò)誤的是 A.該樹一定是一棵完全二叉樹B.樹種一定沒有度為1的結(jié)C.樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)D.樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的權(quán)【例9】( 4)若一棵全完二叉樹有768個(gè)結(jié)點(diǎn),則該二叉樹葉結(jié)點(diǎn)的個(gè)數(shù)A. B. C. D.【例10】(20115)若一棵二叉樹的前序遍歷和后序遍歷分別為1,2,3,4和4,3,2,1,則該二叉樹的中序遍歷不會是 A.1,2,3, B.2,3,4, C.3,2,4, D.4,3,2,應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)個(gè)數(shù)最多是 A. B. C. D.【例12】(20117)對于下列關(guān)鍵序列,不能構(gòu)成某二叉樹排序中的一條查找路徑的序列是 A.95,22,91,24,94, B.92,20,91,34,88,C.21,89,77,29,36, D.12,25,71,68,33,習(xí)題精—、選擇1.在一棵三元樹中度為3的結(jié)點(diǎn)數(shù)為2個(gè),度為2的結(jié)點(diǎn)數(shù)為1個(gè),度為1的結(jié)點(diǎn)為2個(gè),則度為0的結(jié)點(diǎn)數(shù)為( )個(gè)。【哈爾濱工業(yè)大學(xué)2001二、2(2分)】A.4 B.5 C.6 D.72.若度為m的哈夫曼樹中,其葉結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù)為( )。【中科院計(jì)算所1999一、2(2分)】A. B.?n/m C.?(n 1)/(m1)」 D.?n/(m1)」 E.?(n+1)/(m+1)」13.下述二叉樹中,哪一種滿足性質(zhì):從任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序( )。A.二叉排序 B.哈夫曼C.AVL D.【中國科技大學(xué)1998二、8(2分)】【中科院計(jì)算所1998二、8(2分)n4.最優(yōu)二叉樹(哈夫曼樹)、最優(yōu)查找樹均為平均查找路徑長度∑whi最小的樹,i=中對最優(yōu)二叉樹,n表示(1),對最優(yōu)查找樹,n表示(2),構(gòu)造這兩種樹均(3)?!局锌圃河?jì)算所1999一、3(6分)】A.結(jié)點(diǎn) B.葉結(jié)點(diǎn)C.非葉結(jié)點(diǎn)數(shù) D.度為2的結(jié)點(diǎn)數(shù)E.需要一張n個(gè)關(guān)鍵字的有序表F.需要對n個(gè)關(guān)鍵字進(jìn)行動(dòng)態(tài)插G.需要n個(gè)關(guān)鍵字的查找概率表H.不需要任何前提5.下面幾個(gè)符號串編碼集合中,不是前綴編碼的是 )A.{0,10,110, B.{11,10,001,101,C.{00,010,0110, D.{b,c,aa,ac,aba,abb,【西安電子科技大學(xué)2001應(yīng)用 一、6(2分)】二、判斷題1.二叉樹以后序遍歷序列與前序遍歷序列反映的同樣的信息(他們反映的信息不獨(dú)立)?!救A南理工大學(xué)2002一、7(1分)】2.完全二叉樹中,若一個(gè)結(jié)點(diǎn)沒有左孩子,則它必是樹葉?!緰|南大學(xué)2001一、 (1分)】【中科院軟件所1997一、2(1分)】【山東大學(xué)2001一、4(1分)3.在任意一棵非空二叉排序樹,刪除某結(jié)點(diǎn)后又將其插入,則所得二叉排序樹與刪除前原二叉排序樹相同?!局锌圃很浖保梗梗芬弧ⅲ罚ǎ狈郑咳?、填空1.深度為H的完全二叉樹至少有(1)個(gè)結(jié)點(diǎn);至多有(2)個(gè)結(jié)點(diǎn);H和結(jié)點(diǎn)總數(shù)N之間的關(guān)系是(3)。【中科院計(jì)算所1998一、3(3分)1999二、4(3分)】【中國科技大學(xué)1998一、3(4分)】2.設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為0,則高度為k的二叉樹的最大結(jié)點(diǎn)數(shù),最小結(jié)點(diǎn)數(shù) ?!颈本┐髮W(xué)1997一、1(4分)3.在一棵存儲結(jié)構(gòu)為三叉鏈表的二叉樹中,若有一個(gè)結(jié)點(diǎn)是它的雙親的左子女,且它的雙親有右子女,則這個(gè)結(jié)點(diǎn)在后序遍歷中的后繼結(jié)點(diǎn)是 ?!局袊嗣翊髮W(xué)2001一、4(2分)】4.若以{4,5,6,7,8}作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹,則其帶權(quán)路徑長度【西安電子科技大學(xué)2001軟件一、3(2分)】【廈門大學(xué)2002六、2(4分)】5.設(shè)一棵二叉樹的結(jié)點(diǎn)定義為structElemTypedata;BinTreeNode 現(xiàn)采用輸入廣義表表示建立二叉樹。具體規(guī)定如下(1)樹的根結(jié)點(diǎn)作為由子樹構(gòu)成的表的表名放在表的最前面;(2)每個(gè)結(jié)點(diǎn)的左子樹和右子樹用逗號隔開。若僅有右子樹沒有左子樹,逗號不能省略。(3)在整個(gè)廣義表輸入的結(jié)尾加上一個(gè)特殊的符號(例如“?!保┍硎据斎虢Y(jié)束。例如,對于如右圖所示的二叉樹,其廣義表表示為A(B(D,E(G)),C(,F))。此算法的基本思路是:依次從保存廣義表的字符串ls中輸入每個(gè)字符。若遇到的是字母(假設(shè)以字母作為結(jié)點(diǎn)的值),則表示是結(jié)點(diǎn)的值,應(yīng)為它建立一個(gè)新的結(jié)點(diǎn),并把該結(jié)點(diǎn)作為左子女(當(dāng)k=1)或右子女(當(dāng)k=2)鏈接到其雙親結(jié)點(diǎn)上。若遇到的是左括號“(”,則表明子表的開始,將k置為1;若遇到的是右括號“)”,則表明子表結(jié)束。若遇到的是逗號“,”,則表示以左子女為根的子樹處理完畢,接著處理以右子女為根的子樹,將K置為2。在算法中使用了一個(gè)棧s,在進(jìn)入子表之前,將根結(jié)點(diǎn)指針進(jìn)棧,以便括號內(nèi)的子女鏈接之用。在子表處理結(jié)束時(shí)退棧。相關(guān)的棧操作如下:MaeEptys)置空棧 Push(s,p) 元素p入棧Pop(s)退 Top( 存取棧頂元素的函下面給出了建立二叉樹的算法,其中有5個(gè)語句缺失,請閱讀此算法并把缺失的語句補(bǔ)上。(每空3分)voidCreatBinTree( &BT,charls)Stack<BinTreeNode>s; MaeEptys);BT=NULL;//置空二叉樹 intk;istreamins(ls);//把串ls定義為輸入字符串流對象inscharch;ins>>ch;//從ins順序讀入一個(gè)字符while(ch! =‘?!?//逐個(gè)字符處理,直到遇到‘#’為止switch(ch){case‘(’:(1) ;k=1;break;case‘)’: pop(s); case’,’:(2) default:p=newBinTreeNode;( ; >leftChild=NULL; >rightChild=if(BT==NULL)(4) ;elseif(k==1)top(s)>leftChild=p;elsetop(s)>rightChild=p;}( }}【清華大學(xué)2001六、(15分)】四、應(yīng)用題1.一個(gè)深度為L的滿K叉樹有以下性質(zhì):第L層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn),其余各層上每個(gè)結(jié)點(diǎn)都有K棵非空子樹,如果按層次順序從1開始對全部結(jié)點(diǎn)進(jìn)行編號,求:1)各層的結(jié)點(diǎn)的數(shù)目是多少2)編號為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)的編號是多少3)編號為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)(若存在)的編號是多少4)編號為n的結(jié)點(diǎn)有右兄弟的條件是什么?如果有,其右兄弟的編號是多少請給出計(jì)算和推導(dǎo)過程?!疚鞅惫I(yè)大學(xué)1999五(10分)】【中科院自動(dòng)化所1996二、1(10分)】類似本題的另外敘述有(1)一棵高度為h的滿k叉樹有如下性質(zhì):根據(jù)結(jié)點(diǎn)所在層次為0;第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn);其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹,如果按層次自頂向下,同一層自左向右,順序從1開始對全部結(jié)點(diǎn)進(jìn)行編號,試問:1)各層的結(jié)點(diǎn)個(gè)數(shù)是多少?(3分2)編號為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)的編號是多少?(3分3)編號為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)(若存在)的編號是多少?(3分4)編號為i的結(jié)點(diǎn)有右兄弟的條件是什么?其右兄弟結(jié)點(diǎn)的編號是多少?(3分【清華大學(xué)1999 (12分)2.已知完全二叉樹的第七層有10個(gè)葉子結(jié)點(diǎn),則整個(gè)二叉樹的結(jié)點(diǎn)數(shù)最多是多少【西安電子科技大學(xué)2000計(jì)應(yīng) 一、4(5分)3.在一棵表示有序集S的二叉搜索樹(binarysearchtree)中,任意一條從根到葉結(jié)點(diǎn)的路徑將S分為3部分:在該路徑左邊結(jié)點(diǎn)中的元素組成的集合Sl;在該路徑上的結(jié)點(diǎn)中的元素組成的集合S2;在該路徑右邊結(jié)點(diǎn)中的元素組成的集合S3。S=S1∪S2S3。若對于任意的alb∈S2c∈是否總有ac為什么?【清華大學(xué)2000四(10分)】【武漢大學(xué)2000三、34.一棵非空的二叉樹其先序序列和后序序列正好相反,畫出這棵二叉樹的形狀【西安電子科技大學(xué)2000軟件 一、8(5分)】5.對如下算法,解答下列問題。PROCEDUREinorder(T:bitree);BEGINtop:=1;s[top]:=T;Ls[top]<>NILDOBEGINs[top+1]:=s[top]^.lchild;top:=top1;IFtop>1THENBEGINtop:=top1;WRIT(s[top]^.data);s[top]:s[top]^.rchild;UNTILtop=0EN(1)該算法正確嗎?循環(huán)結(jié)束條件top=能否滿足(2)若將IFtop>1…改為IFtop>0…是否正確(3)若將結(jié)束條件改為top=1,其它不變,是否正確(4)若僅將結(jié)束處條件改為(top=1)AND(s[top]=NIL),是否正確(5)試找出二叉樹中各結(jié)點(diǎn)在棧中所處層次的規(guī)律【西安電子科技大學(xué)2000計(jì)應(yīng)用 三(10分)】五、算法設(shè)計(jì)題1.在二叉樹中查找值為x的結(jié)點(diǎn),試編寫算法(用C語言)打印值為x的結(jié)點(diǎn)的所有祖先,假設(shè)值為x的結(jié)點(diǎn)不多于一個(gè),最后試分析該算法的時(shí)間復(fù)雜度(若不加分析,直接寫出結(jié)果,按零分算)?!旧虾=煌ù髮W(xué)1998五】類似本題的另外敘述有(1)在二叉樹中查找值為x的結(jié)點(diǎn),請編寫一算法用以打印值為x的結(jié)點(diǎn)的所有祖先,假設(shè)值為x的結(jié)點(diǎn)不多于1個(gè)。注:采用非遞歸算法?!疚靼搽娮涌萍即髮W(xué)1996六(10分)(2)設(shè)二叉樹中結(jié)點(diǎn)的數(shù)據(jù)域的值互不相同,試設(shè)計(jì)一個(gè)算法將數(shù)據(jù)域值為x的結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的數(shù)據(jù)域打印出來?!颈狈浇煌ù髮W(xué)1996八(20分)】(3)設(shè)二叉樹根指針為t,且樹中結(jié)點(diǎn)值各不相同,寫出算法dispf(t,x),查找樹中值為t的結(jié)點(diǎn),并顯示出其所有祖先結(jié)點(diǎn)的值?!臼锥冀?jīng)貿(mào)大學(xué)1998三、4(20分)】(4)若一棵二叉樹中沒有數(shù)據(jù)域值相同的結(jié)點(diǎn),設(shè)計(jì)算法打印數(shù)據(jù)域值為x的所有祖先結(jié)點(diǎn)的數(shù)據(jù)域。如果根結(jié)點(diǎn)的數(shù)據(jù)域值為x或不存在數(shù)據(jù)域值為x的結(jié)點(diǎn),則什么也不打印。例如右圖所示的二叉樹,則打印結(jié)點(diǎn)序列為A、C、E。【北京工業(yè)大學(xué) 五、(16分)】2.寫一非遞歸遍歷算法,使下圖樹遍歷輸出順序?yàn)樽帜疙樞??!局袊嗣翊髮W(xué)20003.設(shè)兩棵二叉樹的的根結(jié)點(diǎn)地址分別為p和q,采用二叉鏈表的形式存儲這兩棵樹上所有的結(jié)點(diǎn)。請編寫程序,判斷它們是否相似?!旧虾=煌ù髮W(xué)2000十二(8分)】類似本題的另外敘述有(1)編寫一個(gè)函數(shù)或過程判定兩棵二叉樹是否相似,所謂兩棵二叉樹s和t相似,即是要么它們都為空或都只有一個(gè)結(jié)點(diǎn),要么它們的左右子樹都相似。【廈門大學(xué)2000四、1(9分)】(2)設(shè)計(jì)判斷兩棵二叉樹是否相似的算法?!局袊V業(yè)大學(xué)2000四(10分)4.已知二叉樹以二叉鏈表存儲,編寫算法完成:對于樹中每一個(gè)元素值為x的結(jié)點(diǎn),刪去以它為根的子樹,并釋放相應(yīng)的空間?!颈本┹p工業(yè)學(xué)院1998二(14分)】類似本題的另外敘述有(1)設(shè)T是一棵給定的查找樹,試編寫一個(gè)在樹中刪除根結(jié)點(diǎn)為a的子樹的程序,要求在刪除的過程中釋放該子樹所有結(jié)點(diǎn)所占有的存儲空間,這里假設(shè)樹T中結(jié)點(diǎn)所占有的存儲空間是通過動(dòng)態(tài)存儲分配取得的,其結(jié)點(diǎn)的形式為:(lchild,data,rchild)【復(fù)旦大學(xué)1999七、(15分)】第四 在數(shù)據(jù)結(jié)構(gòu)中,圖的結(jié)構(gòu)是最復(fù)雜的,這里的概念也是最多的。我們要掌握圖的基本概念(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、最短路徑、關(guān)鍵路徑等)。圖的存儲及基本操作主要有鄰接矩陣法和鄰接表法,我們要掌握這有向圖和無向圖的這2種存儲方法,要清楚圖的連通和存儲方法之間的關(guān)系。例如,一個(gè)頂點(diǎn)的出度和臨界矩陣中1的個(gè)數(shù)有什么關(guān)系,等等。圖的遍歷方法有深度優(yōu)先搜索和廣度優(yōu)先搜索,我們要掌握這2種遍歷方法的算法實(shí)現(xiàn)。給出一個(gè)具體的圖,要能知道它的遍歷次序。在數(shù)據(jù)結(jié)構(gòu)課程中,圖的基本應(yīng)用是最多的,也是最復(fù)雜的,我們要掌握這些應(yīng)用的復(fù)雜度分析。要掌握的具體應(yīng)用主要包括最?。ù鷥r(jià))生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑。在給出的一個(gè)具體的圖中,我們要會利用已知條件,求出上述應(yīng)用的結(jié)果?!敬缶V解讀在這一章中需要識記的是圖以及基于圖的各種定義,存儲方式。要熟練掌握圖的深度遍歷和廣度遍歷算法,這是用圖來解決應(yīng)用問題時(shí)常用的算法基礎(chǔ)。需要掌握基于圖的多個(gè)算法,能夠以手工計(jì)算的方式在一個(gè)給定的圖上執(zhí)行特定的算法求解問題。常見的應(yīng)用問題直接給出或經(jīng)過抽象,會成為下列問題:最小生成樹求解(PRIM算法和KRUSKAL算法,兩種方法思想都很簡單,但要注意不要混淆這兩種方法),拓?fù)渑判騿栴}(這里會用到數(shù)組實(shí)現(xiàn)的鏈表,可以注意一下),關(guān)鍵路徑問

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論