河南工業(yè)大學(xué)軟件工程專業(yè)大二2017年數(shù)據(jù)結(jié)構(gòu)期末試題

1、河南工業(yè)大學(xué)軟件工程專業(yè)大二2017年數(shù)據(jù)結(jié)構(gòu)期末試題一、選擇題。1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為  。 單選題 *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數(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ù)的  結(jié)構(gòu)。 單選題 *A邏輯(正確答案)B存儲(chǔ)C邏輯和存儲(chǔ)D物理4在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)  。 單選題 *A數(shù)據(jù)的處理方法B數(shù)據(jù)元素的類型C數(shù)據(jù)

2、元素之間的關(guān)系(正確答案)D數(shù)據(jù)的存儲(chǔ)方法5在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮  。 單選題 *A各結(jié)點(diǎn)的值如何(正確答案)B結(jié)點(diǎn)個(gè)數(shù)的多少C對(duì)數(shù)據(jù)有哪些運(yùn)算D所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。6以下說(shuō)法正確的是  。 單選題 *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算法分析的目的是  ，算法分析的兩個(gè)主要方面是  。 *A找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進(jìn)(正確答案)D分析算法的易讀性和文檔性E空間復(fù)雜度和

3、時(shí)間復(fù)雜度(正確答案)F正確性和簡(jiǎn)明性G.可讀性和文檔性H.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性11在以下的敘述中，正確的是  。 單選題 *A線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表(正確答案)C棧的操作方式是先進(jìn)先出D隊(duì)列的操作方式是先進(jìn)后出12通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著  。 單選題 *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鏈表不具備的特點(diǎn)是  。 單選題 *A可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)(

4、正確答案)B插入刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與其長(zhǎng)度成正比14不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是  。 單選題 *Ahead = NULL(正確答案)B head->next =NULLChead->next =headD head!=NULL15帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是  。 單選題 *Ahead = NULLB head->next =NULL(正確答案)Chead->next =headD head!=NULL16若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用 

5、; 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間 單選題 *A單鏈表B給出表頭指針的單循環(huán)鏈表C雙鏈表D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表(正確答案)17需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是 。 單選題 *A單鏈表B靜態(tài)鏈表(正確答案)C線性鏈表D順序存儲(chǔ)結(jié)構(gòu)18非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足  。 單選題 *Ap->next = NULLBp = NULLCp->next =head(正確答案)Dp = head19在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是  。 單選題 *Ap->prior = s；s->next = p；

6、p->prior->next = s；s->prior = p->priorBp->prior = s；p->prior->next = s；s->next = p；s->prior = p->priorCs->next = p；s->prior = p->prior；p->prior = s；p->prior->next = sDs->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s(正確答

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

8、表的優(yōu)點(diǎn)之一是  。 單選題 *A插入、刪除操作更簡(jiǎn)單B可以進(jìn)行隨機(jī)訪問(wèn)C可以省略表頭指針或表尾指針D順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活(正確答案)24如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用  。 單選題 *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 n+1），元素的移動(dòng)次數(shù)為：  。 單選題 *An i + 1(正確答案)Bn iCiDi 126對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存

9、儲(chǔ)結(jié)構(gòu)為  。 單選題 *A順序表B 用頭指針表示的循環(huán)單鏈表C用尾指針表示的循環(huán)單鏈表(正確答案)D單鏈表27下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？  。 單選題 *A插入運(yùn)算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C存儲(chǔ)密度大(正確答案)D刪除運(yùn)算方便28下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？  。 單選題 *A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。(正確答案)C線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。29線性表是具有n個(gè)  的有限序列。 單選題 *

10、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訪問(wèn)第i（1<=i<=n）個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（1(正確答案)B在第i（1<=i<=n）個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C刪除第i（1<=i<=n）個(gè)結(jié)點(diǎn)D以上都不對(duì)31若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為  。 單選題 *AO(0)BO(1)CO(n)(正確答案)DO(n2)32對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為  。 單

11、選題 *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ù)雜度為  。 單選題 *AO(0)BO(1)CO(n)(正確答案)DO(n2)34單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了  。 單選題 *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)，正確的操作是  。 單選題 *Ap->next=s；s->next=p->nextB

12、 s->next=p->next ；p->next=s;(正確答案)Cp->next=s；p->next=s->nextDp->next=s->next；p->next=s36線性表的順序存儲(chǔ)結(jié)構(gòu)是一種  。 單選題 *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)是  。 單選題 *A都是先進(jìn)后出B都是先進(jìn)先出C只允許在端點(diǎn)處插入和刪除元素(正確答案)D沒(méi)有共同

