一、二級公共基礎知識的高頻考點

（一）數據結構與算法

【考點1】算法的基本概念

1.算法的基本概念

（1）概念：算法是指一系列解決問題的清晰指令。

（2）4個基本特征：可行性、確定性、有窮性、擁有足夠的情報。

（3）兩種基本要素：對數據對象的運算和操作、算法的控制結構（運算和操作時間的順序）。

（4）設計的基本方法：列舉法、歸納法、遞推法、遞歸法、減半遞推技術和回溯法。

2.算法的復雜度

（1）算法的時間復雜度：執行算法所需要的計算工作量。

（2）算法的空間復雜度：執行算法所需的內存空間。

【考點2】數據結構的基本概念

數據結構指相互有關聯的數據元素的集合，即數據的組織形式。其中邏輯結構反映數據元素之間的邏輯關系；存儲結構為數據的邏輯結構在計算機存儲空間中的存放形式，有順序存儲、鏈式存儲、索引存儲和散列存儲4種方式。

數據結構按各元素之間前后件關系的復雜度可劃分為以下兩種。

（1）線性結構：有且只有一個根節點，且每個節點最多有一個直接前驅和一個直接后繼的非空數據結構。

（2）非線性結構：不滿足線性結構的數據結構。

【考點3】線性表及其順序存儲結構

1.線性表的基本概念

線性結構又稱線性表，線性表是最簡單也是最常用的一種數據結構。

2.線性表的順序存儲結構

●元素所占的存儲空間必須連續。

●元素在存儲空間的位置是按邏輯順序存放的。

3.線性表的插入運算

在第i個元素之前插入一個新元素的步驟如下。

步驟一：把原來第n個節點至第i個節點依次往后移一個元素位置。

步驟二：把新節點放在第i個位置上。

步驟三：修正線性表的節點個數。

在最壞情況下，即插入元素在第一個位置，線性表中所有元素均需要移動。

4.線性表的刪除運算

刪除第i個位置的元素的步驟如下。

步驟一：把第i個元素之后不包括第i個元素的n-i個元素依次前移一個位置。

步驟二：修正線性表的節點個數。

【考點4】棧和隊列

1.棧及其基本運算

（1）基本概念：棧是一種特殊的線性表，其插入運算與刪除運算都只在線性表的一端進行，也被稱為“先進后出”表或“后進先出”表。

●棧頂：允許插入與刪除的一端。

●棧底：棧頂的另一端。

●空棧：棧中沒有元素的棧。

（2）特點。

●棧頂元素是最后被插入和最早被刪除的元素。

●棧底元素是最早被插入和最后被刪除的元素。

●棧有記憶作用。

●在順序存儲結構下，棧的插入和刪除運算不需移動表中其他數據元素。

●棧頂指針top動態反映了棧中元素的變化情況。

（3）順序存儲和運算：入棧運算、退棧運算和讀棧頂運算。

2.隊列及其基本運算

（1）基本概念：隊列是指允許在一端進行插入，在另一端進行刪除的線性表，又稱“先進先出”的線性表。

●隊尾：允許插入的一端，用尾指針指向隊尾元素。

●排頭：允許刪除的一端，用頭指針指向頭元素的前一位置。

（2）循環隊列及其運算。

所謂循環隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間。

入隊運算是指在循環隊列的隊尾加入一個新元素。當循環隊列非空（s=1）且隊尾指針等于隊頭指針時，說明循環隊列已滿，不能進行入隊運算，這種情況稱為“上溢”。

退隊運算是指在循環隊列的隊頭位置退出一個元素并賦給指定的變量。首先將隊頭指針進一，然后將排頭指針指向的元素賦給指定的變量。當循環隊列為空（s=0）時，不能進行退隊運算，這種情況稱為“下溢”。

【考點5】線性鏈表

在定義的鏈表中，若只含有一個指針域來存放下一個元素地址，稱這樣的鏈表為單鏈表或線性鏈表。

在鏈式存儲方式中，要求每個節點由兩部分組成：一部分用于存放數據元素值，稱為數據域；另一部分用于存放指針，稱為指針域。其中指針用于指向該節點的前一個或后一個節點（即前件或后件）。

