2019年北京師范大學(xué)986軟件基礎(chǔ)考研大綱

1、986986軟件基礎(chǔ)軟件基礎(chǔ)一、考試內(nèi)容（一）概述1、《軟件基礎(chǔ)》的考核內(nèi)容包括“數(shù)據(jù)結(jié)構(gòu)”和“數(shù)據(jù)庫”兩部分。2、考生可以參考任何覆蓋本考試大綱考核內(nèi)容的教材、參考資料等進行復(fù)習(xí)。（二）數(shù)據(jù)結(jié)構(gòu)1概述1.1基本概念和術(shù)語數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型1.2抽象數(shù)據(jù)類型搜索的表現(xiàn)與實現(xiàn)1.3算法和算法分析2線性表2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈式表示和實現(xiàn)

2、2.4一元多項式的表示及相加3棧和隊列3.1棧的定義、表示與實現(xiàn)3.2隊列的定義、表示與實現(xiàn)3.3棧和隊列的基本應(yīng)用4串4.1串的定義、表示和實現(xiàn)4.2串的基本應(yīng)用5數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表現(xiàn)和實現(xiàn)8.1靜態(tài)查找表8.1.1順序表的查找8.1.2有序表的查找8.1.3索引順序表的查找8.2哈希表8.2.1哈希表的定義8.2.2哈希函數(shù)的構(gòu)造方法8.2.3處理沖突的方法8.2.4哈希表的查找及其分析9內(nèi)部排序9.1插

3、入排序9.1.1直接插入排序9.1.2其他插入排序9.1.3希爾排序9.2快速排序9.3選擇排序9.3.1簡單選擇排序9.3.2樹形選擇排序9.3.3堆排序9.4多種內(nèi)部排序方法的比較討論（三）數(shù)據(jù)庫1數(shù)據(jù)庫系統(tǒng)簡介1.1基于文件的數(shù)據(jù)處理與數(shù)據(jù)庫1.2基本概念數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)（DBMS）、數(shù)據(jù)庫系統(tǒng)、元數(shù)據(jù)、數(shù)據(jù)模型、模式1.3DBMS的主要功能1.4數(shù)據(jù)庫系統(tǒng)的三級模式結(jié)構(gòu)1.4.1外模式、概念模式、內(nèi)模式1.4.2邏輯獨立性