NOIP初賽知識點綜述

初賽知識復(fù)習(xí)初賽試題形式

●初賽：初賽全部為筆試，滿分100分。試題由四部分組成：

1、選擇題：共20題，每題1.5分，共計30分。每題有5個備選答案，前10個題為單選題(即每題有且只有一個正確答案，選對得分)，后10題為不定項選擇題(即每題有1至5個正確答案，只有全部選對才得分)。

2、問題求解題：共2題，每題5分，共計10分。試題給出一個敘述較為簡單的問題，要求學(xué)生對問題進(jìn)行分析，找到一個合適的算法，并推算出問題的解。考生給出的答案與標(biāo)準(zhǔn)答案相同，則得分：否則不得分。

3、程序閱讀理解題：共4題，每題8分，共計32分。題目給出一段程序(不一定有關(guān)于程序功能的說明)，考生通過閱讀理解該段程序給出程序的輸出。輸出與標(biāo)準(zhǔn)答案一致，則得分；否則不得分。

4、程序完善題：共2題，每題14分，共計28分。題目給出一段關(guān)于程序功能的文字說明，然后給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分并在這些位置給出空格，要求考生根據(jù)程序的功能說明和代碼的上下文，填出被略去的語句。填對則得分；否則不得分。

知識范圍內(nèi)容與要求

1、計算機(jī)的基本常識●計算機(jī)和信息社會(信息社會的主要特征、計算機(jī)的主要特征、數(shù)字通信網(wǎng)絡(luò)的主要特征、數(shù)字化)●信息輸入輸出基本原理(信息交換環(huán)境、文字圖形多媒體信息的輸入輸出方式)●信息的表示與處理(信息編碼、微處理部件MPU、內(nèi)存儲結(jié)構(gòu)、指令，程序，和存儲程序原理、程序的三種基本控制結(jié)構(gòu))●信息的存儲、組織與管理(存儲介質(zhì)、存儲器結(jié)構(gòu)、文件管理、數(shù)據(jù)庫管理)●信息系統(tǒng)組成及互連網(wǎng)的基本知識(計算機(jī)構(gòu)成原理、槽和端口的部件間可擴(kuò)展互連方式、層次式的互連結(jié)構(gòu)、互聯(lián)網(wǎng)絡(luò)、TCP／IP協(xié)議、HTTP協(xié)議、WEB應(yīng)用的主要方式和特點)●人機(jī)交互界面的基本概念(窗口系統(tǒng)、人和計算機(jī)交流信息的途徑(文本及交互操作))●信息技術(shù)的新發(fā)展、新特點、新應(yīng)用等。2、計算機(jī)的基本操作●WINDOWS和LINUX的基本操作知識●聯(lián)網(wǎng)的基本使用常識(網(wǎng)上瀏覽、搜索和查詢等)●常用的工具軟件使用(文字編輯、電子郵件收發(fā)等)3、程序設(shè)計的基本知識數(shù)據(jù)結(jié)構(gòu)●程序語言中基本數(shù)據(jù)類型(字符、整數(shù)、長整數(shù)、浮點)●浮點運算中的精度和數(shù)值比較●一維數(shù)組(串)與線性表●記錄類型(PASCAL)／結(jié)構(gòu)類型(C)

程序設(shè)計●結(jié)構(gòu)化程序設(shè)計的基本概念●閱讀理解程序的基本能力●具有將簡單問題抽象成適合計算機(jī)解決的模型的基本能力●具有針對模型設(shè)計簡單算法的基本能力●程序流程描述(自然語言／偽碼／NS圖／其他)●程序設(shè)計語言(PASCAL／C／C++，)

基本算法處理●初等算法(計數(shù)、統(tǒng)計、數(shù)學(xué)運算等)●排序算法(冒泡法、插入排序、合并排序、快速排序)●查找(順序查找、二分法)●回溯算法◆

計算機(jī)結(jié)構(gòu)與組成原理◆基本的數(shù)學(xué)知識

（集合的運算、排列與組合）◆

計算機(jī)結(jié)構(gòu)與組成原理

一、計算機(jī)發(fā)展及應(yīng)用1、第一臺電子計算機(jī)的誕生：ENIAC1946年，世界上第一臺數(shù)字式電于計算機(jī)是由美固賓夕法尼亞大學(xué)的物理學(xué)家約翰·莫克利（JohnMauchly）和工程師普雷斯伯·?？颂兀↗.hesper.Eckert）領(lǐng)導(dǎo)研制的取名為ENIAC（ElecotmnicNurnericalIntegratorAndCalculator）的計算杌。2、第一臺具有存儲程序功能的計算機(jī)：EDVAC。馮·諾依曼依據(jù)存儲程序的工作原理設(shè)計.運算器、控制器、存儲器、輸人設(shè)備和輸出設(shè)備這五部分組成，同ENIAC相比，EDVAC方案有兩個重大改進(jìn)：（1）：采用了二進(jìn)制；（2）：提出了“存儲程序”，

1903年，馮·諾伊曼（Neumann，Johnvon）出生于匈牙利的布達(dá)佩斯考題:NOIP101、美籍匈牙利數(shù)學(xué)家馮·諾依曼對計算機(jī)科學(xué)發(fā)展所做出的貢獻(xiàn)包括（）。A)提出理想計算機(jī)的數(shù)學(xué)模型，成為計算機(jī)科學(xué)的理論基礎(chǔ)。B)

提出存儲程序工作原理，對現(xiàn)代電子計算機(jī)的發(fā)展產(chǎn)生深遠(yuǎn)影響。C)

設(shè)計出第一臺具有存儲程序功能的計算機(jī)EDVAC。D)采用集成電路作為計算機(jī)的主要功能部件。E)指出計算機(jī)性能將以每兩年翻一番的速度向前發(fā)展。①圖靈(AlanTuring)是（

）。(NOIP9)

A）美國人

B）英國人

C）德國人

D）匈牙利人

