查找類演算法中其基本運算操作為

1. 每種數據結構都具有插入、刪除和查找三種基本運算，這種說法對不對請詳細解答

每種數據結構都具有插入、刪除和查找三種基本運算，這種說法並不正確。

一般而言，並不是所有的數據結構都有這三種基本運算。

1. 比如多維數組，就沒有插入和刪除，可以看看，哪怕是二維數組，如果刪除其中某個元素，用行還是列來頂替，頂替後，二維數組不就出現缺口了。

2. 再比如說棧和隊列，一般並不需要查找(其實原則上說也不能查找，因為邏輯上其訪問點被嚴格限制在線性表的端點了，即使用順序存儲或者鏈式存儲可以在存儲結構中查找)

2. 二級C公共基礎知識

第一章 數據結構與演算法
經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法復雜度、數據結構的概念、棧、二叉樹的遍歷、二分法查找，讀者應對此部分進行重點學習。
詳細重點學習知識點：
1．演算法的概念、演算法時間復雜度及空間復雜度的概念
2．數據結構的定義、數據邏輯結構及物理結構的定義
3．棧的定義及其運算、線性鏈表的存儲方式
4．樹與二叉樹的概念、二叉樹的基本性質、完全二叉樹的概念、二叉樹的遍歷
5．二分查找法
6．冒泡排序法

1.1演算法
考點1 演算法的基本概念
考試鏈接：
考點1在筆試考試中考核的幾率為30%，主要是以填空題的形式出現，分值為2分，此考點為識記內容，讀者還應該了解演算法中對數據的基本運算。
計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。
1．演算法的基本特徵：可行性、確定性、有窮性、擁有足夠的情報。
2．演算法的基本要素：
（1）演算法中對數據的運算和操作
一個演算法由兩種基本要素組成：一是對數據對象的運算和操作；二是演算法的控制結構。
在一般的計算機系統中，基本的運算和操作有以下4類：算術運算、邏輯運算、關系運算和數據傳輸。
（2）演算法的控制結構：演算法中各操作之間的執行順序稱為演算法的控制結構。
描述演算法的工具通常有傳統流程圖、N-S結構化流程圖、演算法描述語言等。一個演算法一般都可以用順序、選擇、循環3種基本控制結構組合而成。
考點2 演算法復雜度
考試鏈接：
考點2在筆試考試中，是一個經常考查的內容，在筆試考試中出現的幾率為70%，主要是以選擇的形式出現，分值為2分，此考點為重點識記內容，讀者還應該識記演算法時間復雜度及空間復雜度的概念。
1.演算法的時間復雜度
演算法的時間復雜度是指執行演算法所需要的計算工作量。
同一個演算法用不同的語言實現，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率均不同。這表明使用絕對的時間單位衡量演算法的效率是不合適的。撇開這些與計算機硬體、軟體有關的因素，可以認為一個特定演算法"運行工作量"的大小，只依賴於問題的規模（通常用整數n表示），它是問題規模的函數。即
演算法的工作量=f（n）
2.演算法的空間復雜度
演算法的空間復雜度是指執行這個演算法所需要的內存空間。
一個演算法所佔用的存儲空間包括演算法程序所佔的空間、輸入的初始數據所佔的存儲空間以及演算法執行過程中所需要的額外空間。其中額外空間包括演算法程序執行過程中的工作單元以及某種數據結構所需要的附加存儲空間。如果額外空間量相對於問題規模來說是常數，則稱該演算法是原地工作的。在許多實際問題中，為了減少演算法所佔的存儲空間，通常採用壓縮存儲技術，以便盡量減少不必要的額外空間。

