計(jì)算機(jī)國二office公共基礎(chǔ)知識

1、第1章數(shù)據(jù)結(jié)構(gòu)與算法（數(shù)據(jù)結(jié)構(gòu)與算法（10121012分）分）考點(diǎn)：1.算法()2.數(shù)據(jù)結(jié)構(gòu)()3.線性表及其順序存儲結(jié)構(gòu)()4.棧和隊(duì)列()5.線性鏈表()6.樹與二叉樹()7.查找技術(shù)()8.排序技術(shù)()一、數(shù)據(jù)結(jié)構(gòu)與算法1、概念、概念算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作2、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)?線性結(jié)構(gòu)(例：一維數(shù)組、鏈表、棧、隊(duì)列、串、線性表)?非線性結(jié)構(gòu)(例：多維數(shù)

2、組、廣義表、樹、圖)3、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)(線性表線性表)?順序存儲方法：線性表中所有元素所占的存儲空間是連續(xù)的線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的?鏈接存儲方法：邏輯上相鄰的結(jié)點(diǎn)，物理上也相鄰，存儲單元可以是連續(xù)的，也可以是不連續(xù)的?計(jì)算機(jī)中有數(shù)據(jù)進(jìn)行處理時(shí)，數(shù)據(jù)的存儲結(jié)構(gòu)對程序的執(zhí)行效率有很大的關(guān)系?一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)。數(shù)組是數(shù)據(jù)的邏輯結(jié)構(gòu)，可以用多種存儲結(jié)構(gòu)來表示?線性鏈表

3、：就是指線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱鏈表4、算法的基本特征、算法的基本特征?可行性：針對實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果?確定性：算法中的每一個(gè)步驟都必須有明確的定義，不允許出現(xiàn)歧義性?有窮性：算法必須在有限時(shí)間內(nèi)做完，即必須在執(zhí)行有限個(gè)步驟之后終止，算法程序的運(yùn)行時(shí)間是有限的?擁有足夠的情報(bào)：要使算法有效必需為算法提供足夠的情報(bào)當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才最有效的；而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無效5、算法的復(fù)雜度、算

4、法的復(fù)雜度?時(shí)間復(fù)雜度：該算法執(zhí)行的時(shí)間耗費(fèi)，是指執(zhí)行算法所需要的計(jì)算工作量，即算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)?空間復(fù)雜度：該算法執(zhí)行時(shí)所耗費(fèi)的存儲空間6、順序表和鏈表的比較：、順序表和鏈表的比較：基于空間的考慮：(1)順序表的存儲空間是靜態(tài)分配的，而鏈表的存儲空間是動態(tài)分配的。(2)順序表占的存儲空間必須是連續(xù)的，而鏈表占的存儲空間可以是連續(xù)的，也可是不連續(xù)的二、棧?棧實(shí)際也是線性表，只不過是一種特殊的線性表。棧稱為“先進(jìn)后出”表

5、或“后進(jìn)先出”表，順序存儲、鏈?zhǔn)酱鎯?棧的計(jì)算：求棧中元素的個(gè)數(shù)：棧底元素—棧頂元素棧頂topABCD棧底bottom入棧出棧例：前序：ABDEGCF中序：DBGEACF后序：DGEBFCA五、排序?冒泡排序：是最簡單的一種交換類排序法。在最壞的情況下，對長度為n的線性表排序，冒泡排序需要比較的次數(shù)為n(n1)2，其時(shí)間復(fù)雜度為O(n2)?直接選擇排序：最壞情況要比較的次數(shù)為O(n2)，其時(shí)間復(fù)雜度為O(n2)?直接插入排序：最壞的情況

6、下，時(shí)間復(fù)雜度為O(n2)?快速排序：平均時(shí)間為O(nlog2n)，最壞情況下，時(shí)間效率為O(n2)?堆排序：最壞情況下，時(shí)間復(fù)雜度為O(nlog2n)各種內(nèi)部排序方法的比較排序方法最壞時(shí)間直接插入O(n2)或n(n1)2直接選擇O(n2)或n(n1)2冒泡O(n2)或n(n1)2快速O(n2)或n(n1)2堆O(nlog2n)六、查找?順序查找：即適用順序存儲結(jié)構(gòu)，又適用鏈?zhǔn)酱鎯Y(jié)構(gòu)。對長度為n的線性表進(jìn)行順序查找，在最壞情況下需要比