艾倫·麥席森·圖靈（AlanMathisonTuring，1912年6月23日-1954年6月7日），英國數(shù)學(xué)家圖靈機(jī)由三部分組成，包括一條帶子、一個讀寫頭和一個控制裝置。圖靈對于人工智能的發(fā)展有諸多貢獻(xiàn)，例如：圖靈曾寫過一篇名為《機(jī)器會思考嗎？》（CanMachineThink?）的論文，其中提出了一種用于判定機(jī)器是否具有智能的試驗方法，即圖靈試驗。圖靈獎是美國計算機(jī)協(xié)會于1966年設(shè)立的，又叫"A.M.圖靈獎"，專門獎勵那些對計算機(jī)事業(yè)作出重要貢獻(xiàn)的個人。其名稱取自計算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家艾倫·圖靈，這個獎設(shè)立目的之一是紀(jì)念這位科學(xué)家。B3.在下面各世界頂級的獎項中，為計算機(jī)科學(xué)與技術(shù)領(lǐng)域作出杰出貢獻(xiàn)的科學(xué)家設(shè)立的獎項是（）。noip12A.沃爾夫獎B.諾貝爾獎C.菲爾茲獎D.圖靈獎

E.南丁格爾獎11.在下列關(guān)于圖靈獎的說法中，正確的有（）。noip14A.圖靈獎是美國計算機(jī)協(xié)會于1966年設(shè)立的，專門獎勵那些對計算機(jī)事業(yè)作出重要貢獻(xiàn)的個人B.

圖靈獎有“計算機(jī)界諾貝爾獎”之稱C.迄今為止，還沒有華裔計算機(jī)科學(xué)家獲此殊榮D.

圖靈獎的名稱取自計算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家阿蘭·圖靈2000AndrewChi-ChihYao---PhD,UIUC;Prof,Princeton(nowat清華)因?qū)τ嬎憷碚撟龀隽酥T多根本性的重大貢獻(xiàn).(圖靈獎自創(chuàng)立以來獲得該獎項的首位華裔學(xué)者,全球華人的驕傲)

②第一個給計算機(jī)寫程序的人是（

）。(NOIP9)

A）AlanMathisonTuring

B）AdaLovelace

C）JohnvonNeumannD）JohnMc-Carthy

E）EdsgerWybeDijkstr1、英國著名詩人拜倫的女兒AdaLovelace(愛達(dá)).由于她在程序設(shè)計上的開創(chuàng)性工作，AdaLovelace被稱為世界上”第一位程序員”?！笆澜缟系谝晃卉浖こ處煛?。

2、董鐵寶是“中國第一個程序員”。董鐵寶1945年赴美國學(xué)習(xí)，在伊利諾伊大學(xué)學(xué)習(xí)、研究時，他參與了第一代電子計算機(jī)伊利亞克機(jī)的設(shè)計、編程和使用。董鐵寶于1956年回到中國并任教于北京大學(xué)，成為王選（計算數(shù)學(xué)專業(yè)院士）的老師。董鐵寶在1968年文化大革命期間自殺身亡。B3、計算機(jī)發(fā)展的幾個階段

第一代（1946～1958）第二代（1958～1964）第三代（1964～1975）第四代（1975～至今）主要電子器件電子管晶體管中小規(guī)模集成電路大規(guī)模／超大規(guī)模集成電路①微型計算機(jī)的問世是由于（）的出現(xiàn)。(NOIP8)A）中小規(guī)模集成電路B）晶體管電路C）（超）大規(guī)模集成電路D）電子管電路C4、計算機(jī)應(yīng)用⑴科學(xué)計算（數(shù)值計算）。⑵數(shù)據(jù)處理（信息處理）。⑶人工智能。⑷自動控制。⑸計算機(jī)輔助設(shè)計和制造：CAI

（計算機(jī)輔助教學(xué)）CAM

（計算機(jī)輔助制造）CAT（計算機(jī)輔助測試）CAD（計算機(jī)輔助設(shè)計）CAE(計算機(jī)輔助教育)CIMS（計算機(jī)集成制造系統(tǒng)）二、保護(hù)知識產(chǎn)權(quán)：《計算機(jī)軟件保護(hù)條例》最早是1991年6月4日國務(wù)院發(fā)布的<<計算機(jī)軟件保護(hù)條例>>，現(xiàn)已廢止?，F(xiàn)公布《計算機(jī)軟件保護(hù)條例》，自2002年1月1日起實施

。第二章軟件著作權(quán)第八條

軟件著作權(quán)人享有下列各項權(quán)利：（一）發(fā)表權(quán)（二）署名權(quán)（三）修改權(quán)（四）復(fù)制權(quán)；（五）發(fā)行權(quán)（六）出租權(quán)（七）信息網(wǎng)絡(luò)傳播權(quán)（八）翻譯權(quán)（九）應(yīng)當(dāng)由軟件著作權(quán)人享有的其他權(quán)利。①計算機(jī)軟件保護(hù)法是用來保護(hù)軟件()的（NOIP7）

A)編寫權(quán)B)復(fù)制權(quán)C)使用權(quán)D)著作權(quán)D三、計算機(jī)病毒計算機(jī)病毒是一種功能較特殊的計算機(jī)程序，計算機(jī)病毒的特征可以歸納為下面兩點：⑴能夠?qū)⒆陨韽?fù)制到其他程序中。⑵不獨立以文件形式存在，僅附加在別的程序上。失去這兩個特征中的任何一個，都不成其為病毒。①計算機(jī)病毒是()(NOIP7)

A)通過計算機(jī)傳播的危害人體健康的一種病毒

B)人為制造的能夠侵入計算機(jī)系統(tǒng)并給計算機(jī)帶來故障的程序或指令集合

C)一種由于計算機(jī)元器件老化而產(chǎn)生的對生態(tài)環(huán)境有害的物質(zhì)

D)利用計算機(jī)的海量高速運算能力而研制出來的用于疾病預(yù)防的新型病毒②計算機(jī)病毒的特點是（）(NOIP6)

A.傳播性、潛伏性、易讀性與隱蔽性B.破壞性、傳播性、潛伏性與安全性

C.傳播性、潛伏性、破壞性與隱蔽性D.傳播性、潛伏性、破壞性與易讀性

③計算機(jī)病毒傳染的必要條件是：（）。(NOIP8)A）在內(nèi)存中運行病毒程序B）對磁盤進(jìn)行讀寫操作

C）在內(nèi)存中運行含有病毒的可執(zhí)行的程序D）復(fù)制文件BCB四、計算機(jī)系統(tǒng)的組成：1、硬件系統(tǒng)2、軟件系統(tǒng)只有硬件沒有安裝軟件的計算機(jī)稱為“裸機(jī)”1、硬件系統(tǒng)的組成：五個基本部分組成：（1）運算器（2）控制器（3）存儲器（4）輸人設(shè)備（5）輸出設(shè)備輸入設(shè)備運算器存儲器控制器輸出設(shè)備輸入輸出1）運算器+控制器=CPU:中央處理器（CenterProcessUnit）計算機(jī)的核心部件(指揮系統(tǒng))直接決定計算機(jī)的運行速度。如：計算機(jī)的配置：“Intel奔騰IV2.8GHz/512M/80GB/50X”

