2020年北京交通大學(xué)數(shù)據(jù)結(jié)構(gòu)考試大綱925

925 數(shù)據(jù)結(jié)構(gòu)

1、緒論。

（1）掌握相關(guān)的基本概念，如數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類型、 抽象數(shù)據(jù)類型等；（2）掌握算法設(shè)計(jì)的原則，掌握計(jì)算語句頻度和估算算法時(shí)間復(fù)雜度和空 間復(fù)雜度的方法；（3）了解使用類 C 語言描述算法的方法。

2、線性表。

（1）掌握線性表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)；（2）掌握線性表在順序結(jié)構(gòu)和鏈 式結(jié)構(gòu)上實(shí)現(xiàn)基本操作的方法； （3）理解線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合， 會(huì)針對(duì)需求選用合適的存儲(chǔ)結(jié)構(gòu)解決實(shí)際問題；（4）了解一元多項(xiàng)式的表示方法和基本運(yùn)算 的實(shí)現(xiàn)方法。

3、棧和隊(duì)列。

（1）了解棧和隊(duì)列的特點(diǎn)；（2）掌握在兩種存儲(chǔ)結(jié)構(gòu)上棧的基本操作的 實(shí)現(xiàn)；（3）掌握棧的各種應(yīng)用，理解遞歸算法執(zhí)行過程中棧狀態(tài)的變化過程；（4）掌握循環(huán) 隊(duì)列和鏈隊(duì)列的基本運(yùn)算；（5）會(huì)應(yīng)用隊(duì)列結(jié)構(gòu)解決實(shí)際問題。

4、串。

（1）掌握串的基本運(yùn)算的定義，了解利用基本運(yùn)算來實(shí)現(xiàn)串的其它運(yùn)算的方法； （2）了解在順序存儲(chǔ)結(jié)構(gòu)和在堆存儲(chǔ)結(jié)構(gòu)以及塊鏈存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法； （3）理解 KMP 算法，掌握 NEXT 函數(shù)和改進(jìn) NEXT 函數(shù)的定義和計(jì)算。