數(shù)據(jù)結(jié)構(gòu)(客觀題)

第一章緒論一、判斷題數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。丁數(shù)據(jù)元素是數(shù)據(jù)的最小單位。X算法是對(duì)解題方法和步驟的描述。丁程序和算法原則上沒(méi)有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)可以通用。X從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。丁數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映像。丁二、選擇題數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的(A)及它們之間的相互聯(lián)系。存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)B.存儲(chǔ)和抽象 C.聯(lián)系和抽象 D.聯(lián)系與邏輯下列與數(shù)據(jù)元素有關(guān)的敘述中錯(cuò)誤的是(A)。數(shù)據(jù)元素是有獨(dú)立含義的數(shù)據(jù)最小單位B.數(shù)據(jù)元素是描述數(shù)據(jù)的基本單位C.數(shù)據(jù)元素可以稱做結(jié)點(diǎn) D.數(shù)據(jù)元素可以稱做記錄數(shù)據(jù)結(jié)構(gòu)中，在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成：(C)。動(dòng)態(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)數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為(C)存儲(chǔ)結(jié)構(gòu) B.邏輯結(jié)構(gòu) C.順序存儲(chǔ)結(jié)構(gòu) D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)非線性結(jié)構(gòu)的數(shù)據(jù)元素之間存在(D)。一對(duì)一關(guān)系 B. 一對(duì)多關(guān)系 C.多對(duì)多關(guān)系 D.B或C在非線性結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)(D)。無(wú)直接前驅(qū)只有一個(gè)直接前驅(qū)和個(gè)數(shù)不受限制的直接后繼只有一個(gè)直接前驅(qū)和直接后繼有個(gè)數(shù)不受限制的直接前驅(qū)和直接后繼除了考慮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)本身所占用的空間外，實(shí)現(xiàn)算法所用的輔助空間的多少稱為算法的(B)。C.硬件效率 D.C.硬件效率 D.軟件效率刪除運(yùn)算方便B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括以上三個(gè)方面以下屬于順序存儲(chǔ)結(jié)構(gòu)優(yōu)點(diǎn)的是(A)。存儲(chǔ)密度大 B.插入運(yùn)算方便D.可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容是(D)。數(shù)據(jù)的邏輯結(jié)構(gòu)C.建立在相應(yīng)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)上的算法鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間(A)。分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針只有一部分，存放結(jié)點(diǎn)值只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針?lè)謨刹糠?，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)一個(gè)正確的算法應(yīng)該具有5個(gè)特性，除輸入、輸出特性外，另外3個(gè)特性是(A)。確定性、可行性、有窮性C確定性、可行性、有窮性C.有窮性、穩(wěn)定性、確定性易讀性、確定性、有效性D.可行性、易讀性、有窮性以下關(guān)于數(shù)據(jù)的邏輯結(jié)構(gòu)的敘述中正確的是(A)。數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述數(shù)據(jù)的邏輯結(jié)構(gòu)反映了數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式數(shù)據(jù)的邏輯結(jié)構(gòu)分為順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)分為靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)結(jié)構(gòu)設(shè)問(wèn)題的規(guī)模為n，分析以下程序段：k=n;/*n>l*/m=0;while(k>=(m+l)*(m-l))m++；以上程序段的算法時(shí)間復(fù)雜度是(A)O(n) B.O(1) C.O() D.O(n2)設(shè)問(wèn)題的規(guī)模為n，分析以下程序段：a=10;b=l00;while(b>0){a++;b――；}以上程序段的算法時(shí)間復(fù)雜度是(A)。A.O(n) B.O(1) C.O() D.O(n2)設(shè)語(yǔ)句s=s+i的時(shí)間是單位時(shí)間，則語(yǔ)句：s=0;for(i=l;i<=n;i++)s=s+i;的時(shí)間復(fù)雜度為：(B)。A.O(l) B.O(n) C.O(n2) D.O(n3)(16)算法分析的主要任務(wù)是(C)。A.探討算法的正確性和可讀性 B.探討數(shù)據(jù)組織方式的合理性為給定問(wèn)題尋找一種性能良好的解決方案 D.研究數(shù)據(jù)之間的邏輯關(guān)系以下敘述中正確的是(C)。順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu),探討數(shù)據(jù)組織方式的合理性，研究數(shù)據(jù)之間的邏輯關(guān)系順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)都可以用于線性和非線性結(jié)構(gòu)以上三種都不對(duì)以下敘述中正確的是(C)。A.數(shù)據(jù)元素是數(shù)據(jù)處理的最小單位 B.數(shù)據(jù)項(xiàng)是數(shù)據(jù)處理的基本單位C.關(guān)鍵字是能夠惟一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)D.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型的概念是等價(jià)的第二章線性表一、判斷題線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)。X鏈表的每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針域。X線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此