每秒運算次數(shù)是：2.8*210*210*2102）存儲器◆外存儲器：硬盤、光盤、軟盤、優(yōu)盤等?！魞?nèi)存儲器：ROM和RAMROM:ReadOnlyMemory：只讀存儲器

RAM:RandomAccessMemory：隨機(jī)存取存儲器

平時說的內(nèi)存：RAM：256MB,512MB,1GMB◆高速緩存器：cache◆高速緩存器>內(nèi)存速度>外存速度主機(jī)的概念：包括：CPU和內(nèi)存儲器①CPU訪問內(nèi)存的速度比訪問下列哪個（些）存儲設(shè)備要慢（

）。（NOIP9）

A）寄存器

B）硬盤

C）軟盤

D）高速緩存

E）光盤②微型計算機(jī)中，（）的存取速度最快。(NOIP8)A）高速緩存B）外存儲器C）寄存器D）內(nèi)存儲器③在計算機(jī)硬件系統(tǒng)中，cache是()存儲器(NOIP7)

A)只讀B)可編程只讀C)可擦除可編程只讀D)高速緩沖ADAD4、下面哪個部件對于個人桌面電腦的正常運行不是必需的（）。NOIP10

A.CPUB.圖形卡（顯卡）C.光驅(qū)D.主板E.內(nèi)存５、用靜電吸附墨粉后轉(zhuǎn)移到紙張上，是哪種輸出設(shè)備的工作方式（）。NOIP10

A.針式打印機(jī)B.噴墨打印機(jī)C.激光打印機(jī)D.筆式繪圖儀E.噴墨繪圖儀６、下列哪個（些）不是計算機(jī)的存儲設(shè)備（）。NOIP10A.文件管理器B.內(nèi)存C.顯卡D.硬盤E.U盤７、下列說法中正確的有（）。NOIP10

A.CPU的基本功能就是執(zhí)行指令。

B.CPU的主頻是指CPU在1秒內(nèi)完成的指令周期數(shù)，主頻越快的CPU速度一定越快。

C.內(nèi)部構(gòu)造不同的CPU運行相同的機(jī)器語言程序，一定會產(chǎn)生不同的結(jié)果。

D.在一臺計算機(jī)內(nèi)部，一個內(nèi)存地址編碼對應(yīng)唯一的一個內(nèi)存單元。

E.數(shù)據(jù)總線的寬度決定了一次傳遞數(shù)據(jù)量的大小，是影響計算機(jī)性能的因素之一。８、彩色顯示器所顯示的五彩斑斕的色彩，是由哪三色混合而成的（）。NOIP10A.紅B.白C.藍(lán)D.綠E.橙９、下列哪個（些）是64位處理器（）。NOIP10A.IntelItaniumB.IntelPentiumIIIC.AMDAthlon64D.AMDOpteronE.IBMPower5C,C,AC,ADE,ACD,ACDENOIP116.下列設(shè)備中沒有計算功能的是（）。

A.筆記本電腦B.掌上電腦C.智能手機(jī)D.電子計算器E.液晶顯示器

7.Intel的首顆64位處理器是（）。

A.8088B.8086C.80386D.80486E.Pentium

15.下列外設(shè)接口中可以通過無線連接的方式連接設(shè)備的是（）。

A.USB2.0高速版B.紅外C.藍(lán)牙D.串口E.IEEE802.11g無線網(wǎng)卡

17.以下哪個（些）不是計算機(jī)的輸出設(shè)備（）。

A.鼠標(biāo)B.顯示器C.鍵盤D.掃描儀E.繪圖儀

18.以下斷電之后將不能保存數(shù)據(jù)的有（）。

A.硬盤B.寄存器C.顯存D.內(nèi)存E.高速緩存

E,E,BCE,ACD,BCDE17.以下斷電之后將不能保存數(shù)據(jù)的有（）。noip12A.硬盤B.ROMC.顯存D.RAM17.以下斷電之后仍能保存數(shù)據(jù)的有（）。noip13A.硬盤B.ROMC.顯存D.RAM12．計算機(jī)在工作過程中，若突然停電，（）中的信息不會丟失。noip14A.硬盤B.CPUC.ROMD.RAM2．微型計算機(jī)中，控制器的基本功能是（）。noip14A.控制機(jī)器各個部件協(xié)調(diào)工作B.實現(xiàn)算術(shù)運算和邏輯運算C.存儲各種控制信息D.獲取外部信息E.存放程序和數(shù)據(jù)1.在以下各項中，（）不是CPU的組成部分。noip13A.控制器B.運算器C.寄存器D.主板E.算術(shù)邏輯單元(ALU)1.在以下各項中。（）不是CPU的組成部分。noip12A.控制器B.運算器C.寄存器D.ALUE.RAM2、BIOS（基本輸入輸出系統(tǒng)）是一組固化在計算機(jī)內(nèi)（）上一個ROM芯片上的程序。noip12A.控制器B.CPUC.主板D.內(nèi)存條E.硬盤2、計算機(jī)的三總線結(jié)構(gòu)：

總線是一組導(dǎo)線、是公共通路，微型計算機(jī)中各個組成部件之間的信息傳輸都是通過它們來實現(xiàn)的地址總線(AB)是單向總線，用以傳送CPU向外設(shè)或存儲器發(fā)出的地址信息。

數(shù)據(jù)總線(DB)是雙向總線，用以CPU與內(nèi)存或接口之間傳輸數(shù)據(jù)信息。

控制總線(CB)是雙向總線，有的作為輸出，有的作為輸入，用以CPU與內(nèi)存或I/O接口之間傳送控制信息。分別傳送地址信號、數(shù)據(jù)信號和控制信號。①中央處理器（CPU）能訪問的最大存儲器容量取決于（）。(NOIP8NOIP7)A）地址總線B）數(shù)據(jù)總線C）控制總線D）實際內(nèi)存容量②計算機(jī)系統(tǒng)總線上傳送的信號有（）(NOI6)

A.地址信號與控制信號B.數(shù)據(jù)信號、控制信號與地址信號

