數(shù)據(jù)結(jié)構(gòu)學位考試試題

數(shù)據(jù)結(jié)構(gòu)學位考試試題數(shù)據(jù)結(jié)構(gòu)課程學位考試試題判斷題：判斷下列各小題敘述的正誤。對，在題號后的括號內(nèi)填入“√ ”；錯，在題號后填入“ ×”。1、數(shù)據(jù)的最小單位是數(shù)據(jù)項。 ??????????.( √)、多重表文件中主索引為非稠密索引，次索引為稠密索引。???.(√)、通常數(shù)據(jù)結(jié)構(gòu)在計算機中有四種不同的表示方法分為順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、索引存儲、文件存儲。???.??.(×)、算法具有輸入、輸出、可行性、穩(wěn)定性、有窮性五個特性。.(×)5、數(shù)據(jù)的基本單位是數(shù)據(jù)項。??????????.(×)6、算法的復雜度分為時間復雜度和效率復雜度。????.(×)7、性質(zhì)相同的數(shù)據(jù)元素的集合成為數(shù)據(jù)對象。.(√)、所有結(jié)點按1對1的鄰接關(guān)系構(gòu)成的整體就是集合結(jié)構(gòu)。???.(×)9、散列文件不能順序存取、只能按關(guān)鍵字隨機存取。?????.(√)10、數(shù)據(jù)的基本單位是數(shù)據(jù)元素。??????????.(√)11、B+樹中的K個孩子的結(jié)點必有K個關(guān)鍵字。???.(√)12、B+樹中的K個孩子的結(jié)點必有K個關(guān)鍵字。???.??.(√)2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)1/62、倒排表的索引項中沒有頭指針和鏈表長度項。????.( √)、磁帶是順序存取的外存儲設(shè)備。 . .( ×)15 、索引文件只能是磁盤文件。 ????????????(√)、順序文件只適宜于順序存取。 .. .( ×)17 、磁帶是順序存取的外存儲設(shè)備。 ??????????.??.( ×)18 、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲， 也可以鏈接存儲。?????.( √)19、倒排表的索引項中沒有頭指針和鏈表長度項。 ???????.( √)20、散列文件不能順序存取、只能按關(guān)鍵字隨機存取。?.??.( √) 21、棧和隊列都是順序存取的的線性表，但它們對存取位置的限制不同。

22、循環(huán)鏈表從任何一個結(jié)點出發(fā)，都能訪問到所有結(jié)點

.......(

√

)23

、單鏈表從任何一個結(jié)點出發(fā)，

都能訪問到所有結(jié)點。

??.(

×)24、線性表采用順序存儲表示時，必須占用一片連續(xù)的存儲單元。(√)25、循環(huán)鏈表從任何一個結(jié)點出發(fā)，都能訪問到所有結(jié)點。.( √) 26、設(shè)串S的長度為 n,則S的子串個數(shù)為n(n+1)/2??.(×)、線性表采用鏈接存儲表示時，必須占用一片連續(xù)的存儲單元。.(×)28、鏈接表上做刪除和插入運算時的平均時間復雜度都是O(n)?.(×)2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)2/62、線性表中的每個結(jié)點最多只有一個前驅(qū)和一個后繼。 .( √ )30、順序表上做刪除和插入運算時的平均時間復雜度都是 O(n).( √)n31 、具有 n個結(jié)點的完全二叉樹的高度為┖ 2log2┘+1?????.( ×)、在只有度為0和度為2的結(jié)點的二叉樹中，設(shè)度為的結(jié)點有n0個，度為2的結(jié)點有n2個，則有n0=n2+1?????.( √)33 、循環(huán)隊列判斷隊列為滿的條件是 sq->front+1==sq->rear。??(×)、數(shù)組是一種復雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。???.(√)、若二叉樹中各結(jié)點的值均不相同，則二叉樹的前序序列和中序序列，或其后序序列和中序序列均能惟一地確定一棵二叉樹。....(√)、有n個結(jié)點的不同的二叉樹有n！棵。..(×)、一般樹和二叉樹的結(jié)點數(shù)目都可以為0。................(√)38、循環(huán)隊列判斷隊列為空的條件是sq->front==sq->rear。??(√)39、設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)3/62棧，如果 6個元素出線的順序是 s2,s3,s4,s6,s5,s1, 則棧的容量至少應該是 3。.( √)、在只有度為0和度為k的結(jié)點的k叉樹中，設(shè)度為的結(jié)點有n0個，度為k的結(jié)點有nk個，則有n0=nk+1??????.( ×)、一個連通圖的生成樹，是含該連通圖的全部頂點的一個極小連通子圖 .( √)i-142 、在二叉樹的第 i 層上至多有 2 個結(jié)點???.(√)、先根遍歷樹和先根遍歷與該樹對應的二叉樹，其結(jié)果不一樣。...(×)44、樹轉(zhuǎn)化成二叉樹，其根的右子女指針總是空的???.(√)、網(wǎng)絡的最小代價生成樹是唯一的...(×)46、深度優(yōu)先搜索遍歷類似于樹的先根遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是隊列。(×)47、在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進行中 序遍歷和后序遍歷，則具有相同的結(jié)果。???(√)、對于一棵具有n個結(jié)點，其高度為h的二叉樹，進行任一種次序遍歷的時間復雜度為、圖的深度優(yōu)先搜索類似于樹的先根次序遍2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)4/62歷????.(√)50 、在無向圖中定義頂點 Vi與Vj之間的路徑為從 Vi到達Vj的一個頂點序列51、設(shè)無向連通圖的頂點個數(shù)為n，則該圖最多有n(n-1)/2條邊?.(√)52、圖的廣度優(yōu)先遍歷是樹的按中根遍歷推廣。???(×)53、設(shè)圖G=(V,E)，V={1,2,3,4},E={,,,}，從頂點1出發(fā)，對圖G進行廣度優(yōu)先搜索的序列有2種...(√)、用鄰接表作為有向圖G的存儲結(jié)構(gòu)。設(shè)有n個頂點、e條弧，則拓撲排序的時間復雜度為 O(n*e)????.( ×)、查找表是同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合(√)、存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)......()57、圖的深度和廣度遍歷兩種操作的時間復雜度都為O。.(×n)1(v

)58

、只有無向圖，頂點數(shù)

n、邊數(shù)

e和度數(shù)之間有如下關(guān)系：

e=