【考點6】樹和二叉樹

1.樹的基本概念

樹是簡單的非線性結構，樹中有且僅有一個沒有前驅的節點稱為“根”，其余節點分成m個互不相交的有限集合T1,T2,…,Tm，每個集合又是一棵樹，稱T1,T2,…,Tmm為根節點的子樹。

●父節點：每一個節點只有一個前件，無前件的節點只有一個，稱為樹的根節點（簡稱樹的根）。

●子節點：每一個節點可以有多個后件，無后件的節點稱為葉子節點。

●樹的度：所有節點最大的度。

●樹的深度：樹的最大層次。

2.二叉樹的定義及其基本性質

（1）二叉樹的定義：二叉樹是一種非線性結構，是有限的節點集合，該集合為空（空二叉樹）或由一個根節點及兩棵互不相交的左右二叉子樹組成。可分為滿二叉樹和完全二叉樹，其中滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。二叉樹具有如下兩個特點。

●二叉樹可為空，空的二叉樹無節點，非空二叉樹有且只有一個根節點。

●每個節點最多可有兩棵子樹，稱為左子樹和右子樹。

（2）二叉樹的基本性質。

性質1：在二叉樹的第k層上至多有2k-1個節點（k≥1）。

性質2：深度為m的二叉樹至多有2m-1個節點。

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

性質4：具有 n個節點的完全二叉樹的深度至少為[log2n]+1，其中[log2n]表示log2n的整數部分。

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

（1）滿二叉樹。滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有節點都有兩個子節點。滿二叉樹在其第i層上有2i-1個節點。

從上面滿二叉樹定義可知，二叉樹的每一層上的節點數必須都達到最大，否則就不是滿二叉樹。深度為m的滿二叉樹有2m-1個節點。

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

一棵具有n個節點的深度為k的二叉樹，它的每一個節點都與深度為k的滿二叉樹中編號為1～n的節點一一對應。

4.二叉樹的存儲結構

二叉樹通常采用鏈式存儲結構，存儲節點由數據域和指針域（左指針域和右指針域）組成。二叉樹的鏈式存儲結構也稱二叉鏈表，對滿二叉樹和完全二叉樹可按層次進行順序存儲。

5.二叉樹的遍歷

二叉樹的遍歷是指不重復地訪問二叉樹中所有節點，主要指非空二叉樹，對于空二叉樹則結束返回。二叉樹的遍歷包括前序遍歷、中序遍歷和后序遍歷。

（1）前序遍歷。

前序遍歷是指在訪問根節點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根節點，然后遍歷左子樹，最后遍歷右子樹。并且，在遍歷左、右子樹時，仍然先訪問根節點，然后遍歷左子樹，最后遍歷右子樹。前序遍歷描述為：若二叉樹為空，則執行空操作；否則①訪問根節點，②前序遍歷左子樹，③前序遍歷右子樹。

（2）中序遍歷。

中序遍歷是指在訪問根節點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根節點，最后遍歷右子樹。并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根節點，最后遍歷右子樹。中序遍歷描述為：若二叉樹為空，則執行空操作；否則①中序遍歷左子樹，②訪問根節點，③中序遍歷右子樹。

（3）后序遍歷。

后序遍歷是指在訪問根節點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根節點。并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根節點。后序遍歷描述為：若二叉樹為空，則執行空操作；否則①后序遍歷左子樹，②后序遍歷右子樹，③訪問根節點。

【考點7】查找技術

（1）順序查找：在線性表中查找指定的元素。

最壞情況下，最后一個元素才是要找的元素，則需要與線性表中所有元素比較，比較次數為n。

（2）二分查找：二分查找也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制，它要求表必須用順序存儲結構，且表中元素必須按關鍵字有序（升序或降序均可）排列。對長度為n的有序線性表，在最壞情況下，二分查找法只需比較log2n次。

【考點8】排序技術

（1）交換類排序法。

