《算法與數(shù)據(jù)結(jié)構(gòu)》練習(xí)一(答案)

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

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

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

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

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

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

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

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

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

9、法的時(shí)間復(fù)雜度： for（i=0；i＜m；i十十） for（j=0；j＜n；j＋＋） A[i][j]=i*j； O(mn)。 2、寫出下面算法的時(shí)間復(fù)雜度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ O() 3、寫出以下算法的時(shí)間復(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ù)中各條語(yǔ)句的頻度和算法的時(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()