【正文】 限制在于節(jié)點的位置相對固定.（）.（）,則一般唯一.（）(每小題 3 分,共 9 分) (共 31分),并畫出主要轉化過程圖示.(4 分) W={2,3,4,7,8},試構造關于 W 的一棵哈夫曼樹,并求其加權路徑長度 WPL 的 值.(6 分),并從頂點 1 出發(fā)依據存儲結構進行廣度遍歷, ABCDEF,中序序列為 BCAEDF,畫出此二叉樹的示意圖,并給 出其后序序列的線索樹.(6 分){51,28,36,86,7},請建立一個堆,要求畫出堆形成的示意圖.(6 分),現在要在節(jié)點P之后插入一個節(jié)點Q,請寫出插入動作的具體語句.(4分)（共20 分） A[1..m]作為循環(huán)隊列的存儲區(qū)域,試編寫一個出隊的類 PASCAL 語言算法.(6 分)2．利用類 pascal 語言寫出統(tǒng)計二叉樹中節(jié)點個數的算法（6 分）.3．利用類 pascal 語言寫出快速排序中一趟塊排的算法（8 分）.數據結構試題9答案一、CBDADBCDAD1A1D1B1A1C二、A C DA BA C D ED EB C三、順序,鏈接,索引,散列相對位置指令必須有確切含義,無歧義性開地址法,拉鏈法修改,檢索四、√五、三元組表 P244拓撲排序 P229AVL樹 P180六、鄰接表存儲表示同 A 卷六、2 廣度遍歷結果:1, 2, 6, 3, 4, 7, 8, 5后序:C B E F D A q↑.llink←pq↑.rlink←p↑.rlink p↑.rlink↑.llink←q p↑.rlink←q七、算法設計(6+6+8=20′)R=Fthenprint(‘underflow’)elseF←F MOD m+1算法結束TYPEpointer=↑nodenode=RECORD info: datatype。exchange_lr_node(t↑.rchild)end。t↑.rchild←q。beginif t=nilthen 算法結束else begin q ← t ↑.lchild。R〔j〕← R〔j1〕。flag:0..1。X:node。f2(j)=j。數據結構試題8答案一、ADBCBADCBB1B1B1B1A1A二、初等，組合存儲密度散列函數的選取，沖突（碰撞）的解決樹（森）林按關鍵碼排序 1/2Σdi生成樹林相對位置三、B C EB CA B C D四、快速排序是不穩(wěn)定的如對初始類排序碼：81 2 5 82 4 1經第一趟快排后為：〔1 2 5 82 4〕81經第二趟快排后為： 1 〔2 5 82 4〕81經第三趟快排后為： 1 2 〔5 82 4〕81經第四趟快排后為： 1 2 4 5 8281和 82 相對位置發(fā)生了變化由于有了線索的存在而使的周游樹形結構和找結點在指定次序下的前驅、后繼的算法變得很簡單、直截了當。Node=RECORD Data:datatype。END。_______1_____WHILE(______2_____)AND(Y=0)DO BEGIN mid : =(low+hig)DIV 2IF k=r[mid].key THENy:=mid ELSEIF kr[mid].key THEN _____3______ELSE _____4_______END。BEGINLow:=1。FUNCTION binfind(r:table。Info :datatype END。FOR i:=1 TO n DO BEGINt:=1。FOR i:=1 TO n DO Begin flag:=0。END。flag:0..1。數據結構試題7答案一． 二． 1． 2.√ 3.√ 4. 5. 6.√ 7. 8.√ 9. 10.三．1． n1 0 n(n1)/22． 奇數 i13． [log2N]+14． 先根 后根5．選取好的散列函數 沖突（碰撞）6． P↑.next↑.next7． 進棧 退棧8． 384 四．、深度：a,b,d,e,c 廣度：a,b,e,d,c五、TYPE node=RECORDVAR i,j:integer。5．從一棵空的 AVL 樹開始，將關鍵碼 xal,wan,wil,zol,yo,xum 逐個插入，畫出每插入一 個關鍵碼后得到的 AVL 樹。采用線性探測法解決沖突，試在 0～18 的散列地址空間中對該關鍵碼序列構造散列表。（圖1）（圖2）2．將上圖 2所示的二叉樹轉換為樹或樹林（畫出連線刪線圖和結果圖）。8． 已知一棵完全二叉樹中共有 768 結點，則該樹中共有_______個葉子結點。6．在一個帶頭結點的單循環(huán)鏈表中，p 指向尾結點的直接前驅，則指向頭結點的指針 head可用 p 表示為 head=_______。：____ ____、________和層次遍歷。2．若按層次順序將一棵有n個結點的完全二叉樹的所有結點從1到n編號，那么當i為_____且大于 1時，結點I 的左兄弟是結點___ _，否則結點 i 沒有左兄弟。（）。（） 樹的任何子樹都是 AVL樹。()，則該方法沒有實際的應用價值。（） G 的拓撲序列唯一，則其弧數必為 n1(其中 n為 G 的頂點數)。算法的 ADL描述如下： [初始化]FOR i=1 TO n DO A[i]←0FOR i=1 TO n DO FOR j=1 TO n DOIF adjacency[i,j]=1 THENA[i]←A[i]+1數據結構試題7一、單項選擇題（每小題 2 分，共 20 分）1．序列 A,B,C,D,E 順序入棧,不能獲得的序列是:（）A．ABCDE :（） :（） P指針後的節(jié)點 Q 需要修改的指針域個數為:（）A．25．設 n0,n1,n2 分別是二叉樹中度為 0,1,2 的結點數,則有:（）A．n0=n2+1=n21=n1+1=n11 6．下列說法中錯誤的是：（） 個結點的樹的各結點度數之和為 n1 個結點的有向圖最多有 n*(n1)條邊 7． 若線性表采用順序存儲結構，每個元素占用 4個存儲單元，第一個元素的存儲地址為 100，則第 12 個 元素的存儲地址是：（）A． 113 ？（） 5000 個無序的元素，希望用最快的速度挑選出其中前 50個最大的元素，最好選用:（） （25，84，21，47，15，27，68，35，20）進行排序時，序列的 變化情況如下，則所采用的排序方法是:（）20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84A．選擇排序 B．希爾排序 C．歸并排序 D．快速排序二、判斷題（每小題 1 分，共 10 分，對的打√，錯的打），一定得到不同二叉排序樹。，只有直接插入排序、冒泡排序、直接選擇排序易于在鏈表上實現。（1）不存在空間浪費問題；（2）順序存儲方式下，父子結點之間的關系可用公式描述，訪問結點方便。（3）最小堆的最小值元素必在堆頂，最大值的元素只有在葉結點上。數組插入和刪除需移動數據元素，鏈表插入和刪除不移動數據元素，鏈表比數組易于實現插入和刪除操作；（2）在空間占用方面，數組優(yōu)于鏈表；（3）在數據存取方面，數組是隨機存取方式，而2 鏈表是順序存取方式。數據結構試題6答案一、 二、1．O（n）O（1）2．163．2 h 一 h 一14．最小值 最大值5．n一16．O（n 2）O（n十e）、7．順序 有序8．開放定址法 鏈接法（次序無先后）9．O（1og2n）O（n）10．9三、2.√ 5.√8.√四、1．區(qū)別：數組占用連續(xù)的內存空間，鏈表不要求結點的空間連續(xù)。1．已知非空單鏈表第一個結點由 list 指出，寫一算法，交換p 所指結點（不是鏈表中第一個結點,也不是鏈表中最后的那個結點）與其下一個結點在鏈表中的位置，并給出算法的時間復雜度。（）四、簡答題（每題10分，共60分）1．說明數組和鏈表的區(qū)別，各有何優(yōu)缺點？2．回答下列關于堆的一些問題：（1）堆的定義是什么？（2）存儲表示是順序的，還是鏈式的？（3）設有一個最小堆，其具有最小值、最大值的元素分別可能在什么地方？3．完全二叉樹用什么數據結構實現最合適，為什么？、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排 序和歸并排序中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實現？5．用下列三種表示法畫出下圖G的存儲結構（1）相鄰矩陣（2）鄰接表（3）鄰接多重表6．已知序列（70，83，100，65，10，32，7），請給出采用插入排序法對該序列作升序排序時的每一趟結果。（），任一結點均有指向其前驅和后繼的線索。（），所以二叉樹是一種特殊的樹。（），檢索的方法不同。（），只要知道該元素的指針即可，因此單鏈表是隨機存取的存儲結構。三、判斷題（認為對的，在題后的括號內打“√”，錯的打“ⅹ”，每小題 １分，共１０）1．線性表中，每個結點都有一個前驅和一個后繼。9．快速排序在平均情況下的空間復雜度為_____，在最壞情況下的空間復雜度為_____。7．以二分查找方法查找一個線性表時，此線性表必須是_________存儲的________表。，要連通所有頂點則至少需要_________條邊。，最少含有______個結點，最多含有________個結點。()[A] K1[B] K[C] K+1[D] K（K+1）/22二、填空題（每小題2分，共20分）1．對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為______，在表尾插入元素的時間復雜度為________。（）[A] 快速排序[B] 堆排序[C] 歸并排序[D] 直接插入排序9．在對n個元素的序列進行排序時,堆排序所需要的附加存儲空間是__。（）[A] 1[B] 2[C] 1/2[D] 不一定7．遞歸函數F(n)=F(n1)+n+1(n1)的遞歸體是_______。（）[A] 9[B] 10[C] 11[D] 125．已知某二叉樹的后根序列是dabec，中根序列是debac，則先根序列是_____。（）[A] n[B] n/2[C](n+1)/2[D](n1)/23．設每個字符占一個字節(jié)，二維數組 A中每個元素有6個字符組成，其行下標從0到9，列下標從0到3，元素_____當A按行優(yōu)先存儲起始地址與當A按列優(yōu)先存儲的起始地址相同。第一篇：數據結構考試題目及答案數據結構試題6一、單項選擇題（每小題3分，共30分）1．設棧的輸入序列是4，則______不可能是其出棧序列。（）[A] 1234[B] 2134[C] 1432[D] 43122．在一個具有n個結點的線性鏈表中查找某個結點，若查找成功，需要平均比較_____個結點。（）[A] A[3][0][B] A[3][1][C] A[3][2][D] A[2][3]4．具有2000個結點的非空二叉樹的最小深度為_______。（）[A] acbed[B] decab[C] deabc[D] cedba 。（）[A] F(0)=0[B] F(1)=1[C] F(n)=n+1[D] F(n)=F(n1)+n+1 (nlog2n)的時間內完成對 n個元素的排序，且要求排序是穩(wěn)定的,則可選擇的排序方法是_______。（）[A] O(1)[B] O(log2n)[C] O(n)[D] O(n log2n)10．假定有K個關鍵字互為同義詞，若用線性探查法把這K個關鍵字存入散列表中，則總的探查次數至少為______。，第5層(根結點為1層)上的結點數最多為____________。，堆頂結點的值是所有結點中的_________，在一個大根堆中，堆頂結點的值是所有結點中的_________。6．假定一個圖具有n個頂點和e條邊，貝采用鄰接矩陣、鄰接表表示時，其相應的空間復雜度分別為__________和___________。8．在線性表的散列存儲中，處理沖突有___________和___________兩種方法。10．在一棵20階 B_樹中，每個非樹根結點的關鍵字數目最少為_______個,最多為____。（）2．有向圖的鄰接表和逆鄰接表中的結點數一定相同。（）、歸并排序和shell排序中，穩(wěn)定的是shell排序。（），負載因子值越小則存元素時發(fā)生沖突的可能性就越大。（），則它 必是該子樹后序周游序列中的第一個結點。（），所有同義詞在表中相鄰。五、算法設計題（每題15分，共30分）說明：可以使用任何高級程序設計語言或偽（類）程序設計語言。2．設計一個算法，統(tǒng)計一個采用鄰接矩陣存儲、具有n個頂點的無向無權圖所有頂點的度。各有何優(yōu)缺點：（1）插入和刪除操作。2．（1）堆是 n個元素的有限序列 K1，K2，? , KN，且滿足以下條件: Ki 1I=1,2,?, n/2（最小堆）或Ki = K2i 且Ki = K2i+1I