●冒泡排序：通過對待排序序列從后向前或從前向后，依次比較相鄰元素的排序碼，若發現逆序則交換，使較大的元素逐漸從前部移向后部或較小的元素逐漸從后部移向前部，直到所有元素有序為止。

在最壞情況下，對長度為n的線性表排序，冒泡排序需要比較的次數為n（n-1）/2。

●快速排序：它是迄今為止所有內排序算法中速度最快的一種。它的基本思想是：任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基準元素的排序碼，然后分別對兩個子序列繼續進行排序，直至整個序列有序。最壞情況下，即每次劃分，只得到一個序列，時間效率為O（n2）。

（2）插入類排序法。

●簡單插入排序法：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素。排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。在最壞情況下，即初始排序序列是逆序的情況下，比較次數為n（n-1）/2，移動次數為n（n-1）/2。

●希爾排序法：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。

（3）選擇類排序法。

●簡單選擇排序法：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面；然后對剩下的子表采用同樣的方法，直到子表空為止。最壞情況下需要比較n（n-1）/2次。

●堆排序的方法：首先將一個無序序列建成堆；然后將堆頂元素（序列中的最大項）與堆中最后一個元素交換（最大項應該在序列的最后）。不考慮已經換到最后的那個元素，只考慮前n-1個元素構成的子序列，將該子序列調整為堆。反復做第二個步驟，直到剩下的子序列空為止。在最壞情況下，堆排序法需要比較的次數為nlog2n。

真題演練

（1）下列敘述中正確的是（　）。

A）算法就是程序

B）設計算法時只需要考慮數據結構的設計

C）設計算法時只需要考慮結果的可靠性

D）以上3種說法都不對

（2）算法的有窮性是指（　）。

A）算法程序的運行時間是有限的

B）算法程序所處理的數據量是有限的

C）算法程序的長度是有限的

D）算法只能被有限的用戶使用

（3）算法的空間復雜度是指（　）。

A）算法在執行過程中所需要的計算機存儲空間

B）算法所處理的數據量

C）算法程序中的語句或指令條數

D）算法在執行過程中所需要的臨時工作單元數

（4）定義無符號整數類為UInt，下面可以作為類UInt實例化值的是（　）。

A）-369

B）369

C）0.369

D）整數集合｛1,2,3,4,5}

（5）下列敘述中正確的是（　）。

A）程序執行的效率與數據的存儲結構密切相關

B）程序執行的效率只取決于程序的控制結構

C）程序執行的效率只取決于所處理的數據量

D）以上說法均錯誤

（6）下列敘述中正確的是（　）。

A）有一個以上根節點的數據結構不一定是非線性結構

B）只有一個根節點的數據結構不一定是線性結構

C）循環鏈表是非線性結構

D）雙向鏈表是非線性結構

（7）下列敘述中正確的是（　）。

A）順序存儲結構的存儲一定是連續的，鏈式存儲結構的存儲空間不一定是連續的

B）順序存儲結構只針對線性結構，鏈式存儲結構只針對非線性結構

C）順序存儲結構能存儲有序表，鏈式存儲結構不能存儲有序表

D）鏈式存儲結構比順序存儲結構節省存儲空間

（8）下列選項中，（）不是一般算法應該有的特征。

A）無窮性

B）可行性

C）確定性

D）有窮性

（9）下列敘述中正確的是（　）。

A）棧是“先進先出”的線性表

B）隊列是“先進后出”的線性表

C）循環隊列是非線性結構

D）有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構

（10）一個棧的初始狀態為空。現將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是（　）。

A）12345ABCDE

B）EDCBA54321

C）ABCDE12345

D）54321EDCBA

（11）下列關于棧的敘述中正確的是（　）。

A）棧按“先進先出”組織數據

B）棧按“先進后出”組織數據

C）只能在棧底插入數據

D）不能刪除數據

（12）下列關于棧的敘述中正確的是（　）。

A）在棧中只能插入數據，不能刪除數據

B）在棧中只能刪除數據，不能插入數據

C）棧是先進后出（FILO）的線性表

D）棧是先進先出（FIFO）的線性表

（13）下列敘述中正確的是（　）。

A）在棧中，棧中元素隨棧底指針與棧頂指針的變化而動態變化

