没有合适的资源?快使用搜索试试~ 我知道了~
资源详情
资源评论
资源推荐
数据结构 课程重难点分析及考试方向预判
本文档以课程复习纲要为蓝本,进行重难点分析及相关考试方向
预判,其中☆为一级要求,□为二级要求,△为三级要求,单独出题
以[S]表示,混合出题以[M]表示,所有页码标注均为英文课本。
Chapter 0 引论(仅作提纲使用)
a) 数据结构的表示
二维矩阵、栈、队列
逻辑表示
数组、单链表、双链表
存储表示
b) 数据逻辑结构的分类
一位数组、队列、栈
线性结构
图和树 多元关系 递归定义
动态结构
c) 数据存储结构的分类
数组
顺序存储
链表与树
链式存储
d) 要求
1 可以给出 ADT 及其相关描述
(2 可以给出 C++代码)
本书五大重点:
1 线性表(单链表)的表示和基本操作
2 矩阵(稀疏矩阵等特殊矩阵)的表示和基本操作
3 二叉树及其搜索树的的表示、定义及基本操作以及 AVL、B、B+
的扩展理解
4 堆与优先队列的表示、基本操作和相关应用
5 图论基本定义以及相关算法(最小生成树 x2、单源最短路径 x1、
全局最短路径 x1)
Chapter 1 C++
要求范围:类定义方法、递归程序定义、new 使用、友元函数
考试要求:尽量使用 C++进行描述与实现
重难点分析:
模板类、引用声明、const 的使用(包括引用的 const 定义、函数返回
const 的定义)
考点分析:
[M□] C++面向对象的程序设计(包括模板类、引用等)
Chapter 2 程序性能评估
a) 测度分类
时间复杂度 空间复杂度
b) 时间复杂性
知道Ω(n) Ο(n) Θ(n) 的理论定义,即上界、下界、精确界;
要求:估计简单算法的时间复杂性、找出最坏与期望时间复杂性
c) 空间复杂性
了解基本存储单元关于 n 的逼近渐进函数
d) 排序要求
i. 基于比较的排序:
1. 内排序:冒泡、快速、插入、堆、归并
2. 外排序:赢者树排序
ii. 基于储存的排序:桶排序与基数排序(稳定排序)
重难点分析:
1 常见排序算法三种时间复杂性、空间复杂性以及稳定性表
注:本部分收纳后面的所有排序种类,即后面的排序重点在此一并
列出,后面即不在混合列出,方便复习。
(注:前半部分为比较排序,后半部分为非比较排序)
Name
Best
Avera
ge
Worst
Memory
Stable
Method
Other notes
Quicksor
t
on
average,
worst
case is
typica
l
in-pla
ce sort
is not
stable
;
stable
versio
ns
exist
Partitioni
ng
Quicksort is
usually done
in place with
O(log(
n
))
stack space.
Most
implementati
ons are
unstable, as
stable
in-place
partitioning
is more
complex.
Naïve
variants use
an O(
n
) space
array to
store the
partition.
Merge
sort
Depends
[
fur
ther explanation
needed
]
;
worst
case is
Yes
Merging
Highly
parallelizab
le (up to
O(log(
n
))
using the
Three
Hungarian's
Algorithm or
more
practically,
Cole's
parallel
merge sort)
for
processing
large amounts
of data.
Heapsort
No
Selection
Insertio
n sort
Yes
Insertion
O(
n
+
d
),
where
d
is the
number of
Name
Best
Avera
ge
Worst
Memory
Stable
Method
Other notes
inversions
Selectio
n sort
No
Selection
Stable with
O(n) extra
space, for
example using
lists.
[3]
Bubble
sort
Yes
Exchanging
Tiny code
size
Binary
tree sort
Yes
Insertion
When using a
self-balanci
ng binary
search tree
Tourname
nt sort
—
[4]
Selection
Name
Best
Average
Worst
Memory
Stable
N
<<
2
k
Notes
Bucket
sort
(uniform
keys)
—
Yes
No
Assumes uniform
distribution of
elements from the
domain in the
array.
[6]
Bucket
sort
(integer
keys)
—
Yes
Yes
r is the range of
numbers to be
sorted. If r =
then Avg RT =
[7]
Counting
sort
—
Yes
Yes
r is the range of
numbers to be
sorted. If r =
then Avg RT =
[6]
Name
Best
Average
Worst
Memory
Stable
N
<<
2
k
Notes
LSD Radix
Sort
—
Yes
No
[6][7]
MSD Radix
Sort
—
Yes
No
Stable version uses
an external array of
size n to hold all of
the bins
MSD Radix
Sort
—
No
No
In-Place. k / d
recursion levels, 2
d
for count array
2 Ω(n) Ο(n) Θ(n) 的理论定义,即上界、下界、精确界,并可以
对简单的程序进行时间复杂性和空间复杂性估算
考点分析:
[S☆] 排序算法的考查,题型可以涉及问答题、选择题、编程题方向,
考查范围涉及各排序算法的稳定性、时间复杂性空间复杂性的比较问
答、选择正确或者是直接完成一个排序算法的实现。
[M□] 程序或程序块的时间复杂性判定,题型涉及问答题、编程题
剩余41页未读,继续阅读
leosdu
- 粉丝: 0
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0