數(shù)據(jù)結(jié)構(gòu)期末考試題及答案.doc

《數(shù)據(jù)結(jié)構(gòu)期末考試題及答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)期末考試題及答案.doc（19頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 2012年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案一、選擇題1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 C 。A動(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)2數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指A。A數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)B數(shù)據(jù)結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu) D數(shù)據(jù)元素之間的關(guān)系3在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 A 結(jié)構(gòu)。A邏輯B存儲(chǔ)C邏輯和存儲(chǔ)D物理4在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ) C 。A數(shù)據(jù)的處理方法B數(shù)據(jù)元素的類型C數(shù)據(jù)元素之間的關(guān)系D數(shù)據(jù)的存儲(chǔ)方法5在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮 A 。A各結(jié)點(diǎn)的值如何B結(jié)點(diǎn)個(gè)數(shù)的多少C對(duì)數(shù)據(jù)有哪些

2、運(yùn)算D所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。6以下說(shuō)法正確的是D 。A數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位B數(shù)據(jù)元素是數(shù)據(jù)的最小單位C數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7算法分析的目的是C ，算法分析的兩個(gè)主要方面是A 。（1）A找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進(jìn) C分析算法的易讀性和文檔性（2）A空間復(fù)雜度和時(shí)間復(fù)雜度 B正確性和簡(jiǎn)明性C可讀性和文檔性 D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8下面程序段的時(shí)間復(fù)雜度是O（n2）。s 0；for（ I 0； in； i）for（j0；jn；j）s Bij；sum s ；9下面程序段的時(shí)間復(fù)雜

3、度是O（n*m）。for（ i 0； in； i）for（j0；jm；j）Aij 0；10下面程序段的時(shí)間復(fù)雜度是O（log3n）。i 0；while（in）i i * 3；11在以下的敘述中，正確的是 B 。A線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C棧的操作方式是先進(jìn)先出 （先進(jìn)后出）D隊(duì)列的操作方式是先進(jìn)后出 （先進(jìn)先出，尾進(jìn)首出）12通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著B(niǎo) 。A數(shù)據(jù)元素具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致C每個(gè)數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等13鏈表

4、不具備的特點(diǎn)是A 。（順序表是隨機(jī)訪問(wèn)的，只要知道首元素的地址，就可以知道任意的第i個(gè)元素的地址）A可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B插入刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與其長(zhǎng)度成正比14不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 A。 A head=NULL B head-next NULLCheadnext headD head！NULL15帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 B。A head=NULL B head-next NULLCheadnext headD head！NULL16若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用D 存儲(chǔ)方式最節(jié)

5、省運(yùn)算時(shí)間。A單鏈表 B給出表頭指針的單循環(huán)鏈表C雙鏈表 D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是 B 。A單鏈表 B靜態(tài)鏈表C線性鏈表 D順序存儲(chǔ)結(jié)構(gòu) （需要移動(dòng)元素）動(dòng)態(tài)鏈表不需要分配很大的空間，如果空間不足夠，可以申請(qǐng)空間，靜態(tài)鏈表只能使用初始化時(shí)候的空間，不能夠追加空間18非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足C 。Apnext NULLBp NULLCpnext head Dp head19在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是 D 。P-prior-next=s;S-prior=p-prior;S-next

6、=p;P-prior=s; AppriorpriorBppriorpriorCspriornext sDspriorprior s20如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用D存儲(chǔ)方式最節(jié)省時(shí)間。A單鏈表 B雙鏈表C單循環(huán)鏈表D 順序表21在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是B 。AO（1） BO（n）CO（n2）DO（nlog2n）22在一個(gè)長(zhǎng)度為n（n1）的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行 B操作與鏈表的長(zhǎng)度有關(guān)。A刪除單鏈表中的第一個(gè)元素B刪除單鏈表中的最后一個(gè)元素C在單鏈表第一個(gè)元素前插入一個(gè)新元素D在單鏈表最后一個(gè)元素后插入一個(gè)新元素23

7、與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是D。A插入、刪除操作更簡(jiǎn)單B可以進(jìn)行隨機(jī)訪問(wèn)C可以省略表頭指針或表尾指針D順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活24如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用 B 。A只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表B只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表C非循環(huán)雙鏈表D循環(huán)雙鏈表25在長(zhǎng)度為n的順序表的第i個(gè)位置上插入一個(gè)元素（1 i n1），元素的移動(dòng)次數(shù)為： A 。An i 1Bn iCiDi 126對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為 C。A順序表 B 用頭指針表示的循環(huán)單鏈表C用尾指針表示的循環(huán)單鏈表 D單鏈表

