計算機軟件技術(shù)基礎(chǔ)知識點儲備

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第一章：概述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ù)進行處理時，各數(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é)點進行操作的集合，包括插入、刪除、更新、檢索、排序等。4、數(shù)據(jù)元素是數(shù)據(jù)的基本單

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

3、t i, 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、順序表的刪除異常處理：1 當(dāng)線性表為空（即n=0）時為下溢錯誤，不能進行刪除，算法結(jié)束；2 當(dāng)i<1或i>n時，認為不存在該元素，不進行刪除。函數(shù)的代碼實現(xiàn)：void delete(int *v, int m,int n, int i)int k;if(n=0) cout<<”出現(xiàn)下溢錯誤！”<<

4、endl;if(i<1)|(i>n) cout<<”線性表里不存在該元素，不進行刪除操作！”<<endl;for(k=i;k<=n;k+)vk-1=vk;n=n-1;9、棧（相當(dāng)于一個井）的相關(guān)概念 1 先進后出（后進先出）2 棧頂允許插入與刪除3 棧底不允許插入與刪除10、隊列（相對于排隊買飯）的相關(guān)概念1 先進先出2 隊尾允許插入3 對頭允許刪除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-

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

6、t;<endl;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,i

7、nt b)node *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->

8、;next=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層上，最多有2k1(k1

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

10、已給條件進行驗證，最后寫出第三種遍歷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 （p!=NULL）zhong(p->lchild)

11、;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é)點）的鏈接，斷開與其他子結(jié)點的鏈接，且將其他子結(jié)點依次鏈接在第一個子結(jié)點的

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

13、 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<<”線性表里不存在該元素，不進行刪除操作！”<<endl;for(k=i;k<=n;k+)vk-1=vk;n=n-1;5、有序表的對分查找函數(shù)

14、int search（int x,int n）int 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)原理：相鄰兩個元素比較大小，要是大，往后移，要是小，不要動，這樣每進行一次就可以把最大的那個移到末尾了程序?qū)崿F(xiàn)：void maopao(int *s,int n)int i,j;int temp;for(i=1;i<n;i+)for(j=0;j<n-I;j+)if

15、(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（i）>T為止，將P（i）移到P（j）的位置上。上述兩個操作交替進行，直到指針i與j指向同一個位置（即i=j）為止，此

16、時將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>=T)j=j-1;if(i<j)pi=pj;i=i+1;while(i<j)&&(pi<=t)i=i+1;if(i&l

17、t;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)原理：每間隔一定數(shù)量的元素之間進行比較和互換，慢慢減小這個間隔，直到間隔為1時，進行一次插入排序就搞定了。程序?qū)崿F(xiàn)：void shel(int *p

18、,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遍，每一遍掃描均從剩下的子表中選出最小的元素，然后將該最小的元素與剩余子表的第一個元素進行互換。程序?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

19、;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)造二叉排序樹第1個你就放在根結(jié)點就可以啦，然后放第二個的時候你就看如果是大于根結(jié)點的話放在右子樹，如果是小于根結(jié)點的話就放左子樹，整體如此，局部也是一樣，最后還要檢查一下哦，按照一

20、定的順序檢查，還是很好玩的呢。14、二叉排序樹的查找方法：給你一個數(shù)，怎么在二叉排序樹中找到它呢？從上往下比較唄，真的很神奇呢，啦啦啦第四章：資源管理技術(shù)1、多道程序設(shè)計：在一臺處理機上并發(fā)運行多個程序 2、相對地址（邏輯地址）與絕對地址概念 相對地址：編寫程序時使用的地址絕對地址：即為物理地址，數(shù)據(jù)存儲在計算機中的地址3、虛擬存儲的意義：擴大邏輯內(nèi)存第五章：數(shù)據(jù)庫溫馨提示：該部分因為考點較為明確，所以不按照知識點進行劃分，而是按照考題類型進行整理。本章考題占20分，分為兩個題型，對表的操作、對表中數(shù)據(jù)的操作。一、對表的操作例：創(chuàng)建學(xué)生基本信息表（學(xué)號，姓名，年齡，所在系），學(xué)號為字符類型，8

21、個字符長，學(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ù)