數據結構與算法
算法---是壹組嚴謹地定義運算順序的規則
算法的基本要素---壹是對數據對象的運算和操作，二是算法的控制結構
算法設計基本方法---列舉法、歸納法、遞推、遞歸、減半遞推
算法的復雜度---包括時間復雜度和空間復雜度
時間復雜度---執行算法所需的計算工作量
空間復雜度---執行算法所需的內存空間
數據結構---相互有關聯的數據元素的集合。如春、夏、秋、冬；18、11、35、23、16。。。；父親、兒子、女兒等都是數據元素。
前件---數據元素之間的關系，如父親是兒子和女兒的前件
後件---如兒子是父親的後件
結構---指數據元素之間的前後件關系
數據的邏輯結構—是指反映數據元素之間邏輯關系，而與它們在計算機中的存儲位置無關
數據的存儲結構（物理結構）---數據的邏輯結構在計算機存儲空間中的存放形式，數據元素在計算機存儲空間的位置關系可能與邏輯關系不同。
根據數據結構中各數據元素之間前後件關系的復雜程度，可將數據結構分兩類---線性結構與非線性結構
線性結構（線性表）---滿足下列兩個條件（1）有且只有壹個根結點（2）每壹個結點最多有壹個前件和後件。則稱該數據結構為線性結構，否則為非線性結構。
線性表是最簡單、最常用的壹種數據結構，其數據元素之間的相對位置是線性的，其存儲方式為順序存儲的，如數組
棧---是限定在壹端進行插入與刪除的線性表，壹端封閉，另壹端開口，其操作原則是“先進後出”，棧的運算有入棧、退棧、讀棧頂元素
隊列---是指在壹端進行插入（稱為隊尾）而在另壹端進行刪除（稱為隊頭）的線性表，其操作規則是“先進先出”，其運算有入隊和退隊。
樹---是壹種簡單的非線性結構，而且是層次結構，是倒立的大樹，有根結點、父結點、子結點、葉子結點。根結點在第壹層，壹個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為 樹的度，樹的最大層次稱為樹的深度。
二叉樹---（1）非空二叉樹只有壹個根結點（2）每壹個結點最多有兩棵子樹（左子樹和右子樹），其存儲結構為鏈式。
二叉樹性質---（1）K層上最多有2（K-1）個結點（2）深度為m的二叉樹最多有2m-1個結點
（3）度為0的結點（葉子結點）比度為2的結點多壹個（4）具有n個結點的二叉樹，其深度至少為[Log2n]+1，其中[Log2n]表示對Log2n取整
滿二叉樹---除最後壹層外，其余層的結點都有兩個子結點
完全二叉樹---除最後壹層外，每壹層上的結點數均達到最大值，在最後壹層上只缺少右邊的若幹結點，葉子結點只可能在層次最大的兩層上出現。滿二叉樹是完全二叉樹，而完全二叉樹不是滿二叉樹。完全二叉樹有兩個性質：（1）具有n個結點的完全二叉樹的深度為[Log2n]+1（2）
二叉樹遍歷---不重復地訪問各個結點。分為前序遍歷(DLR-根左右)、中序遍歷(LDR-左根右)和後序遍歷（LRD-左右根）
查找技術---順序查找——對於長度為n的有序線性表，查找時需要比較n次
二分法查找——對於長度為n的有序線性表，查找時需要比較log2n次
排序技術---假設線性表的長度為n，則冒泡排序和簡單插入排序的比較次數（時間復雜度）為n(n-1)/2;希爾排序的比較次數為O(n1.5);簡單選擇排序的比較次數為n(n-1)/2;堆排序的比較次數為O(nlog2n).
習題1
算法的時間復雜度是指（ ），算法的空間復雜度是指（ ）；
線性表、棧、隊列、線性鏈表是（線性結構），樹是（非線性結構）；數據的存儲結構是指（ ）；
隊列是（先進先出），棧是（先進後出）；
下列二叉樹的遍歷結果：前序遍歷（ABDECF）、中序遍歷（DBEAFC）、後續遍歷（DEBFCA）
在深度為5的滿二叉樹中，葉子結點的個數為（16）；設樹T的度為4，其中度為1，2，3，4的結點的個數分別為4，2，1，1。則T中的葉子結點的個數為（8）；對於長度為n的有序線性表，順序查找次數為（n）,二分法查找次數為（log2n）；壹棵完全二叉樹***有700個結點，則在該二叉樹中有（350）個葉子結點；壹棵二叉樹的中序遍歷結果為DBEAFC，前序遍歷結果為ABDECF，則後續遍歷結果為（DEBFCA）；冒泡排序的時間復雜度為（n(n-1)/2）;在壹個容量為15的循環隊列中，若頭指針front=6,尾指針rear=9,則該循環隊列中***有（3）元素；
程序設計基礎
結構化程序設計的三種結構---是順序、選擇和循環
對象---表示客觀世界的任何實體
類---是具有***同屬性和方法的對象的集合
實例---任何壹個對象都是其對應類的實例
消息---壹個實例和另壹個實例之間傳遞的信息
繼承---是指直接獲得已有的性質和特征，而不必重復定義它們。例如子類繼承父類
結構化程序設計主要強調---程序的易讀性
良好的程序設計風格是---程序應簡單、清晰、可讀性好
在面向對象方法中，壹個對象請求另壹個對象為其服務的方式是通過發送（消息）來實現的
信息隱蔽的概念與（模塊獨立性）概念直接相關
（任何對象都具有繼承性）這句話是錯誤的
註釋分為（序言性註釋）和（功能性註釋）
在面向對象方法中，信息隱蔽是通過對象的（封裝性）來實現的
類是壹個支持集成的抽象數據類型，而對象是類的（實例）
在面向對象方法中，類之間***享屬性和操作的機制稱為（繼承）
第三章 軟件工程基礎
軟件生命周期---軟件產品從提出、實現、使用維護到停止使用退役的過程。分為軟件定義、軟件開發、軟件運行維護三個階段。
軟件生命周期的主要活動階段---可行性分析、需求分析、軟件設計、軟件實現、軟件測試、運行和維護。
常見的需求分析方法---（1）結構化分析方法---主要包括面向數據流的結構化分析方法SA；面向數據結構的Jackson方法JSD；面向數據結構的結構化數據系統開發方法DSSD。
（2）面向對象的分析方法OOA
結構化分析方法工具---（1）數據流圖DFD，記住DFD圖的幾個符號：
（2）數據字典DD
（3）判定樹
（4）判定表
程序結構圖（SC），N-S圖，問題分析圖（PAD）
程序流程圖（PFD）的幾個符號：
軟件測試---黑盒測試：功能測試
白盒測試：內部結構測試，窮舉路徑測試
習題3
在軟件生命周期中，能準確地判斷軟件系統必須做什麽和必須具備哪些功能的階段是（需求分析）
軟件工程的3個要素（工具），（過程），（方法）
檢查軟件產品是否符合需求定義的過程稱為（確認測試）
軟件設計原則是（抽象）、（模塊化）、（信息隱蔽）
需求分析常用的工具是（DFD）
在結構化方法中，軟件功能分解屬於（總體設計）階段
軟件測試的餓目的是（改正錯誤 ）
軟件需求分析 階段 可分為四個方面（需求獲取）、（需求分析）、（編寫需求格式說明）、（需求評審）
軟件是（程序）、（數據）、（文檔）的集合
Jakson方法是壹中面向（數據流）的結構化方法
軟件工程研究的內容包括（軟件開發技術）、（軟件工程管理）
數據流圖的類型有（交換型）、（事務型）
軟件開發環境是全面支持軟件開發全過程的（軟件工具）集合
第四章 數據庫設計基礎
數據庫---DB；數據庫管理系統---DBMS；數據庫管理員---DBA；數據庫系統---DBS；數據庫應用系統---DBAS
數據模型所描述的內容分三個部分（數據結構）、（數據操作）、（數據約束）
邏輯數據模型分（層次模型）、（網狀模型）、（關系模型）、（面向對象模型）
E-R模型---實體關系模型，主要由實體、屬性、聯系組成，聯系分：1對1，1對多，多對多；
以二維表為基本結構所建立的模型稱為關系模型，關系模型采用二維表來表示，簡稱表，由行和列組成，行稱為元組或記錄，列稱為字段
主鍵---唯壹標識壹個記錄的字段
外鍵---壹個表的字段是其他表的主鍵
在數據管理技術的發展過程中，經歷了人工管理階段、文件系統階段、數據庫系統階段，其中數據獨立性最高的階段是（數據庫系統）
數據庫系統減少了（數據冗余）；數據庫系統的核心是（數據庫管理系統）
用樹型結構來表示實體間聯系的模型稱為（層次模型）
關系表中的每壹行稱為（元組）
關系數據庫管理系統能實現的專門關系運算包括（選擇）、（投影）、（連接）
在關系數據庫中，用來表示實體之間聯系的是（二維表）
數據庫設計包括兩方面的設計內容（概念設計）、（邏輯設計）
將E-R圖轉換到關系模式時，實體與聯系都可以表示成（關系）
壹個項目具有壹個項目主管，壹個項目主管可以管理多個項目，則實體“項目主管”與“項目”的聯系屬於（壹對多）
數據獨立性分為邏輯獨立性和物理獨立性，當數據的存儲結構改變時，其邏輯結構可以不變，因此，基於邏輯結構的應用程序不必修改，稱為（邏輯獨立性）
數據庫系統中實現各種數據管理功能的核心軟件稱為（數據庫管理系統DBMS）
關系模型的完整性規則是對關系的某種約束條件，包括實體完整性、（參照完整性）和自定義完整性
下面是公***基礎部分可以變化的題:
1 壹棵二叉樹,第K層上最多有2(k-1)個結點,深度為K的二叉樹最多有2k-1個結點,如果是滿二叉樹呢?
例如: 在深度為5的滿二叉樹中，葉子結點的個數為（=2(5-1)=16）
2壹棵二叉樹***有70個葉子結點和80個度為1的結點,問這個二叉樹的總結點是多少?
答:因為度為0的結點（葉子結點）比度為2的結點多壹個,所以度為2的結點數是69,所以總結點=70+69+80=219個
3壹棵完全二叉樹***有700個結點，則在該二叉樹中有（350）個葉子結點
解答:700/2=350
若把700改為675呢?(=675/2=337.5進行四舍五入=338)
4設樹T的度為4，其中度為1，2，3，4的結點的個數分別為4，2，1，1。則T中的葉子結點的個數為（8）
解答:n0=(t-1)nt+(t-2)n(t-1)+...+1*n2+0*n1+1=3*1+2*1+1*2+0*4+1=8
5在壹個容量為15的循環隊列中，若頭指針front=6,尾指針rear=9,則該循環隊列中***有多少個元素?(3個)
解答:若頭<尾,元素個數=尾-頭
:若頭>尾,元素個數=15+(尾-頭)
6 設有
則R和S能進行交集（RnS）、並集（RuS）、差操作（R-S）
如果R和S的元不同的 話，則R和S只能進行笛卡爾集（RXS）和自然連接
7 關於二叉樹遍歷問題：有兩個題型，壹是給出二叉樹，求三種遍歷結果；二是給出兩種遍歷，求第三種遍歷結果。後者有點難度
三種遍歷是：前序（根左右）、中序（左根右）和後序（左右根）
8 關於查找和排序問題：
查找技術---順序查找——對於長度為n的有序線性表，查找時需要比較n次
二分法查找——對於長度為n的有序線性表，查找時需要比較log2n次
排序技術---假設線性表的長度為n，則冒泡排序和簡單插入排序的比較次數（時間復雜度）為n(n-1)/2;希爾排序的比較次數為O(n1.5);簡單選擇排序的比較次數為n(n-1)/2;堆排序的比較次數為O(nlog2n).
9 關於出棧的問題：記住是先進後出
例1：棧底到頂依次存放A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧可能的序列是
ABCED DCBEA DBCEA CDABE
例2：如果進棧序列為e1,e2,e3,e4，則可能的出棧序列為：
e3,e1,e4,e2 e2,e4,e3,e1 e3,e4,e1,e2 任意順序
10 關於E---R圖
是實體屬性和實體關系圖，實體之間的關系有1：1 1：m m:n
第二部分 全國計算機等級考試
二級公***考試訓練
模擬試題壹
壹 選擇題（每小題2分）
在下列各題的A），B），C），D），4個選項中，只有1個選項是正確選項
1．棧和隊列的***同特點是（ C ）。
A）都是先進先出 B）都是先進後出
C）只允許在端點處插入和刪除元素 C）沒有***同點
2．已知二叉樹後序編歷序列是dabec，中續遍歷序列是debac，它的前序編歷序列是（ D ）。
A）acbed B）decab C）deabc D）cebda3
3．鏈表不具有的特點是（ B ）。
A）不必事先估計存儲空間 B）可隨機訪問任壹元素
C）插入刪除不需要的移動元素 D）所需空間與線性長度
4．結構化程序設計的3種結構是（ D ）。
A）順序結構、選擇結構、轉移結構 B）分支結構、等價結構、循環結構
C）多分支結構、賦值機構、等價結構 D）順序結構、選擇結構、循環結構
5．為了提高測試的效率。應該（ D ）
A）隨即選取測試數據 B）取壹切可能的輸入數據作為測試數據
C）在完成編碼以後指定軟件的測試次數 D）集中對付那些錯誤的群集的程序
6．算法的時間復雜度是指（ C ）
A）執行算法程序所需要的時間 B）算法程序的長度
C）在完成編碼以後指定軟件的測試次數 D）算法程序中的指定條數
7．軟件生命周期中花費用最多的階段是（ D ）
A）詳細設計 B）軟件編碼 C）軟件測試 D）軟件維護
8．數據庫管理系統DBMS中用來定義模擬、內模式和外模式的語言為（ C ）
A）C B）Basic C)DDL D)DML
9．下列有關數據庫的描述，正確的是（ C ）
A）數據庫是壹個DBF文件 B）數據庫是壹個關系
C）數據庫是壹個結構化的數據集合 D）數據庫是壹組文件
10．下列有關數據庫的描述，正確的是（ D ）
A）數據處理是將信息轉化為數據的過程
B）數據的物理獨立性是指當數據的邏輯結構改變時，數據的存儲結構不變
C）關系中的 每壹列稱為元組，壹個元組就是壹個字節
D）如果壹個關系中的屬性或屬性組並非該關系的關鍵字，但它是另壹個關系的
鍵字，則稱其為本關系的外關鍵字
二、填空題（每空2分）
請將每壹個空的正確答案寫在答題卡11~15序號的橫線上，答案試卷上不得分。
算法的基本特征是可行性、確定性、有窮性。
在長度為n的有序線性表中進行二分查找。最壞的情況下，需要的比較次數為log2n 。
在面向對象的程序設計中。類描述的是具有相似性質的壹組對象 。
通常，將軟件產品從提出、實現、使用維護到停止使用退役的過程稱為軟件生命周期。
數據庫管理系統常見的數據模型有層次模型、網狀模型和關系模型3種。
模擬測試二
壹.選擇題(每小題2分)
在下列各題的A),B),C),D),4個選項中,只有1個選項是正確的,
1.已知壹棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF,則該二叉樹的後序遍歷為( B )
A)GEDHFBCA B)DGEBHFCA C)ABCDEFGH D)ACBFEDHG
2.樹是結點的集合,它的根結點的數目是( A )
A)有且只有1個 B)1或多於1 C)0或1 D)至少2
3.如果進棧序列為e1,e2,e3,e4,則可能的出棧序列是( B )
A)e3,e1,e4,e2 B)e2,e4,e3,e1 C)e3,e4,e1,e2 D )任意順序
4.在設計程序時,應采納的原則之壹是( D )
A)不限制goto語句的使用 B)減少或取消註解行
C)程序越短越好 D)程序結構應有助於讀者理解
5