數(shù)據(jù)結(jié)構(gòu)與算法：第一章 考研真題

第一章緒論考研真題精

一、選擇題

1.算法的計算量的大小稱為計算的(

A.效率B.復雜性C.現(xiàn)實性D.難度

2.算法的時間復雜度取決于()

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

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

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

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

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

4.一個算法應(yīng)該是()。

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

C.

5.下面關(guān)于算法說法錯誤的是()。

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

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

C.算法的可行性是指指令不能有二義性

D.以上幾個都是錯誤的

6.下面說法錯誤的是().

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

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

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

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

A.(1)B.⑴，⑵C.(1),(4)D.(3)

7.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()兩大類。

A.動態(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.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

8.以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是()。

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

9.以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（）。

A.廣義表B.二叉樹C.稀疏矩陣D.串

10.以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（）。

A.棧B.哈希表C.線索樹D.雙向鏈表

11.以下哪個數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（）。

A.棧B.廣義表C.有向圖D.字符串

12.以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。

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

13.下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。

A.棧B.隊列C.完全二叉樹D.堆

14.連續(xù)存儲設(shè)計時，存儲單元的地址（）。

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

15.以下屬于邏輯結(jié)構(gòu)的是（）.

A.順序表B.哈希表C.有序表D.單鏈表

二、判斷題

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

2.記錄是數(shù)據(jù)處理的最小單位。（）

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

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

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

6.算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算

法實際上就是程序了。（）

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

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

9.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實現(xiàn)有關(guān)。（）

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

11.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（）

12.數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準則是，實現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨立.（）

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

三、填空

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

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

(4)四種。

3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指。

4.一個數(shù)據(jù)結(jié)構(gòu)在計算機中稱為存儲結(jié)構(gòu)。

5.抽象數(shù)據(jù)類型的定義僅取決于它的一組工12,而與(2)無關(guān),即不論其內(nèi)部結(jié)構(gòu)如何變

化，只要它的(3)不變,都不影響其外部使用。

6.數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是o

7.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的(1)和(2),以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相

應(yīng)的(3).,設(shè)計出相應(yīng)的(4)。

8.一個算法具有5個特性：(1)、(2)、(3),有零個或多個輸入、有一個或多

個輸出。

9.計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為。

for(i=1；i<n-l；i++)

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

10.下面程序段的時間復雜度為。(n>l)

sum=l；

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

11.設(shè)m.n均為自然數(shù)，m可表示為一些不超過n的自然數(shù)之和，f(m,n)為這種表示方式的

數(shù)目。例f(5,3)=5,有5種表示方式：3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1。

①以下是該函數(shù)的程序段，請將未完成的部分填入，使之完整

intf(intm,intn)

{if(m==l)

return(1);

if(n==l){

return(2)

if(m<n)

{returnf(m,m);}

if(m==n)

{return1+(3);)

returnf(m.n-1)+f(m-n,(4));

)

②執(zhí)行程序，f(6,4)=o

12.在有n個選手參加的單循環(huán)賽中，總共將進行場比賽。

四、應(yīng)用題

1.數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學科？

2.數(shù)據(jù)元素之間的關(guān)系在計算機中有幾種表示方法？各有什么特點？

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

要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？

4.回答問題

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

怎樣的關(guān)系？

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

說明之。

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

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

(4)評價各種不同數(shù)據(jù)結(jié)構(gòu)的標準是什么？

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

6.解釋和比較以下各組概念

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

(3)抽象數(shù)據(jù)類型(4)算法的時間復雜性(5)算法(6)頻度

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

8.對于一個數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個方面的討論？

9.當你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時，應(yīng)從哪些方面考慮？

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

11.數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？

12.數(shù)據(jù)的存儲結(jié)構(gòu)由哪四種基本的存儲方法實現(xiàn)？

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

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

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

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

構(gòu)。

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

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

同。

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

復雜度為T2=O(n2),僅就時間復雜度而言，請具體分析這兩個算法哪一個好。