計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)匯總.doc

計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)

第1章 數(shù)據(jù)結(jié)構(gòu)與算法

1.1 算法

1.1.1 算法的基本概念

算法是指對解題方案的準(zhǔn)確而完整的描述。簡單地說，就是解決問題的操作步驟。

值得注意的是，算法不等于數(shù)學(xué)上的計(jì)算方法，也不等于程序。在用計(jì)算機(jī)解決實(shí)際問題時(shí)，往往先設(shè)計(jì)算法，用某種表達(dá)方式(如流程圖)描述，然后再用具體的程序設(shè)計(jì)語言描述此算法(即編程)。在編程時(shí)由于要受到計(jì)算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制，因此，程序的編制通常不可能優(yōu)于算法的設(shè)計(jì)。

1.1.1.1 算法的基本特征

一般來說，一個(gè)算法應(yīng)具有以下4個(gè)基本特征。

(1)可行性(Effectiveness)：算法在特定的執(zhí)行環(huán)境中執(zhí)行，應(yīng)當(dāng)能夠得出滿意的結(jié)果，即必須有一個(gè)或多個(gè)輸出。

(2)確定性(Definiteness)：算法中的每一個(gè)步驟都必須有明確的定義，不允許有模棱兩可的解釋和多義性。

(3)有窮性(Finiteness)：算法必需在有限時(shí)間內(nèi)做完，即算法必需能在執(zhí)行有限個(gè)步驟之后終止。

(4)擁有足夠的情報(bào)：要使算法有效必需為算法提供足夠的情報(bào)。當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才是有效的；而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無效。

1.1.1.2 算法的基本要素

通常，一個(gè)算法由兩種基本要素組成。

?對數(shù)據(jù)對象的運(yùn)算和操作；

?算法的控制結(jié)構(gòu)，即運(yùn)算或操作時(shí)間的順序。

(1)算法中對數(shù)據(jù)的運(yùn)算和操作

在一般的計(jì)算機(jī)系統(tǒng)中，基本的運(yùn)算和操作有以下4類，如表1-1所示。

表1-1 4類基本的運(yùn)算和操作

運(yùn)算類型 操作實(shí) 例算術(shù)運(yùn)算＋、－、×、÷a＋b、3－1邏輯運(yùn)算與(&)、或(‖)、非(！)！1、1‖0、1&1關(guān)系運(yùn)算＞＜＝≠a>b、a=c 、b≠c數(shù)據(jù)傳輸賦值、輸入、輸出a=0、b=3(2)算法的控制結(jié)構(gòu)

一個(gè)算法的功能不僅僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。

算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅決定了算法中各操作的執(zhí)行順序，而且也直接反映了算法的設(shè)計(jì)是否符合結(jié)構(gòu)化原則。描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等。一個(gè)算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。

1.1.1.3 算法設(shè)計(jì)的基本方法

雖然設(shè)計(jì)算法是一件非常困難的工作，但是算法設(shè)計(jì)也不是無章可循，人們經(jīng)過實(shí)踐，總結(jié)和積累了許多行之有效的方法。常用的幾種算法設(shè)計(jì)方法有列舉法、歸納法、遞推法、遞歸法、減半遞推技術(shù)和回溯法。

1.1.1.4 算法設(shè)計(jì)的要求

通常一個(gè)好的算法應(yīng)達(dá)到如下目標(biāo)：

(1)正確性(Correctness)

正確性大體可以分為以下4個(gè)層次：

①程序不含語法錯(cuò)誤；

②程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；

③程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；

④程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。

(2)可讀性(Readability)

算法主要是為了方便人的閱讀與交流，其次才是其執(zhí)行。可讀性好有助于用戶對算法的理解；晦澀難懂的程序易于隱藏較多錯(cuò)誤，難以調(diào)試和修改。

(3)健壯性(Robustness)

當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。

(4)效率與低存儲(chǔ)量需求

效率指的是程序執(zhí)行時(shí)，對于同一個(gè)問題如果有多個(gè)算法可以解決，執(zhí)行時(shí)間短的算法效率高；存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。

1.1.2 算法的復(fù)雜度

算法的復(fù)雜度是算法效率的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。

算法復(fù)雜度包括算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜的。

1.1.2.1 算法的時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。

為了能夠比較客觀地反映出一個(gè)算法的效率，在度量一個(gè)算法的工作量時(shí)，不僅應(yīng)該與所使用的計(jì)算機(jī)、程序設(shè)計(jì)語言以及程序編制者無關(guān)，而且還應(yīng)該與算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)無關(guān)。

算法的計(jì)算工作量是用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量的，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模(通常用整數(shù)n表示)的函數(shù)。即

算法的工作量=f(n)

例如，在N×N矩陣相乘的算法中，整個(gè)算法的執(zhí)行時(shí)間與該基本操作(乘法)重復(fù)執(zhí)行的次數(shù)n3成正比，也就是時(shí)間復(fù)雜度為n3，即

f(n)=O(n3)

在有的情況下，算法中的基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例如在起泡排序的算法中，當(dāng)要排序的數(shù)組a初始序列為自小至大有序時(shí)，基本操作的執(zhí)行次數(shù)為0；當(dāng)初始序列為自大至小有序時(shí)，基本操作的執(zhí)行次數(shù)為n(n－1)/2。對這類算法，可以采用平均性態(tài)和最壞情況復(fù)雜性兩種方法來分析。

1.1.2.2 算法的

總結(jié)

以上是生活随笔為你收集整理的计算机公共基础知识论文,计算机等级考试二级公共基础知识汇总.doc的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。