C.控制信號與數(shù)據(jù)信號D.數(shù)據(jù)信號與地址信號

AB二）軟件系統(tǒng)包括：１、系統(tǒng)軟件：（１）操作系統(tǒng)軟件：

dos,OS/2

，windows95,windows98,windows2000,windowsxpwindowsServer,windowsNT,unix,linux，Netware

，WindowsVista

（２）計算機(jī)語言:機(jī)器語言：由0和1組成的二進(jìn)制，計算機(jī)可直接識別，低級語言匯編語言：由偽指令編寫，低級語言

高級語言：面向過程：basic（解釋型）,pascal、c（編譯型）面向?qū)ο螅篶++,viscalbasic，java等２、應(yīng)用軟件：為完成某項具體的功能而開發(fā)的軟件。如：office(word,powerpoin,excel),3dmax,flash,photoshop等.（3）數(shù)據(jù)庫管理系統(tǒng):如：MySQL、SQLServer、Oracle、Foxpro、FoxBase、SyBase、VisualFoxpro等什么是面向?qū)ο蟪绦蛟O(shè)計（模塊化）：面向?qū)ο蟪绦蛟O(shè)計（英語：ObjectOrientedProgramming，縮寫：OOP），指一種程序設(shè)計范型，同時也是一種程序開發(fā)的方法論。它將對象作為程序的基本單元，將程序和數(shù)據(jù)封裝其中，以提高軟件的重用性、靈活性和擴(kuò)展性。20世紀(jì)70年代的SmallTalk語言在面向?qū)ο蠓矫婵胺Q經(jīng)典--以至于30年后的今天依然將這一語言視為面向?qū)ο笳Z言的基礎(chǔ)。傳統(tǒng)的面向過程程序設(shè)計面向?qū)ο笳Z言(Object-OrientedLanguage)是一類以對象作為基本程序結(jié)構(gòu)單位的程序設(shè)計語言一種是純面向?qū)ο笳Z言，如Smalltalk、EIFFEL等。混合型面向?qū)ο笳Z言，即在過程式語言及其它語言中加入類、繼承等成分，如C++、Objective-C等。VisualBasic，VisualC++,Java等1、下列哪個（些）不是數(shù)據(jù)庫軟件的名稱（）。NIOP10A.MySQLB.SQLServerC.OracleD.OutlookE.Foxpro2、下列哪個（些）軟件屬于操作系統(tǒng)軟件（）。NIOP10A.MicrosoftWordB.WindowsXPC.FoxmailD.金山影霸

E.RedHatLinux3、下列哪個（些）程序設(shè)計語言支持面向?qū)ο蟪绦蛟O(shè)計方法（）。NIOP10A.C++B.ObjectPascalC.CD.SmalltalkE.Java4、下列哪個（些）軟件不是操作系統(tǒng)軟件的名字（

）。NOIP9

A）WindowsXP

B)DOS

C)Linux

D)OS/2

E)Arch/Info5、

在以下各項中，（）不是操作系統(tǒng)軟件。noip14 SolarisB.LinuxC.SybaseD.WindowsVistaE.SymbianSolaris是SunMicrosystems研發(fā)的計算機(jī)操作系統(tǒng)。它被認(rèn)為是UNIX操作系統(tǒng)的衍生版本之一。18.在下列關(guān)于計算機(jī)語言的說法中，正確的有（）。noip13A.高級語言比匯編語言更高級，是因為它的程序的運行效率更高B.隨著Pascal、C等高級語言的出現(xiàn)，機(jī)器語言和匯編語言已經(jīng)退出了歷史舞臺C.高級語言程序比匯編語言程序更容易從一種計算機(jī)移植到另一種計算機(jī)上D.C是一種面向過程的高級計算機(jī)語言18.在下列關(guān)于計算機(jī)語言的說法中，正確的有（）。noip12A.Pascal和C都是編譯執(zhí)行的高級語言B.高級語言程序比匯編語言程序更容易從一種計算機(jī)移植到另一種計算機(jī)上C.C++是歷史上的第一個支持面向?qū)ο蟮挠嬎銠C(jī)語言D.高級語言比匯編語言更高級，是因為它的程序的運行效率更高Simula語言五、計算機(jī)指令系統(tǒng)計算機(jī)能直接識別和執(zhí)行的命令稱為指令。指令本身是二進(jìn)制代碼。是要計算機(jī)執(zhí)行某種操作的命令。用機(jī)器指令編寫的程序稱之為機(jī)器語言程序。一條指令通常由操作碼和地址碼兩部分組成。六、計算機(jī)的數(shù)字系統(tǒng)數(shù)值信息在計算機(jī)內(nèi)的表示方法就是用二進(jìn)制數(shù)來表示。一般說來，如果數(shù)制只采用R個基本符號，則稱為基R數(shù)值，R稱為數(shù)制的基數(shù)，而數(shù)制中每一固定位置對應(yīng)的單位值稱為權(quán)。進(jìn)制基數(shù)R基本符號二進(jìn)制20，1八進(jìn)制80,1,2,3,4,5,6,7十進(jìn)制100,1,2,3,4,5,6,7,8,9十六進(jìn)制160,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F（對應(yīng)十進(jìn)制數(shù)的10—15。）進(jìn)位計數(shù)制的編碼符合“逢R進(jìn)位”的規(guī)則，各位的權(quán)是以R為底的冪，一個數(shù)可按權(quán)展開成為多項式。例如，一個十進(jìn)制數(shù)256.47可按權(quán)展開為256.47=2×102＋5×101＋6×10°十4×10-1＋7×10-21、R進(jìn)制轉(zhuǎn)換為十進(jìn)制基數(shù)為R的數(shù)字，只要將各位數(shù)字與它的權(quán)相乘，其積相加,和數(shù)就是十進(jìn)制數(shù)例:3506.28=6×8°+0×81+5×82+3×83+2×8-1=1862.25

例:0.2A16=2×16-1+10×16-2

