國家開放大學(xué)《數(shù)據(jù)結(jié)構(gòu)（本）》單元測試參考答案

1、國家開放大學(xué)數(shù)據(jù)結(jié)構(gòu)（本）單元測試參考答案單元1 緒論1.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（ ）。A. 物理和存儲結(jié)構(gòu)B. 物理結(jié)構(gòu)C. 邏輯結(jié)構(gòu)D. 存儲結(jié)構(gòu)2.組成數(shù)據(jù)的基本單位是（ ）。A. 數(shù)據(jù)變量B. 數(shù)據(jù)項C. 數(shù)據(jù)類型D. 數(shù)據(jù)元素3.研究數(shù)據(jù)結(jié)構(gòu)就是研究（ ）。A. 數(shù)據(jù)的存儲結(jié)構(gòu)B. 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)C. 數(shù)據(jù)的邏輯結(jié)構(gòu)D. 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)以及其數(shù)據(jù)在運算上的實現(xiàn)4.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。A. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)B. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)5.數(shù)據(jù)結(jié)構(gòu)是一門研究計算機中（ ）

2、對象及其關(guān)系的科學(xué)。A. 非數(shù)值運算B. 集合C. 數(shù)值運算D. 非集合6.下列說法不正確的是（ ）。A. 數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標(biāo)識單位B. 數(shù)據(jù)項可由若干個數(shù)據(jù)元素構(gòu)成C. 數(shù)據(jù)可由若干個數(shù)據(jù)元素構(gòu)成D. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位7.設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以互相繼承遺產(chǎn)，子女可以繼承父親和母親的遺產(chǎn)，子女間不能相互繼承，則表示該遺產(chǎn)繼承關(guān)系最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（ ）結(jié)構(gòu)。A. 樹形B. 線性C. 圖狀D. 集合8.算法的時間復(fù)雜度與（ ）有關(guān)。A. 算法本身B. 數(shù)據(jù)結(jié)構(gòu)C. 所使用的計算機D. 算法的程序設(shè)計9.算法分析的兩個主要方面是（ ）。A. 正確性和簡明性B

3、. 可讀性和文檔性C. 時間復(fù)雜性和空間復(fù)雜性D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性10.數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（ ）。A. 數(shù)據(jù)元素間關(guān)系的表示B. 相關(guān)算法C. 數(shù)據(jù)處理的方法D. 數(shù)據(jù)元素的類型11.數(shù)據(jù)元素是數(shù)據(jù)的最小單位（×）。12.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系（×）。13.算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)（×）。14.算法是在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上對特定問題求解步驟的一種描述，也是若干條指令組成的優(yōu)先序列（）。15.算法可以用不同的語言描述，如果用C語言等高級語言來描述，則算法實際上就是程序了（×）。16.程序一

4、定是算法（×）。17.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式（）。18.數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是時間復(fù)雜度和空間復(fù)雜度（）。19.在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系（×）。單元2 線性表1.線性表的順序存儲比鏈?zhǔn)酱鎯ψ钆c利于進行（ ）操作。A. 表頭插入或刪除B. 表尾插入或刪除C. 按值插入或刪除D. 查找2.鏈表不具備的特點是（ ）。A. 不必事先估計存儲空間B. 所需空間與其長度成正比C. 插入、刪除不需要移動元素D. 可隨機訪問任一結(jié)點3.向一個有127個元素的順序表中插入一個新元素，并保持原來的順序不變，平均要移動（ ）個元素。

5、A. 63B. 7C. 8D. 63.54.在一個長度為n的順序存儲線性表中，向第i個元素（1in）之前插入一個新元素時，需要依次后移（ ）個元素。A. n-i-1B. n-i+1C. iD. n-i5.在一個長度為n的順序存儲線性表中，刪除第i個元素（1in），需要前移（ ）個元素。A. n-i-1B. iC. n-i+1D. n-i6.一個順序存儲線性表的第一個元素的存儲地址是90，每個元素的長度是2，則第6個元素的存儲地址是（ ）。A. 106B. 98C. 102D. 1007.用鏈表表示線性表的優(yōu)點是（ ）。A. 便于插入和刪除B. 便于隨機存取C. 數(shù)據(jù)元素的物理順序和邏輯順序相同