B）在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態變化

C）在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態變化

D）以上說法都不正確

（14）下列關于棧的敘述中正確的是（　）。

A）棧頂元素最先被刪除

B）棧頂元素最后才能被刪除

C）棧底元素永遠不能被刪除

D）棧底元素最先被刪除

（15）下列關于棧的敘述中正確的是（　）。

A）棧底元素一定是最后入棧的元素

B）棧頂元素一定是最先入棧的元素

C）棧操作遵循先進后出的原則

D）以上說法均錯誤

（16）下列與隊列結構有關聯的是（　）。

A）函數的遞歸調用

B）數組元素的引用

C）多重循環的執行

D）先到先服務的作業調度

（17）下列數據結構中，能夠按照“先進后出”原則存取數據的是（　）。

A）循環隊列

B）棧

C）隊列

D）二叉樹

（18）下列數據結構中，屬于非線性結構的是（　）。

A）循環隊列

B）帶鏈隊列

C）二叉樹

D）帶鏈棧

（19）下列關于循環隊列的敘述中正確的是（　）。

A）隊頭指針是固定不變的

B）隊頭指針一定大于隊尾指針

C）隊頭指針一定小于隊尾指針

D）隊頭指針既可以大于隊尾指針，也可以小于隊尾指針

（20）下列敘述中正確的是（　）。

A）循環隊列有隊頭和隊尾兩個指針，因此，循環隊列是非線性結構

B）在循環隊列中，只需要隊頭指針就能反映隊列中元素的動態變化情況

C）在循環隊列中，只需要隊尾指針就能反映隊列中元素的動態變化情況

D）循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定的

（21）下列敘述中正確的是（　）。

A）循環隊列是隊列的一種鏈式存儲結構

B）循環隊列是隊列的一種順序存儲結構

C）循環隊列是非線性結構

D）循環隊列是一種邏輯結構

（22）設循環隊列的存儲空間為Q（1∶35），初始狀態為front=rear=35。現經過一系列入隊與出隊運算后，front=15,rear=15，則循環隊列中的元素個數為（　）。

A）15

B）16

C）20

D）0或35

（23）下列關于線性鏈表的敘述中正確的是（　）。

A）各數據節點的存儲空間可以不連續，但它們的存儲順序與邏輯順序必須一致

B）各數據節點的存儲順序與邏輯順序可以不一致，但它們的存儲空間必須連續

C）進行插入與刪除時，不需要移動表中的元素

D）以上說法均不正確

（24）下列鏈表中，其邏輯結構屬于非線性結構的是（　）。

A）二叉鏈表

C）雙向鏈表

B）循環鏈表

D）帶鏈的棧

（25）支持子程序調用的數據結構是（　）。

A）棧

B）樹

C）隊列

D）二叉樹

（26）某二叉樹有5個度為2的節點，則該二叉樹中的葉子節點數是（　）。

A）10

B）8

C）6

D）4

（27）一棵二叉樹共有25個節點，其中5個是葉子節點，則度為1的節點數為（　）。

A）16

B）10

C）6

D）4

（28）下列關于二叉樹的敘述中正確的是（　）。

A）葉子節點總是比度為2的節點少1個

B）葉子節點總是比度為2的節點多1個

C）葉子節點數是度為2的節點數的兩倍

D）度為2的節點數是度為1的節點數的兩倍

（29）對下列二叉樹：

進行前序遍歷的結果為（　）。

A）DYBEAFCZX

B）YDEBFZXCA

C）ABDYECFXZ

D）ABCDEFXYZ

（30）在長度為n的有序線性表中進行二分查找，最壞情況下需要比較的次數是（　）。

A）n

B）n2

C）log2n

D）nlog2n

（31）對長度為n的線性表排序，在最壞情況下，比較次數不是n（n-1）/2的排序方法是（　）。

A）快速排序

B）冒泡排序

C）直接插入排序

D）堆排序

（32）下列排序方法中，最壞情況下比較次數最少的是（　）。

A）冒泡排序

B）簡單選擇排序

C）直接插入排序

D）堆排序