D(×i)2i?159 、裝載因子是散列表的一個重要參數(shù)，它反映了散列表的裝滿程度。 60、閉散列法通常比開散列法時間效率更高。61、進行折半搜索的表必須是順序存儲的有序表。、索引順序查找的過程也是一個“縮小區(qū)間”的查找2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)5/62過程(√)、設(shè)有100個數(shù)據(jù)元素，采用折半搜索時，最大比較次數(shù)為7.(×)、在順序表中進行順序搜索時，若各元素的搜索概率不等，則各元素應按照搜索概率的降序排列存放，則可得到最小的平均搜索長度。??.(×)、在二叉搜索樹中，若各結(jié)點的搜索概率不等，使得搜索概率越小的結(jié)點離樹根越近，則得到的是最優(yōu)二叉搜索樹。???(√)66、閉散列法通常比開散列法時間效率更高。、折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。(√)68、起泡選擇排序是一種不穩(wěn)定的排序方法。(×)、折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。..(×)70、除留余法選擇一個適當?shù)恼麛?shù)p,以p除健值以所得的余數(shù)作為散列地址。71、選擇排序是一種不穩(wěn)定的排序方法。 (√)、直接選擇排序是不穩(wěn)定的，其時間復雜性為）O(1)。???.(×)?73 、快速排序是一種不穩(wěn)定的排序方法。 (√)、對于有n個對象的待排序序列進行歸并排序，所需平均時間為O。75、直接選擇排序是一種不穩(wěn)定的排序方2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)6/62法。. . . . . ( √)76 、直接插入排序是一種穩(wěn)定的排序方法。 (√)77 、歸并排序是一種不穩(wěn)定的排序方法。 (×)78、選擇排序是一種不穩(wěn)定的排序方法。(√) 79、歸并排序是一種不穩(wěn)定的排序方法。 (×) 80、堆排序是一種不穩(wěn)定的排序方法。 (√)二、單選題：從選擇的答案中選出正確的答案，將其字母編號填入下列敘述中的括號內(nèi)。 1、以下說法錯誤的是數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)實際的存儲形式B.算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的C.對鏈表進行插人和刪除操作時，不必移動結(jié)點 D.雙鏈表中至多只有一個結(jié)點的后繼指針為空 2、下列有關(guān)散列文件的說法中不正確的是 (C)A. 散列文件具有隨機存放的優(yōu)點 B.散列文件只能按關(guān)鍵字存取 C.散列文件需要索引區(qū) D.散列文件的記錄不需要進行排序、有一個算法3個部分的代碼嵌套連接組成，每部分的時間復雜度分別為O、O、O,該算法的時間復雜度為(D)A.O++ B.O

C. D.4、下列有關(guān)散列文件的說法中不正確的是

(C)A. 散列文件具有隨機存放的優(yōu)點按關(guān)鍵字存取 C.散列文件需要索引區(qū)

B.散列文件只能D.散列文件的記錄不需要進行排序 5、設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為。已知指針2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)7/62q所指結(jié)點是指針 p所指結(jié)事業(yè)的直接前驅(qū)， 若在*q與*p之間插入結(jié)點*s，則應執(zhí)行下列哪一個操作？。>next=p->next;p->next=sB． q->next=s ;s->next=p >next=s->next;s->next=p>next=s;s->next=q、對順序表上的插入、刪除算法的時間復雜性分析來說，通常以為標準操作 A. 條件判斷 B.結(jié)點移動 C.算術(shù)表達式 D.賦值語句、在循環(huán)鏈表中，將頭指針改設(shè)為尾指針后，其頭結(jié)點 和 尾 結(jié) 點 的 存 儲

位

置 分 別 是

和rear->next->next>next

和

real>next->next

和

rear

和

rear->next、有一個算法3個部分的線性代碼連接組成，每部分的時間復雜度分別為O、O、O,該算法的時間復雜度為(C)A.O++ B.O C. D.9、以下說法錯誤的是對循環(huán)鏈表來說，從表中任一結(jié)點出發(fā)都能通過前后操作而掃描整個循環(huán)鏈表B.對單鏈表來說，只有從頭結(jié)點開始才能掃描表中全部結(jié)點 C.雙鏈表的特點是找結(jié)點的前趨和后繼都很容易對雙鏈表來說，結(jié)點*P的存儲位置既存放在其前趨結(jié)點的后繼指針域中，也存放在它的后繼結(jié)點的前趨2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)8/62指針域中。、在串的基本運算中，屬于加工型運算的有(S,T) (S)(S,T) (S,T,R) 11 、線性鏈表不具有的特點是。A ．隨機訪問 B．不必事先估計所需存儲空間大小C．插入與刪除時不必移動元素 D．所需空間與線性表長度成正比 12、以下說法正確的是在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因為可以從頭結(jié)點進行查找任何一個元素在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結(jié)構(gòu)

C.順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈式結(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)

D.順序存儲方式只能用于存儲線性結(jié)構(gòu)、線性表是一個具有n個的有限序列。A ．表元素 B．字符 C．數(shù)據(jù)元素 D．數(shù)據(jù)項14、對于順序表，以下說法錯誤的是順序表是用一維數(shù)組實現(xiàn)的線性表，數(shù)組的下標可以看成是元素的絕對地址 B.順序表的所有存儲結(jié)點按相應數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列 C. 順序表的特點是:邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰順序表的特點是:邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中15、一個長度為n的順序表的表尾插入2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)9/62一個新元素的漸進時間復雜度為。2A.O(n) B.O(n/2) C.O(1) D.O(n)16 、單鏈表的一個存儲結(jié)點包含A. 數(shù)據(jù)域或指針域 B.指針域或鏈域 C. 指針域和鏈域 D.數(shù)據(jù)域和鏈域 17、在串的基本運算中，屬于引用型運算的有(S,T) (S1,i,S2)(S,i,j) (S,i,j)、一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為。2A.O(n) B.O(n/2) C.O(1) D.O(n)19 、向順序棧中壓入新元素時，應當。A. 先移動棧頂指針，再存入元素 B．先存入元素，再移動棧頂指針C. 先后次序無關(guān)緊要 D．同時進行、順序隊列的人隊操作應為(A)=+1;=x=x;=+1=(+1)%maxsize;=x[sqrear]=x;=(+1)%maxsize21 、頭結(jié)點的單鏈表 first 為空的判定條件是： (B)A.first==NULL; B.first->next==NULL;C.first->next==first; D.first!=NULL;22 、如果2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)10/62以鏈表作為棧的存儲結(jié)構(gòu)，則入棧操作時A 、必須判別棧是否滿 B、必須判別棧元素的類型C 、必須判別棧是否空 D、對棧不作任何判別、設(shè)有一個n?n的對稱矩陣A，將其下三角部分按行存放在一個一維數(shù)組

B中，

A[0][0]

存放于

B[0]

中，那么第i行的對角元素

A[i][i]

存放于

B中處。A.(i+3)*i/2 B.(i+1)*i/2D.(2n-i-1)*i/224 、一個棧的入棧序列是 a,b,c,d,e,

C.(2n-i+1)*i/2則棧的不可能的輸出序列是A.dceab

ecba

C.edcba

bcde25 、假定一個鏈式隊列的隊頭和隊尾指針分別為和rear，則判斷隊空的條件為 (A)。 A.frontB.front !=NULL C.rear !=NULL D.front

front==rear==NULL、當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為。 A. n-2 B.n-1 C.n D.n+127、循環(huán)鏈表主要優(yōu)點是不再需要頭指針了已知某個結(jié)點的位置后，能夠容易找到它的直接前趨C.在進行插入、刪除運算時，能更好地保證鏈表不斷開 D.從表中任一結(jié)點出發(fā)都能掃描到整個鏈表 28、稀疏矩陣一2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)11/62般采用(C)方法壓縮存儲。A. 三維數(shù)組 B.單鏈表 C.三元組表 D.散列表29、鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是A 插入操作更加方便 B通常不會出現(xiàn)棧滿的情況C不會出現(xiàn)?？盏那闆r D 刪除操作更加方便30 、設(shè)有一順序棧

S，元素

s1,s2,s3,s4,s5,s6

