全國(guó)二級(jí)考試公共基礎(chǔ)部分重點(diǎn)與難點(diǎn)

1、全國(guó)二級(jí)考試公共基礎(chǔ)部分重點(diǎn)與難點(diǎn) 1順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 1 2 3 4 5 6 圖i線性表的順序存儲(chǔ)示意 頭結(jié)點(diǎn) 圖2線性單鏈表的存儲(chǔ)結(jié)構(gòu)示意 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 優(yōu)點(diǎn) ? 邏輯相鄰，物理相鄰 ? 插入、刪除操作不需要移動(dòng)大量的兀 ? 素, 修改指針即可 可隨機(jī)存取仕元素 ? 存儲(chǔ)空間使用緊湊，存儲(chǔ)密度 =1 ? 存儲(chǔ)空間動(dòng)態(tài)分配，表容量容易擴(kuò)充 ? 存儲(chǔ)空間可以不必連續(xù) 缺點(diǎn) ? 插入、刪除操作需要移動(dòng)大量的兀素 ? 指針需要占用額外的存儲(chǔ)空間， 存儲(chǔ) ? 預(yù)先分配空間需按最大空間分配， 利用 密度 1 不充分 ? 鏈表只能順序存取兀素，不可以隨機(jī) ? 表容量難以擴(kuò)充 存取

2、 2. 入棧與出棧 dat 25 34 57 16 4 09 F 1A % A 數(shù)揖域緡卜域 結(jié)點(diǎn) E 棧：只允許在一端插入和刪除的線性表叫棧，允許插入和刪除的一端稱為棧頂(top)， 另一端稱為棧底（bottom） 特點(diǎn)： 后進(jìn)先出(LIFO, Last In First Out)或先進(jìn)后出(FILO) 順序棧用一維數(shù)組 S （1: m）實(shí)現(xiàn)，top=0表示棧空，top=m表示棧滿。 棧中存放數(shù)據(jù)的個(gè)數(shù)為： num = （top - bottom ）+1 進(jìn)棧（push）:也叫入棧，即在棧頂位置插入一個(gè)新元素，先將 top +1，然后將新元素插 入到top所指的位置；當(dāng)top已指向棧存儲(chǔ)空間

3、的最后一個(gè)位置時(shí)，說明棧已滿，若再進(jìn) 行進(jìn)棧操作則出現(xiàn)“上溢”錯(cuò)誤。 出棧（pop）:也叫退棧，即取出棧頂元素并賦給一個(gè)指定的變量，先將棧頂元素賦值給一 個(gè)指定的變量，然后將 top-1 ;當(dāng)top為0時(shí)，說明棧已空，若再進(jìn)行出棧操作則出現(xiàn)“下 溢”錯(cuò)誤。 讀（get）棧頂元素：將棧頂元素賦值給一個(gè)指定的變量， top不變。 圖3順序棧的進(jìn)棧、出棧運(yùn)算示意 【?？碱}型】已知若干元素的入棧順序，如 A、B、C D、E,問：哪些是不可能的出 棧順序？哪些是可能的出棧順序？ 解題提示：可將棧想象成一個(gè)杯子，入棧就好比往杯子里放園球，先放進(jìn)去的在下面， 后放進(jìn)去的在上面， 取球的時(shí)候必須先取上面的，

4、后取下面的。凡是出入次序不存在矛 盾的元素序列就是可能的出棧順序。 比如本題可能的順序有：1）依次將球A、B、C D、 E全都放進(jìn)去后再取出來，則出棧順序?yàn)?EDCBA 2）先依次將A、B、C放進(jìn)去，然后 取出上面的2個(gè)，再將D、E放進(jìn)去，然后都取出來，則出棧順序?yàn)?CBEDA 3）先依 次將A、B放進(jìn)去，然后取出上面的 1個(gè)，再將C、D放進(jìn)去，然后都取出來，最后將 E 放進(jìn)去再取出來，這時(shí)出棧順序是 BDCAE其它可能的順序不再羅列。 思考：DBCAE DEBAC是可能的出棧順序嗎？ （答：不是，因?yàn)?D 是第一個(gè)出棧的， 說明其前面的 A、B、C 還沒出棧，那么這 3 個(gè)元素再出棧時(shí)必須符

5、合 CBA 的順序） 3. 循環(huán)隊(duì)列中的元素個(gè)數(shù) 隊(duì)列：只允許在一端插入、在另一段刪除的順序表叫隊(duì)列，允許刪除的一端稱為 （front），允許插入的一端稱為 隊(duì)尾（rear）。隊(duì)列用一維數(shù)組實(shí)現(xiàn) sqM隊(duì)頭 特點(diǎn)： 先進(jìn)先出 (FIFO, First In First Out) 隊(duì)列的進(jìn)隊(duì)、退隊(duì)原則: ?入隊(duì)時(shí)隊(duì)尾指針先進(jìn)一， rear = rear + 1，再將新元素按 rear指示位置加入。 ?退隊(duì)時(shí)隊(duì)頭指針先進(jìn)一，front = front + 1，再將下標(biāo)為front的元素取出。 ?隊(duì)滿時(shí)再入隊(duì)將產(chǎn)生“溢出”錯(cuò)誤； ?隊(duì)空時(shí)再退隊(duì)將產(chǎn)生“下溢”錯(cuò)誤。 圖4 隊(duì)列的入隊(duì)、退隊(duì)運(yùn)算示意 循