6、D. 花費的存儲空間較順序存儲少8.帶頭結(jié)點的鏈表為空的判斷條件是（ ）（設(shè)頭指針為head）。A. head->next=NULLB. head->next=headC. head=NULLD. head!=NULL9.非空的單向循環(huán)鏈表的尾結(jié)點滿足（ ）（設(shè)頭指針為head，指針p指向尾結(jié)點）。A. p->next=NULLB. p=headC. p->next=headD. p=NULL10.在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用語句（ ）。A. p->next=qB. p->ne

7、xt=q->nextC. q->next=NULLD. p=q->next11.線性表在鏈?zhǔn)酱鎯χ懈鹘Y(jié)點之間的地址（ ）。A. 必須連續(xù)B. 部分地址必須連續(xù)C. 連續(xù)與否無所謂D. 不能連續(xù)12.有關(guān)線性表的正確說法是（ ）。A. 表中的元素必須按由小到大或由大到下排序B. 線性表至少要求一個元素C. 除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅(qū)和一個直接后繼D. 每個元素都有一個直接前驅(qū)和一個直接后繼13.若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最省時間。A. 雙向循環(huán)鏈表B. 帶頭結(jié)點的雙向循環(huán)鏈表C

8、. 單向循環(huán)鏈表D. 順序表14.在單鏈表中，若*p不是尾結(jié)點，在其后插入*s結(jié)點的操作是（ ）。A. s->next=p->next;p=s;B. s->next=p->next;p->next=s;C. s->next=p;p->next=s;D. p->next=s;s->next=p;15.在一個長度為n的順序表中為了刪除第5個元素，由第6個元素開始從后到前依次移動了15個元素。則原順序表的長度為（ ）。A. 19B. 25C. 21D. 2016.對于一個具有n個結(jié)點的單向鏈表，在給定值為x的結(jié)點之后插入一個新結(jié)點的時間復(fù)雜度為（

9、 ）。A. O(1)B. O(n3)C. O(n2)D. O(n)17.設(shè)順序存儲的線性表長度為n，對于插入操作，設(shè)插入位置是等概率的，則插入一個元素平均移動元素的次數(shù)為（ ）。A. nB. n-i+1C. n-1D. n/218.線性表的順序結(jié)構(gòu)中，（ ）。A. 進行數(shù)據(jù)元素的插入、刪除效率較高B. 邏輯上相鄰的元素在物理位置上也相鄰C. 邏輯上相鄰的元素在物理位置上不一定相鄰D. 數(shù)據(jù)元素是不能隨機訪問的19.以下說法中不正確的是（ ）。A. 雙向循環(huán)鏈表中每個結(jié)點需要包含兩個指針域B. 單向循環(huán)鏈表中尾結(jié)點的指針域中存放的是頭指針C. 順序存儲的線性鏈表是可以隨機訪問的D. 已知單向鏈表

10、中任一結(jié)點的指針就能訪問到鏈表中每個結(jié)點20.以下表中可以隨機訪問的是（ ）。A. 單向鏈表B. 單向循環(huán)鏈表C. 順序表D. 雙向鏈表21.設(shè)鏈表中的結(jié)點是NODE類型的結(jié)構(gòu)體變量，且有NODE *p；為了申請一個新結(jié)點，并由p指向該結(jié)點，可用以下語句（ ）。A. p=(NODE)malloc(sizeof(p);B. p=(NODE*)malloc(sizeof(NODE);C. p=(*NODE)malloc(sizeof(NODE);D. p=(NODE*)malloc(sizeof(p);22.設(shè)head為非空的單向循環(huán)鏈表頭指針，p指向鏈表的尾結(jié)點，則滿足邏輯表達式（ ）的值為真。

11、A. p->next=NULLB. p=NULLC. p->next=headD. p-=head23.順序存取的線性表樂意隨機存?。ǎ?。24.由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活（）。25.線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元具有相同的特性，因此是屬于同一數(shù)據(jù)對象（）。26.在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素但是在物理上位置并不一定是相鄰的（×）。27.在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因為可以從頭結(jié)點進行查找任何一個元素（×）。28.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)（×）。2

12、9.在線性表的順序存儲結(jié)構(gòu)中，插入和刪除元素時，移動元素的個數(shù)與該袁術(shù)的位置有關(guān)（）。30.在單鏈表中，要取得某個元素，只要知道該元素的指針機可，因此單鏈表是隨機存取的存儲結(jié)構(gòu)。（×）31.順序存儲方式只能用于存儲線性結(jié)構(gòu)。（×）32.順序存儲方式的有點是存儲密度大，且插入、刪除運算效率高。（×）單元3 棧和隊列1.一個順序棧一旦被聲明，其占用空間的大?。?）。A. 已固定B. 動態(tài)變化C. 可以改變D. 不能固定2.鏈棧和順序棧相比，有一個比較明顯的缺點，即（ ）。A. 不會出現(xiàn)?？盏那闆rB. 插入操作更加方便C. 刪除操作更加方便D. 通常不會出現(xiàn)棧滿的情況3

13、.用單鏈表表示的鏈?zhǔn)疥犃械年狀^在鏈表的（ ）位置。A. 鏈頭B. 任意位置C. 鏈尾D. 鏈中4.在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個（ ）結(jié)構(gòu)。A. 數(shù)組B. 堆棧C. 隊列D. 線性表5.循環(huán)隊列Am 存放其元素，用front和rear分別表示隊頭及隊尾，則循環(huán)隊列滿的條件是（ ）。A. （rear+1)%m=frontB. （rear=frontC. （rear+1)%m-1=frontD. （rear =front+16.在一個棧頂指針為top的鏈棧中，將一個p指