依次進棧，如果6個元素出線的順序是 s2,s3,s4,s6,s5,s1, 則棧的容量至少應該是 B.3 C.5、設(shè)有50行60列的二維數(shù)組A[50][60]，其元素長度為4字節(jié)，按行優(yōu)先順序存儲，基地址為200，則元素A[18][25]的存儲地址為。A．3700B．4376C．3900D．4620、設(shè)C語言數(shù)組DATA[m+1]作為循環(huán)隊列SQ的存儲空間，front為對頭指針rear為對尾指針，則執(zhí)行出隊操作的語句為=front+1 =(front+1)%m=(rear+1)%m D..front=(front+1)%(m+1)33循環(huán)隊列的隊滿條件為 (C)

、A.(+1)%mazsize==(+1)%maxsize;B.(+1%maxsize==+1(rear+1)%maxsize====、在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加。2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)12/62A.2B.1C.0D.–135、具有65個結(jié)點的完全二叉樹的高度為。A．8B．7C．6D．536、對某二叉樹進行前序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果為A ．DBFEAC B．DFEBCAC ．BDFECA D．BDEFAC37、循環(huán)隊列的出隊操作為(A)=(+1)%maxsize=+1=(+)%maxsize=+138、設(shè)F是一個森林，B是F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非葉結(jié)點，則B中右指針域為空的結(jié)點有個。A ．n-1 B．n C．n+1 D．n+239 、設(shè)二叉樹結(jié)點的先根序列、 中根序列和后根序列中，所有葉子結(jié)點的先后順序 (B)A. 都不相同 B.完全相同 C.先序和中序相同，而與后序不同 D.中序和后序相同，而與先序不同40 、對于順序存儲的隊列，存儲空間大小為 n，頭指針為F，尾指針為R。若在邏輯上看一個環(huán)，則隊列中元素的個數(shù)為(B)B.(n+R-F)modn C.(R-F+1)modn D.n+R-F41、2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)13/62以下說法錯誤的是

(A)A. 樹形結(jié)構(gòu)的特點是一個結(jié)點可以有多個直接前趨

B.線性結(jié)構(gòu)中的一個結(jié)點至多只有一個直接后繼

C.樹形結(jié)構(gòu)可以表達(組織)更復雜的數(shù)據(jù) D.樹(及一切樹形結(jié)構(gòu) )是一種分支層次 結(jié)構(gòu)42、以下說法錯誤的是 (B) 。二叉樹可以是空集B. 二叉樹的任一結(jié)點都有兩棵子樹 C.二叉樹與樹具有相同的樹形結(jié)構(gòu) D.二叉樹中任一結(jié)點的兩棵子樹有次序之分、在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于A．nB．n-1C．n+1D．2*n44、下列說法中正確的是。A.一棵二叉樹的度可以小于2B.二叉樹中任何一個結(jié)點的度都為2C.二叉樹的度為2D.任何一棵二叉樹中至少有一個結(jié)點的度為245、在一棵具有5層的滿二叉樹中結(jié)點數(shù)為A31B32C33D16、一個二叉樹按順序方式存儲在一個維數(shù)組中，如圖01234567891011121314ABCDEFGHIJ則結(jié)點E在二叉樹的第層。、在圖的鄰接表存儲結(jié)構(gòu)上執(zhí)行廣度優(yōu)先搜索遍歷類似于二叉樹上的 A.先根遍歷 B.中根遍歷 C.后根2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)14/62遍歷 D.按層次遍歷、任何一棵二叉樹的葉結(jié)點在其先根、中根、后跟遍歷序列中的相對位置

(C)

A.肯定發(fā)生變化

B.有時發(fā)生變化

C.肯定不發(fā)生變化

D.無法確定、在一棵高度為h(假定樹根結(jié)點的層號為0)的完全二叉樹中，所含結(jié)點個數(shù)不小于(B)。h+1h-1hhA.2 B.2 C.2-1 D.250 、樹若用雙親鏈表表示，則 (A)A. 可容易地實現(xiàn)求雙親及子孫的運算

B.求雙親及子孫的運算均較困難C. 可容易地實現(xiàn)求雙親運算，但求子孫運算較困難

D.可容易地實現(xiàn)求子孫運算，但求雙親運算較困難

51、任何一個帶權(quán)的無向連通圖的最小生成樹A. 只有一棵

B.有一棵或多棵

C.一定有多棵可能不存在52、設(shè)有向圖有n個頂點和e條邊，采用領(lǐng)接表作為其存儲表示，在進行拓撲排序時，總的計算時間為。A ．O B．OC．O(ne) D．O(n2)53、以下說法正確的是連通圖的生成樹，是該連通圖的一個極小連通子圖。無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣一定是不對稱的。C.任何一個有向圖，其全部頂點可以排成一2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)15/62個拓撲序列。 D.有回路的圖不能進行拓撲排序。 54、以下說法錯誤的是 (D)A.一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點越近B.哈夫曼樹中沒有度數(shù)為1的分支結(jié)點若初始森林中共有n裸二叉樹，最終求得的哈夫曼樹共有2n-1個結(jié)點若初始森林中共有n裸二叉樹，進行2n-1次合并后才能剩下一棵最終的哈夫曼樹 55、如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是(B)A. 完全圖 B.連通圖 C.有回路 D.一棵樹、將一棵有50個結(jié)點的完全二叉樹按層編號，則對編號為

25的結(jié)點

x，該結(jié)點

(B)

A.無左、右孩子

B.有左孩子，無右孩子

C.有右孩子，無左孩子

D.有左、右孩子、深度為6的二叉樹最多有(B)個結(jié)點、一個有序順表有255個對象，采用順序搜索法查表，搜索長度為。 A、128 B 、127 C、126 D、255、在有向圖中每個頂點的度等于該頂點的。A. 入度

B.出度C. 入度與出度之和

D.入度與出度之差60 、具有

n個頂點的有向無環(huán)圖最多可包含

(D)

條2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)16/62有向邊。 A．n-1 B．n C．n(n-1)/2 D．n(n-1)、用鄰接表作為有向圖G的存儲結(jié)構(gòu)。設(shè)有n個頂點、e條弧，則拓撲排序的時間復雜度為 (B) A.O(n) B.O(n+e) C.O(e) D.O(n*e)、一個有序順表有255個對象，采用順序搜索法查表，搜索長度為。 A、128 B 、127 C、126 D、255、在有向圖中，所有頂點的入度之和是所有頂點出度之和的倍。 B.1 C.2 64、以下說法錯誤的是用相鄰矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。鄰接表法只能用于有向圖的存儲，而相鄰矩陣法對于有向圖和無向圖的存儲都適用。存儲無向圖的相鄰矩陣是對稱的，因此只要存儲相鄰矩陣的下三角部分就可以了D. 用相鄰矩陣

A表示圖，判定任意兩個結(jié)點

Vi

和

Vj

之間是否有長度為

m的路徑相連，則只要檢查

A的第

i

行第

j列的元素是否為

