#［信息學奧賽基礎(chǔ)知識講義］基礎(chǔ)部分一、進制：2進制數(shù)與8進制、10進制、16進制數(shù)的換算換算1：將N進制數(shù)換算成10進制數(shù)（N可以為2,&16或其它自然數(shù)）換算2：將10進制數(shù)換算成N進制數(shù)（N可以為2,&16或其它自然數(shù)）TOC\o"1-5"\h\z1?下列無符號數(shù)中，最小的數(shù)是（）（）B.（75）C.（37）D.（2A）2108167、小張用十六進制，八進制和十進制寫下了如下一個等式：52-19=33式中三個數(shù)是各不相同進位制的數(shù)，試問52,19,33，分別為。（A）8，10，16（B）10,16,8（c）8,16,10（D）10,8,16二、數(shù)據(jù)的存儲和編碼所有的數(shù)據(jù)都是以二進制存儲在計算機的存儲器中的，數(shù)據(jù)的傳送、存儲、加工、處理或指令都是以二進制形式進行的。對于數(shù)值:弄清原碼、反碼、補碼以及定點數(shù)和浮點數(shù)。負數(shù)在計算機中以補碼形式存放，小數(shù)在計算機中是以浮點數(shù)形式存放。0的原碼表示法有兩種，+0和一08位定點整數(shù)的補碼表示范圍為T28+12714、計算機中的數(shù)有浮點數(shù)與定點數(shù)兩種，其中用浮點數(shù)表示的數(shù)，通常由（）這兩部分組成。指數(shù)與基數(shù)B.尾數(shù)與小數(shù)C.階碼與尾數(shù)D.整數(shù)與小數(shù)8、如果用一個字節(jié)表示一個整數(shù)，最高位用作符號位，其他位表示數(shù)值，例如00000001表示+1，表示_1（1）試問這樣表示法的整數(shù)a的范圍應(yīng)是A、-127〈=a〈=127B、-128〈=a〈=128C、-128〈=a〈127D、-128〈a〈=128（2）在這樣表法法中，以下說法是下確的A、范圍內(nèi)的每一個數(shù)都只有唯一的格式B、范圍內(nèi)的每一個數(shù)有兩種格式C、范圍內(nèi)的一半數(shù)有兩種格式樣D、范圍內(nèi)只有一個數(shù)有兩種表示格式對于字符對英文的字母和其它打印字符：（擴展）ASCII碼（美國標準信息交換碼）標準的ASCII碼為7位二進制編碼，但在計算機中以8位二進制位來存儲（最高位為校驗們位），擴充的ASCII碼為8位二進制編碼對漢字，中國大陸常用的有GB碼、GBK碼、UnicodeGBK碼于1980年發(fā)布，是中文信息處理的國家標準，在大陸及海外使用簡體中文的地區(qū)（如新加坡等）是強制使用的唯一中文編碼。和蘋果OS就是以GB2312為基本漢字編碼，Windows95/98則以GBK為基本漢字編碼、但兼容支持GB2312。GB碼共收錄6763個簡體漢字、682個符號，其中漢字部分：一級字3755，以拼音排序，二級字3008，以偏旁部首排序。

18.組成'教授'（jiaoshou）'副教授'（fujiaoshou）與'講師'（jiangshi）這三個詞的漢字，在GB2312—80字符集中都是一級漢字?對這三個詞排序的結(jié)果是（）?A教授，副教授，講師B.副教授，教授，講師C講師，副教授，教授D.副教授，講師，教授規(guī)定了一級漢字3755個，二級漢字3008個，其中二級漢字字庫中的漢字是以（）為序排列的。A.以筆劃多少B.以部首C.以ASCII碼D.以機內(nèi)碼已知小寫字母'm'的十六進制的ASC11碼值是6D，則小寫字母'c'的十六進制的ASCII碼值是（）三、計算機的硬件結(jié)構(gòu)控制器合稱CPU計算機系統(tǒng)（硬盤、內(nèi)存、光盤、軟盤等）輸入設(shè)備（鍵盤、鼠標、話筒、掃描儀、數(shù)碼相機等）V控制器合稱CPU計算機系統(tǒng)（硬盤、內(nèi)存、光盤、軟盤等）輸入設(shè)備（鍵盤、鼠標、話筒、掃描儀、數(shù)碼相機等）V輸出設(shè)備（顯示器、音箱、打印機、光盤刻錄機等）2.在外部設(shè)備中，繪圖儀屬于（）A.輸入設(shè)備B.輸出設(shè)備C.輔（外）存儲器D.主（內(nèi)）存儲器6.計算機主機是由。卩卩與（）構(gòu)成的A.控制器B.運算器C.輸入、輸出設(shè)備D.內(nèi)存儲器運算器是實現(xiàn)算術(shù)運算或邏輯運算的裝置，對數(shù)據(jù)進行傳送和加工?？刂破魇怯嬎銠C的控制中心，它分析從存儲器取出的信息，然后據(jù)此向計算機的各個部分發(fā)出各種控制信號，指揮與協(xié)調(diào)整臺計算機自動而有序地工作。它是計算機的“神經(jīng)中樞”。存儲器的功能是存儲信息，以備調(diào)用，它由成千上萬個存儲單元組成，每個單元可存放一定位數(shù)的二進制信息，存儲器的容量以字節(jié)Byte為基本單位，還有KB（=1024Byte）、MB（1024KB）、GB（1024MB）等計量單位（如稱某臺計算機的內(nèi)存為64MB，硬盤為10GB）。存儲器是計算機的“記憶系統(tǒng)”微機內(nèi)存儲器的地址是按助存編址的。A.二進制位B.字長C.字節(jié)D.微處理器的型號中的信息是（）A.生產(chǎn)廠家預(yù)先寫入的B.計算機工作時隨機寫入的C.防止計算機病毒侵入所使用的D.專門用于計算機開機時自檢用的12.某種計算機的內(nèi)存容量是640K，這里的640K容量是指（）個字節(jié)*1000*1024*1024*1024不同類型的存儲器組成了多層次結(jié)構(gòu)的存儲器體系,按存取速度從快到慢的排列是（）

