數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言版期末考試復(fù)習(xí)試題

1、?數(shù)據(jù)結(jié)構(gòu)與算法?復(fù)習(xí)題一、選擇題.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.物理(數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映像)稱(chēng)為數(shù)據(jù)的物理(存儲(chǔ))結(jié)構(gòu))4 .在存儲(chǔ)數(shù)據(jù)時(shí),通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值,而且還要存儲(chǔ) CA.數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類(lèi)型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲(chǔ)方法5

2、 .在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí),一般不考慮A .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ō)法正確的選項(xiàng)是 D qA.數(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 .下面程

3、序段的時(shí)間復(fù)雜度是O(n2).s =0;for( I =0; i<n; i+) for(j=0;j<n;j+)s +=Bij;sum = s ;9 .下面程序段的時(shí)間復(fù)雜度是_O(n*m).for( i =0; i<n; i+)for(j=0;j<m;j+)Aij = 0;10 .下面程序段的時(shí)間復(fù)雜度是O(log 3n).1 = 0; while (i<=n)i = i * 3 ;11 .在以下的表達(dá)中,正確的選項(xiàng)是B .A.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進(jìn)先出D.隊(duì)列的操作方式是先進(jìn)后出12 .

4、通常要求同一邏輯結(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)的類(lèi)型要一致C.每個(gè)數(shù)據(jù)元素都一樣D.數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等13.鏈表不具備的特點(diǎn)是A.可隨機(jī)訪問(wèn)任一結(jié)點(diǎn) C.不必事先估計(jì)存儲(chǔ)空間A.B .插入刪除不需要移動(dòng)元素D.所需空間與其長(zhǎng)度成正比14.不帶頭結(jié)點(diǎn)的單鏈表A . head = NULL C. head->next =headA . p->next = NULL C. p->next =headB. p = NULL D . p = headhead為空的判定條

5、件是 AB head->next =NULLD head!=NULL15.帶頭結(jié)點(diǎn)的單鏈表 head為空的判定條件是BA . head = NULLB head->next =NULLC. head->next =headD head!=NULL16 .假設(shè)某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn),那么采用_D 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間.A.單鏈表 B.給出表頭指針的單循環(huán)鏈表C.雙鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17 .需要分配較大空間,插入和刪除不需要移動(dòng)元素的線性表,其存儲(chǔ)結(jié)構(gòu)是BA.單鏈表 B.靜態(tài)鏈表C.線性鏈表 D.順序存儲(chǔ)結(jié)構(gòu)18 .非空的

6、循環(huán)單鏈表 head的尾結(jié)點(diǎn)(由p所指向)滿(mǎn)足 _C.19 .在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是 一DA . p->prior = s ; s->next = p ; p->prior->next = s ; s->prior = p->prior B. p->prior = s ; p->prior->next = s ; s->next = p ; s->prior = p->prior C. s->next = p ; s->prior = p->prior ; p->pri

7、or = s ; p->prior->next = sD. s->next = p ; s->prior = p->prior ; p->prior->next = s ; p->prior = 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_oA. O (1) B. O (n)C, O (n2) D. O (nlog2n)22 .在一個(gè)長(zhǎng)度為n (n>1)的單鏈表上,設(shè)

8、有頭和尾兩個(gè)指針,執(zhí)行B_操作與鏈表的長(zhǎng)度有關(guān).A.刪除單鏈表中的第一個(gè)元素B.刪除單鏈表中的最后一個(gè)元素C.在單鏈表第一個(gè)元素前插入一個(gè)新元素D.在單鏈表最后一個(gè)元素后插入一個(gè)新元素23.與單鏈表相比,雙鏈表的優(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è)元素(1W

9、 i w)n+元素的移動(dòng)次數(shù)為：A_ .A. n -i + 1B. n - iC. iD. i T26 .對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表,宜采用的存儲(chǔ)結(jié)構(gòu)為C .A.順序表B.用頭指針表示的循環(huán)單鏈表C.用尾指針表示的循環(huán)單鏈表D.單鏈表27 .下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)C .A插入運(yùn)算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C存儲(chǔ)密度大D刪除運(yùn)算方便28 .下面關(guān)于 線性表的表達(dá)中,錯(cuò)誤的選項(xiàng)是哪一個(gè)B.A線性表采用順序存儲(chǔ),必須占用一片連續(xù)的存儲(chǔ)單元B線性表采用順序存儲(chǔ),便于進(jìn)行插入和刪除操作.C線性表采用鏈?zhǔn)酱鎯?chǔ),不必占用一片連續(xù)的存儲(chǔ)單元D線性表采用鏈?zhǔn)酱鎯?chǔ),便于進(jìn)行插