13、點(diǎn)39一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 。 單選題 *AedcbaBdecbaCdceab(正確答案)Dabcde40設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E。下列  是不可能的出棧序列。 單選題 *AA,B,C,D,EBB,C,D,E,ACE,A,B,C,D(正確答案)DE,D,C,B,A41以下  不是隊(duì)列的基本運(yùn)算？ 單選題 *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為

14、0; 。 單選題 *AiBniCni1(正確答案)D不確定43判定一個(gè)順序棧st（最多元素為MaxSize）為空的條件是  。 單選題 *Ast->top != -1Bst->top = -1(正確答案)Cst->top != MaxSizeD st->top = MaxSize44判定一個(gè)順序棧st（最多元素為MaxSize）為滿的條件是  。 單選題 *Ast->top != -1Bst->top = -1Cst->top != MaxSizeDst->top = MaxSize(正確答案)45一個(gè)隊(duì)列的入隊(duì)序列是1，2，

15、3，4，則隊(duì)列的輸出序列是  。 單選題 *A4，3，2，1B1，2，3，4(正確答案)C1，4，3，2D3，2，4，146判定一個(gè)循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是  。 單選題 *Aqu->rear qu->front =MaxSizeBqu->rear qu->front -1=MaxSizeCqu->rear =qu->front(正確答案)D qu->rear =qu->front -147在循環(huán)隊(duì)列中，若front與rear 分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是 

16、。 單選題 *Afront=rear+1Brear=front+1Cfront=rear(正確答案)Dfront=048向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行  操作。 單選題 *Ah->next=s Bs->next=h Cs->next=h h =s Ds->next=h->next h->next=s (正確答案)49輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為  。 單選題 *Apush，pop，push，pop，push，popBpus

17、h，push，push，pop， pop， pop(正確答案)Cpush，push，pop， pop，push，popDpush，pop，push，push，pop， pop50若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1 m，top1、top2分別代表第1和第2個(gè)棧的棧頂，棧1的底在V1，棧2的底在Vm，則棧滿的條件是  。 單選題 *A|top2-top1|=0B top1+1=top2(正確答案)Ctop1+top2=mDtop1=top251設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用  數(shù)據(jù)結(jié)構(gòu)最佳。 單選題 *A線性表的順序存儲(chǔ)結(jié)構(gòu)B隊(duì)列C線性表的鏈?zhǔn)?/p>

18、存儲(chǔ)結(jié)構(gòu)D棧(正確答案)52允許對(duì)隊(duì)列進(jìn)行的操作有  。 單選題 *A對(duì)隊(duì)列中的元素排序B取出最近進(jìn)隊(duì)的元素C在隊(duì)頭元素之前插入元素D刪除隊(duì)頭元素(正確答案)53對(duì)于循環(huán)隊(duì)列  。 單選題 *A無(wú)法判斷隊(duì)列是否為空B無(wú)法判斷隊(duì)列是否為滿C隊(duì)列不可能滿D以上說(shuō)法都不對(duì)(正確答案)54若用一個(gè)大小為6的數(shù)值來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為  。 單選題 *A1和5B2和4(正確答案)C4和2D5和155隊(duì)列的“先進(jìn)先出”特性是指  。 單選題 *A最早插入隊(duì)列

19、中的元素總是最后被刪除B當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作D每次從隊(duì)列中刪除的總是最早插入的元素(正確答案)56和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是  。 單選題 *A通常不會(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í)  。 單選題 *A僅修改隊(duì)頭指針B僅修改隊(duì)尾指針C隊(duì)頭、隊(duì)尾指針都可能要修改(正確答案)D隊(duì)頭、隊(duì)尾指針都要修改58若串S=software，其子串的數(shù)目是&#

20、160; 。 單選題 *A8B37(正確答案)C36D959串的長(zhǎng)度是指  。 單選題 *A串中所含不同字母的個(gè)數(shù)B串中所含字符的個(gè)數(shù)(正確答案)C串中所含不同字符的個(gè)數(shù)D串中所含非空格字符的個(gè)數(shù)60串是一種特殊的線性表，其特殊性體現(xiàn)在  。 單選題 *A可以順序存儲(chǔ)B數(shù)據(jù)元素是一個(gè)字符(正確答案)C可以鏈?zhǔn)酱鎯?chǔ)D數(shù)據(jù)元素可以是多個(gè)字符61設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為  。 單選題 *A連接B 模式匹配(正確答案)C求子串D求串長(zhǎng)62數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi)