8、27下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)? C。A插入運(yùn)算方便 B可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C存儲(chǔ)密度大 D刪除運(yùn)算方便 （需要移動(dòng)元素）28下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)? B。A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。29線性表是具有n個(gè) B 的有限序列。A字符B數(shù)據(jù)元素 C數(shù)據(jù)項(xiàng)D表元素30在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組（順序表）實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是O（1）的操作是 A 。A訪問(wèn)第i（1in）個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（1in）B

9、在第i（1in）個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C刪除第i（1in）個(gè)結(jié)點(diǎn)D以上都不對(duì)31若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為C。AO（0） BO（1）CO（n）DO（n2）32對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為 C。（增加一個(gè)元素需要平均移動(dòng)n/2個(gè)元素，刪除一個(gè)元素需要平均移動(dòng)n-1/2個(gè)元素）AO（n） O（n） BO（n） O（1）CO（1） O（n）DO（1） O（1）33線性表（a1，a2， ，an）以鏈?zhǔn)椒绞酱鎯?chǔ)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜度為 C。AO（0） BO（1）CO（n）DO（n2）34單鏈表中，增加一個(gè)頭

10、結(jié)點(diǎn)的目的是為了C。A使單鏈表至少有一個(gè)結(jié)點(diǎn) B標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C方便運(yùn)算的實(shí)現(xiàn) D說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)35在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是 B 。S-next=p-next;P-next=s;Apnextpnextpnexts；Cpnextsnextsnext；pnexts36線性表的順序存儲(chǔ)結(jié)構(gòu)是一種A 。A隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B順序存取的存儲(chǔ)結(jié)構(gòu)C索引存取的存儲(chǔ)結(jié)構(gòu)DHash存取的存儲(chǔ)結(jié)構(gòu)37棧的特點(diǎn)是 B ，隊(duì)列的特點(diǎn)是A。A先進(jìn)先出 B先進(jìn)后出38棧和隊(duì)列的共同點(diǎn)是C 。A都是先進(jìn)后出 B都是先進(jìn)先出C只允許在端點(diǎn)處插入和刪除元素 D沒(méi)有共同點(diǎn)

11、39一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 C 。AedcbaBdecbaCdceabDabcde40設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E。下列 C 是不可能的出棧序列。 AA，B，C，D，E BB，C，D，E，ACE，A，B，C，D DE，D，C，B，A41以下 B 不是隊(duì)列的基本運(yùn)算?（隊(duì)列只能隊(duì)列尾插入，隊(duì)列頭刪除）A從隊(duì)尾插入一個(gè)新元素B從隊(duì)列中刪除第i個(gè)元素C判斷一個(gè)隊(duì)列是否為空D讀取隊(duì)頭元素的值42若已知一個(gè)棧的進(jìn)棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1n，則pi為 C。Ai Bni Cni1 D不確定43判定一個(gè)順序

12、棧st（最多元素為MaxSize）為空的條件是B 。Asttop ！top 1Csttop ！top MaxSize44判定一個(gè)順序棧st（最多元素為MaxSize）為滿的條件是D 。Asttop ！top 1Csttop ！top MaxSize45一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是B 。A4，3，2，1 B1，2，3，4C1，4，3，2 D3，2，4，146判定一個(gè)循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是C 。Aqurear qurear qufront 1MaxSizeCqufront=qu-rearfront 147在循環(huán)隊(duì)列中，若front與rear

13、分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是 C。Afrontrear1 Brearfront1 Cfrontrear Dfront048向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行D操作。 （鏈棧的操作和鏈表類似）Ahnexth ；Csnexthnexts ；49輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為B。Apush，pop，push，pop，push，popBpush，push，push，pop， pop， popCpush，push，pop， pop，push，popDpush，pop，push，push，pop， pop （push是壓棧的

14、意思，pop是彈出棧的意思）50若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1m，top1、top2分別代表第1和第2個(gè)棧的棧頂，棧1的底在V1，棧2的底在Vm，則棧滿的條件是B。A|top2top1|0 B top11top2 Ctop1top2mDtop1top251設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用D 數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲(chǔ)結(jié)構(gòu) B隊(duì)列 C線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D棧52允許對(duì)隊(duì)列進(jìn)行的操作有D。A對(duì)隊(duì)列中的元素排序B取出最近進(jìn)隊(duì)的元素C在隊(duì)頭元素之前插入元素D刪除隊(duì)頭元素53對(duì)于循環(huán)隊(duì)列D 。A無(wú)法判斷隊(duì)列是否為空 B無(wú)法判斷隊(duì)列是否為滿C隊(duì)列不可能滿 D以上說(shuō)

