奧賽考前復習基礎全解奧賽考前復習基礎全解奧賽考前復習基礎全解2.計算機常識2.1計算機結構與組成原理1.組成：（1）運算器（2）控制器（3）存儲器（4）輸人設備（5）輸出設備2.1.22.組成（2）中引入了高速緩存2021/1/422.計算機常識2.1計算機結構與組成原理1.組成：（1）運算器（2）控制器（3）存儲器（4）輸人設備（5）輸出設備2.1.22.組成（2）中引入了高速緩存2021/1/422.參數：（1）主頻：“奔騰2.8”每秒運算次數是2.8*2^30（2）字長:能同時處理32位的二進制數,決定處理精度。32/64位3.目前品牌型號（1）計算機：、系列、系列（2）432位。(安騰)以后（i3i5i7）是64位（3）64速龍、(皓龍)是64位（4）3以及隨后是64位2021/1/434.移動終端品牌型號（1）高通()7227、7230、8250、8255（2）德州儀器()，簡稱，3430和3630（3）英偉達()2雙核處理器2021/1/442.1.3存儲器1.分類2.速度：高速緩存器>內存速度>外存速度3.斷電后信息的保存：以下斷電之后不能保存數據的有（）A.內存1高速緩存卡E.寄存器2021/1/454．儲存單位（1）位（比特）、字節（）千字節（）兆字節（）（2）速率單位（聲音，視頻，網絡）：<=><=><=><=><=><=>（3）大B小b有區別的，一個是，一個是，所以和是不一樣的，比如說“寬帶512”2021/1/462.1.41.基本輸入輸出系統：只存系統啟動的基本信息，不存設備驅動程序2.存放位置：主板上的存儲器2021/1/472.1.5計算機的三總線結構1.總線是一組導線、是公共通路，微型計算機中各個組成部件之間的信息傳輸都是通過它們來實現的2.分類（1）地址總線()是單向總線，用以傳送向外設或存儲器發出的地址信息。（2）數據總線()是雙向總線，用以與內存或接口之間傳輸數據信息。（3）控制總線()是雙向總線，有的作為輸出，有的作為輸入，用以與內存或接口之間傳送控制信息。3.分別傳送地址信號、數據信號和控制信號2021/1/481.中央處理器（）能訪問的最大存儲器容量取決于（）。A.地址總線B.數據總線C.控制總線D.實際內存容量16.地址總線的位數決定了可直接尋址的內存空間大小，例如地址總線為16位，其最大的可尋址空間為64。如果地址總線是32位，則理論上最大可尋址的內存空間為（）。A.128B.1C.1D.4AD2021/1/492.2計算機軟件系統１.系統軟件：（１）操作系統軟件：,2，,,7（２）計算機語言:①機器語言:②匯編語言與具體硬件相關、可以直接訪問寄存器、內存單元、端口；代碼量較大，且不易調試、不易移植③高級語言：面向過程面向對象：是第一個面向對象的語言編譯器將高級語言轉變為目標代碼２.應用軟件：(),3等.3.程序設計語言的定義一般應包（語法、語義和語用）幾個方面。2021/1/4103.在面向對象技術中，（）不是對象A．窗口B．控件C．菜單項D．函數E.字體4.（17）匯編語言（）。A.是一種與具體硬件無關的程序設計語言B.在編寫復雜程序時，相對于高級語言而言代碼量較大，且不易調試C.可以直接訪問寄存器、內存單元、端口D.隨著高級語言的誕生，如今已完全被淘汰，不再使用3.在一次內存限制為50的比賽中，最多能申請一個大小為（）的類型為的數組A.10^6B.10^7C.10^8D.10^9DB50*(2^20)*8/32=131072002021/1/4112.4.5計算機安全1.計算機病毒是一種功能較特殊的計算機程序，特征可以歸納為下面兩點：⑴能夠將自身復制到其他程序中。⑵不獨立以文件形式存在，僅附加在別的程序上。2.安全措施：補丁、殺毒軟件3.防火墻：防外部攻擊11.計算機病毒傳染的必要條件是()。A.在內存中運行病毒程序B.對磁盤進行讀寫操作C.在內存中運行含有病毒的程序D.復制文件C2021/1/4122.6編碼基礎2.6.1碼（1）碼概述：是用來表示英文字符的一種編碼規范。每個字符占用1個字節，（2）編碼可以表示的最大字符數是256（00H—）3.常見的值2021/1/4132.6.2碼1的產生：解決碼編碼數量不足問題，2它占用兩個字節（0000H—）,容納65536個字符2.6.3漢字編碼基礎字型碼:48X48點陣的一個漢字的字型碼要用288字節來表示區位碼：按國標規定，漢字編碼表有94行94列，其行號01~94稱為區號，列號01~94稱為位號。3.國標碼：又稱為“交換碼”,也是通過區位碼找漢字，國標碼=（區位碼）16+(2020)164.機內碼：針對計算機，也是通過區位碼找漢字，機內碼=（區位碼）16+(A0A0)165.外碼(輸入碼):智能搜狗

