考研計算機復(fù)習(xí)資料數(shù)據(jù)結(jié)構(gòu)

1、【考查目標(biāo)】11.理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)。22.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM行設(shè)計與分析。33.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進行問題求解。一、線性表大綱要求：（一）線性表的定義和基本操作（二）線性表的實現(xiàn)1.順序存儲結(jié)構(gòu)12.鏈?zhǔn)酱鎯Y(jié)構(gòu)23.線性表的應(yīng)用知識點：1深刻理解數(shù)據(jù)結(jié)構(gòu)的概念，掌握數(shù)據(jù)結(jié)構(gòu)的“三要素”：邏輯結(jié)構(gòu)、物理（存儲）結(jié)構(gòu)及在這種結(jié)構(gòu)上

2、所定義的操作“運算”。2時間復(fù)雜度和空間復(fù)雜度的定義，常用計算語句頻度來估算算法的時間復(fù)雜度。以下六種計算算法時間的多項式是最常用的。其關(guān)系為：O(1)link=p－link；p－link=sBq－link=s；s－link=pCp－link=s－link；s－link=pDp－link=s；s－link=q10.在一個長度為n的順序表的表尾插入一個新元素的漸進時間復(fù)雜度為（B）。AO（n）BO（1）CO（n2）DO（log2n）11.

3、表長為n的順序存儲的線性表，當(dāng)在任何位置上插入一個元素的概率相等時，插入一個元素所需移動元素的平均個數(shù)為（B）AnB.n2C.(n1)2D.(n1)212.循環(huán)鏈表的主要優(yōu)點是（D）A不再需要頭指針了。B已知某個結(jié)點的位置后，能很容易找到它的直接前驅(qū)結(jié)點。C在進行刪除操作后，能保證鏈表不斷開。D從表中任一結(jié)點出發(fā)都能遍歷整個鏈表。（二）應(yīng)用題1、按增長率由小至大排列以下7個函數(shù)。（2）n、（3n3）n、2100、loglog222n、l