GATE计算机科学与信息技术考试大纲

---

---

科目代码：CS

课程结构

课程大纲

A节：工程数学

单元1：离散数学

• 命题逻辑和一阶逻辑
  • 集合
  • 关系
  • 函数
  • 偏序
  • 格
• 群
• 图 -
  • 连通性
  • 匹配
  • 着色
• 组合学 -
  • 计数
  • 递推关系
  • 生成函数

单元2：线性代数

• 矩阵
• 行列式
• 线性方程组
• 特征值和特征向量
• LU分解

单元3：微积分

• 极限、连续性和可微性
• 最大值和最小值
• 中值定理
• 积分

单元4：概率论

• 随机变量
• 均匀分布、正态分布、指数分布、泊松分布和二项分布
• 均值、中位数、众数和标准差
• 条件概率
• 贝叶斯定理

B节：数字逻辑

• 布尔代数
• 组合电路和时序电路
• 最小化。数
• 表示和计算机算术（定点和浮点）

C节：计算机组成与结构

• 机器指令和寻址方式
• 算术逻辑单元、数据通路和控制单元
• 指令流水线
• 存储层次结构 -
  • 缓存
  • 主存和辅助存储器
  • I/O接口（中断和DMA模式）

D节：编程与数据结构

• C语言编程

• 递归

• 数组、堆栈、队列、链表、树、二叉搜索树、二叉堆、图

E节：算法

• 搜索、排序、哈希
• 渐近最坏情况时间和空间复杂度
• 算法设计技术 -
  • 贪心算法
  • 动态规划
  • 分治法
• 图搜索、最小生成树、最短路径

F节：计算理论

• 正则表达式和有限自动机
• 上下文无关文法和下推自动机
• 正则语言和上下文无关语言，泵引理
• 图灵机和不可判定性

G节：编译器设计

• 词法分析、语法分析、语法制导翻译
• 运行时环境
• 中间代码生成

H节：操作系统

• 进程、线程、进程间通信、并发和同步

• 死锁

• CPU调度

• 内存管理和虚拟内存

• 文件系统

I节：数据库

• ER模型
• 关系模型 -
  • 关系代数
  • 元组演算
  • SQL
• 完整性约束，范式
• 文件组织，索引（例如，B树和B+树）
• 事务和并发控制

J节：计算机网络

• 分层概念
• 局域网技术（以太网）
• 流控和差错控制技术，交换
• IPv4/IPv6，路由器和路由算法（距离矢量，链路状态）
• TCP/UDP和套接字，拥塞控制
• 应用层协议（DNS、SMTP、POP、FTP、HTTP）
• Wi-Fi基础知识
• 网络安全 -
  • 身份验证
  • 公钥和私钥加密基础知识
  • 数字签名和证书
  • 防火墙

下载pdf 点击此处。