14、針?biāo)傅慕Y(jié)點入棧，應(yīng)執(zhí)行（ ）。A. p->next=top; top=p;B. top->next=p;C. p->next=top->next; top->next=p;D. p->next=top->next; top=top->next;7.在一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用 x保存被刪結(jié)點的值，則執(zhí)行（ ）。A. x=top->data; top=top->next;B. x=top;top=top->next;C. top=top->next; x=top->data;D. x=top-&g

15、t;data;8.在一個鏈隊中，設(shè)front和rear分別為隊首和隊尾指針，則插入p所指結(jié)點時，應(yīng)執(zhí)行（ ）。A. p->next=rear;rear=p;B. rear->next=p;rear=p;C. front->next=p;front=p;D. p->next=front;front=p;9.在鏈隊列中，f和r分別為隊頭和隊尾指針，要把s所指結(jié)點入隊，應(yīng)執(zhí)行（ ）。A. r->next=s-> next; r=s;B. r->next=s;C. r->next=s;r=s;D. r->next=s-> next;10.設(shè)t

16、op是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，則取棧頂元素的操作為（ ）。A. x=top->data;top= top->next;B. top=top->next;C. x=top->data;D. top->data=x;11.一個隊列的入隊序列是2，4，6，8，則隊列的輸出序列是（ ）。A. 6，4，2，8B. 4，2，8，6C. 2，4，6，8D. 8，6，4，212.一個棧的進棧序列是5，6，7，8，則棧的不可能的出棧序列是（ ）。（進出棧操作可以交替進行）A. 8，7，6，5B. 7，6，8，5C

17、. 7，6，5，8D. 5，8，6，713.棧的插入刪除操作在（ ）進行。A. 棧底B. 棧頂C. 指定位置D. 任意位置14.棧和隊列的相同點是（ ）。A. 邏輯結(jié)構(gòu)與線性表相同，都是操作規(guī)則受到限制的線性表B. 邏輯結(jié)構(gòu)與線性表不同C. 都是后進后出D. 都是后進先出15.以下說法正確的是（ ）。A. 棧的特點是先進先出，隊列的特點是先進后出B. 棧和隊列的特點都是先進后出C. 棧和隊列的特點都是先進先出D. 棧的特點是先進后出，隊列的特點是先進先出16.設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針。設(shè)p

18、指向要入隊的新結(jié)點(該結(jié)點已被賦值)，則入隊操作為（ ）。A. rear->next=p;p = rear;B. rear->next=p;rear=p;C. p =rear->next;rear=p;D. rear=p;rear->next=p;17.設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用x保存出隊元素的值，p為指向結(jié)點類型的指針，可執(zhí)行如下操作：p=front->next;x=p->data;然后指行（ ）。A. front->next=

