信息學(xué)奧賽基礎(chǔ)知識(shí)講義

1、信息學(xué)奧賽基礎(chǔ)知識(shí)講義基礎(chǔ)部分一、進(jìn)制：2進(jìn)制數(shù)與8進(jìn)制、10進(jìn)制、16進(jìn)制數(shù)的換算換算1：將N進(jìn)制數(shù)換算成10進(jìn)制數(shù)（N可以為2, 8,16或其它自然數(shù)）換算2：將10進(jìn)制數(shù)換算成N進(jìn)制數(shù)（N可以為2, 8,16或其它自然數(shù)）下列無(wú)符號(hào)數(shù)中，最小的數(shù)是（ ）A.（11011001） B.（75） C.（37） D.（2A）2 10 8 167、小X用十六進(jìn)制，八進(jìn)制和十進(jìn)制寫(xiě)下了如下一個(gè)等式：52-19=33 式中三個(gè)數(shù)是各不相同進(jìn)位制的數(shù)，試問(wèn)52,19,33，分別為。（A）8，10， 16 （B）10, 16, 8（c） 8, 16, 10 （D） 10, 8, 16二、數(shù)據(jù)的存儲(chǔ)和編碼

2、 所有的數(shù)據(jù)都是以二進(jìn)制存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中的，數(shù)據(jù)的傳送、存儲(chǔ)、加工、處理或指令都是以二進(jìn)制形式進(jìn)行 的。對(duì)于數(shù)值:弄清原碼、反碼、補(bǔ)碼以與定點(diǎn)數(shù)和浮點(diǎn)數(shù)。負(fù)數(shù)在計(jì)算機(jī)中以補(bǔ)碼形式存放，小數(shù)在計(jì)算機(jī)中是以浮點(diǎn)數(shù) 形式存放。0的原碼表示法有兩種，+0和08位定點(diǎn)整數(shù)的補(bǔ)碼表示X圍為-128+12714、計(jì)算機(jī)中的數(shù)有浮點(diǎn)數(shù)與定點(diǎn)數(shù)兩種，其中用浮點(diǎn)數(shù)表示的數(shù)，通常由（）這兩部分組成。A.指數(shù)與基數(shù) B.尾數(shù)與小數(shù)C.階碼與尾數(shù) D.整數(shù)與小數(shù)8、如果用一個(gè)字節(jié)表示一個(gè)整數(shù)，最高位用作符號(hào)位，其他位表示數(shù)值，例如 00000001表示+1 ， 10000001表示-1（1）試問(wèn)這樣表示法的整數(shù)a

3、的X圍應(yīng)是A、-127=a=127B、-128=a=128C、-128=a127D、-128a=0)個(gè)數(shù)據(jù)元素的有限序列3、特征：(1)數(shù)據(jù)表中的元素具有相同的特性(相同的數(shù)據(jù)類(lèi)型)3、(2)元素之間具備線(xiàn)性關(guān)系(有順序，并且是一對(duì)一的關(guān)系)相關(guān)名詞：表頭、表尾eg:線(xiàn)性表是：A、有限序列，可以為空；B、有限序列，不能為空C、無(wú)限序列，可以為空D、無(wú)限序列，不能為空三、常用的兩種線(xiàn)性表模型 隊(duì)列： 特點(diǎn)：只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線(xiàn)性表 相關(guān)名詞：隊(duì)首、隊(duì)尾堆棧： 特點(diǎn)：只能在表的一端進(jìn)行插入和刪除操作 應(yīng)用：求解數(shù)學(xué)表達(dá)式、實(shí)現(xiàn)遞歸算法相關(guān)名詞：棧頂、棧底eg:設(shè)棧S的初

