數(shù)據(jù)結(jié)構(gòu)期末測(cè)試題及答案

1、數(shù)據(jù)結(jié)構(gòu)期末測(cè)試題及答案1線性表是具有n個(gè)( )的有限序列。 A、數(shù)據(jù)表B、字符C、數(shù)據(jù)元素(正確答案)D、數(shù)據(jù)項(xiàng)2在線性表中,除開(kāi)始元素外,每個(gè)元素( )。 A、只有唯一的前趨元素(正確答案)B、只有唯一的后繼元素C、有多個(gè)前趨元素D、有多個(gè)后繼元素3下述( )是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)。 A、存儲(chǔ)密度大(正確答案)B、插入運(yùn)算方便C、刪除運(yùn)算方便D、方便地運(yùn)用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示4線性表的順序存儲(chǔ)結(jié)構(gòu)是一種( )。 A、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)(正確答案)B、順序存取的存儲(chǔ)結(jié)構(gòu)C、索引存取的存儲(chǔ)結(jié)構(gòu)D、散列存取的存儲(chǔ)結(jié)構(gòu)5一個(gè)順序表所占用的存儲(chǔ)空間大小與( )無(wú)關(guān)。 A、表的長(zhǎng)度B、元素的存放順序

2、(正確答案)C、元素的類型D、元素中各字段的類型6在n個(gè)元素的線性表的數(shù)組表示中,時(shí)間復(fù)雜度為0(1)的操作是( )。I. 訪問(wèn)第i(1in)個(gè)結(jié)點(diǎn)和求第i (2in)個(gè)結(jié)點(diǎn)的直接前驅(qū)II. 在最后一個(gè)結(jié)點(diǎn)后插入一個(gè)新的結(jié)點(diǎn) III.刪除第1個(gè)結(jié)點(diǎn)IV. 在第i(1in)個(gè)結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn) A、IB、II、IIIC、I、II(正確答案)D、I、II、III7在一個(gè)長(zhǎng)度為n的順序表中刪除第i(Ii=MaxSizeC、Q.front=(Q.rear+1) % MaxSize(正確答案)D、Q.rear=(Q.front+1) % MaxSize9用鏈?zhǔn)酱鎯?chǔ)方式的隊(duì)列進(jìn)行刪除操作時(shí)需要( )。 A

3、、僅修改尾指針B、僅修改頭指針C、頭尾指針可能都要修改(正確答案)D、頭尾指針都要修改10在一個(gè)鏈隊(duì)列中, 假設(shè)隊(duì)頭指針為front,隊(duì)尾指針為rear,x所指向的元素需要入隊(duì),則需要執(zhí)行的操作為( )。 A、front=x, front=front.nextB、x.next=front.next,front=xC、rear.next=x, rear=xD、rear.next=x,x.next=null,rear=x(正確答案)11數(shù)組Qn用來(lái)表示一個(gè)循環(huán)隊(duì)列,f為當(dāng)前隊(duì)列頭元素的前一位置,r為隊(duì)尾元素的位置,假定隊(duì)列中元素的個(gè)數(shù)小于n,計(jì)算隊(duì)列中元素的公式為 A、r-fB、(n+f-r)%

4、nC、n+r-fD、(n+r-f)% n(正確答案)12【判斷題】棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。_13【判斷題】棧和隊(duì)列的存儲(chǔ)方式既可是順序方式,也可是鏈接方式_14【判斷題】隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表,是一種先進(jìn)后出型結(jié)構(gòu)。 棧和隊(duì)列綜合應(yīng)用已完成(正確答案)1下列關(guān)于棧的敘述中,錯(cuò)誤的是( )。I. 采用非遞歸方式重寫遞歸程序時(shí)必須使用棧 II. 函數(shù)調(diào)用時(shí),系統(tǒng)要用棧保存必要的信息 III.只要確定了入棧次序,即可確定出棧次序 IV.棧是一種受限的線性表,允許在其兩端進(jìn)行操作 A、僅IB、僅I、II、IIIC、僅I、III、IV(正確答案)D、僅II、III、IV2

5、若棧S1中保存整數(shù),棧S2中保存運(yùn)算符,函數(shù)F()依次執(zhí)行下述各步操作:_1)從S1中依次彈出兩個(gè)操作數(shù)a和b. _2)從S2中彈出一個(gè)運(yùn)算符op._3)執(zhí)行相應(yīng)的運(yùn)算b op a._4)將運(yùn)算結(jié)果壓入S1中假定S1中的操作數(shù)依次是5, 8,3,2(2在棧頂),s2中的運(yùn)算符依次是 、-、+(+在棧頂)。調(diào)用3次F()后,s1棧頂保存的值是( )。 A、-15B、15(正確答案)C、-20D、203已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A0.n-1中, 且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時(shí)隊(duì)列為空,且要 求第一個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A0處,則初始時(shí)front和rear的值分

