數(shù)據(jù)結(jié)構(gòu)練習(xí)：緒論

第1章緒論

一、選擇題

2.算法的時間復(fù)雜度取決于（）【中科院計(jì)算所1998二、1（2分）】

A.問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B

3.計(jì)算機(jī)算法指的是（1）,它必須具備（2）這三個特性。

（1）A.計(jì)算方法B.排序方法C.解決問題的步驟序列D.調(diào)度方

（2）A.可執(zhí)行性、可移植性、可擴(kuò)充性B.可執(zhí)行性、確定性、有窮性

C.確定性、有窮性、穩(wěn)定性易讀性、穩(wěn)定性、安全性

【南京理工大學(xué)1999一、1（2分）【武漢交通科技大學(xué)1996一、1（4分）】

4.一個算法應(yīng)該是（）?！局猩酱髮W(xué)1998二、1（2分）】

A.程序B.問題求解步驟的描述C.要滿足五個基本特性D.A和

5.下面關(guān)于算法說法錯誤的是（）【南京理工大學(xué)2000一、1（1.5分）】

A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)

B.為解決某問題的算法同為該問題編寫的程序含義是相同的

C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的

6.下面說法錯誤的是（）【南京理工大學(xué)2000一、2（1.5分）】

（1）算法原地工作的含義是指不需要任何額外的輔助空間

（2）在相同的規(guī)模n下，復(fù)雜度0（n）的算法在時間上總是優(yōu)于復(fù)雜度0（2"）的算法

（3）所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界

（4）同一個算法，實(shí)現(xiàn)語言的級別越高，執(zhí)行效率就越低

A.（1）B.（1）,（2）C.（1）,（4）D.（3）

7.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。【武漢交通科技大學(xué)1996一、4（2分）】

A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

8.以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（）?！颈狈浇煌ù髮W(xué)2000二、1（2分）】

A.循環(huán)隊(duì)列B.鏈表C.哈希表D.棧

11.在下面的程序段中，對x的賦值語句的頻度為（）【北京工商大學(xué)2001一、10（3

分）】

FORi:=lTOnDO

FORj:=lTOnDO

x:=x+l;

2n

A.0（2n）B.0（n）C.0（n）D.0（log2）

12.程序段FORi:=n-lD0WT01DO

FORj:=lTOiDO

IFA[j]>A[j+l]

THENA[j]與A[j+1]對換;

其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）

A.0（n）B.O（nlogn）C.0（n3）D.0（n2）【南京理工大學(xué)1998—、

1（2分）】

14.以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)【中山大學(xué)1999一、4]

A.樹B.字符串C.隊(duì)D.棧

16.順序存儲設(shè)計(jì)時，存儲單元的地址（【中山大學(xué)1999一、1（1分）】

A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)

二、判斷題

1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）

3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系；（）

4.算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。（）

5.健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（）

7.程序一定是算法。（）

8.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲形式。（）

10.在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。（）

13.數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計(jì)算機(jī)的儲存結(jié)構(gòu).（）

三、填空

1.數(shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示。

2.對于給定的n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有（1）,⑵，（3）,_

（4）四種。

3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指?！颈本┼]電大學(xué)2001二、1（2分）】

4.一個數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中稱為存儲結(jié)構(gòu)?！救A中理工大學(xué)2000一、1（1分）】

6.數(shù)據(jù)結(jié)構(gòu)中評價(jià)算法的兩個重要指標(biāo)是【北京理工大學(xué)2001七、1（2分）】

8.一個算法具有5個特性：（1）、⑵、（3）,有零個或多個輸入、有一個或多

個輸出。

9.已知如下程序段

FORi:=nDOWNTO1DO{語句}1

BEGIN

x:=x+l；{語句2}

FORj:=nDOWNTOiDO{語句3}

y：=y+l;{語句}4

END；

語句1執(zhí)行的頻度為（1）；語句2執(zhí)行的頻度為（2）；語句3執(zhí)行的頻度為（3）；

語句4執(zhí)行的頻度為（4）?！颈狈浇煌ù髮W(xué)1999二、4（5分）】

10.在下面的程序段中，對x的賦值語句的頻度為（表示為n的函數(shù)）

FORi：=1TOnDO

FORj：=1TOiDO

FORk：=1TOjDO

x：=x+delta；

【北京工業(yè)大學(xué)1999一、6（2分）】

11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：【合肥工業(yè)大學(xué)1999三、1（2分）】

i：=1；WHILEi<nDOi：=i*2;

14.計(jì)算機(jī)執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為。【南京理工大學(xué)2000二、1

（1.5分）】

FOR（i=l；i<n-l；i++）

FOR（j=n;j>=i;j—）

s;

15.下面程序段的時間復(fù)雜度為。（n>l）

sum=l；

for（i=0;sum<n;i++）sum+=l;

四、應(yīng)用題

1.數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科？【燕山大學(xué)1999二、1（4分）】

2.數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？【燕山大學(xué)1999二、

2（4分）】

3.數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主

要特點(diǎn)是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？【北京郵電大學(xué)1994-（8分）】

4.回答問題（每題2分）【山東工業(yè)大學(xué)1997-（8分）】

（1）在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算之間存在著

怎樣的關(guān)系？

（2）若邏輯結(jié)構(gòu)相同但存儲結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對嗎？舉例

說明之。

（3）在給定的邏輯結(jié)構(gòu)及其存儲表示上可以定義不同的運(yùn)算集合，從而得到不同的數(shù)

據(jù)結(jié)構(gòu)。這樣說法對嗎？舉例說明之。

（4）評價(jià)各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？

5.評價(jià)一個好的算法，您是從哪幾方面來考慮的？

