C語言公共基礎(chǔ)部分

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

1、C語言公共基礎(chǔ)部分下面分為四個(gè)部分進(jìn)行組織。文中標(biāo)注了三個(gè)星號(hào)的，表示非常重要,基本每次考試都是必考；標(biāo)注了兩個(gè)星號(hào)或一個(gè)星號(hào)的，表示也較重要，很容易考到。出現(xiàn)在【】括號(hào)中的內(nèi)容，表示要很精確的背下來的。整個(gè)文檔中的五頁，建議考前都要認(rèn)真的記憶。第一部分算法與數(shù)據(jù)結(jié)構(gòu)（歷年比例41%）1、算法?問題處理方案的正確而完整的描述稱為【算法】。算法分析的□的是，分析算法的效率以求改進(jìn)。算法的基本特征是【可行性】、【確定性】、【有窮性】和擁有足夠情報(bào)。?算法的有窮性是指：算法程序的運(yùn)行時(shí)間是有限的。?算法的復(fù)雜度是衡量算法好

2、壞的度量，分為【吋間復(fù)雜度】和【空間復(fù)雜度】?！铩飼r(shí)間復(fù)雜度是指執(zhí)行算法所需要的【計(jì)算工作量】；算法的空間復(fù)雜度是指算法執(zhí)行過程中所需的【存儲(chǔ)空間】。?算法時(shí)間復(fù)雜度或空間復(fù)雜度中的一項(xiàng)的值，沒有辦法推出另一項(xiàng)的值。2、數(shù)據(jù)結(jié)構(gòu)?數(shù)據(jù)結(jié)構(gòu)分為【邏輯結(jié)構(gòu)】和【存儲(chǔ)結(jié)構(gòu)】。線性結(jié)構(gòu)和非線性結(jié)構(gòu)屬于邏輯結(jié)構(gòu)；順序、鏈?zhǔn)?、索引屬于存?chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）。循環(huán)隊(duì)列屬于【存儲(chǔ)結(jié)構(gòu)】?！飻?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。?一個(gè)邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率。程序

3、執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)。?數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于【線性結(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ǔ)的存儲(chǔ)空間不一定是連續(xù)的。?有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。?隊(duì)列是一種特殊的線性表，循環(huán)隊(duì)列按照【先進(jìn)先出】原則組織數(shù)據(jù)。循環(huán)隊(duì)列是隊(duì)列的【順序】存儲(chǔ)結(jié)構(gòu)。?數(shù)據(jù)的獨(dú)立性分為【物理獨(dú)立】性和【邏輯獨(dú)立性】。當(dāng)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)改變時(shí)，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應(yīng)用程序可以不用修改，稱為【物

4、理獨(dú)立性】。3、棧和隊(duì)列★★棧是一種特殊的線性表，是只能在一端進(jìn)行插入和刪除的線性表,特點(diǎn)是FILO(FirstInLastOut)。★★棧是【先進(jìn)后出】的線性表；棧具有記憶作用；對(duì)棧的插入與刪除操作中，不需要改變【棧底指針】。假定讓元素1、2、3、A、B依次入棧，則出棧的順序是：B、A、3、2、lo?棧與隊(duì)列都是線性結(jié)構(gòu)，樹是非線性結(jié)構(gòu)。支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是【?！?。?棧與隊(duì)列的共同點(diǎn)是，都只允許在【端點(diǎn)處】插入和刪除元素。?棧只能順序存儲(chǔ)的描述是錯(cuò)誤的。棧可以有【順序和鏈?zhǔn)健績(jī)煞N存儲(chǔ)方式?！铩镪?duì)列是允許在一段

5、插入，在另一端進(jìn)行刪除的線性表，其特點(diǎn)是【先進(jìn)先出】。?循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定。循環(huán)隊(duì)列的頭指針為front,尾指針為rear,容量為maxSize,則循環(huán)隊(duì)列中元素的個(gè)數(shù)是【(rear-front+maxSize)modmaxSizeL4、線性鏈表?線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用鏈表表示線性表的優(yōu)點(diǎn)是【便于插入和刪除操作】。?線性鏈表的存儲(chǔ)空間不一定連續(xù)，且個(gè)元素的存儲(chǔ)順序是任意的。5、樹與二叉樹?在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件(繼)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的

6、度。二叉樹各結(jié)點(diǎn)的度只可能取值0、1、2,不可能是其它值。換言之，知道了度為1結(jié)點(diǎn)數(shù)量的前提下，葉子結(jié)點(diǎn)或度為2的結(jié)點(diǎn)屮知道其一，就可以求出總的結(jié)點(diǎn)數(shù)?！铩铩锵旅骊P(guān)于計(jì)算結(jié)點(diǎn)數(shù)量的兒個(gè)性質(zhì)，非常重要:⑴對(duì)任意的二叉樹，葉子結(jié)點(diǎn)的數(shù)量，比度為2的結(jié)點(diǎn)數(shù)量多一個(gè)（換言之，已知葉子結(jié)點(diǎn)的數(shù)量，減去1則是度為2的結(jié)點(diǎn)數(shù)量；已知度為2的結(jié)點(diǎn)數(shù)量，加上1就是葉子結(jié)點(diǎn)數(shù)量）⑵完全二叉樹如果有N個(gè)結(jié)點(diǎn)，當(dāng)N為奇數(shù)的時(shí)候，葉子結(jié)點(diǎn)數(shù)為（N+l）/2,此吋二叉樹只有度為0的葉了結(jié)點(diǎn)及度為2的結(jié)點(diǎn)，沒有度為1的結(jié)點(diǎn)；當(dāng)N為偶數(shù)的時(shí)候，葉子

7、結(jié)點(diǎn)的數(shù)量為N2（注意條件,必須是完全二叉樹，當(dāng)然包括滿二叉樹）⑶滿二叉樹第K層上的結(jié)點(diǎn)數(shù)量為2K-1；深度為K的滿二叉樹，結(jié)點(diǎn)總數(shù)為2K-lo上述的計(jì)算公式，關(guān)鍵要能夠應(yīng)用，例如，深度為7的滿二叉樹，度為2的結(jié)點(diǎn)數(shù)量是多少？既然是滿二叉樹，葉子結(jié)點(diǎn)的數(shù)量就是第7層的結(jié)點(diǎn)數(shù)量，也就是26,可以算出葉子結(jié)點(diǎn)為64,因此度為2的結(jié)點(diǎn)數(shù)是63（葉子結(jié)點(diǎn)數(shù)減去l）o★★★二叉樹的前序遍歷、屮序遍歷、后續(xù)遍歷：前屮后三個(gè)詞是相對(duì)于根來講的，前序是【根-＞左-＞右】，中序是【左-＞根-＞右】，后續(xù)是【左-＞右-＞根】。具體操作為

8、：先序遍歷(DLR):訪問根結(jié)點(diǎn)，按先序遍歷左了樹，按先序遍歷右了樹。屮序遍歷(LDR):按屮序遍歷左子樹，訪問根結(jié)點(diǎn)，按屮序遍歷右子樹。后序遍歷(LRD):按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點(diǎn)。卜?面以中序遍歷為例，來講解實(shí)際的解題方法：對(duì)一棵樹，將根結(jié)點(diǎn)下的左了樹用一個(gè)橢圓圈起來,右了樹也用一個(gè)橢圓圈起來。在左子樹上標(biāo)記上1,在根