C程序筆試小結

1、數(shù)據結構作為計算機的一門學科，主要研究和討論以下三個方面的問題 ：數(shù)據集合中各數(shù)據 元素之 間所固有的邏輯關系，即數(shù)據的邏輯結構；在對數(shù)據進行處理時，各數(shù)據元素在計算 機中的存儲關 系,即數(shù)據的存儲結構；對各種數(shù)據結構進行的運算。算法具有5個特性：有窮性：一個算法必須（對任何合法的輸入值）在執(zhí)行有窮步之后結束，且每一步都可在有限時間內完成，即運行時間是有限的；確定性:算法中每一條指令必須有 確切的含義，讀者理解時不會產生歧義；可行性：一個算法是可行的，即算法中描述的操作都是可以通過已經實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)；輸入:一個算法有零個或多個輸入，這些輸入取自于某個特定的對象 的集合；輸出：一

2、個算法有一個或多個輸出。算法的復雜度主要包括算法的時間復雜度和空間復雜度。所謂算法的時間復雜度是指執(zhí)行算法所需要的計算工作量，即算法執(zhí)行過程中所需要的基本運算的次數(shù) ；算法的空間復雜度一般是指執(zhí)行這個 算法所需要的內存空間。算法的復雜度主要包括時間復雜度和空間復雜度。算法的時間復雜度是指執(zhí)行算法所需要的計算工作量，可以用執(zhí)行算法過程中所需基本運算的執(zhí)行次數(shù)來度量 ；算法的空間復雜度是指 執(zhí)行這個算法 所需要的內存空間。根據各自的定義可知，算法的時間復雜度與空間復雜度并不相關。算法的執(zhí)行效率不僅與問題的規(guī)模有關，還與數(shù)據的存儲結構有關；算法的空間復雜度是指執(zhí) 行算法 所需要的內存空間；算法的有窮

3、性是指算法必須能在有限的時間內執(zhí)行完，即算法必須能在執(zhí)行有限個步驟之后終止。對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較Iog2n次，而順序查找需要比 較n 次。對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為n/2.在線性表的任何位置插入一個元素的概率相等，即概率為p=l/ （n+I），則插入一個元素時所需移動元素的平均次數(shù)為n/2o數(shù)據結構是指帶有結構的數(shù)據元素的集合。它包括數(shù)據的邏輯結構和數(shù)據的存儲結構。數(shù)據的邏輯結構是指反映數(shù)據元素之間邏輯關系的數(shù)據結構。數(shù)據的存儲結構是指數(shù)據在計算機存儲空間中的存放形式。數(shù)據的邏輯結構有線性結構和非線性結構兩大類。根據數(shù)據

4、結構中各數(shù)據元素之間前后間關系的復雜程度，一般將數(shù)據結構分為兩大類型：線 性結構 與非線性結構。如果一個非空的數(shù)據結構滿足下列兩個條件： （1）有且只有一個根結 點；（2）每 一個結點最多有一個前件，也最多有一個后件。則稱該數(shù)據結構為線性結構，又 稱線性表。所以線 性表、棧與隊列、線性鏈表都是線性結構，而樹是非線性結構數(shù)據結構概念一般包括數(shù)據的邏輯結構、存儲結構及數(shù)據上的運算集合等。數(shù)據的邏輯結構只抽象地反映數(shù)據元素之間的邏輯關系，而不管它在計算機中的存儲形式。所謂數(shù)據的邏輯結構，是指反映數(shù)據元素之間邏輯關系的數(shù)據結構。所謂數(shù)據的存儲結構，是指數(shù)據的邏輯結構在計算機存儲空間中的存放形式。與數(shù)據

5、元素本身的形式、內容、相對位置、個數(shù)有 關。邏輯結構與物理存儲無關。因此本題的正確答案為 Co 線性表可以為空表 ; 第一個元素沒有直接前 件，最后一個元素沒有直接后件 ; 線性表的定義中 , 元素的排列并沒有規(guī)定大小順序。棧是限定在一端進行插入與刪除的線性表。在棧中，允許插入與刪除的一端稱為棧頂，而不允 許插 入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，從而也是最先能被刪除 的元素; 棧底 元素總是最先被插入的元素，從而也是最后才能被刪除的元素，即棧是按照”先進后出”或”后進先出”的原則組織數(shù)據的。和線性表類似，棧也有兩種存儲方法，一是順序棧，二是鏈式棧。棧的順序存儲結構是利用一

6、組 地 址連續(xù)的存儲單元一次存儲自棧底到棧頂?shù)臄?shù)據元素，同時附設指針 top 指示棧頂元素的 位置 , 由于 棧的操作是線性表操作的特例，相對而言 , 鏈式棧的操作更易于實現(xiàn)。例1：如果進棧序列為el,e2,e3,e4,則可能的岀棧序列是e3,el,e4,e2e2,e4,e3,ele3,e4,el,e2任意順序B【解析】由棧“后進先岀”的特點可知：A）中el不可能比e2先岀，C）中el不可能比e2先岀，D）中棧 是先進后岀的，所以不可能是任意順序。通常元素進棧的操作是先移動棧頂指針，后存入元素在循環(huán)隊列中，用隊尾指針 rear指向隊列中的隊尾元素，用排頭指針 front指向排頭元素的 前一個位

