數(shù)據(jù)結(jié)構(gòu)與算法期末考試復(fù)習(xí)試題(共18頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(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ī)無關(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í)，一般不考慮

2、 A 。 A各結(jié)點(diǎn)的值如何 B結(jié)點(diǎn)個(gè)數(shù)的多少 C對數(shù)據(jù)有哪些運(yùn)算 D所用的編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。 6以下說法正確的是 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正確性和簡明性 C可讀性和文檔性 D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 8下面程序段的時(shí)間復(fù)雜度是 O(n2) 。 s =0;

3、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(log3n) 。 i 0； while（i<=n） i = i * 3； 11在以下的敘述中，正確的是 B 。 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ù)元素具有相同

4、的特性，這意味著 B 。 A數(shù)據(jù)元素具有同一特點(diǎn) B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致 C每個(gè)數(shù)據(jù)元素都一樣 D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等 13鏈表不具備的特點(diǎn)是 A 。 A可隨機(jī)訪問任一結(jié)點(diǎn) B插入刪除不需要移動(dòng)元素 C不必事先估計(jì)存儲(chǔ)空間 D所需空間與其長度成正比 14不帶頭結(jié)點(diǎn)的單鏈表 head 為空的判定條件是 A 。 Ahead = NULL B head->next =NULL Chead->next =head D head!=NULL 15帶頭結(jié)點(diǎn)的單鏈表 head 為空的判定條件是 B 。 Ahead = NULL B h

5、ead->next =NULL Chead->next =head D head!=NULL 16若某表最常用的操作是在最后一個(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)是 B 。 A單鏈表 B靜態(tài)鏈表 C線性鏈表 D順序存儲(chǔ)結(jié)構(gòu) 18非空的循環(huán)單鏈表 head 的尾結(jié)點(diǎn)（由 p 所指向）滿足 C 。 Ap->next = NULL Bp = NULL Cp->next =head Dp = hea

6、d 19在循環(huán)雙鏈表的 p 所指的結(jié)點(diǎn)之前插入 s 所指結(jié)點(diǎn)的操作是 D 。 Ap->prior = s；s->next = p；p->prior->next = s；s->prior = p->prior Bp->prior = s；p->prior->next = s；s->next = p；s->prior = p->prior Cs->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s Ds->next

7、= p；s->prior = p->prior；p->prior->next = s；p->prior = s 20如果最常用的操作是取第 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è)長度為 n（n>1）的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行 B 操作與鏈表的長度有關(guān)。 A刪除單鏈表中的第一個(gè)元素 B刪除單鏈表中的最后一個(gè)元素 C在單鏈表第一個(gè)元

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

9、操作的線性表，宜采用的存儲(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)于線性表的敘述中，錯(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表元素

10、30在 n 個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是 O（1）的操作是 A 。 A訪問第 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以上都不對 31若長度為 n 的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第 i 個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為 C 。 AO(0) BO(1) CO(n) DO(n2) 32對于順序存儲(chǔ)的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為 C 。 AO(n) O(n) BO(n) O(1) CO(

11、1) O(n) DO(1) O(1) 33線性表（a1,a2, ,an）以鏈?zhǔn)椒绞酱鎯?chǔ)，訪問第 i 位置元素的時(shí)間復(fù)雜度為 C 。 AO(0) BO(1) CO(n) DO(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說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ) 35在單鏈表指針為 p 的結(jié)點(diǎn)之后插入指針為 s 的結(jié)點(diǎn)，正確的操作是 B 。 Ap->next=s；s->next=p->next B s->next=p->next ；p->next=s; Cp->next=s；p-&

12、gt;next=s->next Dp->next=s->next；p->next=s 36線性表的順序存儲(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沒有共同點(diǎn) 39一個(gè)棧的進(jìn)棧序列是 a，b，c，d，e，則棧的不可能的輸出序列是 C 。 Aedcba Bdecba Cdceab Dabcde 40設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)?A、B

