- 相關(guān)推薦
2017年計算機等級msoffice�？贾R點(diǎn)積累
科學(xué)技術(shù)的發(fā)展特別是尖端科學(xué)技術(shù)的發(fā)展，需要高度精確的計算。計算機控制的導彈之所以能準確地擊中預定的目標，是與計算機的精確計算分不開(kāi)的。下面是小編整理的關(guān)于計算機等級msoffice�？贾R點(diǎn)積累，歡迎大家參考!
1.算法的基本概念
(1)概念：算法是指一系列解決問(wèn)題的清晰指令。
(2)4個(gè)基本特征：可行性、確定性、有窮性、擁有足夠的情報。
(3)兩種基本要素：對數據對象的運算和操作、算法的控制結構(運算和操作時(shí)問(wèn)的順序)。
(4)設計的基本方法：列舉法、歸納法、遞推法、遞歸法、減半遞推技術(shù)和回溯法。
2.算法的復雜度
(1)算法的時(shí)間復雜度：執行算法所需要的計算工作量。
(2)算法的空間復雜度：執行算法所需的內存空間。
1.2數據結構的基本概念
數據結構指相互有關(guān)聯(lián)的數據元素的集合，即數據的組織形式。其中邏輯結構反映數據元素之間邏輯關(guān)系;存儲結構為數據的邏輯結構在計算機存儲空間中的存放形式，有順序存儲、鏈式存儲、索引存儲和散列存儲4種方式。
數據結構按各元素之間前后件關(guān)系的復雜度可劃分為：
(1)線(xiàn)性結構：有且只有一個(gè)根節點(diǎn)，且每個(gè)節點(diǎn)最多有一個(gè)直接前驅和一個(gè)直接后繼的非空數據結構。
(2)非線(xiàn)性結構：不滿(mǎn)足線(xiàn)性結構的數據結構。
1.3線(xiàn)性表及其順序存儲結構
1.線(xiàn)性表的基本概念
線(xiàn)性結構又稱(chēng)線(xiàn)性表，線(xiàn)性表是最簡(jiǎn)單也是最常用的一種數據結構。
2.線(xiàn)性表的順序存儲結構
元素所占的存儲空間必須連續。
元素在存儲空間的位置是按邏輯順序存放的。
3.線(xiàn)性表的插入運算
在第i個(gè)元素之前插入一個(gè)新元素的步驟如下：
步驟一：把原來(lái)第n個(gè)節點(diǎn)至第i個(gè)節點(diǎn)依次往后移一個(gè)元素位置。
步驟二：把新節點(diǎn)放在第i個(gè)位置上。
步驟三：修正線(xiàn)性表的節點(diǎn)個(gè)數。
在最壞情況下，即插入元素在第一個(gè)位置，線(xiàn)性表中所有元素均需要移動(dòng)。
4.線(xiàn)性表的刪除運算
刪除第i個(gè)位置的元素的步驟如下：
步驟一：把第i個(gè)元素之后不包括第i個(gè)元素的n-i個(gè)元素依次前移一個(gè)位置;
步驟二：修正線(xiàn)性表的結點(diǎn)個(gè)數。
1.4棧和隊列
1.棧及其基本運算
(1)基本概念：棧是一種特殊的線(xiàn)性表，其插入運算與刪除運算都只在線(xiàn)性表的一端進(jìn)行，也被稱(chēng)為“先進(jìn)后出”表或“后進(jìn)先出”表。
棧頂：允許插入與刪除的一端。
棧底：棧頂的另一端。
空棧：棧中沒(méi)有元素的棧。
(2)特點(diǎn)。
棧頂元素是最后插入和最早被刪除的元素。
棧底元素是最早插入和最后被刪除的元素。
棧有記憶作用。
在順序存儲結構下，棧的插入和刪除運算不需移動(dòng)表中其他數據元素。
棧頂指針top動(dòng)態(tài)反映了棧中元素的變化情況
(3)順序存儲和運算：入棧運算、退棧運算和讀棧頂運算。
2.隊列及其基本運算
(1)基本概念：隊列是指允許在一端進(jìn)行插入，在另一端進(jìn)行刪除的線(xiàn)性表，又稱(chēng)“先進(jìn)先出”的線(xiàn)性表。
隊尾：允許插入的一端，用尾指針指向隊尾元素。
排頭：允許刪除的一端，用頭指針指向頭元素的前一位置。
(2)循環(huán)隊列及其運算。
所謂循環(huán)隊列，就是將隊列存儲空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。
入隊運算是指在循環(huán)隊列的隊尾加入一個(gè)新元素。
當循環(huán)隊列非空(s=1)且隊尾指針等于隊頭指針時(shí)，說(shuō)明循環(huán)隊列已滿(mǎn)，不能進(jìn)行人隊運算，這種情況稱(chēng)為“上溢”。
退隊運算是指在循環(huán)隊列的隊頭位置退出一個(gè)元素并賦給指定的變量。首先將隊頭指針進(jìn)一，然后將排頭指針指向的元素賦給指定的變量。當循環(huán)隊列為空(s=0)時(shí)，不能進(jìn)行退隊運算，這種情況稱(chēng)為“下溢”。
1.5線(xiàn)性鏈表
在定義的鏈表中，若只含有一個(gè)指針域來(lái)存放下一個(gè)元素地址，稱(chēng)這樣的鏈表為單鏈表或線(xiàn)性鏈表。
在鏈式存儲方式中，要求每個(gè)結點(diǎn)由兩部分組成：一部分用于存放數據元素值，稱(chēng)為數據域;另一部分用于存放指針，稱(chēng)為指針域。其中指針用于指向該結點(diǎn)的前一個(gè)或后一個(gè)結點(diǎn)(即前件或后件)。
1.6樹(shù)和二叉樹(shù)
1.樹(shù)的基本概念
樹(shù)是簡(jiǎn)單的非線(xiàn)性結構，樹(shù)中有且僅有一個(gè)沒(méi)有前驅的節點(diǎn)稱(chēng)為“根”，其余節點(diǎn)分成m個(gè)互不相交的有限集合T1，T2，…，T}mm，每個(gè)集合又是一棵樹(shù)，稱(chēng)T1，T2，…，T}mm為根結點(diǎn)的子樹(shù)。
父節點(diǎn)：每一個(gè)節點(diǎn)只有一個(gè)前件，無(wú)前件的節點(diǎn)只有一個(gè)，稱(chēng)為樹(shù)的根結點(diǎn)(簡(jiǎn)稱(chēng)樹(shù)的根)。
子節點(diǎn)：每～個(gè)節點(diǎn)可以后多個(gè)后件，無(wú)后件的節點(diǎn)稱(chēng)為葉子節點(diǎn)。
樹(shù)的度：所有節點(diǎn)最大的度。
樹(shù)的深度：樹(shù)的最大層次。
2.二叉樹(shù)的定義及其基本性質(zhì)
(1)二叉樹(shù)的定義：二叉樹(shù)是一種非線(xiàn)性結構，是有限的節點(diǎn)集合，該集合為空(空二叉樹(shù))或由一個(gè)根節點(diǎn)及兩棵互不相交的左右二叉子樹(shù)組成�？煞譃闈M(mǎn)二叉樹(shù)和完全二叉樹(shù)，其中滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)，但完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。二叉樹(shù)具有如下兩個(gè)特點(diǎn)：
二叉樹(shù)可為空，空的二叉樹(shù)無(wú)節點(diǎn)，非空二叉樹(shù)有且只有一個(gè)根結點(diǎn);
每個(gè)節點(diǎn)最多可有兩棵子樹(shù)，稱(chēng)為左子樹(shù)和右子樹(shù)。
(2)二叉樹(shù)的基本性質(zhì)。
性質(zhì)1：在二叉樹(shù)的第k層上至多有2k-1個(gè)結點(diǎn)(k≥1)。
性質(zhì)2：深度為m的二叉樹(shù)至多有2m-1個(gè)結點(diǎn)。
性質(zhì)3：對任何一棵二叉樹(shù)，度為0的結點(diǎn)(即葉子結點(diǎn))總是比度為2的結點(diǎn)多一個(gè)。
性質(zhì)4：具有n個(gè)結點(diǎn)的完全二叉樹(shù)的深度至少為[log2n]+1，其中[log2n]表示log2n的整數部分。
3.滿(mǎn)二叉樹(shù)與完全二叉樹(shù)
(1)滿(mǎn)二叉樹(shù)：滿(mǎn)二叉樹(shù)是指這樣的一種二叉樹(shù)：除最后一層外，每一層上的所有結點(diǎn)都有兩個(gè)子結點(diǎn)。滿(mǎn)二叉樹(shù)在其第i層上有2i-1個(gè)結點(diǎn)。
從上面滿(mǎn)二叉樹(shù)定義可知，二叉樹(shù)的每一層上的結點(diǎn)數必須都達到最大，否則就不是滿(mǎn)二叉樹(shù)。深度為m的滿(mǎn)二叉樹(shù)有2m-1個(gè)結點(diǎn)。
(2)完全二叉樹(shù)：完全二叉樹(shù)是指這樣的二叉樹(shù)：除最后一層外，每一層上的結點(diǎn)數均達到最大值;在最后一層上只缺少右邊的若干結點(diǎn)。
如果—棵具有n個(gè)結點(diǎn)的深度為k的二叉樹(shù)，它的每—個(gè)結點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號為1～n的結點(diǎn)——對應。
3.二叉樹(shù)的存儲結構
二叉樹(shù)通常采用鏈式存儲結構，存儲節點(diǎn)由數據域和指針域(左指針域和右指針域)組成。二叉樹(shù)的鏈式存儲結構也稱(chēng)二叉鏈表，對滿(mǎn)二叉樹(shù)和完全二叉樹(shù)可按層次進(jìn)行順序存儲。
4.二叉樹(shù)的遍歷
二叉樹(shù)的遍歷是指不重復地訪(fǎng)問(wèn)二叉樹(shù)中所有節點(diǎn)，主要指非空二叉樹(shù)，對于空二叉樹(shù)則結束返回。二叉樹(shù)的遍歷包括前序遍歷、中序遍歷和后序遍歷。
(1)前序遍歷。
前序遍歷是指在訪(fǎng)問(wèn)根結點(diǎn)、遍歷左子樹(shù)與遍歷右子樹(shù)這三者中，首先訪(fǎng)問(wèn)根結點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù);并且，在遍歷左右子樹(shù)時(shí)，仍然先訪(fǎng)問(wèn)根結點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。前序遍歷描述為：若二叉樹(shù)為空，則執行空操作;否則①訪(fǎng)問(wèn)根結點(diǎn);②前序遍歷左子樹(shù);③前序遍歷右子樹(shù)。
(2)中序遍歷。
中序遍歷是指在訪(fǎng)問(wèn)根結點(diǎn)、遍歷左子樹(shù)與遍歷右子樹(shù)這三者中，首先遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結點(diǎn)，最后遍歷右子樹(shù);并且，在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結點(diǎn)，最后遍歷右子樹(shù)。中序遍歷描述為：若二叉樹(shù)為空，則執行空操作;否則①中序遍歷左子樹(shù);②訪(fǎng)問(wèn)根結點(diǎn);③中序遍歷右子樹(shù)。
(3)后序遍歷。
后序遍歷是指在訪(fǎng)問(wèn)根結點(diǎn)、遍歷左子樹(shù)與遍歷右子樹(shù)這三者中，首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪(fǎng)問(wèn)根結點(diǎn)，并且，在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪(fǎng)問(wèn)根結點(diǎn)。后序遍歷描述為：若二叉樹(shù)為空，則執行空操作;否則①后序遍歷左子樹(shù);②后序遍歷右子樹(shù);③訪(fǎng)問(wèn)根結點(diǎn)。
1.7查找技術(shù)
(1)順序查找：在線(xiàn)性表中查找指定的元素。
(2)最壞情況下，最后一個(gè)元素才是要找的元素，則需要與線(xiàn)性表中所有元素比較，比較次數為n。
(2)二分查找：二分查找也稱(chēng)折半查找，它是一種高效率的查找方法。但二分查找有條件限制，它要求表必須用順序存儲結構，且表中元素必須按關(guān)鍵字有序(升序或降序均可)排列。對長(cháng)度為n的有序線(xiàn)性表，在最壞情況下，二分查找法只需比較log2n次。
1.8排序技術(shù)
(1)交換類(lèi)排序法。
冒泡排序：通過(guò)對待排序序列從后向前或從前向后，依次比較相鄰元素的排序碼，若發(fā)現逆序則交換，使較大的元素逐漸從前部移向后部或較小的元素逐漸從后部移向前部，直到所有元素有序為止。在最壞情況下，對長(cháng)度為n的線(xiàn)性表排序，冒泡排序需要比較的次數為n(n-1)/2。
快速排序：是迄今為止所有內排序算法中速度最快的一種。它的基本思想是：任取待排序序列中的某個(gè)元素作為基準(一般取第一個(gè)元素)，通過(guò)一趟排序，將待排元素分為左右兩個(gè)子序列，左子序列元索的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基準元素的排序碼，然后分別對兩個(gè)子序列繼續進(jìn)行排序，直至整個(gè)序列有序。最壞情況下，即每次劃分，只得到一個(gè)序列，時(shí)間效率為O(n2)。
(2)插人類(lèi)排序法。
簡(jiǎn)單插入排序法：把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無(wú)序表，開(kāi)始時(shí)有序表中只包含一個(gè)元素，無(wú)序表中包含有n-1個(gè)元素，排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素，把它的排序碼依次與有序表元素的排序碼進(jìn)行比較，將它插入到有序表中的適當位置，使之成為新的有序表。在最壞情況下，即初始排序序列是逆序的情況下，比較次數為n(n-1)/2，移動(dòng)次數為n(n-1)/2。
希爾排序法：先將整個(gè)待排元素序列分割成若干個(gè)子序列(由相隔某個(gè)“增量”的元素組成的)分別進(jìn)行直接插入排序。待整個(gè)序列中的元素基本有序(增量足夠小)時(shí)，再對全體元素進(jìn)行一次直接插入排序。
(3)選擇類(lèi)排序法。
簡(jiǎn)單選擇排序法：掃描整個(gè)線(xiàn)性表。從中選出最小的元素。將它交換到表的最前面;然后對剩下的子表采用同樣的方法，直到子表空為止。最壞情況下需要比較n(n-1)/2次。
堆排序的方法：首先將一個(gè)無(wú)序序列建成堆;然后將堆頂元素(序列中的最大項)與堆中最后一個(gè)元素交換(最大項應該在序列的最后)。不考慮已經(jīng)換到最后的那個(gè)元素，只考慮前n-1個(gè)元素構成的子序列，將該子序列調整為堆。反復做步驟②，直到剩下的子序列空為止。在最壞情況下，堆排序法需要比較的次數為0(nlog2n)
【計算機等級msoffice�？贾R點(diǎn)積累】相關(guān)文章：
2017年計算機等級MSOffice�？贾R點(diǎn)03-04
計算機二級MSOffice考試知識點(diǎn)積累09-20
2017年計算機等級一級MSoffice復習知識點(diǎn)03-09
計算機二級vfp�？贾R點(diǎn)03-27