(完整)計算機軟件技術(shù)基礎(chǔ)知識點儲備,推薦文檔

1、第一章：概述1、程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu)2、算法的幾個基本特征：能行性確定性有窮性擁有足夠的情報3、算法的復(fù)雜度主要包括：時間復(fù)雜度和空間復(fù)雜度第二章：數(shù)據(jù)結(jié)構(gòu)1、邏輯結(jié)構(gòu)：數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系（集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)），可以看作是從具體問題抽象出來的數(shù)據(jù)模型。2、物理（存儲）結(jié)構(gòu)：在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，可分為以下四種：順序存儲結(jié)構(gòu)（存儲空間連續(xù)）、鏈?zhǔn)酱鎯Y(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)3、數(shù)據(jù)結(jié)構(gòu)的運算是指對數(shù)據(jù)結(jié)構(gòu)中的結(jié)點進(jìn)行操作的集合，包括插入、刪除、更新、檢索、排序等。4、數(shù)據(jù)元素是數(shù)據(jù)的基本單位5、有時數(shù)據(jù)元素可由若干個

2、數(shù)據(jù)項（數(shù)據(jù)的屬性）組成，在這種情況下，數(shù)據(jù)項組成的數(shù)據(jù)元素稱為記錄，數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位，不可分割6、順序存儲結(jié)構(gòu)：通常定義一維數(shù)組來表示線性表的順序存儲空間7、順序表的插入異常處理：（ m 為線性表的空間大小， n 為線性表的長度 <=m ，插入的位置為i， i 表示在第 i 個元素之前插入）當(dāng)存儲空間已滿（即 n=m ）時為上溢錯誤，不能進(jìn)行插入，算法結(jié)束；當(dāng) i>n時，認(rèn)為在最后一個元素之后（即第n+1 個元素之前）插入；當(dāng) i<1時，認(rèn)為在第 1 個元素之前插入函數(shù)的代碼實現(xiàn)：void insert （int *v,int m,int n,int i,

3、 int b）int k;if(n=m) cout<<”出現(xiàn)上溢錯誤 !”<<endl;if(i>n)i=n+1;if(i<1) i=1;for(k=n;k>=i;k-)vk=vk-1;vi-1=b;n=n+1;8、順序表的刪除異常處理：當(dāng)線性表為空（即n=0 ）時為下溢錯誤，不能進(jìn)行刪除，算法結(jié)束；當(dāng) i<1 或 i>n 時，認(rèn)為不存在該元素，不進(jìn)行刪除。函數(shù)的代碼實現(xiàn)：void delete(int *v, int m,int n, int i)int k;if(n=0)cout<<”出現(xiàn)下溢錯誤！ ”<<end

4、l;if(i<1)|(i>n)cout<<”線性表里不存在該元素，不進(jìn)行刪除操作！”<<endl;for(k=i;k<=n;k+)vk-1=vk;n=n-1;9、棧（相當(dāng)于一個井）的相關(guān)概念先進(jìn)后出（后進(jìn)先出）棧頂允許插入與刪除棧底不允許插入與刪除10 、隊列（相對于排隊買飯）的相關(guān)概念 先進(jìn)先出 隊尾允許插入對頭允許刪除11 、鏈?zhǔn)酱鎯γ總€結(jié)點由兩部分組成：數(shù)據(jù)域和指針域12 、單鏈表的插入函數(shù)實現(xiàn)在包含元素x 的結(jié)點前插入新元素bvoid insert(int x,int b)node *p,*q;p=new node;p->number=b

5、;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;13 、單鏈表的刪除函數(shù)實現(xiàn)刪除包換元素x 的結(jié)點void delete(int x)node *p,*q;if(head=NULL) cout<<”沒有要刪除的元素！”<<endl

6、;if(head->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<<”沒有要刪除的元素！”<<endl;p=q->next;q->next=p->next;delete p;14 、循環(huán)鏈表的插入函數(shù)實現(xiàn)在包含元素x 的結(jié)點前插入新元素bvoid insert(int x,int b)nod

7、e *p,*q;p=new code;p->number=b;q=head;while(q->next!=NULL)&&(q->next)->numbe)r!=x)q=q->next;p->next=q->next;q->next=p;15 、循環(huán)鏈表的刪除函數(shù)實現(xiàn)刪除包含元素x 的結(jié)點void delete(int x)node *p,*q;q=head;while(q->next!=NULL)&&(q->next)->number)!=x)q=q->next;if(q->next=

8、head) cout<<”沒有要刪除的元素”<<endl;p=q->next;q->next=p->next;delete p;16 、單鏈表與循環(huán)鏈表的區(qū)別單鏈表的頭指針指向線性表第一個元素的結(jié)點；而循環(huán)鏈表的頭指針指向表頭結(jié)點，表頭結(jié)點的指針域指向鏈表的第一個結(jié)點。單鏈表的最后結(jié)點的指針域為空；而循環(huán)鏈表最后結(jié)點的指針域指向表頭結(jié)點.17 、下三角矩陣的壓縮存儲（以行為主壓縮）（以列為主壓縮）18 、對稱矩陣的壓縮19 、索引存儲的方式順序 索引 順序、順序 索引 鏈接、鏈接 索引 順序、鏈接 索引 鏈接20 、二叉樹的性質(zhì)在二叉樹的第k 層上，最