19、p->next;B. front=p->next;C. front=p;D. front->next =p;18.以下說法不正確的是（ ）。A. 順序隊列中，當(dāng)尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿B. 順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列已空C. 順序棧中，棧滿時再進行進棧操作稱為“上溢”D. 順序棧中，?？諘r再作出棧棧操作稱為“下溢”19.一個遞歸算法必須包括（ ）。A. 迭代部分B. 終止條件和迭代部分C. 遞歸部分D. 終止條件和遞歸部分20.假定一個鏈?zhǔn)疥犃械年狀^和隊尾指針分別為front和rear，則判斷隊空的條件為（ ）。

20、A. front=NULLB. front!=NULLC. rear!=NULLD. front=rear21.向順序棧中壓入新元素時，應(yīng)當(dāng)（ ）。A. 先存入元素，再移動棧頂指針B. 同時進行C. 先后次序無關(guān)緊要D. 應(yīng)當(dāng)先移動棧頂指針，再存入元素22.判斷一個循環(huán)隊列Q（最多元素為m）為滿的條件是（ ）。A. Q->front=(Q->rear+1)%mB. Q->rear!=(Q->front+1)%mC. Q->front=Q->rearD. Q->front=Q->rear+122.判斷棧滿（元素個數(shù)最多n個）的條件是（ ）。A. t

21、op=n-1B. top!=0C. top=-1D. top=024.隊列的刪除操作是在（ ）。A. 隊頭B. 隊尾C. 隊后D. 隊前25.一個隊列的入隊序列是a,b,c,d,按該隊列的可能輸出序列使各元素依次入棧，該棧的可能輸出序列是 （ ）。（進棧出?？梢越惶孢M行）。A. d,a,b,cB. d,b,a,cC. c,a,b,dD. d,c,b,a單元4 串1.以下陳述中正確的是（ ）。A. 串的長度必須大于零B. 串是一種特殊的線性表C. 空串就是空格串D. 串中元素只能是字母2.設(shè)有兩個串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱為（ ）。A. 匹配B. 求子串C. 連接

22、D. 求串長3.串是（ ）。A. 任意個字母的序列B. 不少于一個字符的序列C. 有限個字符的序列D. 不少于一個字母的序列4.串的長度是指（ ）。A. 串中所含字符的個數(shù)B. 串中所含不同字母的個數(shù)C. 串中所含不同字符的個數(shù)D. 串中所含非空格字符的個數(shù)5.在C語言中，存儲字符串“ABCD”需占用（ ）字節(jié)。A. 2B. 3C. 4D. 56.下面關(guān)于串的敘述中，不正確的是（ ）。A. 空串是由空格構(gòu)成的串B. 串即可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯. 串是字符的有限序列D. 模式匹配是串的一種重要運算7.串與普通的線性表相比較，它的特殊性體現(xiàn)在（ ）。A. 順序的存儲結(jié)構(gòu)B. 數(shù)據(jù)元

23、素是一個字符C. 鏈接的存儲結(jié)構(gòu)D. 數(shù)據(jù)元素可以任意8.空串與空格串（ ）。A. 可能相同B. 相同C. 無法確定D. 不相同9.兩個字符串相等的條件是（ ）。A. 兩串包含的字符相同B. 兩串的長度相等，并且兩串包含的字符相同C. 兩串的長度相等，并且對應(yīng)位置上的字符相同D. 兩串的長度相等10.在實際應(yīng)用中，要輸入多個字符串，且長度無法預(yù)定。則應(yīng)該采用（ ）存儲比較合適（ ）。A. 順序B. 堆結(jié)構(gòu)C. 無法確定D. 鏈?zhǔn)?1.下列關(guān)于串的敘述中，不正確的是（ ）。A. 空串是由空格構(gòu)成的串B. 串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯. 串是字符的有限序列D. 模式匹配是串的一種重要

24、運算12.串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。A. 可以順序存儲B. 數(shù)據(jù)元素是一個字符C. 數(shù)據(jù)元素可以是多個字符D. 可以鏈接存儲13.串函數(shù)StrCmp(“abA”,”aba”)的值為（ ）。A. “abAaba”B. -1C. 1D. 014.在C語言中，存儲字符串“ABCD”需要占用（ ）字節(jié)。A. 2B. 3C. 4D. 515.設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（ ）。A. AbcB. BCdC. ABCD. Bcd16.字符串 a1=“AEIJING”，a2=“AEI”，a3=“AEFANG”，a4=“AEFI”中最大的是（ ）。A

