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