【導(dǎo)讀】參考“00_本次省計(jì)算機(jī)等級(jí)考。計(jì)算機(jī)的發(fā)展與應(yīng)用。計(jì)算機(jī)的基本組成及原理。微型計(jì)算機(jī)的外部設(shè)備。電子商務(wù)和電子政務(wù)。計(jì)算機(jī)的進(jìn)制轉(zhuǎn)換。依運(yùn)算速度、輸入輸出能力、數(shù)據(jù)容量、位數(shù)就越多，精度就越高。機(jī)字長(zhǎng)有：8位、16位、32位和64位。存儲(chǔ)器容量為：128MB以上。機(jī)則以主時(shí)鐘頻率來表示。主頻”）一般有1Ghz以上。打印機(jī)的型號(hào)和速度。掃描儀、數(shù)碼相機(jī)、數(shù)碼攝相。從功能角度看分為五部分：。由運(yùn)算器和控制器合在一起組成。由CPU和內(nèi)存儲(chǔ)器組成。由輸入、輸出設(shè)備和外存儲(chǔ)器組成。所能讀取的最大數(shù)據(jù)量。1倍速光驅(qū)的數(shù)據(jù)傳輸率為：150Kbps。扇區(qū)、磁道和面數(shù)等概念。格式化容量的計(jì)算

　　