6、別是( )。 A、0 , 0B、0 , n-1(正確答案)C、n-1 , 0D、n-1 , n-14循環(huán)隊(duì)列放在一維教組A0. M-1中，end1指向隊(duì)頭元素，end2指向隊(duì)尾元素的后一個(gè)位置，假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容的M-1個(gè)元素。初始時(shí)為空，下列判斷隊(duì)空和隊(duì)滿的條件中，正確的是( )。 A、隊(duì)空:end1=end2 隊(duì)滿:end1=(end2+1)mod M(正確答案)B、隊(duì)空:end1=end2 隊(duì)滿:end2=(end1+1)mod (M-1)C、隊(duì)空:end2=(end1+1)mod M 隊(duì)滿:end1=(end2+1)mod MD、隊(duì)空:end1=(end

7、2+1)mod M 隊(duì)滿:end2=(end1+1)mod (M-1)5現(xiàn)有隊(duì)列Q與棧S,初始時(shí)Q中的元素依次是1,2,3,4,5,6(1在隊(duì)頭),S為空。若僅允許下列3種操作: 出隊(duì)并輸出出隊(duì)元素: 出隊(duì)并將出隊(duì)元素入棧; 出棧并輸出出棧元素。 則不能得到的輸出序列是( )。 A、1,2,5,6,4,3B、2,3,4,5,6,1C、3,4,5,6,1,2(正確答案)D、6,5,4,3,2,16若已知一個(gè)棧的入棧序列是1,2,3,n,其輸出序列為p1,p2,p3,pn,若p1=n,則pi為 A、iB、n-iC、n-i+1(正確答案)D、不確定7設(shè)棧的初始狀態(tài)為空, 當(dāng)字符序列 “n1_”作為棧

8、的輸入時(shí),輸出長(zhǎng)度為3,且可用做C語(yǔ)言標(biāo)識(shí)符的序列有( )個(gè)。 A、4B、5C、3(正確答案)D、68元素a,b,c,d,e依次進(jìn)入初始為空的棧中,若元素進(jìn)棧后可停留、可出棧,直到所有元素都出棧,則在所有可能的出棧序列中,以元素d開(kāi)頭的序列個(gè)數(shù)是( )。 A 3B 4(正確答案)C 5D 69若元素a,b,c,d,e,f依次進(jìn)棧,允許進(jìn)棧、退棧操作交替 進(jìn)行,但不允許連續(xù)3次進(jìn)行退棧操作,不可能得到的出棧序列是( )。 A、dcebfaB、cbdaefC、bcaefdD、afedcb(正確答案)10設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空,元素abcdefg依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q,

9、且7個(gè)元素出隊(duì)的順序是bdcfeag,則棧S的容量至少是( )。 A、1B、2C、3(正確答案)D、411一個(gè)棧的輸入序列為1,2,3,.,n ,輸出序列的第一個(gè)元素是i,則第j個(gè)輸出元素是( )。 A、i-j-1B、i-jC、j-i+1D、不確定(正確答案)12某棧的輸入序列為a,b,c,d, 下面的4個(gè)序列中,不可能為其輸出序列的是( )。 A、a,b,c,dB、c,b,d,aC、d,c,a,b(正確答案)D、a,c,b,d13若一個(gè)棧用該數(shù)組data1.n存儲(chǔ)，初始棧頂指針top為1，則以下元素x進(jìn)棧的正確操作是。 A、top+;datatop=x;B、datatop=x;top+;(正

10、確答案)C、top-;datatop=x;D、datatop=x;top-;14【判斷題】通常使用隊(duì)列來(lái)處理函數(shù)或過(guò)程的調(diào)用。_15判斷題】棧是實(shí)現(xiàn)過(guò)程和函數(shù)等子程序所必需的結(jié)構(gòu)。_16【判斷題】棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。_17【判斷題】隊(duì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。_18【判斷題】循環(huán)隊(duì)列也存在空間溢出問(wèn)題。_19【判斷題】 棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞健?正確答案)樹(shù)與二叉樹(shù)測(cè)試（1）樹(shù)基礎(chǔ)已完成1樹(shù)最適合用來(lái)表示( )的數(shù)據(jù)。 A、有序B、無(wú)序C、任意元素之間具有多種聯(lián)系D、元素之間具有分支層次關(guān)系(正確答案)2對(duì)于一棵具有n個(gè)結(jié)點(diǎn)

