數據結構與算法概論復習習題[1]

　　第章  緒論

　　 簡述下列術語數據數據元素數據對象數據結構存儲結構數據類型和抽象數據類型

　　解數據是對客觀事物的符號表示在計算機科學中是指所有能輸入到計算機中並被計算機程序處理的符號的總稱

　　數據元素是數據的基本單位在計算機程序中通常作為一個整體進行考慮和處理

　　數據對象是性質相同的數據元素的集合是數據的一個子集

　　數據結構是相互之間存在一種或多種特定關系的數據元素的集合

　　存儲結構是數據結構在計算機中的表示

　　數據類型是一個值的集合和定義在這個值集上的一組操作的總稱

　　抽象數據類型是指一個數學模型以及定義在該模型上的一組操作是對一般數據類型的擴展

　　 試描述數據結構和抽象數據類型的概念與程序設計語言中數據類型概念的區別

　　解抽象數據類型包含一般數據類型的概念但含義比一般數據類型更廣更抽象一般數據類型由具體語言系統內部定義直接提供給編程者定義用戶數據因此稱它們為預定義數據類型抽象數據類型通常由編程者定義包括定義它所使用的數據和在這些數據上所進行的操作在定義抽象數據類型中的數據部分和操作部分時要求只定義到數據的邏輯結構和操作說明不考慮數據的存儲結構和操作的具體實現這樣抽象層次更高更能為其他用戶提供良好的使用接口

　　 設有數據結構(DR)其中

　　D={dddd}R={r}r={(dd)（dd）(dd)}

　　試按圖論中圖的畫法慣例畫出其邏輯結構圖

　　解

　　 試仿照三元組的抽象數據類型分別寫出抽象數據類型復數和有理數的定義（有理數是其分子分母均為自然數且分母不為零的分數）

　　解

　　ADT Complex{

　　數據對象D={ri|ri為實數}

　　數據關系R={<ri>}

　　基本操作

　　InitComplex(&Creim)

　　操作結果構造一個復數C其實部和虛部分別為re和im

　　DestroyCmoplex(&C)

　　操作結果銷毀復數C

　　Get(Ck&e)

　　操作結果用e返回復數C的第k元的值

　　Put(&Cke)

　　操作結果改變復數C的第k元的值為e

　　IsAscending(C)

　　操作結果如果復數C的兩個元素按升序排列則返回否則返回

　　IsDescending(C)

　　操作結果如果復數C的兩個元素按降序排列則返回否則返回

　　Max(C&e)

　　操作結果用e返回復數C的兩個元素中值較大的一個

　　Min(C&e)

　　操作結果用e返回復數C的兩個元素中值較小的一個

　　}ADT Complex

　　ADT RationalNumber{

　　數據對象D={sm|sm為自然數且m不為}

　　數據關系R={<sm>}

　　基本操作

　　InitRationalNumber(&Rsm)

　　操作結果構造一個有理數R其分子和分母分別為s和m

　　DestroyRationalNumber(&R)

　　操作結果銷毀有理數R

　　Get(Rk&e)

　　操作結果用e返回有理數R的第k元的值

　　Put(&Rke)

　　操作結果改變有理數R的第k元的值為e

　　IsAscending(R)

　　操作結果若有理數R的兩個元素按升序排列則返回否則返回

　　IsDescending(R)

　　操作結果若有理數R的兩個元素按降序排列則返回否則返回

　　Max(R&e)

　　操作結果用e返回有理數R的兩個元素中值較大的一個

　　Min(R&e)

　　操作結果用e返回有理數R的兩個元素中值較小的一個

　　}ADT RationalNumber

　　 試畫出與下列程序段等價的框圖

　　() product=; i=;

　　while(i<=n){

　　product *= i;

　　i++;

　　}

　　() i=;

　　do {

　　i++;

　　} while((i!=n) && (a[i]!=x));

　　() switch {

　　case x<y: z=yx; break;

　　case x=y: z=abs(x*y); break;

　　default: z=(xy)/abs(x)*abs(y);

　　}

[]  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23630.html