考點2 數據結構的基本概念

真考鏈接

在選擇題中，考核概率為45%。該知識點屬于熟記內容，應熟記數據結構的定義、分類，能區分線性結構與非線性結構。

1.數據結構的定義

數據結構是指相互有關聯的數據元素的集合，即數據的組織形式。

（1）數據的邏輯結構

所謂數據的邏輯結構，是指反映數據元素之間邏輯關系（即前后件關系）的數據結構。它包括兩個要素，即數據元素的集合和數據元素之間的關系。

（2）數據的存儲結構

數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱為數據的物理結構）。數據結構的存儲方式有：順序存儲方法、鏈式存儲方法、索引存儲方法和散列存儲方法。而采用不同的存儲結構，其數據處理的效率是不同的。因此在進行數據處理時，選擇合適的存儲結構是很重要的。

數據結構研究的內容主要包括3個方面：

●數據集合中各數據元素之間的邏輯關系，即數據的邏輯結構；

●在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構；

●對各種數據結構進行的運算。

2.數據結構的圖形表示

數據元素之間最基本的關系是前后件關系。所謂前后件關系即每一個二元組，都可以用圖形來表示。用中間標有元素值的方框表示數據元素，一般稱之為數據節點，簡稱為節點。對于每一個二元組，通常用一條有向線段從前件指向后件。

用圖形表示數據結構具有直觀、易懂的特點，在不引起歧義的情況下，前件節點到后件節點連線上的箭頭可以省去。例如在樹形結構中，通常都是用無向線段來表示前后件關系的。

3.線性結構與非線性結構

根據數據結構中各數據元素之間前后關系的復雜程度，一般可將數據結構分為兩大類型：線性結構和非線性結構。

如果一個非空的數據結構滿足有且只有一個根節點，并且每個節點最多有一個直接前驅和直接后繼，則稱該數據結構為線性結構，又稱線性表。不滿足上述條件的數據結構則稱為非線性結構。

小提示

需要注意的是：在一個線性結構中插入或刪除任何一個節點后還應該是線性結構，否則不能稱之為線性結構。

真題精選

下列敘述中正確的是（ ）。

A）程序執行的效率與數據的存儲結構密切相關

B）程序執行的效率只取決于程序的控制結構

C）程序執行的效率只取決于所處理的數據量

D）以上3種說法都不對

【答案】A

【解析】在計算機中，數據的存儲結構對數據的執行效率有較大的影響，例如在有序存儲的表中查找某個數值就比在無序存儲的表中查找的效率高很多。