一、 用適當(dāng)內(nèi)容填空

　　1.數(shù)據(jù)結(jié)構(gòu)是指具有(相同特征)、相互之間有(關(guān)聯(lián))的數(shù)據(jù)(集合)。

　　2.數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的(邏輯結(jié)構(gòu))、數(shù)據(jù)的(存儲(chǔ)結(jié)構(gòu))，以及(算法)。

　　3.數(shù)據(jù)之間有四種邏輯結(jié)構(gòu)，分別是(集合)、(線性)、(樹形)和(圖形)。

　　4.根據(jù)數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間前件與后件關(guān)系的復(fù)雜程度，將數(shù)據(jù)的邏輯結(jié)構(gòu)分為 (線性結(jié)構(gòu))和(非線性結(jié)構(gòu))。

　　5.在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放(各個(gè)數(shù)據(jù)元素)信息，還要存放(數(shù)據(jù)元素之間前后件關(guān)系)信息。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是(邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中)的表示。

　　6.數(shù)據(jù)元素在計(jì)算機(jī)中通常有四種存儲(chǔ)方式，即(順序)、(鏈?zhǔn)?、(索引)和(散列)。

　　7.順序存儲(chǔ)結(jié)構(gòu)是指在內(nèi)存中開辟一塊(連續(xù))的內(nèi)存單元用于存放數(shù)據(jù)，邏輯上相鄰的結(jié)點(diǎn)在物理位置上也(鄰接)，結(jié)點(diǎn)之間的邏輯關(guān)系是由存儲(chǔ)單元的(相鄰)關(guān)系來體現(xiàn)的。

　　8.在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為(數(shù)據(jù)域);另一部分用于存放前件或后件的存儲(chǔ)地址，稱為(指針域)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(指針)反映出數(shù)據(jù)元素之間的邏輯關(guān)系。

　　9.算法的設(shè)計(jì)基于數(shù)據(jù)的(邏輯結(jié)構(gòu))，而算法的實(shí)現(xiàn)依賴于數(shù)據(jù)的(存儲(chǔ)結(jié)構(gòu)、物理結(jié)構(gòu))。

　　10.一個(gè)算法應(yīng)該具有的基本特征有(可行性)、(確定性)、(有窮性)、(輸入性)和(輸出性)。

　　11.算法的復(fù)雜度有(時(shí)間復(fù)雜度)和(空間復(fù)雜度)。

　　12.棧是(在表的同一端)進(jìn)行插入運(yùn)算和刪除運(yùn)算的線性表。將允許進(jìn)行插入運(yùn)算和刪除運(yùn)算的一端稱為(棧頂、top)，另一端稱為(棧底、bottom)。棧遵循(先進(jìn)后出、后進(jìn)先出)的原則。

　　13.隊(duì)列是(一種允許在一端進(jìn)行插入運(yùn)算，而在另一端進(jìn)行刪除運(yùn)算的)線性表。(允許刪除的一端)稱為隊(duì)頭，(允許插入的一端)稱為隊(duì)尾。隊(duì)列遵循(先進(jìn)先出、后進(jìn)后出)的原則。

　　14.所謂循環(huán)隊(duì)列是將隊(duì)列的存儲(chǔ)空間想象成一個(gè)(首尾相連)的環(huán)狀空間。

　　15.判斷循環(huán)隊(duì)列為滿的條件是((rear+1)% n = front)。

　　16.判斷循環(huán)隊(duì)列為空的條件是(front = rear)。

　　17.樹是一種常用的(非線性)結(jié)構(gòu)，樹結(jié)構(gòu)中結(jié)點(diǎn)之間即具有(分支)關(guān)系又具有(層次)關(guān)系。

　　18.在樹結(jié)構(gòu)中，有且只有一個(gè)根結(jié)點(diǎn)，根結(jié)點(diǎn)有(0、零)個(gè)前件，其它結(jié)點(diǎn)有(1、一、壹)個(gè)前件。結(jié)點(diǎn)的(后件)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)，該結(jié)點(diǎn)是其子結(jié)點(diǎn)的(雙親、父)結(jié)點(diǎn)。將沒有后件的結(jié)點(diǎn)稱為(葉結(jié)點(diǎn))。一個(gè)結(jié)點(diǎn)所擁有后件個(gè)數(shù)稱為該結(jié)點(diǎn)的(度)。

　　19.二叉樹的遍歷分為(先序)遍歷、(中序)遍歷和(后序)遍歷。

　　20.先序遍歷是先訪問(根結(jié)點(diǎn))，然后遍歷(左子樹)，最后再遍歷(右子樹)。

　　21.中序遍歷是先遍歷(左子樹)，然后訪問(根結(jié)點(diǎn))，最后再遍歷(右子樹)。

　　22.后序遍歷是先遍歷(左子樹)，然后遍歷(右子樹)，最后再訪問(根結(jié)點(diǎn))。

　　23.二分查找法只適用于(順序)存儲(chǔ)結(jié)構(gòu)的線性表，且(數(shù)據(jù)元素按數(shù)據(jù)值升序或降序排列)。

　　二、 從參考答案中選擇一個(gè)最佳答案

　　1.數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的表示稱為(B)。

　　A.數(shù)據(jù)的邏輯結(jié)構(gòu) B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

　　C.數(shù)據(jù)結(jié)構(gòu) D.數(shù)據(jù)元素之間的關(guān)系

　　2.根據(jù)數(shù)據(jù)結(jié)構(gòu)中各元素之間前后件關(guān)系的復(fù)雜程度，將數(shù)據(jù)結(jié)構(gòu)分成(C)。

　　A.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) B.靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)結(jié)構(gòu)

　　C.線性結(jié)構(gòu)和非線性結(jié)構(gòu) D.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

　　3.關(guān)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，下列敘述中錯(cuò)誤的是(C)。

　　A.邏輯上相鄰結(jié)點(diǎn)物理上不必鄰接 B.插入、刪除操作方便，不用移動(dòng)結(jié)點(diǎn)

　　C.便于隨機(jī)存取 D.花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)空間多

　　4.有關(guān)線性表的敘述錯(cuò)誤的是(C)。

　　A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的內(nèi)存單元

　　B.線性表采用鏈?zhǔn)酱鎯?chǔ)，所占內(nèi)存單元可以不連續(xù)

　　C.順序表便于進(jìn)行插入和刪除操作

　　D.鏈表便于進(jìn)行插入和刪除操作

　　5.以下數(shù)據(jù)結(jié)構(gòu)中，(A)是非線性結(jié)構(gòu)。

　　A.二叉樹 B.隊(duì)列 C.棧 D.線性鏈表

　　6.設(shè)變量front、rear分別指向隊(duì)頭和隊(duì)尾，判斷隊(duì)列是否為空的條件是(C)。

　　A.front=0 B.front=1 C.front=rear D.front=rear=0

　　7.若進(jìn)棧順序是1、2、3、4，進(jìn)棧和出棧可以穿插進(jìn)行，則不可能的出棧序列是(C)。

　　A.1,2,3,4 B.2,3,4,1 C.3,1,4,2 D.3,4,2,1

　　8.依次在初始為空的隊(duì)列中插入元素a,b,c,d以后，緊接著做了兩次刪除操作，此時(shí)隊(duì)頭元素是(C)。