公共信息基礎(chǔ)

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

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

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

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

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

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

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

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