數(shù)據(jù)結構練習：緒論

第1章緒論

一、選擇題

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

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

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

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

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

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

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

4.一個算法應該是（）?！局猩酱髮W1998二、1（2分）】

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

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

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

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

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

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

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

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

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

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

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

7.從邏輯上可以把數(shù)據(jù)結構分為（）兩大類?！疚錆h交通科技大學1996一、4（2分）】

A.動態(tài)結構、靜態(tài)結構B.順序結構、鏈式結構

C.線性結構、非線性結構D.初等結構、構造型結構

8.以下與數(shù)據(jù)的存儲結構無關的術語是（）。【北方交通大學2000二、1（2分）】

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

11.在下面的程序段中，對x的賦值語句的頻度為（）【北京工商大學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）【南京理工大學1998—、

1（2分）】

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

A.樹B.字符串C.隊D.棧

16.順序存儲設計時，存儲單元的地址（【中山大學1999一、1（1分）】

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

二、判斷題

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

3.數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系；（）

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

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

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

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

10.在順序存儲結構中，有時也存儲數(shù)據(jù)結構中元素之間的關系。（）

13.數(shù)據(jù)的邏輯結構說明數(shù)據(jù)元素之間的順序關系，它依賴于計算機的儲存結構.（）

三、填空

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

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

（4）四種。

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

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

6.數(shù)據(jù)結構中評價算法的兩個重要指標是【北京理工大學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）。【北方交通大學1999二、4（5分）】

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

FORi：=1TOnDO

FORj：=1TOiDO

FORk：=1TOjDO

x：=x+delta；

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

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

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

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

（1.5分）】

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

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

s;

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

sum=l；

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

四、應用題

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

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

2（4分）】

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

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

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

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

怎樣的關系？

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

說明之。

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

據(jù)結構。這樣說法對嗎？舉例說明之。

（4）評價各種不同數(shù)據(jù)結構的標準是什么？

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

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

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

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

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

（4）算法的時間復雜性【河海大學1998一、2（3分）】

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

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

7.根據(jù)數(shù)據(jù)元素之間的邏輯關系，一般有哪幾類基本的數(shù)據(jù)結構？

【北京科技大學1998一、1】【同濟大學1998】

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

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

2000]

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

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

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

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

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

寫出這些結構？

【山東師范大學1996二、2（2分）】

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

完全相同，只是對于運算的定義不同。因而兩個結構具有顯著不同的特性，是兩個不同的結

構。

【北京大學1998—、1（5分）】

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

四、3（6分）】

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

不同。

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

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

雜度為T2=0(南)，僅就時間復雜度而言，請具體分析這兩個算法哪一個好?！颈本┖娇蘸教?/p>

大學2000二(10分)】

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

蓄類型、存入累加數(shù)、利息、帳面總數(shù)。【浙江大學1994一、3(5分)】

19.寫出下面算法中帶標號語句的頻度。

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;

設k的初值等于U

【北京郵電大學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));

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

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

析它的平均時間復雜性。

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；

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

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

PROCEDUREA(h,g:pointer);

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

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)

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

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

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

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

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);

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

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

m:=0;

FORi:=lTOnDO

FORj:=2*iTOnDO