信息系统管理工程师复习笔记(总结)

4.4、相关题目

第五章、数据结构与算法 5.1、数据结构与算法简介

1）计算机程序处理的一切数值的、非数值的信息，乃至程序统称为数据(Data)，而计算机是加工处理数据(信息)的工具。

2）数据的特性以及数据之间存在的关系称为数据结构(Data Structure)。

3）计算机算法与数据结构密切相关，算法依附于具体的数据结构，数据结构直接关系到算法的选择和效率。

4）数据结构的常用名词：数据(符号描述)、数据元素(数据的基本单位)、数据记录、关键项、数据处理、数据结构、数据类型、数据对象、算法、线性结构、集合、图、树等。

5）算法描述：特性包含有穷性、确定性、可行性、输入、输出。 算法是可以用自然语言、数字语言、约定符号来表示、也可以用计算机高级语言描述，例如流程图、Pascal、C语言、伪代码或决策表。

6）算法评价：好的算法评价的特性包含正确性、可读性、健壮性。效率和低存储量需求。

5.2、线性表

1）线性表：最常用最简单的一种数据结构。一个线性表是N个数据元素的有限序列。一个数据元素可以有若干个数据项组成。

2）线性表的存储结构有顺序、链接、散列等方式，注意顺序和链式存储结构的分别。

5.3、栈和队列

1）栈是一种特殊的线性表，是限定在表尾进行插入或者删除操作的线性表。进行插入和删除的那一端为栈顶，另一端为栈底。栈的插入和删除操作分别简称进栈和出栈。

2）栈分为顺序存储和链式存储。

3）栈后进先出，队列先进先出---同样是在线性表中 \按顺序\插入1,2,3,4 对于栈,只允许在尾部删除,所以先出栈的将会是4,即后进先出 对于队列,只允许在头部删除,所以先出队的是1,即先进后出

4）表达式求值：表达式由运算符、操作数、界限符组成。结束符是#号。

5）表达式分为中缀表达式(算法与算数运算一致)和后缀表达式(算法为顺序运算)

5.4、数组与广义表

1）数组分为动态数组(声音没有下标的数组名，使用时再声明下标)与静态数据(使用数值常量、符号常量定义下标)

2）多维数组的顺序存储的两种形式：以列序为主序，以行序为主序。

3）行优先序列是低下标优先或左边下标优先于右下标，Basic、Pascal、C都是采用行优先顺序

4）广义表有两种结构的结点：表结点，表示列表；原子结点，表示原子。表结点可以

由标志域、指示表头的指针域、指示表尾的指针域，原子结点由标志域和值域组成。

5.5、树和二叉树

1）树的表示方法：常用方法（树型）、括号、嵌套集合、凹入。

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

3）二叉树的特点是每个节点最多2个子数，不能大于2，且左右次序不能任意颠倒。 4）常用的树存储结构主要有三种：双亲表示法、孩子表示法、孩子兄弟表示法。 5）树的遍历方式分为三种：前序、后序、层次

前序：先访问根节点，再一次按前序遍历的方式访问根节点的每一个

子树，ABCEFHIGD；后序：先按后续遍历的方式访问根节点的每一个子树，再访问根节点，BEHIFGCDA。层次：首先访问第一层上的根节点，然后从左到右访问第二层所有节点，最后访问最低一层的所有节点，ABCDEFGHI。

5.6、图

1）图的定义：由一个非空的顶点集合和一个描述顶点之间多对多的边集合组成的一种数据结构。

2）图分为有向图和无向图。

3）图的存储结构：邻接矩阵表示法的空间复杂度为S（n）=O（n2） 4）图的遍历：深度优先遍历、广度优先遍历。

第六章、多媒体基础知识 6.1、多媒体概论

1）多媒体就是多种媒体的综合，多媒体技术出现在20世纪80年代初期，将计算机技术、声像处理技术、通信技术、出版技术结合，综合处理“图、文、声、像”多种信息。

2）多媒体计算机技术的特性：集成性、交互性、实时性、数字化。 3）多媒体计算机硬件主要包括：对媒体主机（个人机、工作站）、多媒体输入设备（摄像机、麦克风、扫描仪）、多媒体输出设备（打印机、绘图仪、音响）、多媒体存储设备（硬盘、光盘）、多媒体功能卡（视频卡、声音卡）、操纵控制设备（鼠标、键盘、触摸屏）。

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

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

6.2、多媒体关键技术应用

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

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

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

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

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

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

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

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

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

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

12）电子出版无的特点是：具有集成性和交互性、表现力强。 13）多媒体通信的特点：分布性、同步性、交互性

6.3 多媒体压缩编码技术

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

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

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

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

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

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

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

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

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

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

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

6.4 多媒体技术应用

6.4.1 、数字图像处理技术

1）数字图像的优点是：精度高、数字图像不会被电源的波动电磁场辐射等环境干扰所