屬于同一數(shù)據(jù)對(duì)象。丁在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定相鄰。X在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，所以可以從頭結(jié)點(diǎn)開(kāi)始查找任何一個(gè)元素。丁在線性表的順序結(jié)構(gòu)中，插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。X順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除效率高。X在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。X順序存儲(chǔ)的線性表可以實(shí)現(xiàn)隨機(jī)存取。丁線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。丁二、選擇題線性表是(A)B.B.—個(gè)有限序列，不可以為空D.—個(gè)無(wú)限序列，不可以為空B.兩者長(zhǎng)度均固定D.兩者長(zhǎng)度均可變C.一個(gè)無(wú)限序列，可以為空一維數(shù)組與線性表的特征是(B)A.前者長(zhǎng)度固定，后者長(zhǎng)度可變C.后者長(zhǎng)度固定，前者長(zhǎng)度可變用單鏈表方式存儲(chǔ)的線性表，存儲(chǔ)每個(gè)結(jié)點(diǎn)需要兩個(gè)域，一個(gè)數(shù)據(jù)域，另一個(gè)是B).A.當(dāng)前結(jié)點(diǎn)所在地址域B.A.當(dāng)前結(jié)點(diǎn)所在地址域B.指針域用鏈表表示線性表的優(yōu)點(diǎn)是(B)。A.便于隨機(jī)存取C.占用的存儲(chǔ)空間較順序表少在具有n個(gè)結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)A.遍歷鏈表和求鏈表的第i個(gè)結(jié)點(diǎn)便于進(jìn)行插入和刪除操作元素的物理順序與邏輯順序相同的操作，其算法的時(shí)間復(fù)雜度都是0(n)。A在地址為P的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)C.C.刪除開(kāi)始結(jié)點(diǎn)D.刪除地址為P的結(jié)點(diǎn)的后繼結(jié)點(diǎn)下面關(guān)于線性表的敘述中，錯(cuò)誤的是(B)。線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)單元線性表采用順序存儲(chǔ)便于進(jìn)行插入和刪除操作線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)單元線性表采用鏈?zhǔn)酱鎯?chǔ)便于進(jìn)行插入和刪除操作已知單鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)?，F(xiàn)要將指針q指向的新結(jié)點(diǎn)插入到指針p指向的結(jié)點(diǎn)之后，下面的操作序列中正確的是(C)。A.q=p—>next;p一>next二q—>next;B. p —>next 二 q —>next;q二p—>next ;C. q —>next 二 p —>next;p—>next二q;D. p —>next 二 q ;q—>next二p—>next ;設(shè)al,a2,a3為三個(gè)結(jié)點(diǎn)；p,10,20代表地址，則如下的鏈表存儲(chǔ)結(jié)構(gòu)稱為—BA.鏈表 B.單鏈表 C.雙向循環(huán)鏈表 D.雙向鏈表單鏈表的存儲(chǔ)密度(C)。A.大于1 B.等于1 C.小于1 D.不能確定己知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)需占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址al,則第i個(gè)結(jié)點(diǎn)的地址為(A)。

在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是0(1)的操作是(B)。訪問(wèn)第i個(gè)結(jié)點(diǎn)(1WiWn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2WiWn)在第i個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)(1WiWn-1)刪除第i個(gè)結(jié)點(diǎn)(1WiWn)將n個(gè)結(jié)點(diǎn)從小到大排序在線性表中(B)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。A.A.首元素 B.中間元素對(duì)具有n個(gè)結(jié)點(diǎn)的線性表進(jìn)行查找運(yùn)算A.0(n2) B.0(nlog2n)線性表采用順序存儲(chǔ)的缺點(diǎn)是(D)。A.存儲(chǔ)密度降低元素的邏輯順序與物理順序不一致尾元素 D.所有元素所需的算法時(shí)間復(fù)雜度為(D)。0(log2n) D.0(n)只能順序訪問(wèn)插入、刪除操作效率低以下鏈表結(jié)構(gòu)中，從當(dāng)前結(jié)點(diǎn)出發(fā)能夠訪問(wèn)到任一結(jié)點(diǎn)的是(B)A以下鏈表結(jié)構(gòu)中，從當(dāng)前結(jié)點(diǎn)出發(fā)能夠訪問(wèn)到任一結(jié)點(diǎn)的是(B)A.單向鏈表和雙向鏈表C.單向鏈表和循環(huán)鏈表雙向鏈表和循環(huán)鏈表單向鏈表、雙向鏈表和循環(huán)鏈表線性表是具有n個(gè)(B)的有限序列。A.數(shù)據(jù)項(xiàng) A.數(shù)據(jù)項(xiàng) B.數(shù)據(jù)元素C.表元素D.字符若長(zhǎng)度為n的線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，訪問(wèn)其第i個(gè)元素的算法時(shí)間復(fù)雜度(B)。A.0(l) B.0(n) C.0(n2) D.0(log2n)指針P指向循環(huán)鏈表L的首元素的條件是(A)。A.P==L B.L-〉next==P C.P-〉next二二NULL D.P-〉next==L指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是(D)。A.P==L(20)不帶頭結(jié)點(diǎn)B.P—〉prior==L勺單鏈表L為空的條件是(B)C.P==NULLD.P—>next==LA.L!=NULLB.L==NULLC.L—>next==NULLD.L—>next==L(21)帶頭結(jié)點(diǎn)的單鏈表L為空的條件是(C)A.L!=NULLB.L==NULLC.L—>next==NULLD.L—>next==L兩個(gè)指針P和Q，分別指向單鏈表的兩個(gè)元素，P所指元素是Q所指元素前驅(qū)的條件是(B)。A.P—〉next==Q—〉nextB.P—〉next==Q C.Q—〉next==P D.P==Q在長(zhǎng)度為n的順序表中，若要?jiǎng)h除第i(1WiWn)個(gè)元素，則需要向前移動(dòng)元素的次數(shù)為(B)。A.1 B.n一i C.n一i+1 D.n一i一l在長(zhǎng)度為n的順序表中第i(1WiWn)個(gè)位置上插入一個(gè)元素時(shí)，為留出插入位置所需移動(dòng)元素的次數(shù)為(C)。A.n—i B.iA.n—i B.iC.n—i+1D.n—i—l假定己建立以下動(dòng)態(tài)鏈表結(jié)構(gòu)，且指針Pl和P2已指向如圖所示的結(jié)點(diǎn)：則以下可以將P2所指結(jié)點(diǎn)從鏈表中刪除并釋放該結(jié)點(diǎn)的語(yǔ)句組是(C)A.pl—〉next=p2—〉next;free(pl); B.pl=p2;free(p2);pl—〉next=p2—〉next；free(p2); D.pl=p2—〉next;free(p2);若已建立如圖所示的單向鏈表：則以下不能將s所指的結(jié)點(diǎn)插入到鏈表尾部，構(gòu)成新的單向鏈表的語(yǔ)句組是(D)。A.s一>next二a—〉next一>next;a—〉next—〉next二sa=a—〉next;a一>next二s;s一>next二NULL