4、始狀態(tài)為空，現(xiàn)有個(gè)元素組成的序列（1, 2, 3, 4, 5）,對(duì)該序列在S棧上依次進(jìn)行如下操作（從序列 中的 1 開(kāi)始，出棧后不再進(jìn)棧）：進(jìn)棧，進(jìn)棧，進(jìn)棧，出棧，進(jìn)棧，出棧，進(jìn)棧，請(qǐng)問(wèn)出棧的元素序列是:四、線(xiàn)性表的存儲(chǔ)：（順序存儲(chǔ)和鏈表存儲(chǔ)）順序存儲(chǔ)：是按數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系 程序描述：用一維數(shù)組來(lái)描述順序存儲(chǔ)結(jié)構(gòu),二維數(shù)組的每一個(gè)元素為一個(gè)線(xiàn)性表 鏈表存儲(chǔ)：用一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)數(shù)據(jù)元素,元素之間的關(guān)系通過(guò)指針來(lái) 表現(xiàn)。程序描述：用指針eg：找同學(xué)兩種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)對(duì)比順序表鏈表一個(gè)表必須用一組連續(xù)的內(nèi)存地址存儲(chǔ)內(nèi)存地址可以是連續(xù)的也可以是不連續(xù)的插入

5、和刪除元素難度大插入和刪除元素簡(jiǎn)單（不需移動(dòng)元素,只需修改頭尾指針即可） 存取數(shù)據(jù)快（只要確定了起始位置,線(xiàn)性表中任一數(shù)據(jù)元素可隨機(jī)存?。?存取數(shù)據(jù)慢線(xiàn)性表若采用鏈表存貯結(jié)構(gòu),要求內(nèi)存中可用存貯單元地址（ ）A.必須連續(xù)B.部分地址必須連續(xù)一定不連續(xù)D.連續(xù)不連續(xù)均可下列敘述中,正確的是（ ）線(xiàn)性表的線(xiàn)性存貯結(jié)構(gòu)優(yōu)于鏈表存貯結(jié)構(gòu)隊(duì)列的操作方式是先進(jìn)后出C棧的操作方式是先進(jìn)先出二維數(shù)組是指它的每個(gè)數(shù)據(jù)元素為一個(gè)線(xiàn)性表的線(xiàn)性表14、線(xiàn)性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表,二是鏈表。試問(wèn)：（1）有一個(gè)線(xiàn)性表,在處理過(guò)過(guò)程中表的長(zhǎng)度會(huì)根據(jù)需要?jiǎng)討B(tài)發(fā)生變化,在這種情況下應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)（2）有一個(gè)線(xiàn)性表,很

6、少進(jìn)行插入和刪除操作,但要求以最快的速度存取線(xiàn)性表中的元素,應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)已知數(shù)組A中，每個(gè)元素AI,J在存貯時(shí)要占3個(gè)字節(jié)，設(shè)I從1變化到8, J從1變化到10，分配內(nèi)存時(shí)是從地址SA開(kāi)始連續(xù)按行存貯分配的。試問(wèn)：A5,8的起始地址為（）A.SA+144 B.SA+180 C.SA+222 D.SA+225（4*10+8）*3在下面各世界頂級(jí)的獎(jiǎng)項(xiàng)中,為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域做出杰出貢獻(xiàn)的科學(xué)家設(shè)立的獎(jiǎng)項(xiàng)是（ ）。沃爾夫獎(jiǎng)B. 諾貝爾獎(jiǎng)C.菲爾茲獎(jiǎng)D.圖靈獎(jiǎng)在下列各軟件中,不屬于 NOIP 競(jìng)賽（復(fù)賽）推薦使用的語(yǔ)言環(huán)境有（ ）。gcc/g+ B. Turbo PascalC. RHIDE

7、 D. free pascal以下斷電之后仍能保存數(shù)據(jù)的有（ ）。A.寄存器B. ROM C. RAM D.高速緩存4Linux 是一種（ ）。A.繪圖軟件B.程序設(shè)計(jì)語(yǔ)言C.操作系統(tǒng)D.網(wǎng)絡(luò)瀏覽器CPU 是（ ）的簡(jiǎn)稱(chēng)。A. 硬盤(pán) B. 中央處理器 C. 高級(jí)程序語(yǔ)言 D. 核心寄存器在計(jì)算機(jī)中，防火墻的作用是（ ）。A.防止火災(zāi)蔓延B.防止網(wǎng)絡(luò)攻擊C. 防止計(jì)算機(jī)死機(jī) D. 防止使用者誤刪除數(shù)據(jù)在下列關(guān)于計(jì)算機(jī)語(yǔ)言的說(shuō)法中，不正確的是（ ）。Pascal和C都是編譯執(zhí)行的高級(jí)語(yǔ)言高級(jí)語(yǔ)言程序比匯編語(yǔ)言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上C+是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語(yǔ)言與匯

