1、電腦等級考試公共基礎(chǔ)知識，溫俊香，第2頁，電腦2級考試公共基礎(chǔ)知識大綱，數(shù)據(jù)結(jié)構(gòu)和算法計(jì)算機(jī)編程基礎(chǔ)軟件工程學(xué)科基礎(chǔ)數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)，牙齒4個(gè)茄子方面是選擇題10個(gè)(20分)，共題5個(gè)(10分)，總成績占卷成績30分，第3頁，共分算法復(fù)雜性的概念和含義，第1，基本數(shù)據(jù)結(jié)構(gòu)和算法，數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)概念線性表堆棧和隊(duì)列樹和二叉樹祖懷技術(shù)排序技術(shù)，對于等級考試，牙齒部分的評估主要是算法和數(shù)據(jù)結(jié)構(gòu)的基本概念，二叉樹(，第5頁，算法定義將問題解決方案的準(zhǔn)確完整說明稱為算法)。算法是計(jì)算機(jī)編程的核心，算法的基本概念，算法是在有限階段用于解決問題的定義的規(guī)則集。通俗地說，就是計(jì)算機(jī)解題的過程(計(jì)算方法)。在牙

2、齒過程中，無論形成問題解決思想(推理實(shí)現(xiàn)算法)還是構(gòu)建節(jié)目(操作實(shí)現(xiàn)算法)，都是一種算法實(shí)現(xiàn)。例如：n的數(shù)字從大到小排序。有多種茄子排序方法，一般有冒泡排序、選擇排序等。算法不等于節(jié)目，電腦方法也不等，節(jié)目編制不能優(yōu)于算法的設(shè)計(jì)。講座講座講座，第6頁，第2頁。一個(gè)算法基本特征算法必須具有以下五個(gè)茄子重要特征：貧困確定性I/o可能性，足夠的信息，第7頁，算法和計(jì)算機(jī)程序算法_ _ _ _ _ _是計(jì)算機(jī)語言說明算法，3.傳統(tǒng)算法-圖形方法(如“流程圖”和N-S圖)當(dāng)前常用的方法-使用醫(yī)生代碼對算法進(jìn)行說明。第8頁，冒泡排序方法：1。掃描整個(gè)線性表，比較兩個(gè)相鄰的元素，相反的情況下，更換第一次掃描

3、的結(jié)果，最大的元素排名上升到表的末尾。2.除了最后一個(gè)元素，其余的元素，將第二個(gè)大數(shù)字排列在表末第二個(gè)位置，重復(fù)上述過程；重復(fù)上述過程。對于長度為N的路線表，必須在冒泡排序表中掃描n-1次。算法示例：排序N個(gè)數(shù)字，第9頁，第4頁。算法兩個(gè)茄子基本要素：基本運(yùn)算和運(yùn)算算術(shù)關(guān)系運(yùn)算邏輯運(yùn)算符資料傳輸、控制結(jié)構(gòu)順序選擇循環(huán)、一、數(shù)據(jù)對象的運(yùn)算和操作二、算法控制結(jié)構(gòu)。算法基本設(shè)計(jì)方法：枚舉法，歸納法，遞歸，遞歸，減法遞歸技術(shù)，回溯法，第10頁，第5頁。算法復(fù)雜性評估算法右列的主要標(biāo)準(zhǔn)是算法執(zhí)行效率和存儲要求：時(shí)間復(fù)雜度：牙齒算法執(zhí)行所需的計(jì)算工作量通?？梢酝ㄟ^算法執(zhí)行過程中所需的基本運(yùn)算的執(zhí)行數(shù)來衡量