s>next二NULL;a=a ■>next;a一■>next 二s;a =a一>next;s一>next 二a一>next;a—> next二 s一>next ;有如下函數(shù)：Voidfun(structnode*hl,structnode*h2){structnode*t;t=hl;while(t-〉next!='\0')t=t■>next;t->next=h2;}其中形參hl和h2分別指向2個(gè)不同鏈表的第一個(gè)結(jié)點(diǎn)，此函數(shù)的功能是(A)。將鏈表h2接到鏈表hl后 B.將鏈表hl接到鏈表h2后找到鏈表hl的最后一個(gè)結(jié)點(diǎn)由指針?lè)祷?D.將鏈表hl拆分成兩個(gè)鏈表第三章?！觥⑴袛囝}棧是運(yùn)算受限制的線性表。丁在棧空的情況下，不能作出棧操作，否則產(chǎn)生溢出。丁棧一定是順序存儲(chǔ)的線性結(jié)構(gòu)。X空棧就是所有元素都為0的棧。X不管堆棧采用何種存儲(chǔ)結(jié)構(gòu)，只要不為空，就可以任意的刪除數(shù)據(jù)元素。X在c語(yǔ)言中設(shè)順序棧的長(zhǎng)度為MAXLEN，則top=MAXLEN時(shí)表示棧滿。X一個(gè)棧的輸入序列為：A,B,C,D,可以得到輸出序列：C,A,B,D°X二、選擇題設(shè)用一維數(shù)組元素a[1]-a[n]存儲(chǔ)一個(gè)棧，令a[n]為棧底，用整型變量t指示當(dāng)前棧頂位置，a[t]為棧頂元素。當(dāng)從棧中彈出一個(gè)元素時(shí)，變量t的變化為(A)。A.t=t+1 A.t=t+1 B.t=t-1有6個(gè)元素按6、5、4、3、2下可能的出棧序列是(B)。A.1、4、3、5、2、6C.3、l、4、2、6、5C.t不變 D.t=n1的順序進(jìn)棧，進(jìn)棧過(guò)程中可以出棧，則以B.6、5、4、3、2、lD.3、6、5、4、2、l以下敘述中錯(cuò)誤的是(C)。棧是限制存取操作只能在一端進(jìn)行的線性表消除遞歸不是必須使用棧對(duì)同一組輸入序列進(jìn)行合法的入、出棧操作，得到的輸出序列一定相同實(shí)現(xiàn)遞歸必定使用工作棧以下不屬于棧的基本運(yùn)算的是(B)。A.刪除棧頂元素 B.刪除棧底元素 C.判斷棧是否為空 D.將棧置為空若以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)(C)。A.必須判別棧是否滿 B.必須判別棧元素的類型C.必須判別棧是否空 D.不用作任何判別設(shè)入棧序列是1、2、?、n，入棧過(guò)程中不允許中途出棧，則第i個(gè)輸出的元素是(D)。鐵路調(diào)度用“?！?，假設(shè)進(jìn)棧車(chē)廂編隊(duì)序列為“ABC"(進(jìn)棧過(guò)程中可以出棧)，出棧則有許多編隊(duì)序列，以下不可能出現(xiàn)的序列是(D)。"ABC" B."CBA" C."BAC" D."CAB"當(dāng)棧中當(dāng)前元素為n個(gè)，此時(shí)進(jìn)行進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則該棧的最大容量為(C)。A.n/2B.n一1 C.nD.n+1(9)在棧中存取數(shù)據(jù)的原則是(B)。A.先進(jìn)先出B.后進(jìn)先出 C.后進(jìn)后出D.隨意進(jìn)出(10)插入和刪除只能在一端進(jìn)行的線性表，稱為(C)。A.隊(duì)列B.循環(huán)隊(duì)列 C.棧D.循環(huán)棧在棧中，出棧操作的時(shí)間復(fù)雜度為(A)。A.O(l) B.O(log2n) C.O(n) D.O(n2)順序棧為空的判斷條件是(C)。A.top==0 B.top==1 C.top==-1 D.top==m元素A,B,C,D依次進(jìn)棧以后，棧頂元素是(D)A.A B. B C. C D.D順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用(B)存儲(chǔ)棧元素。A.鏈表 B.數(shù)組 C.循環(huán)鏈表 D.變量一個(gè)順序棧一但說(shuō)明，其占用空間的大小(A)。A.已固定 B.可以變動(dòng) C.不能固定 D.動(dòng)態(tài)變化鏈棧LS的示意圖如下，棧頂元素是(A)。第四章隊(duì)列一、判斷題隊(duì)列是限制在兩端進(jìn)行操作的線性表。丁判斷順序隊(duì)列為空的標(biāo)準(zhǔn)是頭指針和尾指針均指向同一個(gè)結(jié)點(diǎn)。丁在鏈隊(duì)列做出隊(duì)操作時(shí)，會(huì)改變front指針的值。丁在循環(huán)隊(duì)列中，若尾指針rear大于頭指針front,其元素個(gè)數(shù)為rear-front0X隊(duì)列是一種“后進(jìn)先出”的線性表。X在單向循環(huán)隊(duì)列中，若頭指針為h,那么p所指的結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是p=hoX二、選擇題若用單鏈表來(lái)表示鏈隊(duì)列，則應(yīng)該選用(B)。A.帶尾指針的非循環(huán)鏈表 B.帶頭指針的非循環(huán)鏈表C.帶尾指針的循環(huán)鏈表 D.帶頭指針的循環(huán)鏈表設(shè)有一個(gè)空隊(duì)列，若進(jìn)入隊(duì)列的序列為1,2,3,4，則合法的出隊(duì)序列是(D)。A.3,2,4,1B.4,2,3,lC.4,3,2,1D.l,2,3,4若利用數(shù)組a[0]—a[n-1]作為一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)頭元素的前一個(gè)位置，r為隊(duì)尾元素的位置，假定隊(duì)中元素的個(gè)數(shù)總是小于n,則當(dāng)前隊(duì)中元素的個(gè)數(shù)為(A)oA.r一f B.n+f一r C.n+r一1 D.(n+r一f)%n棧和隊(duì)列都是(C)。A.順序存儲(chǔ)的線性結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)C.限制存取點(diǎn)的線性結(jié)構(gòu) D.限制存取點(diǎn)的非線性結(jié)構(gòu)以下不屬于隊(duì)列基本運(yùn)算的是(B)。A.A.從隊(duì)尾插入一個(gè)新兀素C.判斷一個(gè)隊(duì)列是否為空從隊(duì)列中刪除第i個(gè)元素讀取隊(duì)頭元素的值在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，會(huì)產(chǎn)生隊(duì)列中有剩余空間，但確不能執(zhí)行入隊(duì)操作的“假溢出”現(xiàn)象，在以下幾種方法中，不能解決假溢出問(wèn)題的是(D)。A.A.采用首尾相接的循環(huán)隊(duì)列B.當(dāng)有元素入隊(duì)時(shí)，將己有元素向隊(duì)頭移動(dòng)當(dāng)有元素出隊(duì)時(shí)，將己有元素向隊(duì)頭移動(dòng)D.申請(qǐng)新的存儲(chǔ)單元存放入隊(duì)元素設(shè)隊(duì)列空間n=40：隊(duì)尾指針rear=6；隊(duì)頭指針front=25，則此循環(huán)隊(duì)列中當(dāng)前元素的數(shù)目是(A)。A.19 B.21 C.11 D.29設(shè)循環(huán)隊(duì)列的隊(duì)首指針用front表示，隊(duì)尾指針用rear表示，則判斷隊(duì)空的條件是(A)A.front==rear B.front+1==rearC.rear+1=front D.rear==0設(shè)循環(huán)隊(duì)列存儲(chǔ)于數(shù)組元素a[1]—a[n]中，其隊(duì)頭和隊(duì)尾指針?lè)謩e用front和rear表示，則判斷隊(duì)滿的條件是(C)。A.(rear一■1)%n==front B.(front+1)%n==rearC.(rear+1)%n==front D.(front一l)%n==rear循環(huán)隊(duì)列的特點(diǎn)之一是不會(huì)產(chǎn)生(D)。A.上溢出 B.下溢出 C.隊(duì)滿 D.假溢出設(shè)用數(shù)組data[m+l]作為循環(huán)隊(duì)列q的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作應(yīng)執(zhí)行的語(yǔ)句是(B)。A.front=front+1; B.front=(front+l)%(m+l);C.rear=(rear+l)%m; D.front=(front+l)%m;在隊(duì)列中存取數(shù)據(jù)應(yīng)遵循的原則是(A)。A.先進(jìn)先出 B.后進(jìn)先出 C.先進(jìn)后出 D.隨意進(jìn)出設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度為(C)。A.O(l) B. O(log2n) C.O(n) D. O(n2)設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表示，若只設(shè)尾指針，則出隊(duì)操作的時(shí)間復(fù)雜度為(C)。A.O(l) B. O(log2n) C.O(n) D. O(n2)隊(duì)列是限定在(D)進(jìn)行操作的線性表。A.中間 B.隊(duì)頭 C.隊(duì)尾 D.端點(diǎn)一個(gè)循環(huán)隊(duì)列一旦說(shuō)明，其占用空間的大小(A)。A.已固定 B.可以變動(dòng) C.不能固定 D.動(dòng)態(tài)變化在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的(A)位置。A.前一個(gè) B.后一個(gè) C.后面 D.當(dāng)前當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最后一個(gè)元素的下標(biāo)為(B)。A.n-2 B. n-1 C. n D.n+1從一個(gè)順序循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，首先需要做的操作是(A)。A.隊(duì)頭指針減1 B.取出隊(duì)頭指針?biāo)傅脑谻.隊(duì)頭指針加1 D.取出隊(duì)尾指針?biāo)傅脑厝?個(gè)元素按A,B,C,D,順序進(jìn)隊(duì)Q，隊(duì)頭元素是(A)。第六章樹(shù)和二叉樹(shù)一、判斷題樹(shù)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)最多只有一個(gè)直接前驅(qū)。丁二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為2，因此二叉樹(shù)是一種特殊的樹(shù)。丁由樹(shù)轉(zhuǎn)化為二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。丁若有一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的前序遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它也一定是這棵二叉樹(shù)的中序遍歷序列中的第一個(gè)結(jié)點(diǎn)。X若一個(gè)樹(shù)葉是某二叉樹(shù)的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它也一定是這棵二叉樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。丁若一個(gè)樹(shù)葉是某二叉樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它也一定是這棵二叉樹(shù)的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。丁若有一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的前序遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它也一定是這棵二叉樹(shù)的后序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。丁在二叉樹(shù)中，具有一個(gè)子女的父結(jié)點(diǎn)，在中序遍歷序列中沒(méi)有后繼結(jié)點(diǎn)。而具有兩個(gè)子女的父結(jié)點(diǎn)，在中序遍歷序列中，它的后繼結(jié)點(diǎn)最多只能有一個(gè)子女結(jié)點(diǎn)。X雖然已知二叉樹(shù)的前序遍歷和中序遍歷序列，但還不能惟一確定出這棵二叉樹(shù)，因?yàn)椴⒉恢蓝鏄?shù)的根結(jié)點(diǎn)是哪一個(gè)。X中序線索二叉樹(shù)的優(yōu)點(diǎn)之一是便于在中序下查找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。丁二叉樹(shù)中一旦插入了結(jié)點(diǎn)，則該二叉樹(shù)就不再是二叉樹(shù)。X用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷存儲(chǔ)結(jié)點(diǎn)。X在滿二叉樹(shù)中，存在度為1的結(jié)點(diǎn)。丁在任意一棵二叉樹(shù)中，終端結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)個(gè)數(shù)加1。丁(15)哈夫曼樹(shù)是帶權(quán)值的樹(shù)，且權(quán)值較大的結(jié)點(diǎn)離根較近。丁前序遍歷序列與中序遍歷序列完全相同的二叉樹(shù)有：空二叉樹(shù)或任一結(jié)點(diǎn)均無(wú)左子樹(shù)的非空二叉樹(shù)。丁中序遍歷序列與后序遍歷序列完全相同的二叉樹(shù)有：空二叉樹(shù)或任一結(jié)點(diǎn)均無(wú)右子樹(shù)的非空二叉樹(shù)。丁前序遍歷序列與后序遍歷序列完全相同的二叉樹(shù)只有空二叉樹(shù)。X完全二叉樹(shù)一定是滿二叉樹(shù)。丁在中序線索二叉樹(shù)中，右線索若不為空，則一定指向其雙親。X在前序遍歷二叉樹(shù)的序列中，任何結(jié)點(diǎn)的子樹(shù)的所有結(jié)點(diǎn)都是直接跟在該結(jié)點(diǎn)之后。V二叉樹(shù)按某種順序線索后，任一結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索。V二叉樹(shù)的前序遍歷中，任意一個(gè)結(jié)點(diǎn)均處于其子樹(shù)結(jié)點(diǎn)的前面。V二、選擇題深度為h的二叉樹(shù)至多有(B)個(gè)結(jié)點(diǎn)。2h B.2h-1 C.2h-1 D.2h-1-1對(duì)于二叉樹(shù)來(lái)說(shuō)，第K層至多有(C)個(gè)結(jié)點(diǎn)。A.2K B.2K-1 C.2K-1 D.2K-1-1結(jié)點(diǎn)前序?yàn)锳BC的不同二叉樹(shù)有(C)種形態(tài)。A.3 B.4 C.5 D.6某二叉樹(shù)的先序遍歷序列為：IJKLMN0,中序遍歷序列為：JLKINM0,則后序遍歷序列為(C)。A.JLKMN0I B.LKNJ0MI C.LKJN0MI D.LKN0JMI

