數(shù)據(jù)結(jié)構(gòu)c語言版期末考試

1、數(shù)據(jù)結(jié)構(gòu)與算法復習題一、選擇題。1 .在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為C。A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C,線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2 .數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指A。A.數(shù)據(jù)的存儲結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)D.數(shù)據(jù)元素之問的關(guān)系3 .在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)A.邏輯B.存儲C.邏輯和存儲D.物理4 .在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲CA.數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲方法5 .在決定選取何種存儲結(jié)構(gòu)時，一般不考慮A。A.各結(jié)點的值如何B.結(jié)點個數(shù)的多

2、少C.對數(shù)據(jù)有哪些運算D.所用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方便。6 .以下說法正確的是D。A.數(shù)據(jù)項是數(shù)據(jù)的基本單位B.數(shù)據(jù)元素是數(shù)據(jù)的最小單位C.數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合D.一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7 .算法分析的目的是C,算法分析的兩個主要方面是A。(1) A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進C.分析算法的易讀性和文檔性(2) A.空間復雜度和時間復雜度B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復雜性和程序復雜性8 .下面程序段的時間復雜度是O(n2)。s=0;for(I=0;in;i+)for(j=0;jn;j+)s+

3、=Bij;sum=s;9 .下面程序段的時間復雜度是O(n*m)。for(i=0;in;i+)for(j=0;jm;j+)Aij=0;10 .下面程序段的時間復雜度是O(log3n)i=0；while(inext=NULLC.head-next=headDhead!=NULL15.帶頭結(jié)點的單鏈表head為空的判定條件是B。A.head=NULLBhead-next=NULLC.head-next=headDhead!=NULL16 .若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用D存儲方式最節(jié)省運算時間。A.單鏈表B.給出表頭指針的單循環(huán)鏈表C.雙鏈表D.帶頭結(jié)

4、點的雙循環(huán)鏈表17 .需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是B。A.單鏈表B.靜態(tài)鏈表C.線性鏈表D.順序存儲結(jié)構(gòu)18 .非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)滿足CA.p-next=NULLB,p=NULLC.p-next=headD.p=head19 .在循環(huán)雙鏈表的p所指的結(jié)點之前插入s所指結(jié)點的操作是DA.p-prior=s;s-next=p;p-prior-next=s;s-prior=p-priorB.p-prior=sC.s-next=pD.s-next=p;p-prior-next=s;s-prior=p-prior;s-prior=p-pri

5、or；s-next=p;s-prior=p-prior;p-prior=s;p-prior-next=s;p-prior-next=s;p-prior=s20 .如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用D存儲方式最節(jié)省時間。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表21 .在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是B_oA.O(1)B.O(n)C.O(n2)D.O(nlog2n)22 .在一個長度為n(n1)的單鏈表上，設有頭和尾兩個指針，執(zhí)行B操作與鏈表的長度有關(guān)。A.刪除單鏈表中的第一個元素B.刪除單鏈表中的最后一個元素C.在單鏈表第一個元素前插入一

6、個新元素D.在單鏈表最后一個元素后插入一個新元素23.與單鏈表相比，雙鏈表的優(yōu)點之一是_D。A.插入、刪除操作更簡單B.可以進行隨機訪問C.可以省略表頭指針或表尾指針D.順序訪問相鄰結(jié)點更靈活24.如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用B。A,只有表頭指針沒有表尾指針的循環(huán)單鏈表B.只有表尾指針沒有表頭指針的循環(huán)單鏈表C.非循環(huán)雙鏈表D.循環(huán)雙鏈表25 .在長度為n的順序表的第i個位置上插入一個元素(1&in+1),元素的移動次數(shù)為：A。A.n-i+1B.n-iC.iD.i-126 .對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)