【正文】 )。 A 計(jì)算機(jī)考前培訓(xùn) 第六部分 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)與算法的基本概念 線性表的基本概念和基本運(yùn)算 棧和隊(duì)的基本概念和基本運(yùn)算 二叉樹的基本知識(shí) 計(jì)算機(jī)考前培訓(xùn) 數(shù)據(jù)結(jié)構(gòu)與算法的基本概念 ? 主要研究?jī)?nèi)容： 研究數(shù)據(jù)在計(jì)算機(jī)中的 表示方 法 、 關(guān)聯(lián)方法 、 存儲(chǔ)方法 以及在其 上的 典型處理方法 ，就構(gòu)成了數(shù)據(jù) 結(jié)構(gòu)與算法的。 計(jì)算機(jī)考前培訓(xùn) 數(shù)據(jù)結(jié)構(gòu)與算法的基本概念 ? 數(shù)據(jù)元素（ Data Element） ? 數(shù)據(jù)結(jié)構(gòu)（ Data Structure） ? 算法和算法分析 計(jì)算機(jī)考前培訓(xùn) 四類基本數(shù)據(jù)結(jié)構(gòu) 1）集合 （ 同屬于一個(gè)集合 ） 2）線性結(jié)構(gòu) （ 一個(gè)對(duì)一個(gè)關(guān)系 ） 3）樹形結(jié)構(gòu) （ 一個(gè)對(duì)多個(gè) ） 4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) （多個(gè)對(duì)多個(gè)） a） 集合結(jié)構(gòu) b） 線性結(jié)構(gòu) c） 樹型結(jié)構(gòu) d） 圖形結(jié)構(gòu) 計(jì)算機(jī)考前培訓(xùn) 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)元素 ? 數(shù)據(jù)元素的邏輯結(jié)構(gòu) ? 數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu) ? 數(shù)據(jù)元素的運(yùn)算 計(jì)算機(jī)考前培訓(xùn) ? 數(shù)據(jù)元素的邏輯結(jié)構(gòu)只抽象地反映數(shù)據(jù)元素間的 邏輯關(guān)系 ，而不管其在計(jì)算機(jī)中的 存儲(chǔ)表示 方式。 ? 通常分為 線性 結(jié)構(gòu)和 非線性 結(jié)構(gòu) ? 線性表 是線性結(jié)構(gòu) ? 樹、圖 是非線性結(jié)構(gòu) 計(jì)算機(jī)考前培訓(xùn) 數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu) ? 實(shí)現(xiàn)數(shù)據(jù)元素的 邏輯結(jié)構(gòu) 到計(jì)算機(jī) 存儲(chǔ)器 的映象 ， 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)表示分二種： 1）順序存儲(chǔ)結(jié)構(gòu) 2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 計(jì)算機(jī)考前培訓(xùn) 順序存儲(chǔ)結(jié)構(gòu) ? 把 邏輯上 相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上 相鄰的兩個(gè)存儲(chǔ)單元里。 計(jì)算機(jī)考前培訓(xùn) 順序存儲(chǔ)結(jié)構(gòu)特點(diǎn) ①存儲(chǔ)密度大，存儲(chǔ)空間利用率高； ②可以通過計(jì)算直接確定數(shù)據(jù)結(jié)構(gòu)中 第 i個(gè)節(jié)點(diǎn)的存儲(chǔ)地址 ,支持隨機(jī)存?。? ③插入、刪除運(yùn)算不便，會(huì)引起大量 節(jié)點(diǎn)的移動(dòng) 計(jì)算機(jī)考前培訓(xùn) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ? 把 邏輯上 相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上不 相鄰的兩個(gè)存儲(chǔ)單元里。 計(jì)算機(jī)考前培訓(xùn) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn) ① 存儲(chǔ)密度小，存儲(chǔ)空間利用率低； ②邏輯上相鄰的節(jié)點(diǎn)物理上不必鄰接； ③ 插入、刪除操作靈活方便 ，不必移動(dòng) 節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的 指針值 即可。 計(jì)算機(jī)考前培訓(xùn) 數(shù)據(jù)元素的運(yùn)算 ? 常用的運(yùn)算有 檢索 、 插入 、 刪除 、更新 、 排序 等 計(jì)算機(jī)考前培訓(xùn) 算法和算法分析 1．算法（ Algorithm） 2．算法設(shè)計(jì)的要求 3．算法的復(fù)雜度度量 計(jì)算機(jī)考前培訓(xùn) 算法 1．算法（ Algorithm） 2．算法設(shè)計(jì)的要求 3．算法的復(fù)雜度度量 計(jì)算機(jī)考前培訓(xùn) 算法 1．算法（ Algorithm） : ? 是對(duì)特定問題求解步驟的一種描述 ,它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作； 計(jì)算機(jī)考前培訓(xùn) 算法 1．算法的五個(gè)重要特性： ? 有窮性 有窮步之后結(jié)束 ,有窮時(shí)間內(nèi)完成 ? 確定性 指令無二義性 ? 可行性 算法是可實(shí)現(xiàn)的 ? 輸入 一個(gè)算法有零個(gè)或多個(gè)的輸入 ? 輸出 一個(gè)算法有零個(gè)或多個(gè)的輸出 計(jì)算機(jī)考前培訓(xùn) 算法設(shè)計(jì)的要求 通常設(shè)計(jì)一個(gè)“好”的算法應(yīng)考慮 達(dá)到以下幾個(gè)目標(biāo)： ? 正確性 ? 可讀性 ? 健壯性 ? 效率和 低 存儲(chǔ)量的需求 注意： 在設(shè)計(jì)一個(gè)算法時(shí)應(yīng)先考慮算法的 可讀性 然后再考慮 算法的效率和存儲(chǔ)量 。 計(jì)算機(jī)考前培訓(xùn) 算法設(shè)計(jì)的要求 ? 正確性： 所設(shè)計(jì)的程序?qū)τ?精心 選擇的典型、 苛刻 而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到 滿足要求的結(jié)果 ； ? 健壯性 ： 當(dāng)輸入 數(shù)據(jù)非法 時(shí)，算法也能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫明其妙的輸出結(jié)果。 ? 效率： 指的是算法執(zhí)行的時(shí)間 計(jì)算機(jī)考前培訓(xùn) 算法的復(fù)雜度度量 算法的復(fù)雜度： 通常是指算法的 時(shí)間復(fù)雜度 ，算法執(zhí)行的時(shí)間需要通過依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間來度量 。 ? 算法的時(shí)間復(fù)雜度分析通常采用O(f(n))表示 計(jì)算機(jī)考前培訓(xùn) 線性表 ? 順序表： 用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。 ? 鏈表： 用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。 計(jì)算機(jī)考前培訓(xùn) 線性表的特點(diǎn) 在非空有限集中： ① 存在唯一的一個(gè)被稱作“ 第一個(gè) ”的元素； ② 存在唯一的一個(gè)被稱作“ 最后一個(gè) ”的數(shù)據(jù)元素； 計(jì)算機(jī)考前培訓(xùn) 線性表的特點(diǎn) 在非空有限集中： ③ 除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè) 前驅(qū) ； ④ 除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè) 后繼 。 計(jì)算機(jī)考前培訓(xùn) ? 插入或刪除一個(gè)數(shù)據(jù)元素，其時(shí)間主要消耗在 移動(dòng)元素上 ，而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置。 ? 在順序表中插入或刪除一個(gè)數(shù)據(jù)元素的算法復(fù)雜度均為 O(n). 計(jì)算機(jī)考前培訓(xùn) 線性鏈表 ? 每個(gè)數(shù)據(jù)元素，除了存放數(shù)據(jù)元素 自身 的信息之外，還需要和一起存放其 后繼 所在的存貯單元的地址 ，這兩部分信息組成一個(gè)“結(jié)點(diǎn)”。 data link 單鏈表結(jié)點(diǎn)結(jié)構(gòu) 計(jì)算機(jī)考前培訓(xùn) 線性鏈表的基本運(yùn)算 ? 插入運(yùn)算有兩種方式： ? 有后插結(jié)點(diǎn) ? 有前插結(jié)點(diǎn) 計(jì)算機(jī)考前培訓(xùn) 后插結(jié)點(diǎn) 在 *p之后插入 *s p s ① ② 設(shè) p指向單鏈表中某結(jié)點(diǎn)， s指向待插入的值為 x的新結(jié)點(diǎn) ,將 *s(*s表示 s所指向的節(jié)點(diǎn) )插入到 *p的后面 計(jì)算機(jī)考前培訓(xùn) 前插結(jié)點(diǎn) 在 *p之前插入 *s s p q 設(shè) p指向單鏈表中某結(jié)點(diǎn)， s指向待插入的值為 x的新結(jié)點(diǎn) ,將 *s(*s表示 s所指向的節(jié)點(diǎn) )插入到 *p的前面 ,與后插不同的是 ：首先要 找到 *p的前驅(qū) *q，然后再完成在 *q之后插入 *s。 ① ② ③ 計(jì)算機(jī)考前培訓(xùn) 棧和隊(duì) ? 棧 按 “后進(jìn)先出” 的規(guī)則進(jìn)行操作 ? 隊(duì) 按 “先進(jìn)先出” 的規(guī)則進(jìn)行操作 ? 故它們稱運(yùn)算 受限制 的線性表。 計(jì)算機(jī)考前培訓(xùn) 棧 ( LIFO表 ) ? 棧是限制在表的 一端 進(jìn)行插入和刪除的線性表 ? 允許插入、刪除的這一端稱為 棧頂 ? 另一個(gè)固定端稱為 棧底 ? 當(dāng)表中沒有元素時(shí)稱為 空棧， 空棧時(shí)棧頂指針 top=1。 入棧時(shí)，棧頂指針 加１ ，出棧時(shí)，棧頂指針 減１ 計(jì)算機(jī)考前培訓(xùn) 隊(duì) ( FIFO表 ) ? 即插入在表一端進(jìn)行，而刪除在表的另一端進(jìn)行，我們將這種數(shù)據(jù)結(jié)構(gòu)稱為 隊(duì)或隊(duì)列 ? 把允許插入的一端叫 隊(duì)尾 (rear) ? 把允許刪除的一端叫 隊(duì)頭 (front) 計(jì)算機(jī)考前培訓(xùn) 二叉樹的基本知識(shí) ? 結(jié)點(diǎn)的度 ： 結(jié)點(diǎn)所擁有的 子樹 的個(gè)數(shù)稱為該結(jié)點(diǎn)的度 ? 葉結(jié)點(diǎn) ： 度為 0的結(jié)點(diǎn) ? 結(jié)點(diǎn)的層數(shù)： 規(guī)定樹的根結(jié)點(diǎn)的層 數(shù)為 1 ? 樹的深度： 樹中所有結(jié)點(diǎn)的最大層 數(shù)稱為樹的深度 計(jì)算機(jī)考前培訓(xùn) 二叉樹的基本知識(shí) ? 有序樹和無序樹： 如果一棵樹中結(jié)點(diǎn)的各子樹 從左到右 是有次序的，即若交換了某結(jié)點(diǎn)各子樹的相對(duì)位置，則構(gòu)成不同的樹，稱這棵樹為有序樹；反之，則稱為無序樹。 ? 森林： 零棵或有限棵 不相交 的樹的 集合稱為森林 計(jì)算機(jī)考前培訓(xùn) 二叉樹及其基本性質(zhì) ? 當(dāng)集合為空時(shí)，稱該二叉樹為 空 二叉樹 ? 二叉樹是 有序的 ,二叉樹具有 五種 基本形態(tài) ? 一棵深度為 k的二叉樹中，最多具有2k－ 1個(gè)結(jié)點(diǎn) 計(jì)算機(jī)考前培訓(xùn) 二叉樹及其基本性質(zhì) ? 對(duì)于一棵非空的二叉樹，如果葉子結(jié)點(diǎn)數(shù)為 n0，度數(shù)為 2的結(jié)點(diǎn)數(shù)為 n2，則有 : n0＝ n2＋ 1 ? 具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度 k為 [log2n]+1 計(jì)算機(jī)考前培訓(xùn) ? 二叉樹的遍歷： 是指按照某種順序訪問二叉樹中的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。 計(jì)算機(jī)考前培訓(xùn) ? 以 D、 L、 R分別表示訪問根結(jié)點(diǎn)、遍歷根結(jié)點(diǎn)的左子樹、遍歷根結(jié)點(diǎn)的右子樹 ? DLR（ 稱為 先 序遍歷） ? LDR（稱為 中 序遍歷） ? LRD（稱為 后 序遍歷） 計(jì)算機(jī)考前培訓(xùn) 例題 以下有關(guān)線性表敘述中，正確的是 ( )。 直接后繼 至少有一個(gè)元素 邏輯關(guān)系是固定不可改變的 0n個(gè)元素組成的有限序列 D 計(jì)算機(jī)考前培訓(xùn) 例題 在下列選項(xiàng)中， ( )不是算法具有的基本 特征。 C 計(jì)算機(jī)考前培訓(xùn) 例題 棧和隊(duì)列的共同點(diǎn)是 ( )。 C 計(jì)算機(jī)考前培訓(xùn) 例題 棧底至棧頂依次存放元素 A、 B、 C、 D，在第五個(gè)元素 E入棧前，棧中元素可 以出棧，則出棧序列可能是 ( )。 A. ABCED B. DBCEA C. CDABE D. DCBEA D 計(jì)算機(jī)考前培訓(xùn) 例題 在一個(gè)長(zhǎng)度為 n的順序存儲(chǔ)的線性表中， 向第 i個(gè)元素（ 1≤i≤n+1）前插入一個(gè) 新元素時(shí)，需要從后向前依次移動(dòng) ( )個(gè) 元素。 A. ni B. ni+1 C. ni1 D. i B 計(jì)算機(jī)考前培訓(xùn) 第七部分 數(shù)據(jù)庫 數(shù)據(jù)基本知識(shí) 數(shù)據(jù)模型 關(guān)系代數(shù) SQL 數(shù)據(jù)庫設(shè)計(jì)與管理 計(jì)算機(jī)考前培訓(xùn) 數(shù)據(jù)基本知識(shí) ? 數(shù)據(jù)庫（ Database, DB） ? 數(shù)據(jù)庫是以一定的組織形式存放在計(jì)算機(jī)存儲(chǔ)介質(zhì)上的相互關(guān)聯(lián)的 數(shù)據(jù)的集合 計(jì)算機(jī)考前培訓(xùn) 數(shù)據(jù)基本知識(shí) ? 數(shù)據(jù)庫管理系統(tǒng)（ Database Management System, DBMS） ? 數(shù)據(jù)庫管理系統(tǒng)是位于用戶和操作系統(tǒng)之間的一層數(shù)據(jù)管理軟件 計(jì)算機(jī)考前培訓(xùn) 數(shù)據(jù)基本知識(shí) 數(shù)據(jù)庫管理系統(tǒng)的主要功能： 1）數(shù)據(jù)定義功能 數(shù)據(jù)定義語言 DDL 2）數(shù)據(jù)操縱功能 數(shù)據(jù)操縱語言 DML 3）數(shù)據(jù)庫的運(yùn)行管理 4）數(shù)據(jù)庫的建立與維護(hù) 計(jì)算機(jī)考前培訓(xùn) 數(shù)據(jù)基本知識(shí) 4. 數(shù)據(jù)庫系統(tǒng) （ DataBase System, DBS） 是由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、應(yīng)用程 序、數(shù)據(jù)庫管理員和用戶構(gòu)成的人 —機(jī)系 統(tǒng)。其 核心