數據結構期中題庫及答案-資料下載頁

　　

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