某二叉樹(shù)的后序遍歷序列為：DABEC,中序遍歷序列為：DEBAC,則先序遍歷序列為(D)。A.ACBED B.DECAB C.DEABC D.CEDBA具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為(B)。A.5 B. 6 C.7 D. 8二叉樹(shù)按某種順序線索化后,任一結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索,這種說(shuō)法(B)A.正確 B.錯(cuò)誤 C.不確定 D.都有可能根據(jù)樹(shù)的定義,具有3個(gè)結(jié)點(diǎn)的樹(shù)有(A)種樹(shù)型。A.2 B.3 C.4 D.5樹(shù)最適合用來(lái)表示(D)。A.有序數(shù)據(jù)元素樹(shù)最適合用來(lái)表示(D)。A.有序數(shù)據(jù)元素C.元素之間無(wú)聯(lián)系的數(shù)據(jù)對(duì)于一棵滿二叉樹(shù),m個(gè)樹(shù)葉A.n=h+m B.h+m=2n無(wú)序數(shù)據(jù)元素元素之間有分支層次的關(guān)系n個(gè)結(jié)點(diǎn),深度為h,則(D)。m=h-1 D.n=2h-l一棵n個(gè)結(jié)點(diǎn)的二叉樹(shù),其空指針域的個(gè)數(shù)為(B)。A.n B.n+l C.nT D.不確定任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序(A)。A.不發(fā)生改變 B.發(fā)生改變 C.不能確定 D.以上都不對(duì)A,B為一棵二叉樹(shù)上的兩個(gè)葉子結(jié)點(diǎn),在中序遍歷時(shí),A在B前的條件是(C)。A.A在B的右方B.A是B的祖先 C.A在B的左方 D.A是B的子孫線索二叉樹(shù)是一種(A)結(jié)構(gòu)。A.物理 B.邏輯 C.邏輯和存儲(chǔ) D.線性如果結(jié)點(diǎn)A是結(jié)點(diǎn)B的雙親,而且結(jié)點(diǎn)B有4個(gè)兄弟,則結(jié)點(diǎn)A的度是(D)。A.2 B.3 C.4 D.5設(shè)有一棵二叉樹(shù),其1度結(jié)點(diǎn)有m個(gè),2度結(jié)點(diǎn)有n個(gè),則該二叉樹(shù)的結(jié)點(diǎn)總數(shù)為(D)。A.m+n B.2*m+n C.m+2*n D.m+2*n+l設(shè)有一棵二叉樹(shù),其先序遍歷序列是：ABCDEFG,中序遍歷序列是：CBDAFEG,則該二叉樹(shù)的后序遍歷序列是(A)。A.CDBFGEA B.CDFGBEA C.CDBAFGE D.CDBFEGA設(shè)有一棵樹(shù)的度為4,其中度為1、2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2、1、1,則這棵樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)為(D)。A.5 B.6 C.7 D.8用順序存儲(chǔ)結(jié)構(gòu)將完全二叉樹(shù)的結(jié)點(diǎn)逐層存放在數(shù)組B[n]中，其根結(jié)點(diǎn)從B[1]開(kāi)始存放，若結(jié)點(diǎn)B[i]有子女，則其左孩子結(jié)點(diǎn)應(yīng)是()A.B[2i一l]B.B[2i+l] C.B[2i] D.B[i/2]設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為a,b和c，對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是(C)。A.a B.a+b C.c D.b+c設(shè)有13個(gè)值，由它們組成一棵哈夫曼樹(shù)，則該哈夫曼樹(shù)中結(jié)點(diǎn)個(gè)數(shù)共有(D)。A.13 B.12 C.26 D.25設(shè)電文中出現(xiàn)的字母為A、B、C、D和E，每個(gè)字母在電文中出現(xiàn)的次數(shù)分別為

