第一部分棧和佇列
棧是限定在一端進行插入與刪除的線性表,允許插入與刪除的一端稱為棧頂,不允許插入與刪除的一端稱為棧底。形象的來說，比如乙個玻璃杯，棧頂就是杯口可以加水也可以倒水，棧底就是杯底不可以加水也不可以倒水。
棧的儲存：順序儲存，棧按照「先進後出」或「後進先出」組織資料，棧具有記憶作用。用top表示棧頂，bottom表示棧底。
棧的基本運算：
1.入棧運算——插入元素
2.出棧運算——刪除元素
3.讀棧頂元素——將棧頂元素給乙個指定的變數
佇列 是允許在一端(隊尾)進入插入,而在另一端(隊頭)進行刪除的線性表,rear指標指向隊尾,front 指標指向隊頭。
佇列的儲存：佇列按照「先進先出」或「後進後出」組織資料。
佇列的基本運算：1.入隊運算——從隊尾插入乙個元素
2.出隊運算——從隊頭刪除乙個元素
常見題型
1．如果進棧序列為e1,e2,e3,e4,則可能的出棧序列是( )。
d. 任意順序
解析:a答案, e1,e2,e3依次進棧,e3出棧,這時棧頂是e2,不可能為答案中的e1,錯誤
b答案, e1,e2依次進棧, e2出棧, e3,e4依次進棧, 這時棧頂是e4,e4出棧,e3也出棧,最後只剩e1,出棧,所以出棧序列可能是e2,e4,e3,e1
c答案, e1,e2,e3依次進棧,e3出棧,e4進棧再出棧,這時棧頂是e2, 不可能是答案中的e1,錯誤.
d答案,棧中元素要先進後出,不可能任意.
2.棧底至棧頂依次存放元素a,b,c,d,在第五個元素e入棧前，棧中元素可以出棧，則出棧序列可能是（ ）。
a．abcd d. cdab
解析:a答案,abcd依次入棧,棧頂是d,不可能a先出棧,所以錯誤.
b答案,abcd依次入棧,棧頂是d,d出棧,棧頂是c,c出棧...可得,出棧序列dcba.
c答案,abcd依次入棧,棧頂是d,d出棧,棧頂是c,不可能是b出棧,所以錯誤.
d答案,abcd依次入棧,棧頂是d,不可能c先出棧,所以錯誤.
3.乙個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是( )。
解析:c答案的ab不可能,a先進要後出.
4. 乙個佇列的入列序列是1,2,3,4,則佇列的輸出序列是( )。
a.4,3,2,1 b.1,2,3,4 c.1,4,3,2 d.3,2,4,1
解析:佇列的出隊序列和入隊一樣
5. 棧和佇列的共同特點是( ) 。
a.都是先進後出 b.都是先進先出c.只允許在端點處插入和刪除d.沒有共同點
6. 棧是限定在( )處進行插入或刪除操作的線性表。
a. 端點 b.棧底 c.棧頂 d. 中間
7. 棧與一般線性表區別主要在方面 ( ) 。
a. 元素個數 b. 元素型別 c. 邏輯結構 d. 插入、刪除元素的位置
第二部分二叉樹和滿二叉樹、完全二叉樹
1、二叉樹是區分左右子樹的，3個結點的二叉樹有以下5種狀態。
2、二叉樹是由度為1，度為2，度為0的結點（葉子結點）組成的，並且度為0的結點（葉子結點）比度為2的結點多1個。
3、滿二叉樹是深度為k且有個結點的二叉樹。除了最後一層，每一層的結點數都是最大結點數，並且葉子結點的個數為
深度為2，深度為3的滿二叉樹如下圖所示。
4、完全二叉樹是在滿二叉樹的基礎上，去掉右邊的結點。
如深度為3的完全二叉樹可以有
由上圖可以看出，當完全二叉樹結點個數為奇數n時，其葉子結點數為(n+1)/2
當完全二叉樹結點個數為偶數n時，其葉子結點數為n/2
常考題型
1、 在一棵二叉樹上第5層的結點數最多是（ b ）。
a. 8b. 16 c. 32 d. 15
2、設一棵完全二叉樹共有699個結點，則在該二叉樹中的葉子結點數為( b )。
a. 349 b. 350 c. 255 d. 351
3、在深度為5的滿二叉樹中，葉子結點的個數為（ c )
a. 32 b. 31 c. 16 d. 15
4、某二叉樹共有7個結點，其中葉子結點只有1個，則二叉樹的深度為( d
) (假設根結點在第1層)(2023年3月真題)
a. 3 b. 4 c. 6d. 7
5、一棵二叉樹有10個度為1的結點，7個度為2的結點，則該二叉樹共有______個結點(2023年9月真題)
6、某二叉樹中度為2的結點有18個，則該二叉樹中有______個葉子結點。
第三部分關係代數
1．傳統的關係運算：並、交、差
2．專門的關係運算：選擇、投影、連線
並（∪） 兩個相同結構的關係的並是由屬於兩個關係的元組組成集合。
交（∩）兩個相同結構的關係r、s，它們的交是由即屬於r又屬於s的元組組成的集合。
差（-）兩個相同結構的關係r、s，它們的差是由屬於r但不屬於s的元組組成的集合。
選擇 (σ) 關係r中，找出其中的一行或幾行。
投影 (π) 關係r中，找出其中的一列或幾列。
練習：1.設有如下關係表：
則下列操作正確的是（ ）
2.有兩個關係r，s如下
由關係r通過運算得到關係s，則使用的運算為（ ）。
a.選擇 b.投影 c.插入 d.連線
3.有三個關係r、s和t如下：
由關係r和s通過運算得到關係t，則所使用的運算為（ ）。
a.並 b.自然連線 c.笛卡爾積 d.交
4.有兩個關係r，s如下
由關係r通過運算得到關係s，則使用的運算為（ ）。
a. 插入 b.投影 c.選擇 d.連線
3.除( / ) 關係r與s,r中包含s的全部屬性，r中有些屬性不出現在s中，則r/s由不含s的某些屬性組成。
有三個關係r、s和t如下：
則由關係r和s得到關係t的操作是
a)自然連線 b)交 c)除 d)並
4.笛卡爾積( × ) 兩個不同結構的關係r,s,它們的笛卡爾積的行的個數為r的行數與s的行數相乘，列的個數為r的列數與s的列數相加。
r×s5.連線：兩個關係結構不同，按某一條件連線起來。
t d>e
m d=e
6.自然連線兩個關係結構不同，但有相同屬性，通過相同屬性等值連線。
t=r|×s|
全國計算機等級考試二級公共基礎知識
第1章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...
2019全國計算機等級考試二級公共基礎知識 考試大綱
一 資料結構與演算法 一 基本概念 資料 data 資訊的載體，能夠被計算機識別 儲存和加工處理的物理符號。包括文字型別的資料 如 字母 數字 漢字 和多 型別的資料 如 聲音 動畫 影象 資料元素 data element 是資料的基本單位，有時也稱為元素 結點 頂點 記錄，可以有若干個資料項 字...
全國計算機等級考試二級公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 1 演算法的基本特徵 可行性 確定性，有窮性 擁有足夠的情報。2 確定性 演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性 3 演算法基本設計方法 列舉法 歸納法 遞推 遞迴 減鬥遞推技術 回溯法。4 通過觀察一些簡單而特殊的情況，最後...