10、入和刪除操作.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 (1<=i<=n)個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(1<i<=n)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 .假設(shè)長(zhǎng)度為n的線性表采用 順序存儲(chǔ)結(jié)構(gòu),在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為 C .A. O(0) B. 0(1)C. O(n)D, O(n2)32 .對(duì)于順序存儲(chǔ)的

11、線性表,訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為C .A. O(n) O(n) B. O(n) O(1)C. O(1) O(n)D, O(1) O(1)33 .線性表(a1,a2,an)以鏈?zhǔn)椒绞酱鎯?chǔ),訪問(wèn)第 i位置元素的時(shí)間復(fù)雜度為C .A. O(0) B, O(1)C. O(n)D, O(n2)34 .單鏈表中,增加一個(gè)頭結(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 .A . p->next=s; s->next=p->ne

12、xtB. s->next=p->next ; p->next=s;C. p->next=s ; p->next=s->nextD. p->next=s->next ; p->next=s36 .線性表的順序存儲(chǔ)結(jié)構(gòu)是一種A .A.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B.順序存取的存儲(chǔ)結(jié)構(gòu)C.索引存取的存儲(chǔ)結(jié)構(gòu)D. Hash存取的存儲(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)39 . 一個(gè)棧的進(jìn)棧序列是a, b, c, d

13、, e,那么棧的不可能的輸出序列是C .A. edcba B. decba C. dceab D. abcde40 .設(shè)有一個(gè)棧,元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E.以下 C是不可能的出棧序列.A . A,B,C,D,E B. B,C,D,E,A C. E,A,B,C,D D. E,D,C,B,A41 .以下 B不是隊(duì)列的根本運(yùn)算A.從隊(duì)尾插入一個(gè)新元素B.從隊(duì)列中刪除第i個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值42 .假設(shè)一個(gè)棧的進(jìn)棧序列是1,2,3, n,其輸出序列為p1,p2,p3,pn,假設(shè)p1 = n,那么pi為 CA. iB. n-i C. n-i+1 D,不確定43

14、 .判定一個(gè)順序棧 st 最多元素為 MaxSize為空的條件是A . st->top != -1B. st->top = -1C. st->top != MaxSizeD . st->top = MaxSize44 .判定一個(gè)順序棧 st 最多元素為 MaxSize為滿(mǎn)的條件是 DA . st->top != -1B. st->top = -1C. st->top != MaxSizeD . st->top = MaxSize45. 一個(gè)隊(duì)列的入隊(duì)序列是1, 2, 3, 4,那么隊(duì)列的輸出序列是A. 4, 3, 2, 1C. 1, 4, 3,

15、2B. 1 , 2, 3, 4D. 3, 2, 4, 146.判定一個(gè)循環(huán)隊(duì)列 qu 最多元素為A . qu->rear - qu->front =MaxSizeMaxSize為空的條件是C .B . qu->rear - qu->front -1=MaxSizeC. qu->rear =qu->frontD . qu->rear =qu->front -147.在循環(huán)隊(duì)列中,假設(shè)front與rear分別表示對(duì)頭元素和隊(duì)尾元素的位置,那么判斷循環(huán)隊(duì)列空的條件是A. front=rear+1B. rear=front+1C. front=rearD

16、. front=048 .向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí),應(yīng)執(zhí)行D操作.A . h->next=s ;B . s->next=h ;C. s->next=h ;h =s ; D. s->next=h->next ;h->next=s ;? 49.輸入序列為 ABC,可以變?yōu)镃BA時(shí),經(jīng)過(guò)的棧操作為B .A. push, pop, push, pop, push, pop B. push, push, push, pop, pop, popC. push, push, pop, pop, push, pop D. push, pop