疑難解答：演算法的工作量用什麼來計算？
演算法的工作量用演算法所執行的基本運算次數來計算，而演算法所執行的基本運算次數是問題規模的函數，即演算法的工作量=f（n），其中n是問題的規模。
1.2數據結構的基本概念
考點3 數據結構的定義
考試鏈接：
考點3在筆試考試中，是一個經常考查的內容，在筆試考試中出現的幾率為70%，主要是以選擇的形式出現，分值為2分，此考點為識記內容，讀者還應該識記數據的邏輯結構和存儲結構的概念。
數據結構作為計算機的一門學科，主要研究和討論以下三個方面：
（1）數據集合中個數據元素之間所固有的邏輯關系，即數據的邏輯結構；
（2）在對數據元素進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構；
（3）對各種數據結構進行的運算。
數據：是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中並被計算機程序處理的符號的總稱。
數據元素：是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。
數據對象：是性質相同的數據元素的集合，是數據的一個子集。
數據的邏輯結構是對數據元素之間的邏輯關系的描述，它可以用一個數據元素的集合和定義在此集合中的若干關系來表示。數據的邏輯結構有兩個要素：一是數據元素的集合，通常記為D；二是D上的關系，它反映了數據元素之間的前後件關系，通常記為R。一個數據結構可以表示成
B=（D，R）
其中B表示數據結構。為了反映D中各數據元素之間的前後件關系，一般用二元組來表示。
數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱數據的物理結構）。
由於數據元素在計算機存儲空間中的位置關系可能與邏輯關系不同，因此，為了表示存放在計算機存儲空間中的各數據元素之間的邏輯關系（即前後件關系），在數據的存儲結構中，不僅要存放各數據元素的信息，還需要存放各數據元素之間的前後件關系的信息。
一種數據的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序、鏈接、索引等存儲結構。而採用不同的存儲結構，其數據處理的效率是不同的。因此，在進行數據處理時，選擇合適的存儲結構是很重要的。
考點4 線性結構與非線性結構
考試鏈接：
考點4在筆試考試中，雖然說不是考試經常考查的內容，但讀者還是對此考點有所了解，在筆試考試中出現的幾率為30%，主要是以填空題出現的形式出現，分值為2分，此考點為識記內容。
根據數據結構中各數據元素之間前後件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。如果一個非空的數據結構滿足下列兩個條件：
（1）有且只有一個根結點；
（2）每一個結點最多有一個前件，也最多有一個後件。
則稱該數據結構為線性結構。線性結構又稱線性表。在一個線性結構中插入或刪除任何一個結點後還應是線性結構。如果一個數據結構不是線性結構，則稱之為非線性結構。

疑難解答：空的數據結構是線性結構還是非線性結構？
一個空的數據結構究竟是屬於線性結構還是屬於非線性結構，這要根據具體情況來確定。如果對該數據結構的演算法是按線性結構的規則來處理的，則屬於線性結構；否則屬於非線性結構。
1.3棧及線性鏈表
考點5 棧及其基本運算
考試鏈接：
考點5在筆試考試中，是一個必考的內容，在筆試考試中出現的幾率為100%，主要是以選擇的形式出現，分值為2分，此考點為重點掌握內容，讀者應該掌握棧的運算 。
1．棧的基本概念
棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當表中沒有元素時稱為空棧。棧頂元素總是後被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最後才能被刪除的元素。棧是按照"先進後出"或"後進先出"的原則組織數據的。
2．棧的順序存儲及其運算
用一維數組S（1∶m）作為棧的順序存儲空間，其中m為最大容量。
在棧的順序存儲空間S（1∶m）中，S（bottom）為棧底元素，S（top）為棧頂元素。top=0表示棧空；top=m表示棧滿。
棧的基本運算有三種：入棧、退棧與讀棧頂元素。
（1）入棧運算：入棧運算是指在棧頂位置插入一個新元素。首先將棧頂指針加一（即top加1），然後將新元素插入到棧頂指針指向的位置。當棧頂指針已經指向存儲空間的最後一個位置時，說明棧空間已滿，不可能再進行入棧操作。這種情況稱為棧"上溢"錯誤。
（2）退棧運算：退棧是指取出棧頂元素並賦給一個指定的變數。首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變數，然後將棧頂指針減一（即top減1）。當棧頂指針為0時，說明棧空，不可進行退棧操作。這種情況稱為棧的"下溢"錯誤。
（3）讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變數。這個運算不刪除棧頂元素，只是將它賦給一個變數，因此棧頂指針不會改變。當棧頂指針為0時，說明棧空，讀不到棧頂元素。