13、、C、D、E。下列 C 是不可能的出棧序列。 AA,B,C,D,E BB,C,D,E,A CE,A,B,C,D DE,D,C,B,A 41以下 B 不是隊(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 為 C 。 Ai Bni Cni1 D不確定 43判定一個(gè)順序棧 st（最多元素為 MaxSize）為空的條件是 B 。 Ast->top != -1 Bst->top = -1 Cst->top != Ma

14、xSize D st->top = MaxSize 44判定一個(gè)順序棧 st（最多元素為 MaxSize）為滿的條件是 D 。 Ast->top != -1 Bst->top = -1 Cst->top != MaxSize Dst->top = MaxSize 45一個(gè)隊(duì)列的入隊(duì)序列是 1，2，3，4，則隊(duì)列的輸出序列是 B 。 A4，3，2，1 B1，2，3，4 C1，4，3，2 D3，2，4，1 46判定一個(gè)循環(huán)隊(duì)列 qu（最多元素為 MaxSize）為空的條件是 C 。 Aqu->rear qu->front =MaxSize Bqu->

15、rear qu->front -1=MaxSize Cqu->rear =qu->front D qu->rear =qu->front -1 47在循環(huán)隊(duì)列中，若 front 與 rear 分別表示對頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是 C 。 Afront=rear+1 Brear=front+1 Cfront=rear Dfront=0 48向一個(gè)棧頂指針為 h 的帶頭結(jié)點(diǎn)的鏈棧中插入指針 s 所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 D 操作。 Ah->next=s ; Bs->next=h ; Cs->next=h ;h =s ; Ds->

16、;next=h->next ;h->next=s ; 49輸入序列為 ABC，可以變?yōu)?CBA 時(shí)，經(jīng)過的棧操作為 B 。 Apush，pop，push，pop，push，pop Bpush，push，push，pop， pop， pop Cpush，push，pop， pop，push，pop Dpush，pop，push，push，pop， pop 50若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間 V1 m，top1、top2分別代表第 1 和第 2 個(gè)棧的棧頂，棧 1 的底在 V1，棧 2 的底在 Vm，則棧滿的條件是 B 。 A|top2-top1|=0 B top1+1=to

17、p2 Ctop1+top2=m Dtop1=top2 51設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對出現(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ì)列進(jìn)行的操作有 D 。 A對隊(duì)列中的元素排序 B取出最近進(jìn)隊(duì)的元素 C在隊(duì)頭元素之前插入元素 D刪除隊(duì)頭元素 53對于循環(huán)隊(duì)列 D 。 A無法判斷隊(duì)列是否為空 B無法判斷隊(duì)列是否為滿 C隊(duì)列不可能滿 D以上說法都不對 54若用一個(gè)大小為 6 的數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear 和 front 的值分別為 0 和 3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear 和 front 的

18、值分別為 B 。 A1 和 5 B2 和 4 C4 和 2 D5 和 1 55隊(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)勢是 A 。 A通常不會(huì)出現(xiàn)棧滿的情況 B 通常不會(huì)出現(xiàn)?？盏那闆r 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ì)尾指針都可能要

19、修改 D隊(duì)頭、隊(duì)尾指針都要修改 58若串 S=software，其子串的數(shù)目是 B 。 A8 B37 C36 D9 59串的長度是指 B 。 A串中所含不同字母的個(gè)數(shù) B串中所含字符的個(gè)數(shù) C串中所含不同字符的個(gè)數(shù) D串中所含非空格字符的個(gè)數(shù) 60串是一種特殊的線性表，其特殊性體現(xiàn)在 B 。 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)算稱為 B 。 A連接 B 模式匹配 C求子串 D求串長 62數(shù)組 A 中，每個(gè)元素的長度為 3 個(gè)字節(jié)，行下標(biāo) i 從 1 到 8，列下標(biāo) j 從 1 到 10

20、，從首地址 SA 開始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素 A85的起始地址為 C 。 ASA141 B SA144 CSA222 DSA225 63數(shù)組 A 中，每個(gè)元素的長度為 3 個(gè)字節(jié)，行下標(biāo) i 從 1 到 8，列下標(biāo) j 從 1 到 10，從首地址 SA 開始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素 A58的起始地址為 C 。 ASA141 B SA180 CSA222 DSA225 64若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下： froat average=new float30; 假設(shè)該數(shù)組的內(nèi)存起始位置為 200， average15的內(nèi)存地址是 C 。 A214 B215 C260 D

21、256 65設(shè)二維數(shù)組 A1 m,1 n按行存儲(chǔ)在數(shù)組 B 中，則二維數(shù)組元素 Ai,j在一維數(shù)組 B 中的下標(biāo)為 A 。 An*(i-1)+j B n*(i-1)+j-1 Ci*(j-1) Dj*m+i-1 66有一個(gè) 100×90 的稀疏矩陣，非 0 元素有 10，設(shè)每個(gè)整型數(shù)占 2 個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是 B 。 A20 B 66 C18 000 D33 67數(shù)組 A0 4，-1 -3，5 7中含有的元素個(gè)數(shù)是 A 。 A55 B 45 C36 D16 68對矩陣進(jìn)行壓縮存儲(chǔ)是為了 D 。 A方便運(yùn)算 B 方便存儲(chǔ) C提高運(yùn)算速度 D減少存儲(chǔ)空間 69設(shè)

