1、學習必備歡迎下載第一章：概述1、程序 =算法 + 數據結構2、算法的幾個基本特征：能行性確定性有窮性擁有足夠的情報3、算法的復雜度主要包括：時間復雜度和空間復雜度第二章：數據結構1、邏輯結構：數據集合中各數據元素之間所固有的邏輯關系（集合結構、線性結構、樹形結構、圖狀結構），可以看作是從具體問題抽象出來的數據模型。2、物理（存儲）結構：在對數據進行處理時，各數據元素在計算機中的存儲關系，可分為以下四種：順序存儲結構（存儲空間連續）、鏈式存儲結構、索引結構、散列結構3、數據結構的運算是指對數據結構中的結點進行操作的集合，包括插入、刪除、更新、檢索、排序等。4、數據元素是數據的基本單位5、有時數據

2、元素可由若干個數據項（數據的屬性）組成，在這種情況下，數據項組成的數據元素稱為記錄，數據項是具有獨立含義的最小標識單位，不可分割6、順序存儲結構：通常定義一維數組來表示線性表的順序存儲空間7、順序表的插入異常處理：（ m 為線性表的空間大小，n 為線性表的長度 n 時，認為在最后一個元素之后（即第n+1 個元素之前）插入；當 i1 時，認為在第1 個元素之前插入函數的代碼實現：void insert （int *v,int m,int n,int i, int b） int k; 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁，共 16 頁

3、- - - - - - - - -學習必備歡迎下載if(n=m) cout” 出現上溢錯誤 !” n) i=n+1; if(i=i;k-) vk=vk-1; vi-1=b; n=n+1; 8、順序表的刪除異常處理：當線性表為空（即n=0 ）時為下溢錯誤，不能進行刪除，算法結束；當 in 時，認為不存在該元素，不進行刪除。函數的代碼實現：void delete(int *v, int m,int n, int i) int k; if(n=0) cout” 出現下溢錯誤！ ” endl; if(in) cout” 線性表里不存在該元素，不進行刪除操作！” endl; for(k=i;knumbe

4、r=b; if(head=null) head=p; p-next=null; if(head-number=x) p-next=head; head=p; q=head; while(q-next!=null)&(q-next)-number)!=x) q=q-next; p-next=q-next; q-next=p; 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載 13、單鏈表的刪除函數實現刪除包換元素x 的結點void delete(int x) node *p

5、,*q; if(head=null) cout” 沒有要刪除的元素！” number)=x) p=head-next; delete head; head=p; q= head; while(q-next)!=null)&(q-next)-number)!=x) q=q-next; if(q-next=null) cout” 沒有要刪除的元素！” next; q-next=p-next; delete p; 14、循環鏈表的插入函數實現在包含元素x 的結點前插入新元素b void insert(int x,int b) node *p,*q; p=new code; p-number=

6、b; 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載q=head; while(q-next!=null)&(q-next)-numbe)r!=x) q=q-next; p-next=q-next; q-next=p; 15、循環鏈表的刪除函數實現刪除包含元素x 的結點void delete(int x) node *p,*q; q=head; while(q-next!=null)&(q-next)-number)!=x) q=q-next; if(q-nex

7、t=head) cout” 沒有要刪除的元素” next; q-next=p-next; delete p; 16、單鏈表與循環鏈表的區別單鏈表的頭指針指向線性表第一個元素的結點；而循環鏈表的頭指針指向表頭結點，表頭結點的指針域指向鏈表的第一個結點。單鏈表的最后結點的指針域為空；而循環鏈表最后結點的指針域指向表頭結點. 17、下三角矩陣的壓縮存儲（以行為主壓縮）（以列為主壓縮）精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載18、對稱矩陣的壓縮19、索引存儲的方式順序 索引順序、