A.快存/輔存/主存A.快存/輔存/主存外存/主存/輔存快存/主存/輔存D.主存/輔存/外存計算機病毒的特點：隱藏性、潛伏性、可激活性、危害性、可傳染性7.計算機病毒的特點（）A.傳播性、潛伏性、易讀性與隱蔽性B.破壞性、傳播性、潛伏性與安全性C.傳播性、潛伏性、破壞性與隱蔽性D.傳播性、潛伏性、破壞性與易讀性二進制/位/字節(jié)/字/字長bit/byte/word/在計算機內(nèi)部，用來傳送、存儲、加工、處理或指令都是以—形式進行的。（A）十進制頭（B）智能拼音碼（C）二進制碼（D）五筆字型碼微機內(nèi)存儲器的地址是按（）編址的。A.二進制位B.字長C.字節(jié)D.微處理器的型號［信息學奧賽基礎(chǔ)知識講義］初賽基礎(chǔ)知識2本課內(nèi)容：1、數(shù)據(jù)結(jié)構(gòu)之線性表2、構(gòu)造數(shù)據(jù)結(jié)構(gòu)的重要工具：指針程序（讀程序?qū)懡Y(jié)果、完善程序）算法+數(shù)據(jù)結(jié)構(gòu)相關(guān)知識點：?數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)的基本概念。.線性表的基本概念和實現(xiàn)技術(shù)。.棧和隊列的基本概念和實現(xiàn)技術(shù)。4.樹形結(jié)構(gòu)的基本概念，二*樹的表示和遍歷算法，樹與二*樹的轉(zhuǎn)換。5?排序的基本概念和排序算法（插入排序、選擇排序、交換排序）。算法（P62-85）特定的問題采用特定的算法一?數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)的基本概念。數(shù)據(jù)類型用來表示數(shù)據(jù)元素的特性（p24）數(shù)據(jù)結(jié)構(gòu)用來描述數(shù)據(jù)元素之間的關(guān)系數(shù)據(jù)元素之間的關(guān)系有四種（1）集合：同數(shù)學中的集合概念，結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個集合外，別無其它關(guān)系（2）線性表：數(shù)據(jù)元素之間為一個對一個的關(guān)系（3）樹：數(shù)據(jù)之間存在一對多的關(guān)系（4）圖：數(shù)據(jù)之音存在多對多的關(guān)系二、線性表1、線性表的應(yīng)用實例：排隊時的隊列，一個含班上全部同學的成績的表2、概念：線性表是N（N>=0）個數(shù)據(jù)元素的有限序列3、特征：（1）數(shù)據(jù)表中的元素具有相同的特性（相同的數(shù)據(jù)類型）3、（2）元素之間具備線性關(guān)系（有順序，并且是一對一的關(guān)系）相關(guān)名詞：表頭、表尾eg：線性表是：A、有限序列，可以為空；B、有限序列，不能為空C、無限序列，可以為空D、無限序列，不能為空三、常用的兩種線性表模型隊列：特點：只能在表的一端進行插入，在表的另一端進行刪除的線性表相關(guān)名詞：隊首、隊尾堆棧：特點：只能在表的一端進行插入和刪除操作應(yīng)用：求解數(shù)學表達式、實現(xiàn)遞歸算法相關(guān)名詞：棧頂、棧底eg：設(shè)棧S的初始狀態(tài)為空，現(xiàn)有個元素組成的序列（1,2,3,4,5）,對該序列在S棧上依次進行如下操作（從序列中的1開始，出棧后不再進棧）：進棧，進棧，進棧，出棧，進棧，出棧，進棧，請問出棧的元素序列是：四、線性表的存儲：（順序存儲和鏈表存儲）順序存儲：是按數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系程序描述：用一維數(shù)組來描述順序存儲結(jié)構(gòu)，二維數(shù)組的每一個元素為一個線性表鏈表存儲：用一組任意的存儲單元來存儲數(shù)據(jù)元素，元素之間的關(guān)系通過指針來表現(xiàn)。程序描述：用指針eg：找同學兩種存儲結(jié)構(gòu)的特點對比順序表鏈表一個表必須用一組連續(xù)的內(nèi)存地址存儲內(nèi)存地址可以是連續(xù)的也可以是不連續(xù)的插入和刪除元素難度大插入和刪除元素簡單（不需移動元素，只需修改頭尾指針即可）存取數(shù)據(jù)快（只要確定了起始位置，線性表中任一數(shù)據(jù)元素可隨機存?。┐嫒?shù)據(jù)慢線性表若采用鏈表存貯結(jié)構(gòu)，要求內(nèi)存中可用存貯單元地址（）A.必須連續(xù)B.部分地址必須連續(xù)C.一定不連續(xù)D.連續(xù)不連續(xù)均可18?下列敘述中，正確的是（）線性表的線性存貯結(jié)構(gòu)優(yōu)于鏈表存貯結(jié)構(gòu)隊列的操作方式是先進后出棧的操作方式是先進先出二維數(shù)組是指它的每個數(shù)據(jù)元素為一個線性表的線性表14、線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1）有一個線性表，在處理過過程中表的長度會根據(jù)需要動態(tài)發(fā)生變化，在這種情況下應(yīng)選用哪種存儲結(jié)構(gòu)（2）有一個線性表，很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)采用哪種存儲結(jié)構(gòu)已知數(shù)組A中，每個元素A[I,J]在存貯時要占3個字節(jié)，設(shè)I從1變化到8,J從1變化到10,分配內(nèi)存時是從地址SA開始連續(xù)按行存貯分配的。試問：A[5,8]的起始地址為（）+144+180+222+225（4*10+8）*31?在下面各世界頂級的獎項中，為計算機科學與技術(shù)領(lǐng)域做出杰出貢獻的科學家設(shè)立的獎項是（）。沃爾夫獎B.諾貝爾獎C.菲爾茲獎D.圖靈獎在下列各軟件中，不屬于NOIP競賽（復賽）推薦使用的語言環(huán)境有（）。gcc/g++B.TurboPascalC.RHIDED.freepascal以下斷電之后仍能保存數(shù)據(jù)的有（）。寄存器B.ROMC.RAMD.高速緩存Linux是一種（）。A.繪圖軟件B.程序設(shè)計語言C.操作系統(tǒng)D.網(wǎng)絡(luò)瀏覽器CPU是（）的簡稱。A.硬盤B.中央處理器C.高級程序語言D.核心寄存器在計算機中，防火墻的作用是（）。A.防止火災(zāi)蔓延B.防止網(wǎng)絡(luò)攻擊C.防止計算機死機D.防止使用者誤刪除數(shù)據(jù)在下列關(guān)于計算機語言的說法中，不正確的是（）。Pascal和C都是編譯執(zhí)行的高級語言高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上C++是歷史上的第一個支持面向?qū)ο蟮挠嬎銠C語言與匯編語言相比，高級語言程序更容易閱讀

