計算機二級公共基礎(chǔ)知識匯總-在線瀏覽
2025-05-12 12:08本頁面
【正文】 端稱為棧底。即棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。 棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。 隊列及其基本運算 隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。 隊列是“先進先出”或“后進后出”的線性表。 循環(huán)隊列及其運算：所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。 *：循環(huán)隊列中元素的個數(shù)=rearfront。在順序存儲的線性表中，插入或刪除數(shù)據(jù)元素時需要移動大量的數(shù)據(jù)元素。(3)線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。因此，在鏈式存儲方式中，每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域。 在單鏈表中，每一個結(jié)點只有一個指針域，由這個指針只能找到其后件結(jié)點，而不能找到其前件結(jié)點。另一個稱為右指針，指向其后件結(jié)點，這種鏈表稱為雙向鏈表，如下圖所示： 線性鏈表的基本運算 (1)在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素?！ ?2)在線性鏈表中刪除包含指定元素的結(jié)點。 (3)將兩個線性鏈表按要求合并成一個線性鏈表?！ ?5)逆轉(zhuǎn)線性鏈表。 (7)線性鏈表的排序?！ ?：線性鏈表不能隨機存?。ㄗ⑨?）。為了克服線性鏈表的這個缺點，可以采用另一種鏈接方式，即循環(huán)鏈表。2)循環(huán)鏈表中最后一個結(jié)點的指針域不是空，而是指向表頭結(jié)點?！ ∠聢Da是一個非空的循環(huán)鏈表，圖b是一個空的循環(huán)鏈表： 循環(huán)鏈表的優(yōu)點主要體現(xiàn)在兩個方面：一是在循環(huán)鏈表中，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點，而線性單鏈表做不到 這一點?！ ?：循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個表頭結(jié)點，其插入和刪除運算與單鏈表相同。 注釋1：當為一個線性表分配順序存儲結(jié)構(gòu)后，如果出現(xiàn)線性表的存儲空間已滿，但還需要插入新的元素時，就會發(fā)生“上溢”現(xiàn)象。因此，鏈表不是隨機存儲結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。沒有后件的結(jié)點稱為葉子結(jié)點。樹的最大層次稱為樹的深度。2)每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。 (2)二叉樹的基本性質(zhì)(學(xué)吧學(xué)吧獨家稿件) 性質(zhì)1 在二叉樹的第k層上，最多有2k1(k≥1)個結(jié)點。 性質(zhì)3 在任意一棵二叉樹中，度數(shù)為0的結(jié)點(即葉子結(jié)點)總比度為2的結(jié)點多一個。 滿二叉樹與完全二叉樹 滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。在最后一層上只缺少右邊的若干結(jié)點。 下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹： 完全二叉樹還具有如下兩個特性： 性質(zhì)5 具有n個結(jié)點的完全二叉樹深度為[log2n]+1。若k1，則該結(jié)點的父結(jié)點的編號為INT(k/2)。否則該結(jié)點無左子結(jié)點(顯然也沒有右子結(jié)點)。否則該結(jié)點無右子結(jié)點。 與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點也由兩部分組成：數(shù)據(jù)域和指針域。另一個用于指向該結(jié)點的右子結(jié)點的存儲地址，稱為 右指針域。 二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。否則：首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。 (2)中序遍歷(LDR)：若二叉樹為空，則結(jié)束返回。并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。 查找技術(shù) 查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。） 平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。否則就是表中沒有要找的元素，查找不成功。 順序查找一個具有n個元素的線性表，其平均復(fù)雜度為O（n）。 2）即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找。 前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進行。 特點：比順序查找方法效率高。 *：二分法查找只適用于順序存儲的線性表，且表中元素必須按關(guān)鍵字有序（升序）排列（注釋1）。在長度為n的有序線性表中進行二分法查找，其時間復(fù)雜度為O（log2n）。 排序技術(shù) 排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。 插入類排序法（方法：簡單插入排序，希爾排序）。 總結(jié)：各種排序法比較： 程序設(shè)計的風(fēng)格主要強調(diào)：“清晰第一，效率第二”（注釋1）。 ?。?）源程序文檔化。 1）符號名的命名。分為序言性注釋和功能性注釋。 序言性注釋：位于程序開頭部分，包括程序標題、程序功能說明、主要算法、接口說明、程序位置、開發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期及修改日期等。 功能性注釋：嵌在源程序體之中，用于描述其后的語句或程序的主要功能。 3）視覺組織。 2）說明語句中變量安排有序化； 2）程序編寫應(yīng)優(yōu)先考慮清晰性； 4）在保證程序正確的基礎(chǔ)上再要求提高效率； 6）避免不必要的轉(zhuǎn)移； 8）避免采用復(fù)雜的條件語句； 10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化； 12）利用信息隱蔽（注釋2）， 13）從數(shù)據(jù)出發(fā)去構(gòu)造程序； 2）檢查輸入項的各種重要組合的合法性； 4）輸入數(shù)據(jù)時，應(yīng)允許使用自由格式； 6）輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標志； 8）當程序設(shè)計語言對輸入格式有嚴格要求時，應(yīng)保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設(shè)計輸出報表格式。 注釋1：“清晰第一，效率第二”即指在設(shè)計和確定模塊時，使得一個模塊內(nèi)包含的信息（過程或數(shù)據(jù)），對于不需要這些信息的其它模塊來說，是不能訪問的。 ?。?）自頂向下。不要一開始就過多追求眾多的細節(jié)，先從最上層總目標開始設(shè)計，逐步使問題具體化。對復(fù)雜問題，應(yīng)設(shè)計一些子目標作過渡，逐步細化。一個復(fù)雜問題，肯定是由若干稍簡單的問題構(gòu)成。 ?。?）限制使用goto語句。 1）順序結(jié)構(gòu)。 2）選擇結(jié)構(gòu)。 3）重復(fù)結(jié)構(gòu)。 僅僅使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)就足以表達各種其他形式結(jié)構(gòu)，從而實現(xiàn)任何單入口/單出口的程序。也就是說，系統(tǒng) 中的對象及對象之間的關(guān)系能夠如實地反映問題域中固有的事物及其關(guān)系。 *：面向?qū)ο蟮某绦蛟O(shè)計主要考慮的是提高軟件的可重用性。面向?qū)ο蟮某绦蛟O(shè)計方法中的對象是系統(tǒng)中用來描述客觀事物的 一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。 屬性即對象所包含的信息，它在設(shè)計對象時確定，一般只能通過執(zhí)行對象的操作來改變。操作是對象的動態(tài)屬性。 對象的基本特點：標識惟一性，分類性，多態(tài)性，封裝性，模塊獨立性好。指對象是可區(qū)分的，并且由對象的內(nèi)在本質(zhì)來區(qū)分，而不是通過描述來區(qū)分。指可以將具有相同屬性的操作的對象抽象成類。指同一個操作可以是不同對象的行為。從外面看只能看到對象的外部特性，即
高考資料相關(guān)推薦
鄂ICP備17016276號-1