6,23,3,5和12，按哈夫曼編碼，則字母C的編碼應(yīng)是(D)。A.10B.110C.1110D.1111設(shè)樹(shù)中有一結(jié)點(diǎn)x，在先根序列中的序號(hào)為Pre(x)，在后根序列中的序號(hào)為post(x),若樹(shù)中的結(jié)點(diǎn)x是結(jié)點(diǎn)y的祖先，則下列4個(gè)條件中正確的是(B)。TOC\o"1-5"\h\zA.pre ( x ) < pre ( y )且 post ( x ) < post( y )pre ( x ) < pre ( y )且 post ( x ) > post( y )Pre ( x ) > pre ( y )且 post ( x ) < post( y )Pre ( x ) > pre ( y )且 post ( x ) > Post(y)有關(guān)二叉樹(shù)的下列說(shuō)法正確的是(A)。A.二叉樹(shù)的度為2 B.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2C.一棵二叉樹(shù)的度可以小于2 D.任何一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2已知一棵二叉樹(shù)的先序遍歷序列為EFHIGJK，中序遍歷序列為HFIEJGK，則該二叉樹(shù)根的右子樹(shù)的根是(C)。A.E B.F C.G D.J在完全二叉樹(shù)中，如果一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)，則它沒(méi)有(C)。A.左孩子結(jié)點(diǎn) B.右孩子結(jié)點(diǎn) C.左、右孩子結(jié)點(diǎn) D.左、右孩子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)在一棵非空的二叉樹(shù)的中序遍歷序列中，其根結(jié)點(diǎn)的右邊(A)。A.只有右子樹(shù)上的所有結(jié)點(diǎn) B.只有左子樹(shù)上的所有結(jié)點(diǎn)C.只有右子樹(shù)上的部分結(jié)點(diǎn) D.只有左子樹(shù)上的部分結(jié)點(diǎn)在下列存儲(chǔ)形式中，不是樹(shù)的存儲(chǔ)形式的是(D)。A.雙親表示法 B.孩子鏈表表示法 C.孩子兄弟鏈表表示 D.順序存儲(chǔ)表示法在二叉樹(shù)結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序是(A)A.完全相同 B.先序和中序相同，但與后序不同C.都不相同 D.中序和后序相同，但與先序不同如下圖所示的二叉樹(shù)，按先根次序遍歷得到的序列為(B)。D.HIDJEBFGCAD.D.HIDJEBFGCAD.6D.14由4個(gè)結(jié)點(diǎn)構(gòu)造出的不同的樹(shù)個(gè)數(shù)共有(C)。A.3 B.4 C.5由4個(gè)結(jié)點(diǎn)構(gòu)造出的不同的二叉樹(shù)個(gè)數(shù)共有(C)。A.8 B.10 C.12給定一個(gè)整數(shù)集合｛3,5,6,9,12｝，如圖所示的二叉樹(shù)中(B)是該整數(shù)集合對(duì)應(yīng)的哈夫曼樹(shù)。設(shè)一棵二叉樹(shù)結(jié)點(diǎn)的中序遍歷序列為ABCDEFG，后序遍歷序列為BDCAFGE，則：該二叉樹(shù)結(jié)點(diǎn)的先序遍歷序列為(B)。A.EGFACDB B.EACBDGF C.EAGCFBD D.EGACDFB該二叉樹(shù)對(duì)應(yīng)的樹(shù)林中樹(shù)的棵數(shù)共有(B )。A.1 B.2 C.3 D.4該二叉樹(shù)對(duì)應(yīng)的樹(shù)林結(jié)點(diǎn)的前根次序序列為(B)。A.EGFACDB B.EACBDGF C.EAGCFBDD.EGACDFB在一棵滿二叉樹(shù)中，假設(shè)其葉子結(jié)點(diǎn)數(shù)為n分支數(shù)為B，則有B等于(C)。A.2n一1 B.2n＋1 C.2*(n一1) D.2*(n+1)設(shè)結(jié)點(diǎn)A有左孩子結(jié)點(diǎn)B，右孩子結(jié)點(diǎn)C，則在先序遍歷、中序遍歷和后序遍歷這3種基本遍歷序列中B一定是C的(A)。A.前驅(qū) B.后繼 C.相鄰結(jié)點(diǎn) D.不相鄰結(jié)點(diǎn)第七章圖一、判斷題圖可以沒(méi)有邊，但不能沒(méi)有頂點(diǎn)。丁在有向圖中，〈vl,v2〉與〈v2,v1＞是兩條不同的邊。丁鄰接表只能用于有向圖的存儲(chǔ)。X用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。丁若從某個(gè)頂點(diǎn)開(kāi)始，對(duì)有n個(gè)頂點(diǎn)的有向圖G進(jìn)行深度優(yōu)先遍歷，所得的遍歷序列惟一，則可以斷定其弧數(shù)為n—1。丁有向圖不能進(jìn)行廣度優(yōu)先遍歷。X若一個(gè)無(wú)向圖以頂點(diǎn)vl為起點(diǎn)進(jìn)行深度優(yōu)先遍歷，所得的遍歷序列惟一，則可以惟一確定該圖。丁帶權(quán)圖最小生成樹(shù)是惟一的。丁二、選擇題在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的(C)倍。TOC\o"1-5"\h\zA.1/2 B.1 C.2 D.4在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的(B)倍。A.1/2 B.1 C.2 D.4有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有(B)條邊。A. 14 B. 28 C. 56 D. 112有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有(C)條邊。A. 5 B. 6 C. 7 D. 8有8個(gè)結(jié)點(diǎn)的有向完全圖有(C)條邊。A. 14 B. 28 C. 56 D. 112用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常采用(B)來(lái)實(shí)現(xiàn)算法的。A.棧 B.隊(duì)列 C.樹(shù) D.圖用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常采用(A)來(lái)實(shí)現(xiàn)算法的。A.棧B.隊(duì)列C.樹(shù)D.圖(8)深度優(yōu)先遍歷類似于二叉樹(shù)的(A)。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷(9)廣度優(yōu)先遍歷類似于二叉樹(shù)的(D)。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷(10)任何一個(gè)無(wú)向連通圖的最小生成樹(shù)(B)A.只有一棵B.一棵或多棵C. 定有多棵D.可能不存在(11)生成樹(shù)的構(gòu)造方法只有(B)。A.深度優(yōu)先B.深度優(yōu)先和廣度優(yōu)先C.無(wú)前驅(qū)的頂點(diǎn)優(yōu)先D.無(wú)后繼的頂點(diǎn)優(yōu)先無(wú)向圖頂點(diǎn)v的度是關(guān)聯(lián)于該頂點(diǎn)(B)的數(shù)目A.頂點(diǎn) B.邊 C.序號(hào) D.下標(biāo)對(duì)如下所示的圖，頂點(diǎn)V6的入度為(B)A.0 B.2 C.3 D.5對(duì)如下圖所示的無(wú)向圖G，若從頂點(diǎn)Vl開(kāi)始，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能的訪問(wèn)順序?yàn)?A)。A.VlV2V5V8V4V6V7V3 B.VlV2V3V4V5V6V7V8C.VIV2V3V4V8V5V6V7 D.VlV2V4V5V8V3V6V7對(duì)如圖所示的無(wú)向圖，若從頂點(diǎn)V1開(kāi)始，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能訪問(wèn)的順序?yàn)?D)。A.VIV2V3V4V5V6V7V8 B.VIV2V6V3V4V7V8V5C.VIV2V6V3V4V5V7V8 D.VIV2V4V7V3V8V6V5對(duì)如圖所示的有向圖G,它的拓?fù)湫蛄惺?C)。A.a,b,c,dB.a,d,b,cC.a,b,d,c D.b,a,d,c在有向圖G的拓?fù)湫蛄兄?，如果頂點(diǎn)vi在vj之前，則在下列情況中一定不可能出現(xiàn)的是(D)。A.G中有弧Vvi,vj> B.G中有一條從Vi到vj的路徑C.G中沒(méi)有弧VVi,vj〉 D.G中有一條從vj到Vi的路徑對(duì)如下所示的圖，它的生成樹(shù)有(C)棵。A.1 B.5 C.6 D不確定下面哪一種圖的鄰接矩陣肯定是對(duì)稱矩陣(B)。A.有向圖 B.無(wú)向圖 C.AOV網(wǎng) D.AOE網(wǎng)如圖所示的有向圖的頂點(diǎn)可以排成(C)個(gè)不同的拓?fù)湫蛄?。A．3 B．5 C.7 D.9下面關(guān)于圖的存儲(chǔ)的敘述中正確的是(A)。用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊表無(wú)關(guān)。用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖的邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)。用鄰接表存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)。用鄰接表存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)。在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的(B)。A.1倍 B.2倍 C.1/2倍 D.不確定第八章查找一、判斷題二分查找法要求待查表的關(guān)鍵字的值必須有序。丁哈希法是一種將關(guān)鍵字轉(zhuǎn)換為存儲(chǔ)地址的存儲(chǔ)方法。丁在二叉排序樹(shù)中，根結(jié)點(diǎn)的值都小于孩子結(jié)點(diǎn)的值。X對(duì)有序表而言，采用二分查找總比采用順序查找法速度快。丁二叉排序樹(shù)是一種特殊的線性表。X哈希表的查找效率主要取決于哈希表構(gòu)造時(shí)選取的哈希函數(shù)和處理沖突的方法。丁一般來(lái)說(shuō)，用哈希函數(shù)得到的地址，沖突不可能避免，只能盡可能減少。丁對(duì)于滿足二分查找和分塊查找條件的文件而言，無(wú)論它存放在何種介質(zhì)上，均能進(jìn)行順序查找，折半查找和分塊查找。X對(duì)于同一組待輸入的關(guān)鍵值集合，雖然各關(guān)鍵值的輸入順序不同，但得到的二叉排序樹(shù)是相同的。X對(duì)于兩棵具有相同數(shù)據(jù)元素而形狀不同的二叉排序樹(shù)，按中序遍歷它們得到的數(shù)據(jù)元素的排列次序是一樣的。丁在二叉排序樹(shù)中插入新結(jié)點(diǎn)時(shí)，不必移動(dòng)其他結(jié)點(diǎn)，僅需改動(dòng)某個(gè)結(jié)點(diǎn)的指針，使它由空變?yōu)榉强占纯伞６≡诙媾判驑?shù)上刪除一個(gè)結(jié)點(diǎn)時(shí)，不必移動(dòng)其他結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)相應(yīng)的指針域置空即可。X平衡的二叉排序樹(shù)的任何子樹(shù)都是平衡的二叉排序樹(shù)。丁只有最下面的兩層結(jié)點(diǎn)的度數(shù)可以小于2，其他結(jié)點(diǎn)的度數(shù)必須等于2的二叉樹(shù)才是平衡的二叉樹(shù)。X任意一棵二叉排序樹(shù)的平均查找時(shí)間都小于用順序查找算法搜索同一結(jié)點(diǎn)的順序表的平均查找時(shí)間。X二、選擇題查找表是以(A)為查找結(jié)構(gòu)的。A.集合 B.圖 C.樹(shù) D.文件順序查找法適合于存儲(chǔ)結(jié)構(gòu)為(B)的線性表。A.哈希存儲(chǔ) B.順序存儲(chǔ)或鏈接存儲(chǔ)C.壓縮存儲(chǔ) D.索引存儲(chǔ)對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須(D)。A.以順序方式存儲(chǔ) B.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序C.以鏈接方式存儲(chǔ) D.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字序排序采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為(C)。A.n B.n/2 C.(n+l)/2 D.(n-l)/2采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為(D)。A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)有l(wèi)個(gè)有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，(C)次比較后查找成功。A.2 B.3 C.4 D.5設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)H(key)=key%11。表中已有4個(gè)結(jié)點(diǎn)：add(15)=4add(38)=5add(61)=6add(84)=7