11、、度為4的樹(shù)來(lái)說(shuō),( ) A、樹(shù)的高度至多是n-3(正確答案)B、樹(shù)的高度至多是n-4C、第i層上至多有4(i-1)個(gè)結(jié)點(diǎn)D、至少在某一層上正好有4個(gè)結(jié)點(diǎn)3一棵有n個(gè)結(jié)點(diǎn)的樹(shù)的所有結(jié)點(diǎn)的度數(shù)之和為( ) A、n-1(正確答案)B、nC、n+1D、2n4度為4、高度為h的樹(shù),( ) A、至少有h+3個(gè)結(jié)點(diǎn)(正確答案)B、至多有4h-1個(gè)結(jié)點(diǎn)C、至多有4h個(gè)結(jié)點(diǎn)D、至少有h+4個(gè)結(jié)點(diǎn)5假定一棵度為3的樹(shù)中,結(jié)點(diǎn)數(shù)為50,則其最小高度為( ) A、3B、4C、5(正確答案)D、66不含任何結(jié)點(diǎn)的空樹(shù)( )。 A、是一棵樹(shù)B、是一棵二叉樹(shù)C、是一棵樹(shù)也是一棵二叉樹(shù)D、既不是樹(shù)也不是二叉樹(shù)(正確答案)樹(shù)

12、與二叉樹(shù)測(cè)試（2）二叉樹(shù)基礎(chǔ)和性質(zhì)已完成1若一棵完全二叉樹(shù)有768個(gè)結(jié)點(diǎn),則該二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)是( )。 A、257B、258C、384(正確答案)D、3852由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)? ( ) A、2B、3C、4D、5(正確答案)3一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn),其中葉子結(jié)點(diǎn)的個(gè)數(shù)是( )。 A、250B、500C、254D、501(正確答案)4一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為( ) A、11B、10C、11至1025之間(正確答案)D、10至1024之間6設(shè)樹(shù)T的度為4,其中度為1,2,3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1 則T中的葉子數(shù)為( ) A、4B、6C

13、、7D、8(正確答案)7在一棵度為4的樹(shù)T中,若有20個(gè)度為4的結(jié)點(diǎn),10 個(gè)度為3的結(jié)點(diǎn),1個(gè)度為2的結(jié)點(diǎn),10個(gè)度為1的結(jié)點(diǎn),則樹(shù)T的葉子結(jié)點(diǎn)個(gè)數(shù)是( )。 A、41B、82(正確答案)C、113D、1228已知一棵完全二叉樹(shù)的第6層(設(shè)根為第1層)有8個(gè)葉子結(jié)點(diǎn),則該完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多是( )。 A、39B、52C、111(正確答案)D、1199已知一棵完全二叉樹(shù)的第6層(設(shè)根為第1層)有8個(gè)葉子結(jié)點(diǎn),則該完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最少是( )。 A、39(正確答案)B、52C、111D、11910、以下說(shuō)法中,正確的是( )。 A、在完全二叉樹(shù)中,葉子結(jié)點(diǎn)的雙親的左兄弟(若存在)一定不

14、是葉子結(jié)點(diǎn)(正確答案)B、任何一棵二叉樹(shù),葉子結(jié)點(diǎn)個(gè)數(shù)為度為2的結(jié)點(diǎn)數(shù)減1,即n0=n2-1C、完全二叉樹(shù)不適合順序存儲(chǔ)結(jié)構(gòu),只有滿二叉樹(shù)適合順序存儲(chǔ)結(jié)構(gòu)D、結(jié)點(diǎn)按完全二叉樹(shù)層序編號(hào)的二叉樹(shù)中,第i個(gè)結(jié)點(diǎn)的左孩子的編號(hào)為2i11具有10個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)中有( )個(gè)度為2的結(jié)點(diǎn)。 A、8B、9(正確答案)C、10D、1112假設(shè)一棵二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為50, 則它的最小高度是( )。 A、4B、5C、6(正確答案)D、713設(shè)二叉樹(shù)有2n個(gè)結(jié)點(diǎn),且m n，則不可能存在( )的結(jié)點(diǎn)。 A、n個(gè)度為0B、2m個(gè)度為0C、2m個(gè)度為1(正確答案)D、2m個(gè)度為214設(shè)二叉樹(shù)只有度為0和2的結(jié)點(diǎn),其結(jié)點(diǎn)個(gè)數(shù)為15,則該二叉樹(shù)的最大深度為( )。 A、4B、5C、8(正確答案)D、916若一棵深度為6的完全二叉樹(shù)的第6層有3個(gè)葉子結(jié)點(diǎn),則該二叉樹(shù)共有( )個(gè)葉子結(jié)點(diǎn)。 A、17(正確答案)B、18C、19D、2017若一棵二叉樹(shù)有126個(gè)結(jié)點(diǎn),在第7層(根結(jié)點(diǎn)在