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

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

2、映象和非順序映象，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置相鄰的存儲單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)是一種最基本的存儲表示方法，通常借助于程序設(shè)計(jì)語言中的數(shù)組來實(shí)現(xiàn)。鏈?zhǔn)酱鎯Ψ椒ǎ核灰筮壿嬌舷噜彽慕Y(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存

3、儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助于程序設(shè)計(jì)語言中的指針類型來實(shí)現(xiàn)。索引存儲方法：索引存儲方法：除建立存儲結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。散列存儲方法：散列存儲方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲地址。數(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)是一種隨機(jī)存取的存儲結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種順序存取的存儲結(jié)構(gòu)。線性表若采用

4、鏈?zhǔn)酱鎯Ρ硎緯r(shí)所有結(jié)點(diǎn)之間的存儲單元地址可連續(xù)可不連續(xù)。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、所含結(jié)點(diǎn)個(gè)數(shù)都無關(guān)。3、以下哪一個(gè)術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（）。A.順序表B.鏈表C.散列表D.隊(duì)列4、算法在發(fā)生非法操作時(shí)可以做出處理的特性稱為（）。A正確性B易讀性C健壯性D高效性5、邏輯結(jié)構(gòu)是指數(shù)據(jù)元素的（）。A關(guān)聯(lián)方式B存儲方式C結(jié)構(gòu)D數(shù)據(jù)項(xiàng)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ù)的運(yùn)算2）6、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）7、基于某種邏輯結(jié)構(gòu)之上的運(yùn)算，其實(shí)現(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)）和（運(yùn)算運(yùn)算）。2、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)

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