小技巧：棧是按照"先進後出"或"後進先出"的原則組織數據，但是出棧方式有多種選擇，在考題中經常考查各種不同的出棧方式。
考點6 線性鏈表的基本概念
考試鏈接：
考點6在筆試考試中出現的幾率為30%，主要是以選擇的形式出現，分值為2分，此考點為識記內容。重點識記結點的組成。
在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用於存放數據元素值，稱為數據域，另一部分用於存放指針，稱為指針域。其中指針用於指向該結點的前一個或後一個結點（即前件或後件）。
鏈式存儲方式既可用於表示線性結構，也可用於表示非線性結構。
（1）線性鏈表
線性表的鏈式存儲結構稱為線性鏈表。
在某些應用中，對線性鏈表中的每個結點設置兩個指針，一個稱為左指針，用以指向其前件結點；另一個稱為右指針，用以指向其後件結點。這樣的表稱為雙向鏈表。
（2）帶鏈的棧
棧也是線性表，也可以採用鏈式存儲結構。帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結點，這種帶鏈的棧稱為可利用棧。

疑難解答：在鏈式結構中，存儲空間位置關系與邏輯關系是什麼？
在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。
1.4樹與二叉樹
考點7 樹與二叉樹及其基本性質
考試鏈接：
考點7在筆試考試中，是一個必考的內容，在筆試考試中出現的幾率為100%，主要是以選擇的形式出現，有時也有出現在填空題中，分值為2分，此考點為重點掌握內容。重點識記樹及二叉樹的性質。
誤區警示：
滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。應該注意二者的區別。
1、樹的基本概念
樹(tree）是一種簡單的非線性結構。在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點。每一個結點可以有多個後件，它們稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件個數稱為該結點的度。葉子結點的度為0。在樹中，所有結點中的最大的度稱為樹的度。
2、二叉樹及其基本性質
（1）二叉樹的定義
二叉樹是一種很有用的非線性結構，具有以下兩個特點：
①非空二叉樹只有一個根結點；
②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹和右子樹。
由以上特點可以看出，在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。另外，二叉樹中的每個結點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個結點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當一個結點既沒有左子樹也沒有右子樹時，該結點即為葉子結點。
（2）二叉樹的基本性質
二叉樹具有以下幾個性質：
性質1：在二叉樹的第k層上，最多有2k-1（k≥1）個結點；
性質2：深度為m的二叉樹最多有2m-1個結點；
性質3：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。
性質4：具有n個結點的二叉樹，其深度至少為〔log2n〕+1，其中〔log2n〕表示取log2n的整數部分。

小技巧：在二叉樹的遍歷中，無論是前序遍歷，中序遍歷還是後序遍歷，二叉樹的葉子結點的先後順序都是不變的。
3、滿二叉樹與完全二叉樹
滿二叉樹是指這樣的一種二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第k層上有2k-1個結點，且深度為m的滿二叉樹有2m－1個結點。
完全二叉樹是指這樣的二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。
對於完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現：對於任何一個結點，若其右分支下的子孫結點的最大層次為p，則其左分支下的子孫結點的最大層次或為p，或為p+1。
完全二叉樹具有以下兩個性質：
性質5:具有n個結點的完全二叉樹的深度為〔log2n〕+1。
性質6:設完全二叉樹共有n個結點。如果從根結點開始，按層次（每一層從左到右）用自然數1，2，……，n給結點進行編號，則對於編號為k（k=1，2，……，n）的結點有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為INT（k/2）。
②若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
考點8 二叉樹的遍歷
考試鏈接：
考點8在筆試考試中考核幾率為30%，分值為2分，讀者應該熟練掌握各種遍歷的具體演算法，能由兩種遍歷的結果推導另一種遍歷的結果。
在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左後右的原則下，根據訪問根結點的次序，二叉樹的遍歷分為三類：前序遍歷、中序遍歷和後序遍歷。
（1）前序遍歷：先訪問根結點、然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
（2）中序遍歷：先遍歷左子樹、然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
（3）後序遍歷：先遍歷左子樹、然後遍歷右子樹，最後訪問根結點；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。

疑難解答：樹與二叉樹的不同之處是什麼？
在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。
1.5查找技術
考點9 順序查找
考試鏈接：
考點9在筆試考試中考核幾率在30%，一般出現選擇題中，分值為2分，讀者應該具體掌握順序查找的演算法。
查找是指在一個給定的數據結構中查找某個指定的元素。從線性表的第一個元素開始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功；若線性表中所有的元素都與被查找元素進行了比較但都不相等，則表示查找失敗。
在下列兩種情況下也只能採用順序查找：
（1）如果線性表為無序表，則不管是順序存儲結構還是鏈式存儲結構，只能用順序查找。
（2）即使是有序線性表，如果採用鏈式存儲結構，也只能用順序查找。
考點10 二分法查找
考試鏈接：
考點10在筆試考試中考核幾率為30%，一般出現填空題中，分值為2分，考核比較多查找的比較次數，讀者應該具體掌握二分查找法的演算法。
二分法只適用於順序存儲的，按非遞減排列的有序表，其方法如下：
設有序線性表的長度為n，被查找的元素為i，
（1）將i與線性表的中間項進行比較；
（2）若i與中間項的值相等，則查找成功；
（3）若i小於中間項，則在線性表的前半部分以相同的方法查找；
（4）若i大於中間項，則在線性表的後半部分以相同的方法查找。

疑難解答：二分查找法適用於哪種情況？
二分查找法只適用於順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。
這個過程一直進行到查找成功或子表長度為0為止。
對於長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。
1.6排序技術
考點11 交換類排序法
考試鏈接:
考點11屬於比較難的內容，一般以選擇題的形式考查，考核幾率為30%，分值約為2分，讀者應該熟練掌握幾種排序演算法的基本過程。
冒泡排序法和快速排序法都屬於交換類排序法。
（1）冒泡排序法
首先，從表頭開始往後掃描線性表，逐次比較相鄰兩個元素的大小，若前面的元素大於後面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往後移動，最後最大者到了線性表的最後。
然後，從後到前掃描剩下的線性表，逐次比較相鄰兩個元素的大小，若後面的元素小於前面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前移動，最後最小者到了線性表的最前面。
對剩下的線性表重復上述過程，直到剩下的線性表變空為止，此時已經排好序。
在最壞的情況下，冒泡排序需要比較次數為n（n－1）/2。
（2）快速排序法
它的基本思想是：任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小於或等於基準元素的排序碼，右子序列的排序碼則大於基準元素的排序碼，然後分別對兩個子序列繼續進行排序，直至整個序列有序。

疑難解答：冒泡排序和快速排序的平均執行時間分別是多少？
冒泡排序法的平均執行時間是O（n2），而快速排序法的平均執行時間是O（nlog2n）。

1.7 例題詳解
一、選擇題
【例1】演算法的時間復雜度取決於_______。（考點2）
A）問題的規模 B）待處理的數據的初態
C）問題的難度 D）A）和B）
解析：演算法的時間復雜度不僅與問題的規模有關，在同一個問題規模下，而且與輸入數據有關。即與輸入數據所有的可能取值范圍、輸入各種數據或數據集的概率有關。
答案：D）
【例2】在數據結構中，從邏輯上可以把數據結構分成_______。（考點3）
A）內部結構和外部結構 B）線性結構和非線性結構
C）緊湊結構和非緊湊結構 D）動態結構和靜態結構
解析：邏輯結構反映數據元素之間的邏輯關系，線性結構表示數據元素之間為一對一的關系，非線性結構表示數據元素之間為一對多或者多對一的關系，所以答案為B）。
答案：B）
【例3】以下_______不是棧的基本運算。（考點5）
A）判斷棧是否為素空 B）將棧置為空棧
C）刪除棧頂元素 D）刪除棧底元素
解析：棧的基本運算有：入棧，出棧（刪除棧頂元素），初始化、置空、判斷棧是否為空或滿、提取棧頂元素等，對棧的操作都是在棧頂進行的。
答案：D）
【例4】鏈表不具備的特點是_______。（考點6）
A）可隨機訪問任意一個結點 B）插入和刪除不需要移動任何元素
C）不必事先估計存儲空間 D）所需空間與其長度成正比
解析：順序表可以隨機訪問任意一個結點，而鏈表必須從第一個數據結點出發，逐一查找每個結點。所以答案為A）。
答案：A）
【例5】已知某二叉樹的後序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是_______。（考點8）
A）ACBED B）DEABC
C）DECAB D）EDBAC
解析：後序遍歷的順序是"左子樹－右子樹－根結點"；中序遍歷順序是"左子樹－根結點－右子樹"；前序遍歷順序是"根結點－左子樹－右子樹"。根據各種遍歷演算法，不難得出前序遍歷序列是EDBAC。所以答案為D）。
答案：D）
【例6】設有一個已按各元素的值排好序的線性表（長度大於2），對給定的值k，分別用順序查找法和二分查找法查找一個與k相等的元素，比較的次數分別是s和b，在查找不成功的情況下，s和b的關系是_______。（考點9）
A）s=b B）s>b C）s<b D）s≥b
解析：對於順序查找，查找不成功時和給定關鍵字比較的次數為n+1。二分查找查找不成功的關鍵字比較次數為〔log2n〕+1。當n≥2時，顯然n+1>〔log2n〕+1。
答案：B）
【例7】在快速排序過程中，每次劃分，將被劃分的表（或子表）分成左、右兩個子表，考慮這兩個子表，下列結論一定正確的是_______。（考點11）
A）左、右兩個子表都已各自排好序
B）左邊子表中的元素都不大於右邊子表中的元素
C） 左邊子表的長度小於右邊子表的長度
D）左、右兩個子表中元素的平均值相等
解析：快速排序基本思想是：任取待排序表中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子表，左子表元素的排序碼均小於或等於基準元素的排序碼，右子表的排序碼則大於基準元素的排序碼，然後分別對兩個子表繼續進行排序，直至整個表有序。
答案：B）
二、填空題
【例1】問題處理方案的正確而完整的描述稱為_______。（考點1）
解析：計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。
答案：演算法
【例2】一個空的數據結構是按線性結構處理的，則屬於_______。（考點4）
解析：一個空的數據結構是線性結構或是非線性結構，要根據具體情況而定。如果對數據結構的運算是按線性結構來處理的，則屬於線性結構，否則屬於非線性結構。
答案：線性結構
【例3】設樹T的度為4，其中度為1、2、3和4的結點的個數分別為4、2、1、1，則T中葉子結點的個數為_______。（考點7）
解析：根據樹的性質：樹的結點數等於所有結點的度與對應的結點個數乘積之和加1。
因此樹的結點數為1×4＋2×2＋3×1＋4×1＋1＝16。葉子結點數目等於樹結點總數減去度不為0的結點數之和，即16－（4＋2＋1＋1）＝8。
答案：8
【例4】二分法查找的存儲結構僅限於_______且是有序的。（考點10）
解析：二分查找，也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制：要求表必須用順序存儲結構，且表中元素必須按關鍵字有序(升序或降序均可）。
答案：順序存儲結構
參考資料：全國計算機等級考試C公共基礎知識-一本通

3. c++ 數據結構 實驗上機題 查找演算法

二分法查找程序，可以直接運行。
#include<stdio.h>
void main()
{
int beg=0,end=0,mid=0;
int num=0;
int a[8]={1,3,5,9,11,24,56,89};
printf("請輸入要查找的數！\n");
scanf("%d",&num);
beg=0;
end=7;
while(beg<=end)
{
mid=(beg+end)/2;
if(a[mid]==num)
{
printf("第%d個元素是要找的元素\n",mid+1);
break;
}
else if(a[mid]<num)
{
beg=mid+1;
}
else
{
end=mid-1;
}
}
if(beg>end)
{
printf("查找失敗!\n");
}
}

4. 數據結構：數據結構在講演算法效率的度量中提到基本操作和原操作，想問一下什麼叫做基本操作什麼叫做原操

度量演算法的效率：時間復雜度、空間復雜度。
時間復雜度，一般情況，演算法中基本操作重復執行的次數是問題規模n的一個函數f(n)，演算法的時間度量記做T(n)=O(f(n))，他表示隨著問題規模n的增大，演算法執行時間的增長率和f(n)的增長率相同，稱做演算法的漸近時間復雜度，簡稱時間復雜度。
插入一個概念：語句的頻度指的是該語句重復執行是次數。
我們在計算時間復雜度的時候，
先要找出演算法的基本操作，並根據基本操作語句計算出其執行次數。
再找出其同數量級。。。T(n)=O(f(n)=數量級)。
例如：
[cpp] view plain
for(i=1; i<=n; ++i)
{
for(j=1; j<=n; ++j)
{
c[i][j]=0;//該步驟屬於基本操作執行次數：n的平方次
for(k=1; k<=n; ++k)
c[i][j]+=a[i][k]*b[k][j];//該步驟屬於基本操作執行次數：n的三次方次
}
}

我們可以看到，其中的基本操作語句就只有兩個，一個c[i][j]=0，一個c[i][j]+=a[i][k]*b[k][j]，可以知道前一個的執行次數為n^2，後一個的執行次數為n^3。所以T(n)=O(n^3)。
按數量級遞增排列，常見的時間復雜度有：
常數階O(1),對數階O(log2n),線性階O(n),
線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，
k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大，上訴的時間復雜度不斷增大，演算法的執行效率越低。

在pascal中比較容易理解，容易計算的方法是：看看有幾重for循環，只有一重則時間復雜度為O(n)，二重則為O(n^2)，依此類推，如果有二分則為O(logn)，二分例如快速冪、二分查找，如果一個for循環套一個二分，那麼時間復雜度則為O(nlogn)。

對於實際計算中，我們知道，對於相同的程序，對於其運行的時間，影響的因素有很多。
1.程序的演算法優劣。
2.問題的規模。
3.書寫程序的語言。
4.編譯程序產生的機器代碼在質量。
5.機器執行指令的速度。。。等等。

空間復雜度，一個程序的空間復雜度是指運行完一個程序所需內存的大小。利用程序的空間，可以對程序的運行所需要的內存多少有個預先估計。一個程序執行時除了需要存儲空間和存儲本身所使用的指令、常數、變數和輸入數據外，還需要一些對數據進行操作的工作單元和存儲一些為現實計算所需信息的輔助空間。程序執行時所需存儲空間包括以下兩部分。
（1）固定部分。這部分空間的大小與輸入/輸出的數據的個數多少、數值無關。主要包括指令空間（即代碼空間）、數據空間（常量、簡單變數）等所佔的空間。這部分屬於靜態空間。
（2）可變空間，這部分空間的主要包括動態分配的空間，以及遞歸棧所需的空間等。這部分的空間大小與演算法有關。
一個演算法所需的存儲空間用f(n)表示。
S(n)=O(f(n))
其中n為問題的規模，S(n)表示空間復雜度。

5. 線性表的基本操作，建立、查找、插入及刪除操作的演算法實現(作業,HELP)

Status SqList_Init(SqList &L)
{
L.elem = (ElemType*)malloc(InitSize*sizeof(ElemType)) ;
if(!L.elem) return error ;
L.length = 0 ;
L.ListSize=InitSize ;
return ok ;
}
Status SqList_Put(SqList &L)
{
int i ;
ElemType x ;
cout<<"請輸入線性表的元素，輸入9999表示停止輸入"<<endl ;
for(i=0 ; i<L.ListSize;i++)
{
if(L.length>=L.ListSize)
{
L.elem=(ElemType *)malloc((L.ListSize+Increse)*sizeof(ElemType)) ;
L.ListSize += Increse ;
}
cout<<"請輸入線性表的第"<<i<<"個元素" ;
cin>>x;
if(x==9999) break ;
L.elem[i] = x ;
L.length++ ;

}
cout<<"你已經成功把數據元素放入線性表"<<endl;
return ok ;
}
Status SqList_Display(SqList L)
{
int i ;
cout<<"線性表的數據元素為："<<endl ;
for(i=0 ;i<L.length ; i++)
{
cout<<L.elem[i]<<" " ;
}
cout<<endl ;
return ok ;
}
Status SqList_Search(SqList L)
{
ElemType x;
int i , Label=0 ;

cout<<"請輸入你要查找的元素"<<endl ;
cin>>x ;
for(i=0 ; i<L.length; i++)
{
if( L.elem[i]==x )
{
cout<<"你所查找的元素位於該線性表的第"<<i+1<<"個位置"<<endl ;
Label=1 ;
}

}
if(!Label) cout<<"線性表不存在你要查找的元素"<<endl ;
return ok ;
}
Status SqList_Delete(SqList &L)
{
ElemType x ;
int i , j ;
cout<<"請輸入你要刪除的元素"<<endl ;
cin>>x ;
for(i=0 ; i<L.length ; i++)
{
if(L.elem[i]==x)
{
for(j=i ; j<L.length ; j++)
L.elem[j]=L.elem[j+1] ;
i=0 ;
L.length-- ;
}
}
cout<<"在線性表中刪除了所有值為"<<x<<"的元素"<<endl ;
return ok ;
}
SqList_Clear(SqList &L)
{
L.length=0;
return ok;
}
void main()
{
SqList SqList_obj ;
SqList_Init(SqList_obj) ;
SqList_Put(SqList_obj) ;
SqList_Display(SqList_obj) ;
SqList_Search(SqList_obj) ;
SqList_Delete(SqList_obj) ;
SqList_Display(SqList_obj) ;
SqList_Clear(SqList_obj) ;

6. 數據結構中經常對數組進行的兩種基本操作是什麼

數據結構中經常對數組進行的兩種基本操作是查找和修改。

數組是存儲於一個連續存儲空間中的相同數據類型的數據元素集合，通過數組元素的下標（位置序號），就可以找到存放該數組元素的存儲地址，從而可以訪問該數組元素的值。它通常用於實現順序表，通常包括查找和修改運算。

(6)查找類演算法中其基本運算操作為擴展閱讀：

不過要注意的是，順序表是一個一維數組，而多維數組則是典型的非線性結構。另外值得說明的是，數組的特點是：

1、數組元素的數目固定，一旦定義了數組，就不再有元素的增減變化。

2、數據元素具有相同的類型。

3、數組的下標關系具有上下界的約束且下標有序。因此，數組一般不做插入和刪除操作。

7. 哈希查找演算法程序

查找演算法
問題描述：
設計一個實現順序查找、二分查找（折半查找）、二叉排序樹、哈希查找演算法的程序，並具有人機交互界面。
基本要求：
（1）設計一個菜單將實現的查找演算法的名字顯示出來，並提示用戶對查找演算法進行選擇；
（2）分別實現順序查找、二分查找（折半查找）、二叉排序樹、哈希查找；
（3）哈希函數採用除留余數發，解決沖突的方法大家任選擇一種；
（4）二叉排序樹必須實現構建、查找、插入、刪除四個基本操作；
（5）輸出各種排序的結果並進行比較。*/

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 20
typedef struct /*順序結構數據類型*/
h.length++;
h.r[ }
else
if(k<l.r[mid].key) high=mid-1;
else low=mid +1;
}
if(i!=0)
{
printf("l.r[%d].key=%d\n",i,k);
printf("查找成功\n");
}
return ht;
}
void HashSearch(RecordHash ht) /*哈希查找*/
{
int k,i;
page_title("哈希查找");
printf("請輸入要查找的關鍵字:");
scanf("%d",&k);
i=k%13;
if(ht.HashTable[i].key==k)
{
printf("ht.HashTable[%d].key=%d\n",i,k);
printf("查找成功\n");
}
else
{
i=i+1;
for(;i<MAX;i++)
if(ht.HashTable[i].key==k)
{
printf("ht.HashTable[%d].key=%d\n",i,k);
printf("查找成功\n");
break;
}
if(i==MAX) printf("查找失敗\n");
}
return_confirm();
}
void main()
{
RecordList L1,L2;
BSTNode *pt;
RecordHash ht;
int k,i;
printf("\n創建順序查找線性表,輸入0則結束輸入(可不按順序輸入)\n");
L1=creat1();
printf("\n創建二分查找線性表，輸入0則結束輸入(按遞增順序輸入)\n");
L2=creat1();
printf("\n創建二叉排序樹，輸入0則結束輸入\n");
pt=creat2();
printf("\n創建哈希表\n");
ht=creat3();
menu:page_title("請選擇查找方式，輸入0則結束輸入");
printf("順序查找請按1\n二分查找請按2\n二叉排序樹查找請按3\n哈希查找請按4\n推出請按0\n");
switch(getch())
{
case '1':
SeqSearch(L1);
break;
case '2':
Binsrch(L2);
break;
case '3':
page_title("二叉排序樹查找");
printf("請輸入要查找的關鍵字:");
scanf("%d",&k);
SearchBST(pt,k);
break;
case '4':
HashSearch(ht);
break;
case '0':
exit(0);
default :
printf("輸入錯誤，按任意鍵返回");
getch();
}
goto menu;