復(fù)習(xí)題及參考答案

1、第1-3章 復(fù)習(xí)題數(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物理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é)

2、點(diǎn)個(gè)數(shù)的多少C對(duì)數(shù)據(jù)有哪些運(yùn)算 D所用的編程語(yǔ)言實(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正確性和簡(jiǎn)明性 C可讀性和文檔性 D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8下面程序段的時(shí)間復(fù)雜度是 O(n2) 。 s =0;for( I =0; i<n; i+) for(j=0

3、;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ù)元素具有相同的特性，這意味著 B 。A數(shù)據(jù)元素具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而

4、且對(duì)應(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所需空間與其長(zhǎng)度成正比14不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 A 。Ahead = NULL B head->next =NULL Chead->next =head D head!=NULL15帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 B 。Ahead = NULL B head->next =NULL Chead->next =head D head!=NULL16若某表最常用

5、的操作是在最后一個(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 = NULLCp->next =head Dp = head19在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是 D 。Ap->prior = s；s->next = p；p->

6、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 = s20如果最常用的操作

7、是取第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（n>1）的單鏈表上，設(shè)有頭和尾兩個(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ī)訪問C可以省略表頭指針或表尾指針D順序訪問相鄰結(jié)

8、點(diǎn)更靈活24如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用 B 。A只有表頭指針沒有表尾指針的循環(huán)單鏈表B只有表尾指針沒有表頭指針的循環(huán)單鏈表C非循環(huán)雙鏈表D循環(huán)雙鏈表25在長(zhǎng)度為n的順序表的第i個(gè)位置上插入一個(gè)元素（1 i n+1），元素的移動(dòng)次數(shù)為： A 。An i + 1 Bn i Ci Di 1 26對(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ǔ)密

9、度大 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表元素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&

10、lt;=n）個(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ǔ)的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為 C 。AO(n) O(n) BO(n) O(1) CO(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說明單鏈表是

11、線性表的鏈?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->next=s->next Dp->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) 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都

12、是先進(jìn)后出 B都是先進(jìn)先出C只允許在端點(diǎn)處插入和刪除元素 D沒有共同點(diǎn)39一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 C 。Aedcba Bdecba Cdceab Dabcde40設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E。下列 C 是不可能的出棧序列。 AA,B,C,D,E BB,C,D,E,A CE,A,B,C,D DE,D,C,B,A41以下 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

13、。Ai Bni Cni1 D不確定43判定一個(gè)順序棧st（最多元素為MaxSize）為空的條件是 B 。Ast->top != -1 Bst->top = -1 Cst->top != MaxSize 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，4C1

14、，4，3，2 D3，2，4，146判定一個(gè)循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是 C 。Aqu->rear qu->front =MaxSize Bqu->rear qu->front -1=MaxSize Cqu->rear =qu->front D qu->rear =qu->front -147在循環(huán)隊(duì)列中，若front與rear 分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是 C 。 Afront=rear+1 Brear=front+1 Cfront=rear Dfront=048向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的

15、鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 D 操作。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)過的棧操作為 B 。Apush，pop，push，pop，push，pop Bpush，push，push，pop， pop， pop Cpush，push，pop， pop，push，pop Dpush，pop，push，push，pop， pop50若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1 m，top1、top2分別代

16、表第1和第2個(gè)棧的棧頂，棧1的底在V1，棧2的底在Vm，則棧滿的條件是 B 。A|top2-top1|=0 B top1+1=top2 Ctop1+top2=m Dtop1=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對(duì)于循環(huán)隊(duì)列 D 。A無(wú)法判斷隊(duì)列是否為空 B無(wú)法判斷隊(duì)列是否為滿 C隊(duì)列不可能滿 D以上說法都不對(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的值分別為 B 。A1和5 B2和4 C4和2 D5和155隊(duì)列的“先進(jìn)先出”特