office二級共工基礎知識知識點總結（一）

第一章 資料結構與演算法

計算機二級office選擇題真題部分經常考查的是演算法複雜度、資料結構的概念、棧、二叉樹的遍歷、二分法查詢，讀者應對此部分進行重點學習。

詳細重點學習知識點：

1．演算法的概念、演算法時間複雜度及空間複雜度的概念

2．資料結構的定義、資料邏輯結構及物理結構的定義

3．棧的定義及其運算、線性連結串列的儲存方式

4．樹與二叉樹的概念、二叉樹的基本性質、完全二叉樹的概念、二叉樹的遍歷

5．二分查詢法

6．氣泡排序法

1。1演算法

1 、演算法的基本概念

計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。

1．演算法的基本特徵：可行性、確定性、有窮性、擁有足夠的情報。

2．演算法的基本要素：

（1）演算法中對資料的運算和操作

一個演算法由兩種基本要素組成：一是對資料物件的運算和操作；二是演算法的控制結構。

在一般的計算機系統中，基本的運算和操作有以下4類：算術運算、邏輯運算、關係運算和資料傳輸。

（2）演算法的控制結構：演算法中各操作之間的執行順序稱為演算法的控制結構。

描述演算法的工具通常有傳統流程圖、N-S結構化流程圖、演算法描述語言等。一個演算法一般都可以用順序、選擇、迴圈3種基本控制結構組合而成。

2、 演算法複雜度

1。演算法的時間複雜度

演算法的時間複雜度是指執行演算法所需要的計算工作量。

同一個演算法用不同的語言實現，或者用不同的編譯程式進行編譯，或者在不同的計算機上執行，效率均不同。這表明使用絕對的時間單位衡量演算法的效率是不合適的。撇開這些與計算機硬體、軟體有關的因素，可以認為一個特定演算法“執行工作量”的大小，只依賴於問題的規模（通常用整數n表示），它是問題規模的函式。即演算法的工作量=f（n）

2。演算法的空間複雜度

演算法的空間複雜度是指執行這個演算法所需要的記憶體空間。

一個演算法所佔用的儲存空間包括演算法程式所佔的空間、輸入的初始資料所佔的儲存空間以及演算法執行過程中所需要的額外空間。其中額外空間包括演算法程式執行過程中的工作單元以及某種資料結構所需要的附加儲存空間。如果額外空間量相對於問題規模來說是常數，則稱該演算法是原地工作的。在許多實際問題中，為了減少演算法所佔的儲存空間，通常採用壓縮儲存技術，以便儘量減少不必要的額外空間。

演算法的工作量用演算法所執行的基本運算次數來計算，而演算法所執行的基本運算次數是問題規模的函式，即演算法的工作量=f（n），其中n是問題的規模。

1。2資料結構的基本概念

3 、資料結構的定義

資料結構作為計算機的一門學科，主要研究和討論以下三個方面：

（1）資料集合中個數據元素之間所固有的邏輯關係，即資料的邏輯結構；

（2）在對資料元素進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構；

（3）對各種資料結構進行的運算。

資料：是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中並被計算機程式處理的符號的總稱。

資料元素：是資料的基本單位，在計算機程式中通常作為一個整體進行考慮和處理。

資料物件：是性質相同的資料元素的集合，是資料的一個子集。

資料的邏輯結構是對資料元素之間的邏輯關係的描述，它可以用一個數據元素的集合和定義在此集合中的若干關係來表示。資料的邏輯結構有兩個要素：一是資料元素的集合，通常記為D；二是D上的關係，它反映了資料元素之間的前後件關係，通常記為R。一個數據結構可以表示成

B=（D，R）

其中B表示資料結構。為了反映D中各資料元素之間的前後件關係，一般用二元組來表示。

資料的邏輯結構在計算機儲存空間中的存放形式稱為資料的儲存結構（也稱資料的物理結構）。

由於資料元素在計算機儲存空間中的位置關係可能與邏輯關係不同，因此，為了表示存放在計算機儲存空間中的各資料元素之間的邏輯關係（即前後件關係），在資料的儲存結構中，不僅要存放各資料元素的資訊，還需要存放各資料元素之間的前後件關係的資訊。

