數(shù)據(jù)結構c語言版期末考試復習試題

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

2、般不考慮_A一。A.各結點的值如何 B.結點個數(shù)的多少C.對數(shù)據(jù)有哪些運算 D.所用的編程語言實現(xiàn)這種結構是否方便。6 .以下說法正確的是 D。A.數(shù)據(jù)項是數(shù)據(jù)的基本單位B.數(shù)據(jù)元素是數(shù)據(jù)的最小單位C.數(shù)據(jù)結構是帶結構的數(shù)據(jù)項的集合D.一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結構8.下面程序段的時間復雜度是 O(n2)s=0;for(I=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;9 .下面程序段的時間復雜度是 O(n*m)for(i=0;in;i+)for(j=0;jm;j+)A皿=0;10 .下面程序段的時間復雜度是 O(log3n7.算法分析的目的是 C,算法分

3、析的兩個主要方面是 A。B.研究算法中的輸入和輸出的關系(1) A.找出數(shù)據(jù)結構的合理性C.分析算法的效率以求改進(2) A.空間復雜度和時間復雜度C.可讀性和文檔性C.分析算法的易讀性和文檔性B.正確性和簡明性D.數(shù)據(jù)復雜性和程序復雜性i=0;while(inext=NULL15 .帶頭結點的單鏈表 head 為空的判定條件是16 .若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則采用D 存儲方式最節(jié)省運算時間。A.單鏈表 B.給出表頭指針的單循環(huán)鏈表 C.雙鏈表 D.帶頭結點的雙循環(huán)鏈表17 .需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構是B。A.

4、單鏈表 B.靜態(tài)鏈表 C.線性鏈表 D.順序存儲結構18.非空的循環(huán)單鏈表 head 的尾結點（由 p 所指向）滿足 C。A.p-next=NULLB.p=NULLC.p-next=headD.p=head19.在循環(huán)雙鏈表的 p 所指的結點之前插入 s 所指結點的操作是一 D。A.p-prior=s;s-next=p;p-prior-next=s;s-prior=p-priorB.p-prior=s;p-prior-next=s;s-next=p;s-prior=p-priorC.head-next=headDhead!=NULLA.head=NULLBhead-next=NULLC.hea

5、d-next=headDhead!=NULLC. s-next=p;s-prior=p-prior;p-prior=s;p-prior-next=sD. s-next=p;s-prior=p-prior;p-prior-next=s;p-prior=s20 .如果最常用的操作是取第 i 個結點及其前驅，則采用 D 存儲方式最節(jié)省時間。A.單鏈表 B.雙鏈表 C.單循環(huán)鏈表 D.順序表21 .在一個具有 n 個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是 B_。A.O(1)B.O(n)C,O(n2)D.O(nlog2n)22 .在一個長度為 n(n1)的單鏈表上，設有頭和尾兩個指

6、針，執(zhí)行 B 操作與鏈表的長度有關。A.刪除單鏈表中的第一個元素B.刪除單鏈表中的最后一個元素C.在單鏈表第一個元素前插入一個新元素D.在單鏈表最后一個元素后插入一個新元素23.與單鏈表相比，雙鏈表的優(yōu)點之一是_DA.插入、刪除操作更簡單B.可以進行隨機訪問C.可以省略表頭指針或表尾指針D.順序訪問相鄰結點更靈活24 .如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用 B。A.只有表頭指針沒有表尾指針的循環(huán)單鏈表B.只有表尾指針沒有表頭指針的循環(huán)單鏈表C.非循環(huán)雙鏈表D.循環(huán)雙鏈表25.在長度為 n 的順序表的第 i 個位置上插入一個元素 （1wi0 酎

7、 1 元素的移動次數(shù)為：A。A.n-i+1B.n-iC.iD.i-126 .對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結構為C。A.順序表 B.用頭指針表示的循環(huán)單鏈表C.用尾指針表示的循環(huán)單鏈表 D.單鏈表27 .下述哪一條是順序存儲結構的優(yōu)點？C。A 插入運算方便 B 可方便地用于各種邏輯結構的存儲表示C 存儲密度大 D 刪除運算方便28 .下面關于線性表的敘述中，錯誤的是哪一個？B。A 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B 線性表采用順序存儲，便于進行插入和刪除操作。C 線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元D 線性表采用鏈式存儲，便于進行插入和刪除操作

8、29 .線性表是具有 n 個 B 的有限序列。A.字符 B.數(shù)據(jù)元素 C.數(shù)據(jù)項30 .在 n 個結點的線性表的數(shù)組實現(xiàn)中，算法的時間復雜度是 0(1)的操作是A。A.訪問第 i(1=i=n)個結點和求第 i 個結點的直接前驅(1i=n)B.在第 i(1=i=n)個結點后插入一個新結點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 .線性表的順序存儲結構是一種 A。A.隨機存取的存儲結構 B.順序存取的存儲結構C.索引存取的存儲結

9、構 D.Hash 存取的存儲結構37 .棧的特點是 B,隊列的特點是 A。A.先進先出 B.先進后出38 .棧和隊列的共同點是_C。A.都是先進后出 B.都是先進先出C.只允許在端點處插入和刪除元素 D.沒有共同點39 .一個棧的進棧序列是 a,b,c,d,e,則棧的不可能的輸出序列是 CA.edcbaB.decbaC.dceabD.abcde840 .設有一個棧，元素依次進棧的順序為 A、B、C、D、E。下列 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.從隊

10、列中刪除第 i 個元素C.判斷一個隊列是否為空 D.讀取隊頭元素的值42 .若已知一個棧的進棧序列是 1,2,3,n,其輸出序列為 pl,p2,p3,pn,若 p1=n,貝Upi 為 C。A.iB.n-iC.n-i+1D,不確定43.判定一個順序棧 st（最多元素為 MaxSize）為空的條件是 B。A.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=MaxSiz

11、e45 .一個隊列的入隊序列是 1,2,3,4,則隊列的輸出序列是 B。B.1,2,3,4A.4,3,2,146 .判定一個循環(huán)隊列 qu（最多元素為 MaxSize）為空的條件是 C。A.qu-rearqu-front=MaxSizeB.qu-rearqu-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 .向一個棧頂指

12、針為 h 的帶頭結點的鏈棧中插入指針 s 所指的結點時，應執(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)?CBA 時，經(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 個棧的棧

13、頂，棧 1 的底在 V1,棧 2 的底在 Vm,則棧滿的條10C.1,4,3,2D.3,2,4,1件是 B。A.|top2-top1|=0B.top1+1=top2C.top1+top2=mD.top1=top251 .設計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用 D 數(shù)據(jù)結構最佳。A.線性表的順序存儲結構 B.隊列 C.線性表的鏈式存儲結構D.棧54 .若用一個大小為 6 的數(shù)值來實現(xiàn)循環(huán)隊列，且當前 rear 和 front 的值分別為 0和 3,當從隊列中刪除一個元素，再加入兩個元素后，rear 和 front 的值分別為B。A.1 和 5B.2 和 4C.4 和 2D.5 和

14、 155 .隊列的“先進先出”特性是指_D11A.最早插入隊列中的元素總是最后被刪除B.當同時進行插入、刪除操作時，總是插入操作優(yōu)先52 .允許對隊列進行的操作有A.對隊列中的元素排序C.在隊頭元素之前插入元素53 .對于循環(huán)隊列 DA.無法判斷隊列是否為空C.隊列不可能滿D_。B.取出最近進隊的元素D.刪除隊頭元素B.無法判斷隊列是否為滿D.以上說法都不對C.每當有刪除操作時，總是要先做一次插入操作D.每次從隊列中刪除的總是最早插入的元素56 .和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是A。A.通常不會出現(xiàn)棧滿的情況 B.通常不會出現(xiàn)?？盏那闆rC.插入操作更容易實現(xiàn) D.刪除操作更容易實現(xiàn)57

15、 .用不帶頭結點的單鏈表存儲隊列，其頭指針指向隊頭結點，尾指針指向隊尾結點，則在進行出隊操作時 C。A.僅修改隊頭指針 B.僅修改隊尾指針C.隊頭、隊尾指針都可能要修改 D.隊頭、隊尾指針都要修改58 .若串 S=software,其子串的數(shù)目是 B。A.8B.37C.36D.959 .串的長度是指_B。A.串中所含不同字母的個數(shù) B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù) D.串中所含非空格字符的個數(shù)60 .串是一種特殊的線性表，其特殊性體現(xiàn)在 BA.可以順序存儲 B.數(shù)據(jù)元素是一個字符1261 .設有兩個串 p 和 q,求 q 在 p 中首次出現(xiàn)的位置的運算稱為 B。A.連接 B.模

16、式匹配 C.求子串 D.求串長62 .數(shù)組 A 中，每個元素的長度為 3 個字節(jié)，行下標 i 從 1 到 8,列下標 j 從 1 到 10,從首地址 SA 開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素 A85的起始地址為C。A.SA+141B.SA+144C.SA+222D.SA+22563 .數(shù)組 A 中，每個元素的長度為 3 個字節(jié)，行下標 i 從 1 到 8,列下標 j 從 1 到 10,從首地址 SA 開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素 A58的起始地址為C。A.SA+141B.SA+180C.SA+222D.SA+22564 .若聲明一個浮點數(shù)數(shù)組如下：froatavera

17、ge=newfloat30;假設該數(shù)組的內(nèi)存起始位置為 200,average15 附內(nèi)存地址是 CA.214B.215C.260D.256n按行存儲在數(shù)組 B 中，則二維數(shù)組元素 Ai,j在一維數(shù)組 B 中的下標為 AA.n*(i-1)+jB.n*(i-1)+j-1C.i*(j-1)D.j*m+i-113C.可以鏈式存儲D.數(shù)據(jù)元素可以是多個字符65.設二維數(shù)組 A1,m,1,66.有一個 100X90 的稀疏矩陣，非 0 元素有 10,設每個整型數(shù)占 2 個字節(jié),則用三元組表示該矩陣時，所需的字節(jié)數(shù)是 B。A.20B.66C.18000D.33-3,5,7中含有的元素個數(shù)是 AC.36D.

18、1668 .對矩陣進行壓縮存儲是為了 D。A.方便運算 B.方便存儲 C.提高運算速度 D.減少存儲空間69 .設有一個 10 階的對稱矩陣 A,采用壓縮存儲方式，以行序為主存儲，源1為第一個元素，其存儲地址為 1,每個元素占 1 個地址空間，則 a8,5的地址為B。A.13B.33C.18D.4070 .稀疏矩陣一般的壓縮存儲方式有兩種，即 C。A.二維數(shù)組和三維數(shù)組 B,三元組和散列C.三元組和十字鏈表 D.散列和十字鏈表71 .樹最適合用來表示A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素67.數(shù)組 A0,4,-1A.55B.4572 .深度為 5 的二叉樹至多有 C 個結點。A.16B.32C.3

19、1C.1073 .對一個滿二叉樹，m 個葉子，n 個結點，深度為 h,則 DA.n=h+mBh+m=2nCm=h-1Dn=2h-174 .任何一棵二叉樹的葉子結點在前序、中序和后序遍歷序列中的相對次序A。A.不發(fā)生改變 B.發(fā)生改變 C.不能確定 D.以上都不對75.在線索化樹中，每個結點必須設置一個標志來說明它的左、右鏈指向的是樹結構信息，還是線索化信息，若 0 標識樹結構信息，1 標識線索，對應葉結點的左右鏈域，應標識為D。A.00B.01C.10D.1176 .在下述論述中，正確的是 D。只有一個結點的二叉樹的度為 0；二叉樹的度為 2;二叉樹的左右子樹可任意交換；深度為 K 的順序二叉

20、樹的結點個數(shù)小于或等于深度相同的滿二叉樹。A.B.C.D.77 .設森林 F 對應的二叉樹為 B,它有 m 個結點，B 的根為 p,p 的右子樹的結15C.元素之間具有分支層次關系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)14點個數(shù)為 n,森林 F 中第一棵樹的結點的個數(shù)是 A。A.m-nB.m-n-1C.n+1D,不能確定78 .若一棵二叉樹具有 10 個度為 2 的結點，5 個度為 1 的結點，則度為 0 的結點的個數(shù)是 B。A.9B.11C.15D.不能確定79 .具有 10 個葉子結點的二叉樹中有 B 個度為 2 的結點。A.8B.9C.10D.1180 .在一個無向圖中，所有頂點的度數(shù)之和等于所

21、有邊數(shù)的 C 倍。A.1/2B1C2D481 .在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 B 倍。A.1/2B1C2D4（2三中左f）我按我做的題目舉例吧：后序序列為：bfegcda,中序序列為：badefcg,求前序序列。這里會用：后序列序列最后一個值即樹（或子樹）的根。由后序bfegcda知a為根，由中序badefcg知a的左子樹僅有b一個節(jié)點。即圖1.去除序列中的b和a得后序“fegcd和中序“defcg,可知，d為a的右子樹樹根（后序最后一個值）且d的左子樹為空（d前面無值），同理再去掉d得到，“fegcW“efcg,可知c為d的右子樹樹根，如圖2.由中序“efcg知

22、c的右子樹為g,左子樹為e,f,同理得最后結果樹為圖3.于是得出前序列為：abdcefg82 .某二叉樹結點的中序序列為 ABCDEFG,后序序列為 BDCAFGE,則其左子樹中結點數(shù)目為：CA.3B.2C.4D.51683 .已知一算術表達式的中綴形式為 A+B*C-D/E,后綴形式為 ABC*+DE/-,其前綴形式為D。將算術表達式的中綴形式作為一棵二叉樹的中序遍歷序列，將后綴形式作為這棵二叉樹的后序遍歷序列，再由二叉樹的中序遍歷序列和后序遍歷序列唯一的確定這棵二叉樹，在對其進行先序遍歷，就可得出算術表達式的前綴形式。85 .采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的 AA.先序遍

23、歷 B.中序遍歷 C.后序遍歷 D.按層遍歷86 .采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的 D=A.先序遍歷 B.中序遍歷 C.后序遍歷 D.按層遍歷87 .具有 n 個結點的連通圖至少有一 A 一條邊17A.n-1B.nC.n(n-1)/2D.2nA.力+B*C/DEB.力+B*CD/E+ABC/DED.TA*BC/DE84.已知一個圖，如圖所示，若從頂點 a 出搜索法進行遍歷，則可能得到的一種頂點序D;按廣度搜索法進行遍歷， 則可能種頂點序列為 A;A.a,b,e,c,d,fC.a,e,b,c,f,d,A.a,b,c,e,d,fC.a,e,b,c,f,d,B.a,c,f,e,b

24、,dD.a,e,d,f,c,bB.a,b,c,e,f,dD.a,c,f,d,e,b發(fā)按深度列為得到的一88 .廣義表(a),a)的表頭是 C,表尾是 C。A.aB()C(a)D(a)89 .廣義表(a)的表頭是 C、表尾是 BA.aB()C(a)D(a)90 .順序查找法適合于存儲結構為B_的線性表。A 散列存儲 B 順序存儲或鏈式存儲 C 壓縮存儲 D 索引存儲91 .對線性表進行折半查找時，要求線性表必須_B。A 以順序方式存儲 B 以順序方式存儲，且結點按關鍵字有序排列C 以鏈式方式存儲 D 以鏈式方式存儲，且結點按關鍵字有序排列92 .采用折半查找法查找長度為 n 的線性表時，每個元素

25、的平均查找長度為D。AO(n2)BO(nlog2n)CO(n)DO(log2n)12,32,41,45,62,75,77,82,95,100,18當折半查找值為 82 的結點時，C 次比較后查找成功。93.有一個有序表為1,3,9,A.11B5C4D894 .二叉樹為二叉排序樹的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法 B。A 正確 B 錯誤95 .下面關于 B 樹和 B+樹的敘述中，不正確的結論是A。AB樹和 B+樹都能有效的支持順序查找 BB 樹和 B+樹都能有效的支持隨機查找CB 樹和 B+樹都是平衡的多叉樹 DB 樹和 B+樹都可用于文件索引結構96

26、.以下說法錯誤的是 B。A.散列法存儲的思想是由關鍵字值決定數(shù)據(jù)的存儲地址B.散列表的結點中只包含數(shù)據(jù)元素自身的信息，不包含指針。C.負載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度。D.散列表的查找效率主要取決于散列表構造時選取的散列函數(shù)和處理沖突的方法。97.查找效率最高的二叉排序樹是_C。A.所有結點的左子樹都為空的二叉排序樹。B.所有結點的右子樹都為空的二叉排序樹。19C.平衡二叉樹。D.沒有左子樹的二叉排序樹。98 .排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為 C。A.希爾排序 B。冒泡排序 C 插入排序 D

27、o 選擇排序99 .在所有的排序方法中，關鍵字比較的次數(shù)與記錄的初始排列次序無關的是 D。A.希爾排序 B.冒泡排序 C.直接插入排序 D.直接選擇排序?100.堆是一種有用的數(shù)據(jù)結構。下列關鍵碼序列 D 是一個堆。A.94,31,53,23,16,72B.94,53,31,72,16,23將所有數(shù)據(jù)序列按完全二叉樹從根開始放如果所有分支都小于或者等于孩子結點關鍵碼，就是小頂堆，反之，如果所有分支結點的關鍵碼大于或者等于孩子結點關鍵碼，則為大頂堆C.16,53,23,94,31,72D.16,31,23,94,53,72101 .堆排序是一種 B 排序。A.插入 B.選擇 C.交換 D.歸并1

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

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

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

31、t=L。18 .是限定僅在表尾進行插入或刪除操作的線性表，其運算遵循后進先出的原則。19 .空串是零個字符的串,其長度等于 JUo 空白與是由一個或多個空格字符組成的串,其長度等于其包含的空格個數(shù)。20 .組成串的數(shù)據(jù)元素只能是單個字符。21 .一個字符串中任意個連續(xù)字符構成的部分稱為該串的子串。22 .子串“str在主串datastructue中的位置是 5。23 .二維數(shù)組 M 的每個元素是 6 個字符組成的串，行下標 i 的范圍從 0 到 8,列23下標 j 的范圍從 1 到 10,則存放 M 至少需要 540 個字節(jié);M 的第 8 列和第 5 行共占 108個字節(jié)。24 .稀疏矩陣一般

32、的壓縮存儲方法有兩種，即三元組表和十字鏈表。25 .廣義表(a),(b),c),(d)的長度是 3、深度是 4。26 .在一棵二叉樹中，度為零的結點的個數(shù)為 n0,度為 2 的結點的個數(shù)為 n2,則有 n0=n2+1。27 .在有 n 個結點的二叉鏈表中，空鏈域的個數(shù)為_n+T_o28 .一棵有 n 個葉子結點的哈夫曼樹共有_2n-1_個結點。29 .深度為 5 的二叉樹至多有 31 個結點。30 .若某二叉樹有 20 個葉子結點，有 30 個結點僅有一個孩子，則該二叉樹的總結點個數(shù)為 69。31 .某二叉樹的前序遍歷序列是 abdgcefh,中序序列是 dgbaechf,其后序序列為gdbe

