Java二級計算機(jī)等級考試知識點

時間復(fù)雜度和空間復(fù)雜度算法的時間復(fù)雜度和空間復(fù)雜度是從不同的角度來衡量算法的執(zhí)行情況的，它們之間沒有內(nèi)在聯(lián)系。算法的時間復(fù)雜度是一個函數(shù)，它定量描述了該算法的運(yùn)行時間。這是一個關(guān)于代表算法輸入值的字符串的長度的函數(shù)。時間復(fù)雜度常用大O符號表述，不包括這個函數(shù)的低階項和首項系數(shù)。使用這種方式時，時間復(fù)雜度可被稱為是漸近的，它考察當(dāng)輸入值大小趨近無窮時的情況。空間復(fù)雜度(SpaceComplexity)是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))。比如直接插入排序的時間復(fù)雜度是O(n^2),空間復(fù)雜度是O(1)。而一般的遞歸算法就要有O(n)的空間復(fù)雜度了，因為每次遞歸都要存儲返回信息。一個算法的優(yōu)劣主要從算法的執(zhí)行時間和所需要占用的存儲空間兩個方面衡量。2.先進(jìn)的軟件開發(fā)工具和環(huán)境對提高開發(fā)人員工作效率是至關(guān)重要的。3.程序設(shè)計語言的基本成分程序設(shè)計語言的基本成分有：數(shù)據(jù)成分，用于描述程序所涉及的數(shù)據(jù)；運(yùn)算成分，用于描述程序中所包含的運(yùn)算；控制成分，用于描述程序中所包含的控制；傳輸成分，用于表達(dá)程序中數(shù)據(jù)的傳輸，即函數(shù)。程序設(shè)計語言的基本成分：數(shù)據(jù)成分、運(yùn)算成分、控制成分、函數(shù)。（1）數(shù)據(jù)成分程序語言的數(shù)據(jù)成分指的是一種程序語言的數(shù)據(jù)類型。數(shù)據(jù)對象總是對應(yīng)著應(yīng)用系統(tǒng)中某些有意義的東西，數(shù)據(jù)表示則指定了程序中值的組織形式。數(shù)據(jù)類型用于代表數(shù)據(jù)對象，同時還可用于檢查表達(dá)始終對運(yùn)算的應(yīng)用是否正確。數(shù)據(jù)是程序操作的對象，具有存儲類別、類型、名稱、作用域和生存期等屬性，使用時要為它分配內(nèi)存空間。數(shù)據(jù)名稱由用戶通過標(biāo)識符命名，標(biāo)識符是由字母、數(shù)字和稱為下劃線的特殊符號“_”組成的標(biāo)記；類型說明數(shù)據(jù)占用內(nèi)存的大小和存放形式；存儲類別說明數(shù)據(jù)在內(nèi)存中的位置和生存期；作用域則說明可以使用數(shù)據(jù)的代碼范圍；生存期說明數(shù)據(jù)占用內(nèi)存的時間范圍。從不同角度可將數(shù)據(jù)進(jìn)行不同的劃分。數(shù)據(jù)類型的分類如下：（a．）按程序運(yùn)行過程中數(shù)據(jù)的值能否改變，可分為常量（整型常量、實型常量、字符常量、符號常量）和變量。（b．）按數(shù)據(jù)的作用域范圍可分為全局量和局部量。（c．）按數(shù)據(jù)組織形式的不同可分為基本類型（整型、實型、字符型、枚舉型）、構(gòu)造類型（數(shù)組、結(jié)構(gòu)、公用）、指針類型和空類型。（2）運(yùn)算成分大多數(shù)程序設(shè)計語言的基本運(yùn)算可分為算術(shù)運(yùn)算、關(guān)系運(yùn)算、邏輯運(yùn)算。為了確保運(yùn)算結(jié)果的唯一性，運(yùn)算符號規(guī)定優(yōu)先級和結(jié)合性。（3）控制成分控制成分指明語言允許表達(dá)的控制結(jié)構(gòu)，程序員使用控制成分來構(gòu)造程序中的控制邏輯。理論上已經(jīng)表明，可計算問題的程序都可以用順序、選擇和循環(huán)這三種控制結(jié)構(gòu)來描述。（4）函數(shù)(也叫傳輸成分)（a.）任何函數(shù)都是由函數(shù)說明和函數(shù)體兩部分組成。（b.）函數(shù)定義的一般格式如下：返回值的類型函數(shù)名（形式參數(shù)表）//注釋{函數(shù)體}（3）函數(shù)調(diào)用的一般形式為：函數(shù)名（實參表）。（4）傳值的好處是傳值調(diào)用不會改變調(diào)用函數(shù)實參變量的內(nèi)容。（5）函數(shù)體若調(diào)用自身則稱為遞歸調(diào)用。4.線性表線性表（linearlist）是數(shù)據(jù)結(jié)構(gòu)的一種，一個線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列。數(shù)據(jù)元素是一個抽象的符號，其具體含義在不同的情況下一般不同。在稍復(fù)雜的線性表中，一個數(shù)據(jù)元素可由多個數(shù)據(jù)項（item）組成，此種情況下常把數(shù)據(jù)元素稱為記錄（record），含有大量記錄的線性表又稱文件（file）。線性表中的個數(shù)n定義為線性表的長度，n=0時稱為空表。在非空表中每個數(shù)據(jù)元素都有一個確定的位置，如用ai表示數(shù)據(jù)元素，則i稱為數(shù)據(jù)元素ai在線性表中的位序。線性表的相鄰元素之間存在著序偶關(guān)系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一個順序表，則表中ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1，稱ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素。當(dāng)i=1,2，…，n-1時，ai有且僅有一個直接后繼，當(dāng)i=2，3，…，n時，ai有且僅有一個直接前驅(qū)

