中级软考知识点六

中级软考知识点六

数据结构

• 线性表

  • 顺序表
  • 链表
    • 单链表
    • 循环链表
    • 双向链表
  • 队列
  • 栈

• 树

  • 二叉树
    • 先序遍历：根 左 右
    • 中序遍历：左 根 右
    • 后序遍历：左 右 根
    • 层次遍历
  • 最优二叉树（哈弗曼树）
  • 线索二叉树：节点记录前驱和后驱
  • 平衡二叉树：任意节点的左右子树深度不超过1

• 图论

  • 有向图
  • 无向图
  • 图的存储
    • 邻接矩阵：二维数组
    • 邻接表：一位数组+链表
  • 图的遍历
    • 广度优先BFS
    • 深度优先DFS
  • 拓扑排序
  • 图的最小生成树

编译过程

• 

• 词法错误：非法字符，关键字灬标识符拼写错误

• 语法错误：语法结构出错，if endif不匹配，缺分号

• 语义错误：死循环，零除数，其他逻辑错误

表达式

• 前缀表达式：+ab

• 中缀表达式：a+b

• 后缀表达式：ab+

• 程序语言

  

多媒体基础知识

• 音频容量计算：每秒容量=采样频率（Hz）*样本精度（位）*声道数/8
• 图像容量计算：容量=长*宽*位数/8 或 长*宽*\log2(色数)/8
• 常见多媒体标准
  • JPEG-2000
    • 有损&无损
    • 压缩比更高
    • 小波变换
    • 医学图像应用
  • MPEG-1
    • 离散余弦
    • VCD
    • MP3
  • MPEG-2
    • 离散余弦
    • Huffman
    • DVD
    • 有线/卫星电视
    • AAC
  • MPEG-4
    • 网络应用/可视电话
    • 无线通信
    • 增强交互性
    • 数码权限管理
    • 多媒体传输集成框架
  • MPEG-7
    • 多媒体内容描述接口
    • 具备描述功能
    • 不是编码标准
  • MPEG-21
    • 融合不同协议
    • 制定新标准
    • 标准集成
  • JPEG
    • 有损
    • RGB转YUV
    • 离散余弦

知识产权

• 版权
• 软件著作权：不需要申请
• 专利权：需要申请
• 商标权：需要申请
• 商业秘密权

算法

• 分治法：分而治之，将问题分解为规模较小的子问题，一般用递归求解
  • 快排
  • 并归排序
  • 矩阵乘法
  • 大整数乘法
  • 汉诺塔
  • 求斐波那契数列
  • 二分查找
• 回溯法：选优搜索法，按选优条件向前搜索，若到达某一步发现选择并不优或打不到目标就退回伊布重新选择
  • N皇后问题
  • 迷宫
  • 背包问题
• 贪心法：（用于求满意解）总是做出在当前来说是最好的选择，而并不从整体上加以考虑。局部最优选择，不保证整体最优
  • 背包问题（如装箱）
  • 多机调度
  • 找零钱问题
• 动态规划法：（用于求最优解）对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃哪些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。
  • 背包问题
  • LCS最长公共子序列
  • 斐波那契数列
  • 矩阵乘法
• 时间复杂度
  • 
  • 二分或与树相关的时间复杂度一般为O(log2(n))