0即可。、在圖的鄰接表存儲結(jié)構(gòu)上執(zhí)行深度優(yōu)先搜索遍歷類似于二叉樹上的 A.先根遍歷 B.中根遍歷 C.后根遍歷 D按層次遍歷 66、在一個無向圖中， 所有頂點的度2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)17/62數(shù)之和等于所有邊數(shù)的倍。 A．3 B．2 C．1 D．1/2、在無向圖中，所有頂點的度數(shù)之和是所有邊數(shù)的倍。、設(shè)有6個結(jié)點的無向圖，該圖至少應有條邊能確保是一個連通圖。 A.5 B.6 C.7 D.869 、以下說法正確的是A. 連通分量是無向圖中的極小連通子圖。 B.強連通分量是有向圖中的極大強連通子圖。在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧。D.對有向圖G,如果從任意頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個頂點，則該圖一定是完全圖。、對有14個數(shù)據(jù)元素的有序表R[14]進行折半搜索，搜索到R[3]的關(guān)鍵碼等于給定值，此時元素比較順序依次為。A．R[0]，R[1]，R[2]，R[3]B．R[0]，R[13]，R[2]，R[3]C．R[6]，R[2]，R[4]，R[3]D．R[6]，R[4]，R[2]，R[3]71、設(shè)有序表的關(guān)鍵字序列為{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，當用二分查找法查找健值為99的結(jié)點時，經(jīng)次比較后查找成功。 B.3 C.12、設(shè)有100個數(shù)據(jù)元素，采用折半搜索時，最大比較次數(shù)為A6 B7 C8 D102016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)18/62、對長度為n的有序單鏈表，若搜索每個元素的概率相等，則順序搜索到表中任一元素的平均搜索長度為A ．n/2 B．(n+1)/2 C．(n –1)/2 D．n/4、對采用二分查找法進行查找運算的查找表，要求按方式進行存儲。

A順序存儲

B鏈式存儲C 順序存儲且結(jié)點按關(guān)鍵字有序

D鏈式存儲且結(jié)點按關(guān)鍵字有序 75、二分查找法適用于存儲結(jié)構(gòu)為的，且按關(guān)鍵字排序的線性表 A.順序存儲 B. 鏈接存儲 C. 順序存儲或鏈接存儲 D. 索引存儲、在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為 A. O(n) B.O(n/2) C. O(1)D.O(n2)、在對查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于(C)A. 靜態(tài)查找表 B.動態(tài)查找表 C.靜態(tài)查找表與動態(tài)查找表 D.兩種表都不適合、在一個長度為n的順序表的表尾插入一個新元素的漸進時間復雜度為2A ．O(n) B．O(1) C．O(n) D．O(log2n)2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)19/6279、設(shè)有序表的關(guān)鍵字序列為{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，當用二分查找法查找健值為84的結(jié)點時，經(jīng)次比較后查找成功。 A2 B3 C4 D12、靜態(tài)查找表與動態(tài)查找表兩者的根本差別在于A 邏輯結(jié)構(gòu)不同 B存儲實現(xiàn)不同C 施加的操作不同 D數(shù)據(jù)元素的類型不同281 、以下時間復雜性不是插入排序 B. 二路歸并排序

O(n)的排序方法是 A.直接C. 冒泡排序 D. 直接選擇排序82 、一個對象序列的排序碼為

{46

，79，56，38，40，84}，采用快速排序以位于最左位置的對象為基準而得到的第一次劃分結(jié)果為。A ．{38，46，79，56，40，84}

B．{38

，79，56，46，40，84}C

．{40

，38，46，56，79，84}

D．{38

，46，56，79，40，84}83

、用順序查找法對具有

n個結(jié)點的線性表查找的時間復雜性量級為

B.O(nlog2n)

C.ODO(log2n)、用某種排序方法對序列進行排序，記錄序列的變化情況如下：25 84 21 47 15 27 68 35 20152016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)20/622021254727683584152021253527476884152021252735476884則采取的排序方法是A.直接選擇排序B.冒泡排序C.快速排序D.二路歸并排序85、一個對象序列的排序碼為{46，79，56，38，40，84}，采用快速排序以位于最左位置的對象為基準而得到的第一次劃分結(jié)果為。A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}86、順序查找法適合于存儲結(jié)構(gòu)的查找表。A. 壓縮 B.散列 C.索引 D.順序或鏈式 87、以下說法錯誤的是A. 直接插入排序的空間復雜度為 O(1)。B.快速排序附加存儲開銷為 O(log2n) 。C.堆排序的空間復雜度為 O(n)。D. 二路歸并排序的空間復雜度為 O(n),需要附加兩倍的存儲開銷。 88、對于大文件的排序要研究在外設(shè)上的排序技術(shù)，即A. 快速排序法 B. 內(nèi)排序法 C.外排序法 D.交叉排序法、對于長度為9的有序順序表，若采用折半搜索，在2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)21/62等概率情況下搜索成功的平均搜索長度為的值除以 9。A.20 B.18 C.25 D.22、具有24個記錄的序列，采用冒泡排序至少的比較次數(shù)是C.24D.529、當初始序列已按健值有序時，用直接插入算法進行排序，需要比較的次數(shù)為 C.2log2n、排序的目的是為了以后對已排序的數(shù)據(jù)元數(shù)進行操作。A.打印輸出 B.分類 C.合并 D.查找93、以下穩(wěn)定的排序方法是A. 快速排序

B.冒泡排序

C.直接選擇排序

D.堆排序94、方法是從未排序序列中依次取出元素與已排序序列中的元素作比較，將其放入已排序序列的正確位置上。A. 歸并排序 B. 插入排序 C.快速排序

D.選擇排序、在文件局部有序或文件長度較小的情況下，最佳的排序方法是A.直接插入排序B.冒泡排序直接選擇排序D.歸并排序

C.96 、如果只想得到

1024

個元素組成的序列中的前

5個最小元素，那么用方法最快。

A．起泡排序

B．快速排序 C．堆排序

D．直接選擇排序、對一個n個整數(shù)組成的序列，借助排序過程找出其中的最大值，希望比較次數(shù)和移動次數(shù)最少，應選用方法。2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)22/62A. 歸并排序 B.直接插入排序 C.直接選擇排序快速排序98、對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是

A直接選擇排序

B

直接插入排序

C 快速排序

D 起泡排序

99、以下不穩(wěn)定的排序方法是A. 直接插入排序 B.冒泡排序 C.直接選擇排序二路歸并排100 、在一個長度為 n的順序表的任一位置插入一個新元素的漸進時間復雜度為

A.O(n)

B.O(n/2)

C.O(1)

D.O(n2)三、填空題、有一個算法3個部分的線性代碼連接組成，每部分的時間復雜度分別為 O、O、O,該算法的時間復雜度為 (O)。、數(shù)據(jù)的基本單位是(數(shù)據(jù)元素)。、計算機中的算法指的是解決某一問題的有限運算序列，它必須具備輸入、輸出、可行性、(確定性)和(有窮性)等5個特征4 、所有結(jié)點按

1對

1的鄰接關(guān)系構(gòu)成的整體就是

(

線性)結(jié)構(gòu)

5、數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱

“鄰接關(guān)系”稱為

(

邏輯)

