只是供自己復習使用，無參考價值，本人無法對以下內容的準確性做保證，大家看看就好，
如發現錯誤，希望大家多多指正，

第一章：

1.什么是計算思維（書P17）

PPT上的：
“計算思維就是運用計算機科學的基礎概念去求解問題、設計系統和理解人類的行為，它包括了反映計算機科學領域之廣度的一系列思維活動”，
也就是說，計算思維是一種解決問題的思考方式，而不是具體的學科知識，這種思考方式要運用計算機科學的基本理念，而且用途挺廣的，

書上的：
①計算思維是概念化思維，不是程式化思維，
②計算思維是基礎的技能，而不是機械的技術，
③計算思維是人的思維，不是計算機的思維，
④計算思維是思想，不是人造品，
⑤計算思維是數學和工程互補融合的思維，不是數學性的思維，
⑥計算思維面向所有的人，所有領域，

第二章：！！！

1.加法器（4、8位），怎么進位，（書P56）

2.串行加法器的缺點（沒找到，從百度上復制的）

串行加法器運算速度很慢，要等一級的加法運算完成、得到進位的值后再才能進行下一位的運算，加的級數越多、所耗費的時間越長，因為總時間是每一級時間的總和，

3.補碼

已知[x]_補求[-x]_補的方法：[x]_補連同符號位，每一位都取反,之后再加1，

負數補->原:①數值位取反+1;②負數補碼中，最右邊的1及其右邊同原碼，最右邊的1的左邊同反碼，

4.溢位

方法1：

方法2：

方法3：（首推！！！）

5.圖靈機（基本結構：書P61以及PPT第二章P90）

書上的原話：
圖靈機由以下幾部分組成：一條兩端可無限延長的紙帶，一個讀寫頭，以及一個可控制讀寫頭作業的控制器，圖靈機的紙帶被劃分為一系列均勻的方格，每個方格中可填寫一個符號；讀寫頭可以沿帶子方向左右移動（一次只能移動一格）或停留在原地，并可以在當前方格上進行讀寫:控制器是一個有限狀態自動機，擁有預定的有限個互不相同的狀態并能根據輸入改變自身的狀態(即從一種狀態轉換成另一種狀態)，任何時候，它只能處于這些狀態中的一種，

PPT上的：

6.圖靈機：設計狀態執行圖（加法減法、字串操作））（書P62）（必考）

有一個注意點：如果在x上面有多個操作要進行，讀寫頭回到原位是必要的（如inc(),dec()），（P66）
圖靈機可能考求補碼、反碼！！！
以下是字串操作：

7.馮諾依曼體系、馮諾依曼計算機有哪些部分（書P70~71詳細介紹了5大部件）

組成：存盤器、運算器、控制器、輸入設備、輸出設備
特征：采用二進制；計算機按照程式順序執行

8.要會畫馮諾依曼圖，重點關注一下指令流、資料流（書P69右下角）

9.插一個上課講的考點但是提綱沒有的——可計算性與計算復雜性（書P82）

一個問題理論上是否能行，取決于其可計算性，而現實是否能行，取決于其計算復雜度，

第三章：

1.什么是面向物件

面向程序就是分析出解決問題所需要的步驟，然后用函式把這些步驟一步一步實作，使用的時候一個一個依次呼叫就可以了，
面向物件是把構成問題事務分解成各個物件，建立物件的目的不是為了完成一個步驟，而是為了描敘某個事物在整個解決問題的步驟中的行為，

2.面向物件與面向程序的區別（要會說，會舉例）

面向物件是什么，怎么做的，如果換成面向程序怎么做的，所以我們要面向物件

栗子：
面向程序的設計思路就是：
首先分析問題的步驟：1、開始游戲，2、黑子先走，3、繪制畫面，4、判斷輸贏，5、輪到白子，6、繪制畫面，7、判斷輸贏，8、回傳步驟2，9、輸出最后結果，把上面每個步驟用分別的函式來實作，問題就解決了，

面向物件的設計則是從另外的思路來解決問題：
整個五子棋可以分為 1、黑白雙方，這兩方的行為是一模一樣的，2、棋盤系統，負責繪制畫面，3、規則系統，負責判定諸如犯規、輸贏等，第一類物件（玩家物件）負責接受用戶輸入，并告知第二類物件（棋盤物件）棋子布局的變化，棋盤物件接收到了棋子的i變化就要負責在螢屏上面顯示出這種變化，同時利用第三類物件（規則系統）來對棋局進行判定，