8、順序 索引 鏈接、鏈接 索引順序、鏈接 索引鏈接20、二叉樹的性質在二叉樹的第k 層上，最多有2k1(k 1) 個結點深度為 m 的二叉樹最多有2m1 個結點（深度即為層數）在任意一棵二叉樹中，度為0 的結點（即葉子結點）總是比度為2 的結點多一個具有 n 個結點的二叉樹，其深度至少為log2n 1，其中 log2n表示取 log2n 的整數部分21、滿二叉樹是指每層的結點都有兩個子結點，滿的不行不行的了，完全二叉數是指最后一層必須是從左至右的順序斷了線的，其余層都是滿的。22、前序遍歷、中序遍歷、后續遍歷（前中后對應的是根結點的訪問順序）前序遍歷：先根結點，再左再右中序遍歷：先左，再根結點，

9、再右后續遍歷：先左，再右，再根結點23、若給出三種遍歷中的任意兩種遍歷，要求寫出第三種遍歷，思路如下：先正確畫出對應的二叉樹，根據已給條件進行驗證，最后寫出第三種遍歷24、三種遍歷的程序實現前序遍歷void qian_ma() node *p; p=bt; pre(p); 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載coutendl; static qian(node *p) if(p!=null) coutnumberlchild); qian(p-rchild); 中序遍

10、歷void zhong_ma() node *p; p=bt; zhong(p); coutlchild); coutnumberrchild); 后續遍歷精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載void hou_ma() node *p; p=bt; hou(p); coutlchild); hou(p-rchild); coutnumber” ; 25、有序樹轉二叉樹最最簡便的方法對于有序樹中的每一個結點，保留與其第一個子結點（即最左邊的子結點）的鏈接，斷開與其他子結

11、點的鏈接，且將其他子結點依次鏈接在第一個子結點的右邊。26、private 后邊的叫數據成員（私有變量），public 后邊的叫成員函數，其中函數名與類名完全相同，并且無返回值（void 也不能加）的叫構造函數，這個知識點老師說占 4 分的分值，而且老師還說一打眼就可以看出答案來的，方法我都告訴小超了呢。第三章：查找與排序1、無序表只能用順序查找，有序表可用對分查找，分塊查找時，各子表的長度可以相等，也可以互相不等，但要求后一個子表中的每一個元素均大于前一個子表中的所有元素。2、查找效率比較：順序查找 分塊查找 對分查找 哈希表查找3、有序表的插入函數void insert （int *v,i

12、nt m,int n, int x）精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載 int k; if(n=m) cout” 出現上溢錯誤 !” x) vk+1=vk; k=k-1; vk+1=x; n=n+1; 4、有序表的刪除函數void delete(int *v, int m,int n, int i) int k; if(n=0) cout” 出現下溢錯誤！ ” endl; if(in) cout” 線性表里不存在該元素，不進行刪除操作！” endl; for(k=i

13、;k=n;k+) vk-1=vk; n=n-1; 5、有序表的對分查找函數int search （int x,int n ） int i,j,k; i=1; j=n; 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 9 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載while(i=j) k=(i+j)/2; if(vk-1=x) coutx) j=k-1; else i=k-1; return(-1); 6、冒泡排序的原理以及程序實現原理：相鄰兩個元素比較大小，要是大，往后移，要是小，不要動，這樣每進行一次就可以把最大的那個移到

14、末尾了程序實現：void maopao(int *s,int n) int i,j; int temp; for(i=1;in;i+) for(j=0;jsj+1) temp=sj; sj=sj+1; sj+1=temp; 7、快速排序的原理以及程序實現精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 10 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載原理：我明白快速排序了，在考試的時候，老師已經明確說了將第一個元素作為關鍵字，所以這樣的話，將第一個元素設為p（k），并將 p（k）的值賦給t，然后設置兩個指針 i 和 j 分別指

15、向表的起始與最后的位置。反復作以下兩步：將 j 逐漸減小，并逐次比較p（j）與 t，直到發現一個p（j）t 為止，將 p（i）移到 p（j）的位置上。上述兩個操作交替進行，直到指針i 與 j 指向同一個位置（即i=j ）為止，此時將t 移到 p（i）（即 p（j）的位置上。程序實現：void quick （int *p,int n） int m,i; int *s; i=split(p,n); quick(p,i); s=p+ （i+1 ）；m=n-(i+1); quick(s,m); static int spilt(int *p,int n) int i,j,k,l; int t; i=0