=0.16406252、十進(jìn)制轉(zhuǎn)換為R進(jìn)制＋進(jìn)制整數(shù)轉(zhuǎn)換成R進(jìn)制的整數(shù):除R取余法。十進(jìn)制小數(shù)轉(zhuǎn)換成R進(jìn)制時:乘R取整.例：將0.312510轉(zhuǎn)換成二進(jìn)制數(shù)0.3125×2=0.6250.625×2=1.250.25×2=0.50.5×2=1.0所以0.312510=0.010123、二、八、十六進(jìn)制的相互轉(zhuǎn)換每位八進(jìn)制數(shù)相當(dāng)于三位二進(jìn)制數(shù)，每位十六進(jìn)制數(shù)相當(dāng)于四位二進(jìn)制數(shù)。在轉(zhuǎn)換時，位組劃分是以小數(shù)點為中心向左右兩邊延伸，中間的0不能省略，兩頭不夠時可以補(bǔ)0。尤其是小數(shù)后末尾的0例如：將1011010.12轉(zhuǎn)換成八進(jìn)制和十六進(jìn)制數(shù)001011010.1001011010.12＝132.48132.401011010.10001011010.12=5A.816

5A.8

將十六進(jìn)制數(shù)F7.28變?yōu)槎M(jìn)制數(shù)F7.28F7.2816=11110111.00101211110111.00101000①十進(jìn)制數(shù)2003等值于二進(jìn)制數(shù)（

）。(NOIP9)

A）0100000111

B）10000011

C）110000111

D）11111010011

E）1111010011②十進(jìn)制書11/128可用二進(jìn)制數(shù)碼序列表示為:()。(NOIP8)A）1011/1000000B）1011/100000000C）0.001011D）0.0001011③算式（2047）10－（3FF）16＋（2000）8的結(jié)果是（）。(NOIP8NOIP7)A）（2048）10B）（2049）10C）（3746）8D）（1AF7）16④64KB的存儲器用十六進(jìn)制表示，它的最大的地址碼是()(NOIP7)

A)10000

B)FFFF

C)1FFFF

D)EFFFFDDAB⑤十進(jìn)制算術(shù)表達(dá)式3*512+7*64+4*8+5的運算結(jié)果，用二進(jìn)制表示為().(NOIP5)A·10111100101B·11111100101C·11110100101D·11111101101⑥下列無符號數(shù)中，最小的數(shù)是（）(NOIP6)

A.（11011001）2

B.(75)10

C.(37)8

D.(2A)16⑦運算式(2008)10-(3723)8的結(jié)果是（

）。NOIP9

A）(-1715)10

B)(5)10

C)(5)16

D)(101)2

E)(3263)8

BCBCD8、十進(jìn)制數(shù)100.625等值于二進(jìn)制數(shù)（）（NOIP10）。

A.1001100.101B.1100100.101C.1100100.011D.1001100.11E.1001100.0113、(2004)10+(32)16的結(jié)果是（）。（NOIP10）

A.(2036)16B.(2054)10C.(4006)8D.(100000000110)2E.(2036)103、以下二進(jìn)制數(shù)的值與十進(jìn)制數(shù)23.456的值最接近的是（）（NOIP11）。

A.10111.0101B.11011.1111C.11011.0111D.10111.0111E.10111.1111

12.(3725)8+(B)16的運算結(jié)果是（）。（NOIP11）

A.(3736)8B.(2016)10C.(11111100000)2D.(3006)10E.(7E0)16

12.(2010)16+(32)8的結(jié)果是（）。noip12A.(8234)10B.(202A)16C.(100000000110)2D.(2042)167、與十進(jìn)制數(shù)28.5625相等的四進(jìn)制數(shù)是（）。noip14A.123.21B.131.22C.130.22D.130.21E.130.2015.(2008)10+(5B)16的結(jié)果是（）。noip14A.(833)16B.(2099)10C.(4063)8D.(100001100011)28、與十進(jìn)制數(shù)17.5625對應(yīng)的8進(jìn)制數(shù)是（）。noip13A.21.5625B.21.44C.21.73D.21.731E.前4個答案都不對13.(2070)16+(34)8的結(jié)果是（）。noip13A.(8332)10B.(208C)16C.(100000000110)2D.(20214)89.與十進(jìn)制數(shù)1770.625對應(yīng)的八進(jìn)制數(shù)是（）。noip12A.3352.5B.3350.5C.3352.1161D.3350.1151E.前4個答案都不對12.(2010)16+(32)8的結(jié)果是（）。noip12A.(8234)10B.(202A)16C.(100000000110)2D.(2042)16七、在計算機(jī)中帶符號數(shù)的表示法原碼：在用二進(jìn)制原碼表示的數(shù)中，符號位為0表示正數(shù)，符號位為1表示負(fù)數(shù)，其余各位表示數(shù)值部分。如：10000010，00000010反碼：反碼的定義如下:⑴對于正數(shù)，它的反碼表示與原碼相同。即[x]反=[x]原⑵對于負(fù)數(shù)，則除符號位仍為“1”外，其余各位“1”換成”0”，”0”換成1”，即得到反碼[X]反。例如[-1101001]反=10010110。⑶對于0，它的反碼有兩種表示:[+0]反=00…0[-0]反=11…1補(bǔ)碼：

正數(shù)的補(bǔ)碼就是該正數(shù)本身。

[01100100]補(bǔ)＝01000100

對于負(fù)數(shù):兩頭的1不變，中間取反。

[10100100]補(bǔ)＝11011100

[+0]補(bǔ)＝[-0]補(bǔ)＝00…0。BCD碼（8421碼）BCD碼就是用二進(jìn)制代碼表示的十進(jìn)制數(shù)，也稱BCD數(shù)。它是用4位二進(jìn)制代碼0000—1001來表示十進(jìn)制數(shù)0---9。如：39的BCD碼為00111001。①已知x=（0.1011010）2

，則[x/2]補(bǔ)=（）2。(NOIP8)A）0.1011101B）11110110C）0.0101101D）0.100110②[x]補(bǔ)碼=10011000，其原碼為()(NOIP7)

A)011001111

B)11101000

C)11100110

D)01100101CB八、信息存儲單位⑴位（bit，縮寫為b）：度量數(shù)據(jù)的最小單位，表示一位二進(jìn)制信息。⑵字節(jié)(byte，縮寫為B)：一個字節(jié)由八位二進(jìn)制數(shù)字組成（lbyte＝8bit）。字節(jié)是信息存儲中最常用的基本單位。計算機(jī)存儲器（包括內(nèi)存與外存）通常也是以多少字節(jié)來表示它的容量。常用的單位有：KB1K=1024MB1M=1024KGB1G=1024MTB1t=1024G機(jī)器字（word）：字是位的組合，并作為一個獨立的信息單位處理。字又稱為計算機(jī)字，它取決于機(jī)器的類型、字長以及使用者的要求。常用的固定字長有8位、16位、32位等。九、計算機(jī)網(wǎng)絡(luò)知識1、計算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)中各個站點相互連接的方法和形式稱之為網(wǎng)絡(luò)拓?fù)淇偩€拓?fù)湫切屯負(fù)?/p>

