天天看點

NOIP初賽知識點集錦

知識點(by chs):

  1. 一個32位整型變量占4位元組(一個位元組8位)
  2. 運算符優先級表

!> & > ^ > | > && > ||

與位運算結合優先級:邏輯非(!,┐)=按位反(~)>位移運算(<<,>>)>不等号(>=,<=)>等号(==,!=)>按位與(&)>按位異或(^)>按位或(|)>邏輯與(&&,∧)>邏輯或(||,∨)

常用:除、乘、取餘、加、減。(按優先級從大到小順序)

  1. 冒泡排序!!!歸并排序!!!(注意相同的數排序後的不同位置)

5、進制的字母表達:

H(Hexadecimal)——16進制

D(Decimal)——10進制

O(Octonary)——8進制

B(Binary)——2進制

6、進制間的轉換

例:

NOIP初賽知識點集錦
NOIP初賽知識點集錦

注意:最後寫的順序(小數部分與整數部分不同!)

X進制先轉10進制,再轉y進制

https://blog.csdn.net/lleozhang/article/details/82918431

9、線性探查法:設給出一組元素,它們的關鍵碼為:37,25,14,36,49,68,57,11,散清單為HT[12],表的大小m = 12,假設采用Hash(x) = x % p; // (p = 11) 11是接近m的質數,就有:

Hash(37) = 4 Hash(25) = 3 Hash(14) = 3 Hash(36) = 3 Hash(49) = 5 Hash(68) = 2 Hash(57) = 2 Hash(11) = 0

采用線性探查法處理沖突

NOIP初賽知識點集錦

需要加入一個元素時,使用散列函數進行計算,确定元素的桶号H0,按此桶号檢視該桶,如果是所 要搜尋的元素的關鍵碼,則說明表中已有此元素,不再進行此元素的插入,否則即為沖突,再檢視緊 随其後的下一個桶,如果是空桶,則搜尋失敗,新元素插入即可。

在閉散列的情形下不能随便實體删除表中已有的元素。因為若删除元素會影響其他元素的搜尋。

10、IP位址的要求:最大數是255.255.255.255,是一個廣播位址,别的都小于它。

圖論:

完全圖:任意兩點均有連邊的圖,其中邊數為n*(n-1)/2,其中n為圖中節點個數

連通圖:任意兩點之間都能直接或間接通過邊到達的圖

樹:任意兩點之間的簡單路徑有且僅有一條(或有n個點,n-1條邊的連通圖)

歐拉圖:可以一筆畫出來的圖

一個圖是歐拉圖的充要條件(無向圖):度為奇數點的點的個數<=2

相關定義:

歐拉環遊:通過圖中每邊恰好一次的閉路徑

歐拉閉迹:通過圖中每邊恰好一次的路徑

(1)字首、中綴、字尾表達式  轉換與求值

  https://www.cnblogs.com/chensongxian/p/7059802.html

(2)完全圖及其性質:若一個圖的每一對不同頂點恰有一條邊相連,則稱為完全圖。完全圖是每對頂點之間都恰連有一條邊的簡單圖。n個端點的完全圖有n個端點及n(n − 1) / 2條邊 

 (3)二叉樹:

如圖所示:

NOIP初賽知識點集錦
  1. 二叉樹結論:滿二叉樹的葉結點個數為N,則它的結點總數為2 * N – 1    (注意逆用)
  2. 先序周遊、中序周遊、後序周遊
  3. 滿二叉樹:一顆深度為k且有2^k-1個節點的二叉樹稱為滿二叉樹;
  4. 完全二叉樹:對滿二叉樹的結點進行連續編号,約定編号從根結點起,自上而下,自左至右。深度為k的,有n個結點的二叉樹,當且僅當其每一個結點都與深度為k的滿二叉樹編号從1至n的結點對應時,稱為完全二叉樹。

幻方規律:

幻方:第一行中間是1,下一個數寫在上一個數的右上面那個格(第一行的上一行是最後一行,最後一列的右面是第一列),如果右上面那個格已經填過就填下面那個(能填右上填右上,填不了右上就填下面那個)

大佬文章