《《算法與數(shù)據(jù)結構》練習一(答案)》由會員分享，可在線閱讀，更多相關《《算法與數(shù)據(jù)結構》練習一(答案)（4頁珍藏版）》請在裝配圖網上搜索。

1、習題一 一、選擇題 1、數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中的操作對象以及它們之間的（B）和運算的學科。 A．結構 B．關系 C．運算 D．算法 2、在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（C）。 A．動態(tài)結構和靜態(tài)結構 B．緊湊結構和非緊湊結構 C．線性結構和非線性結構 D．邏輯結構和存儲結構 3、線性表的邏輯順序和存儲順序總是一致的，這種說法（B）。 A．正確 B．不正確 C．無法確定 D．以上答

2、案都不對 4、算法分析的目的是（C）。 A．找出算法的合理性 B．研究算法的輸人與輸出關系 C．分析算法的有效性以求改進 D．分析算法的易懂性 二、填空題 1、數(shù)據(jù) 是信息的載體，是對客觀事物的符號表示，它能夠被計算機識別、存儲、加工和處理，數(shù)據(jù) 是對能夠有效的輸人到計算機中并且能夠被計算機處理的符號的總稱。例如，數(shù)學中所用到的整數(shù)和實數(shù)，文本編輯所用到的字符串等。 2、數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有些情況下也稱為元素、結點、頂點、記錄等。 3、數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單元，是具有獨立含義的最小標識單位。例如構成一個數(shù)據(jù)

3、元素的字段、域、屬性等都可稱之為_數(shù)據(jù)項。 4、簡而言之，數(shù)據(jù)結構是數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式。 5、數(shù)據(jù)的邏輯結構是指數(shù)據(jù)之間的邏輯關系。邏輯結構是從邏輯關系上描述數(shù)據(jù)，它與具體存儲無關，是獨立于計算機的。因此邏輯結構可以看作是從具體問題抽象出來的數(shù)學模型。 6、數(shù)據(jù)的存儲結構指數(shù)據(jù)元素及其關系在計算機存儲器內的表示。存儲結構是邏輯結構在計算機里的實現(xiàn)，也稱之為映像。 7、數(shù)據(jù)的運算是指對數(shù)據(jù)施加的操作。它定義在數(shù)據(jù)的邏輯結構之上，每種邏輯結構都有一個數(shù)據(jù)的運算。常用的有：查找、排序、插人、刪除、更新等操作。 8、數(shù)據(jù)邏輯結構可以分

4、為四種基本的類型，集合結構中的元素除了僅僅只是同屬于一個集合_，不存在什么關系。 9、數(shù)據(jù)邏輯結構的四種基本類型中，線性結構_中的元素是一種一對一的關系，這種結構的特征是：若結構是非空集，則有且只有一個開始結點和一個終端結點，并且所有結點最多只能有一個直接前驅和一個直接后繼。 10、數(shù)據(jù)邏輯結構的四種基本類型中，樹形結構中的元素是一種一對多的關系。 11、圖型結構或圖狀結構是一種多對多的關系。在這種邏輯結構中，所有結點均可以有多個前驅和多個后繼。 12、有時也可將樹型結構、集合和圖型結構稱為非線性結構，這樣數(shù)據(jù)的邏輯結構就可以分為線性結構和非線性結構兩大

5、類。 13、順序存儲方式是指邏輯上相鄰的結點被存儲到物理上也相鄰的存儲單元中。這種存儲結構只存儲結點的數(shù)值，不存儲結點之間的關系，結點之間的關系是通過存儲單元的相鄰關系隱含的表示出來的。 14、鏈接存儲方式是種存儲方法，不要求邏輯上相鄰的結點在物理上也相鄰，即數(shù)據(jù)元素可以存儲在任意的位置上。 15、 16、散列存儲方式是利用結點關鍵字的值直接計算出該結點存儲單元地址，然后將結點按某種方式存人該地址的一種方法。 17、所謂算法（Algorithm）是對特定問題求解方法和步驟的一種描述，它是指令的一組有限序列，其中每個指令表示一個或多個操作。 1

6、8、算法的有窮_性是指算法必須能夠在執(zhí)行有限個步驟之后結束，并且每個步驟都必須在有窮的時間內完成。 19、算法的確定性是指算法中的每一個步驟必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。并且，在任何條件下，算法只能有惟一的一條執(zhí)行路徑，即只要輸人是相同的就只能得到相同的輸出結果。 20、算法的可行性又稱為算法的能行性，是指算法中描述的操作是可以通過已經實現(xiàn)的基本運算執(zhí)行有限_次來實現(xiàn)，即算法的具體實現(xiàn)應該能夠被計算機執(zhí)行。 21、判斷一個算法的好壞主要以下幾個標準：正確性，可讀性_、健壯性、效率。 22、算法分析是對一種算法所消耗的計算機

7、資源的估算，其中包括計算機運行時間的長短和所占據(jù)空間的大小。 23、空間復雜度（SPace ComPlexity）也是度量一個算法好壞的標準，它所描述的是算法在運行過程中所占用存儲空間的大小。 三、判斷題 1、順序存儲方式只能用于存儲線性結構。（）樹型結構也可以用順序方式進行存儲。 2、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位。 3、算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言描述，則算法實際上就是程序了。（）算法用各種計算機語言描述表現(xiàn)為一個程序，但是不等于程序，程序邏輯不一定能滿足

8、有窮性。 4、數(shù)據(jù)結構是帶有結構的數(shù)據(jù)元素的集合。（對） 5、數(shù)據(jù)的邏輯結構是指各元素之間的邏輯關系，是用戶根據(jù)需要而建立的。（對） 6、數(shù)據(jù)結構、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映像分別稱為存儲結構、結點、數(shù)據(jù)域。（對） 7、數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機中實際的存儲形式。（對） 8、具有存取任一元素的時間相等這一特點的存儲結構稱為隨機存取結構。（對） 四、綜合題 1、用大O形式表示下面算

9、法的時間復雜度： for（i=0；i＜m；i十十） for（j=0；j＜n；j＋＋） A[i][j]=i*j； O(mn)。 2、寫出下面算法的時間復雜度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ O() 3、寫出以下算法的時間復雜度：

10、 for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j

11、 log3(n)。 5、求下面函數(shù)中各條語句的頻度和算法的時間復雜度： prime（int n） ｛ int i＝2； while ((n％i）！=0＆＆i＜sqrt(n) ) i++; if（i＞sqrt(n) ) printf（”％d is a prime number.＼n”，n）； else printf（”％d is not a prime number.＼n”，n）；｝ O()