1.1數據結構與算法
考點1算法
1.算法的基本概念
算法是指對解題方案準確而完整的描述。
(1)算法的基本特征
考核概率為45%。該知識點屬于熟記內容,考生要熟記算法的概念,以及時間復雜度和空間復雜度的概念。可行性:針對實際問題而設計的算法,執(zhí)行后能夠得到滿意的結果,即必須有一個或多個輸出。注意：即使某一算法在數學理論上是正確的,但如果在實際的計算工具上不能執(zhí)行,則該算法也是不具有可行性的。
確定性:指算法中每一步驟都必須是有明確定義的。
有窮性:指算法必須能在有限的時間內做完。
擁有足夠的情報:一個算法是否有效,還取決于為算法所提供的情報是否足夠。
(2)算法的基本要素
算法一般由兩種基本要素構成:
對數據對象的運算和操作;
算法的控制結構,即運算和操作時間的順序。
算法中對數據的運算和操作:算法就是按解題要求從指令系統(tǒng)中選擇合適的指令組成的指令序列。因此，計算機算法就是計算機能執(zhí)行的操作所組成的指令序列。不同的計算機系統(tǒng),其指令系統(tǒng)是有差異的,但一般的計算機系統(tǒng)中都包括的運算和操作有4類,即算術運算、邏輯運算、關系運算和數據傳輸。
算法的控制結構:算法中各操作之間的執(zhí)行順序稱為算法的控制結構。算法的功能不僅取決于所選用的操作,還與各操作之間的執(zhí)行順序有關�；镜目刂平Y構包括順序結構、選擇結構和循環(huán)結構。
(3)算法設計的基本方法
算法設計的基本方法有列舉法、歸納法、遞推法、遞歸法、減半遞推技術和回溯法。
2.算法復雜度
算法復雜度主要包括時間復雜度和空間復雜度。
(1)算法的時間復雜度
所謂算法的時間復雜度,是指執(zhí)行算法所需要的計算工作量。
一般情況下,算法的工作量用算法所執(zhí)行的基本運算次數來度量,而算法所執(zhí)行的基本運算次數是問題規(guī)模的函數,即
算法的工作量=f（n）
其中n是問題的規(guī)模。這個表達式表示隨著問題規(guī)模n的增大,算法執(zhí)行時間的增長率和f(n)的增長率相同。
在同一個問題規(guī)模下,如果算法執(zhí)行所需的基本運算次數取決于某一特定輸入,可以用兩種方法來分析算法的工作量:平均性態(tài)分析和最壞情況分析。
(2)算法的空間復雜度
一個算法的空間復雜度,一般是指執(zhí)行這個算法所需要的內存空間。算法執(zhí)行期間所需要的存儲空間包括以下3個部分。
算法程序所占的空間;
輸入的初始數據所占的存儲空間;
算法執(zhí)行過程中所需要的額外空間。
在許多實際問題中,為了減少算法所占的存儲空間,通常采用壓縮存儲技術。
考點2數據結構的基本概念1.數據結構的定義
數據結構是指相互有關聯(lián)的數據元素的集合,即數據的組織形式。
考核概率為45%。該知識點屬于熟記內容，考生要熟記數據結構的定義、分類,能區(qū)分線性結構與非線性結構。(1)數據的邏輯結構
所謂數據的邏輯結構,是指反映數據元素之間邏輯關系（即前、后件關系）的數據結構。它包括數據元素的集合和數據元素之間的關系。
(2)數據的存儲結構
數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱為數據的物理結構）。數據結構的存儲方式有順序存儲方法、鏈式存儲方法、索引存儲方法和散列存儲方法。而采用不同的存儲結構,其數據處理的效率是不同的。因此,在進行數據處理時,選擇合適的存儲結構是很重要的。
數據結構研究的內容主要包括3個方面：
數據集合中各數據元素之間的邏輯關系,即數據的邏輯結構;
在對數據進行處理時,各數據元素在計算機中的存儲關系,即數據的存儲結構;
對各種數據結構進行的運算。
2.數據結構的圖形表示
數據元素之間最基本的關系是前、后件關系。前、后件關系即每一個二元組,都可以用圖形來表示。用中間標有元素值的方框表示數據元素,一般稱之為數據節(jié)點,簡稱為節(jié)點。對于每一個二元組,用一條有向線段從前件指向后件。
用圖形表示數據結構具有直觀、易懂的特點，在不引起歧義的情況下,前件節(jié)點到后件節(jié)點連線上的箭頭可以省去。例如,樹形結構中,通常是用無向線段來表示前、后件關系的。
3.線性結構與非線性結構
根據數據結構中各數據元素之間前、后關系的復雜程度,一般將數據結構分為兩大類型,即線性結構和非線性結構。
如果一個非空的數據結構有且只有一個根節(jié)點,并且每個節(jié)點最多有一個直接前驅或直接后繼,則稱該數據結構為線性結構,又稱線性表。不滿足上述條件的數據結構稱為非線性結構。
小提示需要注意的是,在一個線性結構中插入或刪除任何一個節(jié)點后還應該是線性結構;否則,不能稱之為線性結構。
下列敘述中正確的是()。
A.程序執(zhí)行的效率與數據的存儲結構密切相關
B.程序執(zhí)行的效率只取決于程序的控制結構
C.程序執(zhí)行的效率只取決于所處理的數據量
D.以上3種說法都不對
【答案】 A
【解析】在計算機中,數據的存儲結構對數據的執(zhí)行效率有較大影響,如在有序存儲的表中查找某個數值比在無序存儲的表中查找的效率高很多。
書單推薦