2021/1/4141.組成’教授’（）’副教授’（）與’講師’（）這三個詞的漢字，在2312－80字符集中都是一級漢字．對這三個詞排序的結果是（）。A．教授，副教授，講師B．副教授，教授，講師C．講師，副教授，教授D．副教授，講師，教授D2021/1/4152.7數據庫技術1．關系型數據庫：2.關系型數據庫數據的邏輯結構：二維表3.數據冗余：2021/1/4162.8多媒體1.視頻壓縮標準的有:2．矢量圖：具有伸縮性分辨率不變,對圖像進行縮放和旋轉時不易失真，不易制作出豐富多彩的圖像，數據量小。點陣圖：放大后分辨率降低，易失真2021/1/4172.9.1計算機發展史1.第一臺電子計算機的誕生：1946年賓夕法尼亞大學約翰·莫克利（）和普雷斯伯·埃克特（）2．馮·諾依曼——第一臺具有存儲程序功能的計算機：（1）馮·諾依曼:提出了“存儲程序”（2）同相比，方案有兩個重大改進：①采用了二進制；②提出了“存儲程序”“和程序控制”（3）運算器、控制器、存儲器、輸人設備和輸出設備這五部分2021/1/4183.圖靈——人工智能（1）艾倫·麥席森·圖靈（912年6月23日-1954年6月7日），英國數學家（2）圖靈機由三部分組成，包括一條帶子、一個讀寫頭和一個控制裝置。（3）圖靈對于人工智能的發展有諸多貢獻，，其中提出了一種用于判定機器是否具有智能的試驗方法，即圖靈試驗。（3）圖靈獎是美國計算機協會于1966年設立的，又叫".圖靈獎"，專門獎勵那些對計算機事業作出重要貢獻的個人。其名稱取自計算機科學的先驅、英國科學家艾倫·圖靈，這個獎設立目的之一是紀念這位科學家。4.:——被稱為世界上”第一位程序員”5.香農——信息論鼻祖2021/1/4196.萬維網聯盟（W3C）7.計算機發展階段：電子管晶體管中小規模集成電路大規模／超大規模集成電路半導體的研究與摩爾定律塊集成電路的集成度大約每（18）個月翻一番2021/1/4203.離散數學1.五種重要的聯結詞有：

否定（﹁）、合?。ā模?、析?。ā牛?、條件（→）、雙條件（）分配律A∨(B∧C)（A∨B)∧(A∨C)A∧(B∨C)（A∧B)∨(A∧C)德·摩根律(A∧B)A∨B(A∨B)A∧B2021/1/4213.3集合1、集合的運算：并、交、補、差2、容斥原理：在計數時，為了使重疊部分不被重復計算，人們研究出一種新的計數方法，這種方法的基本思想是：先不考慮重疊的情況，把包含于某內容中的所有對象的數目先計算出來，然后再把計數時重復計算的數目排斥出去，使得計算的結果既無遺漏又無重復，這種計數的方法稱為容斥原理。2021/1/4221、（10）75名兒童到游樂場去玩。他們可以騎旋轉木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費用是5元，游樂場總共收入700，可知有10名兒童沒有玩過其中任何一種玩過3種的人數：20人玩過2種的人數:55-20=35人只玩過1種的人所花費用：700-20*15-35*10=50元只玩過1種的人數：50/5=10人沒玩過的人數：70-20-35-10=10人2021/1/4232.某學校足球隊有球衣30件，籃球隊有球衣15件，排球隊有球衣18件，三隊隊員總數為50人，其中有2人同時參加3個隊，則同時只參加兩個隊的隊員有多少？足球A，籃球B,排球C（1）∪B∪++-∩-∩-∩∩B∩=30+15+182=50→15→∩+∩+∩15（2）∩+∩+∩中三個都參加的加了3次。（3）只參加2個的隊員：15-6=9解法2，去掉同時參加3個隊2人（1）∪B∪++-∩-∩-∩=28+13+16=48→9（2）只參加2個的隊員：15-6=9３.類似求能被357整除1000以內數的個數2021/1/4245.時間復雜度2.計算快速排序時間復雜度T(N)=2T(2)22T(22)=2(2h)…設21→2N上例中共有h個N相加T(N)×N×2N2021/1/4255.4P類與類問題5.4.1多項式時間算法2021/1