2024年河南科技大学非全日制研究生招生考试《数据结构》考试大纲

　　一、考试基本要求及适用范围概述

　　要求考生全面、系统地掌握数据结构课程的基础理论、基本知识和基本技能，学会在应用中根据现实世界中的问题选择适当的数据逻辑结构和存储结构以及相应算法，并且培养基本的、良好的程序设计技能。

　　本考试大纲适用于河南科技大学计算机科学与技术、软件工程(学硕)、计算机技术、软件工程(专硕)和大数据技术与工程专业的硕士研究生入学考试。

　　二、考试形式

　　考试采取闭卷笔试形式，考试时间180分钟，总分150分。

　　三、考试内容

　　总体要求：

　　1.熟练掌握C语言和类C语言;

　　2.熟悉数据结构的基本概念，正确理解教材中的术语;

　　3.能够为所处理的数据选择适当的逻辑结构和存储结构;

　　4.对典型的应用问题能够熟练编写出结构清楚和正确易读的算法;

　　5.掌握算法的时间和空间复杂度分析技术。

　　具体内容：

　　1.数据结构有关的概念和术语

　　1)数据结构;

　　2)抽象数据类型;

　　3)算法、算法设计的要求、算法效率的度量。

　　2.链表、栈、队列、串

　　1)链表、静态链表(单链表、双向链表、循环链表)及相关算法;

　　2)栈及顺序栈、链栈的进栈、出栈等算法;

　　3)队及顺序队、链队的进队、出队等算法;

　　4)栈和队的应用;

　　5)串的概念、存储、运算及串的模式匹配算法。

　　3.数组和广义表

　　1)数组的定义、表示和实现;

　　2)矩阵的概念、特殊矩阵和稀疏矩阵;

　　3) 广义表的定义及存储结构。

　　4.树和二叉树

　　1)二叉树的概念、相关术语、性质及存储结构;

　　2)二叉树的遍历;

　　3)树(森林)的存储结构及遍历方法;

　　4)树、二叉树和森林之间的转换;

　　5)哈夫曼(Huffman)树的构造及应用。

　　5.图

　　1)图的概念、相关术语及存储结构;

　　2)图的遍历;

　　3)最小生成树、最短路径、拓扑排序、关键路径等。

　　6.查找

　　1)顺序查找、索引顺序表查找、二分查找;

　　2)二叉排序树的查找、插入及删除;

　　3)平衡二叉树及插入时的平衡方法;

　　4)哈希函数的构造方法、冲突处理的方法、哈希表的查找及其分析;

　　5)查找成功及失败的平均查找长度。

　　7.内部排序

　　直接插入排序、希尔排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序、基数排序的算法思想、复杂度分析、稳定性以及它们之间的比较。

　　四、主要参考教材(参考书目)

　　《数据结构》(C语言版)，严蔚敏等，清华大学出版社。