大綱要求
1．掌握算法的基本概念。
2．掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。
3．掌握基本排序和查找算法。
4．掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。
5．掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。
6．掌握數(shù)據(jù)的基本知識(shí)，了解關(guān)系數(shù)據(jù)庫的設(shè)計(jì)。
考試重點(diǎn)與經(jīng)驗(yàn)分析 
 基本數(shù)據(jù)結(jié)構(gòu)與算法
1．算法的基本概念及特征
算法的概念是考試的重點(diǎn)，是指解題方案的準(zhǔn)確而完整的描述，它由兩種基本要素組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。
算法具有可行性、確定性、有窮性、擁有足夠的情報(bào)等特征。其中，確定性和有窮性是考試的重點(diǎn)。
算法的確定性，是指算法中的每一步驟都必須有明確定義，不允許有模棱兩可的解釋，也不允許有多義性。
算法的有窮性，是指算法必須能在有限的時(shí)間內(nèi)做完，即算法必須能在執(zhí)行有限個(gè)步驟之后終止。
2．算法復(fù)雜度的概念和意義
一個(gè)算法質(zhì)量的好壞可從算法的時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面來衡量。算法的復(fù)雜度也是每次考試的重點(diǎn)，要注意明確有關(guān)概念。
算法的時(shí)間復(fù)雜度是指算法所需要的計(jì)算工作量；算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存    空間。
3．?dāng)?shù)據(jù)結(jié)構(gòu)的定義
數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問題：
① 數(shù)據(jù)集合中各元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。
② 在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。
③ 對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。
要注意數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的區(qū)別與聯(lián)系。
4．線性結(jié)構(gòu)與非線性結(jié)構(gòu)
根據(jù)數(shù)據(jù)結(jié)構(gòu)中各元素之間前后件關(guān)系的復(fù)雜程度，一般數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。要注意這兩種結(jié)構(gòu)的特征、它們之間的區(qū)別以及常見的有關(guān)結(jié)構(gòu)。
（1）線性結(jié)構(gòu)（或稱線性表）有以下主要特征：
① 有且只有一個(gè)根結(jié)點(diǎn)，它無前件。
② 有且只有一個(gè)終結(jié)點(diǎn)，它無后件。
③ 除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的長度，當(dāng)結(jié)點(diǎn)個(gè)數(shù)為0時(shí)，該線性表為空表。
常見的線性結(jié)構(gòu)有：線性表、棧、隊(duì)列等。
（2）如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)，常見的非線性結(jié)構(gòu)有：樹、二叉樹、圖等。
5．線性表的順序存儲(chǔ)結(jié)構(gòu)（順序表）及其插入與刪除運(yùn)算
線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，又可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)。要注意掌握二者在存儲(chǔ)數(shù)據(jù)方面的方式與特點(diǎn)。
（1）線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)
① 線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的。
② 線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。
由此可見，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面。
（2）線性表在順序存儲(chǔ)結(jié)構(gòu)下的插入與刪除運(yùn)算
線性表在順序存儲(chǔ)結(jié)構(gòu)下，若在第i（1?i?n，n為線性表中元素的個(gè)數(shù)）個(gè)位置上插入一個(gè)新元素，則首先從最后一個(gè)（即第n個(gè)）元素開始，直到第i個(gè)元素之間共有n–i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第i個(gè)位置就被空出，然后將新元素插入到第i個(gè)位置。插入結(jié)束后，線性表的長度增1。
顯然，在最好的情況下，插入位置在線性表的末尾進(jìn)行，即在第n個(gè)元素之后插入運(yùn)算，此時(shí)，不需要移動(dòng)表中的元素。而在最壞的情況下，插入位置在第1個(gè)元素上，此時(shí)需要移動(dòng)表中所有的元素。在平均情況下，要在線性表中插入一個(gè)新元素，需要移動(dòng)表中一半的元素。
同理，線性表在順序存儲(chǔ)結(jié)構(gòu)下的刪除運(yùn)算，也需要移動(dòng)表中的元素，只不過是向前移動(dòng)，在最好的情況下，刪除運(yùn)算在線性表的末尾進(jìn)行，即刪除第n個(gè)元素，此時(shí)，不需要移動(dòng)表中的元素。而在最壞的情況下，刪除位置在第1個(gè)元素上，此時(shí)需要移動(dòng)表中所有的元素。在平均情況下，要在線性表中刪除一個(gè)元素，需要移動(dòng)表中一半的元素。
線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，以及在順序存儲(chǔ)結(jié)構(gòu)下插入與刪除運(yùn)算的效率是考試的重點(diǎn)。