7、為C。A.順序表B.用頭指針表示的循環(huán)單鏈表C.用尾指針表示的循環(huán)單鏈表D.單鏈表27 .下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？C。A插入運算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲表示C存儲密度大D刪除運算方便28 .下面關(guān)于線性表的敘述中，錯誤的是哪一個？B。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元D線性表采用鏈式存儲，便于進行插入和刪除操作。29 .線性表是具有n個_B的有限序列。A.字符B.數(shù)據(jù)元素C.數(shù)據(jù)項D.表元素30 .在n個結(jié)點的線性表的數(shù)組實現(xiàn)中，算法的時間復雜度是O(1)的操作是A。

8、A.訪問第i(1=i=n)個結(jié)點和求第i個結(jié)點的直接前驅(qū)(1i=n)B.在第i(1=i=n)個結(jié)點后插入一個新結(jié)點C.刪除第i(1=inext=s;s-next=p-nextB.s-next=p-next；p-next=s;C.p-next=s;p-next=s-nextD.p-next=s-next；p-next=s36 .線性表的順序存儲結(jié)構(gòu)是一種AoA.隨機存取的存儲結(jié)構(gòu)B.順序存取的存儲結(jié)構(gòu)C.索引存取的存儲結(jié)構(gòu)D.Hash存取的存儲結(jié)構(gòu)37 .棧的特點是工,隊列的特點是A。A.先進先出B.先進后出38 .棧和隊列的共同點是C。A.都是先進后出B.都是先進先出C.只允許在端點處插入和刪

9、除元素D.沒有共同點39 .一個棧的進棧序列是a,b,c,d,e,則棧的不可能的輸出序列是CA.edcbaB.decbaC.dceabD.abcde40 .設有一個棧，元素依次進棧的順序為A、BGDE。下列C是不可能的出棧序列。A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.E,D,C,B,A41 .以下B不是隊列的基本運算？A.從隊尾插入一個新元素B.從隊列中刪除第i個元素C.判斷一個隊列是否為空D.讀取隊頭元素的值42 .若已知一個棧的進棧序列是1,2,3,n,其輸出序列為pl,p2,p3,pn,若p1=n,貝Upi為C。A.iB.n-iC.n-i+1D,不確定43.

10、判定一個順序棧st（最多元素為MaxSize）為空的條件是BA.st-top!=-1B.st-top=-1C.st-top!=MaxSizeD.st-top=MaxSize44.判定一個順序棧st（最多元素為MaxSize）為滿的條件是_D。A.st-top!=-1B.st-top=-1C. st-top!=MaxSizeD.st-top=MaxSize45 .一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是B。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,146 .判定一個循環(huán)隊列qu（最多元素為MaxSize）為空的條件是C。A.qu-rear-qu-fron

11、t=MaxSizeB.qu-rear-qu-front-1=MaxSizeC.qu-rear=qu-frontD.qu-rear=qu-front-147 .在循環(huán)隊列中，若front與rear分別表示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條件是_C。A.front=rear+1B.rear=front+1C.front=rearD. front=048.向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針s所指的結(jié)點時，應執(zhí)行D操作。A.h-next=s;B.s-next=h;C.s-next=h;h=s;D.s-next=h-next;h-next=s;49 .輸入序列為ABC可以變?yōu)镃BA

12、寸，經(jīng)過的棧操作為B。A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop50 .若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1m,top1、top2分別代表第1和第2個棧的棧頂，棧1的底在V1,棧2的底在Vm,則棧滿的條件是B。A.|top2-top1|=0B.top1+1=top2C.top1+top2=mD.top1=top251 .設計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用D數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存

13、儲結(jié)構(gòu)B.隊列C.線性表的鏈式存儲結(jié)構(gòu)D.棧52 .允許對隊列進行的操作有_D。A.對隊列中的元素排序B.取出最近進隊的元素C.在隊頭元素之前插入元素D.刪除隊頭元素53 .對于循環(huán)隊列D0A.無法判斷隊列是否為空B.無法判斷隊列是否為滿C.隊列不可能滿D.以上說法都不對54 .若用一個大小為6的數(shù)值來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3,當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為BoA.1和5B.2和4C.4和2D.5和155 .隊列的“先進先出”特性是指DoA.最早插入隊列中的元素總是最后被刪除B.當同時進行插入、刪除操作時，總是插入操作優(yōu)