一種資料的邏輯結構根據需要可以表示成多種儲存結構，常用的儲存結構有順序、連結、索引等儲存結構。而採用不同的儲存結構，其資料處理的效率是不同的。因此，在進行資料處理時，選擇合適的儲存結構是很重要的。

4 、線性結構與非線性結構

根據資料結構中各資料元素之間前後件關係的複雜程度，一般將資料結構分為兩大型別：線性結構與非線性結構。如果一個非空的資料結構滿足下列兩個條件：

（1）有且只有一個根結點；

（2）每一個結點最多有一個前件，也最多有一個後件。

則稱該資料結構為線性結構。線性結構又稱線性表。在一個線性結構中插入或刪除任何一個結點後還應是線性結構。如果一個數據結構不是線性結構，則稱之為非線性結構。

一個空的資料結構究竟是屬於線性結構還是屬於非線性結構，這要根據具體情況來確定。如果對該資料結構的演算法是按線性結構的規則來處理的，則屬於線性結構；否則屬於非線性結構。

1。3棧及線性連結串列

5 、棧及其基本運算

1．棧的基本概念

棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當表中沒有元素時稱為空棧。棧頂元素總是後被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最後才能被刪除的元素。棧是按照“先進後出”或“後進先出”的原則組織資料的。

2．棧的順序儲存及其運算

用一維陣列S（1∶m）作為棧的順序儲存空間，其中m為最大容量。

在棧的順序儲存空間S（1∶m）中，S（bottom）為棧底元素，S（top）為棧頂元素。top=0表示棧空；top=m表示棧滿。

棧的基本運算有三種：入棧、退棧與讀棧頂元素。

（1）入棧運算：入棧運算是指在棧頂位置插入一個新元素。首先將棧頂指標加一（即top加1），然後將新元素插入到棧頂指標指向的位置。當棧頂指標已經指向儲存空間的最後一個位置時，說明棧空間已滿，不可能再進行入棧操作。這種情況稱為棧“上溢”錯誤。

（2）退棧運算：退棧是指取出棧頂元素並賦給一個指定的變數。首先將棧頂元素（棧頂指標指向的元素）賦給一個指定的變數，然後將棧頂指標減一（即top減1）。當棧頂指標為0時，說明棧空，不可進行退棧操作。這種情況稱為棧的“下溢”錯誤。

（3）讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變數。這個運算不刪除棧頂元素，只是將它賦給一個變數，因此棧頂指標不會改變。當棧頂指標為0時，說明棧空，讀不到棧頂元素。

考點6 線性連結串列的基本概念

在鏈式儲存方式中，要求每個結點由兩部分組成：一部分用於存放資料元素值，稱為資料域，另一部分用於存放指標，稱為指標域。其中指標用於指向該結點的前一個或後一個結點（即前件或後件）。

鏈式儲存方式既可用於表示線性結構，也可用於表示非線性結構。

（1）線性連結串列

線性表的鏈式儲存結構稱為線性連結串列。

在某些應用中，對線性連結串列中的每個結點設定兩個指標，一個稱為左指標，用以指向其前件結點；另一個稱為右指標，用以指向其後件結點。這樣的表稱為雙向連結串列。

（2）帶鏈的棧

棧也是線性表，也可以採用鏈式儲存結構。帶鏈的棧可以用來收集計算機儲存空間中所有空閒的儲存結點，這種帶鏈的棧稱為可利用棧。

在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。

1。4樹與二叉樹

考點7 樹與二叉樹及其基本性質

滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。應該注意二者的區別。

1、樹的基本概念

樹（tree）是一種簡單的非線性結構。在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點。每一個結點可以有多個後件，它們稱為該結點的子結點。沒有後件的結點稱為葉子結點。

在樹結構中，一個結點所擁有的後件個數稱為該結點的度。葉子結點的度為0。在樹中，所有結點中的最大的度稱為樹的度。

2、二叉樹及其基本性質

（1）二叉樹的定義

二叉樹是一種很有用的非線性結構，具有以下兩個特點：

①非空二叉樹只有一個根結點；

②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹和右子樹。

由以上特點可以看出，在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。另外，二叉樹中的每個結點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個結點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當一個結點既沒有左子樹也沒有右子樹時，該結點即為葉子結點。

