《《算法與數(shù)據(jù)結(jié)構(gòu)》練習(xí)一(答案)》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》練習(xí)一(答案)（4頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、習(xí)題一 一、選擇題 1、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中的操作對象以及它們之間的（B）和運算的學(xué)科。 A．結(jié)構(gòu) B．關(guān)系 C．運算 D．算法 2、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（C）。 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)和存儲結(jié)構(gòu) 3、線性表的邏輯順序和存儲順序總是一致的，這種說法（B）。 A．正確 B．不正確 C．無法確定 D．以上答

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

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

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

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

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

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

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

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

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ù)中各條語句的頻度和算法的時間復(fù)雜度： 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()