關(guān)系。2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)23/62、有一個算法3個部分的代碼嵌套連接組成，每部分的時間復雜度分別為 O、O、O,該算法的時間復雜度為 (O)。7 、數(shù)據(jù)元素之間邏輯關(guān)系的整體稱為 (邏輯結(jié)構(gòu)) 。、對一個算法要作出全面的分析可分成兩用人才個階段進行，即事先分析和(事后測試)。9、算法的復雜度分為(時間復雜度) 和(空間復雜度) 兩種。10 、數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的 ( 存儲結(jié)構(gòu))。11、文件的檢索有順序存取、直接存取和(按關(guān)鍵字存取)三種方式。12、文件的檢索有順序存取、直接存取和(按關(guān)鍵字存取)三種方式。13、在順序表中插入或刪除一個元素，需要平均移動((n+1)/2)元素，具體移動的元素個數(shù)與()有關(guān)。、VSAM文件結(jié)構(gòu)三部分組成：索引集、(順序集)和數(shù)據(jù)集。、ISAM文件是多級主索引、柱面索引、磁道索引和(主文件索引)組成。、已知：s1=〃I’mateacher〃，s2=〃teacher〃，s3=〃student 〃，則 REPLACE(s1,s2,s3) 等于(I’mateacher) 。、如果文件中的每個記錄都有一個索引項，則這樣的索引稱為(稠密索引)。18、如果文件中多個記錄只有一個索引項，則這樣的索引稱為(非稠密索引)。2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)24/62、在雙鏈表中，每個結(jié)點有兩個指針域，一個指向(前驅(qū))，另一個指向(后繼)。、當且僅當兩個串的(長度)相等并且各個對應位置上的字符都相同時，這兩個串相等。一個串中任意個連續(xù)字符組成的序列稱為該串的 ( 子串)串。、VSAM文件結(jié)構(gòu)三部分組成：索引集、(順序集)和數(shù)據(jù)集。、串的順序存儲有兩種方法：一種是每個單元只存一個字符，稱為(非緊縮格式)格式，另一種是每個單元存放多個字符，稱為(緊縮格式)格式。、線性表的常見鏈式存儲結(jié)構(gòu)有單鏈表、(雙向鏈表)和(循環(huán)鏈表)。、線性表典型的基本運算包括初始化、(插入)、(刪除)、查找定位、求長度、存取等六種。25、已知：s1=〃I’mateacher 〃，s2=〃teacher〃，s3=〃student〃，則SUBSTR(s1,7,7)等于teacher 〃，s2=〃

(student)teacher

。26、已知：s1=〃I’ma〃，s3=〃student 〃，則DELETE(s1,4,10) 等于(I ’m)。27、已知：s1=〃I’mateacher〃，s2=〃teacher〃，s3=〃student〃，則EQUAL(s1,s2)等于(0)。28、順序表中邏輯上相鄰的元素的物理位置(必須)緊鄰。單鏈表中邏輯2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)25/62上相鄰的元素的物理位置 (不需要)緊鄰。、四維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個數(shù)組元素最多有(4)個直接前驅(qū)、一般地，棧和線性表類似有兩種實現(xiàn)方法，即(順序)實現(xiàn)和( 鏈接)實現(xiàn)。31、含零個字符的串稱為 ( 空串)串，用(Ф)表示。、棧是一種限定在表的一端進行插入和刪除的線性表，又被稱為(后進先出)線性表。33、在棧的順序?qū)崿F(xiàn)中，設(shè)棧頂指針為top，棧空的條件為(top=0)。、若已知一個棧的入棧序列是1，2，3，4，?，n，其輸出序列是P1，P2，P3，?，Pn，若P1=n，則Pi為(n-i+1)。、對于順序存儲的棧，因為棧的空間是有限的，在進行(后進)運算時，可能發(fā)生棧的上溢，在進行(先出)運算時，可能發(fā)生棧的下溢。、(棧)可以作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。、對任何二叉樹，若度為2的節(jié)點數(shù)為n2，則葉子數(shù)n0=(n2+1)。38、隊列中允許進行刪除的一端稱為 (對頭)。、一般地，一個n維數(shù)組可視為其數(shù)據(jù)元素為(n)維數(shù)組的線性表。數(shù)組通常只有 (刪除)和(插入)兩種基本運算。、二叉樹有不同的鏈式存儲結(jié)構(gòu)，其中最常用的是(二叉鏈表)與(三叉鏈表)。41、以下運算實現(xiàn)在順序棧上2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)26/62的進棧，請在( )處用適當?shù)恼Z句予以填充。IntPush(SqStackTp*sq,DataTypex){

if(sp->top==sqstack_maxsize-1}{error(

“棧滿”);return(0);}

else{(sq->top++):(sq->data[sq->top])=x;return(1);}}、深度為90的滿二叉樹上，第11層有(210)個結(jié)點。、已知一棵度為3的樹有2個度為1的結(jié)點，3個度過為2的結(jié)點，1個度為3的結(jié)點，則該樹中有(6)個葉子結(jié)點。、深度優(yōu)先搜索遍歷類似于樹的(先根)遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是(棧)。45、具有n個結(jié)點的完全二叉樹的深度為([log2n]＋1)。、(樹)中結(jié)點的最大度數(shù)允許大于2，而(二叉樹)中結(jié)點的最大度數(shù)不允許大于 2、一棵樹按照左子女-右兄弟表示法轉(zhuǎn)換成對應的二叉樹，則該二叉樹中樹根結(jié)點肯定沒有(右)子女。k48 、深度為 k(k>=1)的二叉樹至多有 (2-1) 個結(jié)點。49 、有 m個葉子結(jié)點的哈夫曼樹，其結(jié)點總數(shù)為(2m-1) 。、在一棵樹中，(根)結(jié)點沒有前驅(qū)結(jié)點。2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)27/62、對無向圖，其鄰接矩陣是一個關(guān)于(對角線)對稱的矩陣。52 、n(n﹥0) 個頂點的有向連通圖最多有 (n(n-1))邊，最少有(n-1)條邊53、設(shè)無向連通圖 G的頂點數(shù)為

條n，則G最少有

(n-1)