9、多有2k1 (k 1)個結(jié)點深度為m 的二叉樹最多有2m 1個結(jié)點（深度即為層數(shù)）在任意一棵二叉樹中，度為0 的結(jié)點（即葉子結(jié)點）總是比度為2 的結(jié)點多一個具有 n 個結(jié)點的二叉樹，其深度至少為log 2n 1，其中 log 2 n 表示取 log2 n 的整數(shù)部分21 、滿二叉樹是指每層的結(jié)點都有兩個子結(jié)點，滿的不行不行的了，完全二叉數(shù)是指最后一層必須是從左至右的順序斷了線的，其余層都是滿的。22 、前序遍歷、中序遍歷、后續(xù)遍歷（前中后對應(yīng)的是根結(jié)點的訪問順序）前序遍歷：先根結(jié)點，再左再右中序遍歷：先左，再根結(jié)點，再右后續(xù)遍歷：先左，再右，再根結(jié)點23 、若給出三種遍歷中的任意兩種遍歷，要求

10、寫出第三種遍歷，思路如下：先正確畫出對應(yīng)的二叉樹，根據(jù)已給條件進(jìn)行驗證，最后寫出第三種遍歷24 、三種遍歷的程序?qū)崿F(xiàn)前序遍歷void qian_ma()node *p;p=BT;pre(p);cout<<endl;static qian(node *p)if(p!=NULL)cout<<p->number<<” ”;qian(p->lchild);qian(p->rchild);中序遍歷void zhong_ma()node *p;p=BT;zhong(p);cout<<endl;static zhong(node *p)if

11、（ p!=NULL ）zhong(p->lchild);cout<<p->number<<”;zhong(p->rchild);后續(xù)遍歷void hou_ma()node *p;p=BT;hou(p);cout<<endl;static hou(node *p)if （ p!=NULL ）hou(p->lchild);hou(p->rchild);cout<<p->number<<”;25 、有序樹轉(zhuǎn)二叉樹最最簡便的方法對于有序樹中的每一個結(jié)點，保留與其第一個子結(jié)點（即最左邊的子結(jié)點）的鏈接，斷開與

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

13、void insert （int *v,int m,int n, int x）int k;if(n=m) cout<<”出現(xiàn)上溢錯誤 !”<<endl;k=n-1;while(vk>x)vk+1=vk;k=k-1;vk+1=x;n=n+1;4、有序表的刪除函數(shù)void delete(int *v, int m,int n, int i)int k;if(n=0)cout<<”出現(xiàn)下溢錯誤！ ”<<endl;if(i<1)|(i>n)cout<<”線性表里不存在該元素，不進(jìn)行刪除操作！”<<endl;for

14、(k=i;k<=n;k+)vk-1=vk;n=n-1;5、有序表的對分查找函數(shù)int search （int x,int nint i,j,k;i=1;j=n;）while(i<=j)k=(i+j)/2;if(vk-1=x) cout<<vk-1;return(k-1);if(vk-1>x)j=k-1;else i=k-1;return(-1);6、冒泡排序的原理以及程序?qū)崿F(xiàn)原理：相鄰兩個元素比較大小，要是大，往后移，要是小，不要動，這樣每進(jìn)行一次就可以把最大的那個移到末尾了程序?qū)崿F(xiàn)：void maopao(int *s,int n)int i,j;int tem

15、p;for(i=1;i<n;i+)for(j=0;j<n-I;j+)if(sj>sj+1)temp=sj;sj=sj+1;sj+1=temp;7、快速排序的原理以及程序?qū)崿F(xiàn)原理：我明白快速排序了，在考試的時候，老師已經(jīng)明確說了將第一個元素作為關(guān)鍵字，所以這樣的話 ，將第一個元素設(shè)為 p （k），并將 p（ k）的值賦給 T，然后設(shè)置兩個指針 i 和 j 分別指向表的起始與最后的位置。反復(fù)作以下兩步：將 j 逐漸減小，并逐次比較P（ j）與T，直到發(fā)現(xiàn)一個P（ j） <T為止，將P（ j）移到 P（ i）的位置上。將 i 逐漸增大，并逐次比較P（ i）與T，直到發(fā)現(xiàn)一個P

