2021遼寧科技大學專業基礎綜合（含數據結構與算法、數據庫原理）專業研究生考試大綱 正文

科目代碼：813

數據結構與算法

參考書目

《數據結構（C++版）》王紅梅，胡明，王濤 清華大學出版社 2011

《計算機算法設計與分析》 王曉東編著 電子工業出版社（任意版本）

數據庫原理

參考書目 《數據庫系統概論》（第 5 版）王珊，薩師煊高等教育出版社2014


數據結構與算法考試大綱

目的：考察學生能否熟練掌握組織數據、存儲數據和處理數據的基本方法，是否具備一定的分析問題和解決問題的能力。

考試內容的基本要求、重點和難點

一般要求：

掌握數據結構和算法的基本概念方法，并能夠熟練運用于解決實際問題。這些概念包括:數據、數據元素、數據類型、抽象數據類型、數據邏輯結構、數據存儲結構、數據結構上的操作集合、算法及算法特點等。

了解和掌握算法效率分析的意義和方法。

了解抽象數據類型的概念和表示形式。

具體要求：

線性結構

一維和多維數組、單鏈表、雙鏈表、棧、隊列、字符串的性質和用途，以及然后在程序設計語言中實現相應結構存儲和運算。

非線性結構（樹和圖）

樹和圖的存儲方法和相關操作（二叉樹的前序、中序、后序遍歷，圖的深度優先、廣度優先遍歷，最小生成樹的構造，圖的最短路徑等）

算法

遞歸和分治法

回溯法及其與深度優先搜索的關系

各種常見排序算法和查找算法的效率和特點（插入排序、選擇排序、冒泡排序、快速排序、歸并排序、堆排序、線性搜索和二分搜索）

數據庫原理考試大綱

（一）緒論

內容及基本要求：掌握數據、數據庫、數據庫管理系統、數據庫系統的基本概念，了解數據管理技術的進展情況、數據庫技術產生和發展的背景，掌握數據模型的基本概念、組成要素和理解主要的數據模型，理解概念模型的基本概念及熟練掌握 E-R 方法，掌握數據庫系統的 3 級模式結構以及數據庫系統的組成。

（二）關系數據庫

內容及基本要求：掌握關系模型的三個組成部分及其各部分所包括的主要內容；掌握關系數據結構及其形式化定義；掌握關系的三類完整性約束的概念。了解關系數據庫理論產生和發展的過程，關系數據庫產品的發展及沿革。熟練掌握關系代數的各種運算，包括并、交、差、選擇、投影、連接、除及廣義笛卡兒積。

（三）關系數據庫標準語言 SQL

內容及基本要求：了解 SQL 語言發展的過程及特點，掌握 SQL 的數據定義功能，熟練掌握 SQL 對數據庫的查詢、插入、刪除、更新等操作，掌握 SQL 中視圖的操作。

（四）數據庫安全性

內容及基本要求：了解計算機以及信息安全技術標準的進展。理解最重要的存取控制技術、視圖技術和審計技術。熟練掌握存取控制機制中用戶權限的授權與回收、合法權限檢查、數據庫角色的概念和定義等。了解數據加密和統計數據庫的安全性。

（五）數據庫完整性

內容及基本要求：掌握 RDBMS 的數據庫完整性實現機制，包括實體完整性、參照完整性和用戶自己定義的完整性約束的定義機制、完整性檢查機制和違背完整性約束條件時 RDBMS 采取的預防措施。理解觸發器的概念和掌握觸發器在數據庫完整性檢查中的應用。

（六）關系數據理論

內容及基本要求：掌握數據依賴的基本概念（包括，函數依賴、平凡函數依賴、非平凡的函數依賴、部分函數依賴、完全函數依賴、傳遞函數依賴的概念；碼、候選碼、外碼的概念和定義；多值依賴的概念），掌握范式的概念、1NF、2NF、3NF、BCNF、4NF 的概念和判定方法。掌握數據依賴的 Armstrong 公理系統。

了解什么是一個"不好"的數據庫模式，什么是模式的插入異常和刪除異常。

（七）數據庫設計

內容及基本要求：了解數據庫設計的特點，掌握數據庫設計的基本步驟，掌握數據庫設計過程中數據字典的內容，掌握數據庫設計各個階段的設計目標、具體設計內容、設計描述、設計方法等。重點掌握 E-R 圖的設計及 E-R 圖向關系模型的轉換

（八）數據庫編程

內容及基本要求：掌握嵌入式 SQL、游標的概念；掌握 SQL 的過程化擴展 PL/SQL 和存儲過程的基本概念，基本結構，語句語法和用法；了解使用 ODBC 設計開發數據庫應用程序的方法。

（九）關系查詢處理和查詢優化

內容及基本要求：理解關系數據庫查詢優化的重要性和可能性；掌握查詢處理步驟；理解實現查詢操作的主要算法，主要是選擇操作和連接操作的主要算法思想；了解關系代數表達式等價變換規則；掌握關系代數表達式的優化；掌握物理優化方法。能夠把 SQL 語句轉換成查詢樹，對查詢樹進行代數優化，轉換成優化的查詢樹。

（十）數據庫恢復技術

內容及基本要求：熟練掌握事務的基本概念和事務的 ACID 性質。掌握包括數據庫運行中可能發生的故障類型，掌握數據庫恢復中最經常使用的技術—數據轉儲和登錄日志文件。掌握針對事務故障、系統故障和介質故障等不同故障的恢復策略和恢復方法。理解具有檢查點的恢復技術。理解數據庫鏡像功能。

重點：事務的基本概念和事務的 ACID 性質。數據庫故障恢復的策略和方法。

（十一）并發控制

內容及基本要求：討論數據庫并發控制的基本概念和實現技術。掌握并發操作產生的數據不一致性（丟失修改、不可重復讀、讀“臟數據”）的確切含義。掌握封鎖技術；理解活鎖和死鎖的概念；掌握并發調度的可串行性；理解沖突可串行化調度、掌握兩段鎖協議、理解封鎖的粒度、意向鎖。

遼寧科技大學

本文來源：http://m.btfokj.cn/liaoningkejidaxue/cankaoshumu_387172.html