復習題及參考答案

1、第1-3章 復習題數(shù)據(jù)結構與算法復習題一、選擇題。1在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分為 C 。A動態(tài)結構和靜態(tài)結構 B緊湊結構和非緊湊結構C線性結構和非線性結構 D內(nèi)部結構和外部結構2數(shù)據(jù)結構在計算機內(nèi)存中的表示是指 A 。A數(shù)據(jù)的存儲結構 B數(shù)據(jù)結構 C數(shù)據(jù)的邏輯結構 D數(shù)據(jù)元素之間的關系3在數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的 A 結構。A邏輯 B存儲 C邏輯和存儲 D物理4在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲 C 。A數(shù)據(jù)的處理方法 B數(shù)據(jù)元素的類型 C數(shù)據(jù)元素之間的關系 D數(shù)據(jù)的存儲方法5在決定選取何種存儲結構時，一般不考慮 A 。A各結點的值如何 B結

2、點個數(shù)的多少C對數(shù)據(jù)有哪些運算 D所用的編程語言實現(xiàn)這種結構是否方便。6以下說法正確的是 D 。A數(shù)據(jù)項是數(shù)據(jù)的基本單位B數(shù)據(jù)元素是數(shù)據(jù)的最小單位C數(shù)據(jù)結構是帶結構的數(shù)據(jù)項的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結構7算法分析的目的是 C ，算法分析的兩個主要方面是 A 。（1）A找出數(shù)據(jù)結構的合理性 B研究算法中的輸入和輸出的關系C分析算法的效率以求改進 C分析算法的易讀性和文檔性（2）A空間復雜度和時間復雜度 B正確性和簡明性 C可讀性和文檔性 D數(shù)據(jù)復雜性和程序復雜性8下面程序段的時間復雜度是 O(n2) 。 s =0;for( I =0; i<n; i+) for(j=0

3、;j<n;j+)s +=Bij;sum = s ;9下面程序段的時間復雜度是 O(n*m) 。for( i =0; i<n; i+) for(j=0;j<m;j+)Aij 0;10下面程序段的時間復雜度是 O(log3n) 。i 0；while（i<=n）i = i * 3；11在以下的敘述中，正確的是 B 。A線性表的順序存儲結構優(yōu)于鏈表存儲結構B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C棧的操作方式是先進先出D隊列的操作方式是先進后出12通常要求同一邏輯結構中的所有數(shù)據(jù)元素具有相同的特性，這意味著 B 。A數(shù)據(jù)元素具有同一特點B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而

4、且對應的數(shù)據(jù)項的類型要一致C每個數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等13鏈表不具備的特點是 A 。A可隨機訪問任一結點 B插入刪除不需要移動元素C不必事先估計存儲空間 D所需空間與其長度成正比14不帶頭結點的單鏈表head為空的判定條件是 A 。Ahead = NULL B head->next =NULL Chead->next =head D head!=NULL15帶頭結點的單鏈表head為空的判定條件是 B 。Ahead = NULL B head->next =NULL Chead->next =head D head!=NULL16若某表最常用

5、的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則采用 D 存儲方式最節(jié)省運算時間。A單鏈表 B給出表頭指針的單循環(huán)鏈表 C雙鏈表 D帶頭結點的雙循環(huán)鏈表17需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構是 B 。A單鏈表 B靜態(tài)鏈表 C線性鏈表 D順序存儲結構18非空的循環(huán)單鏈表head的尾結點（由p所指向）滿足 C 。Ap->next = NULL Bp = NULLCp->next =head Dp = head19在循環(huán)雙鏈表的p所指的結點之前插入s所指結點的操作是 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個結點及其前驅，則采用 D 存儲方式最節(jié)省時間。A單鏈表 B雙鏈表 C單循環(huán)鏈表 D 順序表21在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是 B 。AO（1） BO（n） CO（n2） DO（nlog2n）22在一個長度為n（n>1）的單鏈表上，設有頭和尾兩個指針，執(zhí)行 B 操作與鏈表的長度有關。A刪除單鏈表中的第一個元素B刪除單鏈表中的最后一個元素C在單鏈表第一個元素前插入一個新元素D在單鏈表最后一個元素后插入一個新元素23與單鏈表相比，雙鏈表的優(yōu)點之一是 D 。A插入、刪除操作更簡單 B可以進行隨機訪問C可以省略表頭指針或表尾指針D順序訪問相鄰結

