嚴(yán)蔚敏版_數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案

1、 第 1 章 緒論 緒論 1.1 簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。 解：數(shù)據(jù) 解：數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。 數(shù)據(jù)元素 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。 數(shù)據(jù)對(duì)象 數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)

2、據(jù)元素的集合。 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。 數(shù)據(jù)類型 數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。 抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。是對(duì)一般數(shù)據(jù)類型的擴(kuò)展。 1.2 1.2 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別。 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別。 解： 解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但

3、含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。抽象數(shù)據(jù)類型通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進(jìn)行的操作。在定義抽象數(shù)據(jù)類型中的數(shù)據(jù)部分和操作部分時(shí)，要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的具體實(shí)現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。 1.3 1.3 設(shè)有數(shù)據(jù)結(jié)構(gòu) 設(shè)有數(shù)據(jù)結(jié)構(gòu)(D,R) (D

4、,R)，其中 ，其中 ? ? 4 , 3 , 2 , 1 d d d d D ? ， ? ? r R ? ， ? ? ? ? ? ? ? ? 4 , 3 , 3 , 2 , 2 , 1 d d d d d d r ?試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。 試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。 解： 解： 1.4 1.4 試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復(fù)數(shù)和有理數(shù)的定義（有理數(shù)是其分子、分母均 試仿照三元組的抽象數(shù)

5、據(jù)類型分別寫出抽象數(shù)據(jù)類型復(fù)數(shù)和有理數(shù)的定義（有理數(shù)是其分子、分母均為自然數(shù)且分母不為零的分?jǐn)?shù)） 。 為自然數(shù)且分母不為零的分?jǐn)?shù)） 。 解： 解： ADT Complex{ 數(shù)據(jù)對(duì)象：D={r,i|r,i 為實(shí)數(shù)} 數(shù)據(jù)關(guān)系：R={} 基本操作： InitComplex( k=0; (1) i=1; k=0; while(i<=n while(i<=n-1){ 1){ @ k += 10*i; @ k += 10*i;

6、i++; i++; } (2) i=1; k=0; (2) i=1; k=0; do { do { @ k += 10*i; @ k += 10*i; i++; i++; } while(i<=n } while(i<=n-1); 1); (3) i=1; k=0; (3) i=1; k=0; while (i<=n while (i<=n-1) { 1) { i++; i++; @ k += 10*i; @

7、 k += 10*i; } (4) k=0; (4) k=0; for(i=1; i<=n; i++) { for(i=1; i<=n; i++) { for(j=i; j<=n; j++) for(j=i; j<=n; j++) @ @ k++; k++; } (5) for(i=1; i<=n; i++) { (5) for(i=1; i<=n; i++) { for(j=1; j<=i