1.概念:

    数据:统称---------------------------------------------------------------------------qq所有的数据

    数据元素:可细分的数据整体----------------------------------------------------一个qq账号

    数据项:数据元素的一项----------------------------------------------------------一个qq账号中的一项:qq昵称

    数据结构:存在关系的数据元素的集合---------------------------------------你好友列表里的qq账号,存在关系

    数据对象:具有相同性质但不一定存在关系的数据元素的集合---------腾讯所有的qq账号,不一定有关系但性质相同

    ———————————————————————————————————————————————————

    数据类型:原子类型、结构类型

    抽象数据类型:定义逻辑结构和运算而不关心存储结构,只定义不实现

 错题:

     1.可以用以上哪个概念来定义一个完整的数据结构?

     2.循环队列和栈分别与逻辑结构还是存储结构相关?

     3.链式存储节点内的地址单元是否连续?

2.三要素

   逻辑结构:   集合、线性结构、树形结构、图状结构

   物理结构/存储结构:顺序存储、链式存储、索引存储、散列存储

   数据的运算:运算的定义(逻辑结构)和实现(存储结构)

3.算法 

     定义:对特定问题求解的一种描述,是指令的有穷序列,每条指令表示一个或多个操作

     特性:有穷性、确定性、可行性

     目标:正确性、可读性、健壮性、高效率和低存储

4.时间复杂度:最好/最坏/平均(n个时间和/n)时间复杂度

     (1)O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

     (2)i=i*2======》log2n

     (3)递归:单次时间x递归深度  p8-2-01

错题:

    4.长度分别为m和n的升序链表,合并为长度为m+n的降序链表最坏情况是怎样,时间复杂度是什么

    5.王道课后习题  p7--07、09、13、2-01、2-02-③

5.空间复杂度:

    (1)程序运行时内存=程序代码(不变)+数据(变化)---------数据是空间复杂度的关注点

    (2)如果数据大小与n无关==》O(1):算法原地工作、所需空间为常量

    (3)递归:单次空间x递归深度

6.答案:

     1.数据结构=数据关系+数据对象

       抽象数据类型=数据的逻辑机构+抽象运算=数据对象+数据关系+基本操作集

     2.循环队列=顺序表表示的对列

        栈只表示逻辑结构可以用顺序存储或链式存储均可

      3.注意是节点内而不是节点间,节点内一定连续,节点间不一定

      4.最坏情况是一个个进行比较 为O(m+n)也可以为O(max(m,n))

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/ky-Ada/p/17644105.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!