條邊。、遍歷圖的基本方法有(深度)優(yōu)先搜索和(廣度)優(yōu)先搜索兩種。、在集合這種邏輯結(jié)構(gòu)中，任何結(jié)點之間都不存在( 邏輯 ) 關(guān)系，這是集合這種邏輯結(jié)構(gòu)的基本特點。 56、一個有向圖 G中若有弧,、和,則在圖G的拓撲序列中，頂點Vi、Vj和Vk的相對位置為(省略)。、廣度優(yōu)先搜索遍歷類似于樹的(層次)遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是(隊列)。58、(樹)轉(zhuǎn)換成二叉樹時，其根結(jié)點的右子樹總是空的。59、設(shè)圖G=(V,E)，V={1,2,3,4},E={,,,}，從頂點1出發(fā)，對圖G進行廣度優(yōu)先搜索的序列有種(2)。60、任何連通圖的連通分量只有一個，即(本身)。61、向一棵二叉搜索樹中插入一個元素時，若元素的值小于根結(jié)點的值，則應把它插入到根結(jié)點的(左子樹)上。、對有序表(25，30，32，38，47，54，62，68，90，用二分查找法查找32，則所需的比較次數(shù)為(3)。63、靜態(tài)查找表包括(建表)、(查找)、(讀元素)三種基本運算。2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)28/62、動態(tài)查找表包括建表、查找、讀元素、(插入)、(刪除)五種基本運算。、根據(jù)一組記錄依次插入結(jié)點生成一棵AVL樹時，當插入到值為(50)的結(jié)點時需要進行旋轉(zhuǎn)調(diào)整。、平衡二叉排序樹上任一結(jié)點的平衡因子只可能是(0)、(1)或(-1)。67 、在二叉排序樹上插入新結(jié)點時， 不必移動其它結(jié)點，僅需使某結(jié)點的指針域 (空)變?yōu)?指向該結(jié)點)即可。68 、在一棵AVL樹中，每個結(jié)點的左子樹高度與右子 樹高度之差的絕對值不超過 (1) 。、在具有24個元素的有序表上進行二分查找，則比較一次查找成功的結(jié)點數(shù)為(1)。70、快速排序是不穩(wěn)定的，其時間復雜性為(O)71、直接選擇排序是不穩(wěn)定的，其時間復雜性為(O的鍵值且(小)于其右孩子的鍵值。75、歸并排序的時間復雜度是(O)。2、簡單排序的時間復雜性為(O層至多有(2)個節(jié)點。2、直接插入排序是穩(wěn)定的，它的時間復雜性為(O=1000，A共占多少個字節(jié)？A的終端結(jié)點a78的起始地址為多少？按行和按列優(yōu)先存儲時，a45的起始地址分別為多少？答案：288；1284；行：1164列：1176)2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)29/62、設(shè)二維數(shù)組A8*9的每個元素占4個字節(jié)，行下標i的范圍從1到8，列下標j的范圍從0到8已知Loc=1000，A共占多少個字節(jié)？ A的終端結(jié)點 a78的起始地址為多少？按行和按列優(yōu)先存儲時， a65的起 始地址分別為多少？答案：288；1284；行：1200列：1180、設(shè)二維數(shù)組A8*9的每個元素占5個字節(jié)，行下標i的范圍從 0到7，列下標 j的范圍從 1到9已知Loc=2000，A共占多少個字節(jié)？ A的終端結(jié)點 a78的起始地址為多少？按行和按列優(yōu)先存儲時， a45的起始地址分別為多少？答案：360；2355；行：2200列：2185、設(shè)二維數(shù)組A11*9的每個元素占7個字節(jié)，行下標i的范圍從0到10，列下標j的范圍從1到9已知Loc=2500，A共占多少個字節(jié)？A的終端結(jié)點 a109的起始地址為多少？按行和按列優(yōu)先存儲時，a75的起始地址分別為多少？ 答案：693；3186；行：2969

列：28575、設(shè)二維數(shù)組A7*9的每個元素占4個字節(jié)，已知Loc=2000，A共占多少個字節(jié)？A的終端結(jié)點a68的起始地址為多少？按行和按列優(yōu)先存儲時，

a55

的起始地址分別為多少？答案：

252；2208；行：

2160

列：

21286 、設(shè)二維數(shù)組

A8*9

的每個元素占

8個字節(jié)，已知2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)30/62Loc=2000，A共占多少個字節(jié)？ A的終端結(jié)點 a78的起始地址為多少？ 答案：576；2568、設(shè)有一個10階的對稱矩陣A[10][10]，采用壓縮存儲方式按行將矩陣中下三角部分的元素存入一維數(shù)組 B[] 中，A[0][0] 存入B[0]中，則A[7][5]在B[]中位置為多少？答案：338 、設(shè)二維數(shù)組 A10*9的每個元素占 4個字節(jié)，已知Loc=2000，按行和按列優(yōu)先存儲時， a56的起始地址分別為多少？ 答案；2024；2260、設(shè)有一個10階的對稱矩陣A[10][10]，采用壓縮存儲方式按行將矩陣中下三角部分的元素存入一維數(shù)組B[]中，A[0][0]存入B[0]中，則A[8][5]在B[]中位置為多少？答案：41、設(shè)二維數(shù)組A10*9的每個元素占7個字節(jié)，已知Loc=1500，A共占多少個字節(jié)？ A的終端結(jié)點 a98的起始地址為多少？ 答案：630；2123、設(shè)有一個10階的對稱矩陣A[20][20]，采用壓縮存儲方式按行將矩陣中下三角部分的元素存入一維數(shù)組 B[] 中，A[0][0] 存入B[0]中，則A[14][12]在B[]中位置為多少？2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)31/62答案：11712、設(shè)二維數(shù)組A6*7的每個元素占5個字節(jié)，已知Loc=1000，A共占多少個字節(jié)？A的終端結(jié)點a56的起始地址為多少？按行和按列優(yōu)先存儲時，a46的起始地址分別為多少？答案：210；1205；行：1170列：1200、設(shè)二維數(shù)組A12*9的每個元素占4個字節(jié)，已知Loc=2000，A共占多少個字節(jié)？ A的終端結(jié)點 a118的起始地址為多少？按行和按列優(yōu)先存儲時， a85的起始地址分別為多少？答案:432；2428；行：2268列：2220五、綜合題、給出下列二叉樹的前序序列、中序序列、后序序列。答案：前序：CABEFDHG中序：BAFECHDG后序：BFEAHGDC、假定用于通信的電文僅4個字母a，b，c，d,e組成，各個字母在電文中出現(xiàn)的頻率分別為7，6,5，2，4。試為這

5個字母設(shè)計

Huffman

樹且寫出對應的

Huffman

編碼。答案:a:10b:00c:01d:110e:111bca de、把下面的森林轉(zhuǎn)換為對應的二叉樹。2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)32/62AEHDGIKCJB搜索成功時的平均搜索長度為： ASLsucc=12、已知待排序記錄的關(guān)鍵字序列為{83，69，41，22，15，33，8，20}，要求：用歸并排序法按從小到大順序?qū)懗雒刻伺判虻慕Y(jié)果，直到排序結(jié)束；答案：8，15，20，22，33，41，69，83、設(shè)二叉樹t的中序序列為BADCE，后序序列為BDECA，請給出二叉樹的前序序列。要求：畫出這棵二叉樹： 寫出這棵二叉樹的前序遍歷序列。 (1)BED前序序列：ABCDE、假定用于通信的電文僅8個字母a，b，c，d，e，組成，各個字母在電文中出現(xiàn)的頻率分別為5，3，6，10，4。試為這5個字母設(shè)計 Huffman樹。答案：2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)33/62acdbe、把下面的二叉樹轉(zhuǎn)換為相應的森林。答案：bacefhdg16、已知一個圖的鄰接矩陣如下，請分別寫出從頂點V0出發(fā)按深度和廣度優(yōu)先遍歷時得到的頂點序列。01234567011000000100110001100001102010000013010000014001000015001000016000111107答案：深度遍歷： VO,V1,V3,V7,V4,V5,V2,V6廣度遍歷：V0,V1,V2,V3,V4,V5,V6,V7、已知散列函數(shù)為H(K)=Kmod6,健值序列為25，37，52，43，84，99，120，15，26，11采用拉鏈法處理沖突，試構(gòu)造開散列表，并計算查找 成功的平均查找長度。答案：開散列表省略，ASL=18、一個對象序列的排序碼為{46，79，56，38，40，84}，采用快速排序以位于最左位置的對象為基準而得到的第一次劃分結(jié)果為多少？答案：{40，38，46，56，79，84}2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)34/62、已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：A,B,C,D,E,F,G,H,I,JC,B,A,E,F,D,I,H,J,G

中序序列：后序序列：答案：后序序列：