環(huán)型拓?fù)?/p>

樹型拓?fù)?/p>

2、計算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)的核心是OSI模型國際標(biāo)準(zhǔn)化組織（ISO）提出的開放系統(tǒng)互聯(lián)參考模型（OSI）已成為網(wǎng)絡(luò)體系結(jié)構(gòu)的標(biāo)準(zhǔn)

在這些層中，除了最高的第7層沒有需要服務(wù)的上一層、最低的第1層沒有可利用服務(wù)的下一層外，其它的每一層都建立在下一層的基礎(chǔ)上，利用下一層來實現(xiàn)自己的功能，并向上一級提供服務(wù)。主機(jī)A與主機(jī)B進(jìn)行通信時，通信協(xié)議是在對等層之間進(jìn)行的。其中，物理層與物理層之間的通信協(xié)議是直接的，其他對等層之間的通信協(xié)議都是間接的。74329、TCP/IP是一組構(gòu)成互聯(lián)網(wǎng)基礎(chǔ)的網(wǎng)絡(luò)協(xié)議，字面上包括兩組協(xié)議：傳輸控制協(xié)議（TCP）和網(wǎng)際協(xié)議（IP）。TCP/IP協(xié)議把Internet網(wǎng)絡(luò)系統(tǒng)描述成具有四個層次功能的網(wǎng)絡(luò)模型,其中提供源節(jié)點和目的節(jié)點之間的信息傳輸服務(wù)，包括尋址和路由器選擇等功能的是（）。Noip14A.鏈路層B．網(wǎng)絡(luò)層C.傳輸層D.應(yīng)用層E.會話層TCP/IP（TransmissionControlProtocol/InternetProtocol)的簡寫，中文譯名為傳輸控制協(xié)議/因特網(wǎng)互聯(lián)協(xié)議，又叫網(wǎng)絡(luò)通訊協(xié)議。超文本傳輸協(xié)議（HTTP），文件傳輸協(xié)議（FTP），Telnet和簡單郵件傳輸協(xié)議（SMTP：發(fā)送收電子郵件，pop3：接收電子郵件）3、Internet網(wǎng)絡(luò)地址

(IP地址)A類網(wǎng)絡(luò)為大型網(wǎng)絡(luò)；B類網(wǎng)絡(luò)為中型網(wǎng)絡(luò)；C類網(wǎng)絡(luò)為小型網(wǎng)絡(luò)。這三類網(wǎng)絡(luò)的地址特征為⑴A類網(wǎng)絡(luò)以0開頭，網(wǎng)絡(luò)號碼是7位，主機(jī)號碼是24位⑵B類網(wǎng)絡(luò)以10開頭，網(wǎng)絡(luò)號碼是14位，主機(jī)號碼是16位⑶C類網(wǎng)絡(luò)以110開頭，C類網(wǎng)絡(luò)的網(wǎng)絡(luò)號碼是21位，主機(jī)號碼是8位D類地址以1110開頭，E類地址以11110開頭。8.常見的郵件傳輸服務(wù)器使用（）協(xié)議發(fā)送郵件。（NOIp11）

A.HTTPB.SMTPC.TCPD.FTPE.POP3

9.不能在Linux上使用的網(wǎng)頁瀏覽器是（）。（NOIp11）

A.InternetExploreB.NetscapeC.OperaD.FirefoxE.Mozilla

8、下列哪個網(wǎng)絡(luò)上常用的名字縮寫是錯誤的（）。（NOIP10）

A、WWW（WorldWideWeb）

B、URL（UniformResourceLocator）

C、HTTP（HypertextTransferProtocol）

D、FTP（FastTransferProtocol）

E、TCP（TransferControlProtocol）。10、一臺計算機(jī)如果要利用電話線上網(wǎng)，就必須配置能夠?qū)?shù)字信號和模擬信號進(jìn)行相互轉(zhuǎn)換的設(shè)備，這種設(shè)備是（）。

A.調(diào)制解調(diào)器B.路由器C.網(wǎng)卡D.網(wǎng)關(guān)E.網(wǎng)橋十、邏輯運算：◆運算：與:and∧·

或:or∨+

非:not?

異或:xor◆運算的優(yōu)先級：非＞與＞或1、“與”運算（“·”，“∧”，and）

在邏輯問題中，如果決定某一事件發(fā)生的多個條件必須同時具備，事件才能發(fā)生，則這種因果關(guān)系稱之“與”邏輯(并且)。

“與”運算又稱為邏輯乘，其運算符號為“·”，有時也用“∧”表示。兩變量“與”運算關(guān)系可表示為

F=A·B

或者F=A∧B“與”運算的運算法則為：

0·0=0

1·0=0

0·1=0

1·1=1結(jié)論：若A、B均為1，則F為1；否則，F(xiàn)為0推廣：A·0=0A·1=A２、“或”運算（“+”，“∨”

,or）

在邏輯問題的描述中，如果決定某一事件是否發(fā)生的多個條件中，只要有一個或一個以上條件成立，事件便可發(fā)生，則這種因果關(guān)系稱之為“或”邏輯。

“或”運算又稱邏輯加，其運算符號為“+”，有時也用“∨”表示。兩變量“或”運算的關(guān)系可表示為

F=A+B或者F=A∨B

“或”運算的運算法則為：

0+0=0

1+0=10+1=1

1+1=1結(jié)論：僅當(dāng)A、B均為0時，F(xiàn)才為0

推廣：A+0=AA+1=13.“非”運算

?

在邏輯問題中，如果某一事件的發(fā)生取決于條件的否定，即事件與事件發(fā)生的條件之間構(gòu)成矛盾，則這種因果關(guān)系稱為“非”邏輯。?！胺恰边\算也叫求反運算或者邏輯否定。其運算符號為“-”，有時也用“?”表示?！胺恰边\算的邏輯關(guān)系可表示為

F=或者F=?A

“非”運算的運算法則為

=1

=0①(NOIP9)假設(shè)A=true,B=false,C=ture,D=ture,邏輯運算表達(dá)式A/\B\/C/\D的值是（

）。

A）true

B）false

C）0

D）1