（2）二叉樹的基本性質

二叉樹具有以下幾個性質：

性質1：在二叉樹的第k層上，最多有2k-1（k≥1）個結點；

性質2：深度為m的二叉樹最多有2m-1個結點；

性質3：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。

性質4：具有n個結點的二叉樹，其深度至少為［log2n］+1，其中［log2n］表示取log2n的整數部分。

3、滿二叉樹與完全二叉樹

滿二叉樹是指這樣的一種二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第k層上有2k-1個結點，且深度為m的滿二叉樹有2m－1個結點。

完全二叉樹是指這樣的二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。

對於完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現：對於任何一個結點，若其右分支下的子孫結點的最大層次為p，則其左分支下的子孫結點的最大層次或為p，或為p+1。

完全二叉樹具有以下兩個性質：

性質5：具有n個結點的完全二叉樹的深度為［log2n］+1。

性質6：設完全二叉樹共有n個結點。如果從根結點開始，按層次（每一層從左到右）用自然數1，2，……，n給結點進行編號，則對於編號為k（k=1，2，……，n）的結點有以下結論：

①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為INT（k/2）。

②若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。

③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。

考點8 二叉樹的遍歷

在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左後右的原則下，根據訪問根結點的次序，二叉樹的遍歷分為三類：前序遍歷、中序遍歷和後序遍歷。

（1）前序遍歷：先訪問根結點、然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。

（2）中序遍歷：先遍歷左子樹、然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。

（3）後序遍歷：先遍歷左子樹、然後遍歷右子樹，最後訪問根結點；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。

在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。

1。5查詢技術

考點9 順序查詢

查詢是指在一個給定的資料結構中查詢某個指定的元素。從線性表的第一個元素開始，依次將線性表中的元素與被查詢的元素相比較，若相等則表示查詢成功；若線性表中所有的元素都與被查詢元素進行了比較但都不相等，則表示查詢失敗。

在下列兩種情況下也只能採用順序查詢：

（1）如果線性表為無序表，則不管是順序儲存結構還是鏈式儲存結構，只能用順序查詢。

（2）即使是有序線性表，如果採用鏈式儲存結構，也只能用順序查詢。

考點10 二分法查詢

二分法只適用於順序儲存的，按非遞減排列的有序表，其方法如下：

設有序線性表的長度為n，被查詢的元素為i，

（1）將i與線性表的中間項進行比較；

（2）若i與中間項的值相等，則查詢成功；

（3）若i小於中間項，則線上性表的前半部分以相同的方法查詢；

（4）若i大於中間項，則線上性表的後半部分以相同的方法查詢。

二分查詢法只適用於順序儲存的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。

這個過程一直進行到查詢成功或子表長度為0為止。

對於長度為n的有序線性表，在最壞情況下，二分查詢只需要比較log2n次。

1。6排序技術

考點11 交換類排序法

氣泡排序法和快速排序法都屬於交換類排序法。

（1）氣泡排序法

首先，從表頭開始往後掃描線性表，逐次比較相鄰兩個元素的大小，若前面的元素大於後面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往後移動，最後最大者到了線性表的最後。

然後，從後到前掃描剩下的線性表，逐次比較相鄰兩個元素的大小，若後面的元素小於前面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前移動，最後最小者到了線性表的最前面。

對剩下的線性表重複上述過程，直到剩下的線性表變空為止，此時已經排好序。

在最壞的情況下，氣泡排序需要比較次數為n（n－1）/2。

（2）快速排序法

它的基本思想是：任取待排序序列中的某個元素作為基準（一般取第一個元素），透過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小於或等於基準元素的排序碼，右子序列的排序碼則大於基準元素的排序碼，然後分別對兩個子序列繼續進行排序，直至整個序列有序。

氣泡排序法的平均執行時間是O（n2），而快速排序法的平均執行時間是O（nlog2n）。

1。7例題詳細解析

一、選擇題

【例1】演算法的時間複雜度取決於_______。（考點2）

A）問題的規模 B）待處理的資料的初態

C）問題的難度 D）A）和B）

解析：演算法的時間複雜度不僅與問題的規模有關，在同一個問題規模下，而且與輸入資料有關。即與輸入資料所有的可能取值範圍、輸入各種資料或資料集的機率有關。