25、. a4B. a3C. a2D. a117.字符串a(chǎn)bcd321ABCD的子串是（ ）。A. 321aB. abcDC. abcABCDD. 21ABC18.數(shù)組a經(jīng)初始化char a =“English”；a1中存放的是（ ）。 A. EB. 字符EC. 字符nD. n19.空串的長度為（ ）。A. 1B. 2C. 0D. 3 單元5 數(shù)組和廣義表1.一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用4個字節(jié)，第8個元素的存儲地址為120，則該數(shù)組的首地址是（ ）。A. 90B. 32C. 92D. 882.稀疏矩陣采用壓縮存儲的目的主要是（ ）。A. 減少不必要的存儲空間的開銷B. 對矩陣元素的存取

26、變得簡單C. 去掉矩陣中的多余元素D. 表達變得簡單3.一個非空廣義表的表頭（ ）。A. 只能是原子B. 不可能是原子C. 只能是子表D. 可以是子表或原子4.常對數(shù)組進行的兩種基本操作是（ ）。A. 索引與、和修改B. 建立與刪除C. 查找和修改D. 查找與索引5.在二維數(shù)組A810中，每一個數(shù)組元素Aij 占用3個存儲空間，所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中，則存放該數(shù)組至少需要的存儲空間是（ ）。A. 80B. 100C. 270D. 2406.設(shè)有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素A10,8

27、在一維數(shù)組B中的下標(biāo)是（ ）。A. 58B. 53C. 18D. 457.廣義表(a)的表尾是（ ）。A. aB. (a)C. (a)D. 08.設(shè)有一個10階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素A8,5在一維數(shù)組B中的下標(biāo)是（ ）。A. 85B. 41C. 32D. 339.設(shè)廣義表類（(a,b,c)），則L的長度和深度分別為（ ）。A. 1和2B. 1和3C. 2和3D. 1和110.廣義表( a , a ,b , d , e ,( (i ,j ) ,k ) )的表頭是_。A. ( a )B. aC. (a ,b)

28、D. a,(a,b)11.廣義表的（a，d，e，（i，j），k）表尾是_。A. kB. （k）C. （d，e，（i，j），k ）D. （i，j），k）12.稀疏矩陣的壓縮存儲方式通常有兩種，即（ ）。A. 三元組和十字鏈表B. 二元組和三元組C. 散列和十字鏈表D. 三元組和散列13.設(shè)有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），B數(shù)組共有55個元素，則矩陣是（ ）階的對稱矩陣。A. 5B. 20C. 15D. 1014.設(shè)有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），

29、則數(shù)組中第53號元素對應(yīng)于矩陣中的元素是（ ）。A. a8,1B. a8,5C. a10,8D. a7,615.對稀疏矩陣進行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A共有73個零元素，其相應(yīng)的三元組表共有( )個元素。A. 7B. 10C. 80D. 816.廣義表(a)的表尾是（ ）。A. ( )B. (a)C. aD. (a)17.廣義表(a,(a,b),d,e,(i,j),k)的長度和深度分別是（ ）。A. 5，5B. 6，6C. 5，3D. 6，4單元6 樹和二叉樹1.假定一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30，則葉子結(jié)點數(shù)為（ ）。A. 17B. 15C.

30、 47D. 162.已知某二叉樹的后續(xù)遍歷序列是dabec，中序遍歷是debac，則它的先序遍歷序列是（ ）。A. acbedB. cedbaC. deabcD. decab3.二叉樹第k層上最多有（ ）個結(jié)點。A. 2k-1B. 2k-1C. 2k-1D. 2k4.二叉樹的深度為k，則二叉樹最多有（ ）個結(jié)點。A. 2k-1B. 2k-1C. 2kD. 2k-15.設(shè)某一二叉樹先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹后序遍歷的順序是（ ）。A. abdecB. debacC. abedcD. debca6.設(shè)某一二叉樹中序遍歷為badce，后序遍歷為bdeca，則該二叉樹先序遍