8.在下列關(guān)于計算機算法的說法中，不正確的是（）。8.在下列關(guān)于計算機算法的說法中，不正確的是（）。一個正確的算法至少要有一個輸入算法的改進，在很大程度上推動了計算機科學與技術(shù)的進步判斷一個算法的好壞的主要標準是算法的時間復雜性與空間復雜性目前仍然存在許多涉及到國計民生的重大課題，還沒有找到能夠在計算機上實施的有效算法在下列各種排序算法中，不是以“比較”作為主要操作的算法是（）。A.選擇排序B.冒泡排序C.插入排序D.基數(shù)排序在編程時（使用任一種高級語言，不一定是Pascal），如果需要從磁盤文件中輸入一個很大的二維數(shù)組（例如1000*1000的double型數(shù)組），按行讀（即外層循環(huán)是關(guān)于行的）與按列讀（即外層循環(huán)是關(guān)于列的）相比，在輸入效率上（）。A.沒有區(qū)別B.按行讀的方式要高一些C.按列讀的方式要高一些D.取決于數(shù)組的存儲方式。在Pascal語言中，表達式（21xor2）的值是（）A.441B.42在Pascal語言中，判斷a不等于0且b不等于0的正確的條件表達式是（）A.nota=0ornotb=0B.not（（a=0）and（b=0））C.not（a=0andb=0）D.（a<>0）and（b<>0）某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態(tài)為空，從TOC\o"1-5"\h\z這一時刻開始的出入記錄為：“進，出，進，進，進，出，出，進，進，進，出，出”。假設(shè)車輛入站的順序為1，2，3，……，則車輛出站的順序為（）。A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2高度為n的均衡的二叉樹是指：如果去掉葉結(jié)點及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。在這里，樹高等于葉結(jié)點的最大深度，根結(jié)點的深度為0，如果某個均衡的二叉樹共有2381個結(jié)點，則該樹的樹高為（）。A.10B.11C.12D.13與十進制數(shù)1770對應(yīng)的八進制數(shù)是（）。