8、點更靈活24如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用 B 。A只有表頭指針沒有表尾指針的循環(huán)單鏈表B只有表尾指針沒有表頭指針的循環(huán)單鏈表C非循環(huán)雙鏈表D循環(huán)雙鏈表25在長度為n的順序表的第i個位置上插入一個元素（1 i n+1），元素的移動次數(shù)為： A 。An i + 1 Bn i Ci Di 1 26對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結構為 C 。A順序表 B 用頭指針表示的循環(huán)單鏈表C用尾指針表示的循環(huán)單鏈表 D單鏈表27下述哪一條是順序存儲結構的優(yōu)點？ C 。A插入運算方便 B可方便地用于各種邏輯結構的存儲表示C存儲密

9、度大 D刪除運算方便28下面關于線性表的敘述中，錯誤的是哪一個？ B 。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元D線性表采用鏈式存儲，便于進行插入和刪除操作。29線性表是具有n個 B 的有限序列。A字符 B數(shù)據(jù)元素 C數(shù)據(jù)項 D表元素30在n個結點的線性表的數(shù)組實現(xiàn)中，算法的時間復雜度是O（1）的操作是 A 。A訪問第i（1<=i<=n）個結點和求第i個結點的直接前驅（1<i<=n）B在第i（1<=i<=n）個結點后插入一個新結點C刪除第i（1<=i&

10、lt;=n）個結點D以上都不對31若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為 C 。AO(0) BO(1) CO(n) DO(n2)32對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為 C 。AO(n) O(n) BO(n) O(1) CO(1) O(n) DO(1) O(1)33線性表（a1,a2, ,an）以鏈式方式存儲，訪問第i位置元素的時間復雜度為 C 。AO(0) BO(1) CO(n) DO(n2)34單鏈表中，增加一個頭結點的目的是為了 C 。A使單鏈表至少有一個結點 B標識表結點中首結點的位置C方面運算的實現(xiàn) D說明單鏈表是

11、線性表的鏈式存儲35在單鏈表指針為p的結點之后插入指針為s的結點，正確的操作是 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線性表的順序存儲結構是一種 A 。A隨機存取的存儲結構 B順序存取的存儲結構C索引存取的存儲結構 DHash存取的存儲結構37棧的特點是 B ，隊列的特點是 A 。A先進先出 B先進后出38棧和隊列的共同點是 C 。A都

12、是先進后出 B都是先進先出C只允許在端點處插入和刪除元素 D沒有共同點39一個棧的進棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 C 。Aedcba Bdecba Cdceab Dabcde40設有一個棧，元素依次進棧的順序為A、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 不是隊列的基本運算？A從隊尾插入一個新元素 B從隊列中刪除第i個元素C判斷一個隊列是否為空 D讀取隊頭元素的值42若已知一個棧的進棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1n，則pi為 C

13、。Ai Bni Cni1 D不確定43判定一個順序棧st（最多元素為MaxSize）為空的條件是 B 。Ast->top != -1 Bst->top = -1 Cst->top != MaxSize D st->top = MaxSize 44判定一個順序棧st（最多元素為MaxSize）為滿的條件是 D 。Ast->top != -1 Bst->top = -1 Cst->top != MaxSize Dst->top = MaxSize 45一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是 B 。A4，3，2，1 B1，2，3，4C1

14、，4，3，2 D3，2，4，146判定一個循環(huán)隊列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)隊列中，若front與rear 分別表示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條件是 C 。 Afront=rear+1 Brear=front+1 Cfront=rear Dfront=048向一個棧頂指針為h的帶頭結點的

15、鏈棧中插入指針s所指的結點時，應執(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時，經(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若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1 m，top1、top2分別代

16、表第1和第2個棧的棧頂，棧1的底在V1，棧2的底在Vm，則棧滿的條件是 B 。A|top2-top1|=0 B top1+1=top2 Ctop1+top2=m Dtop1=top251設計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用 D 數(shù)據(jù)結構最佳。A線性表的順序存儲結構 B隊列 C線性表的鏈式存儲結構 D棧52允許對隊列進行的操作有 D 。A對隊列中的元素排序 B取出最近進隊的元素 C在隊頭元素之前插入元素 D刪除隊頭元素53對于循環(huán)隊列 D 。A無法判斷隊列是否為空 B無法判斷隊列是否為滿 C隊列不可能滿 D以上說法都不對54若用一個大小為6的數(shù)值來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為 B 。A1和5 B2和4 C4和2 D5和155隊列的“先進先出”特