17、, push, push, pop, pop50.假設(shè)棧采用順序存儲(chǔ)方式存儲(chǔ),現(xiàn)兩棧共享空間V1 m, top1、top2分別代表第1和第2個(gè)棧的棧頂,棧1的底在V1,棧2的底在Vm,那么棧滿(mǎn)的條件是B .A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top251 .設(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 .

18、對(duì)于循環(huán)隊(duì)列D.A.無(wú)法判斷隊(duì)列是否為空B.無(wú)法判斷隊(duì)列是否為滿(mǎn)C.隊(duì)列不可能滿(mǎn)D.以上說(shuō)法都不對(duì)54 .假設(shè)用一個(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 .A . 1 和 5 B. 2 和 4 C . 4 和 2D. 5 和 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

19、 qA.通常不會(huì)出現(xiàn)棧滿(mǎn)的情況B.通常不會(huì)出現(xiàn)棧空的情況C.插入操作更容易實(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ì)尾指針都要修改58 .假設(shè)串S= 'software',其子串的數(shù)目是BA. 8 B. 37 C. 36D. 959 .串的長(zhǎng)度是指B .A.串中所含不同字母的個(gè)數(shù)B.串中所含字符的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)60 .串是一種特殊的線性表,其特殊性表達(dá)在B qA.可

20、以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符61 .設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為B .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),該數(shù)組按行存放,元素 A85的起始地址為 _屋.A. SA+ 141 B. SA+ 144C. SA + 222 D. SA + 22563 .數(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的起始地址為C

21、.A. SA+ 141 B. SA+ 180C. SA + 222 D. SA + 22564 .假設(shè)聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下：froat average=new float30;假設(shè)該數(shù)組的內(nèi)存起始位置為200, average15的內(nèi)存地址是C .A. 214B. 215C. 260D. 25665 .設(shè)二維數(shù)組 A1 m,1n按行存儲(chǔ)在數(shù)組B中,那么二維數(shù)組元素Ai,j在一維數(shù)組 B中的下標(biāo)為A.A. n*(i-1)+j B , n*(i-1)+j-1 C. i*(j-1) D. j*m+i-166 .有一個(gè)100X 90的稀疏矩陣,非 0元素有10,設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié),那么用三元組表

22、示該矩陣時(shí),所需的字節(jié)數(shù)是B .A. 20 B.66C. 18 000 D. 3367 .數(shù)組A04, -1-3, 5 7中含有的元素個(gè)數(shù)是A .A. 55 B. 45C. 36D. 1668 .對(duì)矩陣進(jìn)行壓縮存儲(chǔ)是為了D .A.方便運(yùn)算B.方便存儲(chǔ) C.提升運(yùn)算速度D.減少存儲(chǔ)空間69 .設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A,采用壓縮存儲(chǔ)方式,以行序?yàn)橹鞔鎯?chǔ),a1,1為第一個(gè)元素,其存儲(chǔ)地址為1,每個(gè)元素占1個(gè)地址空間,那么a8,5的地址為B qA. 13 B. 33 C. 18 D. 4070 .稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種,即A.二維數(shù)組和三維數(shù)組C.三元組和十字鏈表B.D.三元組和散列散列和

23、十字鏈表71 .樹(shù)最適合用來(lái)表示A.有序數(shù)據(jù)元素C.兀系之間具有分支層次關(guān)系的數(shù)據(jù)B.無(wú)序數(shù)據(jù)元素D.元素之間無(wú)聯(lián)系的數(shù)據(jù)一個(gè)結(jié)點(diǎn).C.1072 .深度為5的二叉樹(shù)至多有CA. 16 B.32 C.3173 .對(duì)一個(gè)滿(mǎn)二叉樹(shù),m個(gè)葉子,n個(gè)結(jié)點(diǎn),深度為h,那么 DA . n = h+m B h+m = 2n C m = h-1 D n = 2h-174 .任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序AA.不發(fā)生改變B.發(fā)生改變 C.不能確定D.以上都不對(duì)75 .在線索化樹(shù)中,每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來(lái)說(shuō)明它的左、右鏈指向的是樹(shù)結(jié)構(gòu)信息,還是線索化信息,假設(shè)0標(biāo)識(shí)樹(shù)結(jié)本M言息,

24、1標(biāo)識(shí)線索,對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域,應(yīng)標(biāo)識(shí)為D.A. 00B. 01C. 10D . 1176 .在下述論述中,正確的選項(xiàng)是 D q只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0；二叉樹(shù)的度為2;二叉樹(shù)的左右子樹(shù)可任意交換;深度為K的順序二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿(mǎn)二叉樹(shù).A.B.C.D.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ù)是A .A . m-n B . m-n-1 C. n+1 D,不能確定78 .假設(shè)一棵二叉樹(shù)具有 10個(gè)度為2的結(jié)點(diǎn),5個(gè)度為1的結(jié)點(diǎn),那么度為0的結(jié)點(diǎn)的個(gè)數(shù)是B.A. 9 B. 11C. 15 D