6、環(huán)隊(duì)列： 就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀 空間，供隊(duì)列循環(huán)使用，如圖 5所示。 循環(huán)隊(duì)列的運(yùn)算規(guī)則： ?每進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針就進(jìn)一，當(dāng) rear=m+1時(shí)，置rear=1 ； ?每進(jìn)行一次退隊(duì)運(yùn)算，隊(duì)頭指針就進(jìn)一，當(dāng) front=m+1時(shí)，置front=1 ； 循環(huán)隊(duì)列的狀態(tài)判斷： 為了區(qū)分隊(duì)列是滿還是空， 設(shè)立標(biāo)志s，當(dāng)s=1時(shí)表示隊(duì)列非空，當(dāng)s=0時(shí)表示隊(duì)列空。 ?循環(huán)隊(duì)列的初始狀態(tài)為空，即 s=0,且rear=front=m ； ?隊(duì)列空的條件為s=0； ?隊(duì)列滿的條件為 s=1且front=rear 。A B | | front rear H進(jìn)

7、隊(duì) frnnl renr 退隊(duì) 圖5 循環(huán)隊(duì)列的運(yùn)算示意 【?？碱}型】求循環(huán)隊(duì)列中的元素個(gè)數(shù) 循環(huán)隊(duì)列里面的個(gè)數(shù)計(jì)算方法： rear front 的時(shí)候， num = rear -front ; rear 2 rear - 1 Y 空的循環(huán)隊(duì)列 Q ( 1: m) rear m 2 1 正常的循環(huán)隊(duì)刪除A后的循環(huán)隊(duì)列 結(jié)點(diǎn) A 的度.3 結(jié)點(diǎn) B的度土 2 結(jié)點(diǎn) M 的度：0 圖6 樹的結(jié)構(gòu)示意 二叉樹的特點(diǎn)： ?每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn)) ?二叉樹的子樹有左、右之分，且其次序不能任意顛倒 -史樹的皐本庠態(tài)： (1) G) (3) (4) (5) 圖8三個(gè)結(jié)點(diǎn)二叉樹的五種

8、形態(tài) 樹的深度：4 鞫的度：3 結(jié)點(diǎn) A 的層次乂 1 結(jié)點(diǎn)町的層秋： 葉子：Kt L, F, Gr M, 1* J 結(jié)點(diǎn) A 的孩子：ar C, D 結(jié)點(diǎn) U 的孩子：E, F 踣點(diǎn) 的戲親： D 結(jié)點(diǎn) Lfi 曆親:E 轄點(diǎn) B” Ct D 為兄弟 結(jié)點(diǎn)氐，L 為兄弟 結(jié)點(diǎn) F.心為堂兄弟 結(jié)點(diǎn)堵點(diǎn) F &的祖先 1，則其雙親是i/2 ? 如果2in，則結(jié)點(diǎn)i無左孩子；如果2i n,則其左孩子是2i ? 如果2i+1n,則結(jié)點(diǎn)i無右孩子；如果2i+1 n,則其右孩子是 2i+1 ? 【?？碱}型】 計(jì)算二叉樹的結(jié)點(diǎn)個(gè)數(shù) 例如：1)某二叉樹共有 530個(gè)結(jié)點(diǎn)，其中度為 2的結(jié)點(diǎn)有250

9、個(gè)，則度為1的結(jié)點(diǎn)數(shù)為？ 解題思路：已知 n=nO+n 1+ n2 nO=n2+1 貝U: N0=n2+1=250+1=251, n1= n-nO-n2=530-250-25仁29 2)某二叉樹共有400個(gè)結(jié)點(diǎn)，其中有99個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為？ 解題思路： 根據(jù)性質(zhì)3可知：n2=n0-1,代入公式： n=n 0+n1 + n 2= n0+n 1+ n0-1 =2 n0+n1 1 溝二覽則也甕全二叉犧 fl 怛完仝-.華一淀昂満_豐 圖9滿二叉樹與完全二叉樹結(jié)構(gòu)對(duì)照 則：N0=( n-n 1+1)/ 2=(400-99+1)/2=151 二叉樹的遍歷 先序遍歷（DLR）:先