31、歷的順序是（ ）。A. decabB. abcdeC. adbecD. debac7.樹最適合于用來表示（ ）。A. 順序結(jié)構(gòu)的數(shù)據(jù)B. 元素之間無前驅(qū)和后繼關(guān)系的數(shù)據(jù)C. 線性結(jié)構(gòu)的數(shù)據(jù)D. 元素之間有包含和層次關(guān)系的數(shù)據(jù)8.一棵非空的二叉樹，先序遍歷與后續(xù)遍歷正好相反，則該二叉樹滿足（ ）。A. 無右孩子B. 無左孩子C. 任意二叉樹D. 只有一個葉子結(jié)點9.設(shè)a，b為一棵二叉樹的兩個結(jié)點，在后續(xù)遍歷中，a在b前的條件是（ ）。A. a在b上方B. a在b右方C. a在b下方D. a在b左方10.權(quán)值為1，2，6，8的四個結(jié)點構(gòu)成的哈夫曼樹的帶權(quán)路徑長度是（ ）。A. 28B. 19C.

32、18D. 2911.如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（ ）。A. 二叉樹B. 平衡二叉樹C. 完全二叉樹D. 哈夫曼樹12.下列有關(guān)二叉樹的說法正確的是（ ）。A. 完全二叉樹中，任何一個結(jié)點的度，或者為0或者為2B. 二叉樹中結(jié)點個數(shù)必大于0C. 二叉樹中度為0的結(jié)點的個數(shù)等于度為2的結(jié)點的個數(shù)加1D. 二叉樹的度是213.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以（ ）。A. 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲B. 它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲C. 它不能用順序存儲結(jié)構(gòu)存儲D. 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用14.任何一棵二叉樹的葉結(jié)點在先序、中序和后序

33、遍歷序列中的相對次序（ ）。A. 發(fā)生改變B. 不能確定C. 不發(fā)生改變D. 以上都不對15.一棵有n個結(jié)點采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有?）個指針域為空。A. nB. n+1C. n-2D. n-116.設(shè)一棵哈夫曼樹共有n個非葉結(jié)點，則該樹有（ ）個葉結(jié)點。A. n-1B. n+1C. nD. 2n17.一棵完全二叉樹共有5層，且第5層上有六個結(jié)點，該樹共有（ ）個結(jié)點。A. 23B. 30C. 21D. 2018.在一棵二叉樹中，若編號為i的結(jié)點是其雙親結(jié)點的右孩子，則雙親結(jié)點的順序編號為（ ）。A. i/2向下取整B. 2i+1C. i/2.0D. i/2+119.一棵采用鏈?zhǔn)酱鎯Φ亩?/p>

34、叉樹中有n個指針域為空,該二叉樹共有（ ）個結(jié)點。A. n-1B. n+1C. n-2D. n20.一棵 結(jié)點數(shù)31<n<40的完全二叉樹，最后一層有4個結(jié)點，則該樹有（ ）個葉結(jié)點。A. 35B. 36C. 18D. 1721.設(shè)一棵哈夫曼樹共有2n+1個結(jié)點，則該樹有（ ）個非葉結(jié)點。A. n-1B. 2nC. nD. n+122.在一棵具有35個結(jié)點的完全二叉樹中，該樹的深度為( )。A. 6B. 7C. 8D. 523.在一棵二叉樹中，若編號為i的結(jié)點存在左孩子，則左孩子結(jié)點的順序編號為( )。A. 2i+1B. 2i+2C. 2iD. 2i-124.在一棵具有n個結(jié)點的二

35、叉樹的第i層上，最多具有( )個結(jié)點。A. 2nB. 2i+1C. 2iD. 2i-125.以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，在有n個結(jié)點的二叉鏈表中（n>0），鏈表中空鏈域的個數(shù)為（ ）。A. n+1B. n-1C. 2n+1D. 2n-126.將含有150個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為69的結(jié)點的雙親結(jié)點的編號為（ ）。A. 35B. 34C. 36D. 3327.有n個葉子結(jié)點的哈夫曼樹的結(jié)點總數(shù)為（ ）。A. 2n+1B. 2n-1C. 2nD. 不確定28.下面關(guān)于二叉樹的結(jié)論正確的是（ ）。A. 二叉樹中，度為0的