8、編語(yǔ)言相比，高級(jí)語(yǔ)言程序更容易閱讀在下列關(guān)于計(jì)算機(jī)算法的說(shuō)法中，不正確的是（ ）。一個(gè)正確的算法至少要有一個(gè)輸入算法的改進(jìn)，在很大程度上推動(dòng)了計(jì)算機(jī)科學(xué)與技術(shù)的進(jìn)步判斷一個(gè)算法的好壞的主要標(biāo)準(zhǔn)是算法的時(shí)間復(fù)雜性與空間復(fù)雜性目前仍然存在許多涉與到國(guó)計(jì)民生的重大課題，還沒(méi)有找到能夠在計(jì)算機(jī)上實(shí)施的有效算法在下列各種排序算法中，不是以“比較”作為主要操作的算法是（ ）。A. 選擇排序 B. 冒泡排序 C. 插入排序 D. 基數(shù)排序 在編程時(shí)（使用任一種高級(jí)語(yǔ)言，不一定是Pascal），如果需要從磁盤(pán)文件中輸入一個(gè)很大 的二 維數(shù)組（例如 1000*1000 的 double 型數(shù)組），按行讀（即外層

9、循環(huán)是關(guān)于行的）與按列讀（即 外層 循環(huán)是關(guān)于列的）相比，在輸入效率上（ ）。A. 沒(méi)有區(qū)別 B. 按行讀的方式要高一些C. 按列讀的方式要高一些 D. 取決于數(shù)組的存儲(chǔ)方式。在 Pascal 語(yǔ)言中，表達(dá)式 （21 xor 2）的值是（ ）A. 441 B. 42 C.23 D.24在 Pascal 語(yǔ)言中，判斷 a 不等于 0 且 b 不等于 0 的正確的條件表達(dá)式是（ ）A. not a=0 or not b=0 B. not（a=0）and（b=0）C. not（a=0 and b=0） D. （a0）and （b0）某個(gè)車(chē)站呈狹長(zhǎng)形，寬度只能容下一臺(tái)車(chē)，并且只有一個(gè)出入口。已知某時(shí)刻

10、該車(chē)站狀態(tài)為空，從 TOC o 1-5 h z 這一時(shí)刻開(kāi)始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出”。假設(shè)車(chē)輛入站 的順序?yàn)?, 2, 3,，則車(chē)輛出站的順序?yàn)椋ǎ?。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2高度為 n 的均衡的二叉樹(shù)是指：如果去掉葉結(jié)點(diǎn)與相應(yīng)的樹(shù)枝，它應(yīng)該是高度為 n-1 的滿(mǎn)二叉樹(shù)。在這里，樹(shù)高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為 0，如果某個(gè)均衡的二叉樹(shù)共有 2381 個(gè)結(jié)點(diǎn)， 則該樹(shù)的樹(shù)高為（）。A. 10 B. 11 C. 12 D. 13與十進(jìn)制數(shù) 1770 對(duì)應(yīng)的八進(jìn)制數(shù)是（）。A. 3350 B. 3351 C. 3352 D. 3540將 5A. A點(diǎn) B. B點(diǎn) C. C點(diǎn) D. D點(diǎn) E. E點(diǎn)61. 某大學(xué)計(jì)算機(jī)專(zhuān)業(yè)的必修課與其先修課程如下表所示：課程代號(hào) C0 C1 C2 C3 C4 C5 C6 C7 課程名稱(chēng)高等數(shù)學(xué)程序設(shè)計(jì)語(yǔ)言離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)編譯技術(shù)操作系統(tǒng)普通物理計(jì)算機(jī)原理 先修課程C0, C1 C1, C2 C3 C3, C