本文格式為Word版，下載可任意編輯——數據結構復習題匯總

1：數據結構是一門研究非數值計算的程序設計問題中計算機的（1）以及它們之間的（2）和元算等的科學。AB

（1）A,數據元素B計算方法C規律存儲D數據映像（2）A結構B關系C運算D算法

2：在數據結構中，從規律上可以把數據結構分為（）兩類。C

A動態結構和靜態結構

B緊湊結構和非緊湊結構

C線形結構和非線性結構

D內部結構和外部結構

3數據的規律結構是（）關系的整體。AA數據元素之間的規律B數據項之間的規律C數據類型之間

D存儲結構之間

4,在計算機的存儲器中表示時，物理地址和規律地址一致并且是連續的，稱之為：（）。A規律結構

B順序存儲結構C鏈式存儲結構

D以上都對

5一個存儲結點存儲一個（）B

A數據項B數據元素C數據結構

D數據類型6數據運算（

）。A

A，效率與采用何種存儲結構有關。B是根據存儲結構來定義的C有算術運算和關系元算兩大類D必需用程序設計語言來描述

7數據結構在計算機內存中的表示是指：（

）A數據結構的存儲結構

B數據結構C數據的規律結構

D數據元素之間的關系

答：A

8在數據結構中，與所使用的計算機無關的是：（

）

A規律結構

B存儲結構C規律結構和存儲結構

D物理結構

答A

9數據采用鏈式存儲結構時，要求（）

A每個結點占用一片連續的存儲區域B所有結點占用一片連續的存儲區域C結點的最終一個數據域是指針類型

D每個結點有多少個后繼，就設多少個指針域答：A

10：以下說法中，不正確的是（

）A數據元素是數據的基本單位

B數據項是數據中不可分割的最小克標識單位C數據可由若干個數據元素構成D數據項可由若干個數據元素構成答：D11：（

）不是算法的基本特性。A可行性

B程度有限C在規定的時間內完成

D確定性

答：B

12：計算機中算法指的是解決某一種問題的有限運算序列，它必需具備輸入，輸出（

）

1

B

A可行性，可移植性和可擴展性C確定性，有窮性和穩定性答：B

13：一個算法具有（A可行性C確定性

）

B至少一個輸入D頑強性

）

B可行性，有窮性和確定性

D易讀性，穩定性和確定性

14：下面關于算法的說法正確的是（A算法最終必需由計算機程序實現

B為解決某問題的算法同為該問題編寫的程序含義是一致的。C算法的可行性是指指令不能有二義性D以上幾個都是錯誤的。答：B

15：算法的時間繁雜度與（A問題規模答：A

16:算法的主要任務是分析（A算法是否具有較好的可讀性B算法中是否存在語言錯誤C算法的功能是否符合設計要求D算法的執行時間和問題規模之間的關系答：D

17：某算法的時間繁雜度O(n^2)，說明該算法的（A我那天規模是n^2答：C

18：算法分析的目的是（

）

A找出數據結構的合理性B研究算法中輸入和輸出的關系

C.分析算法的效率以求改進D.分析算法的易讀性和文檔性

答：算法分析即算法效率分析，包括時間繁雜度和空間繁雜度分析，其目的是為了改進算法效率。此題答案為C。

19.下述函數中漸進時間繁雜度最小是＿＿。

A.T1(n)=nlbn+5000nB.T2(n)=n-8000nC.T3(n)=n-6000nD.T4(n)=2nlbn-7000lbn

答：T1(n)＝O(nlbn),T2(n)=O(n),T3(n)=O(n),T4(n)=O(nlbn)。其中T1(n)和T4(n)時間繁雜度的數量級一致，但當n足夠大時，lbn>5000n/n-7000,即T1(n)2000lbn,即T1(n)next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next=p;

答：先要將*s結點的next指向*p之后的結點（s->next=p->next），然后將*p結點的next指向*s（p->next=s）。所以答案為B。

8.在一個具有n個結點的有序單鏈表中插入一個新結點使得依舊有序，其算法的時間繁雜度為______。A.O(Ibn)B.O(1)C.O(n2)D.O(n）

答：先要查找到插入結點的前一個結點的指針，其時間繁雜度為O(n)。此題答案為D。

9.對于用一維數組d[1?.n]順序存儲的線性表，其算法的時間繁雜度為O(1)的操作是___、______。A.將n個結點從小到大排序B.從線性表中刪除第i個結點（1≤i≤n）C.查找第i個結點（1≤i≤n）D.求第i個結點（2≤i≤n）的前趨結點

答：A操作一般需要兩層循環，時間繁雜度為O(n2)或O(nIbn)；B操作需要移動結點，時間繁雜度為O(n)；C操作可以直接由d[i]得到，時間繁雜度為O(1);D操作也可以直接由d[i-1]得到，時間繁雜度為O(1)。此題答案為C、D。

10.在一個單鏈表中，刪除*p結點之后的一個結點的操作是____。D

A．p->next=p;B.p->next->next=p->next;C.p->next->next=p;Dp->next=p->next->next;11.在一個雙鏈表中，在*p結點之后插入一個結點*s的操作是_____。BA．s->prior=p;p->next=s;p->next->prior=s;s->next=p->next;B.s->next=p->next;p->next->prior=s;p->next=s;s->prior=p;C.p->next=s;s->prior=p;s->next=p->next;p->next->prior=s;D.p->next->prior=s;s->next=p->next;s->prior=p;p->next=s;12.在一個雙鏈表中，刪除*p結點之后的一個結點的操作是_____。CA．p->next=p->next->next;p->next->next->prior=p;B．p->next->prior=p;p->next=p->next->next;C．p->next=p->next->next;p->next->prior=p;D．p->next->next=p->next;p->next->prior=p;

13在不帶頭結點（頭結點為*head）的單循環鏈表中，至少有一個結點的條件是＿①＿，尾結點為*p的條件是＿②＿。AD

A.head!=NULLB.head->next!=headC.p==NULLD.p->next==head

14在帶頭結點*head的單循環鏈表中，至少有一個結點的條件是＿①＿，尾結點*p的條件是＿②＿。BDAhead->next!=NULLBhead->next!=headCp==NULLDp->next==head2.4.2填空題

1．在線性表的順序存儲中，元素之間的規律關系是通過__物理存儲位置___決定的；在線性表的鏈接存儲中，元素之間的規律關系是通過___鏈域的指針值___決定的。2．帶頭結點的單鏈表head為空的判定條件___head->next==NULL__.

3．在一個單鏈表head中，已知p指向其中的一個結點，若要刪除其后的一個