1、软件水平考试（中级）软件设计师上午（基础知识）试题章节练习试卷 3 及答案解析(总分：44.00，做题时间：90 分钟)一、选择题(总题数：8，分数：44.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_某一确定有限自动机(DFA)的状态转换图如图 2-1 所示，该 DFA 接受的字符串集是(7)，与之等价的正规式是(8)。 （分数：4.00）A.以 1 开头的二进制代码串组成的集合B.以 1 结尾的二进制代码串组成的集合C.包含偶数个 0 的二进制代码串组成的集合D.包含奇数个 0 的二进制代码串组成的集合
2、A.1*0(01)*B.(01*0)*1*C.1*(01)0*D.1*(01*0)*某一确定性有限自动机(DFA)的状态转换图如图 2-2 所示，令 d=01219，则以下字符串中，不能被该 DFA 接受的是(9)，与该 DFA 等价的正规式是(10)。(其中， 表示空字符。) （分数：4.00）A.B.C.D.A.(-dd)d*E(-dd)d*(-dd)d*.d*E(-dd)d*B.(-dd)dd*(.)d*E(-dd)d*C.(-d)dd*E(-d)d*(-dd)dd*.d*E-E(-d)d*D.(-dd)dd*E(-dd)d*(-dd)dd*.d*E(-dd*dd*)某一非确定性有限自动
3、机(NFA)的状态转换图如图 2-6 所示，与该 NFA 等价的正规式是(12)，与该 NFA 等价的 DFA 是(13)。 （分数：4.00）A.0*(01)0B.(010)*C.0*(01)0*D.0*(10)*_图 2-7 为一确定有限自动机(DFA)的状态转换图，与该自动机等价的正规表达式是(14)，图中的(15)是可以合并的状态。 （分数：4.00）A.a(ba)*bb(a*b*)*B.(ab)*bba*b*C.(a*b*)bb(ab)*D.(ab)*bb(a*b*)*A.0 和 1B.2 和 3C.1 和 2D.0 和 3若有一个仓库，可以存放 P1，P2 两种产品，但是每次只能存
4、放一种产品，要求： w=P1 的数量-P2 的数量 -iwk(i，k 为正整数) 若用 PV 操作实现 P1 和 P2 产品的入库过程，至少需要(9)个同步信号量及(10)个互斥信号量，其中，同步信号量的初值分别为(11)，互斥信号量的初值分别为(12)。（分数：8.00）A.0B.1C.2D.3A.0B.1C.2D.3A.0B.i，k，0C.i，kD.i-1，k-1A.1B.1，1C.1，1，1D.i，k在多媒体的音频处理中，由于人所敏感的音频最高为(14)赫兹(Hz)，因此，数字音频文件中对音频的采样频率为(15)赫兹(Hz)。对一个双声道的立体声，保持一秒钟声音，其波形文件所需的字节数为
5、(16)，这里假设每个采样点的量化位数为 8 位。MIDI 文件是最常用的数字音频文件之一，MIDI 是一种(17)，它是该领域国际上的一个(18)。（分数：10.00）A.50B.10kC.22kD.44kA.44.1kB.20.05kC.10kD.88kA.22050B.88200C.176400D.44100A.语音数字接口B.乐器数字接口C.语音模拟接口D.乐器模拟接口A.控制方式B.管理规范C.通信标准D.输入格式数据压缩技术是多媒体信息处理中的关键技术之一，数据压缩技术可分为(29)两大类。(30)是种与频度相关的压缩编码方法，(31)主要用于视频信息的压缩，(32)常用于静止图片
6、的信息压缩。由三基色(RGB)原理出发的 RGB 彩色空间，在多媒体技术中是最常用的，此外还有多种彩色空间，但(33)不是计算机上用的彩色空间。（分数：10.00）A.可逆与不可逆B.高速与低速C.编码与非编码D.冗余与非冗余A.MIPSB.ISDNC.HuffmanD.GaussA.MIPSB.MPEGC.JPEGD.JIPSA.MIPSB.MPEGC.JPEGD.JIPSA.YUVB.HISC.XYZD.IMG软件水平考试（中级）软件设计师上午（基础知识）试题章节练习试卷 3 答案解析(总分：44.00，做题时间：90 分钟)一、选择题(总题数：8，分数：44.00)1.选择题（）下列各题
7、 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_解析：某一确定有限自动机(DFA)的状态转换图如图 2-1 所示，该 DFA 接受的字符串集是(7)，与之等价的正规式是(8)。 （分数：4.00）A.以 1 开头的二进制代码串组成的集合B.以 1 结尾的二进制代码串组成的集合C.包含偶数个 0 的二进制代码串组成的集合 D.包含奇数个 0 的二进制代码串组成的集合解析：A.1*0(01)*B.(01*0)*1*C.1*(01)0*D.1*(01*0)* 解析：解析：DFA 能接受的字符串是指一条从初态节点到终态节点的路径上所有弧上的标记
8、符所连接成的字符串。本题初态、终态节点均为 q0，若字符串中遇到 0，则状态由 q0 变为 q1，这样只有再次遇到 0，状态 q1 才能回到终态 q0，因此该 DFA 接受的字符串是包含偶数个 0 的二进制代码串。所以正规式中也应该含有偶数个 0。某一确定性有限自动机(DFA)的状态转换图如图 2-2 所示，令 d=01219，则以下字符串中，不能被该 DFA 接受的是(9)，与该 DFA 等价的正规式是(10)。(其中， 表示空字符。) （分数：4.00）A.B. C.D.解析：A.(-dd)d*E(-dd)d*(-dd)d*.d*E(-dd)d* B.(-dd)dd*(.)d*E(-dd)
9、d*C.(-d)dd*E(-d)d*(-dd)dd*.d*E-E(-d)d*D.(-dd)dd*E(-dd)d*(-dd)dd*.d*E(-dd*dd*)解析：解析：DFA 能识别的字符串是指一条从初态节点到终态节点的路径上所有弧上的标记符所连接龙的字符串。我们依次检查备选项看哪些字符串不能被 DFA 接受。首先看“3875”，这个字符扫中的元素全是数字，从初态 0 出发输入一个数字进入状态 1：在状态 1 输入一个数字还是回到状态 1，无法前进。所以不能被 DFA 接受。接着看“1.2E+5”，这个不用判断都可以知道不行，因为“+”在 DFA 中不能识别。再看“-123.”，该串能从初态 0
10、 到达终态 5，所以能被只别。最后一个备选项中首字符“.”在初始状态无法被识别，所以不能被 DFA 识别。然后我们把 DFA 转化为正规式。首先可以排除 B 和 D，很显然(-dd)dd*所表达的串比所描述的多一个 d。再看 Cs 选项中(-d)dd*E(-d)d*表示不经过状态 5 的路径，而后面的 -dd)dd*.d*E-E(-d)d*)是指经过状态 5 的路径，所以 C 也被排除。这样答案只能选择 A 了。某一非确定性有限自动机(NFA)的状态转换图如图 2-6 所示，与该 NFA 等价的正规式是(12)，与该 NFA 等价的 DFA 是(13)。 （分数：4.00）A.0*(01)0B
11、.(010)* C.0*(01)0*D.0*(10)*解析：_解析：解析：从 q0 状态可以经过 q1 状态回到 q0 状态，同时也可以输入 0 回到 q0 状态，或输入若干个 0后经过 q1 状态再回到 q0 状态。所以该自动机识别的串等价于正规式(010)*。再利用子集法求出与该NFA 等价的 DFA。图 2-7 为一确定有限自动机(DFA)的状态转换图，与该自动机等价的正规表达式是(14)，图中的(15)是可以合并的状态。 （分数：4.00）A.a(ba)*bb(a*b*)* B.(ab)*bba*b*C.(a*b*)bb(ab)*D.(ab)*bb(a*b*)*解析：A.0 和 1B.
12、2 和 3 C.1 和 2D.0 和 3解析：解析：首先将途中状态分为终态和非终态两个子集，即(0，1，2，3)，再进行子集划分。观察第一个子集，输入 b 后，状态 0 转换为状态 1，而状态 1 转换为状态 2，因此1和2是可区别的。由于状态 2，3 输入字符 a 得到结果 3，输入字符 b 得到相同结果 2，所以子集2， 3是不可区别的。从而得到新的划分：(0，1，2，3)，即 2 和 3 是可以合并的状态。因此第二空的答案选 B。重复子集划分步骤，发现新的状态无法再次划分。删除节点 3 得到新的状态转换图，根据正规式和有限自动机之间的转换规则可以得到与该自动机等价的正规表达式为a(ba)
13、*bb(a*b*)*，从而第一空的答案选 A。若有一个仓库，可以存放 P1，P2 两种产品，但是每次只能存放一种产品，要求： w=P1 的数量-P2 的数量 -iwk(i，k 为正整数) 若用 PV 操作实现 P1 和 P2 产品的入库过程，至少需要(9)个同步信号量及(10)个互斥信号量，其中，同步信号量的初值分别为(11)，互斥信号量的初值分别为(12)。（分数：8.00）A.0B.1C.2 D.3解析：A.0B.1 C.2D.3解析：A.0B.i，k，0C.i，kD.i-1，k-1 解析：A.1 B.1，1C.1，1，1D.i，k解析：解析：为了标识 P1 和 P2 产品入库，我们需要两
14、个同步信号量 S1 和 S2，分别标记 P1 和 P2 的数量。根据题意，S1 的初值显然不能大于等于 k。因为如果 S1 的初值超过 k，而此时又有 P1 产品入库，就有可能会造成 w 的越界。同理 S2 的初值一样不能超过 i。此外，我们还需要设置一个互斥信号量 mutex，其初值为 1，使得多个进程能够互斥地访问临界区。P1 或 P2 两种产品中的任一种产品申请入库成功后，将mutex 减 1，使其他进程无法在此期间使用仓库。入库操作完成后，再将 mutex 加 1，其他进程就可以申请入库了。在多媒体的音频处理中，由于人所敏感的音频最高为(14)赫兹(Hz)，因此，数字音频文件中对音频的
15、采样频率为(15)赫兹(Hz)。对一个双声道的立体声，保持一秒钟声音，其波形文件所需的字节数为(16)，这里假设每个采样点的量化位数为 8 位。MIDI 文件是最常用的数字音频文件之一，MIDI 是一种(17)，它是该领域国际上的一个(18)。（分数：10.00）A.50B.10kC.22k D.44k解析：A.44.1k B.20.05kC.10kD.88k解析：A.22050B.88200 C.176400D.44100解析：A.语音数字接口B.乐器数字接口 C.语音模拟接口D.乐器模拟接口解析：A.控制方式B.管理规范C.通信标准 D.输入格式解析：解析：人的听觉带宽一般为 20Hz20
16、kHz，人敏感的音频最高为 22kHz。数字音频文件中对音频的采样频率为 44.1kHz。 声音能按波形声音采样、存储和再现，如果不经过压缩，声音数字化后每秒所需的存储量可按下式估算： 文件的字节数=采样频率采样位数声道数8 因此，题目所要求的存储量为14410082+8=88200 字节。 MIDI 是一种乐器数字接口的英文缩写，泛指数字音乐的国际标准。数据压缩技术是多媒体信息处理中的关键技术之一，数据压缩技术可分为(29)两大类。(30)是种与频度相关的压缩编码方法，(31)主要用于视频信息的压缩，(32)常用于静止图片的信息压缩。由三基色(RGB)原理出发的 RGB 彩色空间，在多媒体技
17、术中是最常用的，此外还有多种彩色空间，但(33)不是计算机上用的彩色空间。（分数：10.00）A.可逆与不可逆 B.高速与低速C.编码与非编码D.冗余与非冗余解析：A.MIPSB.ISDNC.Huffman D.Gauss解析：A.MIPSB.MPEG C.JPEGD.JIPS解析：A.MIPSB.MPEGC.JPEG D.JIPS解析：A.YUVB.HISC.XYZD.IMG 解析：解析：目前常用的压缩编码方法可以分为两大类。一类是无损压缩编码，也称冗余压缩法，由于这种方法只是把冗余部分清除，所以此算法可逆；另一类是有损压缩编码，此算法可得到较高的压缩比，但无法把压缩数据还原。因此数据压缩技术分为可逆和不可逆两大类。Huffman 编码是一种无损压缩算法，JPEG 用于静态图像压缩，MPEG 用于动态影像压缩。计算机常用的彩色空间有 YUV，XYZ，HIS 和 RGB 等，选项中的 IMG 不是彩色空间。