其余地址為空。如用二次探測(cè)再哈希處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是(D)。A.8B.3C.5D.9有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為(B)。A.35/12B.37/12C.39/12D.43/12如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用()查找方法。A.分塊 B.順序 C.二分 D.哈希采用分塊查找時(shí)，若線性表共有625個(gè)元素，查找每個(gè)元素的概率相等，假設(shè)采用順序查找來(lái)確定結(jié)點(diǎn)所在的塊時(shí)，每塊分()個(gè)結(jié)點(diǎn)最佳。A.6 B.10 C.25 D.625100個(gè)元素采用二分查找時(shí)，最大的比較次數(shù)是(C)。A.25 B.50 C.7 D.10衡量查找算法效率的主要標(biāo)準(zhǔn)是(B)。A.元素個(gè)數(shù) B.平均查找長(zhǎng)度 C.所需的存儲(chǔ)量 D.算法難易程度為了有效地利用散列查找技術(shù)，需要解決的問(wèn)題是(B)。找一個(gè)好的散列函數(shù)設(shè)計(jì)有效的解決沖突的方法用整數(shù)表示關(guān)鍵碼值A(chǔ).①和③ B.①和② C.②和③ D.全部設(shè)有一個(gè)已按元素值排好序的線性表，長(zhǎng)度大于2，對(duì)于給定的關(guān)鍵字值k，分別用順序查找和折半查找算法查找一個(gè)關(guān)鍵字值與k相等的元素，比較的次數(shù)分別記為s和b,在查找不成功的情況下，正確的數(shù)量關(guān)系是(B)。A.總有s=b B總有s>b C總有s<b D.與k值大小有關(guān)散列表的地址區(qū)間為0一16，散列函數(shù)為Hl(K)=K%17，采用線性探測(cè)法解決沖突，將關(guān)鍵字序列26,25,72,38,8,18,59依次存儲(chǔ)到散列表中。①元素59存放在散列表中的地址為(D)。A.8A.8B.9C.10②查找元素59，需要比較的次數(shù)為(C)。A.2B.3C.4D.11D.5對(duì)包含n個(gè)元素的散列表進(jìn)行檢索，平均檢索長(zhǎng)度為(D)。A.O(log2n)A.O(log2n)B.O(nlog2n)C.O(n)D不直接依賴于n對(duì)于具有144個(gè)記錄的文件，若采用分塊查找法，并采用折半查找法確定塊，且每塊長(zhǎng)度為8，則查找成功時(shí)的平均查找長(zhǎng)度為(B)。A.143 B.14 C.13 D.9具有4層結(jié)點(diǎn)的二叉平衡樹(shù)中結(jié)點(diǎn)個(gè)數(shù)至少有(D)。A.16 B.15 C.8 D.7在如下圖所示的四棵二叉樹(shù)中，屬于平衡二叉樹(shù)的是(B).

