noip初賽知識點(diǎn)復(fù)習(xí)總結(jié)(編輯修改稿)
2025-05-22 12:51 本頁面
【文章內(nèi)容簡介】 . 6 B. 7 C. 8 D. 9 E. 10排序思考:最壞情況下最少需要交換多少次?n11. 將數(shù)組{32, 74, 25, 53, 28, 43, 86, 47}中的元素按從小到大的順序排列，每 次可以交換任意兩個(gè)元素，最少需要 交換___5__次。排序穩(wěn)定排序包括：插入排序、冒泡排序不穩(wěn)定排序包括：選擇排序、希爾排序、快速排序、堆排序時(shí)間復(fù)雜度：冒泡排序O(n2)，選擇排序O(n2)，快速排 序O(nlog2n)，堆排序O(nlog2n)二叉樹定義：n個(gè)結(jié)點(diǎn)的有限集，每個(gè)結(jié)點(diǎn)至多 只有兩棵子樹，子樹也是二叉樹。每個(gè)結(jié) 點(diǎn)可以有左孩子和右孩子，順序不可顛倒。概念：度：某個(gè)結(jié)點(diǎn)孩子的個(gè)數(shù)葉子：度為0的結(jié)點(diǎn)深度：二叉樹的層數(shù)滿二叉樹：深度為n且結(jié)點(diǎn)數(shù)為2n1的二叉樹完全二叉樹：深度為k，1~k1層為滿二叉 樹，第k層葉子節(jié)點(diǎn)集中在左邊的二叉樹二叉樹二叉樹的遍歷：先根，中根，后根遍歷以及深度優(yōu)先遍歷和廣度優(yōu)先遍歷，具體方 法參看資料。根據(jù)前根中根或中根后根遍歷確定一顆二叉樹的形態(tài)以及另一種遍歷。二叉樹知識點(diǎn)補(bǔ)充n個(gè)結(jié)點(diǎn)所組成的不同形態(tài)的二叉樹數(shù)目為：C(2n,n)/(n+1)二叉樹二叉樹T，已知其前序遍歷序列為1 2 4 35 7 6，中序遍歷序列為4 2 1 5 7 3 6，則其后序遍歷序列為（B）。A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1E. 4 5 2 6 3 7 1二叉樹已知7個(gè)節(jié)點(diǎn)的二叉樹的先根遍歷是1 2 45 6 3 7(數(shù)字為結(jié)點(diǎn)的編號，以下同)， 后 根遍歷是4 6 5 2 7 3 1， 則該二叉樹的可能的中根遍歷是（ABD）A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3只知道前根遍歷和后根遍歷是無法確定一棵二叉樹的，所以這題采用反推驗(yàn)證二叉樹4. 完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為4 * N + 3，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（E）。A. 2 * N B. 2 * N 1C. 2 * N + 1 D. 2 * N 2E. 2 * N + 24n+3=2*2(n+1) 1，多么熟悉的公式啊2*葉子結(jié)點(diǎn)數(shù)1，這不是滿二叉樹的結(jié)點(diǎn)數(shù) 么？二叉樹8．高度為 n 的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為 n1 的滿二叉樹。在這里，樹高等于葉 結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為 0，如 果某個(gè)均衡的二叉樹共有 2381 個(gè)結(jié)點(diǎn)， 則該樹的樹高為（B）。A. 10 B. 11 C. 12 D. 13E. 210 – 12112381212二叉樹5. 一個(gè)高度為h 的二叉樹最小元素?cái)?shù)目是（B）。A） 2h+1 B） h C） 2h1D） 2h E） 2h1此時(shí)二叉樹退化成一條鏈圖圖是由頂點(diǎn)和邊所組成的數(shù)據(jù)結(jié)構(gòu)。分為有向圖和無向圖。帶權(quán)圖：權(quán)的含義，不加權(quán)的圖也可以認(rèn)為所有邊上的權(quán)都是1。? 階和度：一個(gè)圖的階是指圖中頂點(diǎn)的個(gè)數(shù)如果頂點(diǎn)A和B之間有一條邊相連，則稱A和B是 關(guān)聯(lián)的? 頂點(diǎn)的度：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，有奇點(diǎn)、 偶點(diǎn)之分? 對于有向圖：有入度和出度之分圖大家記住定義，然后就見招拆招了。圖論的題目考得比較少，而且大家知道定義， 運(yùn)用各種方法應(yīng)該不難得到答案。下面就簡單地講一下幾道出現(xiàn)過的題目。圖假設(shè)我們用d=(a1,a2,...,a5),表示無向圖G的5個(gè)頂點(diǎn)的度數(shù)，下面給出的哪（些）組d 值合理（BE）。A）{5，4，4，3，1}B）{4，2，2，1，1}C）{3，3，3，2，2}D）{5，4，3，2，1}E）{2，2，2，2，2}圖9. 歐拉圖G是指可以構(gòu)成一個(gè)閉回路的 圖，且圖G的每一條邊恰好在這個(gè)閉回路 上出現(xiàn)一次（即一筆畫成）。在以下各個(gè) 描述中, 不一定是歐拉圖的是：（ ）。A. 圖G中沒有度為奇數(shù)的頂點(diǎn)B. 包括歐拉環(huán)游的圖(歐拉環(huán)游是指通過 圖中每邊恰好一次的閉路徑)C. 包括歐拉閉跡的圖(歐拉跡是指通過途 中每邊恰好一次的路徑)D. 存在一條回路, 通過每個(gè)頂點(diǎn)恰好一次E. 本身為閉跡的圖解釋：閉跡，一條路徑，起點(diǎn)和終點(diǎn)是一個(gè)點(diǎn)圖5. 平面上有五個(gè)點(diǎn)A(5, 3), B(3, 5), C(2, 1),D(3, 3), E(5, 1)。以這五點(diǎn)作為完全圖G 的 頂點(diǎn)，每兩點(diǎn)之間的直線距離是圖G 中對應(yīng) 邊的權(quán)值。圖G 的最小生成樹中的所有邊的 權(quán)值和為（D） +5 +5+22+5講解：最小生成樹算法圖1. 無向圖G有16條邊，有3個(gè)4度頂點(diǎn)、4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度均小于3，則G至少___1_1___個(gè)頂點(diǎn)。排列組合前置知識：乘法原理，加法原理，排列組 合公式C(n,r)，A(n,r)的計(jì)算方法以及基本 定理和推論。沒學(xué)到的同學(xué)可在課后自學(xué)（參見高二數(shù) 學(xué)課本，沒有的問數(shù)學(xué)老師要相關(guān)資料）另外強(qiáng)烈推薦一本書：《離散數(shù)學(xué)及其應(yīng) 用》，機(jī)械工業(yè)出版社，Kenneth ，袁崇義等譯，當(dāng)當(dāng)和卓越均有售排列組合公式：不可重復(fù)的n個(gè)元素取r個(gè)的排列數(shù)為：A(n,r)可重復(fù)的n個(gè)元素取r個(gè)的排列數(shù)為：nr不可重復(fù)的n個(gè)元素取r個(gè)的組合數(shù)為：C(n,r)可重復(fù)的n個(gè)元素取r個(gè)的組合數(shù)為：C(n+r1,r)排列組合練習(xí)：，從中依次拿出三 個(gè)，可能的排列有多少種，從中依次拿出三 個(gè)，可能的排列有多少種，從中拿出三個(gè)， 可能的組合有多少種，從中拿出三個(gè)， 可能的組合有多少種排列組合由3個(gè)a，5個(gè)b和2個(gè)c構(gòu)成的所有字符串中，包含子串“abc”的共有（D）個(gè)。A. 40320 B. 39600 C. 840 D. 780E. 60C(8,1) * C(7,2) *C(5,4) * C(1,1) C(6,2) * C(4,1)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1