《數(shù)據(jù)結構》習題集

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

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

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

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

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

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