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

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