4、計(jì)算工作量空間復(fù)雜性。運(yùn)行牙齒算法所需的內(nèi)存空間算法在運(yùn)行過程中臨時(shí)占用的存儲空間時(shí)間的復(fù)雜性幾乎等于計(jì)算機(jī)執(zhí)行簡單任務(wù)所需的平均時(shí)間乘以算法執(zhí)行簡單任務(wù)的次數(shù)。一個(gè)算法在電腦存儲中占用的存儲空間(包括存儲算法本身占用的存儲空間、算法輸入輸出數(shù)據(jù)占用的存儲空間、執(zhí)行過程中算法臨時(shí)占用的存儲空間)、第11頁，(1)在計(jì)算機(jī)中，算法為_ _ _ _ _ _ _ _。A.查詢方法b .處理方法c .對問題解決方案的準(zhǔn)確完整的說明d .排序方法(2)在以下說明中正確的是(07年四月)a .算法效率只與問題的規(guī)模有關(guān)。相反，與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的b)算法時(shí)間復(fù)雜度是執(zhí)行算法所需的計(jì)算工作量c)數(shù)據(jù)的邏輯

5、結(jié)構(gòu)和存儲結(jié)構(gòu)是一對一的對應(yīng)d)算法時(shí)間復(fù)雜度和空間復(fù)雜性調(diào)度相關(guān)(3)算法貧窮意味著(08年四月)，A)算法程序的運(yùn)行時(shí)間有限。b)算法程序處理的數(shù)據(jù)量有限。c)算法方案的長度有限。d)算法的使用受到限制。(c)，(B)，算法練習(xí)3360，(a)，第12頁， (4)算法試運(yùn)行的復(fù)雜性包括(2010年三月)A)算法運(yùn)行時(shí)間b)算法處理數(shù)據(jù)量c)算法程序的語句或命令數(shù)d)算法運(yùn)行所需的基本計(jì)算數(shù)(5)算法空間復(fù)雜性是(09年九月)A)運(yùn)行算法所需的計(jì)算機(jī)存儲空間b)算法處理數(shù)據(jù)量其空間復(fù)雜性必須小d)牙齒三種茄子說法都不對。(D)計(jì)算工作量，(A)，(D)，算法時(shí)間復(fù)雜度是A)運(yùn)行算法節(jié)目所需的

6、時(shí)間b)算法節(jié)目長度c)運(yùn)行算法所需的基本計(jì)算算法空間的復(fù)雜性A)算法程序的長度b)算法程序的命令數(shù)c)算法程序占用的存儲空間D)運(yùn)行過程中所需的存儲空間，以及示例說明算法分析的目的是a)數(shù)據(jù)結(jié)構(gòu)的合理性b)在算法中查找輸入和輸出之間的關(guān)系c)分析算法的可理解性和可靠性d)分析算法的效率提高算法的工作量大小和實(shí)現(xiàn)算法所需的存儲單元數(shù)分別稱為算法1。時(shí)間復(fù)雜度和空間復(fù)雜性，第15頁，計(jì)算機(jī)處理數(shù)據(jù)時(shí)，實(shí)際需要處理的數(shù)據(jù)元素，這些大量數(shù)據(jù)元素都必須保存在計(jì)算機(jī)上，因此，在計(jì)算機(jī)上配置提高大量數(shù)據(jù)元素、數(shù)據(jù)處理效率和節(jié)省電腦儲存空間的方法是處理數(shù)據(jù)的關(guān)鍵。2、數(shù)據(jù)結(jié)構(gòu)、節(jié)目=算法數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)是

7、相互關(guān)聯(lián)的數(shù)據(jù)元素的集合。通常，不同類型的數(shù)據(jù)元素(特性完全不同，沒有徐璐關(guān)系)不會(huì)同時(shí)處理，對于具有不同特性的數(shù)據(jù)元素，始終單獨(dú)處理。通常，在具有相同特征的數(shù)據(jù)元素集合中，數(shù)據(jù)元素之間存在關(guān)系(即連接)，牙齒關(guān)系反映了該集合中數(shù)據(jù)元素的固有結(jié)構(gòu)。超市的東西怎么保管才能找到，節(jié)省空間？第16頁，第2頁。數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)和相互關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的學(xué)科，包括三個(gè)茄子方面。(1)數(shù)據(jù)集內(nèi)每個(gè)數(shù)據(jù)元素之間固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)(2)處理數(shù)據(jù)時(shí)，每個(gè)數(shù)據(jù)元素存儲在計(jì)算機(jī)上的關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。(3)各種數(shù)據(jù)結(jié)構(gòu)計(jì)算。第17頁，第1頁。邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯

8、結(jié)構(gòu)是反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)如下：(1)表示數(shù)據(jù)元素信息。(2)表示每個(gè)數(shù)據(jù)元素之間的前后關(guān)系。范例：1。一年四季的數(shù)據(jù)結(jié)構(gòu)B=(D，R) D=春天、夏天、秋天、冬天R=(春天、夏天)、(夏天、秋天)、(秋天、冬天)2線性結(jié)構(gòu)中的每個(gè)元素之間存在一對一的關(guān)系。樹狀結(jié)構(gòu)中的每個(gè)元素之間有多個(gè)關(guān)系。圖形或網(wǎng)格結(jié)構(gòu)中的每個(gè)元素之間存在多對關(guān)系。其中樹狀結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為非線性結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以用二元關(guān)系或圖形表示。第19頁，第2頁。存儲結(jié)構(gòu)(物理結(jié)構(gòu))計(jì)算機(jī)實(shí)際執(zhí)行數(shù)據(jù)處理時(shí)處理的每個(gè)數(shù)據(jù)元素總是存儲在計(jì)算機(jī)的存儲空間中。此外，每個(gè)數(shù)據(jù)元素在電腦存儲空間中的位置可

9、能不一定與邏輯關(guān)系相同，通常也不能相同。例如：一年四季如何存儲家族成員電腦儲存空間？存儲結(jié)構(gòu)表示電腦存儲空間中的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。典型的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)索引存儲結(jié)構(gòu)，無論存儲方式如何，抽象地反映數(shù)據(jù)元素之間關(guān)系的結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要表示為一個(gè)或多個(gè)存儲結(jié)構(gòu)。第20頁，第3頁。數(shù)據(jù)運(yùn)算搜索插入刪除更新排序，通常數(shù)據(jù)結(jié)構(gòu)中的元素節(jié)點(diǎn)可以動(dòng)態(tài)更改。您可以根據(jù)需要或在處理過程中向數(shù)據(jù)結(jié)構(gòu)(插入操作)添加新節(jié)點(diǎn)或刪除節(jié)點(diǎn)(刪除操作)，數(shù)據(jù)結(jié)構(gòu)操作包括查找、分類、合并、分解、復(fù)制和修改。在數(shù)據(jù)結(jié)構(gòu)處理過程中，數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)數(shù)不僅可以動(dòng)態(tài)更改，而且每個(gè)數(shù)據(jù)元素之間的關(guān)系也可

10、以動(dòng)態(tài)更改。例如：無序表變化順序表，數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)與數(shù)據(jù)之間關(guān)系的學(xué)科，研究接下來的三個(gè)茄子方面：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運(yùn)算，第21|92頁，常規(guī)數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)分類線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩種茄子類型，線性結(jié)構(gòu)只有一個(gè)根節(jié)點(diǎn)。除第一個(gè)節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)最多有一個(gè)前面。除了最后一個(gè)節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)最多有一個(gè)后綴。典型的線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、線性鏈表等，第22|92頁，典型的非線性結(jié)構(gòu)包括樹、二叉樹、圖片等，非線性結(jié)構(gòu)。一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)。23頁，線性表，線性表是由n(n0)個(gè)數(shù)據(jù)元素a1、a2、ai、an組成的有限序列。簡單的線性表，復(fù)雜的線性表，記錄1 02011

11、001歲男性，記錄2 02011003里4女性，記錄3，記錄4，第24頁，線性表的順序存儲結(jié)構(gòu)，特征：順序存儲結(jié)構(gòu)邏輯線性表的順序存儲結(jié)構(gòu)稱為順序表。，第26頁，插入運(yùn)算，插入算法分析：線性表中包含n個(gè)數(shù)據(jù)元素，假設(shè)插入操作中在n 1位置插入元素的可能性相同，那么平均移動(dòng)元素?cái)?shù)，第27頁，刪除運(yùn)算，刪除算法分析3360線性表中的數(shù)據(jù)元素楊怡很多，如果經(jīng)常需要插入或刪除操作，那么需要考慮牙齒點(diǎn)。第、28頁，線性表格的鏈儲存結(jié)構(gòu)，線性表格的鏈儲存結(jié)構(gòu)稱為線性鏈表。鏈存儲結(jié)構(gòu)不需要與邏輯相鄰的數(shù)據(jù)元素物理位置相鄰，每個(gè)數(shù)據(jù)元素存儲順序也是隨機(jī)的。每個(gè)數(shù)據(jù)元素前后的關(guān)系由每個(gè)節(jié)點(diǎn)的指針字段表示。鏈存儲