14、先C.每當有刪除操作時，總是要先做一次插入操作D.每次從隊列中刪除的總是最早插入的元素56 .和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是A。A.通常不會出現(xiàn)棧滿的情況B.通常不會出現(xiàn)?？盏那闆rC.插入操作更容易實現(xiàn)D.刪除操作更容易實現(xiàn)其頭指針指向隊頭結(jié)點，尾指針指向隊尾57 .用不帶頭結(jié)點的單鏈表存儲隊列，結(jié)點，則在進行出隊操作時c。.僅修改隊尾指針.隊頭、隊尾指針都要修改A.僅修改隊頭指針BC.隊頭、隊尾指針都可能要修改D58 .若用S=software,其子用的數(shù)目是A8B.37C.3659 .用的長度是指BA.用中所含不同字母的個數(shù)C.用中所含不同字符的個數(shù)用中所含字符的個數(shù)用中所含非空

15、格字符的個數(shù)60 .用是一種特殊的線性表，其特殊性體現(xiàn)在BA.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈式存儲D.數(shù)據(jù)元素可以是多個字符61 .設有兩個用p和q,求q在p中首次出現(xiàn)的位置的運算稱為BA.連接B.模式匹配C.求子用D.求用長62 .數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8,列下標j從1到10,從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A85的起始地址為C0A.SA+141B,SA+144C.SA+222D.SA+22563 .數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8,列下標j從1到10,從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元

16、素A58的起始地址為C0A.SA+141B,SA+180C.SA+222D.SA+22564 .若聲明一個浮點數(shù)數(shù)組如下：froataverage=newfloat30;假設該數(shù)組的內(nèi)存起始位置為200,average15的內(nèi)存地址是C。A.214B,215C.260D.25665 .設二維數(shù)組A1,m,1,n按行存儲在數(shù)組B中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標為A。A.n*(i-1)+jB.n*(i-1)+j-1C,i*(j-1)D.j*m+i-166 .有一個100X90的稀疏矩陣，非0元素有10,設每個整型數(shù)占2個字節(jié),則用三元組表示該矩陣時，所需的字節(jié)數(shù)是B。A.20B.66

17、C.18000D.3367 .數(shù)組A0,4,-1,-3,5,7中含有的元素個數(shù)是A。A.55B.45C.36D.1668 .對矩陣進行壓縮存儲是為了D。A.方便運算B.方便存儲C.提高運算速度D.減少存儲空間69 .設有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，a-為第一個元素，其存儲地址為1,每個元素占1個地址空間，則a8,5的地址為B。A.13B.33C.18D.4070 .稀疏矩陣一般的壓縮存儲方式有兩種，即C。A,二維數(shù)組和三維數(shù)組C.三元組和十字鏈表三元組和散列散列和十字鏈表71.樹最適合用來表示A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù).無序數(shù)據(jù)元素D.元素

18、之間無聯(lián)系的數(shù)據(jù)72 .深度為5的二叉樹至多有C個結(jié)點A.16B.32C.31C.1073 .對一個滿二叉樹，m個葉子，n個結(jié)點，深度為h,則-DA.n=h+mBh+m=2nCm=h-1Dn=2h-174 .任何一棵二叉樹的葉子結(jié)點在前序、中序和后序遍歷序列中的相對次序A。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對75 .在線索化樹中，每個結(jié)點必須設置一個標志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若0標識樹結(jié)構(gòu)信息，1標識線索，對應葉結(jié)點的左右鏈域，應標識為D。A.00B.01C.10D.1176 .在下述論述中，正確的是D0只有一個結(jié)點的二叉樹的度為0;二叉樹的度為

19、2;二叉樹的左右子樹可任意交換；深度為K的順序二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。A.B.C.D.77 .設森林F對應的二叉樹為B,它有m個結(jié)點，B的根為p,p的右子樹的結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點的個數(shù)是一A。A.m-nB.m-n-1C.n+1D,不能確定78 .若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點的個數(shù)是B。A.9B.11C.15D.不能確定79 .具有10個葉子結(jié)點的二叉樹中有B個度為2的結(jié)點A.8B.9C.10D.1180 .在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的C倍A.1/2B1C2D481 .在一個有向圖中，所有頂點的入度