CBFEIJHGDA、把下面的二叉樹轉(zhuǎn)換為對應的森林EHA答案：CBDGIAEFHIDGCB21 、已知無向圖 G的鄰接表如下，請畫出其所有的連通分量。答案： V3V1V2V5V422 、給出如圖所示的有向圖 G的鄰接矩陣的存儲結(jié)構(gòu)。、已知散列函數(shù)為H(K)=Kmod9,健值序列為19，14，25，01，68，28，84，27，56，12采用拉鏈法處理沖突，試構(gòu)造開散列表，并計算查找成功的平均查找長度。 答案：開散列表省略， ASL=、對于給定的一組鍵值：83，40，63，13，84，35，2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)35/6296，57，39，79，61，15，請給出采用起泡排序法對該序列作升序排序時的每一趟的結(jié)果。25 、已知某二叉樹的中序序序列為 ABCDEGFHI，后序序列為ACDBGIHFE，請給出二叉樹的前序序列。要求：畫出這棵二叉樹：寫出這棵二叉樹的前序遍歷序列。 答案：BFADG C先序序列：EBADCFGHI、把下面的二叉樹轉(zhuǎn)換為對應的森林。EEHIADCJBHGIK答案：AEHDGIKCBJ27 、假定用于通信的電文僅 4個字母a，b，c，d組成，各個字母在電文中出現(xiàn)的頻率分別為 7，5，2，4。試為這4個字母設(shè)計 Huffman樹。 答案：abcd2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)36/62、寫出有向圖的拓撲排序序列。答案：V3,V1,V4,V5,V2,V6V4 V5V3V1V2V629、已知散列函數(shù)為 H(K)=Kmod12,健值序列為 25，37，52，43，84，99，120，，26，11，70，82，采用拉鏈法處理沖突，試構(gòu)造開散列表，并計算查找成功的平均查找長度。答案：開散列表省略，ASL=19/1230 、已知待排序記錄的關(guān)鍵字序列為

{83

，69，41，22，15，33，8}

，

要求：用直接選擇排序法按從小到大順序?qū)懗雒刻伺判虻慕Y(jié)果，直到排序結(jié)束；答案：第一趟：8，69，41，22，15，33，83 第二趟：8，15，41，22，69，33，83 第三趟：8，15，22，41，69，33，83第四趟：8，15，22，33，69，41，83第五趟：8，15，22，33，41，69，83第六趟：8，15，22，33，41，69，83、把下面的樹轉(zhuǎn)換為對應的二叉樹答案：ABECDLKHIFJG2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)37/62、已知一棵樹二叉如下，請分別寫出按箭序、中序、后序和層次遍歷時得到的結(jié)點序列。AB CD E FG H前序： 中序： 后序： 層次：答案：前序： ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 層次：ABCDEFGH33 、已知權(quán)值W={8，6,2,15，7}，請構(gòu)造對應的 Huffman樹。 答案：871562、寫出如下有向圖的拓撲排序序列。V3V1V2V6V4V5答案：V1,V3,V4,V5,V2,V6、已知散列函數(shù)為H(K)=Kmod8,健值序列為25，37，52，43，84，99，120，15，26，11，采用拉鏈法處理沖突，試構(gòu)造開散列表，并計算查找成功的平均查找長度答案：開散列表省略，ASL=36、已知待排序記錄的關(guān)鍵字序列為{55，69，41，22，2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)38/6215，33，8，20}， 要求：用堆排序法找出最大的值，要求寫出排序過程；答案：69；過程略37 、已知一棵二叉樹的中序遍歷的結(jié)果為： ABCEFGHD，后序遍歷的結(jié)果為： ABFHGEDC請給出二叉樹的前序序列。要求：畫出這棵二叉樹：寫出這棵二叉樹的前序遍歷序列。 答案：CB A前序序列：CBADEGFHDEGFH38 、試畫出下面二叉試畫出下面二叉樹對應的二叉鏈表。。、假定用于通信的電文僅4個字母a，b，c，d,e組成，各個字母在電文中出現(xiàn)的頻率分別為3，2,4，6，5。試為這5個字母設(shè)計Huffman樹且寫出對應的Huffman編碼。cdeaba:110b:111c:00d:01e:1040 、已知一個圖的鄰接表如下，請寫出從頂點 C0出發(fā)按深度遍歷時得到的頂點序列。答案：C0—C1—C3—C4—C5—C22016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)39/62、已知散列函數(shù)為H(k)=kmod13，關(guān)鍵字序列為25、37、52、43、84、99、120、15、26、11、80、23，處理沖突的方法為線性探測法，散列表長度為13，試畫出該散列表。求出在等概率情況下的查找成功時的平均查找長度。 (2分)答案：哈希表：0123456789101112522615120431184809923372542、已知待排序記錄的關(guān)鍵字序列為{83，69，41，22，15，33，8，20}，要求：用堆排序法找出最小的值，要求寫出排序過程；、已知一棵二叉樹的中序和后序序列如下，求該二叉樹的高度和度為2、度為 1及度為 0的結(jié)點個數(shù)。 中序序列：c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a答案：度為2為：3度為1為：3度為0為：4、給定權(quán)值7，18，3，32，5，26，12，8，構(gòu)造相應的哈夫曼樹45 、已知一個圖的鄰接表如下，請寫出從頂點 C0出發(fā)2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)40/62按廣度遍歷時得到的頂點序列。答案：C0,C1,C2,C3,C4,C5、(該題2選1做)4BA27112F30710EDC1628對于上圖所示的無向圖，要求：按普里姆(prim)算法從頂點A出發(fā)求其最小生成樹，要求寫出求解的順序步驟。(2)按克魯斯卡爾(kruskal)算法求其最小生成樹，要求寫出求解的順序步驟。47 、設(shè)散列表的長度ｍ＝１３；散列函數(shù)為Ｈ＝Ｋ modm，給定的關(guān)鍵碼序列為 19，14，25，01，68，28，84，27，56，12，試畫出用線性探查法解決沖突時所構(gòu)造的散列表。并求出在等概率的情況下，這種方法的搜索成功時的平均搜索長度。0123456789101112搜索成功時的平均搜索長度為：ASLsucc=答案：012345678910111212140168282719845625解：H=19mod13=6H=14mod13=1H=25mod13=12H=01mod13=12016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)41/62不空，所以第一次沖突處理后的地址為H=mod13=2H=68mod13=3H=28mod13=2不空，所以第一次沖突處理后的地址為H=mod13=3[3]不空，所以第二次沖突處理后的地址為 H=mod13=4H=84mod13=6不空，所以第一次沖突處理后的地址為H=mod13=7H=27mod13=1不空，所以第一次沖突處理后的地址為H=mod13=2[2]不空，所以第二次沖突處理后的地址為 H=mod13=3[3]不空，所以第三次沖突處理后的地址為 H=mod13=4[4] 不空，所以第五次沖突處理后的地址為 H=mod13=5H=56mod13=4不空，所以第一次沖突處理后的地址為H=mod13=5[5]不空，所以第二次沖突處理后的地址為 H=mod13=6[6]不空，所以第二次沖突處理后的地址為 H=mod13=7[7] 不空，所以第二次沖突處理后的地址為 H=mod13=8H=12mod13=12不空，所以第一次沖突處理后的地址為H=mod13=0平均搜索長度 ASLsucc=、判斷下列兩序列是否為堆？如不是，按照建堆的思想把它調(diào)整為堆，并用圖表示建堆的過程。 ；。、某二叉樹的結(jié)點數(shù)據(jù)采用順序存儲表示如下：2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)42/62012345678910111213141516171819EAFDHCGIB試畫出此二叉樹的圖形表示。寫出結(jié)點D的雙親結(jié)點及左、右子女。將此二叉樹看作森林的二叉樹表示，試將它還原為森林。答案：(1)EHAB(2)A;C; Ф(3)CDGIAEFHIDGCB50 、已知權(quán)值 W={5,6,2,9,7} ，請構(gòu)造對應的Huffman樹。67952、給出如圖所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)。答案：、已知散列函數(shù)為H(k)=kmod13，關(guān)鍵字序列為25、37、52、43、84、99、120、15、26、、70、82，處理沖突的方法為線性探測法，散列表長度為13，2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)43/62試畫出該散列表。求出在等概率情況下的查找成功時的平均查找長度。 (2分)答案：哈希表：0 1 2 3 4 5 6 7 8 910 11 1252 26 15 120 43 11 84 70 99 82 37 25在等概率情況下查找成功的平均查找次數(shù)為：53、已知待排序記錄的關(guān)鍵字序列為{83，69，41，22，15，33，8}， 要求：用起泡排序法按從小到大順序?qū)懗雒刻伺判虻慕Y(jié)果，直到排序結(jié)束；參考答案：8369412215158694122152281541221533822221533833153384133869883初第第第第第第始一二三四五六關(guān)趟趟趟趟趟趟鍵排排排排排排字序序序序序序后后后后后后、已知一棵二叉樹的中序和前序序列如下，求該二叉2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)44/62樹的后序序列。中序序列：c，b，d，e，a，g，I，h，j，f 前序序列：a，b，c，d，e，f，g，h，I，j 后序序列：答案：后序：bedcfhjiga、樹中哪個結(jié)點為根結(jié)點？哪些結(jié)點為葉子結(jié)點？ 結(jié)點B的雙親為哪個結(jié)點？其子女為哪些結(jié)點？ 哪些結(jié)點為結(jié)點D的兄弟？哪些結(jié)點為結(jié)點 K的兄弟？ 結(jié)點A、C的度分別為多少？樹的度為多少？ 以結(jié)點 B為根的子樹的高度為多少？答案：A;E,G,H,I,C,J,K,L(2)A;E,F,G,H,I (3)B,C,L;J(4)4;0;4 (5)356 、設(shè)某密碼電文 a,b,c,d,e,f,h,i8 個字母組成，每個字母在電文中的出現(xiàn)頻率分別是 7，19，2，6，32，3，21，10，試為這8個字母設(shè)計相應的哈 夫曼編碼答 案 ：a:1110;b:00;c:11010;d:1100;e:10;f:11011;h:01;i:111157、設(shè)有一無向圖 G=(V,E),其中2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)45/62V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)} 。按上述順序輸入后，畫出其相應的鄰接表；在該鄰接表上，從頂點 4開始，寫出 DFS序列和BFS序列。58 、已知散列函數(shù)為 H(K)=Kmod7,健值序列為 19,01,23,14,55,68,11,82,36 ，采用拉鏈法處理沖突，試構(gòu)造開散列表，并計算查找成功的平均查找長度參考答案：開散列表省略， ASL=13/9、已知序列，請給出采用直接插入排序法對該序列作升序排序時的每一趟的結(jié)果六、程序填空題、p是指向待刪結(jié)點的前趨結(jié)點voiddelete_lklist(lklisthead,intI){p=find_lklist(head,I-1)if(p!=NULL)&&(( p –>nex)!=NULL)q=p –>next;p –>next=( q –>next); free(q);

{

}elseerror(

“不存在這樣的結(jié)點”

)

；

}、單鏈表的插入操作2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)46/62voidinsert_lklist(lklisthead,datatypex,intI){p=find_lklist(head,I-1) if(p=NULL)error( “不存在這樣的結(jié)點”）s=(malloc )(size);s –>data=(x);s – >next = p ––>next=(s); }}

