1
2
3
4
計算機科學與技術學院碩士研究生入學考試自命題科目考試范圍
一、02102 離散數學
1 、命題邏輯的基本概念。掌握命題、聯結詞、命題公式、真值表。
2 、命題邏輯等值演算。掌握等價公式、重言式、蘊含式、等值演算、合取范式、析取 范式、主合取范式及主析取范式。
3 、命題邏輯的推理理論。掌握命題推理理論。
4 、一階邏輯基本概念。掌握謂詞、量詞、謂詞公式。
5 、一階邏輯等值演算與推理。掌握謂詞演算公式的前束范式、謂詞演算公式真值的求 解方法、謂詞推理理論。
6、集合代數。理解集合運算和集合等式證明。掌握集合的概念和表示、集合元素計數。
7 、二元關系。(1)理解關系的定義、表示和性質、等價關系與劃分;(2)掌握關系的 定義、表示和性質、偏序關系、哈斯圖與極值。
8 、函數。了解函數的定義與性質、函數的復合運算與逆函數。
9 、代數系統。掌握代數系統概念、代數系統的同態與同構映射。
10 、群與環。(1)掌握半群、獨異點、單位元、零元、群、子群、交換群、循環群、有 限群、置換群、陪集、環、整環、域的定義; (2)掌握群、子群、循環群、有限群、環、整 環、域的性質和判別方法。
11 、格與布爾代數。(1)理解格的同態的概念;(2)掌握格、子格、分配格與有補格的 定義和基本性質;(3)掌握子格、分配格和有補格的判定方法;(4)了解有限布爾代數的結 構和性質。
12 、圖的基本概念。(1)了解圖的運算，理解有向圖、無向圖、通路、回路;(2)掌握 握手定理及推論、圖的矩陣表示及應用。
13 、歐拉圖與哈密頓圖。(1)理解歐拉圖、歐拉通路和回路、哈密頓圖、哈密頓通路和 回路;(2)掌握歐拉圖的性質和判定方法、哈密頓通路和回路的充分條件與必要條件、(3) 掌握 Dijkstra 標號法求最短路徑;(4)了解中國郵遞員問題、貨郎擔問題。
14、樹。(1)掌握求最小生成樹的多種算法、根樹的行遍方法、最優二叉樹和 Huffman 算法;(2)掌握無向樹及其性質、根樹的相關概念。
15、平面圖。(1)理解平面圖的概念、平面圖的對偶圖及其應用;(2)掌握歐拉公式及 相關定理、平面圖或極大平面圖的性質和判定條件。
二、02103 程序設計基礎
1 、過程化程序設計基礎
(1)C 語言基礎、基本數據類型、基本 I/O、運算符表達式與流程控制、函數與遞歸、 參數傳遞; (2)數組和指針、字符串處理、變量及其存儲、內存管理、結構、位運算、文 件 I/O;(3)C 預處理器及運行庫、多模塊程序設計、數據抽象、流程圖、程序設計規范。
2 、面向對象程序設計基礎
(1)OOP 基本思想與方法：類、對象、屬性、方法、重載/覆蓋、封裝、繼承/派生、 多態、模板(集合與泛型)、異常處理等基礎知識。(2)OOP 程序設計語言(C# 、Java 等)、 簡單設計模式、包、類圖、程序設計規范。
3 、基礎算法與數據結構
(1)算法復雜度分析、基礎輸入輸出、簡單實現、暴力、枚舉、貪心、排序、搜索(BFS/DFS)、 二分;(2)簡單數學推理、串處理、棧、隊列、簡單樹/圖算法。
原標題：北京交通大學2025年碩士研究生招生考試自命題科目考試大綱
文章來源：https://gs.bjtu.edu.cn/media/attachments/2024/10/20241008143320_NqBgpKA.pdf
