習(xí)題一一、選擇題1、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中的操作對象以及它們之間的（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動態(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以上答案都不對4、算法分析的目的是（C）。 A找出算法的合理性 B研究算法的輸人與輸出關(guān)系 C分析算法的有效性以求改進(jìn) D分析算法的易懂性二、填空題1、數(shù)據(jù) 是信息的載體，是對客觀事物的符號表示，它能夠被計算機(jī)識別、存儲、加工和處理，數(shù)據(jù) 是對能夠有效的輸人到計算機(jī)中并且能夠被計算機(jī)處理的符號的總稱。例如，數(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)識單位。例如構(gòu)成一個數(shù)據(jù)元素的字段、域、屬性等都可稱之為_數(shù)據(jù)項(xiàng)。 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)，是獨(dú)立于計算機(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ī)里的實(shí)現(xiàn)，也稱之為映像。 7、數(shù)據(jù)的運(yùn)算是指對數(shù)據(jù)施加的操作。它定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上，每種邏輯結(jié)構(gòu)都有一個數(shù)據(jù)的運(yùn)算。常用的有：查找、排序、插人、刪除、更新等操作。 8、數(shù)據(jù)邏輯結(jié)構(gòu)可以分為四種基本的類型，集合結(jié)構(gòu)中的元素除了僅僅只是同屬于一個集合_，不存在什么關(guān)系。 9、數(shù)據(jù)邏輯結(jié)構(gòu)的四種基本類型中，線性結(jié)構(gòu)_中的元素是一種一對一的關(guān)系，這種結(jié)構(gòu)的特征是：若結(jié)構(gòu)是非空集，則有且只有一個開始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)最多只能有一個直接前驅(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é)點(diǎn)均可以有多個前驅(qū)和多個后繼。 12、有時也可將樹型結(jié)構(gòu)、集合和圖型結(jié)構(gòu)稱為非線性結(jié)構(gòu)，這樣數(shù)據(jù)的邏輯結(jié)構(gòu)就可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。 13、順序存儲方式是指邏輯上相鄰的結(jié)點(diǎn)被存儲到物理上也相鄰的存儲單元中。這種存儲結(jié)構(gòu)只存儲結(jié)點(diǎn)的數(shù)值，不存儲結(jié)點(diǎn)之間的關(guān)系，結(jié)點(diǎn)之間的關(guān)系是通過存儲單元的相鄰關(guān)系隱含的表示出來的。 14、鏈接存儲方式是種存儲方法，不要求邏輯上相鄰的結(jié)點(diǎn)在物理上也相鄰，即數(shù)據(jù)元素可以存儲在任意的位置上。 15、 16、散列存儲方式是利用結(jié)點(diǎn)關(guān)鍵字的值直接計算出該結(jié)點(diǎn)存儲單元地址，然后將結(jié)點(diǎn)按某種方式存人該地址的一種方法。 17、所謂算法（Algorithm）是對特定問題求解方法和步驟的一種描述，它是指令的一組有限序列，其中每個指令表示一個或多個操作。18、算法的有窮_性是指算法必須能夠在執(zhí)行有限個步驟之后結(jié)束，并且每個步驟都必須在有窮的時間內(nèi)完成。 19、算法的確定性是指算法中的每一個步驟必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。并且，在任何條件下，算法只能有惟一的一條執(zhí)行路徑，即只要輸人是相同的就只能得到相同的輸出結(jié)果。 20、算法的可行性又稱為算法的能行性，是指算法中描述的操作是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限_次來實(shí)現(xiàn)，即算法的具體實(shí)現(xiàn)應(yīng)該能夠被計算機(jī)執(zhí)行。 21、判斷一個算法的好壞主要以下幾個標(biāo)準(zhǔn)：正確性，可讀性_、健壯性、效率。 22、算法分析是對一種算法所消耗的計算機(jī)資源的估算，其中包括計算機(jī)運(yùn)行時間的長短和所占據(jù)空間的大小。 23、空間復(fù)雜度（SPace ComPlexity）也是度量一個算法好壞的標(biāo)準(zhǔn)，它所描述的是算法在運(yùn)行過程中所占用存儲空間的大小。三、判斷題 1、順序存儲方式只能用于存儲線性結(jié)構(gòu)。（）樹型結(jié)構(gòu)也可以用順序方式進(jìn)行存儲。 2、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。 3、算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言描述，則算法實(shí)際上就是程序了。（）算法用各種計算機(jī)語言描述表現(xiàn)為一個程序，但是不等于程序，程序邏輯不一定能滿足有窮性。 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ù)項(xiàng)在計算機(jī)中的映像分別稱為存儲結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域。（對） 7、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機(jī)中實(shí)際的存儲形式。（對） 8、具有存取任一元素的時間相等這一特點(diǎn)的存儲結(jié)構(gòu)稱為隨機(jī)存取結(jié)構(gòu)。（對）四、綜合題 1、用大O形式表示下面算法的時間復(fù)雜度： for（i=0；im；i十十） for（j=0；jn；j） Aij=i*j； O(mn)。 2、寫出下面算法的時間復(fù)雜度： i0； s=0； while(sn） i+; s+=i; O() 3、寫出以下算法的時間復(fù)雜度： for（i0; im; i）for（j0 ; jt; j） cij=0；for（i=0；im；i） for（j=o; j<t; j+） for（k=0；kn；k） cijaik*bkj; O(mnt)。4、寫出下面算法的時間復(fù)雜度：i=1;while（in） i=i*3; log3(n)。5、求下面函數(shù)中各條語句的頻度和算法的時間復(fù)雜度：prime（int n） int i2； while (ni）！=0isqrt(n) ) i+; if（isqrt(n) ) printf（”d is a prime number.n”，n）； else printf（”d is not a prime number.n”，n）； O()