《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集

1、1緒論緒論一、選擇題：1、下列算法的時間復(fù)雜度是（）f(i=0ini)c[i]=i；AO（1）BO（n）CO（log2n）DO（nlog2n）2、數(shù)據(jù)在計算機存儲器內(nèi)表示時，根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址，這種方法稱為（）A索引存儲方法B順序存儲方法C鏈式存儲方法D散列存儲方法解析：解析：數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（映像）稱為數(shù)據(jù)的物理（存儲）結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序

2、映象和非順序映象，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲方法：它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)是一種最基本的存儲表示方法，通常借助于程序設(shè)計語言中的數(shù)組來實現(xiàn)。鏈式存儲方法：它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存

3、儲表示稱為鏈式存儲結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)通常借助于程序設(shè)計語言中的指針類型來實現(xiàn)。索引存儲方法：索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標識結(jié)點的地址。散列存儲方法：散列存儲方法：就是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。數(shù)據(jù)結(jié)構(gòu)中，邏輯上（邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系）可以把數(shù)據(jù)結(jié)構(gòu)分成線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)，線性表的鏈式存儲結(jié)構(gòu)是一種順序存取的存儲結(jié)構(gòu)。線性表若采用

4、鏈式存儲表示時所有結(jié)點之間的存儲單元地址可連續(xù)可不連續(xù)。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、所含結(jié)點個數(shù)都無關(guān)。3、以下哪一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（）。A.順序表B.鏈表C.散列表D.隊列4、算法在發(fā)生非法操作時可以做出處理的特性稱為（）。A正確性B易讀性C健壯性D高效性5、邏輯結(jié)構(gòu)是指數(shù)據(jù)元素的（）。A關(guān)聯(lián)方式B存儲方式C結(jié)構(gòu)D數(shù)據(jù)項6、研究數(shù)據(jù)結(jié)構(gòu)就是研究（）。A數(shù)據(jù)的邏輯結(jié)構(gòu)B數(shù)據(jù)的存儲結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)

5、構(gòu)D數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)的運算2）6、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）7、基于某種邏輯結(jié)構(gòu)之上的運算，其實現(xiàn)是惟一的。（）參考答案（緒論）參考答案（緒論）一、選擇題一、選擇題12345678910101111BDDCADCBACD二、填空題二、填空題1、數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容，分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、（存儲結(jié)構(gòu)存儲結(jié)構(gòu)）和（運算運算）。2、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)

6、，它與數(shù)據(jù)的（）無關(guān)，是獨立于計算機的。3、(邏輯邏輯)結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。4、程序段“f(i=1i=ni)kf(j=1j=nj)x=xk”的時間復(fù)雜度為(O(n2))。5、數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）可以用（順序順序）、（鏈式鏈式）、（索引索引）及散列存儲等四種存儲方法表示。三、判斷題三、判斷題1、順序存儲方式優(yōu)點是存儲密度大，且插入和刪除運算效率高。（）2、順序存儲結(jié)構(gòu)屬于靜態(tài)存儲結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)屬于動態(tài)存儲結(jié)構(gòu)。（