10、訪問根結(jié)點(diǎn)，然后分別先序遍歷左子樹、右子樹 中序遍歷（LDR）:先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹 后序遍歷（LRD）:先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn) 按層次遍歷：從上到下、從左到右訪問各結(jié)點(diǎn) 先序遍歷y + a * b- cd/ef 中序遍歷2 + 1 * c - 1- e / f 厲序遍歷用 b r O(nJ) -先謹(jǐn)?shù)呐判蚍椒ǘ?T(n)=0(nlogn) -分配類排序:T(nJ=O(d.n) .各種排斥方法的比較 排序方法1 比軟次數(shù) 移動(dòng)次數(shù) 穩(wěn)定 性 附加存儲(chǔ)i 晨好 差 最好 差 最好 差 直播播入排序 it i/ 0 n* 寸 折半虧入攤序 it log

11、2n : ll- 寸 1 起泡持序 n n- U n- 7 r - 快達(dá)排沖 rikii ir El h吧屮 亍 11* K itII3 簡(jiǎn)單遴擇排肩1 li1 n K i錦標(biāo)賽排序 n k響訶 li hgu J 堆播序 ti lo;n El ICgjU i i歸并養(yǎng)序n i logn ti logn r J n 8. 軟件開發(fā)中的各種圖 數(shù)據(jù)流圖(DFD圖)：用于需求分析階段，是描述數(shù)據(jù)處理過程的工具，是需求理解的邏 輯模型的圖形表示。 數(shù)據(jù)流圖所用主要圖形元素氏排序分類 符號(hào) 0 - 意義 加工（轉(zhuǎn)換） 數(shù)據(jù)流 存儲(chǔ)文件 源 E-R模型的五種圖示法 N-S圖：用于描述詳細(xì)設(shè)計(jì)，其選擇結(jié)構(gòu)如

12、下圖: ELSE THEM 問題分析圖（PAD圖）：用于描述詳細(xì)設(shè)計(jì)，其選擇結(jié)構(gòu)如下圖: 構(gòu)成程序流程圖的最基本圖符有: 9. 模塊間的內(nèi)聚與耦合 從弱到強(qiáng)分為7級(jí)：非直接耦合、數(shù)據(jù)耦合、標(biāo)記耦合、控制耦合、外部耦合、公共耦合 和內(nèi)容耦合。實(shí)體聯(lián)系圖（E-R圖）：用于數(shù)據(jù)庫(kù)概念設(shè)計(jì), 實(shí)體之間的聯(lián)系可分為 1:1,1:N , M:N三種。 E-R模型由實(shí)體、聯(lián)系、屬性三個(gè)概念組成, 倉(cāng)（o 質(zhì)性表示法 控制流（一-或J）、加工步驟（ 實(shí)悻集與聯(lián)岳間的履接關(guān)系 程序流程圖 ）、邏輯條件（ ) 10. 關(guān)系運(yùn)算 關(guān)系的基本運(yùn)算有兩類：一類是傳統(tǒng)的集合運(yùn)算（并、差、交等） 系運(yùn)算（選擇、投影、連接、

13、除法等） 1傳統(tǒng)的集合運(yùn)算 （針對(duì)兩個(gè)具有相同結(jié)構(gòu)關(guān)系的 R和S） 1. 并（UNION （ or,或） R和S的并是由屬于 R或?qū)儆赟的元組組成的集合，運(yùn)算符為U。記為 T= RU So 2. 差（DIFFERENCE R和S的差是由屬于 R但不屬于S的元組組成的集合，運(yùn)算符為一。記為 T= R- So 3. 交（INTERSECTION （and ,與） R和S的交是由既屬于 R又屬于S的元組組成的集合，運(yùn)算符為門。記為 T= RA So Rn S= R-（ R- S）o 二.專門的關(guān)系運(yùn)算 1 選擇運(yùn)算（針對(duì)一個(gè)關(guān)系） 2投影運(yùn)算（針對(duì)一個(gè)關(guān)系） 從關(guān)系中挑選若干屬性（列）組成新的關(guān)系稱

14、為投影。這是從列的角度進(jìn)行的運(yùn)算，相 當(dāng)于對(duì)關(guān)系進(jìn)行垂直分解。 例： 3 L B 二 Z ，另一類是專門的關(guān) 從關(guān)系中找出滿足給定條件的那些元組（ 行）稱為選擇。這種運(yùn)算是從水平方向抽取元組。 zn | i 3 I 3.笛卡爾積運(yùn)算（針對(duì)兩個(gè)關(guān)系，結(jié)構(gòu)可以不同） 設(shè)A,B為集合，用A中元素為第一元素，B中元素為第二元素構(gòu)成的有序?qū)Γ羞@ 樣的有序?qū)M成的集合叫做 A與B的笛卡爾積，記作 AxB。 例如，A=a,b,B=0,1,2, 貝 U AxB=, BxA=, 4. 連接與自然連接運(yùn)算 （針對(duì)兩個(gè)關(guān)系，結(jié)構(gòu)可以不同，但必須有公共域） 連接運(yùn)算是從兩個(gè)關(guān)系的笛卡爾積中選擇屬性間滿足一定條件的元組。 連接是將兩個(gè)關(guān)系通過公共的屬性名拼接成一個(gè)更寬的關(guān)系模式，生成的新關(guān)系中包含 滿足連接