22、有一個(gè) 10 階的對稱矩陣 A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a1，1為第一個(gè)元素，其存儲(chǔ)地址為 1，每個(gè)元素占 1 個(gè)地址空間，則 a8，5的地址為 B 。 A13 B 33 C18 D40 70稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即 C 。 A二維數(shù)組和三維數(shù)組 B 三元組和散列 C三元組和十字鏈表 D 散列和十字鏈表 71樹最適合用來表示 C 。 A有序數(shù)據(jù)元素 B無序數(shù)據(jù)元素 C元素之間具有分支層次關(guān)系的數(shù)據(jù) D元素之間無聯(lián)系的數(shù)據(jù) 72深度為 5 的二叉樹至多有 C 個(gè)結(jié)點(diǎn)。 A16 B 32 C 31 C 10 73對一個(gè)滿二叉樹，m 個(gè)葉子，n 個(gè)結(jié)點(diǎn)，深度為 h，則 D 。

23、An = h+m B h+m = 2n C m = h-1 D n = 2h-1 74任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序 A 。 A不發(fā)生改變 B發(fā)生改變 C不能確定 D以上都不對 75在線索化樹中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若 0 標(biāo)識(shí)樹結(jié)構(gòu)信息，1 標(biāo)識(shí)線索，對應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)為_ D _。 A00 B01 C10 D11 76在下述論述中，正確的是 D 。 只有一個(gè)結(jié)點(diǎn)的二叉樹的度為 0；二叉樹的度為 2；二叉樹的左右子樹可任意交換； 深度為 K 的順序二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。

24、 A B C D 77設(shè)森林 F 對應(yīng)的二叉樹為 B，它有 m 個(gè)結(jié)點(diǎn)，B 的根為 p，p 的右子樹的結(jié)點(diǎn)個(gè)數(shù)為 n，森林 F 中第一棵樹的結(jié)點(diǎn)的個(gè)數(shù)是 A 。 Am-n Bm-n-1 Cn+1 D不能確定 78若一棵二叉樹具有 10 個(gè)度為 2 的結(jié)點(diǎn)，5 個(gè)度為 1 的結(jié)點(diǎn)，則度為 0 的結(jié)點(diǎn)的個(gè)數(shù)是 B 。 A9 B11 C15 D不能確定 79具有 10 個(gè)葉子結(jié)點(diǎn)的二叉樹中有 B 個(gè)度為 2 的結(jié)點(diǎn)。 A8 B9 C10 D11 80在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 C 倍。 A1/2 B 1 C 2 D 4 81在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之

25、和的 B 倍。 A1/2 B 1 C 2 D 4 82某二叉樹結(jié)點(diǎn)的中序序列為 ABCDEFG，后序序列為 BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為： C A3 B2 C4 D5 83已知一算術(shù)表達(dá)式的中綴形式為 AB *CD/E，后綴形式為 ABC *+DE/，其前綴形式為 D 。 AA+B*C/DE BA+B*CD/E C +*ABC/DE D+A*BC/DE abcdef84已知一個(gè)圖，如圖所示，若從頂點(diǎn) a 出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_D_；按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_A_； Aa，b，e，c，d，f Ba，c，f，e，b，d Ca，e，b

26、，c，f，d， Da，e，d，f，c，b Aa，b，c，e，d，f Ba，b，c，e，f，d Ca，e，b，c，f，d， Da，c，f，d，e，b 85采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的_A_。 A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷 86采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的_D_。 A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷 87具有 n 個(gè)結(jié)點(diǎn)的連通圖至少有 A 條邊。 A n-1 B n C n(n-1)/2 D 2n 88廣義表（a），a）的表頭是 C ，表尾是 C 。 Aa B （） C （a） D （a） 89廣義表（a）的表頭是 C ，表

27、尾是 B 。 Aa B （） C （a） D （a） 90順序查找法適合于存儲(chǔ)結(jié)構(gòu)為 B 的線性表。 A 散列存儲(chǔ) B 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ) C 壓縮存儲(chǔ) D 索引存儲(chǔ) 91對線性表進(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)鍵字有序排列 92采用折半查找法查找長度為 n 的線性表時(shí)，每個(gè)元素的平均查找長度為 D 。 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)折

28、半查找值為 82 的結(jié)點(diǎn)時(shí)， C 次比較后查找成功。 A 11 B 5 C 4 D 8 94二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法 B 。 A 正確 B 錯(cuò)誤 95下面關(guān)于 B 樹和 B+樹的敘述中，不正確的結(jié)論是 A 。 A B 樹和 B+樹都能有效的支持順序查找 B B 樹和 B+樹都能有效的支持隨機(jī)查找 C B 樹和 B+樹都是平衡的多叉樹 D B 樹和 B+樹都可用于文件索引結(jié)構(gòu) 96以下說法錯(cuò)誤的是 B 。 A散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址 B散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。 C負(fù)載因子是散列

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