36、結(jié)點個數(shù)等于度為2的結(jié)點個數(shù)加1B. 二叉樹的度是2C. 二叉樹中結(jié)點的個數(shù)必大于0D. 完全二叉樹中，任何一個結(jié)點的度，或者為0，或者為2單元7 圖1.在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（ ）倍。A. 1/2B. 4C. 2D. 12.鄰接表是圖的一種（ ）。A. 索引存儲結(jié)構(gòu)B. 散列存儲結(jié)構(gòu)C. 順序存儲結(jié)構(gòu)D. 鏈?zhǔn)酱鎯Y(jié)構(gòu)3.如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是（ ）。A. 完全圖B. 連通圖C. 一棵樹D. 有回路4.下列有關(guān)圖遍歷的說法不正確的是（ ）。A. 連通圖的深度優(yōu)先搜索是一個遞歸過程B. 圖的遍歷要求每一頂點僅被訪

37、問一次C. 圖的廣度優(yōu)先搜索中鄰接點的尋找具有“先進先出”的特征D. 非連通圖不能用深度優(yōu)先搜索法5.無向圖的鄰接矩陣是一個（ ）。A. 對稱矩陣B. 上三角矩陣C. 對角矩陣D. 零矩陣6.圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）遍歷。A. 中序B. 先序C. 后序D. 層次7.已知下圖所示的一個圖，若從頂點V1出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. V1V2V4V8V3V5V6V7B. V1V2V4V5V8V3V6V7C. V1V2V4V8V5V3V6V7D. V1V3V6V7V2V4V5V88.已知如圖2所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行遍

38、歷，則可能得到的一種頂點序列為（ ）。A. aebcfdB. abcedfC. abcefdD. acfdeb9.已知如圖3所示的一個圖，若從頂點a出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. aedfcbB. acfebdC. aebcfdD. abecdf10.一個具有n個頂點的無向完全圖包含（ ）條邊。A. n（n-1）/2B. n（n+1）C. n（n-1）D. n（n+1）/211.已知如圖4所示的一個圖，若從頂點a出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. aebcfdB. abecdfC. aedfcbD. acfebd12.

39、已知如圖5所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. abcedfB. aebcfdC. abcefdD. acfdeb13.已知如圖6所示的一個圖，若從頂點V1出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. V1V2V4V8V5V3V6V7B. V1V2V4V5V8V3V6V7C. V1V2V4V8V3V5V6V7D. V1V3V6V7V2V4V5V814.已知如圖7所示的一個圖，若從頂點V1出發(fā)，按深廣優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. V1V2V3V4V5V6V7V8B. V1V2V3V6

40、V7V4V5V8C. V1V2V3V4V8V5V6V7D. V1V2V3V4V5V8V6V715.采用鄰接表存儲的圖的廣度優(yōu)先搜索遍歷算法類似于二叉樹的（ ）。A. 后續(xù)遍歷B. 中序遍歷C. 層次遍歷D. 先序遍歷16.下面結(jié)論中不正確的是（ ）。A. 按廣度優(yōu)先搜索遍歷時，與始點相鄰的結(jié)點先于不與始點相鄰的結(jié)點訪問B. 圖的多重鄰接表表示法中，表中結(jié)點的數(shù)目等于圖中邊的條數(shù)C. 一個圖按廣度優(yōu)先搜索法遍歷的結(jié)果是唯一的D. 無向圖的鄰接表表示法中，表中結(jié)點的數(shù)目是圖中邊的條數(shù)的2倍17.下面說法不正確的是（ ）。A. 圖的遍歷是從給定的原點出發(fā)每一個頂點僅被訪問一次B. 圖的深度遍歷不適用

41、于有向圖C. 遍歷的基本算法有兩種：深度遍歷和廣度遍歷D. 圖的深度遍歷是一個遞歸過程18.任何一棵無向連通圖的最小生成樹（ ）。A. 可能不存在B. 只有一棵C. 一定有多棵D. 有一棵或多棵19.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要（ ）邊。A. n-1B. nC. n/2D. n+120.采用鄰接表存儲的圖的深度優(yōu)先搜索遍歷算法類似于二叉樹的（ ）。A. 層次遍歷B. 后續(xù)遍歷C. 中序遍歷D. 先序遍歷單元8 查找1.線性表只有以（ ）方式存儲，才能進行折半查找。A. 鏈接B. 順序C. 二叉樹D. 關(guān)鍵字有序的2.有序表為2，4，10，13，33，42，46，64，7

