/Data-Structres

浙江大学《数据结构》上课笔记 + 数据结构实现 + 课后题题解

Primary LanguageC++

Data-Structres

我的博客 :叫我皮卡丘

前言

**大学MOOC上浙大的《数据结构》广受好评,原因有二,一是基础,简单易懂,老师讲得也清楚,另一大优点就是配套的每周相应知识点的编程题了,有难有易,容易题帮助巩固知识点,难题开阔视野。

笔记加入了一些自己的想法,题解也有思路说明

课程地址:https://www.icourse163.org/course/ZJU-93001

现将笔记和题解记录如下

基本概念

基本概念

题目名称 考察知识点 难易度
最大子列和问题 时间复杂度、算法优化 简单
Maximum Subsequence Sum 时间复杂度 中等
二分查找 二分查找算法 简单

线性结构

线性表

堆栈

队列

题目名称 考察知识点 难易度
两个有序链表序列的合并 线性表 简单
一元多项式的乘法与加法运算 线性表 中等
Reversing Linked List 线性表 中等
Pop Sequence 中等

树的定义

二叉树的遍历

二叉搜索树

平衡二叉树

哈夫曼树

并查集的实现和优化

题目名称 考察知识点 难易度
树的同构 树的性质 简单
List Leaves 树的建立与遍历 简单
Tree Traversals Again 树的遍历 中等
是否同一棵二叉搜索树 BST的建立与遍历 简单
Root of AVL Tree AVL的调整 简单
Complete Binary Search Tree BST的花样(?)建立 中等
二叉搜索树的操作集 BST的操作集合 简单
堆中的路径 最小堆的建立 简单
File Transfer 并查集 中等
Huffman Codes 哈夫曼树编码 中等

图的定义

图的遍历

最短路径

最小生成树

题目名称 考察知识点 难易度
列出连通集 图的遍历 简单
Saving James Bond - Easy Version 图的遍历 简单
六度空间 图的遍历 中等
哈利·波特的考试 最短路径 简单
旅游规划 最短路径 简单
公路村村通 最小生成树 简单

排序

排序

题目名称 考察知识点 难易度
排序 用来测试排序算法 简单
Insert or Merge 插入排序、归并排序 简单
Insertion or Heap Sort 插入排序、堆排序 简单
统计工龄 桶排序 简单
PAT Judge 结构体排序 中等
Sort with Swap(0, i) 表排序 简单

散列查找

散列查找

题目名称 考察知识点 难易度
电话聊天狂人 散列查找 简单
Hashing 散列查找 简单
QQ帐户的申请与登陆 散列查找 简单
Hashing - Hard Version 散列查找、拓扑排序 中等

KMP

题目名称 考察知识点 难易度
KMP 串的模式匹配 串的匹配 中等

注:Saving James Bond - Hard Version关键活动 实在没时间做了...

完结撒花,弱弱求个 star~