在軟件專業技術水平考試中，軟件基礎知識試題所占的比重較大。數據結構、操作系統和數據庫系統等知識點始終是考核的重點�？忌趶土晻r應緊扣大綱，把握重點，注意新增
的和調整的知識點，如數據庫結構化查詢語言SQL、操作系統Windows95/98、上網軟件、字處理軟件Word97的使用和多媒體基本知識。
一、基本數據結構:
數據結構基本上是每年必考的知識點。數據結構是指數據和數據之間的聯系。數據結構一般包括數據的邏輯結構、存儲結構和對數據的基本操作3個方面的概念。
數據的邏輯結構反映的是數據元素之間的邏輯關系，并不依賴于計算機。數據的薦儲結構(物理結構)是數據結構在計算機存儲器中的表示。對數據的基本操作包括插入、刪除、修改、查找和排序等，這些都是各種算法的基礎。
數據的基本電位是數據元素(又稱結點、記錄等)，村個數據元素可有多種偶性，每個腦性就是數據項，即數據元素由一個或多個數據項組成。數據項是數據處理的接小單位。
初級程序員考試涉及的內容主要是:線性表 (包括數組、記錄、表、隊列和棧)的定義和存儲操作。
(1)主要知識點:
數組、記錄的定義、存儲和操作
1·數組。數組是一組具有相同類型的變量，其中各個元素共用一個數組名，但用不同的下標來訪問(引用)。一維數組描述了一個向量，維數組描述了一個矩陣。數組被存放在一片連續的內存單元中。一維數組從下標為0的元素開始連續薦放。
二維數組有按行優先和按列優先兩種行儲刀式。絕人多數編程語言，如c語言，郁是按行優先存儲的。使用數組在處理一一批同類型數據時極為力便。
2·記錄。記錄由若干個數據項組成，而各個數據項可具有各自的數據類型。能惟一標識記錄的數據項稱為主鍵。每個記錄本鼻一般是連續存儲的，而各個記錄之間應根據需要連續荷儲，或采用鏈式存儲。記錄的基本操作包括:在己有記錄的尾部插入一個新的記錄，按指定的主鍵值查找并讀出一個記錄，按指定的主鍵值刪除一個記錄，按指定的主鍵值史新一個記錄，以及對已存儲的記錄按主鍵值的升序或降序進行排列等。
線性表、隊列和棧的描述和操作
I·線性表
線性表是最常用且最簡單的一種數據結構，也稱為線性結構。一個線性表是n(n≥0)個具有相同屬性的數據元素的有限序列，其中的各個數據元素有著依次相鄰 (串接)的邏輯關系。當n=0時該線性表稱為空表，n>0時該線性表可記為:
{a1 , a2 , a3 … , an }
其中，a1稱為起點，an稱為終點。
線性表的存儲結構分為兩種:順序存儲結構和鏈式存儲結構。
順序存儲結構就是用一組地址連續的存儲單元依次存儲該線性表中的各個元素。由于表中各個元素具有相同的屬性，所以占用的存儲空間相同。因此，在內存中可以通過地址計算直接存取線性表中的任一元素。這種結構的特點是邏輯上相鄰的元素物理上也相鄰。用順序結構存儲的線性表稱作順序表。
線性表按鏈式存儲時，每個數據元素 (結點)的存儲包括數據區和指針區兩個部分。數據區存放結點本身的數據，指針區存放其后繼元素的地址 (沒有后繼元素時設置為空字符(Null).。只要知道該線性表的起始地址 (記錄在頭指針中)，表中的各個元素就可通過其間的鏈接關系逐步找到，這種鏈表稱為單向鏈表。對于單向鏈表有插入和刪除等基本操作。
在線性表中查找指定元素通常采用順序查找法和二分法。順序查找法是從第一個元素開始，逐個元素地順序查找，屬于線性查找，它比較的次數較多，效率低。二分法查找適合于按鍵值排序的存儲結構。查找時，每次取中間一個元素進行判斷，若己找到滿足條件的數據，則停止查找，否則需要決定取其前一半還是后一半數據元素繼續查找。因此，二分法不是線性查找，效率高一些，但它只適合于己經排序的順序存儲結構，而順序查找對順序存儲和鏈式存儲均適用。
2·隊列 (隊)
隊列是只能在表的一端進行插入，而在另一端進行刪除的線性表。它是一種先進先出(FIFO)的線性結構。隊列的基本操作包括創建一個隊列、入隊、出隊、讀取隊首元素、判斷隊空、清空隊列、求出當前隊列中的元素個數和撤銷一個隊列等。
隊列的存儲結構有順序存儲結構和鏈式存儲結構兩種。順序存儲的隊列中的各個元素在存儲區中連續存儲，鏈式存儲的隊列中的各個元素獨立存儲，依靠指針鏈接建立相鄰的邏輯關系。
3·棧
棧是一種特殊的線性表，這種表只能在其一端 (稱為棧頂為P)進行插入和刪除操作，因此棧的存取特征是后進先出(LIFO)。棧的基本操作包括創建一個棧、迸棧 (PuSh)、出棧 (Top)、讀取棧頂元素、判斷�？�、棧清空 (初始化)、求當前棧中元素的個數和撤銷一個棧等。
棧的存儲結構也有順序存儲結構和鏈式存儲結構兩種。順序存儲的棧中的各個元素在存儲區中連續存儲;鏈式存儲棧中各個元素獨立存儲，依靠指針鏈接建立相鄰的邏輯關系。
一個棧的最大數據容量稱為棧的深度。當進行進棧操作時，首先判斷該棧是否己滿，若棧滿時，迸棧就會出現溢出(上溢)現象。在進行退棧時，首先要判斷棧是不是為空，若為
空，那么退棧同樣出現溢出(下溢)現象。
在一個程序申需要同時使用具有相同成分類型的兩個棧時，為了避免造成存儲空間的浪費，多采用雙棧進棧操作。其操作方法是:為兩個棧共同開辟一個連續的存儲空間，讓一個棧的棧底為該存儲空間的始端，另一個棧的棧底為該存儲空間的末端，即將兩個棧的棧底安排在這個存儲空間的兩端，當元素迸棧時都從此存儲空間的兩端向中間"增長"。這種設計操作將增加內存空間的使用率"這樣，只有當這兩個棧的棧頂在該存儲空間的某處相遇時，才發生上溢現象。
延伸閱讀
文章來源于領測軟件測試網 http://www.kjueaiud.com/
