重庆科技学院2024年考研初试科目考试大纲《数据结构（820）》

考研专业课大纲对备考具有重要价值。大纲可以帮助考生了解考试的整体结构和考查重点，在备考过程中起到明确方向的作用。大纲所列出的考试范围和知识要点，可以帮助考生建立知识体系，明确重难点，有针对性地进行备考。同时，弄清大纲要求可以让考生事先了解复习的时间分配和备考要求，避免在备考过程中盲目浪费时间和精力。以下是重庆科技学院2024年硕士研究生招生考试《数据结构（820）》考试大纲具体内容，报考该校计算机专业相关方向的考生可以根据考试大纲备考。

重庆科技学院2024年硕士研究生初试科目考试大纲《数据结构（820）》

一、考试要求：

本课程要求掌握数据结构的基本理论知识，常用数据结构及对应的基本算法及程序实现技能。内容包括线性表、栈、队列、树、图等常见结构的逻辑结构、存储结构和对应的常用基本算法，以及查找和排序的基本概念和常用算法。了解算法的时间代价和空间代价基本概念。会分析计算机待处理数据的结构特性，以便为应用涉及到的数据选择适当的逻辑结构、存储结构，并实现相应算法。

课程考试中既测试对基本知识、基本理论的掌握程度，又测试对基本知识与基本理论的灵活运用能力。

二、考试要点：

1.绪论

（1）数据结构基本概念和术语；

（2）算法描述的方法；

（3）逻辑结构、存储结构及数据运算三方面的要领及相互关系；

（4）算法复杂度的分析方法。

2.线性表

（1）线性表的逻辑特性；

（2）两类不同的存储结构（顺序和链式存储结构）的异同；

（3）单链表、循环链表、双向链表的特点；

（4）线性表在顺序存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析；

（5）线性表在链式存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析；

（6）用时间和空间复杂度分析线性表的特点。

3.栈和队列

（1）栈和队列的基本概念；

（2）栈和队列在存储结构上的基本运算的实现；

（3）循环队列中对边界条件的处理；

（4）栈的典型应用并能编程实现。

4.串

（1）串的逻辑结构定义；

（2）串的基本运算及其实现；

（3）串的堆分配存储结构；

（4）串的模式匹配算法。

5.数组和广义表

（1）数组的逻辑结构和存储结构；

（2）数组在以行为主的存储结构中地址的计算方法；

（3）特殊矩阵的压缩存储方式及下标变换公式；

（4）稀疏矩阵压缩存储方法的特点和适用范围，三元组表示的稀疏矩阵进行矩阵运算时采用的处理方法。

6.树和二叉树

（1）树的定义和基本术语；

（2）二叉树的定义；

（3）二叉树的结构特性及相应的证明方法；

（4）二叉树的各种存储结构特点及使用范围；

（5）二叉树的各种遍历算法；

（6）线索二叉树的定义；

（7）树的存储结构；

（8）树和二叉树的转换方法；

（9）最优二叉树的特性；

（10）建立最优二叉树和实现Huffman编码的方法。

7.图

（1）图的基本概念；

（2）图的两种常用的存储结构特点及实现；

（3）图的两类遍历算法：深度优先、广度优先；

（4）图的应用：最小生成树、最短路径的算法实现。

8.查找

（1）静态查找表和动态查找表的定义；

（2）顺序查找、二分查找以及块查找的基本思想和算法实现；

（3）二叉排序树的概念及查找过程；

（4）哈希查找的基本思想、哈希函数的构造方法、处理冲突的方法；

（5）各种算法的时间性能（平均查找长度）分析。

9.排序

（1）排序的基本概念、排序算法的稳定性；

（2）冒泡排序、插入排序、选择排序、快速排序、希尔排序和堆排序的基本思想、排序过程、算法实现、时间和空间性能的比较分析结论；

（3）归并排序和基数排序的基本思想。

三、参考书目

《数据结构（C语言版）（第2版）》，人民邮电出版社，2016年，ISBN：9787115379504

原文链接：https://yjs.cqust.edu.cn/info/1072/4003.htm