30、0堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列 D 是一個(gè)堆。 A94,31,53,23,16,72 B94,53,31,72,16,23 C16,53,23,94,31,72 D16,31,23,94,53,72 101堆排序是一種 B 排序。 A插入 B選擇 C交換 D歸并 102 D 在鏈表中進(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) 、 樹形結(jié)構(gòu) 和 圖狀結(jié)構(gòu) 三種類型，樹形結(jié)構(gòu)和圖

31、狀結(jié)構(gòu)合稱非線性結(jié)構(gòu) 。 2數(shù)據(jù)的邏輯結(jié)構(gòu)分為 集合 、線性結(jié)構(gòu) 、 樹形結(jié)構(gòu) 和 圖狀結(jié)構(gòu) 4 種。 3在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(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)中元素之間存在 一對一 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 一對多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對多 關(guān)系。 5在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以 任意多個(gè) 。 6數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是 順序 、 鏈?zhǔn)?、 索引 和 散列 存儲(chǔ) 。 7衡

32、量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和 時(shí)間復(fù)雜度與 空間復(fù)雜度 。 8評(píng)估一個(gè)算法的優(yōu)劣，通常從 時(shí)間復(fù)雜度 和 空間復(fù)雜度 兩個(gè)方面考察。 9算法的 5 個(gè)重要特性是 有窮性 、 確定性 、 可行性 、輸入和輸出。 10在一個(gè)長度為 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) n 個(gè)數(shù)據(jù)元素，移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與 位置有關(guān)。 14當(dāng)線性表的元素總數(shù)基

33、本穩(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)是通過 下標(biāo) 表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過 指針 表示元素之間的關(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è)字符的串 ，其長度等于 零?？瞻状怯梢粋€(gè)或多個(gè)空格字符組成的串，其長度等于其包含的空格個(gè)數(shù)。 20

34、組成串的數(shù)據(jù)元素只能是 單個(gè)字符 。 21一個(gè)字符串中 任意個(gè)連續(xù)字符構(gòu)成的部分 稱為該串的子串。 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）的長度是 3 ，深度是 4 。 26在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為 n0，度為 2 的結(jié)點(diǎn)的

35、個(gè)數(shù)為 n2，則有 n0 n2+1 。 27在有 n 個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為_n+1_。 28一棵有 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有_2n-1_個(gè)結(jié)點(diǎn)。 29深度為 5 的二叉樹至多有 31 個(gè)結(jié)點(diǎn)。 30若某二叉樹有 20 個(gè)葉子結(jié)點(diǎn)，有 30 個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總結(jié)點(diǎn)個(gè)數(shù)為 69 。 31某二叉樹的前序遍歷序列是 abdgcefh，中序序列是 dgbaechf，其后序序列為 gdbehfca 。 32線索二叉樹的左線索指向其 遍歷序列中的前驅(qū) ，右線索指向其遍歷序列中的后繼 。 33在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù) n 無關(guān)的查找方法是 散列查找法 。 34

36、在分塊索引查找方法中，首先查找 索引表 ，然后查找相應(yīng)的 塊表 。 35一個(gè)無序序列可以通過構(gòu)造一棵 二叉排序 樹而變成一個(gè)有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。 36具有 10 個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為_45_。 37已知圖 G 的鄰接表如圖所示，其從頂點(diǎn) v1 出發(fā)的深度優(yōu)先搜索序列為_v1v2v3v6v5v4_，其從頂點(diǎn) v1 出發(fā)的廣度優(yōu)先搜索序列為_v1v2v5v4v3v6_。 v1v2v3v4v5v6v3v2v6v4v5v5v6v3v4 38索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)索引隸屬于某個(gè)數(shù)據(jù)記錄集，它由若干索引項(xiàng)組成，索引項(xiàng)的結(jié)構(gòu)為 關(guān)鍵字 和

37、關(guān)鍵字對應(yīng)記錄的地址 。 39Prim 算法生成一個(gè)最小生成樹每一步選擇都要滿足 邊的總數(shù)不超過 n-1 ， 當(dāng)前選擇的邊的權(quán)值是候選邊中最小的 ， 選中的邊加入樹中不產(chǎn)生回路 三項(xiàng)原則。 40在一棵 m 階 B 樹中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)最多有 m 棵子樹，最少有 m/2 棵子樹。 三、判斷題。 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)。( ) 3抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(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對任何數(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取線