25、.不能確定N0=N2+179 .具有10個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)中有B 個(gè)度為2的結(jié)點(diǎn).A. 8 B. 9 C. 10 D . 1180 .在一個(gè)無(wú)向圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C 倍.A. 1/2 B 1 C 2 D 4B倍.在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的1/2 B 1 C 282.某二叉樹(shù)結(jié)點(diǎn)的中序序列為ABCDEFG ,后序序列為BDCAFGE ,那么其左子樹(shù)中結(jié)點(diǎn)數(shù)目為:B. 2C. 483. 一算術(shù)表達(dá)式的中綴形式為A+B *C -D/E ,后綴形式為A. *+B*C/DEB .蟲(chóng)+B*CD/EC t*ABC/DEABC *+DE/其前綴形式為D. t

26、A*BC/DE84. 一個(gè)圖,如下列圖,假設(shè)從頂點(diǎn)可能得到的一種頂點(diǎn)序列為a出發(fā)按深度搜索法 ;按廣度搜索法進(jìn)行遍到的一種頂點(diǎn)序列為A.a,b,e,c,Ad,B.a,c,f,e,b,85.86.87.88.A.89.C.A .C.a,a,a,e,b,e,b, c, b,c,e,c,f, d, f,d,fd,采用鄰接表存儲(chǔ)的圖的A.先序遍歷D.B.D.深度優(yōu)先遍B.中序遍歷采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍A.先序遍歷B.中序遍歷具有n個(gè)結(jié)點(diǎn)的連通圖至少有廣義表a,a B 廣義表aa B B.a)a,a,a,eb,d, c, f,f, e, d,c, f,e,歷算法類(lèi)似于二叉樹(shù)的C.后序遍歷歷算法類(lèi)

27、似于二叉樹(shù)的C.后序遍歷C. n(n-1)/2條邊.D. 2n的表頭是 C ,表尾是 CC (a)D (a)的表頭是 C 、表尾是 B .C (a)D (a)90 .順序查找法適合于存儲(chǔ)結(jié)構(gòu)為 B 的線性表.A散列存儲(chǔ)B順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C壓縮存儲(chǔ)D索引存儲(chǔ)91 .對(duì)線性表進(jìn)行折半查找時(shí),要求線性表必須B qA 以順序方式存儲(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)度為D .A O(n2)B O(nlog2n)C O(n)D O(log 2n)82的結(jié)93 .有一個(gè)有

28、序表為 1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100,當(dāng)折半查找值為 點(diǎn)時(shí), C次比較后查找成功.A.11B 5C 4D 894 .二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值.這 種說(shuō)法 B .A 正確B 錯(cuò)誤95 .下面關(guān)于B樹(shù)和B+樹(shù)的表達(dá)中,不正確的結(jié)論是A .A B樹(shù)和B+樹(shù)都能有效的支持順序查找B B樹(shù)和B+樹(shù)都能有效的支持隨機(jī)查找C B樹(shù)和B+樹(shù)都是平衡的多叉機(jī)D B樹(shù)和B+樹(shù)都可用于文件索引結(jié)構(gòu)96 .以下說(shuō)法錯(cuò)誤的選項(xiàng)是 B.A.散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址B.散列表

29、的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息,不包含指針.C.負(fù)載因子是散列表的一個(gè)重要參數(shù),它反映了散列表的飽滿(mǎn)程度.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)行比較,將其放入已排序序列的 正確位置上的方法,稱(chēng)為C QA.希爾排序Bo冒泡排序C插入排序Do選擇排序99 .在所有的排序方法中,關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是_DA.希爾

30、排序B.冒泡排序C.直接插入排序D.直接選擇排序100 .堆是一種有用的數(shù)據(jù)結(jié)構(gòu).以下關(guān)鍵碼序列 D 是一個(gè)堆.A. 94,31,53,23,16,72B, 94,53,31,72,16,23C. 16,53,23,94,31,72D. 16,31,23,94,53,72101 .堆排序是一種B 排序.A.插入B.選擇C.交換D.歸并102 .D 在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高.A.順序查找B .折半查找103.直接選擇排序的時(shí)間復(fù)雜度為 A . O ( n) B, O(log2n)二、填空題.1 .數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)非線性結(jié)構(gòu).2 .數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合C.分塊查找 D.

