软件工程学院

重庆邮电大学2020年硕士研究生入学

《数据结构（802）》考试大纲

命题方式 招生单位自命题 科目类别 初试

满分 150

考试性质

初试

考试方式和考试时间

闭卷

试卷结构

考试内容和要求

（一）、概述

[1]熟悉数据结构相关术语的含义，掌握基本概念。

[2]掌握数据结构中逻辑结构、存储结构以及两者之间关系。

[3]了解抽象数据类型的定义和表示方法。

[4]掌握计算语句频度和估算算法时间复杂度的方法。

（二）、线性结构——线性表、栈、队列和串

[1]理解线性表的逻辑结构定义。

[2]熟悉抽象数据类型定义方式。

[3]熟练掌握线性结构的顺序和链式存储结构。

[4]掌握线性表、栈和队列的应用，理解各种线性结构之间的关系。

[5]熟悉串的逻辑结构和典型存储方式，理解串的主要运算。

[6]熟练掌握在顺序和链式存储结构上实现相关基本操作。

（三）、数组和广义表

[1]掌握数组的逻辑特征与存储方式。

[2]掌握矩阵的压缩存储方式及其特点。

[3]理解广义表的逻辑特征和存储方式。

[4]掌握广义表的基本操作。

（四）、树和二叉树

[1]熟练掌握二叉树的基本性质。

[2]熟练掌握二叉树的各种存储结构的实现，各存储结构的特点及适用范围。

[3]熟练掌握二叉树各种遍历策略的递归算法。

[4]熟练掌握基于遍历策略的二叉树操作及应用。

[5]树（森林）与二叉树的关系（存储）

[6]了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。

（五）、图

[1]掌握图的定义及其它基本概念。

[2]掌握图的存储结构——邻接矩阵、邻接表。

[3]掌握图的遍历方法——深度优先搜索、广度优先搜索。

[4]掌握最小生成树生成方法。

[5]掌握图的最短路径算法。

[6]了解拓扑排序概念，了解关键路径算法。

（六）、查找（检索）

[1]掌握静态查找表——顺序表、有序表、索引表的查找算法；理解算法复杂性的分析过程；熟悉算法特点。

[2]掌握动态查找表——二叉排序树和平衡二叉树的概念、基本操作及其实现。

[3]理解B?树的概念和特点。

[4]熟练掌握哈希查找思想、哈希冲突解决方法、哈希查找性能。

（七）、排序

[1]掌握直接插入排序、希尔排序、冒泡排序、简单选择排序的思想及实现方法；

[2]掌握快速排序、堆排序、归并排序的思想和及实现方法。

[3]掌握算法复杂度及其分析方法；熟悉算法特点及其适用场景。

（八）、文件

[1]了解与文件有关的基本概念；

[2]理解文件结构及其组织方式——顺序、索引、散列文件（HASH）。

参考书目

《数据结构（C语言版）》，严蔚敏、吴伟民，清华大学出版社。

备注

重庆邮电大学2020年硕士研究生入学

《程序设计（F021）》考试大纲

命题方式 招生单位自命题 科目类别 复试

满分 100

考试性质

复试

考试方式和考试时间

闭卷

试卷结构

读程序、改程序、算法设计、写程序及综合题

考试内容和要求

（一）、考试要求：

1.掌握结构化程序设计方法或面向对象编程技术

2.掌握程序语言的基础知识

3.掌握常用算法设计及描述方法

4.掌握程序调试方法

5.具有阅读程序和改错能力

6.具有良好的编程风格

7.用C、C++或其它语言熟练编写程序

（二）、考试内容：

1.数据类型及其操作：基本数据类型、数组、指针、结构体、链表等的定义、初始化、引用和操作

2.程序语言的三种控制结构：顺序、选择、循环

3.程序输入输出实现：程序中赋值、键盘输入和输出，通过文件进行数据存取

4.函数：函数定义、函数调用、参数传递、函数返回

5.算法描述方法：程序流程图、N‐S盒图、伪代码等

6.常用算法示例：

（1）加法器与累乘器

（2）求最大数与最小数

（3）排序（冒泡排序、选择排序等）

（4）大小写字母转换

（5）判别键盘输入字符的类别

（6）判别闰年

（7）百分制成绩与等级制成绩互相转换

（8）求两个数的最大公因数和最小公倍数

（9）求菲比拉契数列有限项

（10）统计学生成绩，包括总成绩、平均成绩、各分数段人数等

（11）验证哥德巴赫猜想

（12）用穷举法求某数段的素数、水仙花数、完全平方数等

（13）求近似数（如定积分、用牛顿迭代法或二分法或弦截法求多元方程的根） （14）求两个矩阵之和、之积

（15）统计输入字符中的单词个数

参考书目

《C语言程序设计（第三版)》，谭浩强，清华大学出版社。

《C++程序设计教程（第二版）》，钱能，清华大学出版社。

备注

《软件工程（J021）》考试大纲

命题方式 招生单位自命题 科目类别 加试 满分 100

考试性质

考试方式和考试时间

试卷结构

考试内容和要求

参考书目

《软件工程导论（第五版）》，张海藩，清华大学出版社。

备注

《数据库原理（J022）》考试大纲

命题方式 招生单位自命题 科目类别 加试 满分 100

考试性质

考试方式和考试时间

试卷结构

考试内容和要求

参考书目

《数据库系统概论（第四版）》，王珊、萨师煊，高等教育出版社。

备注