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