數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題匯總

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題匯總

1：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的（1）以及它們之間的（2）和元算等的科學(xué)。AB

（1）A,數(shù)據(jù)元素B計(jì)算方法C規(guī)律存儲(chǔ)D數(shù)據(jù)映像（2）A結(jié)構(gòu)B關(guān)系C運(yùn)算D算法

2：在數(shù)據(jù)結(jié)構(gòu)中，從規(guī)律上可以把數(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)

3數(shù)據(jù)的規(guī)律結(jié)構(gòu)是（）關(guān)系的整體。AA數(shù)據(jù)元素之間的規(guī)律B數(shù)據(jù)項(xiàng)之間的規(guī)律C數(shù)據(jù)類型之間

D存儲(chǔ)結(jié)構(gòu)之間

4,在計(jì)算機(jī)的存儲(chǔ)器中表示時(shí)，物理地址和規(guī)律地址一致并且是連續(xù)的，稱之為：（）。A規(guī)律結(jié)構(gòu)

B順序存儲(chǔ)結(jié)構(gòu)C鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

D以上都對(duì)

5一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（）B

A數(shù)據(jù)項(xiàng)B數(shù)據(jù)元素C數(shù)據(jù)結(jié)構(gòu)

D數(shù)據(jù)類型6數(shù)據(jù)運(yùn)算（

）。A

A，效率與采用何種存儲(chǔ)結(jié)構(gòu)有關(guān)。B是根據(jù)存儲(chǔ)結(jié)構(gòu)來(lái)定義的C有算術(shù)運(yùn)算和關(guān)系元算兩大類D必需用程序設(shè)計(jì)語(yǔ)言來(lái)描述

7數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指：（

）A數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)

B數(shù)據(jù)結(jié)構(gòu)C數(shù)據(jù)的規(guī)律結(jié)構(gòu)

D數(shù)據(jù)元素之間的關(guān)系

答：A

8在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是：（

）

A規(guī)律結(jié)構(gòu)

B存儲(chǔ)結(jié)構(gòu)C規(guī)律結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

D物理結(jié)構(gòu)

答A

9數(shù)據(jù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求（）

A每個(gè)結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域B所有結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域C結(jié)點(diǎn)的最終一個(gè)數(shù)據(jù)域是指針類型

D每個(gè)結(jié)點(diǎn)有多少個(gè)后繼，就設(shè)多少個(gè)指針域答：A

10：以下說(shuō)法中，不正確的是（

）A數(shù)據(jù)元素是數(shù)據(jù)的基本單位

B數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小克標(biāo)識(shí)單位C數(shù)據(jù)可由若干個(gè)數(shù)據(jù)元素構(gòu)成D數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成答：D11：（

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

B程度有限C在規(guī)定的時(shí)間內(nèi)完成

D確定性

答：B

12：計(jì)算機(jī)中算法指的是解決某一種問(wèn)題的有限運(yùn)算序列，它必需具備輸入，輸出（

）

1

B

A可行性，可移植性和可擴(kuò)展性C確定性，有窮性和穩(wěn)定性答：B

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

）

B至少一個(gè)輸入D頑強(qiáng)性

）

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

D易讀性，穩(wěn)定性和確定性

14：下面關(guān)于算法的說(shuō)法正確的是（A算法最終必需由計(jì)算機(jī)程序?qū)崿F(xiàn)

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

15：算法的時(shí)間繁雜度與（A問(wèn)題規(guī)模答：A

16:算法的主要任務(wù)是分析（A算法是否具有較好的可讀性B算法中是否存在語(yǔ)言錯(cuò)誤C算法的功能是否符合設(shè)計(jì)要求D算法的執(zhí)行時(shí)間和問(wèn)題規(guī)模之間的關(guān)系答：D

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

18：算法分析的目的是（

）

A找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中輸入和輸出的關(guān)系

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

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

19.下述函數(shù)中漸進(jìn)時(shí)間繁雜度最小是＿＿。

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)時(shí)間繁雜度的數(shù)量級(jí)一致，但當(dāng)n足夠大時(shí)，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結(jié)點(diǎn)的next指向*p之后的結(jié)點(diǎn)（s->next=p->next），然后將*p結(jié)點(diǎn)的next指向*s（p->next=s）。所以答案為B。

8.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)使得依舊有序，其算法的時(shí)間繁雜度為_(kāi)_____。A.O(Ibn)B.O(1)C.O(n2)D.O(n）

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

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

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

10.在一個(gè)單鏈表中，刪除*p結(jié)點(diǎn)之后的一個(gè)結(jié)點(diǎn)的操作是____。D

A．p->next=p;B.p->next->next=p->next;C.p->next->next=p;Dp->next=p->next->next;11.在一個(gè)雙鏈表中，在*p結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)*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.在一個(gè)雙鏈表中，刪除*p結(jié)點(diǎn)之后的一個(gè)結(jié)點(diǎn)的操作是_____。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在不帶頭結(jié)點(diǎn)（頭結(jié)點(diǎn)為*head）的單循環(huán)鏈表中，至少有一個(gè)結(jié)點(diǎn)的條件是＿①＿，尾結(jié)點(diǎn)為*p的條件是＿②＿。AD

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

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

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

3．在一個(gè)單鏈表head中，已知p指向其中的一個(gè)結(jié)點(diǎn)，若要?jiǎng)h除其后的一個(gè)