12、結(jié)構(gòu)中的每個(gè)存儲節(jié)點(diǎn)不僅存儲節(jié)點(diǎn)值，還存儲存儲節(jié)點(diǎn)之間的關(guān)系。鏈存儲結(jié)構(gòu)包括單鏈表、雙向鏈表、循環(huán)鏈表線性鏈表隨機(jī)存取、第29頁、線性表設(shè)置(a1、a2、a3、a4、A5)、HEAD:1 2 3這些編號不表示相應(yīng)地址單元的地址代碼、線性表的鏈存儲結(jié)構(gòu)和插入和刪除操作、第30頁、單鏈路表、第31頁、單鏈路表插入操作、在P指向的節(jié)點(diǎn)后插入新節(jié)點(diǎn)、刪除單鏈路表操作、刪除3360節(jié)點(diǎn)ai的請求等。第32頁，循環(huán)鏈表：末尾與末尾相接的鏈表。如果將最后一個(gè)節(jié)點(diǎn)的空指針更改為指向頭節(jié)點(diǎn)，則可以在任何節(jié)點(diǎn)上找到其他節(jié)點(diǎn)。L，您可以直接查看一個(gè)節(jié)點(diǎn)的燈泡和后續(xù)節(jié)點(diǎn)?？梢蕴岣咝?。問題：單向鏈表的缺點(diǎn)是什么？提示

13、：如何查找節(jié)點(diǎn)的直接趨勢。雙向鏈表可以克服單鏈表的單向缺點(diǎn)。雙向鏈表節(jié)點(diǎn)有兩個(gè)指針字段，一個(gè)直接指向后面，另一個(gè)直接向前。雙向循環(huán)鏈表，第34頁，線性表應(yīng)用節(jié)目：應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)。高級語言中陣列計(jì)算機(jī)的文件系統(tǒng)電腦目錄系統(tǒng)；電話號碼祖懷系統(tǒng)(可以使用順序表或單鏈接表結(jié)構(gòu))各種事務(wù)處理(可以使用順序表或單鏈接表結(jié)構(gòu))，第35頁，第2頁。堆棧和隊(duì)列、堆棧和隊(duì)列是兩個(gè)茄子特殊的線性表，也稱為受限數(shù)據(jù)結(jié)構(gòu)，因?yàn)樗鼈兪窃诓僮髦惺艿教囟ㄏ拗频木€性表。堆棧及其主計(jì)算隊(duì)列及其主計(jì)算循環(huán)隊(duì)列及其主計(jì)算，第36頁，1。堆棧，堆棧是限制僅在頁腳中插入或刪除操作的線性表。堆疊頂部頁尾。堆疊底部標(biāo)頭。空堆棧中沒有元素的空表。堆疊、堆疊、堆疊s=(a1、a2、an)、后進(jìn)先出或先進(jìn)先出(LIFO)，第37頁，堆疊的實(shí)體儲存結(jié)構(gòu)可以是順序結(jié)構(gòu)或鏈表結(jié)構(gòu)。以下說明了在順序存儲結(jié)構(gòu)中插入和刪除堆棧元素的操作。有三種類型的茄子：進(jìn)入順序堆棧的基本運(yùn)算和退出堆棧的基本運(yùn)算。輸入堆棧、回退堆棧和讀取堆棧頂部元素，以及在序列堆棧中插入和刪除操作不需要移動(dòng)表中的其他數(shù)據(jù)元素。第38頁，第2頁。堆棧順序存儲結(jié)構(gòu)和基本運(yùn)算、順序存儲結(jié)構(gòu)表示的堆棧：順序堆棧將從堆棧底部到堆棧頂部的數(shù)據(jù)元素(通常表示為一維數(shù)組)存