計算機(jī)奧賽基礎(chǔ)知識

兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 1 頁 第一章第一章 計算機(jī)基礎(chǔ)知識計算機(jī)基礎(chǔ)知識 一 1946 年 2 月世界上第一臺計算機(jī) ENIAC 誕生在美國 二 計算機(jī)的發(fā)展分為 4 個階段 1 電子管時代 2 晶體管時代 3 中小規(guī) 模集成電路時代 4 大規(guī)模和超大規(guī)模集成電路時代 三 主存容量 1024 個字節(jié)為 1K 1024K 為 1M 1024M 為 1G 四 數(shù)據(jù)在計算機(jī)內(nèi)都是用二進(jìn)制編碼形式表示的 五 四種常用數(shù)制 1 十進(jìn)制 即逢十進(jìn)位 含有十個數(shù)字符號 0 9 形式表示 D 2 二進(jìn)制 即逢二進(jìn)位 含有兩個數(shù)字符號 0 1 形式表示 B 3 八進(jìn)制 即逢八進(jìn)位 含有八個數(shù)字符號 0 7 形式表示 O 4 十六進(jìn)制 即逢十六進(jìn)位 含有十六個數(shù)字符號 0 9 A B C D E F 形式表示 H 六 進(jìn)制轉(zhuǎn)換 1 R 進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù) 基數(shù)為 R 的數(shù)字 只要將各位數(shù)字與它的位權(quán)相乘的積相加 和數(shù)就是十 進(jìn)制 例 1 1101101 0101 B 1 26 1 25 0 24 1 23 1 22 0 21 1 20 0 2 1 1 2 2 0 2 3 1 2 4 109 3125 D 例 2 12321 2 O 5329 25 D 2 十進(jìn)制數(shù)轉(zhuǎn)換成 R 進(jìn)制數(shù) 將整數(shù)與小數(shù)兩部分分別轉(zhuǎn)換 整數(shù)部分轉(zhuǎn)換方法 除 R 倒取余 小數(shù)部 分轉(zhuǎn)換方法 乘 R 正取整法 例 100 345 D 1100100 01011 B 八進(jìn)制與二進(jìn)制 十六進(jìn)制與二進(jìn)制的關(guān)系 八進(jìn)制對應(yīng)二進(jìn)制十六進(jìn)制對應(yīng)二進(jìn)制十六進(jìn)制對應(yīng)二進(jìn)制 00000000081000 10011000191001 201020010A1010 301130011B1011 410040100C1100 510150101D1101 611060110E1110 711170111F1111 七 原碼 反碼和補(bǔ)碼 1 正數(shù)的反碼 補(bǔ)碼與其原碼相同 2 負(fù)數(shù)的反碼 除符號位外 各位依次取反 負(fù)數(shù)的補(bǔ)碼 為其反碼加 1 八 計算機(jī)系統(tǒng) 一臺完整的計算機(jī)系統(tǒng)是由硬件系統(tǒng)和軟件系統(tǒng)兩部分組成的 1 計算機(jī)的硬件系統(tǒng) 其基本結(jié)構(gòu)屬于馮 諾依曼型計算機(jī) 它的主要特 點 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 2 頁 1 計算機(jī)由五個基本部分組成 運算器 控制器 存儲器 輸入設(shè)備和輸 出設(shè)備 2 程序和數(shù)據(jù)以同等地位存放在存儲器中 并要按地址尋訪 3 程序和數(shù)據(jù)以二進(jìn)制表示 2 CPU 稱為中央處理單元 又稱微處理器 3 存儲器 存儲器的主要功能是存放程序和數(shù)據(jù) 存儲器通常分為內(nèi)存儲器和外存儲器 內(nèi)存的存取速度直接影響計算機(jī)的運算速度 內(nèi)部存儲器按其功能特征分為三類 1 隨機(jī)存儲器 RAM 一旦關(guān)機(jī)斷電 RAM 中的信息將全部消失 2 只讀存儲器 ROM 3 高速緩沖存儲器 Cache 4 計算機(jī)軟件系統(tǒng) 軟件分為系統(tǒng)軟件和應(yīng)用軟件兩大類 九 計算機(jī)病毒 計算機(jī)病毒是一組人為設(shè)計的程序 這種特殊的程序隱藏在計算機(jī)中 在系 統(tǒng)運行過程中能把自身準(zhǔn)確復(fù)制或有修改地復(fù)制到其他程序體內(nèi) 從而給計 算機(jī)系統(tǒng)造成一定的損害甚至嚴(yán)重破壞 計算機(jī)病毒的特性 1 傳染性 2 潛伏性 3 隱蔽性 4 破壞性 5 寄生性 十 計算機(jī)網(wǎng)絡(luò) 1 計算機(jī)網(wǎng)絡(luò)的類型 1 廣域網(wǎng) WAN 和局域網(wǎng) LAN 2 專用網(wǎng)和公共網(wǎng) 2 計算機(jī)網(wǎng)絡(luò)協(xié)議 1 TCP IP 傳輸控制協(xié)議和網(wǎng)際協(xié)議 規(guī)范了網(wǎng)絡(luò)上所有通信設(shè)備之間的數(shù)據(jù)傳輸格式及傳送方法 以保證數(shù) 據(jù)安全可靠地到達(dá)指定的目的地 2 FTP 文件傳送協(xié)議 3 TELNET 遠(yuǎn)程登錄協(xié)議 4 SMTP 簡單郵件傳送協(xié)議 5 PPP 點 點協(xié)議 6 HTTP 超文本傳輸協(xié)議 3 WWW 全稱是 World Wide Web 有時也簡稱 Web 或 3W 4 URL 統(tǒng)一資源定位標(biāo)識 任何一個信息文檔 圖形圖像 視頻或音頻都被看作是資源 為了引用資源 在 WWW 上 每一信息資源都有統(tǒng)一的且在網(wǎng)上唯一的地址 該地址就叫 URL 第二章第二章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 1 算法 問題處理方案的正確而完整的描述 2 算法的 4 個特性 確定性 可行性 有窮性 擁有足夠的情報 3 算法的復(fù)雜度包括 時間復(fù)雜度和空間復(fù)雜度 4 算法的時間復(fù)雜度是指 算法執(zhí)行過程中所需要的基本運算次數(shù) CPU 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 3 頁 5 算法的空間復(fù)雜度是指 算法執(zhí)行過程中所需要的存儲空間 6 一個算法通常由兩種基本要素組成 一是對數(shù)據(jù)對象的運算和操作 二 是算法的控制結(jié)構(gòu) 7 算法的 3 種基本控制結(jié)構(gòu) 順序 選擇 循環(huán) 8 算法設(shè)計的基本方法 列舉法 歸納法 遞推 遞歸和減半遞推技術(shù) 9 數(shù)據(jù)的存儲結(jié)構(gòu) 是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式 10 數(shù)據(jù)處理 是指對數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運算 11 數(shù)據(jù)結(jié)構(gòu) 是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合 12 數(shù)據(jù)元素之間的任何關(guān)系都可以用前驅(qū)和后繼關(guān)系來描述 13 常用的存儲結(jié)構(gòu)有順序 鏈接 索引等存儲結(jié)構(gòu) 14 采用不同的存儲結(jié)構(gòu) 數(shù)據(jù)處理的效率不同 15 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 循環(huán)隊列屬于存儲結(jié)構(gòu) 16 在數(shù)據(jù)結(jié)構(gòu)中 沒有前驅(qū)的結(jié)點稱為根結(jié)點 沒有后繼的結(jié)點稱為葉子 結(jié)點 17 數(shù)據(jù)結(jié)構(gòu)按邏輯關(guān)系的不同 通常可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類 18 在稍微復(fù)雜的線性表中 一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成 在這 種情況下 常把數(shù)據(jù)元素稱為記錄 含有大量記錄的線性表就稱作文件 19 在計算機(jī)中存放線性表 一種最簡單的方法是順序存儲 20 在程序設(shè)計語言中 通常定義一個一維數(shù)組來表示線性表的順序存儲空 間 21 棧 棧是一種只允許在一端進(jìn)行插入與刪除的線性表 22 棧的特點 1 先進(jìn)后出 或后進(jìn)先出 2 棧具有記憶作用 3 對 棧的操作中 不需要改變棧底指針 23 棧的基本運算有三種 入棧 退棧與讀棧頂元素 24 隊列 隊列是一種允許在一端進(jìn)行插入 而在另一端進(jìn)行刪除的線性表 允許插入的一端稱為隊尾 允許刪除的一端稱為隊頭 25 隊列的特點 先進(jìn)先出 或后進(jìn)后出 26 循環(huán)隊列主要有兩種基本運算 入隊運算與退隊運算 每進(jìn)行一次入隊 運算 隊尾指針就進(jìn)一 27 遞歸算法一般需要利用棧實現(xiàn) 28 對長度為 n 的線性表進(jìn)行插入一個新元素或刪除一個元素時 在最壞情 況下所需要的比較次數(shù)為 n 在平均情況下 需要比較次數(shù)為 n 2 29 線性鏈表屬于鏈?zhǔn)酱鎯Y(jié)構(gòu) 在鏈?zhǔn)酱鎯Y(jié)構(gòu)中 存儲空間可以不連續(xù) 各元素的存儲順序是任意的 30 在鏈?zhǔn)酱鎯Ψ绞街?要求每個結(jié)點由兩部分組成 一部分用于存放數(shù)據(jù) 元素值 稱為數(shù)據(jù)域 另一部分用于存放指針 稱為指針域 31 在線性單鏈表中 每一個結(jié)點只有一個指針域 由這個指針只能找到后 繼結(jié)點 但不能找到前驅(qū)結(jié)點 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 4 頁 32 與單向鏈表相比 雙向鏈表更容易訪問相鄰結(jié)點 33 在實際應(yīng)用中 帶鏈的?？梢杂脕硎占嬎銠C(jī)存儲空間中所有空閑的存 儲結(jié)點 這種帶鏈的棧稱為可利用棧 34 在線性鏈表中刪除一個元素 只需要改變被刪除元素所在結(jié)點的前一個 結(jié)點的指針域即可 35 在循環(huán)鏈表中 只要指出表中任何一個結(jié)點的位置 就可以從它出發(fā)訪 問到表中其他所有的結(jié)點 在對循環(huán)鏈表進(jìn)行插入和刪除的過程中 實現(xiàn)了 空表與非空表的運算統(tǒng)一 36 二叉樹的遍歷 是指不重復(fù)地訪問二叉樹中的所有結(jié)點 37 二叉樹的遍歷有三種 前序遍歷 中序遍歷 后序遍歷 1 前序遍歷 訪問根結(jié)點 前序遍歷左子樹 前序遍歷右子樹 2 中序遍歷 中序遍歷左子樹 訪問根結(jié)點 中序遍歷右子樹 3 后序遍歷 后序遍歷左子樹 后序遍歷右子樹 訪問根結(jié)點 38 滿二叉樹 除最后一層外 每一層上的所有結(jié)點都有兩個子結(jié)點 39 二叉樹的性質(zhì) 1 在二叉樹的第 k 層上 最多有 2k 1個結(jié)點 2 深度為 m 的二叉樹 最多有 2m 1 個結(jié)點 3 在任意一棵二叉樹中 度為 0 的結(jié)點 即葉子結(jié)點 總是比度為 2 的結(jié) 點多一個 40 完全二叉樹 除最后一層外 每一層上的所有結(jié)點都有兩個子結(jié)點 在 最后一層上缺少右邊的若干結(jié)點 41 對于長度為 n 的有序線性表 在最壞情況下 二分法查找需要比較 log2n 次 而順序查找需要比較 n 次 42 二分法查找只適用于順序存儲的有序線性表 43 順序查找一般是指在線性表中查找指定的元素 44 交換類排序 快速排序法和冒泡排序法 插入類排序 簡單插入排序法和希爾排序法 選擇類排序 簡單選擇排序法和堆排序法 45 對于長度為 n 的線性表 在最壞情況下 各種排序法的比較次數(shù) 冒泡排序 n n 1 2 快速排序 n n 1 2 簡單插入排序 n n 1 2 簡單選擇排序 n n 1 2 希爾排序 n1 5 堆排序 nlog2n 46 在最壞情況下 堆排序的時間復(fù)雜度最小 47 快速排序法可以實現(xiàn)通過一次交換而消除多個逆序 48 快速排序法的關(guān)鍵是對線性表進(jìn)行分割 第三章第三章 程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ) 1 程序設(shè)計風(fēng)格 清晰第一 效率第二 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 5 頁 2 源程序文檔化時程序應(yīng)加注釋 注釋一般分為序言性注釋和功能性注釋 3 在編寫程序時 需要注意數(shù)據(jù)說明的風(fēng)格 以便使程序中的數(shù)據(jù)說明更 易于理解和維護(hù) 4 程序應(yīng)該簡單易懂 語句構(gòu)造應(yīng)該簡單直接 不應(yīng)該為提高效率而把語 句復(fù)雜化 5 當(dāng)程序設(shè)計語言對輸入格式有嚴(yán)格要求時 應(yīng)保持輸入格式與輸入語句 的一致性 6 結(jié)構(gòu)化程序設(shè)計的主要特點是 1 程序易于理解 使用和維護(hù) 2 提高了編程工作的效率 降低了軟件開發(fā)成本 3 每個控制結(jié)構(gòu)只允許有一個入口和一個出口 7 結(jié)構(gòu)化程序設(shè)計的三種基本邏輯結(jié)構(gòu)為順序 選擇和循環(huán) 8 結(jié)構(gòu)化程序設(shè)計的主要原則 自頂向下 逐步求精 模塊化 限制使用 GOTO 語句 9 結(jié)構(gòu)化程序設(shè)計的一種基本方法是逐步求精法 10 在模塊化程序設(shè)計中 按功能劃分模塊的原則是 各模塊的功能盡量單 一 且各模塊之間的聯(lián)系盡量少 11 在面向?qū)ο蠓椒ㄖ?信息隱蔽是通過對象的封裝性來實現(xiàn)的 封裝是一 種信息隱蔽技術(shù) 12 在面向?qū)ο蠓椒ㄖ?類的實例稱為對象 13 在面向?qū)ο蠓椒ㄖ?類之間共享屬性和操作的機(jī)制稱為繼承 不是所有的對象都有繼承性 14 在面向?qū)ο蠓椒ㄖ?一個對象請求另一對象為其服務(wù)的方式是通過發(fā)送 消息 15 信息隱蔽的概念與模塊獨立性直接有關(guān) 耦合是指模塊之間聯(lián)系的緊密 程度 耦合度越高則模塊的獨立性越差 16 在面向?qū)ο蠓椒▽W(xué)中 直接反映了用戶對目標(biāo)系統(tǒng)的要求的模型是功能 模型 17 面向?qū)ο蠹夹g(shù)中 對象是類的實例 對象有三種成分 標(biāo)識 屬性和方 法 18 多態(tài)性 是指同一個操作作用于不同的對象可以有不同的解釋 產(chǎn)生不 同的執(zhí)行結(jié)果 第四章第四章 軟件工程基礎(chǔ)軟件工程基礎(chǔ) 1 軟件工程研究的內(nèi)容主要包括 軟件開發(fā)技術(shù)和軟件工程管理 2 軟件是程序 數(shù)據(jù)與相關(guān)文檔的集合 3 軟件工程的主要思想是強(qiáng)調(diào)在軟件開發(fā)過程中需要應(yīng)用工程化原則 4 軟件的生命周期 是從軟件產(chǎn)品提出 實現(xiàn) 使用維護(hù)到停止使用退役 的過程 軟件交付后還要進(jìn)行維護(hù) 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 6 頁 5 在軟件生命周期中 能準(zhǔn)確地確定軟件系統(tǒng)必須做什么和必須具備哪些 功能的階段是 需求分析 6 軟件工程的三要素是方法 工具和過程 7 軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的軟件工具集合 8 軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動 9 軟件生命周期一般包括可行性研究與需求分析 設(shè)計 實現(xiàn) 測試 交 付使用以及維護(hù)等活動 10 軟件工程的原則包括抽象 信息隱蔽 模塊化 局部化 確定性 一致 性 完備性和可驗證性 11 結(jié)構(gòu)化方法的核心和基礎(chǔ)是 結(jié)構(gòu)化程序設(shè)計理論 12 數(shù)據(jù)流程圖 DFD 是描述數(shù)據(jù)處理過程的工具 是需求理解的邏輯 模型的圖形表示 它直接支持系統(tǒng)的功能建模 在數(shù)據(jù)流程圖中 表示數(shù)據(jù)流 表示加工 表示文件 表示源 潭 是系統(tǒng)和環(huán)境的接口 屬系統(tǒng)之外的實體 表示存儲 13 在數(shù)據(jù)流程圖 DFD 中 帶有名字的箭頭表示數(shù)據(jù)的流向 14 結(jié)構(gòu)化分析 需求分析 常用工具有 數(shù)據(jù)流程圖 DFD 數(shù)據(jù)字典 DD 判定樹和判定表 15 Jackson 方法是一種面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化方法 16 軟件功能分解屬于總體設(shè)計階段 17 軟件需求分析階段的工作 可以分為 4 個方面 需求獲取 需求分析 編寫需求規(guī)格說明書以及需求評審 18 數(shù)據(jù)描述是對軟件系統(tǒng)所必須解決的問題作出的詳細(xì)說明 19 在結(jié)構(gòu)化分析方法中 用于描述系統(tǒng)中所用到的全部數(shù)據(jù)和文件的文檔 稱為數(shù)據(jù)字典 數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心 20 軟件需求規(guī)格說明書是需求分析階段的最后成果 21 軟件設(shè)計原則 抽象 模塊化 信息隱蔽 模塊獨立性 22 在結(jié)構(gòu)化設(shè)計方法中生成的結(jié)構(gòu)圖 SC 中 帶有箭頭的連線表示 模塊之間的調(diào)用關(guān)系 23 為了使模塊盡可能獨立 要求 模塊的內(nèi)聚程度要盡量高 且各模塊間 的耦合程度要盡量弱 24 耦合 是指模塊之間聯(lián)系的緊密程度 耦合度越高則模塊的獨立性越差 內(nèi)聚 是指模塊內(nèi)部各元素之間聯(lián)系的緊密程度 內(nèi)聚度越低則模塊 獨立性越差 25 數(shù)據(jù)流程圖的類型有變換型和事務(wù)型兩種 26 將變換型映射成結(jié)構(gòu)圖 稱為變換分析 27 好的軟件設(shè)計結(jié)構(gòu)通常頂層高扇出 中間扇出較少 底層高扇入 一個模塊的扇入是指直接調(diào)用該模塊的上級模塊個數(shù) 一個模塊的扇出 是指該模塊直接調(diào)用的下級模塊的個數(shù) 扇入大表示模塊的復(fù)用程度高 扇 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 7 頁 出大表示模塊的復(fù)雜度高 28 模塊的作用范圍應(yīng)在控制范圍之內(nèi) 29 詳細(xì)設(shè)計的方法主要是結(jié)構(gòu)化程序設(shè)計 30 常用的圖形描述工具有 程序流程圖 盒圖和問題分析圖 31 常見的過程設(shè)計工具有 1 圖形工具 程序流程圖 N S PAD HIPO 2 表格工具 判定表 3 語言工具 PDL 過程設(shè)計語言 32 詳細(xì)設(shè)計的典型的語言描述工具是 PDL 33 軟件測試的目的 是盡可能多地發(fā)現(xiàn)軟件產(chǎn)品 主要是指程序 中的錯 誤和缺陷 34 軟件調(diào)試的目的 是改正程序中的錯誤 35 程序經(jīng)調(diào)試改錯后還應(yīng)進(jìn)行再測試 36 黑盒測試 是根據(jù)規(guī)格說明所規(guī)定的功能來設(shè)計測試用例 它不考慮程 序的內(nèi)部結(jié)構(gòu)和處理過程 白盒測試 是在程序內(nèi)部進(jìn)行 主要用于完成軟 件內(nèi)部所有數(shù)據(jù)結(jié)構(gòu)的驗證 37 軟件測試的方法和技術(shù)是多種多樣的 從是否需要執(zhí)行被測軟件的角度 可以分為 靜態(tài)測試與動態(tài)測試 若按功能劃分則可分為白盒測試和黑盒測 試方法 38 靜態(tài)測試 包括代碼檢查 靜態(tài)結(jié)構(gòu)分析 代碼質(zhì)量度量等 靜態(tài)測試 不實際運行軟件 主要通過人工進(jìn)行 動態(tài)測試 是基于計算機(jī)的測試 是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程 39 在進(jìn)行模塊測試時 要為每個被測試的模塊另外設(shè)計兩類模塊 驅(qū)動模 塊和承接模塊 其中驅(qū)動模塊的作用是將測試數(shù)據(jù)傳送給被測試的模塊 并 顯示被測試模塊所產(chǎn)生的結(jié)果 承接模塊是用于代替被測試模塊調(diào)用的其他 模塊 它僅做少量的數(shù)據(jù)操作 是一個模擬子程序 不必將子模塊的所有功 能帶入 40 檢查軟件產(chǎn)品是否符合需求定義的過程稱為確認(rèn)測試 41 白盒測試方法一般適合用于單元測試 黑盒測試一般適合用于集成測試 和確認(rèn)測試 42 軟件測試過程一般按 4 個步驟進(jìn)行 即單元測試 集成測試 驗收測試 確認(rèn)測試 和系統(tǒng)測試 43 軟件調(diào)試方法主要有強(qiáng)行排錯法 回溯法和原因排除法 第五章第五章 數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ) 1 數(shù)據(jù)庫技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)的共享問題 2 數(shù)據(jù)庫系統(tǒng)由 5 部分構(gòu)成 數(shù)據(jù)庫 數(shù)據(jù)庫管理系統(tǒng) 數(shù)據(jù)庫管理員 硬件和軟件 3 在數(shù)據(jù)管理技術(shù)的發(fā)展過程中 經(jīng)歷了人工管理階段 文件系統(tǒng)階段和 數(shù)據(jù)庫系統(tǒng)階段 其中數(shù)據(jù)獨立性最高的階段是數(shù)據(jù)庫系統(tǒng) 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 8 頁 4 數(shù)據(jù)庫系統(tǒng)減少了數(shù)據(jù)冗余 5 數(shù)據(jù)庫系統(tǒng)的核心是 數(shù)據(jù)庫管理系統(tǒng) DBMS 6 數(shù)據(jù) 就是描述事物的符號記錄 7 數(shù)據(jù)庫是數(shù)據(jù)的集合 具有統(tǒng)一的結(jié)構(gòu)形式 是多種應(yīng)用數(shù)據(jù)的集成 并可被各個應(yīng)用程序所共享 8 數(shù)據(jù)庫管理系統(tǒng)提供了 3 種數(shù)據(jù)語言 1 數(shù)據(jù)定義語言 DDL 該語言負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取 構(gòu)建 2 數(shù)據(jù)操縱語言 DML 該語言負(fù)責(zé)數(shù)據(jù)的操縱 包括查詢及增 刪 改等操作 3 數(shù)據(jù)控制語言 DCL 該語言負(fù)責(zé)數(shù)據(jù)完整性 安全性的定義與檢查以 及并發(fā)控制 故障恢復(fù)等功能 9 數(shù)據(jù)庫應(yīng)用系統(tǒng)由數(shù)據(jù)庫系統(tǒng) 應(yīng)用軟件和應(yīng)用界面組成 10 數(shù)據(jù)獨立性一般分為物理獨立性與邏輯獨立性 物理獨立性 數(shù)據(jù)的物理結(jié)構(gòu)的改變 不影響數(shù)據(jù)庫的邏輯結(jié)構(gòu) 從 而不致引起應(yīng)用程序的變化 邏輯獨立性 數(shù)據(jù)庫總體邏輯結(jié)構(gòu)的改變 不需要相應(yīng)修改應(yīng)用程序 這就是數(shù)據(jù)的邏輯獨立性 11 所謂數(shù)據(jù)獨立性是指數(shù)據(jù)不依賴于應(yīng)用程序 數(shù)據(jù)的邏輯結(jié)構(gòu) 存儲結(jié) 構(gòu)與存取方式的改變不會影響應(yīng)用程序 12 數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)集成性的主要特征是 全局與局部的結(jié)構(gòu)模式 13 數(shù)據(jù)庫系統(tǒng)在其內(nèi)部具有三級模式及二級映射 三級模式分別是概念級 模式 內(nèi)部級模式與外部級模式 二級映射分別是概念級到內(nèi)部級的映射以及外部級到概念級的映射 概念級模式 是數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述 是全體用戶公共數(shù) 據(jù)視圖 外部級模式 也稱子模式或用戶模式 它是用戶的數(shù)據(jù)視圖 也就是用戶所 見到的數(shù)據(jù)模式 內(nèi)部級模式 又稱物理模式 給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法 如數(shù)據(jù)存儲的文件結(jié)構(gòu) 索引 集簇及 hash 等存取方式與存取路徑 14 以內(nèi)模式為框架所組成的數(shù)據(jù)庫叫物理數(shù)據(jù)庫 15 相對于數(shù)據(jù)庫系統(tǒng) 文件系統(tǒng)的主要缺陷有數(shù)據(jù)聯(lián)系弱 數(shù)據(jù)的不一致 性和數(shù)據(jù)的冗余性 16 數(shù)據(jù)庫系統(tǒng)通過二級映射建立了模式間的聯(lián)系與轉(zhuǎn)換 17 由于數(shù)據(jù)庫的共享性 因此對數(shù)據(jù)庫的規(guī)劃 設(shè)計 維護(hù) 監(jiān)視等需要 有專人管理 稱他們?yōu)閿?shù)據(jù)庫管理員 18 數(shù)據(jù)模型所描述的內(nèi)容有數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)操作與數(shù)據(jù)約束三個部分 19 常見的數(shù)據(jù)模型有三種 層次模型 網(wǎng)狀模型和關(guān)系模型 層次模型 用樹形結(jié)構(gòu)來表示實體之間聯(lián)系的模型 網(wǎng)狀模型 用網(wǎng)狀結(jié)構(gòu)來表示實體之間聯(lián)系的模型 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 9 頁 關(guān)系模型 用二維表結(jié)構(gòu)來表示實體之間聯(lián)系的模型 20 在關(guān)系數(shù)據(jù)庫中 把數(shù)據(jù)表示成二維表 每一個二維表稱為關(guān)系 21 E R 模型的基本概念 實體 屬性 聯(lián)系 實體 客觀存在的并且可以下互區(qū)別的事物 屬性 實體的特性 聯(lián)系 現(xiàn)實世界中事物間的關(guān)聯(lián) 22 實體集間的聯(lián)系有多種 就實體集的個數(shù)而言有 1 兩個實體集間的聯(lián)系 2 多個實體集間的聯(lián)系 3 一個實體集內(nèi) 部的聯(lián)系 23 兩個實體集間的聯(lián)系 一對一 1 1 一對多 1 M 多對 一 M 1 多對多 M N 24 一個項目具有一個項目主管 一個項目主管可管理多個項目 則實體 項目主管 與實體 項目 的聯(lián)系屬于一對多的聯(lián)系 25 一個關(guān)系的屬性名表稱為關(guān)系模式 26 下列數(shù)據(jù)模型中 具有堅實理論基礎(chǔ)的是 C A 層次模型 B 網(wǎng)狀模型 C 關(guān)系模型 D 以上 3 個都是 27 關(guān)系模型的數(shù)據(jù)操縱即是建立在關(guān)系上的數(shù)據(jù)操縱 一般有查詢 增加 刪除及及修改 4 種操作 28 對關(guān)系數(shù)據(jù)庫的查詢可以分解成一個關(guān)系內(nèi)部的屬性指定 一個關(guān)系內(nèi) 的元組選擇 兩個關(guān)系的合并三個基本定位操作以及一個查詢操作 29 關(guān)系表中的每一行稱為一個元組 每一列稱為一個屬性 30 數(shù)據(jù)模型分為格式化模型與非格式化模型 層次模型與網(wǎng)狀模型屬于格 式化模型 31 關(guān)系模型的完整性規(guī)則是對關(guān)系的某種約束條件 包括實體完整性 參 照完整性和自定義完整性 32 關(guān)系型數(shù)據(jù)庫管理系統(tǒng)中存儲與管理數(shù)據(jù)的基本形式是二維表 33 關(guān)系代數(shù)是以集合代數(shù)為基礎(chǔ)發(fā)展起來的 以關(guān)系為運算對象的一組高 級運算的集合 常用的操作有并 差 交 笛卡兒積 投影 選擇和連接等 34 下列關(guān)系運算中 能使經(jīng)運算后得到的新關(guān)系中屬性個數(shù)多于原來關(guān)系 中屬性個數(shù)的是 B A 選擇 B 連接 C 投影 D 并 35 下列關(guān)系運算中 能使經(jīng)運算后得到的新關(guān)系中元組個數(shù)少于原來關(guān)系 中元組個數(shù)的是 A A 選擇 B 連接 C 投影 D 并 36 按條件 f 對關(guān)系 R 進(jìn)行選擇 其關(guān)系代數(shù)表達(dá)式是 f R 37 關(guān)系數(shù)據(jù)庫管理系統(tǒng)能實現(xiàn)的專門關(guān)系運算包括 選擇 投影 連接 38 將 E R 圖轉(zhuǎn)換到關(guān)系模式時 實體與聯(lián)系都可以表示成關(guān)系 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 10 頁 39 數(shù)據(jù)庫設(shè)計是指在已有數(shù)據(jù)庫管理系統(tǒng)的基礎(chǔ)上建立數(shù)據(jù)庫 40 數(shù)據(jù)庫設(shè)計包括兩個方面的設(shè)計內(nèi)容 它們是概念設(shè)計和邏輯設(shè)計 41 數(shù)據(jù)庫設(shè)計一般采用生命周期法 42 E R 模型可以轉(zhuǎn)換成關(guān)系模型 當(dāng)兩個實體間聯(lián)系是 M N 聯(lián)系時 它通?？赊D(zhuǎn)換成 3 個關(guān)系模式 43 數(shù)據(jù)庫的物理結(jié)構(gòu)主要指數(shù)據(jù)庫的存儲記錄格式 存儲記錄安排和存取 方法 44 數(shù)據(jù)庫的建立包括數(shù)據(jù)模式的建立與數(shù)據(jù)加載 基礎(chǔ)知識部分習(xí)題基礎(chǔ)知識部分習(xí)題 一 選擇題 1 下列敘述中正確的是 A 算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) B 算法的空間復(fù)雜度是指執(zhí)行算 法程序中指令 或語句 的條數(shù) C 算法的有窮性是指算法必須能執(zhí)行有限 個步驟之后終止 D 以上 3 種描述都不對 2 以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是 A 隊列 B 線性表 C 二叉樹 D 棧 3 在一棵二叉樹上第 5 層的結(jié)點數(shù)最多是 A 8 B 16 C 32 D 15 4 在深度為 7 的滿二叉樹中 葉子結(jié)點的個數(shù)為 A 32 B 31 C 64 D 63 5 對長度為 N 的線性表進(jìn)行順序查找 在最壞情況下所需要的比較次數(shù)為 A log2n B n 2 C n D n 1 6 設(shè)樹 T 的度為 4 其中度為 1 2 3 4 的結(jié)點個數(shù)分別為 4 2 1 1 則葉子結(jié)點 A 8 B 7 C 6 D 5 7 一棵二叉樹共有 70 個葉子結(jié)點與 80 個度為 1 的結(jié)點 則該二叉樹中總 的結(jié)點個數(shù)為 A 221 B 219 C 231 D 229 8 設(shè)棧 S 的初始狀態(tài)為空 元素 a b c d e f 依次通過棧 S 若出棧 的順序是 b d c f e a 則棧的容量至少應(yīng)該為 A 3 B 4 C 5 D 6 9 已知二叉樹后序遍歷序列是 DABEC 中序遍歷是 DEBAC 則前序遍歷 是 A ACBED B DECAB C DEABC D CEDBA 10 如果進(jìn)棧序列為 e1 e2 e3 e4 則可能的出棧序列是 A e3 e1 e4 e2 B e2 e4 e3 e1 C e3 e4 e1 e2 D 任意順序 11 下列選項中不屬于結(jié)構(gòu)化程序設(shè)計方法的是 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 11 頁 A 自頂向下 B 逐步求精 C 模塊化 D 可復(fù)用 12 下面不屬于面向?qū)ο蠓椒ǖ氖?A 對象 B 繼承 C 類 D 過程調(diào)用 13 數(shù)據(jù)庫系統(tǒng)的核心是 A 數(shù)據(jù)模型 B 數(shù)據(jù)庫管理系統(tǒng) C 軟件工具 D 數(shù)據(jù)庫 14 將 E R 圖轉(zhuǎn)換到關(guān)系模式時 實體和聯(lián)系都可以表示成 A 屬性 B 關(guān)系 C 鍵 D 域 15 SQL 語言又稱為 A 結(jié)構(gòu)化定義語言 B 結(jié)構(gòu)化控制語言 C 結(jié)構(gòu)化查詢語言 D 結(jié)構(gòu)化操縱語言 16 下在不屬于軟件工程的 3 個要素的是 A 工具 B 過程 C 方法 D 環(huán)境 17 下面各項中不屬于軟件生命周期中的開發(fā)階段的是 A 需求分析 B 程序設(shè)計 C 概要設(shè)計 D 軟件測試 18 軟件生命周期中所花費用最多的階段是 A 詳細(xì)設(shè)計 B 軟件編碼 C 軟件測試 D 軟件維護(hù) 19 程序設(shè)計語言的基本成分是數(shù)據(jù)成分 運算成分 控制成分和 A 對象成分 B 變量成分 C 語句成分 D 傳輸成分 20 以下不屬于對象的基本特點的是 A 分類性 B 多態(tài)性 C 繼承性 D 封裝性 二 填空題 1 設(shè)一棵完全二叉樹共有 700 個結(jié)點 則二叉樹中有 個葉子結(jié)點 2 在一個容量為 15 的循環(huán)隊列中 若頭指針為 front 6 尾指針 rear 9 則該循環(huán)隊列中共有 個元素 3 軟件是程序 數(shù)據(jù)和 的集合 4 在一個關(guān)系數(shù)據(jù)庫中 把數(shù)據(jù)表示成二維表 每個二維表稱為 5 數(shù)據(jù)庫系統(tǒng)在其內(nèi)部分為三級模式 即概念模式 內(nèi)模式和外模式 其 中 給出了數(shù)據(jù)庫中物理存儲結(jié)構(gòu)與物理存取方法 6 在面向?qū)ο蠓椒ㄖ?信息隱蔽是通過對象的 性來實現(xiàn)的 7 面向?qū)ο蟮哪Ｐ椭?最基本的概念是對象和 8 測試的目的是暴露錯誤 評價程序的可靠性 而 的目的是發(fā)現(xiàn) 錯誤的位置并改正錯誤 9 完成下列數(shù)制間的轉(zhuǎn)換 1 127 10 2 2 0 45 10 2 3 57 256 10 2 4 1101011 2 8 16 5 49A B6 16 8 2 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 12 頁 第十屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題 普及組 Pascal 語言 二小時完成 一 選擇一個正確答案代碼 一 選擇一個正確答案代碼 A B C D E 填入每題的掛號內(nèi) 填入每題的掛號內(nèi) 1 美籍匈牙利數(shù)學(xué)家 馮 諾依曼 對計算機(jī)科學(xué)發(fā)展所做出的貢獻(xiàn)是 A 提出理想計算機(jī)數(shù)學(xué)模型 成為計算機(jī)科學(xué)理論基礎(chǔ) B 是世界上第一個編寫計算機(jī)程序的人 C 提出存儲程序工作原理 并設(shè)計出第一臺具有存儲程序功能的計算 機(jī) EDVAC D 采用集成電路作為計算機(jī)的主要功能部件 E 指出計算機(jī)性能將以每兩年翻一番的速度向前發(fā)展 2 下列哪個不是 CPU 中央處理單元 A Intel Itanium B DDR SDRAM C AMD Athlon64 D AMD Opteron E IBM Power 5 3 下列網(wǎng)絡(luò)中常用的名字縮寫對應(yīng)的中文解釋錯誤的是 A WWW World Wide Web 萬維網(wǎng) B URL Uinform Resource Locator 統(tǒng)一資源定位器 C HTTP Hypertext Transfer Protocol 超文本傳輸協(xié)議 D FTP File Transfer Protocol 快速傳輸協(xié)議 E TCP Transfer Control Protocol 傳輸控制協(xié)議 4 下面哪個部件對于個人桌面電腦的正常運行不是必需的 A cpu B 顯卡 圖形卡 C 光驅(qū) D 主板 E 內(nèi)存 5 下列哪個軟件屬于操作系統(tǒng)軟件 A Microsoft Word B 金山詞霸 C Foxmail D WinRAR E Red Hat Linux 6 下列哪個不是計算機(jī)存儲設(shè)備 A 文件管理器 B 內(nèi)存 C 高速緩存 D 硬盤 E U 盤 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 13 頁 7 下列說法中錯誤的是 A CPU 的基本功能就是執(zhí)行指令 B CPU 訪問內(nèi)存的速度快于訪問高速緩存的速度 C CPU 的主頻是指 CPU 在 1 秒內(nèi)完成的指令周期數(shù) D 在一臺計算機(jī)內(nèi)部 一個內(nèi)存地址編碼對應(yīng)唯一的一個內(nèi)存單元 E 數(shù)據(jù)中線的寬度決定了一次傳遞數(shù)據(jù)量的大小 8 彩色顯示器所顯示的五彩斑斕的色彩 是由紅色 藍(lán)色和 色混合而 成的 A 紫色 B 白色 C 黑色 D 綠色 E 橙色 9 用靜電吸附磨粉后轉(zhuǎn)移到紙張上 是那種輸出設(shè)備的工作方式 A 針式打印機(jī) B 噴墨打印機(jī) C 激光打印機(jī) D 筆式繪圖儀 E 噴墨繪圖儀 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)橋 11 下列哪個不是數(shù)據(jù)庫軟件的名稱 A MYSQL B SQL Sever C Oracle D 金山影霸 E Foxpro 12 下列哪個程序設(shè)計語言不支持面向?qū)ο蟮某绦蛟O(shè)計方法 A C B Object Pascal C C D Smalltalk E Java 13 由 3 個 a 1 個 b 和 2 個 c 構(gòu)成的所有字符串中 包含子串 abc 的共 有 個 A 20 B 8 C 16 D 12 E 24 14 某車站呈狹長形 寬度只能容下一臺車 并且只有一個出入口 已知某 時該車站站臺為空 從這一時刻開始出入記錄為 進(jìn)出進(jìn)進(jìn)出進(jìn)進(jìn)進(jìn) 出出進(jìn)出 假設(shè)車輛入站的順序為 1 2 3 則車輛出站的順序為 A 1 2 3 4 5 B 1 2 4 5 7 C 1 3 5 4 6 D 1 3 5 6 7 E 1 3 6 5 7 15 二叉樹 T 已知其前序遍歷序列為 1 2 4 3 5 7 6 中序遍歷序列為 4 2 1 5 7 3 6 其后序遍歷序列為 A 4 2 5 7 6 3 1 B 4 2 7 5 6 3 1 C 4 2 7 5 3 6 1 D 4 7 2 3 5 6 1 E 4 5 2 6 3 7 1 16 滿二叉樹的葉節(jié)點為 N 則它的節(jié)點總數(shù)為 A N B 2N C 2N 1 D 2N 1 E 2 N 1 17 十進(jìn)制 2004 等于八進(jìn)制數(shù) 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 14 頁 A 3077 B 3724 C 2766 D 4002 E 3755 18 2004 10 32 16的結(jié)果是 A 2036 10 B 2054 16 C 4006 10 D 100000000110 2 E 2036 16 19 在下圖 從端點 出發(fā)存在一條路徑可以遍歷圖中的每條邊一次 而且僅遍歷一次 20 某大學(xué)計算機(jī)專業(yè)的必修課及期先修課程如下表所示 課程 代號 C0C1C2C3C4C5C6C7 課程 名稱 高等 數(shù)學(xué) 程序 設(shè)計 語言 離散 數(shù)學(xué) 數(shù)據(jù) 結(jié)構(gòu) 編譯 技術(shù) 操作 系統(tǒng) 普通 物理 計算 機(jī)原 理 先修 課程 C0 C1C1 C2C3C3 C7C0C6 請判斷下列課程安排哪個是不合理的 A C0 C6 C7 C1 C2 C3 C4 C5 B C0 C1 C2 C3 C4 C6 C7 C5 C C0 C1 C6 C7 C2 C3 C4 C5 D C0 C1 C6 C7 C5 C2 C3 C4 E C0 C1 C2 C3 C6 C7 C5 C4 二 問題求解 二 問題求解 5 分一題 共分一題 共 10 分 分 1 一個家具公司生產(chǎn)桌子和椅子 現(xiàn)有 113 個單位的木材 每張桌子要使 用 20 個單位的木材 售價是 30 元 每張椅子要用 16 個單位的木材 售 價是 20 元 使用已有的木材生產(chǎn)桌椅 不一定要用光木材 做多可以買 元錢 2 75 名兒童去游樂場玩 他們可以騎旋轉(zhuǎn)木馬 坐滑行軌道 乘宇宙飛船 已知其中 20 人這三種東西都玩過 55 人至少玩過其中兩種 若每玩一樣 的費用為 5 元 游樂場總共收入 700 可知有 名兒童沒有玩過其中 任何一種 三 閱讀程序 三 閱讀程序 8 一題 共一題 共 32 1 program program1 Var a b c d e integer begin a 79 b 34 c 57 d 0 e 1 if ac then d d e else if d 10 e then d e 10 else d e a writeln d A ED B C 兄弟培訓(xùn)內(nèi)部教學(xué)資料 第 15 頁 end 輸出 2 program program2 var i j integer str1 str2 string begin str1 pig is stupid str2 clever str1 1 d str1 2 o i 8 for j 1 to 6 do begin str1 i str2 j inc i end writeln str1 end 輸出 3 program program3 var u array 0 3 of integer a b c x y z integer begin read u 0 u 1 u 2 u 3 a u 0 u 1 u 2 u 3 5 b u 0 u 1 u 2 div u 3 8 c u 0 u 1 div u 2 u 3 x a b 2 3 u c 3 mod 4 y c 100 13 div a div u b mod 3 5 if x y mod 2 0 then z a b c x y div 2 z a b c x y 2 w