公共信息基礎(chǔ)

《公共信息基礎(chǔ)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、算法算法是指解題方案的準(zhǔn)確而完整的描述算法的時間復(fù)雜度：是指執(zhí)行算法所需要的計算工作量，是由算法所執(zhí)行的基本運(yùn)算次數(shù)來度量算法的空間復(fù)雜度：一個算法的空間復(fù)雜度，是指執(zhí)行這個算法所需要的內(nèi)存空間時間復(fù)雜度和空間復(fù)雜度并不相關(guān)算法具有5個特性:①有窮性：-?個算法必須（對任何合法的輸入值）在執(zhí)行有窮步之后結(jié)束，且每一步都可在有限時間內(nèi)完成，即運(yùn)行時間是有限的;②確定性:算法中每一條指令必須有確切的含義，讀者理解吋不會產(chǎn)牛:歧義;③可行性:—?個算法是可行的,即算法中描述的操作都是可以通過己經(jīng)實(shí)現(xiàn)的基木運(yùn)算執(zhí)行有限次來實(shí)現(xiàn);④輸入:一個算法有零個或多個輸入，這些輸入?yún)ё?/p>

2、于某個特定的對?象的集合;⑤輸出:一個算法有一個或多個輸出。一個算法一般都可以用順序、選擇、循壞三種基本控制結(jié)構(gòu)組合而成數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)，是指反映數(shù)據(jù)元索Z間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。數(shù)據(jù)元素在計算機(jī)中存儲空間中的位置關(guān)系可以與它們的邏輯關(guān)系相同，也可以不相同。數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。數(shù)據(jù)的邏輯結(jié)構(gòu)有線性及非線性結(jié)構(gòu)數(shù)據(jù)元索采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)，對該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)的規(guī)則來處理的，則屬于線性結(jié)構(gòu)；否則

3、屬于非線性結(jié)構(gòu)循壞隊(duì)列屈于順序存儲結(jié)構(gòu)帶鏈的隊(duì)列屬于線性結(jié)構(gòu)雙向鏈表是線性結(jié)構(gòu)線性表線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的。鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲空間多于順序存儲有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)棧，隊(duì)列（必考）08.4棧是限定在一端進(jìn)行插入為刪除的線性表，允許插入少刪除的一端稱為棧頂，不允許插入與刪除的一端稱為棧底。棧按照〃先進(jìn)后出〃或"后進(jìn)先出〃組織數(shù)據(jù)，棧具有記憶作用。對于棧的插入與刪除操作中，不需要改變棧底指針；棧可以鏈?zhǔn)胶晚樞虼鎯?；棧屮元索隨著棧頂指針的變化而

4、變化支持了程序調(diào)用的結(jié)構(gòu)是棧若top=a,bottom=b,那么此棧有b?a+l個元素隊(duì)列是允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的特殊的線性表。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為排頭（或隊(duì)頭）。隊(duì)列乂稱為〃先進(jìn)先出或〃后進(jìn)后出的線性表。往隊(duì)列的隊(duì)尾插入-?個元索稱為入隊(duì)運(yùn)算，從隊(duì)列的排頭刪除一個元索稱為退隊(duì)運(yùn)算當(dāng)循環(huán)隊(duì)列非空（s“）且隊(duì)尾指針等于排頭指針時，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，這種情況稱為〃上溢〃。當(dāng)循環(huán)隊(duì)列為空（s=0）時，不能進(jìn)行退隊(duì)運(yùn)算，這種情況稱為〃下溢循環(huán)序列隊(duì)頭指針可以大于也可以小于隊(duì)尾指針循環(huán)隊(duì)列中元素的個數(shù)及動態(tài)變化情況是山

5、隊(duì)頭指針和隊(duì)尾指針共同決定的。個數(shù)=隊(duì)尾指針（rear）?隊(duì)頭指針（front）+容量（maxSize）隊(duì)列空的條件為s=0;隊(duì)列滿的條件為s=l且front=rear線性鏈表線性列表存儲空間不一定是連續(xù)，且各元素的存儲順序是任意的，優(yōu)點(diǎn)是便于插入和刪除操作二叉樹（必考）二叉樹的基本性質(zhì)：（重要）a.在二叉樹的第k層上，最多有2kl（k>=l）個結(jié)點(diǎn)（滿二叉樹）b.深度為m的二叉樹最多有2卩1個結(jié)點(diǎn)。深度為m的二叉樹是指二叉樹共冇m層。c.已知葉子結(jié)點(diǎn)的數(shù)量，減去1則是度為2的結(jié)點(diǎn)的數(shù)量d.貝-有n個結(jié)點(diǎn)的二叉樹，其深度至少為［Iog2n］+1,其中［Iog2n］表

6、示取Iog2n的整數(shù)部分滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。a.滿二叉樹：在滿二叉樹屮，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最人值，即在滿二叉樹的第k層上有2“個結(jié)點(diǎn)，幾深度為m的滿二義樹共有2叫1個結(jié)點(diǎn)。b.完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最人值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。完全二叉樹如果有N個結(jié)點(diǎn)，當(dāng)N為奇數(shù)的時候，葉子結(jié)點(diǎn)數(shù)為(N+l)/2，此時二叉樹只有度為0的葉子結(jié)點(diǎn)及度為2的結(jié)點(diǎn)，沒有度為1的結(jié)點(diǎn)；當(dāng)N為偶數(shù)的時候，葉了結(jié)點(diǎn)的數(shù)量為N/2注意：滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。二義樹結(jié)點(diǎn)個數(shù)公式：2*度數(shù)為二的結(jié)點(diǎn)數(shù)+

7、1*度數(shù)為一的結(jié)點(diǎn)數(shù)+1二叉樹的遍歷：在先左后右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷可以分為三種：前序遍歷、屮序遍歷、后序遍歷。葉子結(jié)點(diǎn)的先后順序是不變的，和遍歷無關(guān)。.前序遍歷：首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。根左右b.中序遍歷：首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。左根右c.后序遍歷：首先遍歷左了樹，然后遍歷右了樹，最后訪問根結(jié)點(diǎn)。左右跟前序遍歷屮一定以根結(jié)點(diǎn)開頭，后序遍歷一定以根結(jié)點(diǎn)結(jié)尾，而屮序遍歷中，根結(jié)點(diǎn)前面的為樹的左子樹，而其后面的為樹的右子樹査找技術(shù)對于長度為n的有序線性表，在最壞的悄況下，二分查找只需要比較比較［