2011年3月二級(jí)公共基礎(chǔ)知識(shí)講義.ppt

1 內(nèi)部資料 2011年3月計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)培訓(xùn)講義理工大樓915 2 二級(jí)Access考試介紹 一 考試方式1 筆試 90分鐘 滿分100分 其中含公共基礎(chǔ)知識(shí)部分30分2 上機(jī)操作 90分鐘 滿分100分二 筆試題型及分值 根據(jù)考試大綱及往年試題 1 選擇題70分 每小題2分 共35題 2 填空題30分 每空2分 共15題 三 上機(jī)操作1 基本操作 30分 2 簡(jiǎn)單應(yīng)用 40分 3 綜合應(yīng)用 30分 3 我們的目標(biāo) 通過二級(jí)考試 4 基礎(chǔ)知識(shí)部分 30分 設(shè)有10道選擇題和5道填空題 5 第一章數(shù)據(jù)結(jié)構(gòu)與算法 1 1算法1 2數(shù)據(jù)結(jié)構(gòu)的基本概念1 3線性表及其順序存儲(chǔ)結(jié)構(gòu)1 4棧和隊(duì)列1 5線性鏈表1 6樹與二叉樹1 7查找技術(shù)1 8排序技術(shù) 6 1 6樹與二叉樹 1 6 1樹的基本概念樹是一種簡(jiǎn)單的非線性結(jié)構(gòu) 所有元素之間具有明顯的層次特性 在樹結(jié)構(gòu)中 每一個(gè)結(jié)點(diǎn)只有一個(gè)前件 稱為父結(jié)點(diǎn) 沒有前件的結(jié)點(diǎn)只有一個(gè) 稱為樹的根結(jié)點(diǎn) 簡(jiǎn)稱樹的根 每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件 稱為該結(jié)點(diǎn)的子結(jié)點(diǎn) 沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn) 在樹結(jié)構(gòu)中 一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度 所有結(jié)點(diǎn)中最大的度稱為樹的度 樹的最大層次稱為樹的深度 7 1 6 2二叉樹及其基本性質(zhì) 二叉樹的特點(diǎn) 1 非空二叉樹只有一個(gè)根結(jié)點(diǎn) 2 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹 且分別稱為該結(jié)點(diǎn)的左子樹與右子樹 8 二叉樹的基本性質(zhì) 1 在二叉樹的第k層上 最多有2k 1 k 1 個(gè)結(jié)點(diǎn) 2 深度為m的二叉樹最多有2m 1個(gè)結(jié)點(diǎn) 3 度為0的結(jié)點(diǎn) 即葉子結(jié)點(diǎn) 總是比度為2的結(jié)點(diǎn)多一個(gè) 4 具有n個(gè)結(jié)點(diǎn)的二叉樹 其深度至少為 log2n 1 其中 log2n 表示取log2n的整數(shù)部分 9 滿二叉樹 滿二叉樹是指除最后一層外 每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn) 則k層上有2k 1個(gè)結(jié)點(diǎn)深度為m的滿二叉樹有2m 1個(gè)結(jié)點(diǎn) 10 11 12 完全二叉樹 完全二叉樹是指除最后一層外 每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值 在最后一層上只缺少右邊的若干結(jié)點(diǎn) 13 滿二叉樹與完全二叉樹 5 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n 1 6 設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn) 如果從根結(jié)點(diǎn)開始 按層序 每一層從左到右 用自然數(shù)1 2 n給結(jié)點(diǎn)進(jìn)行編號(hào) k 1 2 n 有以下結(jié)論 若k 1 則該結(jié)點(diǎn)為根結(jié)點(diǎn) 它沒有父結(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)無左子結(jié)點(diǎn) 也無右子結(jié)點(diǎn) 若2k 1 n 則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k 1 否則該結(jié)點(diǎn)無右子結(jié)點(diǎn) 14 1 6 3二叉樹的存儲(chǔ)結(jié)構(gòu) 在計(jì)算機(jī)中 二叉樹存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 對(duì)于滿二叉樹與完全二叉樹可以按層序進(jìn)行順序存儲(chǔ) 15 1 6 4二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn) 二叉樹的遍歷 1 前序遍歷 DLR 首先訪問根結(jié)點(diǎn) 然后遍歷左子樹 最后遍歷右子樹 2 中序遍歷 LDR 首先遍歷左子樹 然后訪問根結(jié)點(diǎn) 最后遍歷右子樹 3 后序遍歷 LRD 首先遍歷左子樹 然后訪問遍歷右子樹 最后訪問根結(jié)點(diǎn) 16 1 前序遍歷 DLR 前序遍歷首先訪問根結(jié)點(diǎn)然后遍歷左子樹 最后遍歷右子樹 在遍歷左 右子樹時(shí) 仍然先訪問根結(jié)點(diǎn) 然后遍歷左子樹 最后遍歷右子樹 即 若二叉樹為空則結(jié)束返回 否則 1 訪問根結(jié)點(diǎn) 2 前序遍歷左子樹 3 前序遍歷右子樹注意的是 遍歷左右子樹時(shí)仍然采用前序遍歷方法 例 如圖二叉樹 則前序遍歷結(jié)果是 ABDECF 17 2 中序遍歷 LDR 中序遍歷首先遍歷左子樹 然后訪問根結(jié)點(diǎn) 最后遍歷右子樹 在遍歷左 右子樹時(shí) 仍然先遍歷左子樹 再訪問根結(jié)點(diǎn) 最后遍歷右子樹 即 若二叉樹為空則結(jié)束返回 否則 1 中序遍歷左子樹 2 訪問根結(jié)點(diǎn) 3 中序遍歷右子樹 注意的是 遍歷左右子樹時(shí)仍然采用中序遍歷方法 例 如圖二叉樹 則中序遍歷結(jié)果是 DBEAFC 18 3 后序遍歷 LRD 后序遍歷首先遍歷左子樹 然后遍歷右子樹 最后訪問根結(jié)點(diǎn) 在遍歷左 右子樹時(shí) 仍然先遍歷左子樹 然后遍歷右子樹 最后訪問根結(jié)點(diǎn) 即 若二叉樹為空則結(jié)束返回 否則 1 后序遍歷左子樹 2 后序遍歷右子樹 3 最后訪問根結(jié)點(diǎn) 注意的是 遍歷左右子樹時(shí)仍然采用后序遍歷方法 例 如圖二叉樹 19 例 ABDECFG DBEAFGC DEBGFCA 前序遍歷 中序遍歷 后序遍歷 20 歷年考題 2005年4月填空第1題 1 某二叉樹中度為2的結(jié)點(diǎn)有18個(gè) 則該二叉樹中有 個(gè)葉子結(jié)點(diǎn) 2005年4月填空第4題 4 一棵二叉樹第六層 根結(jié)點(diǎn)為第一層 的結(jié)點(diǎn)數(shù)最多為 個(gè) 2007年4月選擇第7題 7 某二叉樹中有n個(gè)度為2的結(jié)點(diǎn) 則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為A n 1B n 1C 2nD n 2 21 歷年考題 2007年4月填空第1題 1 在深度為7的滿二叉樹中 度為2的結(jié)點(diǎn)個(gè)數(shù)為 2007年9月選擇第8題 8 一棵二叉樹中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn) 則該二叉樹中的總結(jié)點(diǎn)數(shù)為A 219B 221C 229D 231 2008年4月填空第2題 2 深度為5的滿二叉樹有個(gè)葉子結(jié)點(diǎn) 22 2006年4月選擇第6題 6 對(duì)下列二叉樹進(jìn)行后序遍歷的結(jié)果為A ABCDEFB DBEAFCC ABDECFD DEBFCA 23 2007年4月選擇第6題 6 對(duì)下列二叉樹進(jìn)行前序遍歷的結(jié)果為A DYBEAFCZXB YDEBFZXCAC ABDYECFXZD ABCDEFXYZ 24 2007年9月填空第4題 4 對(duì)下列二叉樹進(jìn)行中序遍歷的結(jié)果為 4 25 2008 9 1 對(duì)下列二叉樹進(jìn)行中序遍歷的結(jié)果是 1 26 P3