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

2、 。A. 各結點的值如何B.結點個數的多少C.對數據有哪些運算D.所用的編程語言實現這種結構是否方便。6 .以下說法正確的選項是D 。A. 數據項是數據的根本單位B. 數據元素是數據的最小單位C. 數據結構是帶結構的數據項的集合D. 些外表上很不相同的數據可以有相同的邏輯結構OB.研究算法中的輸入和輸出的關系C.分析算法的易讀性和文檔性B.正確性和簡明性D.數據復雜性和程序復雜性算法分析的目的是J ，算法分析的兩個主要方面是_A1A.找出數據結構的合理性C.分析算法的效率以求改進2A.空間復雜度和時間復雜度C.可讀性和文檔性&下面程序段的時間復雜度是_0(n2)s =0;for( I

3、=0; i<n; i+)for(j=0;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(log3 n)。i = 0;while i<=ni = i * 3 ;11. 在以下的表達中，正確的選項是B 。A. 線性表的順序存儲結構優于鏈表存儲結構B. 二維數組是其數據元素為線性表的線性表C. 棧的操作方式是先進先出D. 隊列的操作方式是先進后出12通常要求同一邏輯結構中的所有數據元素具有相同的特性，這意味

4、著_B_。A. 數據元素具有同一特點B. 不僅數據元素所包含的數據項的個數要相同，而且對應的數據項的類型要一致C. 每個數據元素都一樣D. 數據元素所包含的數據項的個數要相等13.鏈表不具備的特點是A 。A.可隨機訪問任一結點B.插入刪除不需要移動兀素C.不必事先估計存儲空間D.所需空間與其長度成正比14.不帶頭結點的單鏈表head為空的判定條件是AA. head = NULLB head-> next =NULLC. head->next =headD head!=NULL15.帶頭結點的單鏈表head為空的判定條件是B<A. head = NULLB head->

5、next =NULLC. head->next =headD head!=NULL16 假設某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，那么采用D存儲方式最節省運算時間。A. 單鏈表 B.給出表頭指針的單循環鏈表C.雙鏈表D.帶頭結點的雙循環鏈表17需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構是B。A. 單鏈表 B.靜態鏈表C.線性鏈表D.順序存儲結構18 .非空的循環單鏈表head的尾結點由p所指向滿足 C 。A. p->next = NULLB. p = NULLC. p->next =headD. p = head19. 在循環

6、雙鏈表的 p所指的結點之前插入s所指結點的操作是 D_ 。A. p->prior = s; s_>next = p; p->prior->next = s ; s->prior = p->priorB. p->prior = s; p->prior->next = s ; s_>next = p; s->prior = p->priorC. s_>next = p; s->prior = p->prior ; p->prior = s; p->prior->next = sD. s_&g

7、t;next = p; s->prior = p->prior ; p->prior->next = s ; p->prior = s20. 如果最常用的操作是取第i個結點及其前驅，那么采用 D 存儲方式最節省時間。A. 單鏈表 B.雙鏈表C.單循環鏈表D.順序表21. 在一個具有 n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是B。A. O 1 B. OnC. On2 D. O nlog2n22 .在一個長度為 n n>1的單鏈表上，設有頭和尾兩個指針，執行B操作與鏈表的長度有關。A. 刪除單鏈表中的第一個元素B. 刪除單鏈表中的最后一個元

8、素C. 在單鏈表第一個元素前插入一個新元素D. 在單鏈表最后一個元素后插入一個新元素23. 與單鏈表相比，雙鏈表的優點之一是_DA. 插入、刪除操作更簡單B. 可以進行隨機訪問C. 可以省略表頭指針或表尾指針D. 順序訪問相鄰結點更靈活在最后一個元素的后面插入新元素,24. 如果對線性表的操作只有兩種，即刪除第一個元素,那么最好使用B 。A. 只有表頭指針沒有表尾指針的循環單鏈表B. 只有表尾指針沒有表頭指針的循環單鏈表C. 非循環雙鏈表D. 循環雙鏈表25 .在長度為n的順序表的第i個位置上插入一個元素A_。A. n - i + 1B. n - iC. i1w i w n+1，元素的移動次數

9、為:D. i - 126. 對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結構為CA.順序表B.用頭指針表示的循環單鏈表C. 用尾指針表示的循環單鏈表D.單鏈表27. 下述哪一條是順序存儲結構的優點？C 。A插入運算方便B可方便地用于各種邏輯結構的存儲表示C存儲密度大D刪除運算方便28. 下面關于線性表的表達中，錯誤的選項是哪一個？BA線性表采用順序存儲，必須占用一片連續的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈式存儲，不必占用一片連續的存儲單元D線性表采用鏈式存儲，便于進行插入和刪除操作。29 .線性表是具有n個 B的有限序列。A.字符B.數據元素C.數

10、據項D.表元素30. 在n個結點的線性表的數組實現中，算法的時間復雜度是0 1的操作是AA. 訪問第i 1<=i<=n個結點和求第i個結點的直接前驅1<i<=nB. 在第i 1<=i<=n個結點后插入一個新結點C. 刪除第i 1<=i<=n個結點D. 以上都不對31. 假設長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為C 。A. 0(0) B. 0(1)C. 0(n)D. 0(n2)32對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為C 。A. 0(n) 0(n) B. 0(n) 0(1)C. 0(

11、1) 0(n)D. 0(1) 0(1)33 .線性表a1,a2,，an以鏈式方式存儲，訪問第i位置元素的時間復雜度為CA. 0(0) B. 0(1)C. 0(n)D. 0(n2)34. 單鏈表中，增加一個頭結點的目的是為了C 。A.使單鏈表至少有一個結點B.標識表結點中首結點的位置C.方面運算的實現D.說明單鏈表是線性表的鏈式存儲35. 在單鏈表指針為 p的結點之后插入指針為s的結點，正確的操作是B 列。A. p->next=s; s->next=p->nextBC. p->next=s; p->next=s->nextD36. 線性表的順序存儲結構是一種_

12、AA.隨機存取的存儲結構B.C.索引存取的存儲結構D.37. 棧的特點是B ，隊列的特點是A.先進先出B.先進后出38. 棧和隊列的共同點是C 。A.都是先進后出C.只允許在端點處插入和刪除元素s->next=p->next ; p->next=s;p->next=s->next; p->next=s。順序存取的存儲結構Hash存取的存儲結構A39. 一個棧的進棧序列是 a, b, c, d,A. edcba B. decbaC. dceabB. 都是先進先出D. 沒有共同點e,那么棧的不可能的輸出序列是CD. abcdeA. A,B,C,D,E B. B,

13、C,D,E,A C. E,A,B,C,D D. E,D,C,B,A41.以下 B不是隊列的根本運算？A.從隊尾插入一個新元素B.從隊列中刪除第i個元素C. 判斷一個隊列是否為空D.讀取隊頭元素的值1, 2, 3, n,其輸出序列為 pl, p2, p3,，pn,假42假設一個棧的進棧序列是 設pl = n ,那么pi為 C 。A. iB. n iC. n i+ 1 D.不確定43.判定一個順序棧st最多元素為 MaxSize為空的條件是A. st->top != -1C. st->top != MaxSizeB. st->top = -1D. st->top = Max

14、Size44.判定一個順序棧st最多元素為 MaxSize為滿的條件是A. st->top != -1B. st->top = -1C. st->top != MaxSizeD. st->top = MaxSize45.一個隊列的入隊序列是1, 2 , 3 , 4,那么隊列的輸出序列是BA.4 , 3 , 2 , 1B.1 , 2 , 3 , 4C.1, 4, 3 , 2D.3 , 2 , 4 , 146.判定一個循環隊列 qu最多元素為A. qu->rear - qu->front =MaxSizeC. qu->rear =qu->frontM

15、axSize為空的條件是 CB. qu->rear - qu->front -1=MaxSizeD. qu->rear =qu->front -147.在循環隊列中，假設front與rear分別表示對頭元素和隊尾元素的位置，那么判斷循環隊列空的條件是C 。A. front=rear+1B. rear=front+1C. front=rearD. front=048.向一個棧頂指針為A. h->next=s ;C. s->next=h ;h =s ;h的帶頭結點的鏈棧中插入指針s所指的結點時，應執行 D操作。B. s->next=h ;D. s->

16、next=h->next ;h->next=s ;49.輸入序列為 ABC,可以變為 CBA時，經過的棧操作為 B_。A. push, pop , push, pop, push, pop B. push, push, push, pop , pop , popC. push , push , pop , pop , push , pop D. push , pop , push , push , pop , pop50.假設棧采用順序存儲方式存儲，現兩棧共享空間V1 m, top1、top2分別代表第1和第2個棧的棧頂，棧1的底在V1,棧2的底在Vm,那么棧滿的條件是 B_。A.

17、 |top2-top1|=0B.top1+1=top2C. top1+top2=m D. top1=top251 設計一個判別表達式中左、右括號是否配對出現的算法，采用D 數據結構最正確。A.線性表的順序存儲結構B.隊列 C.線性表的鏈式存儲結構D.棧52 允許對隊列進行的操作有A.對隊列中的元素排序C.在隊頭元素之前插入元素D。B. 取出最近進隊的元素D. 刪除隊頭元素53. 對于循環隊列 DA.無法判斷隊列是否為空C. 隊列不可能滿B. 無法判斷隊列是否為滿D. 以上說法都不對54. 假設用一個大小為6的數值來實現循環隊列，且當前 rear和front的值分別為0和3,當從隊列中刪除一個元素，再參加兩個元素后，rear和front的值分別為 _B 。A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 155. 隊列的“先進先出