数据结构 第1章 绪论（一轮习题总结）

1.1 数据结构的基本概念（1 3 4 6 7）
1.2 算法和算法评价（9 13）

1.1 数据结构的基本概念

• T1
  一个完整的数据结构：抽象数据类型ADT，用三元组（数据对象，数据类型，基本操作集）表示
• T3 / T4
  哈希表：既有逻辑结构，又有存储结构。
  循环队列（易错点）：既有逻辑结构，又有存储结构。是用顺序表表示的队列。
• T6
  存储数据：数据的值+数值元素之间的关系
  关系：同属一个集合（集合）一对一（线）、一对多（树）、多对多（图/网）
• T7
  链式存储：结点间不一定连续，结点内一定连续

1.2 算法和算法评价

• T8
  （补充）递归算法的复杂度分析：可以画出递归树/执行树，根据树的结点进行计算
  eg：斐波那契函数f(7) —>2⁰+2¹+…+2⁶(2⁷-1）—>时间复杂度为O(2ⁿ)
• T9
  两链表合并，比较次数m+n < 2max(m, n)，时间复杂度O(max(m, n))
• T10 / T6 / T13
  双循环的时间复杂度分析（三种，个人总结欢迎补充）
  T10 第1种：i和j只与n有关，分别计算相乘
  时间复杂度：O(nlogn)

  for(i=1; i<=n ;i*=2)
  	for(j=1; j<=n; j++)
  1
  2

  T6 第2种：j和i有关，i正常+1增长，逐层分析j循环
  时间复杂度：O(n²)

  for(i=1; i<=n; i++)
  	for(j=1; j<=i*2; j++)
  1
  2

  T13 第3种（难点）：j和i有关，i不正常增长，可借用辅助设i循环k次，计算n和k的表达式
  时间复杂度：O(n)

  for(i=i=1; i<=n; i*2)
  	for(j=1; j<=i; j++)
  1
  2