全國(guó)計(jì)算機(jī)二級(jí)輔導(dǎo)公共基礎(chǔ)部分.ppt

全國(guó)計(jì)算機(jī)二級(jí)考試 公共基礎(chǔ)知識(shí) 1 筆試 90分鐘 滿分100分 其中含公共基礎(chǔ)知識(shí)部分的30分 2 上機(jī)操作 90分鐘 滿分100分 上機(jī)操作包括 基本操作 簡(jiǎn)單應(yīng)用 綜合應(yīng)用 全國(guó)計(jì)算機(jī)二級(jí)考試形式 第一章數(shù)據(jù)結(jié)構(gòu)與算法 本章考試要點(diǎn) 算法的基本概念 算法復(fù)雜度的概念和意義 時(shí)間復(fù)雜度和空間復(fù)雜度 數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的圖形表示 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 線性表的定義 線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除 棧和隊(duì)列的定義 棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)有其基本運(yùn)算 線性單鏈表 雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算 樹(shù)的基本概念 二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)的前序 中序和后序遍歷 順序查找與二分法查找算法 基本排序算法 交換類排序 選擇類排序 插入類排序 本章考試要點(diǎn) 續(xù) 一 算法 算法 是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則算法的5個(gè)特性 可行性 確定性 有窮性 擁有足夠的情報(bào) 算法的基本要素 一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作 二是算法的控制結(jié)構(gòu)算法設(shè)計(jì)基本方法 列舉法 歸納法 遞推 遞歸 減半遞推 算法的復(fù)雜度 包括時(shí)間復(fù)雜度和空間復(fù)雜度時(shí)間復(fù)雜度 執(zhí)行算法所需的計(jì)算工作量空間復(fù)雜度 執(zhí)行算法所需的內(nèi)存空間 例 下列敘述中正確的是 A 一個(gè)算法的空間復(fù)雜度大 則其時(shí)間復(fù)雜度也必定大B 一個(gè)算法的空間復(fù)雜度大 則其時(shí)間復(fù)雜度必定小C 一個(gè)算法的時(shí)間復(fù)雜度大 則其空間復(fù)雜度必定小D 上述三種說(shuō)法都不對(duì) 答案 D 例 算法的時(shí)間復(fù)雜度是指 A 算法的執(zhí)行時(shí)間B 算法所處理的數(shù)據(jù)量C 算法程序中的語(yǔ)句或指令條數(shù)D 算法在執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù) 答案 D 例 算法的有窮性是指 A算法程序的運(yùn)行時(shí)間是有限的B算法程序所處理的數(shù)據(jù)量是有限的C算法程序的長(zhǎng)度是有限的D算法只能被有限的用戶使用 算法的基本特征 可行性 確定性 有窮性 擁有足夠的情報(bào) 算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止 即算法程序運(yùn)行的時(shí)間是有限的 答案 A 二 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) 相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合 如春 夏 秋 冬 18 11 35 23 16 父親 兒子 女兒等都是數(shù)據(jù)元素 前件 數(shù)據(jù)元素之間的關(guān)系 如父親是兒子和女兒的前件后件 如兒子是父親的后件結(jié)構(gòu) 指數(shù)據(jù)元素之間的前后件關(guān)系 數(shù)據(jù)的邏輯結(jié)構(gòu) 是指反映數(shù)據(jù)元素之間邏輯關(guān)系 而與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 物理結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式 數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間的位置關(guān)系可能與邏輯關(guān)系不同 例 下列敘述中正確的是 A 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)必定是一一對(duì)應(yīng)的B 由于計(jì)算機(jī)存儲(chǔ)空間是向量式的存儲(chǔ)結(jié)構(gòu) 因此 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一定是線性結(jié)構(gòu)C 程序設(shè)計(jì)語(yǔ)言中的數(shù)組一般是順序存儲(chǔ)結(jié)構(gòu) 因此 利用數(shù)組只能處理線性結(jié)構(gòu)D 以上三種說(shuō)法都不對(duì) 答案 D 數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示成多種存儲(chǔ)結(jié)構(gòu) 如 線性表就可用順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 三 線性表 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度 可將數(shù)據(jù)結(jié)構(gòu)分兩類 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 線性結(jié)構(gòu) 線性表 滿足下列兩個(gè)條件 1 有且只有一個(gè)根結(jié)點(diǎn) 2 每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件和后件 則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu) 否則為非線性結(jié)構(gòu) 線性表是最簡(jiǎn)單 最常用的一種數(shù)據(jù)結(jié)構(gòu) 其數(shù)據(jù)元素之間的相對(duì)位置是線性的 其存儲(chǔ)方式為順序存儲(chǔ)的 如數(shù)組 線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn) 線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的 線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的 基本操作 插入 刪除元素 在平均情況下 在線性表中插入 刪除一個(gè)元素 需要移動(dòng)表中一半的元素 例 如果一個(gè)線性表第1個(gè)元素的存儲(chǔ)地址是100 每個(gè)元素的長(zhǎng)度是2 則第5個(gè)元素的地址是 108 分析 數(shù)據(jù)元素的存儲(chǔ)地址取決于第1個(gè)元素的存儲(chǔ)地址 即 第i個(gè)元素的存儲(chǔ)地址 第1個(gè)元素的地址 i 1 每個(gè)元素的長(zhǎng)度 四 棧 棧 是限定在一端進(jìn)行插入與刪除的線性表 一端封閉 另一端開(kāi)口 在棧中 允許插入與刪除的一端稱為棧頂 而不允許插入與刪除的另一端稱為棧底 其操作原則是 先進(jìn)后出 棧的運(yùn)算有入棧 退棧 讀棧頂元素 在順序存儲(chǔ)結(jié)構(gòu)下 對(duì)這種類型線性表的插入與刪除運(yùn)算是不需要移動(dòng)表中其他數(shù)據(jù)元素的 例 下列關(guān)于棧的敘述正確的是 A 棧按 先進(jìn)先出 組織數(shù)據(jù)B 棧按 先進(jìn)后出 組織數(shù)據(jù)C 只能在棧底插入數(shù)據(jù)D 不能刪除數(shù)據(jù) 答案 B 例 一個(gè)棧的初始狀態(tài)為空 現(xiàn)將元素1 2 3 4 5 A B C D E依次入棧 然后再依次出棧 則元素出棧的順序是 A 12345ABCDEB EDCBA54321C ABCDE12345D 54321EDCBA 答案 B 例 一個(gè)棧的入棧序列是1 2 3 n 其出棧序列是P1 P2 P3 Pn 如果P1 n 那么Pi為 n i 1 分析 棧是先進(jìn)后出的線性表 當(dāng)P1 n 即n是最先出棧的 n必定是最后入棧的 那么 進(jìn)棧順序是 1 2 3 n 則出棧的順序是 n n 1 n 2 1 例 假設(shè)用一個(gè)長(zhǎng)度為50的數(shù)組 數(shù)組元素的下標(biāo)從0到49 作為棧的存儲(chǔ)空間 棧底指針bottom指向棧底元素 棧頂指針top指向棧頂元素 如果bottom 49 top 30 數(shù)組下標(biāo) 則棧中具有 個(gè)元素 答案 20 五 隊(duì)列 隊(duì)列 是指在一端進(jìn)行插入 稱為隊(duì)尾 而在另一端進(jìn)行刪除 稱為隊(duì)頭 的線性表 尾指針 rear 總是指向最后被插入的元素 排頭指針 front 指向排頭元素的前一個(gè)位置 其操作規(guī)則是 先進(jìn)先出 其運(yùn)算有入隊(duì)和退隊(duì) 循環(huán)隊(duì)列 就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置 形成邏輯上的環(huán)狀空間 供隊(duì)列循環(huán)使用 循環(huán)隊(duì)列主要有兩種基本運(yùn)算 1 入隊(duì)運(yùn)算 rear rear 1 2 退隊(duì)運(yùn)算 front front 1 例 線性表的存儲(chǔ)結(jié)構(gòu)主要分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 隊(duì)列是一種特殊的線性表 循環(huán)隊(duì)列是隊(duì)列的存儲(chǔ)結(jié)構(gòu) 答案 順序 例 下列對(duì)隊(duì)列的敘述正確的是A 隊(duì)列屬于非線性表B 隊(duì)列按 先進(jìn)后出 原則組織數(shù)據(jù)C 隊(duì)列在隊(duì)尾刪除數(shù)據(jù)D 隊(duì)列按 先進(jìn)先出 原則組織數(shù)據(jù) 答案 D 例 設(shè)某循環(huán)隊(duì)列的容量為50 頭指針front 5 指向隊(duì)頭元素的前一位置 尾指針rear 29 指向隊(duì)尾元素 則該循環(huán)隊(duì)列中共有個(gè)元素 考察數(shù)據(jù)結(jié)構(gòu)的循環(huán)隊(duì)列的知識(shí) 隊(duì)列元素?cái)?shù)為 rear front 29 5 24個(gè) 答案 24 在循環(huán)隊(duì)列中 若front rear 隊(duì)列中有n front rear個(gè)元素 其中n為循環(huán)隊(duì)列的容量 若front rear 隊(duì)列中有rear front個(gè)元素 若front rear 隊(duì)列中有n個(gè)或0個(gè)元素 例 設(shè)某循環(huán)隊(duì)列的容量為50 如果頭指針front 45 指向隊(duì)頭元素的前一位置 尾指針rear 10 指向隊(duì)尾元素 則該循環(huán)隊(duì)列中共有個(gè)元素 答案 15 例 下列敘述中正確的是 A 循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針 因此 循環(huán)隊(duì)列是非線性結(jié)構(gòu)B 在循環(huán)隊(duì)列中 只需要隊(duì)頭指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況C 在循環(huán)隊(duì)列中 只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況D 循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定 答案 D 七 線性鏈表 線性鏈表的基本概念在線性鏈表中 各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來(lái)指示的 指向線性表中第一個(gè)結(jié)點(diǎn)的指針HEAD稱為頭指針 當(dāng)HEAD NULL 或0 時(shí)稱為空表 線性鏈表的運(yùn)算主要有 線性鏈表的插入 刪除 查找 合并 分解 逆轉(zhuǎn) 復(fù)制 排序等 在線性鏈表中查找指定元素在非空線性鏈表中尋找包括指定元素x的前一個(gè)結(jié)點(diǎn)p的基本方法如下 從頭指針指向的結(jié)點(diǎn)開(kāi)始往后沿指針進(jìn)行掃描 直到后面已沒(méi)有結(jié)點(diǎn)或下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤為止 當(dāng)線性鏈表中不存在包含元素x的結(jié)點(diǎn)時(shí) 則找到的p為線性鏈表中的最后一個(gè)節(jié)點(diǎn)號(hào) 線性鏈表的插入為了在線性鏈表中插入一個(gè)新元素 首先要給該元素分配一個(gè)新節(jié)點(diǎn) 它可以從可利用棧中取得 然后將存放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的位置 線性鏈表的刪除為了在線性鏈表中刪除包含指定元素的結(jié)點(diǎn) 首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn) 然后將要?jiǎng)h除結(jié)點(diǎn)放回到可利用棧 例 下列關(guān)于線性鏈表的敘述中 正確的是 A 各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù) 但它們的存儲(chǔ)順序與邏輯順序必須一致B 各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致 但它們的存儲(chǔ)空間必須連續(xù)C 進(jìn)行插入與刪除時(shí) 不需要移動(dòng)表中的元素D 以上三種說(shuō)法都不對(duì) 答案 C 八 樹(shù) 樹(shù) 是一種簡(jiǎn)單的非線性結(jié)構(gòu) 是層次結(jié)構(gòu) 樹(shù)結(jié)構(gòu)中 每一個(gè)結(jié)點(diǎn)只有一個(gè)前件 稱為父結(jié)點(diǎn) 沒(méi)有前件的結(jié)點(diǎn)只有一個(gè) 稱為樹(shù)的根結(jié)點(diǎn) 在樹(shù)結(jié)構(gòu)中 每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件 它們稱為該結(jié)點(diǎn)的子結(jié)點(diǎn) 沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn) 一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度 所有結(jié)點(diǎn)中最大的度稱為樹(shù)的度 樹(shù)的最大層次稱為樹(shù)的深度 1 二叉樹(shù)的定義 二叉樹(shù)具有以下兩個(gè)特點(diǎn) 非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn) 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù) 且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù) 用于存儲(chǔ)二叉樹(shù)的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè) 一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址 稱為左指針域 另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址 稱為右指針域 2 二叉樹(shù)的基本性質(zhì) 二叉樹(shù)具有以下幾個(gè)性質(zhì) 性質(zhì)1 在二叉樹(shù)的第k層上 最多有2k 1 k 1 個(gè)結(jié)點(diǎn) 性質(zhì)2 深度為m的二叉樹(shù)最多有2m 1個(gè)結(jié)點(diǎn) 性質(zhì)3 在任意一棵二叉樹(shù)中 度為0的結(jié)點(diǎn) 即葉子結(jié)點(diǎn) 總是比度為2的結(jié)點(diǎn)多一個(gè) 如果葉子結(jié)點(diǎn)n0 度為2的結(jié)點(diǎn)數(shù)為n2 則n0 n2 1 性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù) 其深度至少為 log2n 1 其中 log2n 表示取log2n的整數(shù)部分 3 滿二叉樹(shù)和完全二叉樹(shù) 滿二叉樹(shù) 除最后一層無(wú)任何子節(jié)點(diǎn)外 每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn) 節(jié)點(diǎn)數(shù)達(dá)到最大值 完全二叉樹(shù) 除最后一層外 其它各層的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù) 最后一層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n 1 設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn) 如果從根結(jié)點(diǎn)開(kāi)始 從上到下 從左到右用自然數(shù)1 2 3 n給結(jié)點(diǎn)進(jìn)行編號(hào) 則對(duì)于編號(hào)為k的結(jié)點(diǎn)有以下結(jié)論 若k 1 則該結(jié)點(diǎn)為根結(jié)點(diǎn) 它無(wú)父結(jié)點(diǎn) 若k 1 則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT k 2 若2k n 則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k 否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn) 顯然也無(wú)右子結(jié)點(diǎn) 若2k 1 n 則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k 1 否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn) 完全二叉樹(shù)的兩個(gè)性質(zhì) 4 二叉樹(shù)的遍歷 二叉樹(shù)的遍歷是指不重復(fù)地訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn) 前序遍歷 根節(jié)點(diǎn) 遍歷左子樹(shù) 遍歷右子樹(shù) 中序遍歷 遍歷左子樹(shù) 根節(jié)點(diǎn) 遍歷右子樹(shù) 后序遍歷 遍歷左子樹(shù) 遍歷右子樹(shù) 根節(jié)點(diǎn) 例 對(duì)下列二叉樹(shù)進(jìn)行前序遍歷的結(jié)果為 A DYBEAFCZXB DEBFZXCAC ABDYECFXZD ABCDEFXYZ 答案 C 例 對(duì)下列二叉樹(shù)進(jìn)行中序遍歷的結(jié)果 答案 DBXEAYFZC 例 設(shè)一棵二叉樹(shù)的前序遍歷結(jié)果為A B D E C F 中序遍歷結(jié)果為D B E A F C 則其后序遍歷的結(jié)果為 D E B F C A 例 設(shè)一棵二叉樹(shù)的中序遍歷為CDBAFEHG 后序遍歷為DCBFHGEA 則其前序遍歷的結(jié)果為 ABCDEFGH 例 設(shè)一棵二叉樹(shù)的前序遍歷結(jié)果為A B D H E C F I J G 中序遍歷結(jié)果為D H B E A I F J C G 則其后序遍歷的結(jié)果為 H D E B I J F G C A 例 深度為5的滿二叉樹(shù)有 個(gè)葉子結(jié)點(diǎn) 根據(jù)二叉樹(shù)的性質(zhì) 二叉樹(shù)第i i 1 層上至多有2i 1個(gè)結(jié)點(diǎn) 得到第5層的節(jié)點(diǎn)數(shù)最多是16 答案 16 例 某二叉樹(shù)有n個(gè)度為2的結(jié)點(diǎn) 則該二叉樹(shù)的葉子結(jié)點(diǎn)為個(gè) A n 1B n 1C 2nD n 2 據(jù)二叉樹(shù)性質(zhì)3 在任意一棵二叉樹(shù)中 度為0的節(jié)點(diǎn) 即葉子節(jié)點(diǎn) 總比度為2的節(jié)點(diǎn)多一個(gè) 即n0 n2 1 答案 A 例 一棵二叉樹(shù)有10個(gè)度為1的結(jié)點(diǎn) 7個(gè)度為2的結(jié)點(diǎn) 則該二叉樹(shù)共有個(gè)結(jié)點(diǎn) 答案 25 例 某二叉樹(shù)共有7個(gè)結(jié)點(diǎn) 其中葉子結(jié)點(diǎn)只有1個(gè) 則該二叉樹(shù)的深度為 假設(shè)根結(jié)點(diǎn)在第1層 A 3B 4C 6D 7 答案 D 例 在深度為7的滿二叉樹(shù)中 度為2的結(jié)點(diǎn)個(gè)數(shù)為 答案 63 分析 根據(jù)二叉樹(shù)性質(zhì)1 該深度為7的滿二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)為2 7 1 個(gè) 根據(jù)二叉樹(shù)性質(zhì)2 該深度為7的滿二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為27 1個(gè) 故深度為2的結(jié)點(diǎn)個(gè)數(shù)為 n2 27 1 2 7 1 63 分析 根據(jù)二叉樹(shù)性質(zhì)1 滿二叉第7層的葉子結(jié)點(diǎn)數(shù)為27 1個(gè) 即64個(gè) 根據(jù)二叉樹(shù)的葉子結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)數(shù)多1個(gè)的結(jié)論 故度為2的結(jié)點(diǎn)個(gè)數(shù)為 64 1 63 例 一棵二叉樹(shù)共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn) 則該二叉樹(shù)中的總結(jié)點(diǎn)數(shù)為 A 219B 221C 229D 231 二叉樹(shù)性質(zhì)3 度為0的結(jié)點(diǎn)比度為2的結(jié)點(diǎn)多一個(gè) 故總結(jié)點(diǎn)數(shù)為 M n0 n1 n2 n0 n1 n0 1 2n0 n1 1 2 70 80 1 219 答案 A 例 設(shè)樹(shù)T的度為4 其中度為1 2 3 4的結(jié)點(diǎn)個(gè)數(shù)分別為 4 2 1 1 則這棵樹(shù)中的葉子結(jié)點(diǎn)有 8 分析 1 此樹(shù)的結(jié)點(diǎn)數(shù) 含根結(jié)點(diǎn)和葉子結(jié)點(diǎn) 共計(jì) 1 4 2 2 3 1 4 1 1 16 2 此樹(shù)的子樹(shù)共計(jì) 4 2 1 1 8 3 因此該樹(shù)的葉子結(jié)點(diǎn)為 16 8 8 例 設(shè)一棵完全二叉樹(shù)共有700個(gè)結(jié)點(diǎn) 則在該二叉樹(shù)中有 葉子結(jié)點(diǎn) 350 分析 根據(jù)完全二叉樹(shù)的性質(zhì)6 P36 可知 1 編號(hào)700的葉子結(jié)點(diǎn) 即最后一個(gè)葉子結(jié)點(diǎn) 其父結(jié)點(diǎn)編號(hào)為 INT 700 2 350 2 編號(hào)為350的結(jié)點(diǎn)為最后一個(gè)樹(shù)結(jié)點(diǎn) 即 編號(hào)1至350均為父結(jié)點(diǎn) 計(jì)350個(gè) 編號(hào)351至700均為葉子結(jié)點(diǎn) 3 所以葉子結(jié)點(diǎn)的個(gè)數(shù)為 700 350 350 九 查找技術(shù) 一 順序查找順序查找一般指在線性表中查找指定的元素 在平均情況下 利用順序查找法在線性表中查找一個(gè)元素 大約要與線性表中的一半元素進(jìn)行比較 最大查找次數(shù)為n次 二 二分法查找二分法查找只適用于順序查找的有序表 有序表 元素按值非遞減排列的線性表 對(duì)于長(zhǎng)度為n的有序線性表 在最壞情況下 二分查找只需要比較log2n次 而順序查找需要比較n次 例 有序線性表能進(jìn)行二分查找的前提是該線性表必須是存儲(chǔ)的 答案 升序 例 在長(zhǎng)度為64的有序線性表中進(jìn)行順序查找 最壞情況下需要比較的次數(shù)為 A 63B 64C 6D 7 答案 B 例 在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找 最壞情況下需要比較的次數(shù)是 A O n B O n2 C O log2n D O nlog2n 二分查找的效率要比順序查找高得多 對(duì)于長(zhǎng)度為n的有序線性表 在最壞情況下 二分查找只需要比較log2n次 而順序查找需要比較n次 答案 C 十 排序技術(shù) 一 交換類排序交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法 1 冒泡排序法冒泡排序需要經(jīng)過(guò)n 2遍的從前往后的掃描和n 2遍的從后往前的掃描 需要的比較次數(shù)為n n 1 2 2 快速排序法快速排序過(guò)程中 隨著對(duì)各子表不斷地進(jìn)行分割 劃分出的子表會(huì)越來(lái)越多 但一次又只能對(duì)一個(gè)子表進(jìn)行再分割處理 需要將暫時(shí)不分割的子表記憶起來(lái) 這就要用一個(gè)棧來(lái)實(shí)現(xiàn) 1 簡(jiǎn)單插入排序?qū)o(wú)序序列中的各個(gè)數(shù)據(jù)元素依次插入到已經(jīng)有序的線性表中 長(zhǎng)度為n的線性表 在最壞的情況下 簡(jiǎn)單插入排序需要經(jīng)過(guò)n n 1 2次的比較 2 希爾排序法將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序 長(zhǎng)度為n的線性表 在最壞的情況下 希爾排序所需要的比較次數(shù)為 O n1 5 二 插入類排序 三 選擇類排序 1 簡(jiǎn)單選擇排序掃描整個(gè)線性表 從選出最小的元素 將它交換到最前面 對(duì)剩下的子表采用同樣的方法 直到子表為空 長(zhǎng)度為n的序列 在最壞的情況下 簡(jiǎn)單選擇排序法需要經(jīng)過(guò)n n 1 2次的比較 2 堆排序法長(zhǎng)度為n的序列 在最壞的情況下 堆排序的比較次數(shù)為O nlog2n 假設(shè)線性表的長(zhǎng)度為n 則 冒泡排序和簡(jiǎn)單插入排序的比較次數(shù) 時(shí)間復(fù)雜度 為n n 1 2 希爾排序的比較次數(shù)為O n1 5 簡(jiǎn)單選擇排序的比較次數(shù)為n n 1 2 堆排序的比較次數(shù)為O nlog2n 例 冒泡排序在最壞的情況下的比較次數(shù)是 A n n 1 2B nlog2nC n n 1 2D n 2 答案 C 例 對(duì)長(zhǎng)度為n的線性表排序 在最壞情況下 比較次數(shù)不是n n 1 2的排序方法是 A快速排序B冒泡排序C直接插入排序D堆排序 答案 D 例 按 先進(jìn)后出 原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 答案 棧 例 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu) 帶鏈的隊(duì)列屬于 答案 線性結(jié)構(gòu) 第二章程序設(shè)計(jì)基礎(chǔ) 本章考試要點(diǎn) 程序設(shè)計(jì)方法與風(fēng)格 結(jié)構(gòu)化程序設(shè)計(jì) 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法 掌握并理解對(duì)象 方法 屬性 以及繼承與多態(tài)性的概念 程序設(shè)計(jì)風(fēng)格是指編寫(xiě)程序時(shí)所表現(xiàn)出的特點(diǎn) 習(xí)慣和邏輯思路 當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格是著名的 清晰第一 效率第二 一 程序設(shè)計(jì)方法與風(fēng)格 要形成良好的程序設(shè)計(jì)風(fēng)格 應(yīng)注重和考慮這些因素 源程序文檔化 數(shù)據(jù)說(shuō)明的方法 語(yǔ)句的結(jié)構(gòu) 輸入和輸出 1 結(jié)構(gòu)化程序設(shè)計(jì)的原則結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為 自頂向下 逐步求精 模塊化 限制使用goto語(yǔ)句 二 結(jié)構(gòu)化程序設(shè)計(jì) 2 結(jié)構(gòu)化程序設(shè)計(jì)的三種基本結(jié)構(gòu)分別是 順序結(jié)構(gòu) 選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu) 使用程序設(shè)計(jì)語(yǔ)言中的順序 選擇 循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯 選用的控制結(jié)構(gòu)只準(zhǔn)許一個(gè)入口和一個(gè)出口 程序語(yǔ)句組成容易識(shí)別的塊 每塊只有一個(gè)入口和一個(gè)出口 復(fù)雜結(jié)構(gòu)應(yīng)該用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來(lái)實(shí)現(xiàn) 語(yǔ)言中所沒(méi)有的控制結(jié)構(gòu) 應(yīng)該采用前后一致的方法來(lái)模擬 嚴(yán)格控制goto語(yǔ)句的使用 注意 面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn) 與人類習(xí)慣的思維方法一致 穩(wěn)定性好 可重用性好 易于開(kāi)發(fā)大型軟件產(chǎn)品 可維護(hù)性好 三 面向?qū)ο蟮某绦蛟O(shè)計(jì) 2 面向?qū)ο蠓椒ǖ幕靖拍?1 對(duì)象面向?qū)ο蟪绦蛟O(shè)計(jì)中的最基本的概念 用來(lái)表示客觀世界中的任何實(shí)體 它既可以是具體的物理實(shí)體 也可以是一個(gè)抽象的概念 對(duì)象具有 標(biāo)識(shí)惟一性 分類性 多態(tài)性 封裝性和模塊獨(dú)立性 2 屬性對(duì)象所包含的信息 一般只能通過(guò)執(zhí)行對(duì)象的操作來(lái)改變 3 操作 方法 描述了對(duì)象的執(zhí)行功能 若通過(guò)信息傳遞 還可以為其它對(duì)象使用 操作過(guò)程對(duì)外是封閉的 用戶只能看到這一操作實(shí)施后的結(jié)果 4 類和實(shí)例類是具有共同屬性 共同方法的對(duì)象的集合 類的對(duì)象的抽象 它描述了屬于該對(duì)象類型的所有對(duì)象的性質(zhì) 而一個(gè)對(duì)象則是其對(duì)應(yīng)類的一個(gè)實(shí)例 5 消息 事件 面向?qū)ο蟮氖澜缡峭ㄟ^(guò)對(duì)象與對(duì)象間彼此的相互合作來(lái)推動(dòng)的 對(duì)象間的這種相互合作需要一個(gè)機(jī)制協(xié)助進(jìn)行 這樣的機(jī)制稱為 消息 6 繼承繼承是使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù) 已有的類可當(dāng)做基類來(lái)引用 則新類相應(yīng)地可當(dāng)做派生類來(lái)引用 繼承是指能夠直接獲得已有的性質(zhì)和特征 而不必重復(fù)定義它們 7 多態(tài)性對(duì)象根據(jù)所接受的消息而做出的動(dòng)作 同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng) 該現(xiàn)象稱為多態(tài)性 多態(tài)性是指子類對(duì)象可以像父類對(duì)象那樣使用 同樣的消息既可以發(fā)送給父類對(duì)象 也可以發(fā)送給子類對(duì)象 多態(tài)性機(jī)制增加了面向?qū)ο筌浖到y(tǒng)的靈活性 進(jìn)一步減少了信息冗余 面向?qū)ο蟪绦蛟O(shè)計(jì)中 對(duì)象具有以下特征 繼承性 抽象性 封裝性 多態(tài)性 例 下列選項(xiàng)中不符合良好程序設(shè)計(jì)風(fēng)格的是 A 源程序要文檔化B 數(shù)據(jù)說(shuō)明的次序要規(guī)范化C 避免濫用goto語(yǔ)句D 模塊設(shè)計(jì)要保證高耦合 高內(nèi)聚 模塊設(shè)計(jì)要保證低耦合 高內(nèi)聚 答案 D 例 在結(jié)構(gòu)化程序設(shè)計(jì)中 模塊劃分的原則是 A 各模塊應(yīng)包括盡量多的功能B 各模塊的規(guī)模應(yīng)盡量大C 各模塊之間的聯(lián)系應(yīng)盡量緊密D 模塊內(nèi)有高內(nèi)聚度 模塊間有低耦合度 答案 D 例 下面選項(xiàng)中不屬于面向?qū)ο蟪绦蛟O(shè)計(jì)的是 A 繼承性B 多態(tài)性C 類比性D 封裝性 面向?qū)ο蟪绦蛟O(shè)計(jì)的特征包括 分類性 多態(tài)性 封裝性 繼承性等 答案 C 例 在面向?qū)ο蠓椒ㄖ?實(shí)現(xiàn)信息隱蔽是依靠 A 對(duì)象的繼承B 對(duì)象的多態(tài)C 對(duì)象的封裝D 對(duì)象的分類 對(duì)象的封裝性 即從外面只能看到對(duì)象的外部特征 而對(duì)象的內(nèi)部狀態(tài)對(duì)外是不可見(jiàn)的 因此對(duì)象的信息隱蔽是依靠對(duì)象的封裝來(lái)實(shí)現(xiàn)的 答案 C 例 下列敘述中 不符合良好程序設(shè)計(jì)風(fēng)格要求的是 A 程序的效率第一 清晰第二B 程序的可讀性好C 程序中要有必要的注釋D 輸入數(shù)據(jù)前要有提示信息 軟件在編碼階段 力求程序語(yǔ)句簡(jiǎn)單 直接 不能只為了追求效率而使語(yǔ)句復(fù)雜化 除非對(duì)效率有特殊的要求 程序編寫(xiě)要做到清晰第一 效率第二 答案 A 例 在面向?qū)ο蠓椒ㄖ?不屬于 對(duì)象 基本特點(diǎn)的是 A 一致性B 分類性C 多態(tài)性D 標(biāo)識(shí)唯一性 對(duì)象的基本特點(diǎn) 標(biāo)識(shí)唯一性 分類性 多態(tài)性 封裝性 模塊獨(dú)立性好 答案 A 例 下列敘述中正確的是 A 程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)B 程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)C 程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量D 以上三種說(shuō)法都不對(duì) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu) 而采用不同的存儲(chǔ)結(jié)構(gòu) 其數(shù)據(jù)處理的效率是不同的 因此 在進(jìn)行數(shù)據(jù)處理時(shí) 選擇合適的存儲(chǔ)結(jié)構(gòu)是很重要的 答案 A 例 符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是 選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu)和 答案 順序結(jié)構(gòu) 例 下列選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)原則的是 A 可封裝B 自頂向下C 模塊化D 逐步求精 結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為自頂向下 逐步求精 模塊化 限制使用goto語(yǔ)句等 答案 A 第三章軟件工程基礎(chǔ) 本章考試要點(diǎn) 軟件工程基本概念 軟件生命周期概念 軟件工具與軟件開(kāi)發(fā)環(huán)境 結(jié)構(gòu)化分析方法 數(shù)據(jù)流圖 數(shù)據(jù)字典 軟件需求規(guī)格說(shuō)明書(shū)的概念 結(jié)構(gòu)化設(shè)計(jì)方法 總體設(shè)計(jì)與詳細(xì)設(shè)計(jì) 軟件測(cè)試方法 白盒測(cè)試與黑盒測(cè)試 測(cè)試用例設(shè)計(jì) 軟件測(cè)試的實(shí)施 單元測(cè)試 集成測(cè)試和測(cè)試系統(tǒng) 程序調(diào)試 靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試 一 軟件工程基本概念 1 軟件定義 1 軟件的定義 軟件是與計(jì)算機(jī)操作相關(guān)的計(jì)算機(jī)程序 規(guī)程 規(guī)則 以及可能有的文件 文檔及數(shù)據(jù) 軟件的三個(gè)要素 程序 數(shù)據(jù) 文檔 2 軟件分類 軟件按功能可分為三大類 應(yīng)用軟件 系統(tǒng)軟件 支撐軟件 或工具軟件 3 軟件危機(jī)的定義 軟件危機(jī)是泛指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問(wèn)題 1 軟件工程的定義 軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義 開(kāi)發(fā)和維護(hù)的一整套方法 工具 文檔 實(shí)踐標(biāo)準(zhǔn)和工序 軟件工程的三個(gè)要素 方法 工具和過(guò)程 2 軟件工程定義與軟件生命周期 2 軟件生命周期就是軟件產(chǎn)品從提出 實(shí)現(xiàn) 使用維護(hù)到停止使用退役的全過(guò)程 軟件定義階段的任務(wù)包括可行性研究與計(jì)劃制定 需求分析 軟件開(kāi)發(fā)階段的任務(wù)包括概要設(shè)計(jì) 詳細(xì)設(shè)計(jì) 軟件實(shí)現(xiàn) 軟件測(cè)試 軟件維護(hù)階段的任務(wù)包括軟件的運(yùn)行 維護(hù)和退役 1 軟件開(kāi)發(fā)工具軟件開(kāi)發(fā)工具的發(fā)展是從單項(xiàng)工具的開(kāi)發(fā)逐步向集成工具發(fā)展的 軟件開(kāi)發(fā)工具為軟件工程方法提供了自動(dòng)的或半自動(dòng)的軟件支撐環(huán)境 3 軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境 2 軟件開(kāi)發(fā)環(huán)境軟件開(kāi)發(fā)環(huán)境或稱軟件工程環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合 這些軟件工具按照一定的方法或模式組合起來(lái) 支持軟件生命周期內(nèi)的各個(gè)階段和各項(xiàng)任務(wù)的完成 1 需求分析與需求分析方法需求分析的定義需求分析階段的工作需求分析方法 結(jié)構(gòu)化分析方法 面向?qū)ο蟮姆治龇椒?二 結(jié)構(gòu)化分析方法 2 關(guān)于結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的運(yùn)用 結(jié)構(gòu)化分析的常用工具有 數(shù)據(jù)流圖 DFD 記住DFD圖的幾個(gè)符號(hào) 數(shù)據(jù)字典 DD 判定樹(shù)和判定表 其中最重要的工具是數(shù)據(jù)流圖 數(shù)據(jù)流圖是通過(guò)對(duì)需求的理解構(gòu)造出邏輯模型的圖形表示 它直接支持系統(tǒng)的功能建模 數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心 數(shù)據(jù)字典是對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表 以及精確的 嚴(yán)格的定義 使得用戶和系統(tǒng)分析員對(duì)輸入 輸出 存儲(chǔ)成分和中間計(jì)算結(jié)果用共同的理解 3 結(jié)構(gòu)化分析的常用工具 軟件需求規(guī)格說(shuō)明書(shū) SRS 是需求分析階段的最后結(jié)果 是軟件開(kāi)發(fā)中的重要文檔之一 作用 內(nèi)容 特點(diǎn) 4 軟件需求規(guī)格說(shuō)明書(shū) 軟件設(shè)計(jì)的基本概念 軟件設(shè)計(jì)是軟件工程的重要階段 是一個(gè)把軟件需求轉(zhuǎn)換為軟件表示的過(guò)程 軟件設(shè)計(jì)的基礎(chǔ)目標(biāo)是用比較抽象概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù) 即軟件設(shè)計(jì)是確定系統(tǒng)的物理模型 三 結(jié)構(gòu)化設(shè)計(jì)方法 從技術(shù)觀點(diǎn)看 軟件設(shè)計(jì)包括結(jié)構(gòu)設(shè)計(jì) 數(shù)據(jù)設(shè)計(jì) 接口設(shè)計(jì)和過(guò)程設(shè)計(jì) 結(jié)構(gòu)設(shè)計(jì)是定義軟件系統(tǒng)各主要部件之間的關(guān)系 數(shù)據(jù)設(shè)計(jì)是將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義 接口設(shè)計(jì)是描述軟件內(nèi)部 軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信 過(guò)程設(shè)計(jì)是把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程性描述 軟件設(shè)計(jì)的內(nèi)容 結(jié)構(gòu)化設(shè)計(jì)方法的基本思想 將軟件設(shè)計(jì)成相對(duì)獨(dú)立 單一功能的模塊組成的結(jié)構(gòu) 為了提高模塊的獨(dú)立性 應(yīng)該盡量提高模塊的內(nèi)聚性 降低模塊間的耦合性 概要設(shè)計(jì)的基本任務(wù) 設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu) 確定數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì) 編寫(xiě)概要設(shè)計(jì)文檔 進(jìn)行概要設(shè)計(jì)文檔評(píng)審 軟件結(jié)構(gòu)設(shè)計(jì)工具 結(jié)構(gòu)圖 SC 也稱為程序結(jié)構(gòu)圖 結(jié)構(gòu)圖是描述軟件結(jié)構(gòu)的圖形工具 1 概要設(shè)計(jì) a 提高模塊獨(dú)立性 b 模塊規(guī)模適中 c 深度 寬度 扇出和扇入適當(dāng) d 使模塊的作用域在該模塊的控制域內(nèi) e 應(yīng)減少模塊的接口和界面的復(fù)雜性 f 設(shè)計(jì)成單入口 單出口的模塊 g 設(shè)計(jì)功能可預(yù)測(cè)的模塊 軟件設(shè)計(jì)的準(zhǔn)則 詳細(xì)設(shè)計(jì)的任務(wù) 為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法的局部數(shù)據(jù)結(jié)構(gòu) 用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié) 過(guò)程設(shè)計(jì)的任務(wù) 對(duì)每個(gè)模塊規(guī)定的功能以及算法的設(shè)計(jì) 給出適當(dāng)?shù)乃惴枋?2 詳細(xì)設(shè)計(jì) 常見(jiàn)的過(guò)程設(shè)計(jì)工具有 a 程序流程圖 N S 方框圖 PAD 問(wèn)題分析圖 b 表格工具 判定表 c 語(yǔ)言工具 PDL 過(guò)程設(shè)計(jì)語(yǔ)言 程序流程圖 N S圖 軟件測(cè)試是保證軟件質(zhì)量的重要手段 其主要過(guò)程涵蓋了整個(gè)軟件生命期的過(guò)程 包括需求定義階段的需求測(cè)試 編碼階段的單元測(cè)試 繼承測(cè)試以及后期的確認(rèn)測(cè)試 系統(tǒng)測(cè)試 驗(yàn)證軟件是否合格 能否交付用戶使用等 1 軟件測(cè)試 四 軟件測(cè)試及程序的調(diào)試 軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程 一個(gè)好的測(cè)試用例是指很可能找到迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤的用例 一個(gè)成功的測(cè)試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試 1 軟件測(cè)試的目的 軟件測(cè)試過(guò)程中應(yīng)遵循以下準(zhǔn)則 所有測(cè)試都有追溯到需求 嚴(yán)格執(zhí)行測(cè)試計(jì)劃 派出測(cè)試的隨意性 充分注意測(cè)試中的群集現(xiàn)象 程序員應(yīng)避免監(jiān)察自己的程序 窮舉測(cè)試不可能 妥善保存測(cè)試計(jì)劃 測(cè)試用例 出錯(cuò)統(tǒng)計(jì)和最終分析報(bào)告 2 軟件測(cè)試的準(zhǔn)則 軟件測(cè)試從是否要執(zhí)行被測(cè)試軟件的角度可以分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試 軟件測(cè)試按照功能劃分可分為白盒測(cè)試和黑盒測(cè)試方法 3 軟件測(cè)試技術(shù)與方法綜述 白盒測(cè)試又稱結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試 是根據(jù)軟件產(chǎn)品的內(nèi)部工作過(guò)程 檢測(cè)內(nèi)部成分 以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)范要求 白盒測(cè)試 a 保證所測(cè)模塊中每一獨(dú)立路徑至少執(zhí)行一次 b 保證所測(cè)模塊所有判斷的每一分支至少執(zhí)行一次 c 保證所測(cè)模塊每一循環(huán)都在邊界條件和一般條件下至少各執(zhí)行一次 d 驗(yàn)證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性 白盒測(cè)試的基本原則 a 邏輯覆蓋測(cè)試方法 邏輯覆蓋是泛指一系列以程序內(nèi)部的邏輯結(jié)構(gòu)為基礎(chǔ)的測(cè)試用例設(shè)計(jì)技術(shù) 邏輯覆蓋測(cè)試方法有語(yǔ)句覆蓋 路徑覆蓋 判定覆蓋 條件覆蓋以及判斷 條件覆蓋 b 基本路徑測(cè)試 基本路徑測(cè)試的思想和步驟是 根據(jù)軟件過(guò)程性描述中的控制流程確定程序的環(huán)路復(fù)雜性度量 用此度量定義基本路徑集合 并由此導(dǎo)出一組測(cè)試用例對(duì)每一條獨(dú)立執(zhí)行路徑進(jìn)行測(cè)試 白盒測(cè)試的主要方法 黑盒測(cè)試也稱功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試 是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿足需要進(jìn)行測(cè)試和驗(yàn)證 黑盒測(cè)試 a 等價(jià)類劃分法 將程序的所有可能的輸入數(shù)據(jù)劃分成若干部分 及若干等價(jià)類 然后從每個(gè)等價(jià)類中選取數(shù)據(jù)作為測(cè)試用例 b 邊界值分析法 邊界值分析法是對(duì)各種輸入 輸出范圍的邊界情況設(shè)計(jì)測(cè)試用例的方法 c 錯(cuò)誤推測(cè)法 靠經(jīng)驗(yàn)和直覺(jué)推測(cè)程序中可能存在的各種錯(cuò)誤 從而有針對(duì)性地編寫(xiě)檢查這些錯(cuò)誤的例子的方法 黑盒測(cè)試的方法 軟件測(cè)試過(guò)程一般按4個(gè)步驟進(jìn)行 即 單元測(cè)試 集成測(cè)試 驗(yàn)收測(cè)試 確認(rèn)測(cè)試 系統(tǒng)測(cè)試 4 軟件測(cè)試的實(shí)施 程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤 它與軟件測(cè)試不同 軟件測(cè)試是盡可能多地發(fā)現(xiàn)軟件中的錯(cuò)誤 軟件測(cè)試貫穿整個(gè)軟件生命期 調(diào)試主要在開(kāi)發(fā)階段 2 程序的調(diào)試 程序調(diào)試的基本步驟 第1步 錯(cuò)誤定位 第2步 修改設(shè)計(jì)和代碼 以排除錯(cuò)誤 第3步 進(jìn)行回歸測(cè)試 防止引進(jìn)新的錯(cuò)誤 主要的軟件調(diào)試方法有 強(qiáng)行排錯(cuò)法 回溯法 原因排除法 強(qiáng)行排錯(cuò)法是傳統(tǒng)的調(diào)試方法 回溯法適合于小規(guī)模的排錯(cuò) 原因排除法是通過(guò)演繹和回歸 以及二分法來(lái)實(shí)現(xiàn)的 軟件調(diào)試方法 例 從工程管理角度 軟件設(shè)計(jì)一般分為兩步完成 它們是 A 概要設(shè)計(jì)與詳細(xì)設(shè)計(jì)B 數(shù)據(jù)設(shè)計(jì)與接口設(shè)計(jì)C 軟件結(jié)構(gòu)設(shè)計(jì)與數(shù)據(jù)設(shè)計(jì)D 過(guò)程設(shè)計(jì)與數(shù)據(jù)設(shè)計(jì) 從技術(shù)觀點(diǎn)來(lái)看 軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì) 數(shù)據(jù)設(shè)計(jì) 接口設(shè)計(jì) 過(guò)程設(shè)計(jì) 從工程管理角度 軟件設(shè)計(jì)分為兩步完成 概要設(shè)計(jì)和詳細(xì)設(shè)計(jì) 答案 A 例 下列選項(xiàng)中不屬于軟件生命周期開(kāi)發(fā)階段任務(wù)的是 A 軟件測(cè)試B 概要設(shè)計(jì)C 軟件維護(hù)D 詳細(xì)設(shè)計(jì) 答案 C 例 的任務(wù)是診斷和改正程序中的錯(cuò)誤 答案 軟件調(diào)試 例 下列敘述中正確的是 A 軟件測(cè)試的主要目的是發(fā)現(xiàn)程序中的錯(cuò)誤B 軟件測(cè)試的主要目的是確定程序中錯(cuò)誤的位置C 為了提高軟件測(cè)試的效率 最好由程序編制者自己來(lái)完成軟件測(cè)試的工作D 軟件測(cè)試是證明軟件沒(méi)有錯(cuò)誤 軟件測(cè)試的主要目的是為了發(fā)現(xiàn)軟件中還沒(méi)有被發(fā)現(xiàn)的錯(cuò)誤 軟件調(diào)試的目的是定位及改正軟件中的錯(cuò)誤 答案 A 例 軟件測(cè)試分為白箱 盒 測(cè)試和黑箱 盒 測(cè)試 等階類劃分法屬于測(cè)試 黑箱測(cè)試的方法有等價(jià)類劃分法 錯(cuò)誤推測(cè)法 邊界值分析法等 白箱測(cè)試的方法有基本路徑測(cè)試 邏輯覆蓋等 答案 黑箱 盒 測(cè)試 例 軟件生命周期可分為多個(gè)階段 一般分為定義階段 開(kāi)發(fā)階段和維護(hù)階段 編碼和測(cè)試屬于階段 軟件開(kāi)發(fā)階段可分為 概要設(shè)計(jì) 詳細(xì)設(shè)計(jì) 軟件測(cè)試 而編碼屬于詳細(xì)設(shè)計(jì)階段的主要任務(wù) 答案 開(kāi)發(fā)階段 例 軟件是指 A 程序B 程序和文檔C 算法加數(shù)據(jù)結(jié)構(gòu)D 程序 數(shù)據(jù)與相關(guān)文檔的完整集合 軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分 是包括程序 數(shù)據(jù)和相關(guān)文檔的完整集合 答案 D 例 軟件需求規(guī)格說(shuō)明書(shū)應(yīng)具有完整性 無(wú)歧義性 可驗(yàn)證性 可修改性等特性 其中最重要的是 無(wú)歧義性 作為設(shè)計(jì)的基礎(chǔ)和驗(yàn)收的依據(jù) 軟件需求規(guī)格說(shuō)明書(shū)應(yīng)該是精確而無(wú)二義性的 需求說(shuō)明書(shū)越精確 則以后出現(xiàn)錯(cuò)誤 混淆 反復(fù)的可能性就越小 答案 無(wú)歧義性 例 在兩種基本測(cè)試方法中 測(cè)試的原則之一是保證所測(cè)模塊中每一個(gè)獨(dú)立路徑至少執(zhí)行一次 答案 路徑覆蓋 例 軟件設(shè)計(jì)中模塊劃分應(yīng)遵循的準(zhǔn)則是 A低內(nèi)聚低耦合B高內(nèi)聚低耦合C低內(nèi)聚高耦合D高內(nèi)聚低耦合 答案 B 例 在軟件開(kāi)發(fā)中 需求分析階段產(chǎn)生的主要文檔是 A 可行性分析報(bào)告B 軟件需求規(guī)格說(shuō)明書(shū)C 概要設(shè)計(jì)說(shuō)明書(shū)D 集成測(cè)試計(jì)劃 答案 B 例 在軟件開(kāi)發(fā)中 需求分析階段可以使用的 工具是 A N S圖B DFD圖C PAD圖D 程序流程圖 結(jié)構(gòu)化分析常用工具 數(shù)據(jù)流圖 DFD 數(shù)據(jù)字典 DD 詳細(xì)設(shè)計(jì)階段常用的工具 程序流程圖 N S圖 PAD圖 答案 B 例 按照軟件測(cè)試的一般步驟 集成測(cè)試應(yīng)在測(cè)試之后進(jìn)行 軟件測(cè)試過(guò)程一般按4個(gè)步驟進(jìn)行 即單元測(cè)試 集成測(cè)試 驗(yàn)收測(cè)試 確認(rèn)測(cè)試 和系統(tǒng)測(cè)試 答案 單元 例 軟件工程三要素包括方法 工具和過(guò)程 其中 支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控制和管理 軟件工程包括3個(gè)要素 即方法 工具和過(guò)程 方法是完成軟件工程項(xiàng)目的技術(shù)手段 工具支持軟件的開(kāi)發(fā) 管理 文檔生成 過(guò)程支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控制 管理 答案 過(guò)程 例 軟件按功能可以分為 應(yīng)用軟件 系統(tǒng)軟件和支撐軟件 或工具軟件 下面屬于應(yīng)用軟件的是 A 編譯程序B 操作系統(tǒng)C 教務(wù)管理系統(tǒng)D 匯編程序 編譯程序 操作系統(tǒng)和匯編程序都屬于系統(tǒng)軟件 而只有教務(wù)管理系統(tǒng)是為解決特定領(lǐng)域的應(yīng)用而開(kāi)發(fā)的軟件 屬于應(yīng)用軟件的范疇 答案 C 例 下面敘述中錯(cuò)誤的是 A 軟件測(cè)試的目的是發(fā)現(xiàn)錯(cuò)誤并改正錯(cuò)誤B 對(duì)被調(diào)試的程序進(jìn)行 錯(cuò)誤定位 是程序調(diào)試的必要步驟C 程序調(diào)試通常也稱為DebugD 軟件測(cè)試應(yīng)嚴(yán)格執(zhí)行測(cè)試計(jì)劃 排除測(cè)試的隨意性 軟件測(cè)試的目的是為了發(fā)現(xiàn)錯(cuò)誤 而改正錯(cuò)誤屬于程序調(diào)試的范疇 答案 A 例 軟件測(cè)試可分為白盒測(cè)試和黑盒測(cè)試 基本路徑測(cè)試屬于測(cè)試 白盒測(cè)試的主要方法有邏輯覆蓋 基本路徑測(cè)試等 答案 白盒測(cè)試 例 程序流程圖中帶箭頭的線段表示的是 A圖元關(guān)系B數(shù)據(jù)流C控制流D調(diào)用關(guān)系 詳細(xì)設(shè)計(jì)階段的主要描述工具分為圖形 語(yǔ)言和表格描述工具 程序流程圖是常用的圖形描述工具之一 流程圖中包含的主要元素有方框 表示一個(gè)處理步驟 菱形框 表示一個(gè)邏輯條件 箭頭 表示控制流向 答案 C 例 下圖所示的流程控制結(jié)構(gòu)稱為 答案 分支結(jié)構(gòu) 選擇結(jié)構(gòu)或條件結(jié)構(gòu) 例 某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示 該系統(tǒng)總體結(jié)構(gòu)圖的深度是A 7B 6C 3D 2 答案 C 例 在結(jié)構(gòu)化分析使用的數(shù)據(jù)流圖 DFD 中 利用對(duì)其中的圖形元素進(jìn)行確切解釋 數(shù)據(jù)字典的作用是對(duì)DFD中出現(xiàn)的被命名的圖形元素的確切解釋 答案 數(shù)據(jù)字典 第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) 本章考試要點(diǎn) 數(shù)據(jù)庫(kù)的基本概念 數(shù)據(jù)庫(kù) 數(shù)據(jù)庫(kù)管理系統(tǒng) 數(shù)據(jù)庫(kù)系統(tǒng) 數(shù)據(jù)模型 實(shí)體聯(lián)系模型及E R圖 從E R圖導(dǎo)出關(guān)系數(shù)據(jù)模型 關(guān)系代數(shù)運(yùn)算 集合運(yùn)算及選擇 投影 聯(lián)接運(yùn)算 數(shù)據(jù)庫(kù)規(guī)范化理論 數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟 需求分析 概念設(shè)計(jì) 邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略 1 數(shù)據(jù) 數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)管理系統(tǒng) 數(shù)據(jù) 數(shù)據(jù)庫(kù) 長(zhǎng)期存儲(chǔ)在計(jì)算機(jī)內(nèi)的 有組織的 可共享的數(shù)據(jù)集合 數(shù)據(jù)庫(kù)是由一個(gè)互相關(guān)聯(lián)的數(shù)據(jù)的集合和一組用以訪問(wèn)這些數(shù)據(jù)的程序組成 數(shù)據(jù)庫(kù)管理系統(tǒng) 數(shù)據(jù)庫(kù)管理員 數(shù)據(jù)庫(kù)系統(tǒng) 數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng) 一 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念 2 數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展 人工管理階段 文件系統(tǒng)階段 數(shù)據(jù)庫(kù)統(tǒng)階段3 數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn) 數(shù)據(jù)的集成性 數(shù)據(jù)的高共享性與低冗余性 數(shù)據(jù)的獨(dú)立性 物理獨(dú)立性與邏輯獨(dú)立性 數(shù)據(jù)統(tǒng)一管理與控制 4 數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系 三級(jí)模式 概念模式 內(nèi)模式 外模式 兩級(jí)映射 概念模式到內(nèi)模式的映射 外模式到概念模式的映射 1 數(shù)據(jù)模型的基本概念 數(shù)據(jù)模型的定義 數(shù)據(jù)模型所描述內(nèi)容的三個(gè)部分?jǐn)?shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)操作 數(shù)據(jù)約束 數(shù)據(jù)模型的類型 概念模型面向用戶的模型 邏輯模型 數(shù)據(jù)模型 面向數(shù)據(jù)庫(kù)系統(tǒng)的模型 只有轉(zhuǎn)換成數(shù)據(jù)模型后才能在數(shù)據(jù)庫(kù)中得以表示 物理模型面向計(jì)算機(jī)的物理表示 二 數(shù)據(jù)模型 2 E R模型 長(zhǎng)期以來(lái)被廣泛使用的概念模型是E R模型 E R模型的基本概念 實(shí)體 屬性 聯(lián)系 1 1 1 m m n E R模型三個(gè)基本概念之間的連接關(guān)系 實(shí)體集 聯(lián)系 與屬性之間的連接關(guān)系 實(shí)體 集 與聯(lián)系 E R模型的圖示法 實(shí)體集表示法 矩形 屬性表示法 橢圓形 聯(lián)系表示法 菱形 實(shí)體集 聯(lián)系 與屬性之間的連接關(guān)系 實(shí)體集與聯(lián)系之間的連接關(guān)系 E R圖 3 層次模型 是最早發(fā)展起來(lái)的數(shù)據(jù)庫(kù)模型 層次模型的基本結(jié)構(gòu)是樹(shù)形結(jié)構(gòu) 樹(shù)結(jié)構(gòu)的特點(diǎn)4 網(wǎng)狀模型 是一個(gè)不加任何條件限制的無(wú)向圖 一般采用分解的方法將一個(gè)網(wǎng)絡(luò)分成若干個(gè)二級(jí)樹(shù) 5 關(guān)系模型 關(guān)系的數(shù)據(jù)結(jié)構(gòu) 關(guān)系模型采用二維表來(lái)表示 二維表由表的框架及表的元組組成 二維表一般滿足七個(gè)性質(zhì) 關(guān)系模型中的重要概念 鍵 碼 鍵 二維表中凡能惟一識(shí)別元組的最小屬性集稱該表的鍵 候選鍵 主鍵 外鍵 關(guān)系操縱關(guān)系模型的數(shù)據(jù)操縱是建立在關(guān)系上的數(shù)據(jù)操縱 包括 數(shù)據(jù)查詢 數(shù)據(jù)刪除 數(shù)據(jù)插入 數(shù)據(jù)修改 關(guān)系中的數(shù)據(jù)約束關(guān)系模型允許3類數(shù)據(jù)約束 實(shí)體完整性約束主鍵的值不能為空 參照完整性約束不允許關(guān)系引用不存在的元組 用戶自定義約束針對(duì)具體數(shù)據(jù)環(huán)境由用戶設(shè)置的約束 1 關(guān)系模型的基本操作 關(guān)系是由若干個(gè)不同的元組所組成 因此關(guān)系可視為元組的集合 關(guān)系模型有插入 刪除 修改和查詢4種操作 關(guān)系的屬性指定 關(guān)系的元組選擇 關(guān)系的合并 關(guān)系的查詢 關(guān)系元組的插入 關(guān)系元組的刪除 三 關(guān)系代數(shù) 關(guān)系是有序組的集合 因此可以將操作看作是集合的運(yùn)算 關(guān)系模型的基本運(yùn)算包括 插入R R 刪除R R 修改 R R R 先刪后插 查詢 用于查詢運(yùn)算的3個(gè)操作需引入新的運(yùn)算 投影 字段 選擇 記錄 笛卡爾兒積T R S 2 關(guān)系模型的基本運(yùn)算 3 關(guān)系代數(shù)中的擴(kuò)充運(yùn)算 交運(yùn)算R S R R S 除運(yùn)算T R S 連接與自然連接運(yùn)算 連接是將兩個(gè)關(guān)系按指定的條件合并成一個(gè)關(guān)系 條件可以是等值或不等值 自然連接必須滿足 兩關(guān)系間有公共域 通過(guò)公共域的相等值進(jìn)行連接 例 關(guān)系R和S如下圖 它們自然連接后得到T T R S 例 關(guān)系R和S如下圖 它們按D E進(jìn)行連接后得到T T R S 1 數(shù)據(jù)庫(kù)設(shè)計(jì)概述 數(shù)據(jù)庫(kù)設(shè)計(jì)一般采用生命周期法 數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的開(kāi)發(fā)分為若干個(gè)階段 需求分析階段 需求說(shuō)明書(shū) 概念設(shè)計(jì)階段 概念數(shù)據(jù)模型 邏輯設(shè)計(jì)階段 邏輯數(shù)據(jù)模型 物理設(shè)計(jì)階段 數(shù)據(jù)庫(kù)內(nèi)模式 編碼階段 測(cè)試階段 運(yùn)行階段 進(jìn)一步修改階段 數(shù)據(jù)庫(kù)設(shè)計(jì) 四 數(shù)據(jù)庫(kù)設(shè)計(jì)與管理 2 數(shù)據(jù)庫(kù)設(shè)計(jì)的需求分析 需求分析是設(shè)計(jì)數(shù)據(jù)庫(kù)的起點(diǎn) 需求分析的任務(wù) 需求分析的主要工具是數(shù)據(jù)流圖 數(shù)據(jù)字典是進(jìn)行詳細(xì)的數(shù)據(jù)收信和數(shù)據(jù)分析所獲得的主要結(jié)果 包括五個(gè)部分 數(shù)據(jù)項(xiàng) 數(shù)據(jù)的最小單位 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)流 可以是數(shù)據(jù)項(xiàng)或數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)存儲(chǔ) 處理過(guò)程 3 數(shù)據(jù)庫(kù)的概念設(shè)計(jì) 數(shù)據(jù)庫(kù)概念設(shè)計(jì)的目的 數(shù)據(jù)庫(kù)概念設(shè)計(jì)的方法 集中式模式設(shè)計(jì)法 視圖集成設(shè)計(jì)法 數(shù)據(jù)庫(kù)概念設(shè)計(jì)的過(guò)程 使用E R圖 4 數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì) 邏輯設(shè)計(jì)是在概念設(shè)計(jì)的基礎(chǔ)上 將與數(shù)據(jù)庫(kù)管理系統(tǒng)無(wú)關(guān)的E R圖轉(zhuǎn)換成以數(shù)據(jù)庫(kù)管理系統(tǒng)的邏輯數(shù)據(jù)模型表示的邏輯模式 關(guān)系數(shù)據(jù)模型 邏輯設(shè)計(jì)的過(guò)程 5 數(shù)據(jù)庫(kù)的物理設(shè)計(jì) 數(shù)據(jù)庫(kù)在物理設(shè)備上的存儲(chǔ)結(jié)構(gòu)與存取方法稱為數(shù)據(jù)庫(kù)的物理結(jié)構(gòu) 它依賴于給定的數(shù)據(jù)庫(kù)管理系統(tǒng)和計(jì)算機(jī)系統(tǒng) 物理設(shè)計(jì)的主要目標(biāo) 物理設(shè)計(jì)的內(nèi)容 索引設(shè)計(jì) 集簇設(shè)計(jì) 分區(qū)設(shè)計(jì) 數(shù)據(jù)庫(kù)的建立 數(shù)據(jù)庫(kù)的調(diào)整 數(shù)據(jù)庫(kù)的重組 數(shù)據(jù)庫(kù)安全性控制與完整性控制 數(shù)據(jù)庫(kù)的故障恢復(fù) 數(shù)據(jù)庫(kù)監(jiān)控 數(shù)據(jù)庫(kù)管理 例 在數(shù)據(jù)庫(kù)系統(tǒng)中 用戶所見(jiàn)的數(shù)據(jù)模式為 A 概念模式B 外模式C 內(nèi)模式D 物理模式 外模式是用戶的數(shù)據(jù)視圖 就是用戶所見(jiàn)到的數(shù)據(jù)模式 答案 B 例 數(shù)據(jù)庫(kù)設(shè)計(jì)的四個(gè)階段是 需求分析 概念設(shè)計(jì) 邏輯設(shè)計(jì)和 A 編碼設(shè)計(jì)B 測(cè)試階段C 運(yùn)行階段D 物理設(shè)計(jì) 數(shù)據(jù)庫(kù)設(shè)計(jì)主要分四個(gè)步驟 需求分析 概念結(jié)構(gòu)設(shè)計(jì) 邏輯結(jié)構(gòu)設(shè)計(jì) 物理結(jié)構(gòu)設(shè)計(jì) 答案 D 例 有三個(gè)關(guān)系R S和T如下 則由關(guān)系R和S得到關(guān)系T的操作是 A 自然連接B 交C 除D 并 答案 C 例 設(shè)有如三個(gè)關(guān)系表下列操作中正確的是A T R SB T R SC T R SD T R S 答案 C 笛卡爾積 例 數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)的 A 存儲(chǔ)問(wèn)題B 共享問(wèn)題C 安全問(wèn)題D 保護(hù)問(wèn)題 答案 B 例 下列實(shí)體的聯(lián)系中 屬于多對(duì)多聯(lián)系的是 A 學(xué)生與課程B 學(xué)校與校長(zhǎng)C 住院的病人與病床D 職工與工資 答案 A 例 在關(guān)系運(yùn)算中 投影運(yùn)算的含義是 A 在基本表中選擇滿足條件的記錄組成一個(gè)新的關(guān)系B 在基本表中選擇需要的字段 屬性 組成一個(gè)新的關(guān)系C 在基本表中選擇滿足條件的記錄和屬性組成一個(gè)新的關(guān)系D 上述說(shuō)法均是正確的 答案 B 例 SQL的含義是 A 結(jié)構(gòu)化查詢語(yǔ)言B 數(shù)據(jù)定義語(yǔ)言C 數(shù)據(jù)庫(kù)查詢語(yǔ)言D 數(shù)據(jù)庫(kù)操縱與控制語(yǔ)言 答案 A 例 一個(gè)關(guān)系表的行稱為 答案 記錄 例 在下列關(guān)系運(yùn)算中 不改變關(guān)系表中的屬性個(gè)數(shù)但能減少元組個(gè)數(shù)的是 A 并B 交C 投影D 笛卡兒乘積 答案 B 關(guān)系運(yùn)算包括 常用的集合運(yùn)算有交 并 差和專門(mén)的關(guān)系運(yùn)算選擇 投影 連接 這其中只有交 選擇運(yùn)算能夠在不改變基本表中的屬性個(gè)數(shù)但能減少元組個(gè)數(shù) 例 在E R圖中 用來(lái)表示實(shí)體之間聯(lián)系的圖形是 A 矩形B 橢圓形C 菱形D 平行四邊形 在E R圖中 有三個(gè)基本的抽象概念 實(shí)體 聯(lián)系和屬性 E R圖示E R模型的圖形表示法 在E R圖中 用矩形框表示實(shí)體 菱形框表示聯(lián)系 橢圓形框表示屬性 答案 C 例 在關(guān)系數(shù)據(jù)中 能夠惟一地標(biāo)識(shí)一個(gè)記錄的屬性或?qū)傩缘慕Y(jié)合 稱為 A 關(guān)鍵字B 屬性C 關(guān)系D 域 在關(guān)系數(shù)據(jù)庫(kù)中 能夠唯一標(biāo)識(shí)一個(gè)記錄的屬性或?qū)傩缘慕M合稱為關(guān)鍵字 答案 A 例 在現(xiàn)實(shí)世界中 每個(gè)人都有自己的出生地 實(shí)體 人 與實(shí)體 出生地 之間的聯(lián)系是 A 一對(duì)一聯(lián)系B 一對(duì)多聯(lián)系C 多對(duì)多聯(lián)系D 無(wú)聯(lián)系 答案 B 例 在數(shù)據(jù)庫(kù)系統(tǒng)中 實(shí)現(xiàn)各種數(shù)據(jù)管理功能的核心軟件稱為 答案 數(shù)據(jù)庫(kù)管理系統(tǒng) 例 如果表中一個(gè)字段不是本表的主關(guān)鍵字 而另外一個(gè)表的主關(guān)鍵字或候選關(guān)鍵字 這個(gè)字段稱為 答案 外部關(guān)鍵字 例 實(shí)體完整性約束要求關(guān)系數(shù)據(jù)庫(kù)中元組的屬性值不能為空 答案 關(guān)鍵字 例 在關(guān)系A(chǔ) S SN D 和關(guān)系B D CN NM 中 A的主關(guān)鍵字是S B的主關(guān)鍵字是D 則稱 是關(guān)系A(chǔ)的外碼 答案 D 例 在SQL的Select命令中用短語(yǔ)對(duì)查詢的結(jié)果進(jìn)行排序 答案 ORDERBY 例 在關(guān)系運(yùn)算中 要從關(guān)系模式中指定若干屬性組成新的關(guān)系 該關(guān)系運(yùn)算稱為 答案 投影 例 下列敘述中正確的是 A 為了建立一個(gè)關(guān)系 首先要構(gòu)造數(shù)據(jù)的邏輯關(guān)系B 表示關(guān)系的二維表中各元組的每一個(gè)分量還可以分成若干個(gè)數(shù)據(jù)項(xiàng)C 一個(gè)關(guān)系的屬性名表稱為關(guān)系模式D 一個(gè)關(guān)系可以包括多個(gè)二維表 答案 C 例 用二維表來(lái)表示實(shí)體及實(shí)體之間聯(lián)系的數(shù)據(jù)模型是 A 實(shí)體 聯(lián)系模型B 層次模型C 網(wǎng)狀模型D 關(guān)系模型 關(guān)系數(shù)據(jù)模型用二維表的形式來(lái)表示實(shí)體間的聯(lián)系 答案 D 例 在企業(yè)中 職工的 工資級(jí)別 與職工個(gè)人 工資 的聯(lián)系是 A 一對(duì)一聯(lián)系B 一對(duì)多聯(lián)系C 多對(duì)多聯(lián)系D 無(wú)聯(lián)系 每個(gè)人的個(gè)人工資都對(duì)應(yīng)有一個(gè)工資級(jí)別 但一個(gè)工資級(jí)別可對(duì)應(yīng)多個(gè)人的個(gè)人工資 所以工資級(jí)別與工資之間的聯(lián)系是一對(duì)多 答案 B 例 假設(shè)一個(gè)書(shū)店用 書(shū)號(hào) 書(shū)名 作者 出版社 出版日期 庫(kù)存數(shù)量 一組屬性來(lái)描述圖書(shū) 可以作為 關(guān)鍵字 的是 A 書(shū)號(hào)B 書(shū)名C 作者D 出版社 關(guān)鍵字的定義為 若一個(gè)屬性或多個(gè)屬性的組合可以起到唯一識(shí)別元組的作用 即可被選取為關(guān)鍵字 答案 A 例 在教師表中 如果找出職稱為 教授 的教師 所采用的關(guān)系運(yùn)算是 A選擇B投影C聯(lián)接D自然聯(lián)接 選擇運(yùn)算是根據(jù)給定的條件選擇符合條件的記錄 投影運(yùn)算是從關(guān)系表中選擇部分屬性進(jìn)行顯示 連接運(yùn)算是把多個(gè)表進(jìn)行連接顯示 自然連接是連接運(yùn)算的一種 自然連接的條件是共有屬性對(duì)應(yīng)相等進(jìn)行連接 要找出職稱為教授的教師是一種選擇運(yùn)算 答案 A 例 在數(shù)據(jù)庫(kù)管理系統(tǒng)提供的數(shù)據(jù)定義語(yǔ)言 數(shù)據(jù)操縱語(yǔ)言和數(shù)據(jù)控制語(yǔ)言中 負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建 數(shù)據(jù)定義語(yǔ)言 數(shù)據(jù)定義語(yǔ)言用于定義數(shù)據(jù)庫(kù)的所有特性和屬性 尤其是行布局 列定義 鍵列 有時(shí)是選鍵方法 文件位置和存儲(chǔ)策略 數(shù)據(jù)庫(kù)操縱語(yǔ)言用于查詢和操縱模式對(duì)象中的數(shù)據(jù) 數(shù)據(jù)庫(kù)控制語(yǔ)言控制用戶對(duì)數(shù)據(jù)庫(kù)的存取能力 控制數(shù)據(jù)庫(kù)的安全性 答案 數(shù)據(jù)定義語(yǔ)言 例 在數(shù)據(jù)管理技術(shù)發(fā)展的三個(gè)階段中 數(shù)據(jù)共享最好的是 A 人工管理階段B 文件系統(tǒng)階段C 數(shù)據(jù)庫(kù)系統(tǒng)階段D 三個(gè)階段相同 人工管理階段 無(wú)共享 冗余度大 文件系統(tǒng)階段 共享性差 冗余度大 數(shù)據(jù)庫(kù)系統(tǒng)階段 共享性大 冗余度小 答案 C 例 有三個(gè)關(guān)系R S和T如下