第九章排序一、判斷題大多數(shù)排序算法都有比較關(guān)鍵字大小和改變指向記錄的指針或移動(dòng)記錄本身兩種基本操作。丁快速排序在任何情況下都比其他排序方法速度快。X快速排序算法在每一趟排序中都能找到一個(gè)元素放在其最終位置上。丁如果某種排序算法不穩(wěn)定，則該排序方法就沒(méi)有實(shí)際應(yīng)用價(jià)值。X⑸對(duì)n個(gè)記錄的進(jìn)行快速排序，所需要的平均時(shí)間是0(nlog2n)°J⑹冒泡排序是不穩(wěn)定的排序。X堆排序所需的時(shí)間與待排序的記錄個(gè)數(shù)無(wú)關(guān)。X當(dāng)待排序的元素個(gè)數(shù)很多時(shí)，為了交換元素的位置要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜度的主要因素。X對(duì)快速排序來(lái)說(shuō)，初始序列為正序或反序都是最壞的情況。丁二、選擇題A. 1 , 2 , 3 , 4 , 5C. 3 , l , 2 , 4 , 5對(duì)以下幾個(gè)關(guān)鍵字序列進(jìn)行快速排序A. 4 , l , 2 , 3 , 6 , 5 , 7C. 4 , 2 , l , 3 , 6 , 7 , 5對(duì)以下幾個(gè)關(guān)鍵字序列進(jìn)行快速排序A. A. 1 , 2 , 3 , 4 , 5C. 3 , l , 2 , 4 , 5對(duì)以下幾個(gè)關(guān)鍵字序列進(jìn)行快速排序A. 4 , l , 2 , 3 , 6 , 5 , 7C. 4 , 2 , l , 3 , 6 , 7 , 5對(duì)以下幾個(gè)關(guān)鍵字序列進(jìn)行快速排序A. 2 , 3 , l , 4 ,C. 2 , l , 3 , 4 ,堆排序?qū)儆?CA.插入排序6,56,7）。B.交換排序B.2,l,D.5,3,以第一個(gè)元素為軸，B.4,3,D.l,2,3,4,5l,2,4一次劃分效果不好的是（D）。l,7,6,3,4,5,每次劃分效果都好的是（B4,3,l4,1,2B.D.）。6,5,假設(shè)待排序數(shù)據(jù)元素序列為［4,2,己知一趟的結(jié)果為［)。B.直接選擇C.,1,82,4法進(jìn)行按遞增序排序，選用的排序方法為(CA.冒泡(從后向前)樞軸)(9)設(shè)待排序數(shù)據(jù)元素序列為［4,l,2,3］C.選擇排序,7,6,1,3,7,二路歸并排序D.歸并排序

