1.1數(shù)據(jù)結(jié)構(gòu)的基本概念

01、可以用「抽象數(shù)據(jù)類型」定義一個完整的數(shù)據(jù)結(jié)構(gòu)。

02、以下數(shù)據(jù)結(jié)構(gòu)中，「樹」是非線性數(shù)據(jù)結(jié)構(gòu)。

03、以下屬于邏輯結(jié)構(gòu)的是「有序表」。

04、以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是「?！?。

05、「數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立于其存儲結(jié)構(gòu)」。

06、在存儲結(jié)構(gòu)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且要存儲「數(shù)據(jù)元素之間的關(guān)系」。

07、鏈?zhǔn)酱鎯υO(shè)計時，結(jié)點(diǎn)內(nèi)的存儲單元地址「一定連續(xù)」。

08、Q：對于兩種不同的數(shù)據(jù)結(jié)構(gòu)，邏輯結(jié)構(gòu)和物理結(jié)構(gòu)一定不相同嗎？

A：對于兩種不同的數(shù)據(jù)結(jié)構(gòu)，它們的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)有可能相同。比如“二叉樹”和“二叉排序樹”，二叉排序樹可以采用二叉樹的邏輯表示和存儲方式，前者通常用于表示層次關(guān)系，而后者通常用于排序和查找。雖然它們的運(yùn)算都有建立樹、插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)和查找結(jié)點(diǎn)等功能，但對于二叉樹和二叉排序樹，這些運(yùn)算的定義是不同的，以查找結(jié)點(diǎn)為例，二叉樹的時間復(fù)雜度為，而二叉排序樹的時間復(fù)雜度為。

09、Q：試舉一例，說明對相同的邏輯結(jié)構(gòu)，同一種運(yùn)算在不同的存儲方式下實現(xiàn)時，其運(yùn)算效率不同。

A：線性表既可以用順序存儲方式實現(xiàn)，又可以用鏈?zhǔn)酱鎯Ψ绞綄崿F(xiàn)。在順序存儲方式下，在線性表中插入和刪除元素，平均要移動近一半的元素，時間復(fù)雜度為；而在鏈?zhǔn)酱鎯Ψ绞较?，插入和刪除的時間復(fù)雜度都是。