【大連海事大學(xué)1996二、3（2分）】【中山大學(xué)1998三、1（5分）】

6.解釋和比較以下各組概念【華南師范大學(xué)2000一（10分）】

（1）抽象數(shù)據(jù)類型及數(shù)據(jù)類型（2）數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)

（3）抽象數(shù)據(jù)類型【哈爾濱工業(yè)大學(xué)2000一、1（3分）】

（4）算法的時間復(fù)雜性【河海大學(xué)1998一、2（3分）】

（5）算法【吉林工業(yè)大學(xué)1999一、1（2分）】

（6）頻度【吉林工業(yè)大學(xué)1999一、2（2分）】

7.根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類基本的數(shù)據(jù)結(jié)構(gòu)？

【北京科技大學(xué)1998一、1】【同濟(jì)大學(xué)1998】

8.對于一個數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個方面的討論？【北京科技大學(xué)1999一、1（2分）】

9.當(dāng)你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時，應(yīng)從哪些方面考慮？【西安電子北京科技大學(xué)

2000]

10.若將數(shù)據(jù)結(jié)構(gòu)定義為一個二元組（D,R），說明符號D,R應(yīng)分別表示什么？

【北京科技大學(xué)2001一、1（2分）】

11.數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？【哈爾濱工業(yè)大學(xué)2001三、1（3分）】

12.數(shù)據(jù)的存儲結(jié)構(gòu)由哪四種基本的存儲方法實(shí)現(xiàn)？【山東科技大學(xué)2001一、1（4分）】

13.若有100個學(xué)生，每個學(xué)生有學(xué)號，姓名，平均成績，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便，

寫出這些結(jié)構(gòu)？

【山東師范大學(xué)1996二、2（2分）】

14.運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲方式

完全相同，只是對于運(yùn)算的定義不同。因而兩個結(jié)構(gòu)具有顯著不同的特性，是兩個不同的結(jié)

構(gòu)。

【北京大學(xué)1998—、1（5分）】

15.在編制管理通訊錄的程序時.，什么樣的數(shù)據(jù)結(jié)構(gòu)合適？為什么？【長沙鐵道學(xué)院1998

四、3（6分）】

16.試舉一例，說明對相同的邏輯結(jié)構(gòu)，同一種運(yùn)算在不同的存儲方式下實(shí)現(xiàn)，其運(yùn)算效率

不同。

【北京理工大學(xué)2000三、1(4.5分)】

17.有實(shí)現(xiàn)同一功能的兩個算法A1和A2,其中A1的時間復(fù)雜度為Tl=0(2”)，A2的時間復(fù)

雜度為T2=0(南)，僅就時間復(fù)雜度而言，請具體分析這兩個算法哪一個好。【北京航空航天

大學(xué)2000二(10分)】

18.設(shè)計(jì)一數(shù)據(jù)結(jié)構(gòu)，用來表示某一銀行儲戶的基本信息：賬號、姓名、開戶年月日、儲

蓄類型、存入累加數(shù)、利息、帳面總數(shù)?！菊憬髮W(xué)1994一、3(5分)】

19.寫出下面算法中帶標(biāo)號語句的頻度。

TYPEar=ARRAY[l..n]OFdatatype;

PROCEDUREperm(a:ar;k,n:integer);

VARx:datatype;i:integer;

BEGIN

(1)IFk=n

THENBEGIN

(2)FORi:=lTOnDO

(3)write(a[i]);

writein;

END

ELSEBEGIN

(4)FORi:=kTOnDO

(5)a[i]:=a[i]+i*i;

(6)perm(a,k+1,n);

END;

END;

設(shè)k的初值等于U

【北京郵電大學(xué)1997二(10分)】

20.分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。

i:=0;s:=0;n:=100;

REPEAT

i:=i+l;

s:=s+10*i;

UNTILN0T((i<n)AND(s<n));

【北京郵電大學(xué)1998四、1(5分)】

21.下列算法對一n位二進(jìn)制數(shù)加1,假如無溢出，該算法的最壞時間復(fù)雜性是什么？并分

析它的平均時間復(fù)雜性。

TYPEnum=ARRAY[1..n]of[0..1]；

PROCEDUREInc(VARa：num)；

VARi：integer；

BEGINi：=n；

WHILEA[i]=lDO

BEGINA[i]：=0；i：=i-l；END；

END；

A[i]：=1；

ENDInc；

【東南大學(xué)1998三(8分)1994二(15分)】

22.閱讀下列算法，指出算法A的功能和時間復(fù)雜性

PROCEDUREA(h,g:pointer);

(h,g分別為單循環(huán)鏈表(singlelinkedcircularlist)中兩個結(jié)點(diǎn)指針)

PROCEDUREB(s,q:pointer)；

VARp:pointer;

BEGIN

P：=s;

WHILEp\nextOqDOp:=p\next;

p二next:=s;

END;(ofB)

BEGIN

B(h,g);B(g,h);

END;(ofA)

【東南大學(xué)1999二(10分)】

23.調(diào)用下列C函數(shù)f(n)或PASACAL函數(shù)f(n)回答下列問題：

(1)試指出f(n)值的大小，并寫出f(n)值的推導(dǎo)過程；

(2)假定"5,試指出f(5)值的大小和執(zhí)行f(5)時的輸出結(jié)果。

C函數(shù)：intf(intn)

{inti,j,k,sum=0;

for(i=l;i<n+l;i++)

{for(j=n;j>i-l;j-)

for(k=l;k<j+l;k++)

sum++;

printf(〃sum=%d\n〃，sum)；

}

return(sum);

}【華中理工大學(xué)2000六(10分)】

24.設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時間復(fù)雜度。

m:=0;

FORi:=lTOnDO

FORj:=2*iTOnDO