習題1

1.1 選擇題

（1）計算機識別、存儲和加工處理的對象統稱為_________。

A.數據 B.數據元素

C.數據結構 D.數據類型

（2）數據結構通常研究數據的_________及它們之間的聯系。

A.存儲和邏輯結構 B.存儲和抽象

C.理想和抽象 D.理想與邏輯

（3）不是數據的邏輯結構的是__________。

A.散列結構 B.線性結構

C.樹結構 D.圖結構

（4）數據結構被形式地定義為<D,R>，其中D是_________的有限集，R是_________的有限集。

A.算法 B.數據元素

C.數據操作 D.邏輯結構

（5）組成數據的基本單位是__________。

A.數據項 B.數據類型

C.數據元素 D.數據變量

（6）設數據結構A=(D, R)，其中D={1, 2, 3, 4}，R={r}, r={<1, 2>, <2, 3>, <3, 4>, <4, 1>}，則數據結構A是__________。

A.線性結構 B.樹形結構

C.圖狀結構 D.集合

（7）數據在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續的，稱為_____。

A.存儲結構 B.邏輯結構

C.順序存儲結構 D.鏈式存儲結構

（8）在數據結構的討論中，把數據結構從邏輯上分為_______。

A.內部結構與外部結構 B.靜態結構與動態結構

C.線性結構與非線性結構 D.緊湊結構與非緊湊結構

（9）對一個算法的評價，不包括_________方面的內容。

A.健壯性和可讀性 B.并行性

C.正確性 D.時空復雜度

（10）算法分析的兩個方面是______。

A.空間復雜性和時間復雜性 B.正確性和簡明性

C.可讀性和文檔性 D.數據復雜性和程序復雜性

1.2 填空題

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

（2）數據結構包括數據的_________結構和_________結構。

（3）數據結構從邏輯上劃分為三種基本類型：___________、__________和___________。

（4）數據的物理結構被分為_________、________、__________和___________四種。

（5）一種抽象數據類型包括_________和_________兩部分。

（6）數據的邏輯結構是指_________，數據的存儲結構是指_________。

（7）數據結構是指數據及其相互之間的____________。當結點之間存在M對N（M∶N）的聯系時，稱這種結構為________________。當結點之間存在1對N（1∶N）的聯系時，稱這種結構為_______________。

（8）對算法從時間和空間兩方面進行度量，分別稱為_________分析。

（9）算法的效率可分為_______________效率和_______________效率。

（10）for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的時間復雜度為_________。

1.3 簡述下列術語：數據、數據項、數據元素、數據邏輯結構、數據存儲結構、數據類型和算法。

（1）for(i＝1；i<＝n；i++)

　　　　　for(j＝1；j<＝n；j++)

　　　　　　　　s++；

（2）for(i＝1；i<＝n；i++)

　　　　　for(j＝i；j<＝n；j++)

　　　　　　　s++；

（3）for(i＝1；i<＝n；i++)

　　　　　for(j＝1；j<＝i；j++)

　　　　　　　s++；

（4）i＝1；k＝0；

　　　　　　while(i<＝n-1){

　　　　　　　k+＝10*i；

　　　　　　　　i++；

　　　　　　　　　}

（5）for (i＝1；i<＝n；i++)

　　　　　for (j＝1；j<＝i ；j++)

　　　　　　　　for (k＝1；k<＝j；k++)

　　　　　　　　　　　x=x+1；

1.5 試寫一算法，自大至小依次輸出順序讀入的三個整數X、Y和Z的值。

1.6 編寫算法，求一元多項式Pn(x)=a0+a1x+a2x2+a3x3+…+anxn的值Pn(x0)，要求算法的時間復雜度盡可能地小。