總結：
面向物件是以功能來劃分問題，而不是步驟，同樣是繪制棋局，這樣的行為在面向程序的設計中分散在了總多步驟中，很可能出現不同的繪制版本，因為通常設計人員會考慮到實際情況進行各種各樣的簡化，而面向物件的設計中，繪圖只可能在棋盤物件中出現，從而保證了繪圖的統一，
功能上的統一保證了面向物件設計的可擴展性，比如我要加入悔棋的功能，如果要改動面向程序的設計，那么從輸入到判斷到顯示這一連串的步驟都要改動，甚至步驟之間的循序都要進行大規模調整，如果是面向物件的話，只用改動棋盤物件就行了，棋盤系統保存了黑白雙方的棋譜，簡單回溯就可以了，而顯示和規則判斷則不用顧及，同時整個對物件功能的呼叫順序都沒有變化，改動只是區域的，
把這個五子棋游戲改為圍棋游戲，如果你是面向程序設計，那么五子棋的規則就分布在了你的程式的每一個角落，要改動還不如重寫，但是如果你當初就是面向物件的設計，那么你只用改動規則物件就可以了，五子棋和圍棋的區別不就是規則嗎？而下棋的大致步驟從面向物件的角度來看沒有任何變化，
面向程序就像兩條生產不同型別汽車的流水線，面向物件則是生產出玻璃，底盤等等后再分給不同的汽車，

3.什么是抽象（PPT的P62相關內容帶著看，不能局限于只知道什么是抽象）

所謂抽象是從眾多的事物中抽出與問題相關的最本質的屬性，而忽略或隱藏與認識問題，求解問題無關的非本質的屬性，
抽象的程序
舉栗：
蘋果，香蕉和梨子 ——水果

一切科學抽象程序都具有以下環節：分離—提純—簡略，

第四章：

1.什么是演算法

演算法是解決問題的方法和步驟，通常把解題程序準確而完整的描述稱之為解該題的演算法，

2.演算法和程式的區別

程式是為解決特定問題的計算機語言有窮操作規則（即低級語言的指令，高級語言的陳述句）的有序集合，
程式=資料結構+演算法
程式是在資料的某些特定的表示方式和結構基礎之上，對抽象演算法的計算機的語言具體表述

演算法和程式的差異與聯系，

1. 一個程式不一定滿足有窮性，但一個演算法必須是有窮的，
2. 程式中的指令必須是機器可執行的，而演算法中的指令則無此限制，
3. 演算法代表了對問題的解，而程式則是演算法在計算機上的特定的實作，
4. 演算法側重問題的解決方法和步驟，程式側重于機器上的實作，
5. 樹干（演算法），樹（程式），
6. 程式=資料結構+演算法，

3.演算法怎么表示的，它的時間空間復雜度是什么

描述演算法的方式（書P148有具體的）

1. 自然語言
2. 計算機語言
3. 圖形化工具
4. 偽代碼

演算法的時間復雜度
簡單地說，執行一個演算法所需要的時間
演算法的空間復雜度
簡單的說，執行一個演算法所需要的空間

4.分清演算法和程式，分清演算法和偽代碼、偽代碼、流程圖（書P153）

5.演算法是否要求有輸入和輸出

允許演算法沒有輸入量，但是每種演算法必須有確定的結果，產生一個或多個輸出，

6.一個實戰性的演算法：遞推、遞回、回溯、分治 4挑1（大概率在后三個中）

分治法：歸并排序、快速排序
回溯法：DFS

插入排序（可不看）

快速排序（以下為代碼片段，考試時請寫偽代碼）

歸并排序（以下為代碼片段，考試時請寫偽代碼）

第五章：（注意一下 網頁排序）

1.網頁排序（書P208，PPT第五章P10）

1. 超鏈接技術
2. 權重技術
3. 隨機訪問模型

2.編碼（奇偶校驗碼怎么執行的，怎么校驗的，是否一定可以校驗出偶數個錯誤（上課講過了的，什么情況下能校驗出偶數個錯誤，什么情況下不行），PPT上的舉例子）

①什么是奇偶校驗碼

奇偶校驗碼也是一種校驗碼，它用來檢測資料傳輸程序中是否發生錯誤，是眾多校驗碼中最為簡單的一種，
顧名思義，它有兩種校驗方法：奇校驗和偶校驗
奇校驗：原始碼流+校驗位 總共有奇數個1
偶校驗：原始碼流+校驗位 總共有偶數個1
相關博客

②

栗子：
奇偶校驗碼一個最為常見的應用場合就是ASCII碼，ASCII碼占用一個位元組，低7位是有效位，最高位用作奇偶校驗，

3.哈夫曼編碼（大概率考）多練練（書P253）

把資訊中排除了冗余后的平均資訊量稱為“資訊熵”，資訊熵表示無序的資訊，
哈夫曼編碼所得的編碼長度只是對資訊熵計算結果的一種近似，無法真正逼近資訊熵的極限，

第六章：大概率不考

第七章：（考兩題）

1.方程的求根（牛頓法、迭代法）

P294 7.1.2迭代法
P296 7.1.3牛頓法

2.蒙特卡洛法

P324 7.6蒙特卡洛法
基于概率的演算法，要從本質理解，為什么可以，基于什么定理，為什么可以執行，結果是概率性的為什么我們還要用呢？（<-要區分開）

完結，撒花
未完待續