數(shù)據(jù)結(jié)構(gòu)期末考試試題有答案

數(shù)據(jù)結(jié)一、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設計問題中計算機的 操作對象 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R，其中D是 是D上的 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu) 、數(shù)據(jù)的結(jié)構(gòu) 和數(shù)據(jù)的 運算 線性結(jié)構(gòu)中元間存在一對一關系，樹形結(jié)構(gòu)中元間存在一對多關系，圖形結(jié)構(gòu)中元間存在多對多關系。性結(jié)構(gòu)中，第一個結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點最后一個結(jié)點沒有 后續(xù)結(jié)點其余每個結(jié)點有且只有1個后續(xù)結(jié)點。在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點葉子結(jié)點沒有后續(xù) 結(jié)點其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意個 。在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以任意多 數(shù)據(jù)的結(jié)構(gòu)可用四種基本的方法表示它們分別是順序、鏈式、索引和散列。數(shù)據(jù)的運算最常用的有5、刪除、修改、查找、排序一個算法的效率可分為時 效率 空 效率在順序表中插入或刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數(shù)與表長和該元素在表中的位置有關。線性表中結(jié)點的集合是有 的，結(jié)點間的關系 一對 的向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動n-i+1個元素。n刪除第i元素(1≤i≤nn-i個在順序表中任意一結(jié)點的時間復雜度均為O(1)，因此，順序表也稱為隨機存取的數(shù)據(jù)結(jié)構(gòu)。順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。在單鏈表中，除了首元結(jié)點外，任一結(jié)點的位置由其直接前驅(qū)結(jié)點的鏈域的值指示。在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的前驅(qū)結(jié)點的地址，其時間復雜度為O（n。向量、棧和隊列都是線性結(jié)構(gòu)，可以在向量的任何位置插入和刪能在隊尾插入和隊首刪除元素。棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂。不允許插入和刪除運算的一端稱為棧底。隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除不包含任何字符（長度為0）的串稱為空串；由一個或多個空格（由空格符）組成的 稱為空白串子串的定位運算稱為串的模式匹配；被匹配的主串 稱為目標串，子串假設有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)，器按字節(jié)編址。已知A的起始位置（址為1000，則數(shù)組A的體積（量 ；末尾元素A57的第一個字節(jié)地址為 ；若按行時，元素A14的第一個字節(jié)地址為(8+4)×6 ；若按列時，元素A47的第一個字節(jié)地址為(6×7＋4)×6＋1000）＝1276 由３個結(jié)點所構(gòu)成的二叉樹 5種形態(tài) 6n+n0+nn1=31 個葉子注：滿二叉樹沒有度為1的結(jié)點，所以分支結(jié)點數(shù)就是二度結(jié)點數(shù)一棵具有２５７個結(jié)點的完全二叉樹，它的深度 （log2(n)+1=8.xx設一棵完全二叉樹有700350個葉子結(jié)點。設一棵完全二叉樹具有1000結(jié)500有499個度為2的結(jié)點，有1個結(jié)點只有非空左，有0個結(jié)點答：最快方法：用葉子數(shù)＝[n/2]＝500，n2=n0-1=499。另外，最后一結(jié)點為2i屬于左葉子，右葉子是空的，所以有1個非空左。完全二叉樹的特點決定不可在數(shù)據(jù)的存放無規(guī)律而言的線性表中進行檢索的最佳方法是順序查找（查找）線性有序表（a1，a2，a3，…，a256)是從小到大排列的，對一個給定的值k，用二分法檢索表中與k相等的元素在查找不成功的情況下最多需要檢索8 設有100個結(jié)點，用二分法查找時，最大比較次數(shù)是7 假設在有序線性表a[20]上進行折半查找，則比較一次查找成功的結(jié)點數(shù)為1；比較兩次查找成功的結(jié)點數(shù)為2 ；比較四次查找成功的結(jié)點數(shù)為8 查找長度 3.72解：顯然，平均查找長度＝O（logn）<5（25。但具體是多少次，則不應當按照2nn＝2m-1的情況下推導出來的公式。應當用窮舉法羅列全部元素的查找次數(shù)為＝（122438455）＝74ASL74/20=3.7折半查找有序表（46122028385070，88100，若查找表中元素20，它將依次與表中元素 28，6，12，20 比較大小。在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關的查找方法是散列查 散列法的基本思想是由關鍵字的值 （）1.表的每個結(jié)點中都恰好包含一個指針的結(jié)點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結(jié)點的指針。（×）2.鏈表的物理結(jié)構(gòu)具有同鏈表一樣的順序。錯，鏈表的結(jié)構(gòu)特（×）3.表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動（×）4.性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一錯，了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。（×）5.序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。（×）6.順序方式的優(yōu)點是密度大，且插入、刪除運算效率高錯，前一半正確，但后一半說法錯誤，那是鏈式的優(yōu)點。順序方式插入、刪除運算效率較低，在表長為n動表長一半個數(shù)的數(shù)據(jù)元素。（×）7.線性表在物理空間中也一定是連續(xù)的錯，線性表有兩種方式，順序和鏈式。后者不要求連續(xù)存放（×）8.線性表在順序時，邏輯上相鄰的元素未必在的物理位置次序錯誤。線性表有兩種方式，在順序時，邏輯上相鄰的元素在的物理位置次序上也相鄰。（×）9.順序方式只能用于線性結(jié)構(gòu) （×）10.線性表的邏輯順序與順序總是一致的。錯，理由同7。鏈式就無需一致。（×）11.線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是錯，線性表是邏輯結(jié)構(gòu)概念，可以順序或鏈式，與元素數(shù)據(jù)類型無關（×）12.表結(jié)構(gòu)中最常用的是線性表，棧和隊列不太常用。錯，不一定吧？調(diào)用子程序或函數(shù)常用，CPU也用隊列。（√）13.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是（√）14.對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可而已。（×）15.和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)錯，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是結(jié)構(gòu)概念，二者不是類項。（×）16.和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)同而已。（√）17.棧和隊列的方式既可是順序方式，也可是方式（√）18.兩個棧共片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機（×）19.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)構(gòu)錯，后半句不對（×）20.個棧的輸入序列是12345，則棧的輸出序列不可能是12345。（）21.二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n結(jié)點的二叉樹鏈表中只n—1個非空指針域（×）22.二叉樹中每個結(jié)點的兩棵的高度差等于1（√）23.二叉樹中每個結(jié)點的兩棵是有序的（×）24.二叉樹中每個結(jié)點有兩棵非空或有兩棵空（（×）25.二叉樹中每個結(jié)點的關鍵字值大于其左非空若存在的話）所有結(jié)點的關鍵字值，且小于其右非空（若存在的話）所有結(jié)點的關鍵字值。（應（（×）26.二叉樹中所有結(jié)點個數(shù)是2k-1-1，其中k是樹的深（應2i-（×）27.二叉樹中所有結(jié)點，如果不存在非空左，則不存在非空右2i—1結(jié)點（應2i-1）（√）29.用二叉鏈表法（link-rlink）包含n個結(jié)點的二叉樹，結(jié)點的個指針區(qū)域中有n+1個為空指針（）30.具有12結(jié)點的完全二叉樹有5度為2結(jié)點。（B）1.非線性結(jié)構(gòu)是數(shù)據(jù)元間存在一種A）一對多關系B）多對多關系C）多對一關系D）一對一（C）2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關的是數(shù)據(jù)的結(jié)構(gòu)A)B)物 C)邏 D)物理（C）3.的目A)找出數(shù)據(jù)結(jié)構(gòu)的合理 B)研究算法中的輸入和輸出的關C)分析算法的效率以求改 D)分析算法的易懂性和（A）4.的兩A)空間復雜性和時間復雜 B)正確性和簡明C)可讀性和文D)數(shù)據(jù)復雜性和程序復雜（C）5.法指A)計算方法 B)排序方法C)解決問題的有限運算序列 D)調(diào)度方（B）6.計算機算法必須具備輸入、輸出 等5個特性A)可行性、可移植性和可擴充 B)可行性、確定性和有窮C)確定性、有窮性和穩(wěn)定 D)易讀性、穩(wěn)定性和安全（C）7．數(shù)據(jù)在計算機器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù) （B）8.一個向量第一個元素的地址是100，每個元素的長度為2，則第個元 （A）9.n結(jié)點的順序表中，算法O（1）的操作是 第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)在第i個結(jié)點后插入一個新結(jié)點刪除第in個結(jié)點從小到大排（B）10個有127素的順序表中插入一個新元素并保持原來順序不變，平均要移動個元素 （A）11.的結(jié)構(gòu)所占空間分兩部分，一部分存放結(jié)點值，另一只有一部分，存放結(jié)點(C）只有一部分，表示結(jié)點間關系的指（D）分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元（B）12.鏈表是一種采 結(jié)構(gòu)的線性表（A）順 （B）鏈 （C）星 （D）網(wǎng)（D）13.線性表若采用鏈式結(jié)構(gòu)時，要求內(nèi)存中可用單元的地址（A）必須是連續(xù) （B）部分地址必須是連續(xù)（C）一定是不連續(xù) （D）連續(xù)或不連續(xù)都可（B）14．線性表Ｌ 情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)（Ａ）需經(jīng)常修改Ｌ中的結(jié)點 （Ｂ）需不斷對Ｌ進行刪除插（Ｃ）Ｌ中的結(jié) （Ｄ）Ｌ中結(jié)點結(jié)構(gòu)復（B）15.棧中元素的進出原則Ａ．先進先 Ｂ．后進先 Ｃ．?？談t Ｄ．棧滿則（C）16.棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi Ｃ．n- （B）17一個棧ST（最多元m0）為空的條件Ａ．ST- Ｂ．ST- Ｃ．ST-Ｄ．ST-（C）18.在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù) 倍 B. C. D.（B）19.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 B. C. D.（B）20.有8個結(jié)點的無向圖最多 條邊 B. C. （C）21.有8個結(jié)點的有向完全圖 條邊 B. C. （B）22．在表長為ｎ的鏈表中進行線性查找，它的平均查找長度為Ａ.ＡＳＬ＝ｎ; Ｂ.ＡＳＬ＝（ｎ＋１）／２;nＣ. Ｄ.n（A）23．折半查找有序表（4，6，10，12，20，30，50，70，88，100。若查找表中元素58，則它將依次與表中 （C）24．對22個記錄的有序表作折半查找，當查找失敗時，至少需要次關D．（A查A．順 B．二分 C．順序，也能二分 D．隨《數(shù)據(jù)結(jié)構(gòu)與算法》一、選擇題 2．數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指A 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關的是數(shù)據(jù) 結(jié)構(gòu)邏 B．C．邏輯和D．物在數(shù)據(jù)時，通常不僅要各數(shù)據(jù)元素的值，而且還要 C．數(shù)據(jù)元間的關 D．數(shù)據(jù)的方在決定選取何種結(jié)構(gòu)時，一般不考 各結(jié)點的值如 B．結(jié)點個數(shù)的多C．對數(shù)據(jù)有哪些運 D．所用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方便以下說法正確的是 D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)算法分析的目的是 ，算法分析的兩個主要方面是 （2）A．空間復雜度和時間復雜 B．正確性和簡明C．可讀性和文D．數(shù)據(jù)復雜性和程序復雜下面程序段的時間復雜度是 sfor(I=0;i<n;s+=B[i][j];sum=s下面程序段的時間復雜度是 for(i=0;i<n;A[i][j]＝0;下面程序段的時間復雜度是 i＝0；i=i* D．隊列的操作方式是先進后通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著B數(shù)據(jù)元素具有同一D．數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)鏈表不具備的特點 C．不必事先估計空 D．所需空間與其長度成正不結(jié)點的單鏈表head為空的判定條件 A．head== Bhead->nextC．head->next D結(jié)點的單鏈表head為空的判定條件是 A．head==NULL Bhead->next==NULLC．head->next==head Dhead!=NULL 方式最節(jié)省運算時間 需要分配較大空間，插入和刪除不需要移動元素的線性表，其結(jié)構(gòu) A．單鏈 B．靜態(tài)鏈 C．線性鏈 D．順序結(jié)非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足 A．p->next==NULL B．p==NULLC．p->next==head D．p==head在循環(huán)雙鏈表的p所指的結(jié)點之前插入s所指結(jié)點的操作是 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-C．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=如果最常用的操作是取第i個結(jié)點及其前驅(qū)則采用D方式最節(jié)省時間單鏈 B．雙鏈 C．單循環(huán)鏈 D．順序在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是B。 在一個長度為n（n>1）的單鏈表上，設有頭和尾兩個指針，執(zhí)行 B操作與與單鏈表相比，雙鏈表的優(yōu)點之一是D 入新元素，則最好使用B。D．循環(huán)雙鏈≤n+1， A．n–i+ B．n– D．i–對于只在表的首尾兩端進行插入操作的線性表宜采用的結(jié)構(gòu) 順序 B．用頭指針表示的循環(huán)單鏈C．用尾指針表示的循環(huán)單鏈 D．單鏈下述哪一條是順序結(jié)構(gòu)的優(yōu)點 A插入運算方 B可方便地用于各種邏輯結(jié)構(gòu)的表C密度 D刪除運算方下面關于線性表的敘述中，錯誤的是哪一個 A線性表采用順序，必須占用一片連續(xù)的單B線性表采用順序，便于進行插入和刪除操作C線性表采用鏈式，不必占用一片連續(xù)的單D線性表采用鏈 ，便于進行插入和刪除操作線性表是具有n 的有限序列字 B．數(shù)據(jù)元 C．數(shù)據(jù) D．表元在n個結(jié)點的線性表的數(shù)組實現(xiàn)中算法的時間復雜度是（1的操作 第i（1<=i<=n）個結(jié)點和求第i個結(jié)點的直接前驅(qū)在第i（1<=i<=n）個結(jié)點后插入一個新結(jié)若長度為n的線性表采用順序結(jié)構(gòu)，在其第i個位置插入一個新元素的算 C。 ，對于順序的線性表結(jié)點和增加、刪除結(jié)點的時間復雜度 ，A．O(n) B．O(n) C．O(1) D．O(1)線性表（a1,a2,…,an）以鏈式方式，第i位置元素的時間復雜度 單鏈表中，增加一個頭結(jié)點的目的是為了 使單鏈表至少有一個結(jié) B．標識表結(jié)點中首結(jié)點的位C．方面運算的實 D．說明單鏈表是線性表的鏈在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是 B．s->next=p->next；p->next=s; 線性表的順序結(jié)構(gòu)是一種 隨機存取的結(jié) B．順序存取的結(jié)C．索引存取的結(jié) D．Hash存取的結(jié)棧的特點 ，隊列的特點是 先進先 B．先進后棧和隊列的共同點是 一個棧的進棧序列是a，b，c，d，e，則棧的不可能的輸出序列 設有一個棧，元素依次進棧的順序為A、B、C、D、E。下列 以 不是隊列的基本運算從隊入一個新元 B．從隊列中刪除第i個元C．判斷一個隊列是否為 D．隊頭元素的若已知一個棧的進棧序列是1，2，3，n，其輸出序列為p1，p2，p3，…，pn，若p1＝n，則pi為 D．不確判定一個順序棧st（最多元素為MaxSize）為空的條件是 st->top!=- B．st->top==-C．st->top!= D．st->top==判定一個順序棧st（最多元素為MaxSize）為滿的條件是 st->top!=- B．st->top==-C．st->top!= D．st->top==一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是 判定一個循環(huán)隊列qu（最多元素為MaxSize）為空的條件是 qu->rear–qu->front B．qu->rear–qu--C．qu->rear==qu- D．qu->rear=qu->front-在循環(huán)隊列中，若front與rear分別表示對頭元素和隊尾元素的位置，則判 向一個棧頂指針為h的結(jié)點的鏈棧中插入指針s所指的結(jié)點時應執(zhí)行操作A．h->next=s B．s->next=hC．s->next=h;h=s D．s->next=h->next;h->next=s輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為 B。 C．push，push，pop， D．push，pop，push，push，pop，若棧采用順序方式，現(xiàn)兩棧共享空間V[1m]，top[1]、top[2]分別B。A．|top[2]-top[1]|=0 B．top[1]+1=top[2] 設計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用 數(shù)據(jù)結(jié)最佳線性表的順序結(jié) C．線性表的鏈式結(jié) 允許對隊列進行的操作有 對于循環(huán)隊 若用一個大小為6的數(shù)值來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為B。和 B．2和 C．4和 D．5和隊列的“先進先出”特性是 最早插入隊列中的元素總是最后D．每次從隊列中刪除的總是最早插入的元和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是 通常不會出現(xiàn)棧滿的情 B．通常不會出現(xiàn)?？盏那镃．插入操作更容易實 D．刪除操作更容易實用不結(jié)點的單鏈表隊列，其頭指針指向隊頭結(jié)點，尾指針指向隊尾結(jié)點，則在進行出隊操作時 C 。僅修改隊頭指 B．僅修改隊尾指C．隊頭、隊尾指針都可能要修 D．隊頭、隊尾指針都要修若串S=‘software，其子串的數(shù)目 串的長度是 串是一種特殊的線性表，其特殊性體現(xiàn)在 可以順序B．數(shù)據(jù)元素是一個字C．可以鏈式D．數(shù)據(jù)元素可以是多個字設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為 連 B．模式匹 C．求子 D．求串數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i18，列下標j110，從首地址SA開始連續(xù)存放的器內(nèi)，該數(shù)組按行存放，元素A[8][5]的起始 C。A．SA＋141B． 數(shù)組A每個元素的長度為3字節(jié)，行下標i18，列下標j110，從首地址SA開始連續(xù)存放的器內(nèi)，該數(shù)組按行存放，元素A[5][8]的起始 A．SA＋141B． 若一個浮點數(shù)數(shù)組如下：froataverage[]=new假設該數(shù)組的內(nèi)存起始位置為200，average[15]的內(nèi)存地址是 設二維數(shù)組A[1…m,1…n]按行在數(shù)組B中則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標為 n*(i-1)+jB．n*(i-1)+j- C．i*(j- D．j*m+i-有一個100×90的稀疏矩陣，非0元素有10，設每個整型數(shù)占2個字節(jié)，則 B． C．18 數(shù)組A[0…4，-1…-3，5…7]中含有的元素個數(shù)是 B． 對矩陣進行壓縮是為 方便運算B．方便C．提高運算速 D．減少空設有一個10階的對稱矩陣A，采用壓縮方式，以行序為主，a1，1為第一個元素，其地址為1，每個元素占1個地址空間，則a8，5的地址為B。A．13B． 稀疏矩陣一般的壓縮方式有兩種，即C B．三元組和散列 D．散列和十字鏈表樹最適合用來表 C 深度為5的二叉樹至多 個結(jié)點 B． C． 對一個滿二叉樹，m個葉子，n個結(jié)點，深度為h，則 A．n= Bh+m= Cm=h- Dn=2h-任何一棵二叉樹的葉子結(jié) 序中序和后序遍歷序列中的相對次 不發(fā)生改 B．發(fā)生改 C．不能確 D．以上都不索化樹中，每個結(jié)點必須設置一個標志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若0標識樹結(jié)構(gòu)信息，1右鏈域，應標識為D。 在下述論述中，正確的 ①只有一個結(jié)點的二叉樹的度為0；②二叉樹的度為2；③二叉樹的左右可任意④深度為K的順序二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉 設森林F對應的二叉樹為B，它有m個結(jié)點，B的根為p，p的右的結(jié)點個數(shù)為n，森林F中第一棵樹的結(jié)點的個數(shù)是 A．m- B．m-n- D．不能若一棵二叉樹具有10度為25度為1則度為0的個數(shù)是B。 D．不能確具有10個葉子結(jié)點的二叉樹中 個度為2的結(jié)點 在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的C倍 B C D在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的B倍 B C D某二叉樹結(jié)點的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左中結(jié) 已知一算術表達式的中綴形式為A＋B*C–D/E，后綴形式為ABC*+DE/–，其 A．– B．– C 已知一個圖，如圖所示，若從頂點a出發(fā)按深度搜索法進行遍歷，則可能得到的一種頂點序列為D；按廣度搜索法進行遍歷，則可能得到的一種頂點序列為A；abecdabecdf②A．a(chǎn)，b，c，e，d，fB．a(chǎn)，b，c，e，f，dC．a(chǎn)，e，b，c，f，d，采用鄰接表的圖的深度優(yōu)先遍歷算法類似于二叉樹的 先序遍 B．中序遍 C．后序遍 D．按層遍采用鄰接表的圖的廣度優(yōu)先遍歷算法類似于二叉樹的 先序遍 B．中序遍 C．后序遍 D．按層遍具有n個結(jié)點的連通圖至少 條邊n- B． C．n(n- D．廣義表（a，a）的表C，表尾是C。 B C D廣義表（a）的表頭是C，表尾是B B C D順序查找法適合于結(jié)構(gòu) B的線性表A散列B順序或鏈式C壓縮D索對線性表進行折半查找時，要求線性表必須 A以順序方式B以順序方式，且結(jié)點按關鍵字有序排C以鏈式方式D以鏈式方式，且結(jié)點按關鍵字有序排采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為D。ABCD有一個有序表｛139123241456275778295100當折半查找值為82的結(jié)點時，C 次比較后查找成功。 B 二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值小于其右孩子的值。這種說法 B 。 正 錯下面關于B樹和B+樹的敘述中，不正確的結(jié)論 AB樹和B+樹都能有效的支持順序查找 BB樹和B+樹都能有效的支持隨機CB樹和B+樹都是平衡的多叉樹 DB樹和B+樹都可用于文件索引結(jié)以下說法錯誤的 散列法的思想是由關鍵字值決定數(shù)據(jù)的地D．散列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處 的方法查找效率最高的二叉排序樹是 所有結(jié)點的左都為空的二叉排序樹所有結(jié)點的右都為空的二叉排序樹排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較將其放入已排序序列的正確位置上的方法，稱為 C 。希爾排 B。冒泡排 C插入排 D。選擇排在所有的排序方法中，關鍵字比較的次數(shù)與記錄的初始排列次序無關的是 A．希爾排 B．冒泡排 C．直接插入排 D．直接選擇排堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關鍵碼序 是一個堆 堆排序是一 排序插 B．選 C．交 D．歸 在鏈表中進行操作比在順序表中進行操作效率順序查 B．折半查 C．分塊查 D．插直接選擇排序的時間復雜度 （n為元素個數(shù) B．O(log C．O(nlog D． 二、填空題數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu) 、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)分 集 、線性結(jié) 、樹形結(jié)構(gòu)和圖狀結(jié)4種．3性結(jié)構(gòu)中，第一個結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點．線性結(jié)構(gòu)中元間存在一對一關系樹形結(jié)構(gòu)中元間存在一對多關系，圖形結(jié)構(gòu)中元間存在多對多關系。在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū) 后續(xù)結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點可以任意多個。數(shù)據(jù)結(jié)構(gòu)的基本方法是順序、鏈式 索引 散列衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和間復間復雜度。評估一個算法的優(yōu)劣，通常從時間復雜 和空間復雜 兩個方面察算法的5要特性是有窮性、確定性、可行性、輸入和輸在一個長度為n順序表中刪除第i元素時，需向前移動n-i-1個元素在單鏈表中，要刪除某一指定的結(jié)點，必須找到該結(jié)點的前驅(qū)在雙鏈表中，每個結(jié)點有兩個指針域，一個指向點，另一個繼結(jié)點。在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動n個數(shù)據(jù)元素，移動數(shù)據(jù)元素的個數(shù)與位置有關。當線性表的元素總數(shù)基本穩(wěn)定且很少進行插入和刪除操作但要求以最快的速度存取線性表的元素是，應采用順序 結(jié)構(gòu)。15．根據(jù)線性表的鏈式結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成單鏈表 和雙鏈表。16順序結(jié)構(gòu)是通過下標 表示元間的關系的鏈式結(jié)構(gòu)是通過指針表示元間的關系的。17．結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是L->next- 棧是限定僅在表尾進行插入或刪除操作的線性表，其運算遵循后進先出字符的串，其長?？瞻状怯梢粋€或多個空格字符組組成串的數(shù)據(jù)元素只能是個字符一個字符個連續(xù)字符構(gòu)成的部分為該串的子子串”strdatastructure的位置是5二維數(shù)組M的每6組成的串，行i08，列下j的范圍從110則存放M540M的第8列和第5108稀疏矩陣一般的壓縮方法有兩種，即元組表和十字廣義表（a（b，c（d）的長度是3，深度是4在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0，2結(jié)點的個n2，則n0＝n2+1在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為 一棵有n葉子結(jié)點的哈夫曼樹共有2n-1_個結(jié)深度為5的二叉樹至多有 個結(jié)點若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總點個數(shù) 某二叉樹的前序遍歷序abdgcefh，中序序列是dgbaechf，其后序序列為gdbehfca。線索二叉樹的左線索指向其遍歷序列中的前驅(qū) 列中的后繼。在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關的查找方法是散列查找 在分塊索引查找方法中首先查 索引 然后查找相應的塊表一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序具有10個頂點的無向圖