計算機公共基礎知識
2024-09-07 13:37:22
供稿：網友
1.3.1 基本數據結構與算法
1．算法的基本概念及特征
算法的概念是考試的重點，是指解題方案的準確而完整的描述，它由兩種基本要素組成：一是對數據對象的運算和操作，二是算法的控制結構。
算法具有可行性、確定性、有窮性、擁有足夠的情報等特征。其中，確定性和有窮性是考試的重點。
算法的確定性，是指算法中的每一步驟都必須有明確定義，不允許有模棱兩可的解釋，也不允許有多義性。
算法的有窮性，是指算法必須能在有限的時間內做完，即算法必須能在執行有限個步驟之后終止。
2．算法復雜度的概念和意義
一個算法質量的好壞可從算法的時間復雜度和空間復雜度兩個方面來衡量。算法的復雜度也是每次考試的重點，要注意明確有關概念。
算法的時間復雜度是指算法所需要的計算工作量；算法的空間復雜度是指執行這個算法所需要的內存 空間。
3．數據結構的定義
數據結構主要研究和討論以下三個方面的問題：
① 數據集合中各元素之間所固有的邏輯關系，即數據的邏輯結構。
② 在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構。
③ 對各種數據結構進行的運算。
要注意數據的邏輯結構與存儲結構的區別與聯系。
4．線性結構與非線性結構
根據數據結構中各元素之間前后件關系的復雜程度，一般數據結構分為兩大類型：線性結構與非線性結構。要注意這兩種結構的特征、它們之間的區別以及常見的有關結構。
（1）線性結構（或稱線性表）有以下主要特征：
① 有且只有一個根結點，它無前件。
② 有且只有一個終結點，它無后件。
③ 除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個后件。線性表中結點的個數稱為線性表的長度，當結點個數為0時，該線性表為空表。
常見的線性結構有：線性表、棧、隊列等。
（2）如果一個數據結構不是線性結構，則稱之為非線性結構，常見的非線性結構有：樹、二叉樹、圖等。
5．線性表的順序存儲結構（順序表）及其插入與刪除運算
線性表既可以采用順序存儲結構，又可以采用鏈式存儲結構進行存儲。要注意掌握二者在存儲數據方面的方式與特點。
（1）線性表的順序存儲結構的特點
① 線性表中所有元素所占的存儲空間是連續的。
② 線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。
由此可見，在線性表的順序存儲結構中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面。
（2）線性表在順序存儲結構下的插入與刪除運算
線性表在順序存儲結構下，若在第i（1?i?n，n為線性表中元素的個數）個位置上插入一個新元素，則首先從最后一個（即第n個）元素開始，直到第i個元素之間共有n–i+1個元素依次向后移動一個位置，移動結束后，第i個位置就被空出，然后將新元素插入到第i個位置。插入結束后，線性表的長度增1。
顯然，在最好的情況下，插入位置在線性表的末尾進行，即在第n個元素之后插入運算，此時，不需要移動表中的元素。而在最壞的情況下，插入位置在第1個元素上，此時需要移動表中所有的元素。在平均情況下，要在線性表中插入一個新元素，需要移動表中一半的元素。
同理，線性表在順序存儲結構下的刪除運算，也需要移動表中的元素，只不過是向前移動，在最好的情況下，刪除運算在線性表的末尾進行，即刪除第n個元素，此時，不需要移動表中的元素。而在最壞的情況下，刪除位置在第1個元素上，此時需要移動表中所有的元素。在平均情況下，要在線性表中刪除一個元素，需要移動表中一半的元素。
線性表的順序存儲結構的特點，以及在順序存儲結構下插入與刪除運算的效率是考試的重點。
6．棧與隊列
要深刻領會二者的概念，以及對二者進行插入、刪除運算的特點，這是考試的重點。
棧實際上也是線性表，只不過是一種特殊的線性表。在這種特殊的線性表中，其插入與刪除運算都只在線性表的一端進行。即在這種線性表的結構中，一端是封閉的，不允許進行插入與刪除元素；另一端是開口的，允許插入與刪除元素。允許插入與刪除運算的一端稱為棧頂，而不允許插入與刪除運算的一端稱為棧底。棧頂元素總是最后被插入的元素，從而也是最先能被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。即棧是按照“先進后出”（First In Last Out，FILO）或“后進先出”（Last In First Out，LIFO）的原則組織數據的，因此，棧也被稱為“先進后出”表或“后進先出”表。由此可以看出，棧具有記憶作用。對棧?？梢赃M行進棧、出棧、讀取棧頂元素的運算。
隊列是指允許在一端進行插入運算、而在另一端進行刪除運算的線性表。允許插入運算的一端稱為隊尾，通常用一個稱為隊尾指針的指針指向隊尾元素，即隊尾指針總是指向最后被插入的元素。允許刪除運算的一端稱為隊頭，通常也用一個隊頭指針指向隊頭的元素。顯然，在隊列這種數據結構中，最先插入的元素將最先能夠被刪除，反之，最后插入的元素將最后才能被刪除。因此，隊列又稱為“先進先出”（First In First Out，FIFO）或“后進后出”（Last In Last Out，LILO）的線性表。對隊列可以進行入隊、退隊運算。