20、之和等于所有頂點的出度之和的B倍A.1/2B1C2D482 .某二叉樹結(jié)點的中序序列為ABCDEFG后序序列為BDCAFGE則其左子樹中結(jié)點數(shù)目為：CA3B.2C.4D.583 .已知一算術(shù)表達式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為D0A.-A+B*C/DEB.-A+B*CD/EC+*ABC/DED.+A*BC/DE84 .已知一個圖，如圖所示，若從頂點a出發(fā)按深度搜索法進行遍歷，則可能得到的一種頂點序列為D;按廣度搜索法進行遍歷，則可能得到的一種頂點序列為A;A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,d,D.a,e,d,

21、f,c,bA.a,b,c,e,d,fB.a,b,c,e,f,C.a,e,b,c,f,d,D.a,c,f,d,e,85 .采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的AA.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷86 .采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的DA.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷87 .具有n個結(jié)點的連通圖至少有A條邊。A.n-1B.nC.n(n-1)/2D.2n88 .廣義表(a),a)的表頭是_,表尾是_C。A.aB()C(a)D(a)89 .廣義表(a)的表頭是C,表尾是B。A.aB()C(a)D(a)90 .順序查找法適合于存儲結(jié)構(gòu)為B的

22、線性表。A散列存儲B順序存儲或鏈式存儲C壓縮存儲D索引存儲91 .對線性表進行折半查找時，要求線性表必須B。A以順序方式存儲B以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列C以鏈式方式存儲D以鏈式方式存儲，且結(jié)點按關(guān)鍵字有序排列92.采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為D。2n)AO(n2)BO(nlog2n)CO(n)DO(log93 .有一個有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當折半查找值為82的結(jié)點時，C次比較后查找成功。A.11B5C4D894 .二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右

23、孩子的值。這種說法B0A正確B錯誤95 .下面關(guān)于B樹和8刑的敘述中，不正確的結(jié)論是A。AB樹和B刑都能有效的支持順序查找BB樹和B+M都能有效的支持隨機查找CB樹和B+W都是平衡的多叉樹DB樹和B+M都可用于文件索引結(jié)構(gòu)96 .以下說法錯誤的是B。A.散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址B.散列表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含指針。C.負載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度。D.散列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處理沖突的方法。97.查找效率最高的二叉排序樹是_C。A.所有結(jié)點的左子樹都為空的二叉排序樹。B.所有結(jié)點的右子樹都為空的二

24、叉排序樹。C.平衡二叉樹。D.沒有左子樹的二叉排序樹。98 .排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為C0A.希爾排序B冒泡排序C插入排序選擇排序99 .在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是D_。ATll爾排序B.冒泡排序C,直接插入排序D,直接選擇排序100 .堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個堆。A.94,31,53,23,16,72B.94,53,31,72,16,23C.16,53,23,94,31,72D.16,31,23,94,53,72101 .堆排序是一種B排序。A.插

25、入B.選擇C.交換D.歸并102 .D在鏈表中進行操作比在順序表中進行操作效率高。A.順序查找B.折半查找C.分塊查找D.插入103 .直接選擇排序的時間復雜度為D。(n為元素個數(shù))A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)二、填空題。1 .數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型,樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu)。2 .數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。3 .在線性結(jié)構(gòu)中，第一個結(jié)點沒有前驅(qū)結(jié)點、其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點沒位后續(xù)結(jié)點，其余每個結(jié)點有且只有一個后續(xù)結(jié)點04 .線性結(jié)構(gòu)中元素之間存在一對一關(guān)系、樹