16、; j=n-1; t=p0; while(i!=j) while(i=t) 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 11 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載j=j-1; if(ij) pi=pj;i=i+1; while(ij)&(pi=t) i=i+1; if(ij) pj=pi;j=j-1; pi=t; return(i); 8、簡單插入排序的原理及程序實現原理：就是從第二個元素開始，往前插到它應該在的位置就好啦，還是蠻實用的嘛程序實現：void insert(int *p,int n) int

17、j,k; int t; for(j=1;j=0)&(pkt) pk+1=pk;k=k-1; pk+1=t; 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 12 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載9、希爾排序的原理以及程序實現原理：每間隔一定數量的元素之間進行比較和互換，慢慢減小這個間隔，直到間隔為1 時，進行一次插入排序就搞定了。程序實現：void shel(int *p,int n) int k,j,i; int t; k=n/2; while(k0) for(j=k;j=0)&(pit) pi+

18、k=pi;i=i-k; pi+k=t; k=k/2; 10、簡單選擇排序的原理以及程序實現原理：對于長度為n 的序列，需要掃描n-1 遍，每一遍掃描均從剩下的子表中選出最小的元素，然后將該最小的元素與剩余子表的第一個元素進行互換。程序實現：void select(int *p,int n) int i,j,k; int d; for(i=0;in-1;i+) 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 13 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載 k=i; for(j=i+1;jn;j+) if(pipk) k=j;

19、 if(k!=j) d=pi;pi=pk;pk=d; 11、堆排序的原理以及程序實現這個有點復雜，你只需要記住兩句話就可以啦，一是堆一定是完全二叉樹，二是堆中所有根結點一定是大于其對應的葉子結點的。12、二叉排序樹的概念及特性概念：左子樹上所有結點的值均小于根結點的值；右子樹上所有結點的值均不小于根結點的值。特征：中序遍歷二叉排序樹即可得到有序數列。13、給定序列構造二叉排序樹第 1 個你就放在根結點就可以啦，然后放第二個的時候你就看如果是大于根結點的話放在右子樹，如果是小于根結點的話就放左子樹，整體如此，局部也是一樣，最后還要檢查一下哦，按照一定的順序檢查，還是很好玩的呢。14、二叉排序樹的

20、查找方法：給你一個數，怎么在二叉排序樹中找到它呢？從上往下比較唄，真的很神奇呢，啦啦啦第四章：資源管理技術1、多道程序設計：在一臺處理機上并發運行多個程序2、相對地址（邏輯地址）與絕對地址概念相對地址：編寫程序時使用的地址絕對地址：即為物理地址，數據存儲在計算機中的地址3、虛擬存儲的意義：擴大邏輯內存第五章：數據庫精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 14 頁，共 16 頁 - - - - - - - - -學習必備歡迎下載溫馨提示：該部分因為考點較為明確，所以不按照知識點進行劃分，而是按照考題類型進行整理。本章考題占20 分，分為兩個題型

21、，對表的操作、對表中數據的操作。一、對表的操作例：創建學生基本信息表（學號，姓名，年齡，所在系），學號為字符類型，8 個字符長，學號為該表關鍵字；姓名為字符類型，10 個字符長；年齡為整型，可以不輸入值；所在系為字符型，12 個字符長，允許不輸入值creame table s( sno char(8) primary key, sname char(10) not null, age int, depart char(12) ); 例：學生信息表s 沒有記錄學生性別，修改表結構，增加“性別”列sex，此列為字符型，長度為2 alter table s add sex char(2) 例：將學生表s 姓名 sname 列字符長度修改為20 alter table s modify (sname char(20)；例：刪除 s 表drop table s 二、對表中數據的操作有如下表employee(emp_id, name, dept, salary, skill) 雇員（雇員編號，姓名，所屬部門，工資，技能）雇員編號為關鍵字，寫出滿足下面要求的sql語句：1）查詢全部雇員所屬部門的信息；select dept from employee; 2）查詢工資在2000-3000 范圍內雇