數(shù)據(jù)結構(客觀題)

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

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

在n個結點的順序表中，算法的時間復雜度是0(1)的操作是(B)。訪問第i個結點(1WiWn)和求第i個結點的直接前驅(2WiWn)在第i個結點之后插入一個新結點(1WiWn-1)刪除第i個結點(1WiWn)將n個結點從小到大排序在線性表中(B)只有一個直接前驅和一個直接后繼。A.A.首元素 B.中間元素對具有n個結點的線性表進行查找運算A.0(n2) B.0(nlog2n)線性表采用順序存儲的缺點是(D)。A.存儲密度降低元素的邏輯順序與物理順序不一致尾元素 D.所有元素所需的算法時間復雜度為(D)。0(log2n) D.0(n)只能順序訪問插入、刪除操作效率低以下鏈表結構中，從當前結點出發(fā)能夠訪問到任一結點的是(B)A以下鏈表結構中，從當前結點出發(fā)能夠訪問到任一結點的是(B)A.單向鏈表和雙向鏈表C.單向鏈表和循環(huán)鏈表雙向鏈表和循環(huán)鏈表單向鏈表、雙向鏈表和循環(huán)鏈表線性表是具有n個(B)的有限序列。A.數(shù)據(jù)項 A.數(shù)據(jù)項 B.數(shù)據(jù)元素C.表元素D.字符若長度為n的線性表采用鏈式存儲結構，訪問其第i個元素的算法時間復雜度(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)不帶頭結點B.P—〉prior==L勺單鏈表L為空的條件是(B)C.P==NULLD.P—>next==LA.L!=NULLB.L==NULLC.L—>next==NULLD.L—>next==L(21)帶頭結點的單鏈表L為空的條件是(C)A.L!=NULLB.L==NULLC.L—>next==NULLD.L—>next==L兩個指針P和Q，分別指向單鏈表的兩個元素，P所指元素是Q所指元素前驅的條件是(B)。A.P—〉next==Q—〉nextB.P—〉next==Q C.Q—〉next==P D.P==Q在長度為n的順序表中，若要刪除第i(1WiWn)個元素，則需要向前移動元素的次數(shù)為(B)。A.1 B.n一i C.n一i+1 D.n一i一l在長度為n的順序表中第i(1WiWn)個位置上插入一個元素時，為留出插入位置所需移動元素的次數(shù)為(C)。A.n—i B.iA.n—i B.iC.n—i+1D.n—i—l假定己建立以下動態(tài)鏈表結構，且指針Pl和P2已指向如圖所示的結點：則以下可以將P2所指結點從鏈表中刪除并釋放該結點的語句組是(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所指的結點插入到鏈表尾部，構成新的單向鏈表的語句組是(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個不同鏈表的第一個結點，此函數(shù)的功能是(A)。將鏈表h2接到鏈表hl后 B.將鏈表hl接到鏈表h2后找到鏈表hl的最后一個結點由指針返回 D.將鏈表hl拆分成兩個鏈表第三章棧■、判斷題棧是運算受限制的線性表。丁在?？盏那闆r下，不能作出棧操作，否則產(chǎn)生溢出。丁棧一定是順序存儲的線性結構。X空棧就是所有元素都為0的棧。X不管堆棧采用何種存儲結構，只要不為空，就可以任意的刪除數(shù)據(jù)元素。X在c語言中設順序棧的長度為MAXLEN，則top=MAXLEN時表示棧滿。X一個棧的輸入序列為：A,B,C,D,可以得到輸出序列：C,A,B,D°X二、選擇題設用一維數(shù)組元素a[1]-a[n]存儲一個棧，令a[n]為棧底，用整型變量t指示當前棧頂位置，a[t]為棧頂元素。當從棧中彈出一個元素時，變量t的變化為(A)。A.t=t+1 A.t=t+1 B.t=t-1有6個元素按6、5、4、3、2下可能的出棧序列是(B)。A.1、4、3、5、2、6C.3、l、4、2、6、5C.t不變 D.t=n1的順序進棧，進棧過程中可以出棧，則以B.6、5、4、3、2、lD.3、6、5、4、2、l以下敘述中錯誤的是(C)。棧是限制存取操作只能在一端進行的線性表消除遞歸不是必須使用棧對同一組輸入序列進行合法的入、出棧操作，得到的輸出序列一定相同實現(xiàn)遞歸必定使用工作棧以下不屬于棧的基本運算的是(B)。A.刪除棧頂元素 B.刪除棧底元素 C.判斷棧是否為空 D.將棧置為空若以鏈表作為棧的存儲結構，則退棧操作時(C)。A.必須判別棧是否滿 B.必須判別棧元素的類型C.必須判別棧是否空 D.不用作任何判別設入棧序列是1、2、?、n，入棧過程中不允許中途出棧，則第i個輸出的元素是(D)。鐵路調(diào)度用“?！?，假設進棧車廂編隊序列為“ABC"(進棧過程中可以出棧)，出棧則有許多編隊序列，以下不可能出現(xiàn)的序列是(D)。"ABC" B."CBA" C."BAC" D."CAB"當棧中當前元素為n個，此時進行進棧運算時發(fā)生上溢，則該棧的最大容量為(C)。A.n/2B.n一1 C.nD.n+1(9)在棧中存取數(shù)據(jù)的原則是(B)。A.先進先出B.后進先出 C.后進后出D.隨意進出(10)插入和刪除只能在一端進行的線性表，稱為(C)。A.隊列B.循環(huán)隊列 C.棧D.循環(huán)棧在棧中，出棧操作的時間復雜度為(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依次進棧以后，棧頂元素是(D)A.A B. B C. C D.D順序棧存儲空間的實現(xiàn)使用(B)存儲棧元素。A.鏈表 B.數(shù)組 C.循環(huán)鏈表 D.變量一個順序棧一但說明，其占用空間的大小(A)。A.已固定 B.可以變動 C.不能固定 D.動態(tài)變化鏈棧LS的示意圖如下，棧頂元素是(A)。第四章隊列一、判斷題隊列是限制在兩端進行操作的線性表。丁判斷順序隊列為空的標準是頭指針和尾指針均指向同一個結點。丁在鏈隊列做出隊操作時，會改變front指針的值。丁在循環(huán)隊列中，若尾指針rear大于頭指針front,其元素個數(shù)為rear-front0X隊列是一種“后進先出”的線性表。X在單向循環(huán)隊列中，若頭指針為h,那么p所指的結點為尾結點的條件是p=hoX二、選擇題若用單鏈表來表示鏈隊列，則應該選用(B)。A.帶尾指針的非循環(huán)鏈表 B.帶頭指針的非循環(huán)鏈表C.帶尾指針的循環(huán)鏈表 D.帶頭指針的循環(huán)鏈表設有一個空隊列，若進入隊列的序列為1,2,3,4，則合法的出隊序列是(D)。A.3,2,4,1B.4,2,3,lC.4,3,2,1D.l,2,3,4若利用數(shù)組a[0]—a[n-1]作為一個循環(huán)隊列，f為當前隊頭元素的前一個位置，r為隊尾元素的位置，假定隊中元素的個數(shù)總是小于n,則當前隊中元素的個數(shù)為(A)oA.r一f B.n+f一r C.n+r一1 D.(n+r一f)%n棧和隊列都是(C)。A.順序存儲的線性結構 B.鏈式存儲的線性結構C.限制存取點的線性結構 D.限制存取點的非線性結構以下不屬于隊列基本運算的是(B)。A.A.從隊尾插入一個新兀素C.判斷一個隊列是否為空從隊列中刪除第i個元素讀取隊頭元素的值在隊列的順序存儲結構中，會產(chǎn)生隊列中有剩余空間，但確不能執(zhí)行入隊操作的“假溢出”現(xiàn)象，在以下幾種方法中，不能解決假溢出問題的是(D)。A.A.采用首尾相接的循環(huán)隊列B.當有元素入隊時，將己有元素向隊頭移動當有元素出隊時，將己有元素向隊頭移動D.申請新的存儲單元存放入隊元素設隊列空間n=40：隊尾指針rear=6；隊頭指針front=25，則此循環(huán)隊列中當前元素的數(shù)目是(A)。A.19 B.21 C.11 D.29設循環(huán)隊列的隊首指針用front表示，隊尾指針用rear表示，則判斷隊空的條件是(A)A.front==rear B.front+1==rearC.rear+1=front D.rear==0設循環(huán)隊列存儲于數(shù)組元素a[1]—a[n]中，其隊頭和隊尾指針分別用front和rear表示，則判斷隊滿的條件是(C)。A.(rear一■1)%n==front B.(front+1)%n==rearC.(rear+1)%n==front D.(front一l)%n==rear循環(huán)隊列的特點之一是不會產(chǎn)生(D)。A.上溢出 B.下溢出 C.隊滿 D.假溢出設用數(shù)組data[m+l]作為循環(huán)隊列q的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作應執(zhí)行的語句是(B)。A.front=front+1; B.front=(front+l)%(m+l);C.rear=(rear+l)%m; D.front=(front+l)%m;在隊列中存取數(shù)據(jù)應遵循的原則是(A)。A.先進先出 B.后進先出 C.先進后出 D.隨意進出設長度為n的鏈隊列用單循環(huán)鏈表表示，若只設頭指針，則入隊操作的時間復雜度為(C)。A.O(l) B. O(log2n) C.O(n) D. O(n2)設長度為n的鏈隊列用單循環(huán)鏈表示，若只設尾指針，則出隊操作的時間復雜度為(C)。A.O(l) B. O(log2n) C.O(n) D. O(n2)隊列是限定在(D)進行操作的線性表。A.中間 B.隊頭 C.隊尾 D.端點一個循環(huán)隊列一旦說明，其占用空間的大小(A)。A.已固定 B.可以變動 C.不能固定 D.動態(tài)變化在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的(A)位置。A.前一個 B.后一個 C.后面 D.當前當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最后一個元素的下標為(B)。A.n-2 B. n-1 C. n D.n+1從一個順序循環(huán)隊列中刪除一個元素時，首先需要做的操作是(A)。A.隊頭指針減1 B.取出隊頭指針所指的元素C.隊頭指針加1 D.取出隊尾指針所指的元素若4個元素按A,B,C,D,順序進隊Q，隊頭元素是(A)。第六章樹和二叉樹一、判斷題樹結構中每個結點最多只有一個直接前驅。丁二叉樹中每個結點的度最大為2，因此二叉樹是一種特殊的樹。丁由樹轉化為二叉樹，其根結點的右子樹總是空的。丁若有一個結點是某二叉樹的前序遍歷序列中的第一個結點，則它也一定是這棵二叉樹的中序遍歷序列中的第一個結點。X若一個樹葉是某二叉樹的前序遍歷序列中的最后一個結點，則它也一定是這棵二叉樹的中序遍歷序列中的最后一個結點。丁若一個樹葉是某二叉樹的中序遍歷序列中的最后一個結點，則它也一定是這棵二叉樹的前序遍歷序列中的最后一個結點。丁若有一個結點是某二叉樹的前序遍歷序列中的第一個結點，則它也一定是這棵二叉樹的后序遍歷序列中的最后一個結點。丁在二叉樹中，具有一個子女的父結點，在中序遍歷序列中沒有后繼結點。而具有兩個子女的父結點，在中序遍歷序列中，它的后繼結點最多只能有一個子女結點。X雖然已知二叉樹的前序遍歷和中序遍歷序列，但還不能惟一確定出這棵二叉樹，因為并不知道二叉樹的根結點是哪一個。X中序線索二叉樹的優(yōu)點之一是便于在中序下查找前驅結點和后繼結點。丁二叉樹中一旦插入了結點，則該二叉樹就不再是二叉樹。X用一維數(shù)組存儲二叉樹時，總是以前序遍歷存儲結點。X在滿二叉樹中，存在度為1的結點。丁在任意一棵二叉樹中，終端結點的個數(shù)等于度為2的結點個數(shù)加1。丁(15)哈夫曼樹是帶權值的樹，且權值較大的結點離根較近。丁前序遍歷序列與中序遍歷序列完全相同的二叉樹有：空二叉樹或任一結點均無左子樹的非空二叉樹。丁中序遍歷序列與后序遍歷序列完全相同的二叉樹有：空二叉樹或任一結點均無右子樹的非空二叉樹。丁前序遍歷序列與后序遍歷序列完全相同的二叉樹只有空二叉樹。X完全二叉樹一定是滿二叉樹。丁在中序線索二叉樹中，右線索若不為空，則一定指向其雙親。X在前序遍歷二叉樹的序列中，任何結點的子樹的所有結點都是直接跟在該結點之后。V二叉樹按某種順序線索后，任一結點均有指向其前驅和后繼的線索。V二叉樹的前序遍歷中，任意一個結點均處于其子樹結點的前面。V二、選擇題深度為h的二叉樹至多有(B)個結點。2h B.2h-1 C.2h-1 D.2h-1-1對于二叉樹來說，第K層至多有(C)個結點。A.2K B.2K-1 C.2K-1 D.2K-1-1結點前序為ABC的不同二叉樹有(C)種形態(tài)。A.3 B.4 C.5 D.6某二叉樹的先序遍歷序列為：IJKLMN0,中序遍歷序列為：JLKINM0,則后序遍歷序列為(C)。A.JLKMN0I B.LKNJ0MI C.LKJN0MI D.LKN0JMI

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

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

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

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

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