31、插入D .(n為元素個(gè)數(shù))C. O(nlog 2n)D.O(n2)樹(shù)形結(jié)構(gòu) 和 圖狀結(jié)構(gòu) 三種類(lèi)型,樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱(chēng)、線性結(jié)構(gòu)、 樹(shù)形結(jié)構(gòu) 和 圖狀結(jié)構(gòu) 4種.,個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)逡一對(duì)多關(guān)系,圖形結(jié)構(gòu)中元素之個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有 后3 .在線性結(jié)構(gòu)中,第一個(gè)結(jié)點(diǎn) 沒(méi)有 前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有有后續(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)系.5 .在樹(shù)形結(jié)構(gòu)中,樹(shù)根結(jié)點(diǎn)沒(méi)有 前驅(qū) 結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有 續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以任意多個(gè) .6 .數(shù)據(jù)結(jié)構(gòu)的根本存儲(chǔ)方法是順序 、

32、 鏈?zhǔn)?、 索引 和 散列 存儲(chǔ).7 .衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時(shí)間復(fù)雜度與 空間復(fù)雜度8 .評(píng)估一個(gè)算法的優(yōu)劣,通常從 時(shí)間復(fù)雜個(gè) 和 空間復(fù)雜度兩個(gè)方面考察.9 .算法的5個(gè)重要特性是 有窮性、確定性、可行性、輸入和輸出.10 .在一個(gè)長(zhǎng)度為 n的順序表中刪除第i個(gè)元素時(shí),需向前移動(dòng) n-i-1 個(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)個(gè)數(shù)據(jù)元素,移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與位置有關(guān).14 .當(dāng)線性表的

33、元素總數(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ù),將線性鏈表分成單鏈表和雙鏈表 .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)的條件是L->next->next=L .18 .棧 是限定僅在表尾進(jìn)行插入或刪除操作的線性表,其運(yùn)算遵循后進(jìn)先出 的原那么.19 .空串是 零個(gè)字符的串,其長(zhǎng)度等于 生 空白串是由一個(gè)或多個(gè)空格字符組成的串,其長(zhǎng)度等于其 _包含的空格個(gè)數(shù).20

34、 .組成串的數(shù)據(jù)元素只能是單個(gè)字符 .21 . 一個(gè)字符串中 任意個(gè)連續(xù)字符構(gòu)成的局部稱(chēng)為該串的子串.22 .子串 “str"在主串"datastructure中的位置是5.23 .二維數(shù)組 M的每個(gè)元素是6個(gè)字符組成的串,行下標(biāo) i的范圍從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

35、=n2+1 o27 .在有n個(gè)結(jié)點(diǎn)的二叉鏈表中,空鏈域的個(gè)數(shù)為_(kāi)n+1_o28 . 一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有 _2n1_個(gè)結(jié)點(diǎn).29 .深度為5的二叉樹(shù)至多有 _J31個(gè)結(jié)點(diǎn).30 .假設(shè)某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn),有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子,那么該二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為69.31 .某二叉樹(shù)的前序遍歷序列是abdgcefh,中序序列是dgbaechf,其后序序列為 _gdbehfca_.32 .線索二叉樹(shù)的左線索指向其遍歷序列中的前驅(qū),右線索指向其遍歷序列中的后繼O33 .在各種查找方法中,平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是散列查找法.34 .在分塊索引查找方法中,首先查找索引表 ,

36、然后查找相應(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ù)最多為4537 .圖G的鄰接表如下列圖,其從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序列為v1v2V3V6V5V4 ,其從頂點(diǎn)v1出發(fā)的廣度優(yōu)先搜索序列為 _v1v2 V5V4V3V6.38 .索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu).一個(gè)索引隸屬于某個(gè)數(shù)據(jù)記錄集,它由假設(shè)干索引項(xiàng) 組成,索引項(xiàng)的結(jié)構(gòu)為關(guān)鍵字 和 關(guān)鍵字對(duì)應(yīng)記錄的地址 .39 . Prim算法生成一個(gè)最小生成樹(shù)每一步選擇都要滿(mǎn)足邊的總數(shù)不超過(guò)n-1 ,當(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ù)類(lèi)型ADT 包括定義和實(shí)現(xiàn)兩方面,其中定義是獨(dú)立于實(shí)現(xiàn)的,定義僅給出一個(gè)ADT的邏輯特性,不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn).,3 .抽象數(shù)據(jù)類(lèi)型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無(wú)關(guān).,4 .順序存儲(chǔ)方式插入和刪除時(shí)效率太低,因此它不如鏈?zhǔn)酱鎯?chǔ)方式好.X 5 .線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí),結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)