33、hfca。2432 .線索二叉樹的左線索指向其遍歷序列中的前驅,右線索指向其近歷序歹 U 中的后繼。33 .在各種查找方法中，平均查找長度與結點個數(shù) n 無關的查找方法是散列查找法。34 .在分塊索引查找方法中，首先查找索引表，然后查找相應的塊35 .一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列、構造樹的過程即為對無序序列進行排序的過程。36 .具有 10 個頂點的無向圖，邊的總數(shù)最多為_45-37 .已知圖 G 的鄰接表如圖所示，其從頂點 v1 出發(fā)的深度優(yōu)先搜索序列為_v1v2V3V6V5V4,其從頂點 v1 出發(fā)的廣度優(yōu)先搜索序列為_v1v2V5V4V3V6_。38 .索引是

34、為了加快檢索速度而引進的一種數(shù)據(jù)結構。一個索引隸屬于某個數(shù)25據(jù)記錄集，它由若干索引項組成，索引項的結構為關鍵字和關鍵字對應記錄的地址。39 .Prim 算法生成一個最小生成樹每一步選擇都要滿足邊的總數(shù)不超過 n-1,當前選擇的邊的權值是候選邊中最小的，選中的邊加入樹中不產(chǎn)生回路三項原則。40 .在一棵 m 階 B 樹中，除根結點外，每個結點最多有 m 棵子樹，最少有 m/2 棵子樹。三、判斷題。1 .在決定選取何種存儲結構時，一般不考慮各結點的值如何。（，）2 .抽象數(shù)據(jù)類型（ADT）包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個 ADT 的邏輯特性，不必考慮如何在計算機中實現(xiàn)。（，）3 .抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關。（，）4 .順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（X）5 .線性表采用鏈式存儲結構時，結點和結點內(nèi)部的存儲空間可以是不連續(xù)的。（x）6 .對任何數(shù)據(jù)結構鏈式存儲結構一定優(yōu)于順序存儲結構。（x）7 .順序存儲方式只能用于存儲線性結構。（X）8 .集合與線性表的區(qū)別在于是否按關鍵字排序。（X）9 .線性表中每個元素都有一個直接前驅和一個直接