26、形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。5 .在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)結(jié)點、其余每個結(jié)點有且只有二個前驅(qū)結(jié)點；葉子結(jié)點沒有后續(xù)結(jié)點、其余每個結(jié)點的后續(xù)結(jié)點可以任意多個。6 .數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是順序、鏈式、索引和散列在儲。7 .衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時間復雜度與空間復雜度8 .評估一個算法的優(yōu)劣，通常從時間復雜度和空間復雜度兩個方面考察。9 .算法的5個重要特性是有窮性、確定性、可行性、輸入和輸出。10 .在一個長度為n的順序表中刪除第i個元素時，需向前移動n-i-1個元素。11 .在單鏈表中，要刪除某一指定的結(jié)點，必須找到該結(jié)點

27、的前驅(qū)結(jié)點。12 .在雙鏈表中，每個結(jié)點有兩個指針域，一個指向前驅(qū)結(jié)點,另一個指向后繼結(jié)點。13 .在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動n個數(shù)據(jù)元素,移動數(shù)據(jù)元素的個數(shù)與位置有關(guān)。14 .當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應采用順序存儲結(jié)構(gòu)。15 .根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成單鏈表和雙鏈表。16 .順序存儲結(jié)構(gòu)是通過下標表示元素之間的關(guān)系的；鏈式存儲結(jié)構(gòu)是通過指針表示元素之間的關(guān)系的。17 .帶頭結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是L-next-next=L。18 .棧是限定僅在表

28、尾進行插入或刪除操作的線性表,其運算遵循后進先出的原則。19 .空用是零個字符的一,其長度等于零?？瞻子檬怯梢粋€或多個空格字符組成的年,其長度等于其包含的空格個數(shù)。20 .組成用的數(shù)據(jù)元素只能是單個字符。21 .一個字符串中任意個連續(xù)字符構(gòu)成的部分稱為該串的子串。22 .子用“str”在主用datastructure”中的位置是5。23 .二維數(shù)組M的每個元素是6個字符組成的用，行下標i的范圍從0到8,列下標j的范圍從1到10,則存放M至少需要540個字節(jié):M的第8列和第5行共占共8個字節(jié)。24 .稀疏矩陣一般的壓縮存儲方法有兩種，即三元組表和十字鏈表。25 .廣義表(a),(b),c),(d

29、)的長度是/,深度是4。26 .在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0,度為2的結(jié)點的個數(shù)為n2,則有n0=n2+1。27 .在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為n+1。28 .一棵有n個葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點。29 .深度為5的二叉樹至多有W個結(jié)點。30 .若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點個數(shù)為69。31 .某二叉樹的前序遍歷序列是abdgcefh,中序序列是dgbaechf,其后序序列為gdbehfca。32 .線索二叉樹的左線索指向其遍歷序列中的前驅(qū),右線索指向其遍歷序列中的后繼。33 .在各種查找方法中，平均查找長度與結(jié)點個數(shù)

30、n無關(guān)的查找方法是散列查找法。34 .在分塊索引查找方法中，首先查找索引表，然后查找相應的35 .一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列、構(gòu)造樹的過程即為對無序序列進行排序的過程。36 .具有10個頂點的無向圖，邊的總數(shù)最多為45037 .已知圖G的鄰接表如圖所示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為_v1v2v3v6v5v4一具從頂點v1出發(fā)的廣度優(yōu)先搜索序列為一v1v2v5v4v3v6一。38 .索引是為了加快檢索速度而引進的一種數(shù)據(jù)結(jié)構(gòu)。一個索引隸屬于某個數(shù)據(jù)記錄集，它由若干索引項組成，索引項的結(jié)構(gòu)為關(guān)鍵字和關(guān)鍵字對應記錄的39 .Prim算法生成一個最小生成樹每一步選

31、擇都要滿足邊的總數(shù)不超過n-1,當前選擇的邊的權(quán)值是候選邊中最小的，選中的邊加入樹中不產(chǎn)生回路.項原則。40 .在一棵m階B樹中，除根結(jié)點外，每個結(jié)點最多有m棵子樹，最少有m/2棵子樹。三、判斷題。1 .在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何。（V）2 .抽象數(shù)據(jù)類型（ADT包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現(xiàn)。（，）3 .抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關(guān)。（，）4 .順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（X）5 .線性表采用鏈式存儲結(jié)構(gòu)時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（X