7、 置，因此，從排頭指針front指向的后一個位置直至隊尾指針 rear指向的位置之間 所有的元素均為隊 列中的元素。入隊運算是指在循環(huán)隊列的隊尾加入一個新元素。這個運算有兩個基本操作： 首先將隊尾指 針進一（即rear=rear+l）,并當rear=m+l時，置rear=l;然后將新元素插入隊尾指針指向的位置。當循環(huán)隊列非空（s=l）且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算，這種情況稱為”上溢”。循環(huán)隊列是線性表的一種，循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定的。數(shù)據結構包括數(shù)據的邏輯結構和存儲 （物理）結構，其中邏輯結構分為線性結構和非線性結構 , 存儲結 構包

8、括順序結構和鏈式結構。在循環(huán)隊列中，隊尾的指針指向隊首元素，是隊列的鏈式存儲結構。數(shù)據結構分為邏輯結構與存儲結構，線性鏈表屬于存儲結構 數(shù)據的邏輯結構是指反映數(shù)據元素之間邏輯關系的數(shù)據結構 ; 數(shù)據的存儲結構是指數(shù)據的邏 輯結構在 計算機存儲空間中的存放形式。在數(shù)據的存儲結構中，不僅要存放各數(shù)據元素的信息,還需要存放各數(shù)據元素之間前后件關系的信息。儲結構。線性表的順序存儲結構和線性表的鏈式存儲結構分別是隨機存取的存儲結構、順序存取的存 線性鏈表的存儲空間不一定是連續(xù)的，且各元素的存儲順序是任意的在鏈式存儲結構中，存儲數(shù)據結構的存儲空間可以不連續(xù)，各數(shù)據結點的存儲順序與數(shù)據元素之間的邏輯關系可以

9、不一致，而數(shù)據元素之間的邏輯關系是山指針域來確定的。順序存儲結構中，數(shù)據元素存放在一組地址連續(xù)的存儲單元中，每個數(shù)據元素地址可通過公式 LOC （ai）=LOC （al）+（i-l）L 計算得到，從而實現(xiàn)了隨機存取。對于鏈式存儲結構, 要對某結點進 行存取，都得從鏈的頭指針指向的結點開始，這是一種順序存取的存儲結構。順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下： 從線性 表的第一個元素開始，依次將線性表中的元素與被查元素進行比較，若相等則表示找 到（即查找成 功）；若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線 性表中沒有要找的元 素（即查找失

10、敗）。二分法查找只適用于順序存儲的有序表。設有序線性表的長度為n,被查元素為x,則二分查找的方法如下：將 x 與線性表的中間項進行比較，若中間項的值等于 x, 則說明查到，查找結束；若 x 小 于中間項的 值，則在線性表的前半部分（即中間項以前的部分）以相同的方法進行查找；若X 大于中間項的值，則在線性表的后半部分（即中間項以后的部分）以相同的方法進行查 找。這個過程一直進行到查找 成功或子表長度為 0 （說明線性表中沒有這個元素）為止。對于長度為 n 的有序線性表，在最壞情況下，二分查找只需要比較 log2n 次，而順序查 找需要比較 n 次。順序查找是從線性表的第一個元素開始依次向后查找，

11、如果線性表中的第一個元素就是要查找的元素, 則只需要做一次比較就查找成功 ; 但如果要查找的元素是線性表中的最后一個元素 , 或者要查找元 素不在線性表中，則需要與線性表中所有元素進行比較，這是順序查找的最壞情況, 比較次數(shù)為線性表的長度。二分法查找僅適用于這樣的表 : 表中的記錄必須按關鍵字排序，其存儲結構必須是順序存儲。二分法查找只適用于順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。這是二分查找法的前提條件。二分查找法也稱為折半查找法。它的基本思想是：將 n 個元素分成個數(shù)大致相同的兩半，取 an/2 與 欲查找的x作比較，如果x

12、= an/2,則找到x,算法終止；如果x<an/2,則只要在數(shù)組a的左半部繼續(xù) 搜索x （這里假設數(shù)組元素呈升序排列）；如果 x>an/2,則只要在數(shù)組a的右半部繼續(xù)搜索x。每次 余下n/（ 2Ai）個元素待比較，當最后剩下一個時，即 n/（ 2Ai） = Io故，n=2Ai;所以i = Iog2n?例 1 ：設有一個已按各元素的值排好序的順序表(長度大于2) ,現(xiàn)分別用順序查找法和二分查找 法查找與給定值k相等的元素，比較次數(shù)分別是 s和b,在查找不成功的情況下，s和b的關系是s= bs> bs< bs> =bB【解析】二分法查找只適用于順序存儲的有序表。在此所