21、，該數(shù)組按行存放，元素A85的起始地址為  。 單選題 *ASA141B SA144CSA222(正確答案)DSA22563數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素A58的起始地址為  。 單選題 *ASA141B SA180CSA222(正確答案)DSA22564若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下： froat average=new float30;假設(shè)該數(shù)組的內(nèi)存起始位置為200， average15的內(nèi)存地址是  。 單選題 *A214B215C260(正確答案)D25665設(shè)

22、二維數(shù)組A1 m,1 n按行存儲(chǔ)在數(shù)組B中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為  。 單選題 *An*(i-1)+j(正確答案)B n*(i-1)+j-1Ci*(j-1)Dj*m+i-166有一個(gè)100×90的稀疏矩陣，非0元素有10，設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是  。 單選題 *A20B 66(正確答案)C18 000D3367數(shù)組A0 4，-1 -3，5 7中含有的元素個(gè)數(shù)是  。 單選題 *A55(正確答案)B 45C36D1668對(duì)矩陣進(jìn)行壓縮存儲(chǔ)是為了  。 單選題 *A方便運(yùn)算B 方便存儲(chǔ)

23、C提高運(yùn)算速度D減少存儲(chǔ)空間(正確答案)69設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a1，1為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)地址空間，則a8，5的地址為  。 單選題 *A13B 33(正確答案)C18D4070稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即  。 單選題 *A二維數(shù)組和三維數(shù)組B 三元組和散列C三元組和十字鏈表(正確答案)D 散列和十字鏈表71樹(shù)最適合用來(lái)表示  。 單選題 *A有序數(shù)據(jù)元素B無(wú)序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)(正確答案)D元素之間無(wú)聯(lián)系的數(shù)據(jù)72深度為5的二叉樹(shù)至多有  個(gè)結(jié)點(diǎn)。 單選

24、題 *A16B 32C 31(正確答案)d 1073對(duì)一個(gè)滿二叉樹(shù)，m個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h，則  。 單選題 *An = h+mB h+m = 2nC m = h-1D n = 2h-1(正確答案)74任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序  。 單選題 *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)  _。 單選題 *A00B01C10D11(正確答案)76在下述

25、論述中，正確的是  。只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0；二叉樹(shù)的度為2；二叉樹(shù)的左右子樹(shù)可任意交換；深度為K的順序二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)。單選題 *ABCD(正確答案)77設(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ù)是  。 單選題 *Am-n(正確答案)Bm-n-1Cn+1D不能確定78若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個(gè)數(shù)是  。 單選題 *A9B11(正確答案)C15D不能確定79具有10個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)中有  個(gè)度為2的結(jié)點(diǎn)。 單

26、選題 *A8B9(正確答案)C10D1180在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 倍。 單選題 *A1/2B 1C 2(正確答案)D 481在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的  倍。 單選題 *A1/2B 1(正確答案)C 2D 482某二叉樹(shù)結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：  單選題 *A3B2C4(正確答案)D583已知一算術(shù)表達(dá)式的中綴形式為AB *CD/E，后綴形式為ABC *+DE/，其前綴形式為      。 單選題 *AA+B*C/DEBA+B*

27、CD/EC +*ABC/DED+A*BC/DE(正確答案)84已知一個(gè)圖，如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)D_；按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)A_； *Aa，b，e，c，d，f(正確答案)Ba，c，f，e，b，dCa，e，b，c，f，d，Da，e，d，f，c，b(正確答案)Ea，b，c，e，d，fFa，b，c，e，f，dGa，e，b，c，f，d，Ha，c，f，d，e，b85采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹(shù)的_。 單選題 *A先序遍歷(正確答案)B中序遍歷C后序遍歷D按層遍歷86采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似

28、于二叉樹(shù)的_。 單選題 *A先序遍歷B中序遍歷C后序遍歷D按層遍歷(正確答案)87具有n 個(gè)結(jié)點(diǎn)的連通圖至少有  條邊。 單選題 *A n-1(正確答案)B nC n(n-1)/2D 2n88廣義表（a），a）的表頭是 C ，表尾是 C 。 單選題 *AaB （）C （a）(正確答案)D （a）89廣義表（a）的表頭是 C ，表尾是 B 。 *AaB （）(正確答案)C （a）(正確答案)D （a）90順序查找法適合于存儲(chǔ)結(jié)構(gòu)為  的線性表。 單選題 *A 散列存儲(chǔ)B 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)(正確答案)C 壓縮存儲(chǔ)D 索引存儲(chǔ)91對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須 