E）NULL②(NOIP8)已知A=35H，A/\05H\/A/\30H的結(jié)果是：（）。A）30HB）05HC）35HD）53H11.（NIOP11）設(shè)A=true，B=false，C=false，D=true，以下邏輯運算表達(dá)式值為真的有（）。

A.(A∧B)∨(C∧D)B.((A∧B)∨C)∧DC.A∧((B∨C)∨D)

D.(A∧(B∨C))∨DE.(A∨B)∧(C∨D)

5．已知A=11001010，B=00001111，C=01011100，A∨B∧C=()。(A)11001110(B)01110110(C)11101110(D)0100110013．下列邏輯運算正確的是（）。A)A·（A+B）=AB)A+（A·B）=A

C)A·（B+C）=A·B+A·CD)A+（B·C）=（A+B）·（A+C）E)A+1=A5．在Pascal語言中，表達(dá)式(21xor2)的值是（）noip12A.441B.42C.23D.24E.256．在Pascal語言中，判斷a不等于0且b不等于0的正確的條件表達(dá)式是（）noip12A.nota=0ornotb=0B.not((a=0)and(b=0))C.not(a=0andb=0)D.(a<>0)or(b<>0)E.(a<>0)and(b<>0)11.設(shè)A=B=D=true，C=E=false，以下邏輯運算表達(dá)式值為真的有（）。noip12A.(?

A∧B)∨(C∧D)∨?

EB.?(((A∧B)∨C)∧D∧E)C.A∧(B∨C∨D∨E)D.(A∧(B∨C))∧D∧E競賽環(huán)境的考查：16.在下列各軟件中，屬于NOIP競賽（復(fù)賽）推薦使用的語言環(huán)境有（）。noip12A.gcc/g++B.TurboPascalC.TurboCD.freepascal16.在下列各軟件中，屬于NOIP競賽（復(fù)賽）推薦使用的語言環(huán)境有（）。noip13A.gccB.g++C.TurboCD.freepascal19.NOIP競賽推薦使用的語言環(huán)境有（）。noi14A.Dev-C++B.VisualC++C.freepascalD.Lazarus信息學(xué)競賽中的數(shù)學(xué)知識◆集合的運算◆排列與組合◆集合及其運算1、集合的運算：并、交、補(bǔ)、差2、容斥原理1、集合的運算：并、交、補(bǔ)、差并：∪交：∩補(bǔ)：^或～或差:-ABABAABA∪BA∩BA-B8.

（NOIP9）設(shè)全集E={1，2，3，4，5}，集合A={1，4}，B={1，2，5}，C={2，4}，則集合（A∩B）∪～C為（

）。

A）空集

B）{1}

C）{3，5}

D）{1，5}

E）{1，3，5}1、（NOIP10）設(shè)全集I={a,b,c,d,e,f,g}，集合A={a,b,c}，

B={b,d,e}，C={e,f,g}，那么集合為（）。

A.{a,b,c,d}B.{a,b,d,e}C.{b,d,e}D.{b,c,d,e}E.{d,f,g}2.（NOIP11）設(shè)全集I={a,b,c,d,e,f,g,h}，集合B∪A={a,b,c,d,e,f}，

C∩A={c,d,e}，A∩~B={a,d}，那么集合C∩B∩A為（）。

A.{c,e}B.{d,e}C.{e}D.{c,d,e}E.{d,f}

2、容斥原理在計數(shù)時，為了使重疊部分不被重復(fù)計算，人們研究出一種新的計數(shù)方法，這種方法的基本思想是：先不考慮重疊的情況，把包含于某內(nèi)容中的所有對象的數(shù)目先計算出來，然后再把計數(shù)時重復(fù)計算的數(shù)目排斥出去，使得計算的結(jié)果既無遺漏又無重復(fù)，這種計數(shù)的方法稱為容斥原理。對有限集合S，用表示S的元素個數(shù)容斥原理的第一形式：設(shè)A，B是有限集合，則容斥原理的第二形式：設(shè)A、B、C是有限集合，則1、（NOIP10）75名兒童到游樂場去玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費用是5元，游樂場總共收入700，可知有

名兒童沒有玩過其中任何一種。2、某學(xué)校足球隊有球衣30件，籃球隊有球衣15件，排球隊有球衣18件，三隊隊員總數(shù)為50人，其中有2人同時參加3個隊，那么同時只參加兩個隊的隊員有多少？３、分母是1001的最簡分?jǐn)?shù)一共有多少個？10，9１００１＝７＊１１＊１３

在１——１００１這些自然數(shù)中，１００１的約數(shù)有：

１、７、１１、１３、７＊１１、７＊１３、１１＊１３、７＊１１＊１３共８個，

所以，分母是１００１的最簡真分?jǐn)?shù)共有：１００１－８＋１＝９９４個。◆排列與組合1.排列的定義:從n個不同元素中,任取m個元素,按照一定的順序排成一列,叫做從n個不同元素中取出m個元素的一個排列.排列數(shù)公式:全排列問題：

n個不同的元素排成一排，排列方法有：=n*(n-1)*(n-2)*…*2*1=n!2.組合的定義:從n個不同元素中,任取m個元素,并成一組,叫做從n個不同元素中取出m個元素的一個組合.組合數(shù)公式:排列與組合的區(qū)別與聯(lián)系:與順序有關(guān)的為排列問題,與順序無關(guān)的為組合問題.加法原理和乘法原理從A到C共有多少中走法？ABC例1:學(xué)校師生合影，共8個學(xué)生，4個老師，要求老師在學(xué)生中間，且老師互不相鄰，共有多少種不同的合影方式？解先排學(xué)生共有種排法,然后把老師插入學(xué)生之間的空檔，共有7個空檔可插,選其中的4個空檔,共有種選法.根據(jù)乘法原理,共有的不同坐法為種.結(jié)論1

插入法:對于某兩個元素或者幾個元素要求不相鄰的問題,可以用插入法.即先排好沒有限制條件的元素,然后將有限制條件的元素按要求插入排好元素的空檔之中即可.例2:5個男生3個女生排成一排,3個女生要排在一起,有多少種不同的排法?

解

因為女生要排在一起,所以可以將3個女生看成是一個人,與5個男生作全排列,有種排法,其中女生內(nèi)部也有種排法,根據(jù)乘法原理,共有種不同的排法.結(jié)論2

