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