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

2、，一般不考慮A °A. 各結點的值如何B .結點個數的多少C對數據有哪些運算 D .所用的編程語言實現這種結構是否方便。6. 以下說確的是_D°A. 數據項是數據的根本單位B. 數據元素是數據的最小單位C. 數據結構是帶結構的數據項的集合D. 些外表上很不一樣的數據可以有一樣的邏輯結構7. 算法分析的目的是 C，算法分析的兩個主要方面是_A°1A.找出數據結構的合理性B.研究算法中的輸入和輸出的關系C.分析算法的效率以求改進C.分析算法的易讀性和文檔性2A.空間復雜度和時間復雜度B.正確性和簡明性C可讀性和文檔性D.數據復雜性和程序復雜性8下面程序段的時間復雜度是

3、0(n 2)。s =0;for( I =0; i<n; i+)for(j=0;j <n ;j+)s +=Bij；sum = s ;9 下面程序段的時間復雜度是0(n*m)。for( i =0; i<n; i+)for(j=0;j<m;j+)Aij 二 0;10下面程序段的時間復雜度是O(log 3n)i = 0 ；while i<=ni = i * 311 在以下的表達中，正確的選項是 _BA. 線性表的順序存儲結構優于鏈表存儲結構B. 二維數組是其數據元素為線性表的線性表C棧的操作方式是先進先出D.隊列的操作方式是先進后出12通常要求同一邏輯結構中的所有數據元素

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

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

6、循環雙鏈表的p所指的結點之前插入s所指結點的操作是_D；s->next = p ; p->prior->next = s;s->prior = p->priorB.p->prior :=s;p->prior->next = sC.s->n ext =:p;s->prior =p->priorD.s->n ext =:p;s->prior =p->priorA. p->prior = s;s->next = p ; s->prior = p->prior;p->prior = s ;

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

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

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

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

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

12、t ； p->n ext=s;C. p->next=s ; p->next=s->nextD. p->next=s->next ; p->next=s36. 線性表的順序存儲結構是一種_A_。A.隨機存取的存儲結構B.順序存取的存儲結構C.索引存取的存儲結構D. Hash存取的存儲結構37. 棧的特點是_B，隊列的特點是 A。A.先進先出B .先進后出38. 棧和隊列的共同點是_C。A.都是先進后出B.都是先進先出C只允許在端點處插入和刪除元素D.沒有共同點39. 個棧的進棧序列是a, b, c, d, e,那么棧的不可能的輸出序列是 C_。A. ed

13、cba B . decba C . dceab D . abcde40. 設有一個棧，元素依次進棧的順序為 能的出棧序列。A、B、C、D E。以下 C 是不可E,A,B,C,D D . E,D,C,B,AA. A,B,C,D,E B . B,C,D,E,A C41 .以下_B不是隊列的根本運算？A.從隊尾插入一個新元素B.從隊列中刪除第i個元素C.判斷一個隊列是否為空D.讀取隊頭元素的值42. 假設一個棧的進棧序列是1, 2, 3, n,其輸出序列為pl, p2, p3, pn,假設p1 = n,那么pi為C 。A. i B . n i C . n i +1 D .不確定43. 判定一個順序棧

14、st最多元素為MaxSize為空的條件是_B_A. st->top != -1B. st->top = -1C. st->top != MaxSize D . st->top = MaxSize44. 判定一個順序棧st最多元素為MaxSize為滿的條件是_D_A. st->top != -1B. st->top = -1C. st->top != MaxSize D . st->top = MaxSize45. 個隊列的入隊序列是1, 2, 3, 4,那么隊列的輸出序列是_B_A. 4, 3, 2, 1B. 1, 2, 3, 4C. 1, 4,

15、 3, 2D. 3, 2, 4, 146 .判定一個循環隊列qu最多元素為MaxSize為空的條件是_C。A . qu->rear - qu->front =MaxSize B. qu->rear - qu->front -1=MaxSizeC . qu->rear =qu->frontD. qu->rear =qu->front -147 .在循環隊列中，假設front與rear分別表示對頭元素和隊尾元素的位置,那么判斷循環隊列空的條件是_CA . fron t=rear+1 B . rear=fr on t+1 C . fron t=rear

