① 計算機二級c語言主要考點
引用。。：
數據結構與演算法
1 演算法
演算法：是指解題方案的准確而完整的描述。
演算法不等於程序，也不等計算機方法，程序的編制不可能優於演算法的設計。
演算法的基本特徵：是一組嚴謹地定義運算順序的規則，每一個規則都是有效的，是明確的，此順序將在有限的次數下終止。特徵包括：
（1）可行性；
（2）確定性，演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性；
（3）有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止，包括合理的執行時間的含義；
（4）擁有足夠的情報。
演算法的基本要素：一是對數據對象的運算和操作；二是演算法的控制結構。
指令系統：一個計算機系統能執行的所有指令的集合。
基本運算和操作包括：算術運算、邏輯運算、關系運算、數據傳輸。
演算法的控制結構：順序結構、選擇結構、循環結構。
演算法基本設計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術、回溯法。
演算法復雜度：演算法時間復雜度和演算法空間復雜度。
演算法時間復雜度是指執行演算法所需要的計算工作量。
演算法空間復雜度是指執行這個演算法所需要的內存空間。
2 數據結構的基本基本概念
數據結構研究的三個方面：
（1）數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構；
（2）在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構；
（3）對各種數據結構進行的運算。
數據結構是指相互有關聯的數據元素的集合。
數據的邏輯結構包含：
（1）表示數據元素的信息；
（2）表示各數據元素之間的前後件關系。
數據的存儲結構有順序、鏈接、索引等。
線性結構條件：
（1）有且只有一個根結點；
（2）每一個結點最多有一個前件，也最多有一個後件。
非線性結構：不滿足線性結構條件的數據結構。
3 線性表及其順序存儲結構
線性表由一組數據元素構成，數據元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
在復雜線性表中，由若干項數據元素組成的數據元素稱為記錄，而由多個記錄構成的線性表又稱為文件。
非空線性表的結構特徵：
（1）且只有一個根結點a1，它無前件；
（2）有且只有一個終端結點an，它無後件；
（3）除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個後件。結點個數n稱為線性表的長度，當n=0時，稱為空表。
線性表的順序存儲結構具有以下兩個基本特點：
（1）線性表中所有元素的所佔的存儲空間是連續的；
（2）線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。
ai的存儲地址為：adr(ai)=adr(a1)+(i-1)k,，adr(a1)為第一個元素的地址，k代表每個元素占的位元組數。
順序表的運算：插入、刪除。 （詳見14--16頁）
4 棧和隊列
棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。
棧按照「先進後出」（filo）或「後進先出」（lifo）組織數據，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。
棧的基本運算：（1）插入元素稱為入棧運算；（2）刪除元素稱為退棧運算；（3）讀棧頂元素是將棧頂元素賦給一個指定的變數，此時指針無變化。
隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。rear指針指向隊尾，front指針指向隊頭。
隊列是「先進行出」（fifo）或「後進後出」（lilo）的線性表。
隊列運算包括（1）入隊運算：從隊尾插入一個元素；（2）退隊運算：從隊頭刪除一個元素。
循環隊列：s=0表示隊列空，s=1且front=rear表示隊列滿
5 線性鏈表
數據結構中的每一個結點對應於一個存儲單元，這種存儲單元稱為存儲結點，簡稱結點。
結點由兩部分組成：（1）用於存儲數據元素值，稱為數據域；（2）用於存放指針，稱為指針域，用於指向前一個或後一個結點。
2008-2-21 10:07 回復 鬥牛士 黛石Sara 2樓在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。
鏈式存儲方式即可用於表示線性結構，也可用於表示非線性結構。
線性鏈表，head稱為頭指針，head=null（或0）稱為空表，如果是兩指針：左指針（llink）指向前件結點，右指針（rlink）指向後件結點。
線性鏈表的基本運算：查找、插入、刪除。
6 樹與二叉樹
樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
二叉樹的特點：（1）非空二叉樹只有一個根結點；（2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
二叉樹的基本性質：
（1）在二叉樹的第k層上，最多有2k-1(k≥1)個結點；
（2）深度為m的二叉樹最多有2m-1個結點；
（3）度為0的結點（即葉子結點）總是比度為2的結點多一個；
（4）具有n個結點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分；
（5）具有n個結點的完全二叉樹的深度為[log2n]+1；
（6）設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從左到右）用自然數1，2，….n給結點進行編號（k=1,2….n），有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為int(k/2)；
②若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（也無右子結點）；
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
滿二叉樹是指除最後一層外，每一層上的所有結點有兩個子結點，則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。
完全二叉樹是指除最後一層外，每一層上的結點數均達到最大值，在最後一層上只缺少右邊的若干結點。
二叉樹存儲結構採用鏈式存儲結構，對於滿二叉樹與完全二叉樹可以按層序進行順序存儲。
二叉樹的遍歷：
（1）前序遍歷（dlr），首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；
（2）中序遍歷（ldr），首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；
（3）後序遍歷（lrd）首先遍歷左子樹，然後訪問遍歷右子樹，最後訪問根結點。
7 查找技術
順序查找的使用情況：
（1）線性表為無序表；
（2）表採用鏈式存儲結構。
二分法查找只適用於順序存儲的有序表，對於長度為n的有序線性表，最壞情況只需比較log2n次。
8 排序技術
排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。
交換類排序法：（1）冒泡排序法，需要比較的次數為n(n-1)/2； （2）快速排序法。
插入類排序法：（1）簡單插入排序法，最壞情況需要n(n-1)/2次比較；（2）希爾排序法，最壞情況需要o(n1.5)次比較。
選擇類排序法：（1）簡單選擇排序法,
最壞情況需要n(n-1)/2次比較；（2）堆排序法，最壞情況需要o(nlog2n)次比較。
② c++的「棧」是什麼啊
一種只能在一端進行插入和刪除操作的特殊線性表。它按照後進先出的原則存儲數據，先進入的數據被壓入棧底，最後的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最後一個數據被第一個讀出來）。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。
棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為後進先出表。
棧可以用來在函數調用的時候存儲斷點，做遞歸時要用到棧！
以上定義是在經典計算機科學中的解釋。
在計算機系統中，棧則是一個具有以上屬性的動態內存區域。程序可以將數據壓入棧中，也可以將數據從棧頂彈出。在i386機器中，棧頂由稱為esp的寄存器進行定位。壓棧的操作使得棧頂的地址減小，彈出的操作使得棧頂的地址增大。
棧在程序的運行中有著舉足輕重的作用。最重要的是棧保存了一個函數調用時所需要的維護信息，這常常稱之為堆棧幀或者活動記錄。堆棧幀一般包含如下幾方面的信息：
1．函數的返回地址和參數
2．臨時變數：包括函數的非靜態局部變數以及編譯器自動生成的其他臨時變數。
③ 1． 用c語言編寫順序存儲結構下的順序查找法和鏈式存儲結構下的順序查找法。
是啊！而且非常重要它在筆試中佔30%！！！
這是我找到的一些資料：第一章 數據結構與演算法
1.1 演算法
1、演算法是指解題方案的准確而完整的描述。換句話說，演算法是對特定問題求解步驟的一種描述。
*：演算法不等於程序，也不等於計算方法。程序的編制不可能優於演算法的設計。
2、演算法的基本特徵
（1）可行性。針對實際問題而設計的演算法，執行後能夠得到滿意的結果。
（2）確定性。每一條指令的含義明確，無二義性。並且在任何條件下，演算法只有唯一的一條執行路徑，即相同的輸入只能得出相同的輸出。
（3）有窮性。演算法必須在有限的時間內完成。有兩重含義，一是演算法中的操作步驟為有限個，二是每個步驟都能在有限時間內完成。
（4）擁有足夠的情報。演算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態，這就是演算法執行的起點或依據。因此，一個演算法執行的結果總是與輸入的初始數據有關，不同的輸入將會有不同的結果輸出。當輸入不夠或輸入錯誤時，演算法將無法執行或執行有錯。一般說來，當演算法擁有足夠的情報時，此演算法才是有效的；而當提供的情報不夠時，演算法可能無效。
*：綜上所述，所謂演算法，是一組嚴謹地定義運算順序的規則，並且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。
3、演算法復雜度主要包括時間復雜度和空間復雜度。
（1）演算法時間復雜度是指執行演算法所需要的計算工作量，可以用執行演算法的過程中所需基本運算的執行次數來度量。
（2）演算法空間復雜度是指執行這個演算法所需要的內存空間。
1.2 數據結構的基本概念
1、數據結構是指相互有關聯的數據元素的集合。
2、數據結構主要研究和討論以下三個方面的問題：
（1）數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構。
數據的邏輯結構包含：1）表示數據元素的信息；2）表示各數據元素之間的前後件關系。
（2）在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構。
數據的存儲結構有順序、鏈接、索引等。
1）順序存儲。它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構。
2）鏈接存儲。它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構。
3）索引存儲：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。
*：數據的邏輯結構反映數據元素之間的邏輯關系，數據的存儲結構（也稱數據的物理結構）是數據的邏輯結構在計算機存儲空間中的存放形式。同一種邏輯結構的數據可以採用不同的存儲結構，但影響數據處理效率。
（3）對各種數據結構進行的運算。
3、數據結構的圖形表示
一個數據結構除了用二元關系表示外，還可以直觀地用圖形表示。在數據結構的圖形表示中，對於數據集合D中的每一個數據元素用中間標有元素值的方框表示，一般稱之為數據結點，並簡稱為結點；為了進一步表示各數據元素之間的前後件關系，對於關系R中的每一個二元組，用一條有向線段從前件結點指向後件結點。
4、數據結構分為兩大類型：線性結構和非線性結構。
（1）線性結構（非空的數據結構）條件：1）有且只有一個根結點；2）每一個結點最多有一個前件，也最多有一個後件。
*：常見的線性結構有線性表、棧、隊列和線性鏈表等。
（2）非線性結構：不滿足線性結構條件的數據結構。
*：常見的非線性結構有樹、二叉樹和圖等。
1.3 線性表及其順序存儲結構
1、線性表由一組數據元素構成，數據元素的位置只取決於自己的序號，元素之間的相對位置是線性的。線性表是由n(n≥0)個數據元素組成的一個有限序列，表中的每一個數據元素，除了第一個外，有且只有一個前件，除了最後一個外，有且只有一個後件。線性表中數據元素的個數稱為線性表的長度。線性表可以為空表。
*：線性表是一種存儲結構，它的存儲方式：順序和鏈式。
2、線性表的順序存儲結構具有兩個基本特點：（1）線性表中所有元素所佔的存儲空間是連續的；（2）線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。
*：由此可以看出，在線性表的順序存儲結構中，其前後件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在後件元素的前面，可以通過計算機直接確定第i個結點的存儲地址。
3、順序表的插入、刪除運算（學吧學吧獨家稿件）
（1）順序表的插入運算：在一般情況下，要在第i（1≤i≤n）個元素之前插入一個新元素時，首先要從最後一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向後移動一個位置，移動結束後，第i個位置就被空出，然後將新元素插入到第i項。插入結束後，線性表的長度就增加了1。
*：順性表的插入運算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。
（2）順序表的刪除運算：在一般情況下，要刪除第i（1≤i≤n）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結束後，線性表的長度就減小了1。
*：進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-1）/2個元素。插入、刪除運算不方便。
1.4 棧和隊列
1、棧及其基本運算（學吧學吧獨家稿件）
棧是限定在一端進行插入與刪除運算的線性表。
在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最後被插入的元素，棧底元素總是最先被插入的元素。即棧是按照「先進後出」或「後進先出」的原則組織數據的。
棧具有記憶作用。
棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂元素是將棧頂元素賦給一個指定的變數，此時指針無變化。
棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈式棧。
2、隊列及其基本運算
隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。尾指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊頭）。
隊列是「先進先出」或「後進後出」的線性表。
隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一個元素。
循環隊列及其運算：所謂循環隊列，就是將隊列存儲空間的最後一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的後一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。
*：循環隊列中元素的個數=rear-front。
1.5 線性鏈表（學吧學吧獨家稿件）
1、線性表順序存儲的缺點（學吧學吧獨家稿件）：（1）插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數據元素時需要移動大量的數據元素；（2）線性表的順序存儲結構下，線性表的存儲空間不便於擴充；（3）線性表的順序存儲結構不便於對存儲空間的動態分配。
2、線性鏈表：線性表的鏈式存儲結構稱為線性鏈表，是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接來實現的。因此，在鏈式存儲方式中，每個結點由兩部分組成：一部分用於存放數據元素的值，稱為數據域；另一部分用於存放指針，稱為指針域，用於指向該結點的前一個或後一個結點（即前件或後件），如下圖所示：
線性鏈表分為單鏈表、雙向鏈表和循環鏈表三種類型。
在單鏈表中，每一個結點只有一個指針域，由這個指針只能找到其後件結點，而不能找到其前件結點。因此，在某些應用中，對於線性鏈表中的每個結點設置兩個指針，一個稱為左指針，指向其前件結點；另一個稱為右指針，指向其後件結點，這種鏈表稱為雙向鏈表，如下圖所示：
3、線性鏈表的基本運算
（1）在線性鏈表中包含指定元素的結點之前插入一個新元素。
*：在線性鏈表中插入元素時，不需要移動數據元素，只需要修改相關結點指針即可，也不會出現「上溢」現象（學吧學吧獨家稿件）。
（2）在線性鏈表中刪除包含指定元素的結點。
*：在線性鏈表中刪除元素時，也不需要移動數據元素，只需要修改相關結點指針即可。
（3）將兩個線性鏈表按要求合並成一個線性鏈表。
（4）將一個線性鏈表按要求進行分解。
（5）逆轉線性鏈表。
（6）復制線性鏈表。
（7）線性鏈表的排序。
（8）線性鏈表的查找。
*：線性鏈表不能隨機存取。
4、循環鏈表及其基本運算
在線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對於空表和對第一個結點的處理必須單獨考慮，使空表與非空表的運算不統一。為了克服線性鏈表的這個缺點，可以採用另一種鏈接方式，即循環鏈表。
與前面所討論的線性鏈表相比，循環鏈表具有以下兩個特點：1）在鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點，而循環鏈表的頭指針指向表頭結點；2）循環鏈表中最後一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。
下圖a是一個非空的循環鏈表，圖b是一個空的循環鏈表：
循環鏈表的優點主要體現在兩個方面：一是在循環鏈表中，只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有的結點，而線性單鏈表做不到這一點；二是由於在循環鏈表中設置了一個表頭結點，在任何情況下，循環鏈表中至少有一個結點存在，從而使空表與非空表的運算統一。
*：循環鏈表是在單鏈表的基礎上增加了一個表頭結點，其插入和刪除運算與單鏈表相同。但它可以從任一結點出發來訪問表中其他所有結點，並實現空表與非空表的運算的統一。
1.6 樹與二叉樹（學吧學吧獨家稿件）
1、樹的基本概念
樹是一種簡單的非線性結構。在樹這種數據結構中，所有數據元素之間的關系具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點。沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
（1）什麼是二叉樹
二叉樹是一種很有用的非線性結構，它具有以下兩個特點：1）非空二叉樹只有一個根結點；2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
*：根據二叉樹的概念可知，二叉樹的度可以為0（葉結點）、1（只有一棵子樹）或2（有2棵子樹）。
（2）二叉樹的基本性質（學吧學吧獨家稿件）
性質1 在二叉樹的第k層上，最多有 個結點。
性質2 深度為m的二叉樹最多有個 個結點。
性質3 在任意一棵二叉樹中，度數為0的結點（即葉子結點）總比度為2的結點多一個。性質4 具有n個結點的二叉樹，其深度至少為 ，其中 表示取 的整數部分。
3、滿二叉樹與完全二叉樹
滿二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。
完全二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。
*：根據完全二叉樹的定義可得出：度為1的結點的個數為0或1。
下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：
完全二叉樹還具有如下兩個特性：
性質5 具有n個結點的完全二叉樹深度為 。
性質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；否則該結點無右子結點。
4、二叉樹的存儲結構
在計算機中，二叉樹通常採用鏈式存儲結構。
與線性鏈表類似，用於存儲二叉樹中各元素的存儲結點也由兩部分組成：數據域和指針域。但在二叉樹中，由於每一個元素可以有兩個後件（即兩個子結點），因此，用於存儲二叉樹的存儲結點的指針域有兩個：一個用於指向該結點的左子結點的存儲地址，稱為左指針域；另一個用於指向該結點的右子結點的存儲地址，稱為右指針域。
*：一般二叉樹通常採用鏈式存儲結構，對於滿二叉樹與完全二叉樹來說，可以按層序進行順序存儲。
5、二叉樹的遍歷（學吧學吧獨家稿件）
二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種：
（1）前序遍歷（DLR）：若二叉樹為空，則結束返回。否則：首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
（2）中序遍歷（LDR）：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
（3）後序遍歷（LRD）：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。
1.7 查找技術（學吧學吧獨家稿件）
查找：根據給定的某個值，在查找表中確定一個其關鍵字等於給定值的數據元素。
查找結果：（查找成功：找到；查找不成功：沒找到。）
平均查找長度：查找過程中關鍵字和給定值比較的平均次數。
1、順序查找
基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。
在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較，最壞情況下需要比較n次。
順序查找一個具有n個元素的線性表，其平均復雜度為O（n）。
下列兩種情況下只能採用順序查找：
1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找。
2）即使是有序線性表，如果採用鏈式存儲結構，也只能用順序查找。
2、二分法查找
思想：先確定待查找記錄所在的范圍，然後逐步縮小范圍，直到找到或確認找不到該記錄為止。
前提：必須在具有順序存儲結構的有序表中進行。
查找過程：
1）若中間項（中間項mid=(n-1)/2，mid的值四捨五入取整）的值等於x，則說明已查到；
2）若x小於中間項的值，則在線性表的前半部分查找；
3）若x大於中間項的值，則在線性表的後半部分查找。
特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。
*：二分法查找只適用於順序存儲的線性表，且表中元素必須按關鍵字有序（升序）排列。對於無序線性表和線性表的鏈式存儲結構只能用順序查找。在長度為n的有序線性表中進行二分法查找，其時間復雜度為O（log2n）。
1.8 排序技術（學吧學吧獨家稿件）
排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調整為有序記錄序列的一種操作。
1、交換類排序法（方法：冒泡排序，快速排序）。
2、插入類排序法（方法：簡單插入排序，希爾排序）。
3、選擇類排序法（方法：簡單選擇排序，堆排序）。
總結：各種排序法比較：
本章應考點撥：本章內容在筆試中會出現5-6個題目，是公共基礎知識部分出題量比較多的一章，所佔分值也比較大，約10分。
④ 堆棧 在C語言中看到的,是什麼東西啊.有什麼作用啊,怎麼用
「堆棧」實際上是分為兩部分：
堆是指系統可以動態申請和釋放的一部分究竟，這部分是可以用代碼進行操作的。
棧是函數之間調度所使用的一部分空間，這部分在代碼上沒有明顯的表示。
對於堆來與，可以使用malloc、realloc語句進行申請空間，通常情況下申請得到的是堆空間中的一塊區域，而通常情況下定義的數組也會使用堆空間。通常情況下，由代碼申請得到的空間需要使用對應的代碼進行釋放，否則會造成內存泄漏。
對於棧來與，主函數在調用子函數之前，系統會自動將主函數所使用的寄存器參數等入棧，調用子函數完畢後再將參數出棧，實現了主函數和子函數之間的寄存器復用功能。
⑤ 急求計算機二級考試的試題(C語言)
05年4月全國計算機二級C語言考試試題及答案
(1)數據的存儲結構是指 D
(A)存儲在外存中的數據 (B)數據所佔的存儲空間量
(C)數據在計算機中的順序存儲方式 (D)數據的邏輯結構在計算機中的表示
(2)下列關於棧的描述中錯誤的是 B
(A)棧是先進後出的先性表
(B)棧只能順序存儲
(C)棧具有記憶作用
(D)對棧的插入和刪除操作中，不需要改變棧底指針
(3)對於長度為N的線性表,在最壞的情況下,下列各排序法所對應的比較次數中正確的是D
(A)冒泡排序為N/2 (B)冒泡排序為N
(C)快速排序為N (D)快速排序為N(N-1)/2
(4)對長度為N的線性表進行順序查找,在最壞的情況下所需要的比較次數為 C
(A)log2n (B)n/2 (C)n (D)n+1
(5)下列對於線性表的描述中正確的是 A
A)存儲空間不一定是連續,且各元素的存儲順序是任意的
B)存儲空間不一定是連續,且前件元素一定存儲在後件元素的前面
C)存儲空間必須連續,且各前件元素一定存儲在後件元素的前面
D)存儲空間必須連續,且各元素的存儲順序是任意的
(6)下列對於軟體測試的描述中正確的是 C
A)軟體測試的目的是證明程序是否正確
B)軟體測試的目的是使程序運行結果正確
C)軟體測試的目的是盡可能地多發現程序中的錯誤
D)軟體測試的目的是使程序符合結構化原則
(7)為了使模塊盡可能獨立,要求 B
(A)模塊的內聚程度要盡量高,且各模塊間的耦合程度要盡量強
(B)模塊的內聚程度要盡量高,且各模塊間的耦合程度要盡量弱
(C)模塊的內聚程度要盡量低,且各模塊間的耦合程度要盡量弱
(D)模塊的內聚程度要盡量低,且各模塊間的耦合程度要盡量強
(8)下列描述中正確的是 D
(A)程序就是軟體 (B)軟體開發不受計算機系統的限制
(C)軟體既是邏輯實體,又是物理實體 (D)軟體是程序、數據與相關文檔的集合
(9)數據獨立性是資料庫技術的重要特點之一.所謂數據獨立性是指 D
(A)數據與程序獨立存放
(B)不同的數據被存放在不同的文件中
(C)不同的數據只能被對應的應用程序所使用
(D)以上三種說法都不對
(10)用樹形結構表示實體之間聯系的模型是 C
(A)關系模型 (B)網狀模型 (C)層次模型 (D)以上三個都是
(11)演算法具有五個特性,以下選項中不屬於演算法特性的是 B
(A)有窮性 (B)簡潔性 (C)可行性 (D)確定性
(12)以下選項中可作為C語言合法常量的是 A
(A)-80. (B)-080 (C)-8e1.0 (D)-80.0e
(13)以下敘述中正確的是 C
(A)用C語言實現的演算法必須要有輸入和輸出操作
(B)用C語言實現的演算法可以沒有輸出但必須要有輸入
(C)用C程序實現的演算法可以沒有輸入但必須要有輸出
(D)用C程序實現的演算法可以既沒有輸入也沒有輸出
(14)以下不能定義為用戶標識符是 D
(A)Main (B)_0 (C)_int (D)sizeof
(15)以下選項中,不能作為合法常量的是 B
(A)1.234e04 (B)1.234e0.4 (C)1.234e+4 (D)1.234e0
(16)數字字元0的ASCII值為48,若有以下程序 C
main()
{
char a=』1』,b=』2』;
printf("%c,",b++);
printf("%d\n",b-a);
}
程序運行後的輸出結果是
(A)3,2 (B)50,2 (C)2,2 (D)2,50
(17)有以下程序 A
main()
{
int m=12,n=34;
printf("%d%d",m++,++n); printf("%d%d\n",n++,++m);
}
程序運行後的輸出結果是
(A)12353514 (B)12353513 (C)12343514 (D)12343513
(18)有以下語句:int b;char c[10];,則正確的輸入語句是 B
A)scanf("%d%s",&b,&c); B) scanf("%d%s",&b,c);
c)scanf("%d%s",b,c); D)scanf("%d%s",b,&c);
(19)有以下程序 A
main()
{
int m,n,p;
scanf("m=%dn=%dp=%d",&m,&n,&p);
printf("%d%d%d\n",m,n,p);
}
若想從鍵盤上輸入數據,使變數M中的值為123,N中的值為456,P中的值為789,則正確的輸入是
A)M=123N=456P=789 B)M=123 N=456 P=789 C)M=123,N=456,P=789 D)123 456 789
(20)有以下程序 B
main()
{
int a,b,d=25;
a=d/10%9;b=a&&(-1);
printf("%d,%d\n",a,b);
}
程序運行後的輸出結果是
A）6，1 B）2，1 C）6，0 D）2，0
(21)有以下程序 D
main()
{
int i=1,j=2,k=3;
if(i++==1&&(++j==3||k++==3))
printf("%d %d %d\n",i,j,k);
}
程序運行後的輸出結果是
(A)1 2 3 (B)2 3 4 (C)2 2 3 (D)2 3 3
(22)若整型變數a、b、c、d中的值依次為：1、4、3、2。
則條件表達式aA) 1 B)2 C)3 D)
(23)有以下程序 B
main()
{
int p[8]={11,12,13,14,15,16,17,18},i=0,j=0;
while(i++<7) if(p[i]%2) j+=p[i];
printf("%d\n",j);
}
程序運行後的輸出結果是
A)42 B)45 C)56 D)60
(24)有以下程序 C
main()
{
char a[7]="a0\0a0\0"; int i,j;
i=sizeof(a); j=strlen(a);
printf("%d %d\n",i,j);
}
程序運行後的輸出結果是
A)2 2 B)7 6 C)7 2 D)6 2
(25)以下能正確定義一維數組的選項是 B
A)int a[5]={0,1,2,3,4,5}; B)char a[]={0,1,2,3,4,5};
C)char a={』A』,』B』,』C』}; D)int a[5]="0123";
(26)有以下程序 A
int f1(int x,int y){return x>y?x:y;}
int f2(int x,int y){return x>y?y:x;}
main()
{
int a=4,b=3,c=5,d=2,e,f,g;
e=f2(f1(a,b),f1(c,d)); f=f1(f2(a,b),f2(c,d));
g=a+b+c+d-e-f;
printf("%d,%d,%d\n",e,f,g);
}
程序運行後的輸出結果是
A)4,3,7 B)3,4,7 C)5,2,7 D)2,5,7
27)已有定義:char a[]="xyz",b[]={』x』,』y』,』z』};,以下敘述中正確的是 C
A)數組a和b的長度相同 B)a數組長度小於b數組長度
C)a數組長度大於b數組長度 D)上述說法都不對
28)有以下程序 D
void f(int *x,int *y)
{
int t;
t=*x;*x=*y;*y=t;
}
main()
{
int a[8]={1,2,3,4,5,6,7,8},i,*p,*q;
p=a;q=&a[7];
while(p{f(p,q);p++;q--;}
for(i=0;i<8;i++)printf("%d,",a[i]);
}
程序運行後的輸出結果是
A)8,2,3,4,5,6,7,1, B)5,6,7,8,1,2,3,4,
C)1,2,3,4,5,6,7,8, D)8,7,6,5,4,3,2,1,
29)有以下程序 D
main()
{
int a[3][3],*p,i;
p=&a[0][0];
for(i=0;i<9;i++)p[i]=i;
for(i=0;i<3;i++)printf("%d",a[1][i]);
}
程序運行後的輸出結果是
A)0 1 2 B)1 2 3 C)2 3 4 D)3 4 5
(30)以下敘述中錯誤的是 A
A)對於double類型數組,不可以直接用數組名對數組進行整體輸入或輸出
B)數組名代表的是數組所佔存儲區的首地址,其值不可改變
C)當程序執行中,數組元素的下標超出所定義的下標范圍時,系統將給出"下標越界"的出錯信息
D)可以通過賦初值的方式確定數組元素的個數
(31)有以下程序 C
#define N 20
fun(int a[],int n,int m)
{int i,j;
for(i=m;i>=n;i--)a[i+1]=a[i];
}
main()
{
int i,a[N]={1,2,3,4,5,6,7,8,9,10};
fun(a,2,9);
for(i=0;i<5;i++)printf("%d",a[i]);
}
程序運行後的輸出結果是
A)10234 B)12344 C)12334 D)12234
32)有以下程序 B
main()
{
int a[3][2]={0},(*ptr)[2],i,j;
for(i=0;i<2;i++)
{ptr=a+i;scanf("%d",ptr);ptr++;}
for(i=0;i<3;i++)
{for(j=0;j<2;j++)printf("-",a[i][j]);
printf("\n");
}
}
若運行時輸入:1 2 3<回車>,則輸出結果是
A)產生錯誤信息 B)1 0 C)1 2 D)1 0
2 0 3 0 2 0
0 0 0 0 3 0
33)有以下程序 B
prt(int *m,int n)
{int i;
for(i=0;i)
main()
{
int a[]={1,2,3,4,5},i;
prt(a,5);
for(i=0;i<5;i++)
printf("%d,",a[i]);
}
程序運行後的輸出結果是
A}1,2,3,4,5, B}2,3,4,5,6, C}3,4,5,6,7, D}2,3,4,5,1,
34)有以下程序 A
main()
{int a[]={1,2,3,4,5,6,7,8,9,0},*p;
for(p=a;p}
程序運行後的輸出結果是
A)1,2,3,4,5,6,7,8,9,0, B)2,3,4,5,6,7,8,9,10,1,
C)0,1,2,3,4,5,6,7,8,9, D)1,1,1,1,1,1,1,1,1,1,
35)有以下程序 D
#define P 3
void F(int x){return(P*x*x);}
main()
{printf("%d\n",F(3+5));}
程序運行後的輸出結果是
A)192 B)29 C)25 D)編譯出錯
36)有以下程序 C
main()
{int c=35;printf("%d\n",c&c);}
程序運行後的輸出結果是
A)0 B)70 C)35 D)1
37)以下敘述中正確的是 D
A)預處理命令行必須位於源文件的開頭
B)在源文件的一行上可以有多條預處理命令
C)宏名必須用大寫字母表示
D)宏替換不佔用程序的運行時間
38)若有以下說明和定義 C
union dt
{int a;char b;double c;}data;
以下敘述中錯誤的是
A)data的每個成員起始地址都相同
B)變數data所佔的內存位元組數與成員c所佔位元組數相等
C)程序段:data.a=5;printf("%f\n",data.c);輸出結果為5.000000
D)data可以作為函數的實參
39)以下語句或語句組中,能正確進行字元串賦值的是 C
A)char *sp;*sp="right!"; B)char s[10];s="right!";
C)char s[10];*s="right!"; D)char *sp="right!";
40)設有如下說明 C
typedef struct ST
{long a;int b;char c[2];}NEW;
則下面敘述中正確的是
A)以上的說明形式非法 B)ST是一個結構體類型
C)NEW是一個結構體類型 D)NEW是一個結構體變數
41)有以下程序 B
main()
{int a=1,b;
for(b=1;b<=10;b++)
{if(a>=8)break;
if(a%2==1){a+=5;continue;}
a-=3;
}
printf("%d\n",b);
}
程序運行後的輸出結果是
A) 3 B) 4 C)5 D) 6
42)有以下程序 A
main()
{char s[]="159",*p;
p=s;
printf("%c",*p++);printf("%c",*p++);
}
程序運行後的輸出結果是
A)15 B)16 C)12 D)59
43)有以下函數 D
fun(char *a,char *b)
{while((*a!=』\0』)&&(*b!=』\0』)&&(*a==*b))
{a++;b++;}
return(*a-*b);
}
該函數的功能是
A)計算a和b所指字元串的長度之差
B)將b所指字元串連接到a所指字元串中
C)將b所指字元串連接到a所指字元串後面
D)比較a和b所指字元串的大小
44)有以下程序 B
main()
{int num[4][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}},i,j;
for(i=0;i<4;i++)
{for(j=0;j<=i;j++)printf("L",』 』);
for(j=_____;j<4;j++)printf("M",num[i][j]);
printf("\n");
}
}
若要按以下形式輸出數組右上半三角
1 2 3 4
6 7 8
11 12
16
則在程序下劃線處應填入的是
A)i-1 B)i C)i+1 D)4-i
45)有以下程序 D
point(char *p){p+=3;}
main()
{char b[4]={』a』,』b』,』c』,』d』},*p=b;
point(p);printf("%c\n",*p);
}
程序運行後的輸出結果是
A)a B)b C)c D)d
46)程序中若有如下說明和定義語句 A
char fun(char *);
main()
{
char *s="one",a[5]={0},(*f1)()=fun,ch;
......
}
以下選項中對函數fun的正確調用語句是
A)(*f1)(a); B)*f1(*s); C)fun(&a); D)ch=*f1(s);
47)有以下結構體說明和變數定義,如圖所示,
指針p、q、r分別指向此鏈表中的三個連續結點。
struct node
{int data;struct node *next;}*p,*q,*r;
現要將Q所指結點從鏈表中刪除，同時要保持鏈表的連續，
以下不能完成指定操作的語句是 D
A)P->next=q->next; B)p->next=p->next->next;
c)p->next=r; D)p=q->next;
48)以下對結構體類型變數td的定義中,錯誤的是 C
A)typedef struct aa B)struct aa C)struct D)struct
{int n; {int n; {int n; {int n;
float m; float m; float m; float m;
}AA; }td; }aa; }td;
AA td; struct aa td; struct aa td;
49)以下與函數fseek(fp,0L,SEEK_SET)有相同作用的是 D
A)feof(fp) B)ftell(fp) C)fgetc(fp) D)rewind(fp)
50)有以下程序 B
#include
void WriteStr(char *fn,char *str)
{FILE *fp;
fp=fopen(fn,"w");fputs(str,fp);fclose(fp);
}
main()
{
WriteStr("t1.dat","start");
WriteStr("t1.dat","end");
}
程序運行後,文件t1.dat中的內容是
A)start B)end C)startend D)endrt
1.某二叉樹中度為2的結點有18個，則該二叉樹中有______個葉子結點。
答案:19
2.在面向對象方法中,類的實例稱為____.
答案:對象
3.診斷和改正程序中錯誤的工作通常稱為______.
答案:調試
4.在關系資料庫中,把數據表示成二維表,每一個二維表稱為_____
答案:關系
5.問題處理方案的正確而完整的描述稱為___
答案:演算法
6.以下程序運行時若從鍵盤輸入:10 20 30<回車>.輸出結果是______
#include
main()
{
int i=0,j=0,k=0;
scanf("%d%*d%d",&i,&j,&k);printf("%d%d%d\n",i,j,k);
}
答案:10 30 0
7.以下程序運行後的輸出結果是____
#define S(x) 4*x*x+1
main()
{
int i=6,j=8;
printf("%d\n",S(i+j));
}
答案:81
*8.以下程序運行後的輸出結果是_____
main()
{int a=3,b=4,c=5,t=99;
if(b if(a printf("%d%d%d\n",a,b,c);
}
答案:4399
9.以下程序運行後的輸出結果是____
main()
{
int a,b,c;
a=10;b=20;c=(a%b<1)||(a/b>1);
printf("%d %d %d\n",a,b,c);
}
答案：10 20 0
10.以下程序運行後的輸出結果是___
main()
{char c1,c2;
for(c1=』0』,c2=』9』;c1printf("\n");
)
答案:0918273645
11.已知字元A的ASCII代碼值為65,以下程序運行時若從鍵盤輸入:B33<回車>.則
輸出結果是_____
#include
main()
{char a,b;
a=getchar();scanf("%d",&b);
a=a-』A』+』0』;b=b*2;
printf("%c %c\n",a,b);
}
答案:1 B
12.以下程序中,fun函數的功能是求3行4列二維數組每行元素中的最大值.請填空
void fun(int,int,int(*)[4],int *);
main()
{int a[3][4]={{12,41,36,28},{19,33,15,27},{3,27,19,1}},b[3],i;
fun(3,4,a,b);
for(i=0;i<3;i++)printf("M",b[i]);
printf("\n");
}
void fun(int m,int n,int ar[][4],int *bar)
{
int i,j,x;
for(i=0;i {x=ar[i][0];
for(j=0;j ________=x;
)
}
)
答案:bar[i]
13.以下程序運行後的輸出結果是______
void swap(int x,int y)
{ int t;
t=x;x=y;y=t;printf("%d %d ",x,y);
}
main()
{ int a=3,b=4;
swap(a,b);printf("%d %d\n",a,b);
}
答案:4 3 3 4
14.以下程序運行後的輸出結果是____
#include
void fun(char *s,int p,int k)
{int i;
for(i=p;i)
main()
{char s[]="abcdefg";
fun(s,3,strlen(s));puts(s);
}
答案:abcfg
17.以下程序運行後的輸出結果是______
struct NODE
{int k;
struct NODE *link;
};
main()
{ struct NODE m[5],*p=m,*q=m+4;
int i=0;
while(p!=q)
{p->k=++i;p++;
q->k=i++;q--;
}
q->k=i;
for(i=0;i<5;i++)printf("%d",m[i].k);
printf("\n");
}
答案:13431
18.以下程序中函數huiwen的功能是檢查一個字元串是否是迴文,當字元串是迴文時,
函數返回字元串:yes!,否則函數返回字元串:no!,並在主函數中輸出.所謂迴文即
正向與反向的拼寫都一樣,例如:adgda.請填空.
#include
char *huiwen(char *str)
{char *p1,*p2;int i,t=0;
p1=str;p2=______;
for(i=0;i<=strlen(str)/2;i++)
if(*p1++!=*p2--){t=1;break;}
if(____)return("yes!");
else return("no!");
}
main()
{char str[50];
printf("Input:");scanf("%s",str);
printf("%s\n",______);
}
答案:18) str+(strlen(str)-1)
19) !t
20) huiwen(str)