16、（ i）>T為止，將P（i）移到 P（ j）的位置上。上述兩個操作交替進(jìn)行，直到指針i 與j 指向同一個位置（即i=j）為止，此時將T 移到 P（ i）（即 P（ j）的位置上。程序?qū)崿F(xiàn)：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; j=n-1;T=p0;while(i!=j)while(i<j)&&(pj>=

17、T)j=j-1;if(i<j)pi=pj;i=i+1;while(i<j)&&(pi<=t)i=i+1;if(i<j)pj=pi;j=j-1;pi=T;return(i);8、簡單插入排序的原理及程序?qū)崿F(xiàn)原理：就是從第二個元素開始，往前插到它應(yīng)該在的位置就好啦，還是蠻實用的嘛程序?qū)崿F(xiàn)：void insert(int *p,int n)int j,k;int t;for(j=1;j<n;j+)t=pj;k=j-1;while(k>=0)&&(pk>t)pk+1=pk;k=k-1;pk+1=t;9、希爾排序的原理以及程序?qū)崿F(xiàn)

18、原理：每間隔一定數(shù)量的元素之間進(jìn)行比較和互換，慢慢減小這個間隔，直到間隔為1 時，進(jìn)行一次插入排序就搞定了。程序?qū)崿F(xiàn)：void shel(int *p,int n)int k,j,i;int t;k=n/2;while(k>0)for(j=k;j<=n-1;j+)t=pj;i=j-k;while(i>=0)&&(pi>t) pi+k=pi;i=i-k; pi+k=t;k=k/2;10 、簡單選擇排序的原理以及程序?qū)崿F(xiàn)原理：對于長度為 n 的序列，需要掃描 n-1 遍，每一遍掃描均從剩下的子表中選出最小的元素，然后將該最小的元素與剩余子表的第一個元素進(jìn)行互

19、換。程序?qū)崿F(xiàn)：void select(int *p,int n)int i,j,k;int d;for(i=0;i<n-1;i+)k=i;for(j=i+1;j<n;j+)if(pi<pk)k=j;if(k!=j)d=pi;pi=pk;pk=d;11 、堆排序的原理以及程序?qū)崿F(xiàn)這個有點復(fù)雜，你只需要記住兩句話就可以啦，一是堆一定是完全二叉樹，二是堆中所有根結(jié)點一定是大于其對應(yīng)的葉子結(jié)點的。12 、二叉排序樹的概念及特性概念：左子樹上所有結(jié)點的值均小于根結(jié)點的值；右子樹上所有結(jié)點的值均不小于根結(jié)點的值。 特征：中序遍歷二叉排序樹即可得到有序數(shù)列。13 、給定序列構(gòu)造二叉排序樹第

20、 1 個你就放在根結(jié)點就可以啦，然后放第二個的時候你就看如果是大于根結(jié)點的話放在右子樹，如果是小于根結(jié)點的話就放左子樹，整體如此，局部也是一樣，最后還要檢查一下哦，按照一定的順序檢查，還是很好玩的呢。14 、二叉排序樹的查找方法：給你一個數(shù)，怎么在二叉排序樹中找到它呢？從上往下比較唄，真的很神奇呢，啦啦啦第四章：資源管理技術(shù)1、多道程序設(shè)計：在一臺處理機上并發(fā)運行多個程序2、相對地址（邏輯地址）與絕對地址概念相對地址：編寫程序時使用的地址絕對地址：即為物理地址，數(shù)據(jù)存儲在計算機中的地址3、虛擬存儲的意義：擴大邏輯內(nèi)存第五章：數(shù)據(jù)庫溫馨提示：該部分因為考點較為明確，所以不按照知識點進(jìn)行劃分，而是

21、按照考題類型進(jìn)行整理。本章考題占 20 分，分為兩個題型，對表的操作、對表中數(shù)據(jù)的操作。一、對表的操作例：創(chuàng)建學(xué)生基本信息表（學(xué)號，姓名，年齡，所在系），學(xué)號為字符類型， 8 個字符長，學(xué)號為該表關(guān)鍵字；姓名為字符類型， 10 個字符長；年齡為整型，可以不輸入值；所在系為字符型，12 個字符長，允許不輸入值CREAME TABLE S(SNO CHAR(8) PRIMARY KEY,SNAME CHAR(10) NOT NULL,AGE INT,DEPART CHAR(12);例：學(xué)生信息表 S 沒有記錄學(xué)生性別，修改表結(jié)構(gòu)，增加“性別”列 SEX，此列為字符型，長度為 2ALTER TABLE S ADD SEX CHAR(2)例：將學(xué)生表S 姓名 SNAME 列字符長度修改為20ALTER TABLE S MODIFY (SNAME CHAR(20)；例：刪除 S 表DROP TABLE S二、對表中數(shù)據(jù)的操作有如下表Emplo