32、）6 .對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（x）7 .順序存儲方式只能用于存儲線性結(jié)構(gòu)。（X）8 .集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。（x）9 .線性表中每個元素都有一個直接前驅(qū)和一個直接后繼。（x）10 .線性表就是順序存儲的表。（x）11 .取線性表的第i個元素的時間同i的大小有關(guān)。（x）12 .循環(huán)鏈表不是線性表。（x）13 .鏈表是采用鏈式存儲結(jié)構(gòu)的線性表，進行插入、刪除操作時，在鏈表中比在順序表中效率高。（V）14 .雙向鏈表可隨機訪問任一結(jié)點。（X）15 .在單鏈表中，給定任一結(jié)點的地址p,則可用下述語句將新結(jié)點s插入結(jié)點p的后面：p-next=s;s-next

33、=p-next;（x）16 .隊列是一種插入和刪除操作分別在表的兩端進行的線性表，是一種先進后出的結(jié)構(gòu)。（X）17 .用是一種特殊的線性表，其特殊性體現(xiàn)在可以順序存儲。（x）18 .長度為1的用等價于一個字符型常量。（X）19 .空用和空白用是相同的。（X）20 .數(shù)組元素的下標值越大，存取時間越長。（X）21 .用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。（，）22 .一個廣義表的表頭總是一個廣義表。（X23 .一個廣義表的表尾總是一個廣義表。（V）24 .廣義表（a）,b）,c）25 .二叉樹的后序遍歷序列中,26 .度為

34、2的有序樹是二叉樹27 .二叉樹的前序遍歷序列中,的表頭（a）,b）,表尾是（c）。任意一個結(jié)點均處在其孩子結(jié)點的后面（X）任意一個結(jié)點均處在其孩子結(jié)點的前面28 .用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點。（X）29 .若已知一棵二叉樹的前序遍歷序列和后序遍歷序列，則可以恢復該二叉樹（x）30 .在哈夫曼樹中，權(quán)值最小的結(jié)點離根結(jié)點最近。（X）31 .強連通圖的各頂點間均可達。（V）32 .對于任意一個圖，從它的某個結(jié)點進行一次深度或廣度優(yōu)先遍歷可以訪問到該圖的每個頂點。（x）33 .在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，稱這種

35、排序為穩(wěn)定排序。（V）34 .在平衡二叉樹中，任意結(jié)點左右子樹的高度差（絕對值）不超過1。（V）35 .拓撲排序是按AOER中每個結(jié)點事件的最早發(fā)生時間對結(jié)點進行排序。（X）36 .冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)。（X）37 .對線性表進行折半查找時，要求線性表必須以鏈式方式存儲，且結(jié)點按關(guān)鍵字有序排列。（X）38 .散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址。（，）39 .二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。（X）40 .具有n個結(jié)點的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的。（V）41 .直接選擇排序算法

36、在最好情況下的時間復雜度為O（n）。（X）四、應用簡答題1 .有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們分別對應的邏輯圖形表示，并指出它們分別屬于何種結(jié)構(gòu)。(1) A=D,R,其中：D=a,b,c,d,e,f,g,h,R=r,r=,(2) B=D,R,其中：D=a,b,c,d,e,f,g,h,R=r,r=,(3) C=D,R,其中：D=1,2,3,4,5,6,R=r,r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)2 .簡述順序表和鏈表存儲方式的特點。答：順序表的優(yōu)點是可以隨機訪問數(shù)據(jù)元素，缺點是大小固定，不利于增減結(jié)點（增減結(jié)點操作需要移動元

