信息系统管理工程师教程整理版全新考试2018年(7)

1 描述一个算法可以采用文字描述，也可以采用传统流程图、N-S图或PAD图。 2 算法特性：有穷性、确定性、可行性、输入、输出。

3 算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如流程图、Pascal语言、C语言、伪代码或决策表。 5.1.4 算法评价

4一个“好”的算法应满足正确性、可读性、健壮性、效率和低存储量需求。 5 算法评价：时间复杂度和空间复杂度。 5.1.5 算法与数据结构的关系 5.2 线性表

5.2.1 线性表的定义和逻辑结构

6 线性表表示：A=（a1 ，a2，…，ai-1，ai，ai+1，…， an）

linear_list=（A，R）

7 线性表的抽象数据类型包括数据对象和数据关系2部分。 5.2.2 线性表的顺序存储结构

8 线性表的存储结构有顺序、链接、散列。 5.2.3 线性表的链式存储结构 5.3 栈和队列

5.3.1 栈的定义和实现

9 栈的主要操作是初始化、插入、删除、判断是否空、读取栈顶结点值。 5.3.2 表达式求值

10 表达式是由操作数（operand）、运算符（operator）、界限符（delimiter）组成。 11 表达式一般分为中缀表达式和后缀表达式。 5.3.3 队列

21 / 122

12 队列分为链队列和循环队列。 5.4 数组和广义表 5.4.1 数组

13 数组一般采用顺序存储结构表示，多维数组的顺序存储有两种形式：以列序为主序、以行序为主序。

14 行优先顺序又称为低下标优先或左下标优先于右下标。Basic、Pascal、C都是采用行优先顺序。

5.4.2 广义表的定义和存储结构

15 广义表有两种结构的结点：表结点，表示列表；原子结点，表示原子。表结点可以由标志域、指示表头的指针域、指示表尾的指针域，原子结点由标志域和值域组成。 5.5 树和二叉树 5.5.1 树的定义

16 树的表示方法：常用方法（树型）、括号、嵌套集合、凹入。 5.5.2 树的存储结构

17 常用的树存储结构主要有三种：双亲表示法、孩子表示法、孩子兄弟表示法。 5.5.3 树的遍历

18 树的遍历方式分为三种：前序遍历、后序遍历、层次遍历。

19 如下图进行三种遍历的结果：前序遍历—ABCEFHIGD;后序遍历—BEHIFGCDA;层次遍历—ABCDEFGHI。 5.6 图

5.6.1 图的定义和术语 5.6.2 图的存储结构

20 邻接矩阵表示法的空间复杂度为S（n）=O（n2）。

22 / 122

5.6.3 图的遍历

21 图的遍历方法深度优先遍历、广度优先遍历。

第六章 多媒体基础知识

6.1 多媒体技术概论 6.1.1 多媒体技术基础概念

1多媒体计算机技术的特性：集成性、交互性、实时性、数字化。

2多媒体计算机硬件主要包括一下几部分：多媒体主机（个人机、工作站）、多媒体输入设备（摄像机、麦克风、扫描仪）、多媒体输出设备（打印机、绘图仪、音响）、多媒体存储设备（硬盘、光盘）、多媒体功能卡（视频卡、声音卡）、操纵控制设备（鼠标、键盘、触摸屏）。

3多媒体计算机软件系统包括：操作系统、多媒体数据库管理系统、多媒体压缩/解压缩软件、多媒体声像同步软件、多媒体通信软件以及多媒体开发和创作工具。

4多媒体开发软件包提供了图形、色彩板、声音、动画、图像及各种媒体文件的转换与编辑软件。

6.1.2 多媒体关键技术和应用

1多媒体技术的主要组成归纳为以下几个方面：各种媒体信息的处理技术和压缩技术、多媒体计算机技术、多媒体网络通信技术、多媒体数据库技术。

2多媒体计算机系统的关键技术：视频和音频数据的压缩和解压缩技术、多媒体专用芯片技术、多媒体系统软件技术、大容量信息存储技术、多媒体网路通信技术、超文本与超媒体技术。

3在研究和选用编码时，主要有两个问题：编码方法能用计算机软件或集成电路芯片快速实现；符合压缩编码和解压缩编码的国际标准。

23 / 122

4多媒体专用芯片基于大规模集成电路（VLSI）技术，除专用处理器芯片外，多媒体系统还需要其他集成电路芯片支持：数模和模数转换器、音频视频芯片、彩色空间变换器及时钟信号产生器。

5多媒体系统软件技术主要包括：多媒体操作系统、媒体编辑系统、多媒体数据库管理技术、多媒体信息和混合于重叠技术。

6多媒体数据库的关键技术是解决：多媒体数据的模型、表示方式；多媒体数据的压缩及解压缩；多媒体数据的存储管理和存储方法。

7多媒体网络通信的关键技术是多媒体数据的压缩技术和高速的数据通信技术。 8超媒体技术是超文本＋多媒体。

9多媒体计算机技术的应用：教育与培训、桌面出版与办公自动化、多媒体电子出版物、多媒体通信、多媒体声光艺术品的创作。

10桌面出版物主要包括：印刷品、表格、布告、广告、宣传品、海报、市场图表、蓝图及商品图。

11多媒体电子出版物的内容可分为：电子图书、文档资料、报刊杂志、教育培训、娱乐游戏、宣传广告、信息咨询。

12电子出版物的特点是：具有集成性和交互性、表现力强。 13多媒体通信的特点：分布性、同步性、交互性。 6.2 多媒体压缩编码技术

6.2.1 多媒体数据压缩的基本原理

1信息压缩比是指压缩前后所需的多媒体数字信息存储量之比，压缩比越大，数据减少的就越多，压缩技术越复杂。

2可用如下指标衡量一种数据压缩技术的好坏：压缩比、压缩后多媒体信息的质量、压缩和解压缩速度、压缩所需的软硬件开销。

24 / 122

3多媒体数据压缩处理包括：编码（压缩）过程和解码（解压缩）过程。 4一般来说，压缩的计算量比解压缩的计算量大。 6.2.2 多媒体数据压缩的基本编码方法

1数据压缩方法：无损压缩法（冗余压缩法）和有损压缩法（熵压缩法）。 2无损压缩的压缩率一般为2：1到5：1。

3常用的无损压缩方法有：哈夫曼编码、算术编码、行程编码、使用统计的方法或字典查找的方法进行压缩。

4常用的有损压缩方法有：预测编码、变换编码、子带编码、矢量量化编码、混合编码、小波编码。

5哈夫曼编码是对独立信源达到最小平均码长的编码方法，具有唯一可译性。 6算术方法是一种二元码的编码方法。

7预测编码常用的是差分脉冲编码调制法（DPCM）和自适应的差分脉冲编码调制法（ADPCM）。

8变换编码种类：傅立叶变换、离散余弦变换、离散正弦变换。 6.2.3 编码的国际标准

1通用的压缩编码国际标准：JPEG、MPEG、H.261、DVI。

2JPEG（联合照片专家组），静止图像压缩和解压缩算法。由ISO和CCITT（国际电报电话咨询委员会）共同制定。一般来说，JPEG图像压缩比大于20：1时，图像质量开始变坏。

3MPEG（动态图像专家组），提供的压缩比可高达200：1，通常有三个版本MPEG—1、MPEG—2、MPEG—3。优点：兼容性好、压缩比高、数据失真小。 4H.261也称PX64标准。 6.3 多媒体技术应用

25 / 122