【正文】 ____c)在表首插入S結(jié)點的語句序列是______d)在表尾插入S結(jié)點的語句序列是______(1)Pnext=S。(2)Pnext=Pnext.next。(3)Pnext=Snext。(4)Snext=Pnext。(5)Snext=L。(6)Snext=NIL。(7)Q=P。(8)WHILEPnextQP=Pnext。(9)WHILEPnext!=NULLP=Pnext。(10)P=Q。(11)P=L。(12)L=S。(13)L=P。4已知樹T的先序遍歷序列為ABCDEFGHIJKL，后序遍歷序列為CBEFDJIKLHGA，請畫出樹T。4對關(guān)鍵字序列（72，87，61，23，94，16，5，58）進行堆排序、快速排序、直接選擇排序，使之關(guān)鍵字遞增有序，請寫出每個排序的前三趟結(jié)果。4請畫出廣義表D的圖形表示D=(D,(a,b),((a,b),c),())4若一二叉樹有2度結(jié)點100個，則其葉結(jié)點有多少個？該二叉樹可以有多少個1度頂點？4對于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個指向鏈表中某結(jié)點的指針p，能否將p所指結(jié)點的數(shù)據(jù)元素與其確實存在的直接前驅(qū)交換?請對每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。單鏈表和單循環(huán)鏈表的結(jié)點結(jié)構(gòu)為datenext雙向鏈表的結(jié)點結(jié)構(gòu)為priordatenext(1)單鏈表(2)單循環(huán)鏈表(3)雙向鏈表4已知散列函數(shù)為H(key)=key%7，散列表長度為7(散列地址空間為0..6)，待散列序列為：(25，48，32，50，68)。要求：(1)根據(jù)以上條件構(gòu)造一散列表，并用線性探測法解決有關(guān)地址沖突；(2)若要用該散列表查找元素68，給出所需的比較次數(shù)。4已知一組鍵值序列為(38，64，73，52，40，37，56，43)，試采用快速排序法對該組序列作升序排序，并給出每一趟的排序結(jié)果。4已知某二叉樹的順序存儲結(jié)構(gòu)如圖所示，試畫出該二叉樹。50、設(shè)有一個關(guān)鍵碼的輸入序列{55,31,11,37,46,73,63,02,07}(1)從空樹開始構(gòu)造平衡二叉搜索樹,畫出每加入一個新結(jié)點時二叉樹的形態(tài)。若發(fā)生不平衡,指明需做的平衡旋轉(zhuǎn)的類型及平衡旋轉(zhuǎn)的結(jié)果。(2)計算該平衡二叉搜索樹在等概率下的查找成功的平均查找長度和查找不成功的平均查找長度。5求下列廣義表運算的結(jié)果：1)HEAD(p,h,w)。2)TAIL(b,k,p,h)。3)HEAD((a,b),(c,d))。4)TAIL(a,b),(c,d)。5)HEAD（TAIL（（(a,b),(c,d)）））6)TAIL（HEAD((a,b),(c,d))）5畫出下列廣義表的圖形表示：1)D（A（）），B（e），C（a,L(b,c,d)）2)J1(J2,(J1,a,J3(J1)),J3(J1))5完成下列要求：1）請畫出下列廣義表的存儲結(jié)構(gòu)（(((a),b)),(((),(d)),(e,f))）2）請寫出下面鏈表表示的廣義表5一棵二叉樹如圖：1)寫出對此樹進行中序、先序、后續(xù)遍歷時得到的結(jié)點序列。2)畫出樹的后序線索二叉樹。5具有3個節(jié)點的樹和具有3個節(jié)點的二叉樹它們的所有不同形態(tài)有哪些？5將下列森林轉(zhuǎn)化為二叉樹。5已知一個圖如下所示，寫出其臨接矩陣，并從頂點a出發(fā)按深度優(yōu)先搜索、按廣度優(yōu)先搜索，則可以得到所有頂點序列為什么？5試問在直接插入排序、希爾排序、快速排序、歸并排序、二分法排序、直接選擇排序中，哪些排序是穩(wěn)定的？哪些是不穩(wěn)定的，哪個排序平均比較次數(shù)最少？哪個排序要求內(nèi)存容量最多？5哈希表中使用哈希函數(shù)H（key）=3*key%11,并采用開放定址法處理沖突，隨機探測再散列的下一地址公式為：d1=H(key)di=(di1+7*key)%11（I=2,3…..）試在0到10的散列地址空間中對關(guān)鍵字序列（22，41，53，46，30，13，01，67）畫出Hash表示意圖，并求在等概率情況下查找成功的平均查找長度。60、什么是內(nèi)部排序？什么是排序方法的穩(wěn)定性？說出你所學過的三個穩(wěn)定算法，一個不穩(wěn)定算法。6何為隊列上溢？一般用什么方法解決，簡述之。6載入下圖所示的有權(quán)圖G，回答下列問題：1）給出從結(jié)點v1出發(fā)按深度優(yōu)先搜索遍歷圖所得的結(jié)點序列；2）給出圖的拓撲序列；3）給出從結(jié)點v1到結(jié)點v8的最短路徑和關(guān)鍵路徑。6對于下圖，請給出1）對應(yīng)的鄰接矩陣，并給出A,B,C三個頂點的入度和出度；2）鄰接表表示和逆鄰接表表示；3）求其連同分量；6對于下圖的樹，分別用孩子鏈表和孩子兄弟鏈表法畫出存儲結(jié)構(gòu)。6對于下圖的樹，請分別用中序、先序的方法寫出其遍歷結(jié)果。6已知一個表{jan,feb,mar,apr,may,june,july,aug,sep}1)使按表中元素的次序依次插入一棵初始為空的二叉排序樹，畫出表中元素構(gòu)成的二叉排序樹。2)求初等概率情況下查找july的查找長度。6數(shù)組a[1..10,2..6,2..8]以行優(yōu)先的順序存儲，設(shè)第一個元素的首地址為100，每個元素占3個存儲長度的存儲空間，則元素A[5,1,8]的存儲地址為多少？6設(shè)有一組關(guān)鍵字（17，13，153，29，35，21）需插入到表長為12的表中，請回答下列問題：1）自己設(shè)計一個合理的散列函數(shù)2）用自己設(shè)計的函數(shù)將上述關(guān)鍵字插入到散列表中，畫出其結(jié)構(gòu)；并指出用線性探測法解決沖突構(gòu)造散列表的裝填因子為多少？6已知一棵三階B樹如下圖所示，假定依次從中刪除關(guān)鍵字46，24，52，8，93和80試畫出每次刪除結(jié)點后樹的情況：70、已知一棵三階的B樹如下圖所示，假定依次插入關(guān)鍵字50，83，10請畫出插入個結(jié)點后樹的情況：7令s=’aaab’,t=’abcaaa’,u=’abcaabbabcabaacbacbaaa’,分別求出他們的next值。7請畫出下列二叉樹的中序線索化前趨鏈樹，后序線索化后繼鏈樹。7將下列結(jié)點按輸入順序構(gòu)造一棵二叉平衡樹。{As，Bx，Ca，Dww，Ae，Cf，Edd，F(xiàn)ap，Goi，F(xiàn)ab，Hre}7試在如圖所示線索化的二叉樹中，查找指定結(jié)點E的后繼結(jié)點、C的前驅(qū)結(jié)點，并說明找到結(jié)果的原因。7什么是數(shù)據(jù)結(jié)構(gòu)？7試比較線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點。7堆棧和隊列都是特殊線性表，其特殊性是什么？7將兩個棧存入數(shù)組V[1..m]中應(yīng)如何安排最好?這時?？諚M的條件是什么?7內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m），提供給兩個棧S1和S2使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當這部分空間全滿時才發(fā)生上溢。80、給出數(shù)組intA[3…8，2…6]；當它在內(nèi)存中按行存放和按列存放時，分別寫出數(shù)組元素A[i,j]的地址計算公式（設(shè)每個元素占兩個存儲單元）。8若一二叉樹有2度結(jié)點100個，則其葉結(jié)點有多少個？該二叉樹可以有多少個1度頂點？8如圖所示的二叉樹完成中序遍歷、后續(xù)遍歷、先序遍歷，并畫出后續(xù)線索化的二叉樹。8將下圖轉(zhuǎn)換為二叉樹，對轉(zhuǎn)換后的二叉樹進行先根、中根、后根遍歷。8有一組數(shù)值123128，畫出哈夫曼樹的生成過程及最后結(jié)果。8有n個頂點的有向連通圖最多有多少條邊?最少有多少條邊？8什么是哈夫曼（Huffman）樹？8已知圖G={V,E}V={a,b,c,d,e}E={(a,b),(b,d),(c,d),(d,e),(e,a),(a,c)}畫出圖G，畫出圖G的鄰接表。8設(shè)一個有向圖為G=(V,E),其中V={v1,v2,v3,v4}，E={v2,v1,v2,v3,v4,v1,v1,v4,v4,v2},畫出該有向圖，并求出每個結(jié)點的入度和出度，畫出相應(yīng)的鄰接矩陣、鄰接表和逆鄰接表。8請給出下圖的鄰接矩陣和鄰接表。90、請畫出下圖中的極大連通子圖。9對于如下圖請畫出其用prim和kruskal兩種不同算法生成最小生成樹的各條邊的并入順序。畫出最小生成樹。并寫出廣度優(yōu)先和深度優(yōu)先的結(jié)點遍歷順序。9什么是靜態(tài)查找，什么時動態(tài)查找，什么叫平均查找長度。9用序列（46，88，45，39，70，58，101，10，66，34）建立一個二叉排序樹，畫出該樹，并求在等概率情況下查找成功的平均查找長度。9已知一個線性表（38，25，74，63，52，48），假定采用h(k)=k%7計算散列地址進行散列存儲，若引用線性探測的開放地址法解決沖突，則在該散列表上進行檢索的平均檢索長度為多少，若利用連地址法處理沖突，則在該散列表上進行檢索的平均查找長度為多少？設(shè)地址空間為9。請畫出算列表。9已知長度為12的表：（Jan,Fed,Mar,Apr,May,Jun,Aug,Sep,Oct,Nov,Dec）按表中元素的順序，依次插入一棵初始為空的二叉排序樹，畫出插完之后的二叉排序樹，并求其在等概率情況下，查找成功的平均查找長度。9有散列函數(shù)為h(k)=k%11,如果用二次探測在散列的方式解決沖突，49應(yīng)放入哪？0123456789101112139用增量序列{1}對下列關(guān)鍵字進行希爾排序，用圖表示排序過程。{535494950、654560、7890}100、有一組關(guān)鍵字{14，15，30，28，5，10}，分別畫出冒泡排序、快速排序過程的圖示。10已知一組鍵值序列為(38，64，73，52，40，37，56，43)，試采用快速排序法對該組序列作升序排序，并給出每一趟的排序結(jié)果。10對關(guān)鍵字序列（72，87，61，23，94，16，5，58）進行堆排序、快速排序、直接選擇排序，使之關(guān)鍵字遞增有序，請寫出每個排序的前三趟結(jié)果。五、程序題四、程序題已知二叉樹用下面的順序結(jié)構(gòu)存儲，寫出中序遍歷該二叉樹的算法。leftdateright下列算法為刪除單鏈表中值為X的算法，將程序填完整voiddel(structnode*head){q=head。p=qnext。while(()amp。amp。()){q=p。_________。}if(p==null)printf(“error”)。else{______________。free(p)。printf(“success!”)。}}以下函數(shù)中，h是帶頭結(jié)點的雙向循環(huán)鏈表的頭指針，（1）寫出下列程序的功能。（2）當鏈表中結(jié)點數(shù)分別為1和6（不包括頭結(jié)點）時，請寫出程序中while循環(huán)體的執(zhí)行次數(shù)。Intfox(structnode*h){structnodep,q。intj=1。p=hnext。q=hprior。while(p!=qamp。amp。pprior!=q){if(pdata==qdata){p=pnext。q=qprior。j++。}elsej=0。}return(j)。}寫出按后序序列遍歷中序線索樹的算法.寫出計算樹深度的算法。寫出計算樹葉子結(jié)點的算法。寫出計算字符串長度的算法。試寫出以帶頭結(jié)點單鏈表為存儲結(jié)構(gòu)實現(xiàn)簡單選擇排序的算法閱讀下列算法，并回答下列問題：（1）該算法完成什么功能？（2）算法中R[n+1]的作用是什么？Voidsort(elemtyper[],intn){intk,i。for(k=n1。k=1。k)if(r[k]r[k+1]){r[n+1]=r[k]。for(i=k+1。r[i]r[n+1]。i++)r[i1]=r[i]。r[i1]=r[n+1]。}}試編寫一算法，以完成在帶頭結(jié)點單鏈表L中第i個位置前插入元素X的操作。，若某結(jié)點度為2，則該結(jié)點有左右兩個孩子，請編寫算法計算一二叉樹所有度數(shù)為2的結(jié)點個數(shù)。1試設(shè)計一個算法在中序線索化的樹中，求指定結(jié)點P在后序遍歷序列中的前驅(qū)結(jié)點，要求用非遞歸算法。1若X和Y是兩個單鏈表存儲的串，設(shè)計一個算法，找出X中第一個不在Y中出現(xiàn)的字符。1試設(shè)計一個算法在中序線索化的樹中，求指定結(jié)點P在后序遍歷序列中的前驅(qū)結(jié)點，要求用非遞歸算法。1設(shè)計一個算法，刪去串中第I個字符開始的J個字符，說明算法所用的存儲結(jié)構(gòu)，并估計算法的執(zhí)行時間。1設(shè)有單鏈表中存放著N個字符，試設(shè)計算法判斷字符串是否中心對稱關(guān)系，例如：XYZZYX，XYZYX都算是中心對稱的字符串。要求用盡可能少的時間完成判斷(提示：將一半字符先依次進棧)。提示:我們設(shè)H為指向鏈表頭結(jié)點的指針,單鏈表每個結(jié)點包括兩個域:分別是date,next分別代表數(shù)據(jù)域和指針域,s為定義的棧。1設(shè)計一個算法將任意輸入的N個數(shù)，按輸入的順序(或逆序)鏈接成一個單鏈表。1試設(shè)計一個算法，求單鏈表中數(shù)據(jù)值為X0的元素的地址。1試編一個程序，將兩個字符串s1和s2進行比較，若s1s2則輸出一個正數(shù)；若s1=s2，則輸出0；若s1s2，則輸出一個負數(shù)。不能用strcmp函數(shù)。寫出在中序線索二叉樹中結(jié)點*p的右子樹中插入一個結(jié)點*s的算法。2給定一棵用鏈表表示的二叉樹，其根指針為t，試寫出從根開始，按層次遍歷二叉樹的算法，同層的節(jié)點按從左到有的次序訪問。2完成在二叉排序樹中查找結(jié)點的程序Bitreptr*bstsearch(t,k)Bitreptr*k。Keytypek。{if(t==null)returnnull。elsewhile(t!=null){if(tkey==k)_________。if(tkeyk)______________。else____________________。}}2編寫一個算法交換單鏈表中P所指向的位置和其后續(xù)位置上的兩個結(jié)點，HEAD指向該鏈表的表頭，P指向該鏈表中的某一結(jié)點。2已知兩個鏈表A和B，其元素值遞增排列。寫出編程將A和B合并成一個遞減有序（相同值只保留一個）的鏈表C的思想，并要求利用原表結(jié)點。（*）2下列算法完成在一個帶頭單鏈表中第i個結(jié)點前插入一個結(jié)點算法，請將空余處填上。Voidinserti(structnode*head){p=headnext。k=0。while(p!=null)amp。amp。(k_______){________。k++。}ifp!=null{printf(“pleaseinputtox”)。scanf(“%d”,amp。x)。q=(structnode*)malloc(sizeof(structnode))。qdata=x。_________。_________。}elseprintf(“notfoundithnode”)。}2寫出下列算法的功能：voidweizhi(structnode*head){p=headnext；headnext=null。while(p!=null){q=pnext。pnext=headnext。headnext=p。p=q。}}2建立一個帶頭結(jié)點、有10個結(jié)點的單鏈表，請將下列算法填完整。Voidgreat(){structnode*head,*p,*s。inti,x。head=(structnode*)malloc(sizeof(structnode))。headnext=null。p=head。for160