42、6，79，85，95，120，用折半查找值為85的結(jié)點時，經(jīng)（ ）次比較后成功查到。A. 1B. 8C. 4D. 23.采用順序查找法對長度為n（n為偶數(shù)）的線性表進行查找，采用從前向后的方向查找。在等概率條件下成功查找到前n/2個元素的平均查找長度為（ ）。A. (n+1)/2B. n/2C. (n+2)/4D. (2n+1)/44.對二叉排序樹進行（ ）遍歷，可以使遍歷所得到的序列是有序序列。A. 按層次B. 中序C. 前序D. 后序5.以下說法正確的是（ ）。A. 二叉樹的根結(jié)點值大于其左子樹結(jié)點的值，小于右子樹結(jié)點的值，則它是一棵二叉排序樹。B. 二叉樹中任一結(jié)點的值均大于其左孩子的值

43、，小于其右孩子的值。則它是一棵二叉排序樹。C. 二叉排序樹中某一結(jié)點的左兒子一定小于樹中任一個結(jié)點的右兒子。D. 二叉排序樹中任一棵子樹都是二叉排序樹。6.對線性表進行二分查找時，要求線性表必需（ ）。A. 以順序方式存儲B. 以鏈接方式存儲C. 以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列D. 以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列7.使用折半查找法時，要求查找表中各元素的鍵值必須是（ ）排列的。A. 遞減B. 無序C. 遞增或遞減D. 遞增8.已知一個有序表為11,22,33,44,55,66,77,88,99，則順序查找元素55需要比較（ ）次。A. 5B. 3C. 4D. 69.有一個長度為

44、10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ）。A. 31/10B. 29/9C. 26/10D. 29/1010.采用分塊查找時，若線性表中共有324個元素，查找每個元素的概率相同，假設(shè)采用順序查找來確定結(jié)點所在的塊，每塊應(yīng)分（ ）個結(jié)點最佳。A. 6B. 324C. 18D. 1011.如果要求一個線性表既能較快地查找，又能動態(tài)適應(yīng)變化要求，可以采用（ ）查找方法。A. 折半B. 分塊C. 順序D. 散列12.關(guān)于哈希查找的說法正確的是（ ）。A. 刪除一個元素后，不管用哪種方法處理沖突，都只需簡單地把該元素刪除掉B. 因為沖突是不可避免的，所以裝填因

45、子越小越好C. 除留余數(shù)法是最好的D. 哈希函數(shù)的好壞要根據(jù)具體情況而定13.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（ ）。A. n/2B. (n+1)/2C. (n-1)/2D. n14.采用分塊查找時，數(shù)據(jù)的組織方式為（ ）。A. 把數(shù)據(jù)分城若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引表B. 把數(shù)據(jù)分城若干塊，每塊內(nèi)數(shù)據(jù)有序C. 把數(shù)據(jù)分城若干塊，塊內(nèi)數(shù)據(jù)不必有序，但塊間必需有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引表D. 把數(shù)據(jù)分城若干塊，每塊（除最后一塊外）中的數(shù)據(jù)個數(shù)相等15.假設(shè)在有序線性表A1.20上進行折半查找，則比較五次查找成功的結(jié)點數(shù)為

46、（ ）。A. 8B. 4C. 5D. 6單元9 排序1.設(shè)有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用（）排序法。A. 冒泡排序B. 基數(shù)排序C. 快速排序D. 堆排序2.對數(shù)據(jù)元素序列（49，72，68，13，38，50，97，27）進行排序，前三趟排序結(jié)果時的結(jié)果依次為第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。該排序采用的方法是（ ）。A. 選擇排序法B. 插入排序法C. 堆排序法D. 冒泡排序法3.一組記錄的關(guān)鍵字序列為（47，8

47、0，57，39，41，46），利用堆排序（堆頂元素是最小元素）的方法建立的初始化堆為（ ）。A. 39，41，46，80，47，57B. 39，47，46，80，41，57C. 41，39，46，47，57，80D. 39，80，46，47，41，574.一組記錄的關(guān)鍵字序列為（37，70，47，29，31，85），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ ）。A. 31，29，37，47，77，85B. 31，29，37，85，47，70C. 29，31，37，47，70，85D. 31，29，37，70，47，855.下述幾種排序方法中，要求內(nèi)存量最大的是（ ）。A. 插入排序B. 選擇