16、D . fron t=048 .向一個棧頂指針為h的帶頭結點的鏈棧中插入指針s所指的結點時，應執 行_D操作。A . h->n ext=s; B . s->n ext=h;C. s->next=h ;h =sD . s->next=h->next;h->next=s49. 輸入序列為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, p

17、op, push, push, pop, pop50. 假設棧采用順序存儲方式存儲，現兩棧共享空間V1 m , top1、top2分別代表第1和第2個棧的棧頂，棧1的底在V1，棧2的底在Vm，那么棧 滿的條件是 B 。A. |top2-top1|=0 B. top1+1=top2 C . top1+top2=mD. top1=top251. 設計一個判別表達式中左、右括號是否配對出現的算法，采用_D_ 數據結構最正確。A.線性表的順序存儲結構B .隊列C .線性表的鏈式存儲結構D.棧52. 允許對隊列進展的操作有_D。A.對隊列中的元素排序B.取出最近進隊的元素C.在隊頭元素之前插入元素D .

18、刪除隊頭元素53. 對于循環隊列D。A.無法判斷隊列是否為空B.無法判斷隊列是否為滿C.隊列不可能滿D .以上說法都不對54. 假設用一個大小為6的數值來實現循環隊列，且當前rear和front的值分 別為0和3,當從隊列中刪除一個元素，再參加兩個元素后， rear和front的 值分別為_B。A. 1 和 5 B . 2 和 4 C . 4 和 2 D . 5 和 155 隊列的“先進先出特性是指 _D。A. 最早插入隊列中的元素總是最后被刪除B. 當同時進展插入、刪除操作時，總是插入操作優先C. 每當有刪除操作時，總是要先做一次插入操作D. 每次從隊列中刪除的總是最早插入的元素56. 和順

19、序棧相比，鏈棧有一個比較明顯的優勢是 _A_。A.通常不會出現棧滿的情況B .通常不會出現?？盏那闆rC.插入操作更容易實現D.刪除操作更容易實現57. 用不帶頭結點的單鏈表存儲隊列，其頭指針指向隊頭結點，尾指針指向隊 尾結點，那么在進展出隊操作時_C 0A.僅修改隊頭指針B.僅修改隊尾指針C.隊頭、隊尾指針都可能要修改D隊頭、隊尾指針都要修改58 .假設串S= software '，其子串的數目是B 。A. 8 B . 37 C . 36 D . 959 .串的長度是指_B oA.串中所含不同字母的個數C.串中所含不同字符的個數B .串中所含字符的個數D .串中所含非空格字符的個數60

20、 .串是一種特殊的線性表，其特殊性表達在 _BA.可以順序存儲B .數據元素是一個字符C.可以鏈式存儲D .數據元素可以是多個字符61 .設有兩個串p和q，求q在p中首次出現的位置的運算稱為BA.連接 B .模式匹配 C 求子串D 求串長62. 數組A中，每個元素的長度為3個字節，行下標i從1到8,列下標j從1 到10，從首地址SA開場連續存放的存儲器，該數組按行存放，元素 A85的 起始地址為 C 。A. SA+141 B . SA+144 C . SA+ 222 D . SA+ 22563. 數組A中，每個元素的長度為3個字節，行下標i從1到8,列下標j從1 到10，從首地址SA開場連續存

21、放的存儲器，該數組按行存放，元素 A58的 起始地址為 C 。A. SA+141 B . SA+180 C . SA+ 222 D . SA+ 22564 .假設聲明一個浮點數數組如下：froat average=new float30;假設該數組的存起始位置為200，average15的存地址是_C。A. 214 B . 215 C . 260 D . 25665.設二維數組A1m,1n按行存儲在數組B中，那么二維數組元素Ai,j在一維數組B中的下標為 A 。A. n*(i-1)+j B . n*(i-1)+j-1 C . i*(j-1) D . j*m+i-166 .有一個100X 90的

22、稀疏矩陣，非0元素有10,設每個整型數占2個字節,那么用三元組表示該矩陣時，所需的字節數是B 。A. 20 B . 66 C . 18 000 D . 3367 .數組A04，-1-3，57中含有的元素個數是_A。A. 55 B . 45 C . 36 D . 1668 .對矩陣進展壓縮存儲是為了D 。A.方便運算B .方便存儲C .提高運算速度D .減少存儲空間69. 設有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，ai, i 為第一個元素，其存儲地址為1,每個元素占1個地址空間，那么a8,5的地址 為 _B_。A. 13 B . 33 C . 18 D . 4070. 稀疏矩

