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

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

2、所定義的操作“運(yùn)算”。2時(shí)間復(fù)雜度和空間復(fù)雜度的定義，常用計(jì)算語句頻度來估算算法的時(shí)間復(fù)雜度。以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(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.在一個(gè)長度為n的順序表的表尾插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（B）。AO（n）BO（1）CO（n2）DO（log2n）11.

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