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

810

信息安全

《數(shù)據(jù)結(jié)構(gòu)》是我校信息安全專(zhuān)業(yè)的碩士研究生入學(xué)考試的一門(mén)專(zhuān)業(yè)基礎(chǔ)課程，考試對(duì)象為參加本年度全國(guó)碩士研究生入學(xué)考試的本科應(yīng)屆畢業(yè)生，或具有同等學(xué)歷的在職人員及其他人員。它的評(píng)價(jià)標(biāo)準(zhǔn)是計(jì)算機(jī)類(lèi)專(zhuān)業(yè)優(yōu)秀本科畢業(yè)生所能達(dá)到的及格或及格以上的水平，以保證被錄取者具有較扎實(shí)的算法設(shè)計(jì)基礎(chǔ)及有利于學(xué)校對(duì)考生的擇優(yōu)選拔。

 

例：《數(shù)據(jù)結(jié)構(gòu)》試卷旨在考查考生對(duì)算法基本知識(shí)、基本理論的掌握，注重考查考生靈活運(yùn)用這些基礎(chǔ)知識(shí)的能力和分析解決計(jì)算問(wèn)題的能力。

具體要求如下：

1、了解數(shù)據(jù)結(jié)構(gòu)及其分類(lèi)、數(shù)據(jù)結(jié)構(gòu)與算法的密切關(guān)系。

2、熟悉各種基本數(shù)據(jù)結(jié)構(gòu)及其操作，學(xué)會(huì)根據(jù)實(shí)際問(wèn)題要求來(lái)選擇數(shù)據(jù)結(jié)構(gòu)。

3、掌握設(shè)計(jì)算法的步驟和算法分析方法。

4、掌握數(shù)據(jù)結(jié)構(gòu)在排序和查找等常用算法中的應(yīng)用。

5、初步掌握文件組織方法和索引技術(shù)。

包括：1. 考試時(shí)間：考試時(shí)間為180分鐘，3小時(shí)。

2. 試卷滿(mǎn)分：本試卷滿(mǎn)分為150分。

3. 考試形式：閉卷、筆試。

4. 試卷題型結(jié)構(gòu)：

（1）填空題       約 20%

（2）選擇題      約 20%

（3）計(jì)算題       約 50%

（4）分析論述題   約 10%

5. 試卷內(nèi)容結(jié)構(gòu)：

（1）數(shù)據(jù)結(jié)構(gòu)基本概念及簡(jiǎn)單的算法分析 約5%

（2）線性表   約10%

（3）棧與隊(duì)列 約10%

（4）串  約10%

（5）數(shù)組與廣義表 約15%

（6）樹(shù)與二叉樹(shù)  約20%

（7）查找與排序 約 20%

（8）圖 約10%

 

1． 緒論

要求掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，理解數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間關(guān)系，清楚數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別，理解抽象數(shù)據(jù)類(lèi)型的概念，掌握算法的時(shí)間性能和空間性能分析。要點(diǎn)是分析算法的時(shí)間和空間性能。

2． 線性表

要求掌握線性表的基本概念、線性表的順序?qū)崿F(xiàn)、線性表的鏈?zhǔn)綄?shí)現(xiàn)、線性表順序?qū)崿F(xiàn)與鏈接實(shí)現(xiàn)的異同。要點(diǎn)是線性表的順序結(jié)構(gòu)與線性表的鏈?zhǔn)浇Y(jié)構(gòu)的插入、刪除和按關(guān)鍵字查找的算法實(shí)現(xiàn)。

3．棧與隊(duì)列

要求掌握棧與隊(duì)列的概念與基本操作，棧的應(yīng)用，鏈隊(duì)列與循環(huán)隊(duì)列的組織方法。要點(diǎn)是鏈隊(duì)列與循環(huán)隊(duì)列的組織方法與基本操作的實(shí)現(xiàn)。

4．串

要求掌握串的概念與串的表示和實(shí)現(xiàn)。要點(diǎn)是以堆形式實(shí)現(xiàn)的串的組織方法與基本操作的實(shí)現(xiàn)。

5．?dāng)?shù)組與廣義表

要求掌握多維數(shù)組的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)地址計(jì)算方法，矩陣的壓縮存儲(chǔ)思想，廣義表及其存儲(chǔ)結(jié)構(gòu)。要點(diǎn)是數(shù)組的存儲(chǔ)地址計(jì)算、矩陣壓縮存儲(chǔ)地址映射關(guān)系及廣義表的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)。

6．樹(shù)與二叉樹(shù)

要求掌握樹(shù)的基本概念、二叉樹(shù)的定義與性質(zhì)，二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的遍歷算法，樹(shù)和森林的基本概念，哈夫曼樹(shù)等。要點(diǎn)是二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，二叉樹(shù)的遍歷算法與哈夫曼編碼。

7．圖

要求掌握?qǐng)D的基本概念，圖的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法，圖的遍歷算法，圖的最小生成樹(shù)的概念及相關(guān)算法，拓?fù)渑判蚺c關(guān)健路徑。要點(diǎn)是圖的存儲(chǔ)結(jié)構(gòu)與圖的遍歷算法，圖的拓?fù)渑判蛩惴ā?/div>

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）、嚴(yán)蔚敏，吳偉民、清華大學(xué)出版社