13、說的有序表是指線性表中的元素按值非遞減排列(即從小到大，但允許相鄰元素值相等)。設有序線性表的長度為n,被查元素為x,則二分查找的方法如下：將x與線性表的中間項進行比較，若中間項的值等于x,則說明查到，查找結束；若x小于中間項的值，則在線性表的前半部分(即中間項以前的部分)以相同的方法進行查找；若 x 大于中間項的值，則在線性表的后半部分(即中間項以后的部分)以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為 0(說明線性表中沒有這個元素) 為止。順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：從線性表的第一個元素開始，依次將線性表中的元素與被查元素進

14、行比較，若相等則表示找到(即查找成功)；若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素(即查找失敗)。山此可見，對于長度為 n 的有序線性表，在最壞情況下，二分查找只需要比較 log2n 次，而順序 查找需要比較n次。在最壞情況下，快速排序、冒泡排序和直接插入排序需要的比較次數(shù)都為n (n-l)/2,堆排序需要 的比較次數(shù)為 nlog2n排序是計算機程序設計中的一種重要操作，常見的排序方法有插入排序、交換排序和選擇排序等。假設線性表的長度為n,則在最壞情況下，冒泡排序需要的比較次數(shù)為n( n-l)/2假設線性表的長度為n,則在最壞情況下，冒泡排序要經過n/2

15、遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為 n( n-l ) /2o在最壞情況下，冒泡排序所需要的比較次數(shù)為O(n(n-l)/2) ； 簡單插入排序所需要的比較次數(shù) 為O(n(n-l)/2) ； 希爾排序所需要的比較次數(shù)為 O (M1.5) ； 堆排序所需要的比較次數(shù)為 O(nlog2n) o數(shù)據庫系統(tǒng)在其內部具有三級模式及二級映射，三級模式分別是概念級模式、內部級模式與外部級模式，二級映射則分別是概念級到內部級的映射及外部級到概念級的映射。E-R模型可用E-R圖來表示，它具有3個要素：實體(型)用矩形框表示，框內為實體名稱。 屬性 用橢圓型來表示，并用線與實體連接。屬性較

16、多時也可以將實體及其屬性單獨列表。實體間的聯(lián)系用菱形框表示。用線將菱形框與實體相連 , 并在線上標注聯(lián)系的類型。E-R模型可用E-R圖來表示，它具有3個要素：實體(型)用矩形框表示，框內為實體名稱。 屬性 用橢圓型來表示，并用線與實體連接。屬性較多時也可以將實體及其屬性單獨列表。實體間的聯(lián) 系用菱形框表示。用線將菱形框與實體相連 , 并在線上標注聯(lián)系的類型。兩個實體之間的聯(lián)系實際上是實體集間的函數(shù)關系，這種函數(shù)關系可以有下面幾種，即一對一 的聯(lián) 系、一對多 ( 或多對一 ) 的聯(lián)系和多對多的聯(lián)系 ; 概念模型便于向各種模型轉換。山于概念模型不依賴于具體的數(shù)據庫管理系統(tǒng)，因此，容易向關系模型、網

17、狀模型和層次模型等各種模 型轉換。關系數(shù)據庫邏輯設計的主要工作是將 E-R 圖轉換成指定 RDBMS 中的關系模式。首先 , 從 E-R 圖到 關系模式的轉換是比較直接的，實體與聯(lián)系都可以表不成關系 , E-R 圖中屬性也可 以轉換成關系的屬 性，實體集也可以轉換成關系。查詢過程的查詢表達式用到的關系運算有：選擇、投影、連接。 選擇：從關系模式中找出滿足給定條件的元組的操作稱為選擇。 投影：從關系模式中指定若干個屬性組成新的關系稱為投影。連接：將兩個關系模式拼接成一個更寬的關系模式，生成的新關系中包含滿足條件的元組。選擇運算：從關系模式中找出滿足給定條件的元組的操作稱為選擇。選擇運算的運算符：

18、 of(R)連接運算：將兩個關系模式拼接成一個更寬的關系模式，生成的新關系中包含滿足條件的元 組。 連接運算的運算符： RIXIS投影運算：從關系模式中指定若干個屬性組成新的關系稱為投影。投影運算的運算符： nf(R) 在關系運算中，“并的定義如下 : 設 R1 和 R2 為參加運算的兩個關系， 它們具有相同的度n,且相 對應的屬性值取自同一個域，則 R1UR2為并運算，結果仍為度等于 n的關 系，其中的元組或屬 于 R1 或屬于 R2。在關系運算中，“交”的定義如下：設R1和R2為參加運算的兩個關系，它們具有相同的度 n,且相 對應的屬性值取自同一個域，則 R1AR2 為交運算，結果仍為度等于 n 的關系，其中的元組既屬 于