37、素）。鏈表的優(yōu)點是采用指針方式增減結(jié)點，非常方便（只需改變指針指向，不移動結(jié)點）。其缺點是不能進行隨機訪問，只能順序訪問。另外，每個結(jié)點上增加指針域，造出額外存儲空間增大。3 .對鏈表設置頭結(jié)點的作用是什么？（至少說出兩條好處）答：其好處有：（1）對帶頭結(jié)點的鏈表，在表的任何結(jié)點之前插入結(jié)點或刪除表中任何結(jié)點，所要做的都是修改前一個結(jié)點的指針域，因為任何元素結(jié)點都有前驅(qū)結(jié)點（若鏈表沒有頭結(jié)點，則首元素結(jié)點沒有前驅(qū)結(jié)點，在其前插入結(jié)點和刪除該結(jié)點時操作復雜些）。（2）對帶頭結(jié)點的鏈表，表頭指針是指向頭結(jié)點的非空指針，因此空表與非空表的處理是一樣的。4 .對于一個棧，給出輸入項A,B,C。如果輸入

38、項序列由A,B,C組成，試給出全部可能的輸出序列。5 .設有4個元素1、2、3、4依次進棧，而棧的操作可隨時進行（進出?？扇我饨诲e進行，但要保證進棧次序不破壞1、2、3、4的相對次序），請寫出所有不可能的出棧次序和所有可能的出棧次序。6 .現(xiàn)有稀疏矩陣A如圖所示，要求畫出三元組表示法和十字鏈表表示法:1500220-15013300000091000028000-6000000000007,設4維數(shù)組的4個下標的范圍分別為-1,0,1,2,1,3,卜2,-1,請分別按行序和列序列出各元素。8 .有一份電文中共使用5個字符：a,b,c,d,e,它們出現(xiàn)的頻率依次為4,7,5,2,9,試畫出對應的

39、哈夫曼樹（請按左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的次序構(gòu)造），并求出每個字符的哈夫曼編碼。9 .有如圖所示的二叉樹，回答如下問題。（1）寫出該樹的中序遍歷序列；（2）寫出該樹的先序遍歷序列；（3）寫出該樹的后序遍歷序列；(4)畫出該二叉樹的中序線索二叉樹；(5)畫出該二叉樹的后序線索二叉樹；(6)畫出該二叉樹對應的森林；(1)其巾序遍歷序列為(dgbaeduf)(2分)(2)其先序遍歷序列為(Abdgcefhi先(2分)(3)其后序遍歷序列為(gdbeihfca)(2分以(5J陵二叉樹的后序線索二叉悔表為G分)(6)該二叉樹對應的森林是(3分)10 .已知一棵樹邊的集合為,畫出這棵樹。(

40、4)畫出把此二叉樹還原成森林的圖11.假設二叉樹采用順序存儲結(jié)構(gòu)，如圖所示。(1)畫出二叉樹表示；(2)寫出先序遍歷、中序遍歷和后序遍歷的結(jié)果；(3)寫出結(jié)點值c的雙親結(jié)點，其左、右孩子；(1):1234567891011121314151617181920eafdgcjhib（2）寫出先序遍歷，巾序遍歷和后序遍歷的結(jié)果,解:先序遍歷序列；eadcbjfghi（3分）中序遍歷序列：abcdjefligi（3分）后序遍歷序列；bcjdahigfe（3分）（3）寫出結(jié)點值c的雙親結(jié)點，其左右孩子；（3分）解，c的雙親結(jié)點為d,左孩子為b,沒有右孩子。（4）畫出把此二叉樹還原成森林的圖（4分）12.

41、已知一棵二叉樹的中序序列為cbedahgijf,后序序列為cedbhjigfa,畫出該二叉樹的先序線索二叉樹。NULL后序：ce&bhjfa先序:abcdefghij已知一棵二叉樹的中序序列為cbedahgijf,后序序列為cedbhjigfa,畫出該二叉樹的先序線索二叉樹。中序：cbed.1ahg_ijfQ13.某二叉樹的先序遍歷序列是abdgcefh,中序遍歷序列是dgbaechf,給出其后序遍歷序列。后序遍歷序列：gdbehfca14.將下圖所示森林轉(zhuǎn)換成為二叉樹，并寫出轉(zhuǎn)化后二叉樹中序遍歷結(jié)果。DEF15 .有一份電文中共使用8個字符：a、b、c、d、e、f、o、i,它們的出現(xiàn)頻率依次

42、為10,20,15,32,40,60,26,18。試畫出對應的哈夫曼樹（請按左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的次序構(gòu)造），并求出每個字符的哈夫曼編碼。16 .已知某系統(tǒng)在通信聯(lián)絡中只可能出現(xiàn)A,B,C,D,E,F,G,H八種字符，其頻率為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11試設計哈夫曼編碼。17 .對有五個頂點v1,v2,v3,v4,v5的圖的鄰接矩陣如圖所示，解答下歹問題:(1)畫出邏輯圖。(2)畫出該邏輯結(jié)構(gòu)的鄰接表。(3)基于鄰接矩陣寫出圖的深度、廣度優(yōu)先遍歷序列。一010030O01080oOCOod60020cd010QO0cOO0O

43、O500飛1QG30x1T工X(EH工I60h20ocxL0ocx?3?IxIh36hICL3M土瀑駕百茨一口分7iVI3。S土FV4)門；耳三手一。n=三發(fā)三衣豆立光逵定直立先速千個臬沃境峰無兄VIVSV41V5E美K隼一)一名tt王毛5：vmsam吉某萬庭一；18 .如圖所示，解答如下問題：(1)寫出從定點A出發(fā)，深度和廣度優(yōu)先遍歷方法遍歷該圖的頂點序列。(2)根據(jù)普里姆算法和克魯斯卡爾算法，分別求它的最小生成樹，要求給出構(gòu)造過程。19 .給出如圖所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)。并在給定的鄰接表的基礎上，指出從頂點1出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列。20 .使用普里姆算法