A.3350B.3351C.3352D.3540將5個數(shù)的序列排序，不論原先的順序如何，最少都可以通過()次比較,大的排序。A.6B.7C.8D.9TOC\o"1-5"\h\z設(shè)A=B=D=true,C二false，以下邏輯運算表達式值為真的有()。A.(-AAB)V(CAD)B.-((AVBVD)AC)C.AA(BVCVD)D.(AABAC)VD(2010)16+(32)8的結(jié)果是()。A.(8234)10B.(202B)16C.(20056)8D.()2設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e依次入棧，以下出棧序列不可能出現(xiàn)的有(A.a,b,c,e,dB.b,c,a,e,dC.a,e,c,b,dD.d,c,e,b,a已知6個結(jié)點的二叉樹的先根遍歷是123456(數(shù)字為結(jié)點的編號，以下同)，325641,則該二叉樹的可能的中根遍歷是()A.321465B.321546C.213546D.231465練習二在字符串“ababacbabcbdecced"中出現(xiàn)次數(shù)最多的字母出現(xiàn)了()次。A.6B.5C.4D.3E.2設(shè)全集I二{a,b,c,d,e,f,g,h}，集合A={a,b,c,d,e,f}，B={c,d,d}，那么集合ACBC~C為()。A.{c,e}B.{d,e}C.{e}D.{c,d,e}E.{d,f}和十進制數(shù)23的值相等的二進制數(shù)是()。完成從小到)。后根遍歷是e}，C={a,A.10110B.11011C.11011完成從小到)。后根遍歷是e}，C={a,完全二叉樹的結(jié)點個數(shù)為11，則它的葉結(jié)點個數(shù)為（）。A.4D.2E.6平面上有五個點A（5,3）,B（3,5）,C（2,1）,D（3,3）,E（5,1）。以這五點作為完全圖G的頂點,每兩點之間的直線距離是圖G中對應(yīng)邊的權(quán)值。以下哪條邊不是圖G的最小生成樹中的邊（）。A.ADB.BDC.CDD.DEE.EAIntel的首顆16位處理器是（）。A.8088B.80386C.80486D.8086E.Pentium處理器A每秒處理的指令數(shù)是處理器B的2倍。某一特定程序P分別編譯為處理器A和處理器B的指令，編譯結(jié)果處理器A的指令數(shù)是處理器B的4倍。已知程序P在處理器A上執(zhí)行需要1個小時，那么在輸入相同的情況下，程序P在處理器B上執(zhí)行需要（）小時。A.4B.2C.1D.1/2E.1/4以下哪個不是計算機的輸出設(shè)備（）。A.音箱B.顯示器C.打印機D.掃描儀E.繪圖儀下列活動中不屬于信息學奧賽的系列活動的是（）。A.NOIPB.NOIC.IOID.冬令營E.程序員等級考試以下斷電之后仍能保存數(shù)據(jù)的是（）。A.硬盤B.寄存器C.顯存D.內(nèi)存E.高速緩存以下哪個軟件不是即時通信軟件（）。A.網(wǎng)易泡泡B.MSNMessengerC.GoogleTalkD.3DSMaxE.QQ下列關(guān)于高級語言的說法錯誤的是（）。Fortran是歷史上的第一個面向科學計算的高級語言Pascal和C都是編譯執(zhí)行的高級語言C++是歷史上的第一個支持面向?qū)ο蟮恼Z言編譯器將高級語言程序轉(zhuǎn)變?yōu)槟繕舜a高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上下列設(shè)備不具有計算功能的是（）。A.筆記本電腦B.掌上電腦C.智能手機D.電子計算器A.筆記本電腦B.掌上電腦C.智能手機D.電子計算器E.液晶顯示器14