23、陣一般的壓縮存儲方式有兩種，即 _C_A.二維數組和三維數組B .C.三元組和十字鏈表D .71. 樹最適合用來表示C 。A.有序數據元素BC.元素之間具有分支層次關系的數據72 .深度為5的二叉樹至多有 C三元組和散列散列和十字鏈表.無序數據元素D .元素之間無聯系的數據 個結點。A. 16 B . 32 C .31 C .1073. 對一個滿二叉樹，m個葉子，n個結點，深度為h,那么DA. n = h+m B h+m = 2n C m = h-1 D n = 2h-174. 任何一棵二叉樹的葉子結點在前序、中序和后序遍歷序列中的相對次序A_。A.不發生改變B.發生改變C.不能確定D .以上

24、都不對75. 在線索化樹中，每個結點必須設置一個標志來說明它的左、右鏈指向的是樹結構信息，還是線索化信息，假設 0標識樹結構信息，1標識線索，對應 葉結點的左右鏈域，應標識為_ D _ 。A. 00B. 01C . 10D. 1176. 在下述論述中，正確的選項是D只有一個結點的二叉樹的度為 0;二叉樹的度為2;二叉樹的左右子樹可 任意交換；深度為K的順序二叉樹的結點個數小于或等于深度一樣的滿二叉樹。A. B .C . D .77. 設森林F對應的二叉樹為B,它有m個結點，B的根為p, p的右子樹的結 點個數為n,森林F中第一棵樹的結點的個數是_A。A. m-n B . m-n-1 C . n

25、+1 D .不能確定78. 假設一棵二叉樹具有10個度為2的結點，5個度為1的結點，那么度為0 的結點的個數是B 。A. 9 B . 11 C . 15 D .不能確定79. 具有10個葉子結點的二叉樹中有B 個度為2的結點。A. 8 B . 9 C . 10 D . 1180 .在一個無向圖中，所有頂點的度數之和等于所有邊數的_C_ 倍。A . 1/2 B 1 C 2 D 481 .在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的_B倍A . 1/2 B 1 C 2 D 482 .某二叉樹結點的中序序列為 ABCDEF,G后序序列為BDCAFGE那么其左子樹中結點數目為：CA. 3

26、B . 2C . 4D. 583 . 一算術表達式的中綴形式為 A+ B *C - D/E,后綴形式為ABC *+DE/-,其前綴形式為D 。A. A+B*C/DE B A+B*CD/E C +*ABC/DED . - +A*BC/DE84. 一個圖，如下列圖，假設從頂點 a出發按深度搜 索法進展遍歷，那么可能得到的一種頂點序列為_D_;按廣度搜索法進展遍歷，那么可能得到的一種頂點序列為A ；A. a， b， e，c，d，f B b，dC . a， e， b， c， f ， d，D . a，e，d，f，c， bA. a， b， c，e，d，f B.a， b， c， e， f， dC . a，

27、e， b， c， f ， d，D . a，c，f，d，e， b85. 采用鄰接表存儲的圖的深度優先遍歷算法類似于二叉樹的AA.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷86. 采用鄰接表存儲的圖的廣度優先遍歷算法類似于二叉樹的DA.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷87. 具有n個結點的連通圖至少有_A條邊。A .n-1 B . n C . n(n-1)/2D . 2n88. 廣義表a，a的表頭是Q，表尾是_C。A. a B 丨 C:aD a89. 廣義表a的表頭是，表尾是_B_A. a B 丨 C :a Da90. 順序查找法適合于存儲結構為 _B的線性表。A散列存儲 B順序存儲或鏈式存儲 C 壓縮存儲 D索引存儲91 對線性表進展折半查找時，要求線性表必須 _BA以順序萬式存儲 列B以順序萬式存儲，且結點按天鍵字有序排C以鏈式方式存儲D以鏈式方式存儲，且結點按關鍵字有序排92. 采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為 D_。2A 0(n ) B 0(nlog 2n) C 0(n) D O(log2n)93. 有一