。線性表中數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系，即除了第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部。比如，循環(huán)鏈表邏輯層次上也是一種線性表（存儲層次上屬于鏈?zhǔn)酱鎯Γ?，但是把最后一個數(shù)據(jù)元素的尾指針指向了首位結(jié)點）。我們說“線性”和“非線性”，只在邏輯層次上討論，而不考慮存儲層次，所以雙向鏈表和循環(huán)鏈表依舊是線性表。在數(shù)據(jù)結(jié)構(gòu)邏輯層次上細(xì)分，線性表可分為一般線性表和受限線性表。一般線性表也就是我們通常所說的“線性表”，可以自由的刪除或添加結(jié)點。受限線性表主要包括棧和隊列，受限表示對結(jié)點的操作受限制。線性表的邏輯結(jié)構(gòu)簡單，便于實現(xiàn)和操作。因此，線性表這種數(shù)據(jù)結(jié)構(gòu)在實際應(yīng)用中是廣泛采用的一種數(shù)據(jù)結(jié)構(gòu)。線性表主要由順序表示或鏈?zhǔn)奖硎?。在實際應(yīng)用中，常以棧、隊列、字符串等特殊形式使用。順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，稱為線性表的順序存儲結(jié)構(gòu)或順序映像（sequentialmapping）。它以“物理位置相鄰”來表示線性表中數(shù)據(jù)元素間的邏輯關(guān)系，可隨機(jī)存取表中任一元素。鏈?zhǔn)奖硎局傅氖怯靡唤M任意的存儲單元存儲線性表中的數(shù)據(jù)元素，稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它的存儲單元可以是連續(xù)的，也可以是不連續(xù)的。在表示數(shù)據(jù)元素之間的邏輯關(guān)系時，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置），這兩部分信息組成數(shù)據(jù)元素的存儲映像，稱為結(jié)點（node）。它包括兩個域；存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；存儲直接后繼存儲位置的域稱為指針域。指針域中存儲的信息稱為指針或鏈對線性表進(jìn)行順序查找時，從表中的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查找到所要找的元素為止。在最壞情況下，要查找的元素是表的最后一個元素或查找失敗，這兩種情況都需要將這個元素與表中的所有元素進(jìn)行比較，因此比較次數(shù)為n。5.二叉樹（1）基本概念每個結(jié)點最多有兩棵子樹，左子樹和右子樹，次序不可以顛倒。A、非空二叉樹的第n層上至多有2^(n-1)個元素。B、深度為h的二叉樹至多有2^h-1個結(jié)點。C、滿二叉樹：所有終端都在同一層次，且非終端結(jié)點的度數(shù)為2。D、在滿二叉樹中若其深度為h，則其所包含的結(jié)點數(shù)必為2^h-1。E、完全二叉樹：除了最大的層次即成為一顆滿二叉樹且層次最大那層所有的結(jié)點均向左靠齊，即集中在左面的位置上，不能有空位置。對于完全二叉樹，設(shè)一個結(jié)點為i則其父節(jié)點為i/2，2i為左子節(jié)點，2i