44、構(gòu)造出如圖所示的圖G的一棵最小生成樹圖一個無向圖G21 .使用克魯斯卡爾算法構(gòu)造出如圖所示的圖G的一棵最小生成樹圖一個無向圖G請畫出該二叉樹22 .設有一棵二叉樹，它的中序和后序遍歷結(jié)果如下,中序：143562后序：46532123.設一棵順序二叉樹具有10個結(jié)點，請計算其中葉子結(jié)點的數(shù)目。24 .設如圖所示二叉樹是由某棵樹轉(zhuǎn)化而來，請畫出其對應的原樹25 .設有如圖所示的一棵樹，請將其轉(zhuǎn)化為二叉樹26.下表給出了某工程各工序之間的優(yōu)先關(guān)系和各工序所需時間。解答下列問題:(1)畫出相應的AOE圖；(2)給出各事件的最早發(fā)生時間和最晚發(fā)生時間；(3)找出關(guān)鍵路徑，并指明完成該工程所需最短時間；(

45、4)若把AOEH視為AOVW,給出具一個拓撲序列的例子。工序代號ABCDEFGHIJKLMM時間151050815409015806015302040先驅(qū)工作一一A,BBC,DBEG,IEIF,Ih,j,k|LGA。川僅是接續(xù)順序關(guān)系，不存在儂賴關(guān)系口頂點代入霞中頂點1代表工程開始事件，頂點11答案:n7g101112130038039542544542039542544542527 .某不帶權(quán)有向圖如下所示。給出其鄰接矩陣和鄰接表表示28 .求如下AOE圖的關(guān)鍵路徑，要求給出求解過程29 .有一組數(shù)據(jù)，內(nèi)容如下：8,15,38,57,68,88,98,108,129,234,256試用二分查找法查找68和222,要求先畫出二叉折半檢索樹，然后寫出查找過程。不一蛆蒙莞；$.15.3見5,朝.蕤-9的18.129.工三士條受芝半森茨士有二三三老老，介一-二與餐技大度.答，ASL=(1+2*2-3*4-4*4)11=3311=3(2于馬今發(fā)港對它的判百初6分30 .已知有序表為12,18,24,35,47,50,62,83,90,115,134,請畫出采用折半查找法對應的判斷樹。31 .設