【考试大纲】(计算机科学与技术学院）青岛大学2022年硕士研究生招生考试自命题科目...
硕士入学考试大纲考试科目代码及名称：910数据结构 一、考试要求1、掌握数据结构的基本概念、基本原理和基本方法。2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3、能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。
二、考试内容一、线性表(一) 线性表的定义和基本操作(二) 线性表的实现1、顺序存储2、链式存储3、线性表的应用二、栈、队列和数组(一) 栈和队列的基本概念(二) 栈和队列的顺序存储结构(三) 栈和队列的链式存储结构(四) 栈和队列的应用(五) 特殊矩阵的压缩存储三、树与二叉树(一) 树的基本概念(二) 二叉树1、二叉树的定义及其主要特征2、二叉树的顺序存储结构和链式存储结构3、二叉树的遍历4、线索二叉树的基本概念和构造(三) 树、森林1、树的存储结构2、森林与二叉树的转换3、树和森林的遍历(四) 树与二叉树的应用1、二叉排序树2、平衡二叉树3、哈夫曼(Huffman) 树和哈夫曼编码四、图(一) 图的基本概念(二) 图的存储及基本操作1、邻接矩阵法2、邻接表法3、邻接多重表、十字链表(三) 图的遍历1、深度优先搜索2、广度优先搜索(四) 图的基本应用1、最小(代价) 生成树2、最短路径3、拓扑排序4、关键路径五、查找(一) 查找的基本概念(二) 顺序查找法(三) 分块查找法(四) 折半查找法(五) B-树及其基本操作、B+树的基本概念(六) 散列(Hash) 表(七) 字符串模式匹配(八) 查找算法的分析及应用六、排序(一) 排序的基本概念(二) 插入排序1、直接插入排序2、折半插入排序(三) 冒泡排序(Bubble Sort)(四) 简单选择排序(五) 希尔排序(Shell Sort)(六) 快速排序(七) 堆排序(八) 二路归并排序(Merge Sort)(九) 基数排序(十) 各种排序算法的比较(十一) 排序算法的应用
三、试卷结构（题型分值）1. 本科目满分为150分，考试时间为180分钟。2.题型结构（1）选择题：占总分的40/150。（2）简答题: 占总分的20/150。（3）分析计算题：占总分的30/150。（4）算法分析阅读题: 占总分的30/150。（5）算法设计题：占总分的30/150。
四、参考书目《数据结构（C语言版）》，严蔚敏、吴伟民编著，清华大学出版社，2007年。
页:
[1]