答案：D）

【例2】在資料結構中，從邏輯上可以把資料結構分成_______。（考點3）

A）內部結構和外部結構 B）線性結構和非線性結構

C）緊湊結構和非緊湊結構 D）動態結構和靜態結構

解析：邏輯結構反映資料元素之間的邏輯關係，線性結構表示資料元素之間為一對一的關係，非線性結構表示資料元素之間為一對多或者多對一的關係，所以答案為B）。

答案：B）

【例3】以下_______不是棧的基本運算。（考點5）

A）判斷棧是否為素空 B）將棧置為空棧

C）刪除棧頂元素 D）刪除棧底元素

解析：棧的基本運算有：入棧，出棧（刪除棧頂元素），初始化、置空、判斷棧是否為空或滿、提取棧頂元素等，對棧的操作都是在棧頂進行的。

答案：D）

【例4】連結串列不具備的特點是_______。（考點6）

A）可隨機訪問任意一個結點 B）插入和刪除不需要移動任何元素

C）不必事先估計儲存空間 D）所需空間與其長度成正比

解析：順序表可以隨機訪問任意一個結點，而連結串列必須從第一個資料結點出發，逐一查詢每個結點。所以答案為A）。

答案：A）

【例5】已知某二叉樹的後序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是_______。（考點8）

A）ACBED B）DEABC

C）DECAB D）EDBAC

解析：後序遍歷的順序是“左子樹－右子樹－根結點”；中序遍歷順序是“左子樹－根結點－右子樹”；前序遍歷順序是“根結點－左子樹－右子樹”。根據各種遍歷演算法，不難得出前序遍歷序列是EDBAC。所以答案為D）。

答案：D）

【例6】設有一個已按各元素的值排好序的線性表（長度大於2），對給定的值k，分別用順序查詢法和二分查詢法查詢一個與k相等的元素，比較的次數分別是s和b，在查詢不成功的情況下，s和b的關係是_______。（考點9）

A）s=b B）s>b C）s

解析：對於順序查詢，查詢不成功時和給定關鍵字比較的次數為n+1。二分查詢查詢不成功的關鍵字比較次數為［log2n］+1。當n≥2時，顯然n+1>［log2n］+1。

答案：B）

【例7】在快速排序過程中，每次劃分，將被劃分的表（或子表）分成左、右兩個子表，考慮這兩個子表，下列結論一定正確的是_______。（考點11）

A）左、右兩個子表都已各自排好序

B）左邊子表中的元素都不大於右邊子表中的元素

C） 左邊子表的長度小於右邊子表的長度

D）左、右兩個子表中元素的平均值相等

解析：快速排序基本思想是：任取待排序表中的某個元素作為基準（一般取第一個元素），透過一趟排序，將待排元素分為左右兩個子表，左子表元素的排序碼均小於或等於基準元素的排序碼，右子表的排序碼則大於基準元素的排序碼，然後分別對兩個子表繼續進行排序，直至整個表有序。

答案：B）

二、填空題

【例1】問題處理方案的正確而完整的描述稱為_______。（考點1）

解析：計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。

答案：演算法

【例2】一個空的資料結構是按線性結構處理的，則屬於_______。（考點4）

解析：一個空的資料結構是線性結構或是非線性結構，要根據具體情況而定。如果對資料結構的運算是按線性結構來處理的，則屬於線性結構，否則屬於非線性結構。

答案：線性結構

【例3】設樹Ｔ的度為４，其中度為１、２、３和４的結點的個數分別為４、２、１、１，則Ｔ中葉子結點的個數為_______。（考點7）

解析：根據樹的性質：樹的結點數等於所有結點的度與對應的結點個數乘積之和加１。

因此樹的結點數為１×４＋２×２＋３×１＋４×１＋１＝16。葉子結點數目等於樹結點總數減去度不為０的結點數之和，即16－（４＋２＋１＋１）＝８。

答案：8

【例4】二分法查詢的儲存結構僅限於_______且是有序的。（考點10）

解析：二分查詢，也稱折半查詢，它是一種高效率的查詢方法。但二分查詢有條件限制：要求表必須用順序儲存結構，且表中元素必須按關鍵字有序（升序或降序均可）。

答案：順序儲存結構