15、法都不對(duì)循環(huán)隊(duì)列滿的標(biāo)志：front=rear+1對(duì)列空的標(biāo)志：front=rear54若用一個(gè)大小為6的數(shù)值來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為 B。 當(dāng)前隊(duì)列中元素個(gè)數(shù)公式：（rear-front+n）%nA1和5 B2和4 C4和2D5和155隊(duì)列的“先進(jìn)先出”特性是指 D 。A最早插入隊(duì)列中的元素總是最后被刪除B當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作D每次從隊(duì)列中刪除的總是最早插入的元素56和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是A 。A通常不

16、會(huì)出現(xiàn)棧滿的情況 B 通常不會(huì)出現(xiàn)?？盏那闆rC插入操作更容易實(shí)現(xiàn) D刪除操作更容易實(shí)現(xiàn)57用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作時(shí) C。A僅修改隊(duì)頭指針B僅修改隊(duì)尾指針C隊(duì)頭、隊(duì)尾指針都可能要修改D隊(duì)頭、隊(duì)尾指針都要修改71樹(shù)最適合用來(lái)表示 C。A有序數(shù)據(jù)元素B無(wú)序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無(wú)聯(lián)系的數(shù)據(jù)72深度為5的二叉樹(shù)至多有 C 個(gè)結(jié)點(diǎn)。A16B 32 C31 C 1073對(duì)一個(gè)滿二叉樹(shù)，m個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h，則D 。An hm B hm 2n C m h1Dn 2h174任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序

17、和后序遍歷序列中的相對(duì)次序 A 。A不發(fā)生改變 B發(fā)生改變C不能確定 D以上都不對(duì)75在線索化樹(shù)中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來(lái)說(shuō)明它的左、右鏈指向的是樹(shù)結(jié)構(gòu)信息，還是線索化信息，若0標(biāo)識(shí)樹(shù)結(jié)構(gòu)信息，1標(biāo)識(shí)線索，對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)為_(kāi) D_。A00 B01C10D1176在下述論述中，正確的是 D 。只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0；二叉樹(shù)的度為2；二叉樹(shù)的左右子樹(shù)可任意交換；深度為K的順序二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)。AB C D77設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)是A 。Amn Bmn1 Cn1D

18、不能確定78若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個(gè)數(shù)是B 。A9 B11 C15D不能確定79具有10個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)中有 B 個(gè)度為2的結(jié)點(diǎn)。A8 B9 C10 D1180在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C 倍。A1/2 B 1C 2 D4同一條邊被兩端頂點(diǎn)計(jì)算了兩次81在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的B倍。A1/2 B 1C 2 D4在一個(gè)有向圖中，入度之和等于出度之和82某二叉樹(shù)結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：CA3B2 C4D583已知一算術(shù)表達(dá)式的中綴形式為

19、AB *CD/E，后綴形式為ABC *DE/，其前綴形式為 D。 AAB*C/DE BAB*CD/E C *ABC/DE DA*BC/DE84已知一個(gè)圖，如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)D_；按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)A_；Aa，b，e，c，d，fBa，c，f，e，b，dCa，e，b，c，f，d，Da，e，d，f，c，bAa，b，c，e，d，fBa，b，c，e，f，dCa，e，b，c，f，d，Da，c，f，d，e，b85采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹(shù)的_A_。A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷這是因

20、為圖的深度優(yōu)先遍歷算法先訪問(wèn)所在結(jié)點(diǎn)，再訪問(wèn)它的鄰接點(diǎn)。與二叉樹(shù)的先序遍歷先訪問(wèn)子樹(shù)的根結(jié)點(diǎn)，再訪問(wèn)它的孩子結(jié)點(diǎn)（鄰接點(diǎn)）類似。圖的廣度優(yōu)先遍歷算法類似于二叉樹(shù)的按層次遍歷。86采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹(shù)的_D_。A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷87具有n 個(gè)結(jié)點(diǎn)的連通圖至少有 A 條邊。An1B n C n（n1）/2 D 2n88廣義表（a），a）的表頭是 C，表尾是C。Aa B（）C （a） D （a）89廣義表（a）的表頭是 C，表尾是B。Aa B（）C （a） D （a）90順序查找法適合于存儲(chǔ)結(jié)構(gòu)為 B的線性表。A散列存儲(chǔ) B順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C

21、壓縮存儲(chǔ) D索引存儲(chǔ)91對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須B。A以順序方式存儲(chǔ) B以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯?chǔ) D以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列折半查找必須是順序存儲(chǔ)，而且關(guān)鍵字必須是有序的92采用折半查找法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為D 。AO（n2） BO（nlog2n） CO（n）DO（log2n）93有一個(gè)有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí)，C次比較后查找成功。A11 B5 C 4 D894二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值

