1、NCRE二級(jí)公共基礎(chǔ)知識(shí)輔導(dǎo)講義I全國(guó)計(jì)算機(jī)等級(jí)考試全國(guó)計(jì)算機(jī)等級(jí)考試——二級(jí)公共基礎(chǔ)知識(shí)輔導(dǎo)講義二級(jí)公共基礎(chǔ)知識(shí)輔導(dǎo)講義目錄目錄第一章數(shù)據(jù)結(jié)構(gòu)與算法............................................................................................................................11.1算法...............
2、...........................................................................................................................................................11.2數(shù)據(jù)結(jié)構(gòu)的基本概念....................................................
3、..........................................................................................11.3線性表及其順序存儲(chǔ)結(jié)構(gòu)...................................................................................................................
4、...................21.4棧和隊(duì)列..................................................................................................................................................................21.5線性鏈表.......................
5、...........................................................................................................................................31.6樹(shù)與二叉樹(shù)........................................................................
6、......................................................................................41.7查找技術(shù)..............................................................................................................................
7、....................................51.8排序技術(shù)..................................................................................................................................................................6本章應(yīng)考點(diǎn)撥.......
8、..........................................................................................................................................................6第二章程序設(shè)計(jì)基礎(chǔ)........................................................
9、........................................................................72.1程序設(shè)計(jì)風(fēng)格..........................................................................................................................................
10、................72.2結(jié)構(gòu)化程序設(shè)計(jì)（面向過(guò)程的程序設(shè)計(jì)方法）..................................................................................................72.3面向?qū)ο蟮某绦蛟O(shè)計(jì).....................................................................
11、.........................................................................8本章應(yīng)考點(diǎn)撥............................................................................................................................................
12、.....................8第三章軟件工程基礎(chǔ)................................................................................................................................93.1軟件工程基本概念.................................................
13、.................................................................................................93.2結(jié)構(gòu)化分析方法................................................................................................................
14、....................................103.3結(jié)構(gòu)化設(shè)計(jì)方法....................................................................................................................................................113.4軟件測(cè)試...............
15、.................................................................................................................................................133.5程序的調(diào)試.................................................................
16、...........................................................................................15本章應(yīng)考點(diǎn)撥.........................................................................................................................
17、......................................15第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)..........................................................................................................................164.1數(shù)據(jù)庫(kù)系統(tǒng)的基本概念.................................
18、.......................................................................................................164.2數(shù)據(jù)模型............................................................................................................
19、....................................................184.3關(guān)系代數(shù)...............................................................................................................................................................
20、.204.4數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟........................................................................................................................................21本章應(yīng)考點(diǎn)撥............................................................
21、...................................................................................................21Comment[wx3]:在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前件的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)。NCRE二級(jí)公共基礎(chǔ)知識(shí)輔導(dǎo)講義2一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。4、數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（1）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1
22、）有且只有一個(gè)根結(jié)點(diǎn)；2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。：常見(jiàn)的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。（2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。：常見(jiàn)的非線性結(jié)構(gòu)有樹(shù)、二叉樹(shù)和圖等。1.3線性表及其順序存儲(chǔ)結(jié)構(gòu)線性表及其順序存儲(chǔ)結(jié)構(gòu)1、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。線性表是由n(n≥0)個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只
23、有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。線性表中數(shù)據(jù)元素的個(gè)數(shù)稱(chēng)為線性表的長(zhǎng)度。線性表可以為空表。2、線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。：由此可以看出，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面，可以通過(guò)計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。3、順序表的插入、刪除運(yùn)算（
24、1）順序表的插入運(yùn)算：在一般情況下，要在第i（1≤i≤n）個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)（即第n個(gè)）元素開(kāi)始，直到第i個(gè)元素之間共ni1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第i個(gè)位置就被空出，然后將新元素插入到第i項(xiàng)。插入結(jié)束后，線性表的長(zhǎng)度就增加了1。：順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)n2個(gè)元素。（2）順序表的刪除運(yùn)算：在一般情況下，要?jiǎng)h除第i（1≤i≤n）個(gè)元素時(shí)，則要從第i1個(gè)元素開(kāi)始
25、，直到第n個(gè)元素之間共ni個(gè)元素依次向前移動(dòng)一個(gè)位置。刪除結(jié)束后，線性表的長(zhǎng)度就減小了1。：進(jìn)行順性表的刪除運(yùn)算時(shí)也需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)（n1）2個(gè)元素。插入、刪除運(yùn)算不方便。1.4棧和隊(duì)列棧和隊(duì)列1、棧及其基本運(yùn)算棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性表。在棧中，允許插入與刪除的一端稱(chēng)為棧頂，不允許插入與刪除的另一端稱(chēng)為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進(jìn)后出”或“后
26、進(jìn)先出”的原則組織數(shù)據(jù)的。棧具有記憶作用。棧的基本運(yùn)算：1）插入元素稱(chēng)為入棧運(yùn)算；2）刪除元素稱(chēng)為退棧運(yùn)算；3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化。棧的存儲(chǔ)方式和線性表類(lèi)似，也有兩種，即順序棧和鏈?zhǔn)綏！?、隊(duì)列及其基本運(yùn)算隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)行插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。尾指針（Rear）指向隊(duì)尾元素，頭指針（front）指向排頭元素的前一個(gè)位置（隊(duì)頭）。隊(duì)列是“先進(jìn)先出”或“后進(jìn)后出”的線性