捆綁法:要求某幾個元素必須排在一起的問題,可以用捆綁法來解決問題.即將需要相鄰的元素合并為一個元素,再與其它元素一起作排列,同時要注意合并元素內(nèi)部也可以作排列.例3:袋中有不同年份生產(chǎn)的5分硬幣23個,不同年份生產(chǎn)的1角硬幣10個,如果從袋中取出2元錢,有多少種取法?解

把所有的硬幣全部取出來,將得到0.05×23+0.10×10=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3個5分或1個5分與1個1角,所以共有種取法.結(jié)論3

剩余法:在組合問題中,有多少取法,就有多少種剩法,他們是一一對應(yīng)的,因此,當(dāng)求取法困難時,可轉(zhuǎn)化為求剩法.分析此題是一個組合問題,若是直接考慮取錢的問題的話,情況比較多,也顯得比較凌亂,難以理出頭緒來.但是如果根據(jù)組合數(shù)性質(zhì)考慮剩余問題的話,就會很容易解決問題.例4

學(xué)校安排考試科目9門,語文要在數(shù)學(xué)之前考,有多少種不同的安排順序?解不加任何限制條件,整個排法有種,“語文安排在數(shù)學(xué)之前考”,與“數(shù)學(xué)安排在語文之前考”的排法是相等的,所以語文安排在數(shù)學(xué)之前考的排法共有種.結(jié)論4

對等法:在有些題目中,它的限制條件的肯定與否定是對等的,各占全體的二分之一.在求解中只要求出全體,就可以得到所求.分析對于任何一個排列問題,就其中的兩個元素來講的話,他們的排列順序只有兩種情況,并且在整個排列中,他們出現(xiàn)的機(jī)會是均等的,因此要求其中的某一種情況,能夠得到全體,那么問題就可以解決了.并且也避免了問題的復(fù)雜性.例5

某個班級共有43位同學(xué),從中任抽5人,正、副班長、團(tuán)支部書記至少有一人在內(nèi)的抽法有多少種?解

43人中任抽5人的方法有種,正副班長,團(tuán)支部書記都不在內(nèi)的抽法有種,所以正副班長,團(tuán)支部書記至少有1人在內(nèi)的抽法有種.結(jié)論5

排異法:有些問題,正面直接考慮比較復(fù)雜,而它的反面往往比較簡捷,可以先求出它的反面,再從整體中排除.分析此題若是直接去考慮的話,就要將問題分成好幾種情況,這樣解題的話,容易造成各種情況遺漏或者重復(fù)的情況.而如果從此問題相反的方面去考慮的話,不但容易理解,而且在計算中也是非常的簡便.這樣就可以簡化計算過程.圓周排列：從n個不同的元素中取r個沿一圓周排列，排列的方案：/rN個元素的圓周排列：/n=（n-1）!有重復(fù)元素的排列問題：如：n1個a，n2個b，n3個c，排成一排，有多少種排列方法。重復(fù)元素的組合問題：

從n種不同的元素中取r個的元素的組合，允許有重復(fù)元素的組合：典型模型：

r個相同的小球，放到n個不同的盒子里，所有的放置方法。1.（NOIP7）平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同四邊形？2、（NOIP10）由3個a，5個b和2個c構(gòu)成的所有字符串中，包含子串“abc”的共有（）個。

A.40320B.39600C.840D.780E.601分兩種情況

(1)4個點在兩條直線上A上2個點和B上2個點有C(5,2)*C(6,2)=10*15=150在AC上有C(5,2)*C(7,2)=10*21=210在BC上有C(6,2)*C(7,2)=15*21=315(2)在一直線上有2點，令二點分別在另兩條直線上則若A上有2點，是C(5,2)，BC上各一點，分別有6種和7種可能，是C(5,2)*6*7=420同理若B上2點是C(6,2)*5*7=525若C上2點則C(7,2)*5*6=630所以一共150+210+315+420+525+630=22502一共是10個字母當(dāng)abc在第一位時,后面一共有105種排列(7!/(2!*4!)=105)

當(dāng)abc在第二位時,也是105種

...當(dāng)abc在第八位時,也是105.105*8=840種里面有重復(fù)的,要減去,就是減去有2個字字串a(chǎn)bc的.

一共60種(6!/(2!*3!)=60)所以840-60=780種1．

(NOIP8)

在書架上放有編號為1，2，．．．，n的n本書?，F(xiàn)將n本書全部取下然后再放回去，當(dāng)放回去時要求每本書都不能放在原來的位置上。例如：n=3時：原來位置為：123

放回去時只能為：312或231這兩種

問題：求當(dāng)n=5時滿足以上條件的放法共有多少種？（不用列出每種放法）錯排問題：

n個不同元素的錯排問題：如：1，2，3，。。。，n的錯排問題，i不在第i個位置的排列方法。分析：設(shè)f(n)為n個不同元素的錯排方案。第一部分：n先不動，把另外的n-1個數(shù)錯排，方案是：f（n-1），然后n和另外的n-1個每一個交換，共有(n-1)*f(n-1)種方案。第二部分：n和其他的n-1個之一交換，其余的n-2個錯排，共有（n-1）*f（n-2）種方案。由加法原理：

f(n)=(n-1)*(f(n-1)+f(n-2))f(1)=0;f(2)=1;44錯排的計算公式：幾類重要的遞推關(guān)系：一、第二類Stirling數(shù)問題一：放置小球n個有區(qū)別的球放到m個相同的盒子中，要求無一空盒，其不同的方案數(shù)用S(n,m)表示，稱為第二類Stirling數(shù)

設(shè)有n個不同的球，分別用b1,b2,……bn表示。從中取出一個球bn，bn的放法有以下兩種：1)bn獨自占一個盒子；那么剩下的球只能放在m-1個盒子中，方案數(shù)為S(n-1,m-1)2)bn與別的球共占一個盒子；那么可以事先將b1,b2,……bn-1這n-1個球放入m個盒子中，然后再將球bn可以放入其中一個盒子中，方案數(shù)為m*S(n-1,m)S(n,m)=m*S(n-1,m)+S(n-1,m-1)(n>1,m>1)邊界條件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)問題二：集合劃分問題。設(shè)S是一個包含n個元素的集合，S={b1,b2,b3,…,bn},現(xiàn)需要將S集合劃分為m個滿足如下條件的集合S1,S2,…Sm。

Si≠∮;

Si∩Sj=∮;

S1∪S2∪…∪Sm=S;(1<=I,j<=m)則稱S1,S2,…,S