29、; 。 單選題 *A 以順序方式存儲(chǔ)B 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列(正確答案)C 以鏈?zhǔn)椒绞酱鎯?chǔ)D 以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列92采用折半查找法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為  。 單選題 *A O(n2)B O(nlog2n)C O(n)D O(log2n)(正確答案)93有一個(gè)有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí)，  次比較后查找成功。 單選題 *A 11B 5C 4(正確答案)D 894二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小

30、于其右孩子的值。這種說(shuō)法  。 單選題 *A 正確B 錯(cuò)誤(正確答案)95下面關(guān)于B樹(shù)和B+樹(shù)的敘述中，不正確的結(jié)論是  。 單選題 *A(正確答案)B樹(shù)和B+樹(shù)都能有效的支持順序查找 B B樹(shù)和B+樹(shù)都能有效的支持隨機(jī)查找C B樹(shù)和B+樹(shù)都是平衡的多叉樹(shù)D B樹(shù)和B+樹(shù)都可用于文件索引結(jié)構(gòu)96以下說(shuō)法錯(cuò)誤的是  。 單選題 *A散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址B散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。(正確答案)C負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿程度。D散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的

31、方法。97查找效率最高的二叉排序樹(shù)是  。 單選題 *A所有結(jié)點(diǎn)的左子樹(shù)都為空的二叉排序樹(shù)。B所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)。C平衡二叉樹(shù)。(正確答案)D沒(méi)有左子樹(shù)的二叉排序樹(shù)。98排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為  。 單選題 *A希爾排序B。冒泡排序C插入排序(正確答案)D。選擇排序99在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是  。 單選題 *A希爾排序B冒泡排序C直接插入排序D直接選擇排序(正確答案)100堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列 

32、; 是一個(gè)堆。 單選題 *A94,31,53,23,16,72B94,53,31,72,16,23C16,53,23,94,31,72D16,31,23,94,53,72(正確答案)101堆排序是一種  排序。 單選題 *A插入B選擇(正確答案)C交換D歸并102  在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。 單選題 *A順序查找B折半查找C分塊查找D插入(正確答案)103直接選擇排序的時(shí)間復(fù)雜度為  。（n 為元素個(gè)數(shù)） 單選題 *AO（n)BO(log2n)CO(nlog2n)D O(n2)(正確答案)三、判斷題。1在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮各結(jié)點(diǎn)

33、的值如何。 判斷題 *對(duì)(正確答案)錯(cuò)2抽象數(shù)據(jù)類型（ADT）包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一個(gè)ADT的邏輯特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。 判斷題 *對(duì)(正確答案)錯(cuò)3抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無(wú)關(guān)。 判斷題 *對(duì)(正確答案)錯(cuò)4順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。 判斷題 *對(duì)錯(cuò)(正確答案)5線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。 判斷題 *對(duì)錯(cuò)(正確答案)6對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。 判斷題 *對(duì)錯(cuò)(正確答案)7順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。 判斷題 *對(duì)錯(cuò)(正確答案)8集合

34、與線性表的區(qū)別在于是否按關(guān)鍵字排序。 判斷題 *對(duì)錯(cuò)(正確答案)9線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。 判斷題 *對(duì)錯(cuò)(正確答案)10線性表就是順序存儲(chǔ)的表。 判斷題 *對(duì)錯(cuò)(正確答案)11取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)。 判斷題 *對(duì)錯(cuò)(正確答案)12循環(huán)鏈表不是線性表。 判斷題 *對(duì)錯(cuò)(正確答案)13鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序表中效率高。 判斷題 *對(duì)(正確答案)錯(cuò)14雙向鏈表可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)。 判斷題 *對(duì)錯(cuò)(正確答案)15在單鏈表中，給定任一結(jié)點(diǎn)的地址p，則可用下述語(yǔ)句將新結(jié)點(diǎn)s插入結(jié)點(diǎn)p的后面 ：p->next = s; s->next = p->next; 判斷題 *對(duì)錯(cuò)(正確答案)16隊(duì)列是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表，是一種