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