計算機二級公共基礎知識
計算機二級考試包括計算機基礎知識。雖然分值不高但是我們還是要把握好每一分。下面本站小編整理了相關計算機二級公共基礎知識,希望大家喜歡。
計算機二級公共基礎知識1.1棧和隊列
1、棧及其基本運算
棧是限定在一端進行插入與刪除運算的線性表。
在棧中,允許插入與刪除的一端稱為棧頂,不允許插入與刪除的另一端稱為棧底。棧頂元素總是最後插入的元素,棧底元素總是最先插入的元素。即棧是按照“先進後出”或“後進先出”的原則組織數據的。
棧具有記憶作用。
棧的基本運算:1)插入元素稱為入棧運算;2)刪除元素稱為退棧運算;3)讀棧頂元素是將棧頂元素賦給一個指定的變量,此時指針無變化。
棧的存儲方式和線性表類似,也有兩種,即順序棧和鏈式棧。
2、隊列及其基本運算
隊列是指允許在一端(隊尾)進入插入,而在另一端(隊頭)進行刪除的線性表。尾指針(Rear)指向隊尾元素,頭指針(front)指向排頭元素的前一個位置(隊頭)。
隊列是“先進先出”或“後進後出”的線性表。
隊列運算包括:1)入隊運算:從隊尾插入一個元素;2)退隊運算:從隊頭刪除一個元素。
循環隊列及其運算:所謂循環隊列,就是將隊列存儲空間的最後一個位置繞到第一個位置,形成邏輯上的'環狀空間,供隊列循環使用。在循環隊列中,用隊尾指針rear指向隊列中的隊尾元素,用排頭指針front指向排頭元素的前一個位置,因此,從頭指針front指向的後一個位置直到隊尾指針rear指向的位置之間,所有的元素均為隊列中的元素。
循環隊列中元素的個數=rear-front。
1.2 樹與二叉樹
1、樹的基本概念
樹是一種簡單的非線性結構。在樹這種數據結構中,所有數據元素之間的關係具有明顯的層次特性。
在樹結構中,每一個結點只有一個前件,稱為父結點。沒有前件的結點只有一個,稱為樹的根結點,簡稱樹的根。每一個結點可以有多個後件,稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中,一個結點所擁有的後件的個數稱為該結點的度,所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
(1)什麼是二叉樹
二叉樹是一種很有用的非線性結構,它具有以下兩個特點:1)非空二叉樹只有一個根結點;2)每一個結點最多有兩棵子樹,且分別稱為該結點的左子樹與右子樹。
根據二叉樹的概念可知,二叉樹的度可以為0(葉結點)、1(只有一棵子樹)或2(有2棵子樹)。
(2)二叉樹的基本性質(學吧學吧獨家稿件)
性質1 在二叉樹的第k層上,最多有2k-1(k≥1)個結點。
性質2 深度為m的二叉樹最多有個2m-1個結點。
性質3 在任意一棵二叉樹中,度數為0的結點(即葉子結點)總比度為2的結點多一個。
性質4 具有n個結點的二叉樹,其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分。
3、滿二叉樹與完全二叉樹
滿二叉樹:除最後一層外,每一層上的所有結點都有兩個子結點。
完全二叉樹:除最後一層外,每一層上的結點數均達到最大值;在最後一層上只缺少右邊的若干結點。
根據完全二叉樹的定義可得出:度為1的結點的個數為0或1。
下圖a表示的是滿二叉樹,下圖b表示的是完全二叉樹:
完全二叉樹還具有如下兩個特性:
性質5 具有n個結點的完全二叉樹深度為[log2n]+1。
性質6 設完全二叉樹共有n個結點,如果從根結點開始,按層序(每一層從左到右)用自然數1,2,…,n給結點進行編號,則對於編號為k(k=1,2,…,n)的結點有以下結論:
①若k=1,則該結點為根結點,它沒有父結點;若k>1,則該結點的父結點的編號為INT(k/2)。
②若2k≤n,則編號為k的左子結點編號為2k;否則該結點無左子結點(顯然也沒有右子結點)。
③若2k+1≤n,則編號為k的右子結點編號為2k+1;否則該結點無右子結點。
4、二叉樹的存儲結構
在計算機中,二叉樹通常採用鏈式存儲結構。
與線性鏈表類似,用於存儲二叉樹中各元素的存儲結點也由兩部分組成:數據域和指針域。但在二叉樹中,由於每一個元素可以有兩個後件(即兩個子結點),因此,用於存儲二叉樹的存儲結點的指針域有兩個:一個用於指向該結點的左子結點的存儲地址,稱為左指針域;另一個用於指向該結點的右子結點的存儲地址,稱為右指針域。
一般二叉樹通常採用鏈式存儲結構,對於滿二叉樹與完全二叉樹來説,可以按層序進行順序存儲(註釋1)。
5、二叉樹的遍歷
二叉樹的遍歷是指不重複地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種:
(1)前序遍歷(DLR):若二叉樹為空,則結束返回。否則:首先訪問根結點,然後遍歷左子樹,最後遍歷右子樹;並且,在遍歷左右子樹時,仍然先訪問根結點,然後遍歷左子樹,最後遍歷右子樹。
(2)中序遍歷(LDR):若二叉樹為空,則結束返回。否則:首先遍歷左子樹,然後訪問根結點,最後遍歷右子樹;並且,在遍歷左、右子樹時,仍然先遍歷左子樹,然後訪問根結點,最後遍歷右子樹。
(3)後序遍歷(LRD):若二叉樹為空,則結束返回。否則:首先遍歷左子樹,然後遍歷右子樹,最後訪問根結點,並且,在遍歷左、右子樹時,仍然先遍歷左子樹,然後遍歷右子樹,最後訪問根結點。
註釋1:這樣,不僅節省了存儲空間,又能方便地確定每一個結點的父結點與左右子結點的位置,但順序存儲結構對於一般的二叉樹不適用。
-
交通安全知識教育觀後感(通用20篇)
看完某一作品後,大家一定收穫不少吧,為此需要好好認真地寫觀後感。那麼你真的懂得怎麼寫觀後感嗎?以下是小編整理的交通安全知識教育觀後感,僅供參考,大家一起來看看吧。交通安全知識教育觀後感1一場場交通事故,不是在特技表演,一切都是真實的,什麼事都有可能發生。讓...
-
【推薦】生日禮物作文300字10篇
在平日的學習、工作和生活裏,大家都有寫作文的經歷,對作文很是熟悉吧,寫作文是培養人們的觀察力、聯想力、想象力、思考力和記憶力的重要手段。那麼你有了解過作文嗎?以下是小編為大家整理的生日禮物作文300字10篇,僅供參考,歡迎大家閲讀。生日禮物作文300字篇1英桃...
-
【推薦】禮物三年級作文300字集錦六篇
在學習、工作、生活中,大家或多或少都會接觸過作文吧,藉助作文可以提高我們的語言組織能力。你知道作文怎樣寫才規範嗎?以下是小編精心整理的禮物三年級作文300字6篇,僅供參考,大家一起來看看吧。禮物三年級作文300字篇1母親節到了,以往我都是給媽媽洗腳,但是這次我要...
-
關於安全知識作文彙編九篇
在日常學習、工作或生活中,大家都嘗試過寫作文吧,作文是從內部言語向外部言語的過渡,即從經過壓縮的簡要的、自己能明白的語言,向開展的、具有規範語法結構的、能為他人所理解的外部語言形式的轉化。你寫作文時總是無從下筆?下面是小編為大家收集的安全知識作文9篇,...