］，應(yīng)用一種排序方5,6,9］，則所D.快速(以2為應(yīng)用一種排序方法進(jìn)行遞增序排序，已(1)假設(shè)待排序數(shù)據(jù)元素序列的關(guān)鍵字序列為2,1,2'，應(yīng)用選擇排序方法排降序得到的結(jié)果為(C)。A.2',2,1 B.1,2',2C.2,2',1 D.l,2,2'(2)假設(shè)待排序數(shù)據(jù)元素序列的關(guān)鍵字序列為1,2,2',1'，應(yīng)用冒泡(插入、歸并)排序方法按遞增序排序得到的結(jié)果為(A)。A.1,l',2,2'B.1,1',2',2C.l',l,2,2'D.1',1,2',2快速排序每次劃分的效果好壞和以下何種因素有直接關(guān)系(C)。A.關(guān)鍵字的排列情況 B.數(shù)據(jù)元素的個(gè)數(shù) C.軸的相對(duì)大小 D.關(guān)鍵字值的最大值對(duì)以下幾個(gè)關(guān)鍵字序列進(jìn)行快速排序，以第一個(gè)元素為軸，一次劃分效果最好的是(C)。知兩趟后的結(jié)果為［1,2,3,4］，則所選用的排序方法為(C)。A.直接插入 B.直接選擇 C.冒泡(從前向后)D.冒泡(從后向前）（10）設(shè)待排序數(shù)據(jù)元素序列為［2,4,1,3,7,1'］，應(yīng)用一種排序方法進(jìn)行遞增序排序，已知最終的結(jié)果為［1',1,2,3,4,7，］則所選用的排序方法為（B）。A.直接插入 B.直接選擇 C.冒泡（從前向后） D.二路歸并（11） 設(shè)待排序數(shù)據(jù)元素序列有n個(gè)記錄，應(yīng)用直接插入排序方法，進(jìn)行一趟排序，所需比較和移動(dòng)記錄的最少次數(shù)分別為（A）。A.1、2 B.2、1 C.1、1 D.2、2（12） 假設(shè)待排序數(shù)據(jù)元素序列有n個(gè)記錄，應(yīng)用冒泡排序方法，進(jìn)行一趟排序，所需比較和移動(dòng)記錄的最少次數(shù)分別為（C）。A.1、2 B.n一1、1 C.n一l、0 D.n一l、n一1（13） 設(shè)待排序數(shù)據(jù)元素序列有n個(gè)記錄，應(yīng)用冒泡排序方法，進(jìn)行一趟排序，所需比較和交換記錄的最多次數(shù)分別為（D）。A.n、n B.n一1、n C.n一l、0 D.n一l、n一1（14） 設(shè)待排序數(shù)據(jù)元素序列有n個(gè)記錄，應(yīng)用快速排序方法，進(jìn)行一次劃分，所需比較和移動(dòng)記錄的最少次數(shù)分別為（C）。A.1、1