22、、小于其右孩子的值。這種說(shuō)法B 。A 正確 B 錯(cuò)誤二叉樹(shù)是二叉排序樹(shù)的充要條件：（1）若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；（2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；（3）左、右子樹(shù)也分別為二叉排序樹(shù)；（4）沒(méi)有鍵值相等的節(jié)點(diǎn)。95下面關(guān)于B樹(shù)和B樹(shù)的敘述中，不正確的結(jié)論是 A。AB樹(shù)和B樹(shù)都能有效的支持順序查找 BB樹(shù)和B樹(shù)都能有效的支持隨機(jī)查找CB樹(shù)和B樹(shù)都是平衡的多叉樹(shù) DB樹(shù)和B樹(shù)都可用于文件索引結(jié)構(gòu)96以下說(shuō)法錯(cuò)誤的是 B。A散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址B散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。C負(fù)載因子

23、是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿程度。D散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的方法。97查找效率最高的二叉排序樹(shù)是C。A所有結(jié)點(diǎn)的左子樹(shù)都為空的二叉排序樹(shù)。B所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)。C平衡二叉樹(shù)。D沒(méi)有左子樹(shù)的二叉排序樹(shù)。98排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為C。A希爾排序 B。冒泡排序 C插入排序 D。選擇排序99在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是D 。A希爾排序B冒泡排序 C直接插入排序 D直接選擇排序100堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列

24、關(guān)鍵碼序列D 是一個(gè)堆。A94，31，53，23，16，72B94，53，31，72，16，23C16，53，23，94，31，72D16，31，23，94，53，72101堆排序是一種B排序。A插入B選擇C交換D歸并堆排序是一種選擇排序102D 在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。A順序查找B折半查找C分塊查找D插入103直接選擇排序的時(shí)間復(fù)雜度為 D 。（n 為元素個(gè)數(shù)）AO（n） BO（log2n） CO（nlog2n）D O（n2）二、填空題。1數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu) 、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型，樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱 非線性結(jié)構(gòu) 。2數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合 、線性結(jié)構(gòu) 、

25、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。3在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒(méi)有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒(méi)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。4線性結(jié)構(gòu)中元素之間存在 一對(duì)一 關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在 一對(duì)多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。5在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有 前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以任意多個(gè)。6數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是 順序、鏈?zhǔn)健?索引和 散列存儲(chǔ) 。7衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和 時(shí)間復(fù)雜度與 空間復(fù)雜度 。8評(píng)估一個(gè)算法的優(yōu)劣，通常從時(shí)間復(fù)雜度 和

26、空間復(fù)雜度 兩個(gè)方面考察。9算法的5個(gè)重要特性是有窮性、確定性 、可行性、輸入和輸出。10在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素時(shí)，需向前移動(dòng) ni1個(gè)元素。11在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。12在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 前驅(qū) 結(jié)點(diǎn)，另一個(gè)指向 后繼結(jié)點(diǎn) 。13在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，需要平均移動(dòng) n個(gè)數(shù)據(jù)元素，移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與 位置 有關(guān)。14當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用順序 存儲(chǔ)結(jié)構(gòu)。15根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成單鏈表

27、 和 雙鏈表 。16順序存儲(chǔ)結(jié)構(gòu)是通過(guò) 下標(biāo) 表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)指針 表示元素之間的關(guān)系的。17帶頭結(jié)點(diǎn)的循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是LnextnextL 。18棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表，其運(yùn)算遵循后進(jìn)先出的原則。19空串是 零個(gè)字符的串，其長(zhǎng)度等于 零。空白串是由一個(gè)或多個(gè)空格字符組成的串，其長(zhǎng)度等于其包含的空格個(gè)數(shù)。20組成串的數(shù)據(jù)元素只能是 單個(gè)字符。21一個(gè)字符串中 任意個(gè)連續(xù)字符構(gòu)成的部分 稱為該串的子串。22子串 ”str” 在主串 ”datastructure” 中的位置是 5。23二維數(shù)組M的每個(gè)元素是6個(gè)字符組成的串，行下標(biāo)i的

28、范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要 540個(gè)字節(jié)；M的第8列和第5行共占108個(gè)字節(jié)。24稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即 三元組表和十字鏈表 。25廣義表（a），（b），c），（d）的長(zhǎng)度是3，深度是4。26在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2 的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0 n21。27在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為_(kāi)n1_。28一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有_2n1_個(gè)結(jié)點(diǎn)。29深度為5的二叉樹(shù)至多有31 個(gè)結(jié)點(diǎn)。30若某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為 69 。31某二叉樹(shù)的前序遍歷序列是abdg

