文档库

最新最全的文档下载
当前位置:文档库 > 西安电子科技大学2008年数据结构笔记

西安电子科技大学2008年数据结构笔记

西电计算机系2008专业课笔记------数据结构

前言:

用书<数据结构> 清华大学出版社严蔚敏

范围章八不考双星号(4.3除外) 不考章一章十一章十二只考概念

算法题语法不限

参考书近年真题(选择填空少了题目趋于简单习题集要做重在线性表查找排序二叉树)

第一部分: 基本概念

一.D.S的概念

1.定义: 关系

2.三要素: a 逻辑结构(关系) b 物理存储结构(元素,关系) c 基本算法(定义在逻辑关系

上,实现在物理结构上)

3.分类: 线数图集合(以直接前驱,直接后继的关系来区分)

4.存储结构: a 顺序(用一组地址连续空间…能随即访问) 如cd机b 链式(关系是显

性表示顺序访问) 如磁带c 索引 d 散列(hash)

二.算法概念

1.定义: 解决问题方法的描述.

2.描述: 可以是自然语言,也可以是高级语言

3.性质: 有穷性确定性可行性输入输出

4.分析: 时间空间(事后统计事前估计:基本语句执行次数的数量级)

例: 1. x=n;y=0

While x>0(y+1)+(y+1);

y++;

问:时间复杂度O(n)

2. viod main()

{

int y=0;

int x=5/y

Printf(x,y);

}

分母为0 违反了可行性不是算法

O()不仅与数据规模有关,还与除态有关.如数据开始就是顺序排列的那么查找的时候的算法就可以比随即排列是快

3.判断正误

算法最终要用计算机实现F

可行性:是指算法不能有二异性F(是说确定性)

同意算法实现语言越高效率越低T