(完整)計算機軟件技術(shù)基礎(chǔ)知識點儲備,推薦文檔_第1頁
(完整)計算機軟件技術(shù)基礎(chǔ)知識點儲備,推薦文檔_第2頁
(完整)計算機軟件技術(shù)基礎(chǔ)知識點儲備,推薦文檔_第3頁
(完整)計算機軟件技術(shù)基礎(chǔ)知識點儲備,推薦文檔_第4頁
已閱讀5頁,還剩11頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論