29、cefh，中序序列是dgbaechf，其后序序列為gdbehfca。32線索二叉樹(shù)的左線索指向其 遍歷序列中的前驅(qū) ，右線索指向其遍歷序列中的后繼。33在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是散列查找法 。34在分塊索引查找方法中，首先查找 索引表，然后查找相應(yīng)的塊表。35一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序 樹(shù)而變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。36具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為_(kāi)45_。37已知圖G的鄰接表如圖所示，其從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序列為_(kāi)v1v2v3v6v5v4_，其從頂點(diǎn)v1出發(fā)的廣度優(yōu)先搜索序列為_(kāi)v1v2v5v4v3

30、v6_。 38索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)索引隸屬于某個(gè)數(shù)據(jù)記錄集，它由若干索引項(xiàng)組成，索引項(xiàng)的結(jié)構(gòu)為關(guān)鍵字 和 關(guān)鍵字對(duì)應(yīng)記錄的地址 。39Prim 算法生成一個(gè)最小生成樹(shù)每一步選擇都要滿足 邊的總數(shù)不超過(guò)n1， 當(dāng)前選擇的邊的權(quán)值是候選邊中最小的 ， 選中的邊加入樹(shù)中不產(chǎn)生回路三項(xiàng)原則。40在一棵m階B樹(shù)中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)最多有 m棵子樹(shù)，最少有 m/2 棵子樹(shù)。三、判斷題。1在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮各結(jié)點(diǎn)的值如何。（）2抽象數(shù)據(jù)類型（ADT）包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一個(gè)ADT的邏輯特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。（

31、）3抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無(wú)關(guān)。（ ）4順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。（ ）5線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。（ ）6對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（ ）7順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（ ）8集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。（ ）9線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。（ ）10線性表就是順序存儲(chǔ)的表。（ ）11取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)。（ ）12循環(huán)鏈表不是線性表。（ ）13鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序表中效率高。（

32、）14雙向鏈表可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)。（）15在單鏈表中，給定任一結(jié)點(diǎn)的地址p，則可用下述語(yǔ)句將新結(jié)點(diǎn)s插入結(jié)點(diǎn)p的后面 ：pnext； （ ）16隊(duì)列是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出的結(jié)構(gòu)。（ ）17 串是一種特殊的線性表，其特殊性體現(xiàn)在可以順序存儲(chǔ)。（ ）18長(zhǎng)度為1的串等價(jià)于一個(gè)字符型常量。（）19空串和空白串是相同的。（）20數(shù)組元素的下標(biāo)值越大，存取時(shí)間越長(zhǎng)。（ ）21用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。（ ）22一個(gè)廣義表的表頭總是一個(gè)廣義表。（）23一個(gè)廣義表的表尾總是一個(gè)廣義表

33、。（ ）24廣義表（ a ）， b）， c ） 的表頭是（ a ）， b），表尾是（ c ）。（ ）25二叉樹(shù)的后序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的后面。（ ）26度為2的有序樹(shù)是二叉樹(shù)。（ ）27二叉樹(shù)的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。（ ）28用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。（）29若已知一棵二叉樹(shù)的前序遍歷序列和后序遍歷序列，則可以恢復(fù)該二叉樹(shù)。（ ）30在哈夫曼樹(shù)中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。（ ）31強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。（ ）32對(duì)于任意一個(gè)圖，從它的某個(gè)結(jié)點(diǎn)進(jìn)行一次深度或廣度優(yōu)先遍歷可以訪問(wèn)到該圖的每個(gè)頂點(diǎn)。（ ）33在待排

34、序的記錄集中，存在多個(gè)具有相同鍵值的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序仍然保持不變，稱這種排序?yàn)榉€(wěn)定排序。（）34在平衡二叉樹(shù)中，任意結(jié)點(diǎn)左右子樹(shù)的高度差（絕對(duì)值）不超過(guò)1。（）35拓?fù)渑判蚴前碅OE網(wǎng)中每個(gè)結(jié)點(diǎn)事件的最早發(fā)生時(shí)間對(duì)結(jié)點(diǎn)進(jìn)行排序。（ ）36冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)。（ ）37對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列。（ ）38散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址。（）39二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。（）40具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)有多種，其中樹(shù)高最小的二叉排序樹(shù)是最佳的。（ ）41直接選擇排序算法在最好情況下的時(shí)間復(fù)雜度為O（n）。（ ）