else>next;

{

p、順序表的插入操作#definemaxsize 100typedefintDataType;DataTypedata[maxsize];

typedefstruc{int last;

}Sqlist;VoidInsert_sqlist(SqlistL ，DataTypex，intI){ if (==( maxsize )) error( “表滿”）；if(I(+1))error( “非法位置”）； for(j=L. last;j>=I;j--)[j]=([j-1]); [I-1]=x;L.last=(+1);}4 、查找第一個與給定值 X相同的表結(jié)點的序號。Pointerfind_lklist(lklisthead,intI){p=(head);j=0;2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)47/62while(p – >next!=NULL)&&( ( p –data) !=x) {p=(p –>next);j++; }ifp –>data==xreturn(p); elsereturn(0);}

>、順序表上的查找算法。intSearch_Seq(SSTableST,KeyTypekey){ 。[( 0)].key=key; // “哨兵”for(i=;[i].key!=key;( i--));從后往前找 returni; // 找不到時，i 為0}//

//Search_Seq6 、INITIATE() 的功能是建立一個空表。請在 ________處填上正確的語句。 lklist initiate_lklist()/*建立一個空表*/{__ t=malloc(size)_; ___t –>next=NULL _;return(t);}、以下為求單鏈表表長的運算，分析算法，請在________ 處 填 上length_lklist(lklisthead)

正 確 的

語/*

句 。求表 head

的長度

int*/{p=head;j=0;while(p->next!=NULL)

{__

p=p

–

>next

_;2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)48/62j++;}return(j);

/*

回傳表長

*/}8 、以下對

r[h],r[h+1],??r[p]

子序列進行一趟快速排序。請分析算法，并在 ________上填充適當?shù)恼Z句。intquickpass(listr,inth,intp){i=h;j=p;x=r[i];/*準 */ while(i{ (r[i]=r[j] );i++;/*

置初值，以第一個記錄的鍵值為標{while((r[j].key>=)&&(i將 r[j].kiy if(ir[i]=x;return(i);/*

一趟快速

排序結(jié)束，將

x移至正確的位置*/

}9、在一個單鏈表中的指結(jié)點，可執(zhí)行如下操作。

P所指的結(jié)點之前插入一個S->next=(p->next)

S所;p->next=s;t=p->data;p->data=

(s->data)

;s->data=

(t)

;、以下算法在有序表R中用二分查找法查找鍵值等于K的元素，請分析程序，并在 ________上填充合適的語句。intbinsearch(sqtableR,keytypeK){low=1;hig=;/* 置查找區(qū)間初值。 low,hig 分別標記查找區(qū)間的下、上界*/ while(low {mid=；for(j=I+1;j>=;j++)2016全新精品資料-全新公文范文-全程指導寫作 –獨家原創(chuàng)49/62[j-2]=([j-1]);L.last=(L.last-1);}數(shù)據(jù)結(jié)構(gòu)課程學位考試試題判斷題：判斷下列各小題敘述的正誤。對，在題號后的括號內(nèi)填入“√ ”；錯，在題號后填入“ ×”。1、數(shù)據(jù)的最小單位是數(shù)據(jù)項。 ??????????.( √)、多重表文件中主索引為非稠密索引，次索引為稠密索引。???.(√)、通常數(shù)據(jù)結(jié)構(gòu)在計算機中有四種不同的表示方法分為順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、索引存