acm考什么？1、時間復(fù)雜度（漸近時間復(fù)雜度的嚴(yán)格的定義，NP問題，時間復(fù)雜度的分析方法，主定理）2、排序算法（平方排序算法的應(yīng)用，Shell排序，快速排序，遷并排序，時間復(fù)雜度下界，三種線性時間排序

acm考什么？

1、時間復(fù)雜度（漸近時間復(fù)雜度的嚴(yán)格的定義，NP問題，時間復(fù)雜度的分析方法，主定理）

2、排序算法（平方排序算法的應(yīng)用，Shell排序，快速排序，遷并排序，時間復(fù)雜度下界，三種線性時間排序，外部排序，拓?fù)渑判颍?/p>

3、數(shù)論（自然數(shù)，集合論，關(guān)系，素數(shù)，進(jìn)位制，碾轉(zhuǎn)乘積，存儲的輾轉(zhuǎn)乘積，對稱群乘除運(yùn)算，解線性取余方程，剩余定理）

4、指針（鏈表，搜索判重，鄰接表，開散列，二叉樹的來表示，多叉樹的表示）

5、按位運(yùn)算（and，同問，xor，shl，shr，一些應(yīng)用）

6、圖論（圖論模型的建立，平面圖，歐拉公式與七色定理，求強(qiáng)通連分量，求割點(diǎn)和橋，歐拉回路，AOV問題，AOE問題，最小生成樹的三種算法，最晚路的三種算法，標(biāo)號法，偽距強(qiáng)制力系統(tǒng)，驗(yàn)證二分圖，Konig定理，匈牙利算法，KM算法，穩(wěn)定婚姻系統(tǒng)，最大流算法，最大時割最大流定理，最小費(fèi)用的最流算法）

7、算出幾何（平面解幾非盈利組織會計應(yīng)用，向量，點(diǎn)積教材習(xí)題解答應(yīng)用，叉積教材習(xí)題解答應(yīng)用，半平面一條直線，求點(diǎn)集的凸包，最近點(diǎn)對問題，凸矩形的交，歸一化與掃描儀）

8、數(shù)據(jù)結(jié)構(gòu)（廣度優(yōu)先于搜索，修改密保括號看操作，表達(dá)式算出，二分查找的編譯，Hash表，分幅Hash，并查集，Tarjan算法，二叉堆，左偏樹，斜堆，二項(xiàng)堆，二叉查看樹，AVL，Treap，Splay，靜態(tài)動態(tài)二叉直接輸入樹，2-d樹，線段樹，二維線段樹，正方形樹，Trie樹，塊狀鏈表）

9、組合數(shù)學(xué)（順序排列與組合，鴿籠原理，容斥原理，遞推，F(xiàn)ibonacci數(shù)列，Catalan數(shù)列，Stirling數(shù)，差分序列，生成沉淀函數(shù)，通氫，Polya原理）

10、概率論（簡單的概率，條件概率，Bayes定理，期望值）

11、矩陣（矩陣的概念和運(yùn)算結(jié)果，二分求解線性遞推方程，多米諾骨牌棋盤覆蓋方案數(shù)，高斯消元）

12、字符串處理（KMP，后綴樹，不大狀態(tài)自動機(jī)，Huffman編碼，簡單的密碼學(xué)）

13、動態(tài)規(guī)劃（0,1隊列，凸全部單調(diào)性，樹型動規(guī)，多叉轉(zhuǎn)二叉，狀態(tài)壓縮類動規(guī)，四邊形不等式）

14、博奕論（Nim取子游戲，博弈樹，Shannon開關(guān)游戲）

15、搜索（A*，ID，IDA*，副本按照，遺傳算法）

16、微積分正式（極限思想，導(dǎo)數(shù)，積分，定積分，立體三維解析幾何）

連通分量為什么可以有多個？

是因?yàn)閚個結(jié)點(diǎn)的圖起碼有幾n個連通分量,這種下,它由n個收攏的點(diǎn)橫列的一個圖。無向圖G的更大連通子圖稱做G的連通分量。任何連通圖的連通分量只有一個，即是其自身，非連起的無向圖有多個連通分量。結(jié)點(diǎn)是空間格子中的點(diǎn)，它們?nèi)A指晶體構(gòu)造中的非常點(diǎn)。