免费智能真题库 > 历年试卷 > 软件设计师 > 2012年下半年 软件设计师 上午试卷 综合知识
  第64题      
  知识点:   队列   编码   编码方案   霍夫曼编码
  关键词:   存储空间   根节点   孩子节点   霍夫曼编码   优先级队列   最优编码   编码   队列        章/节:   计算机软件知识       

 
霍夫曼编码将频繁出现的字符釆用短编码,出现频率较低的字符采用长编码。具体的操作过程为:i)以每个字符的出现频率作为关键字构建最小优先级队列;ii)取出关键 字最小的两个结点生成子树,根节点的关键字为孩子节点关键字之和,并将根节点插入到最小优先级队列中,直至得到一颗最优编码树。
霍夫曼编码方案是基于(64)策略的。用该方案对包含a到f六个字符的文件进行编码,文件包含100,000个字符,每个字符的出现频率(用百分比表示)如下表所示,则与固定长度编码相比,该编码方案节省了(65)存储空间。
 
 
  A.  分治
 
  B.  贪心
 
  C.  动态规划
 
  D.  回溯
 
 
 

 
  第58题    2015年上半年  
   32%
设栈S和队列Q的初始状态为空,元素a b c d e f g依次进入栈S。要求每个元素出栈后立即进入队列Q,若7个元素出队列的顺序为b d f ..
  第57题    2022年下半年  
   58%
设栈初始时为空,对于入栈序列1,2,3…n这些元素经过栈之后得到出栈序列P1,P2,P3,.…Pn,若P3-4,则P1,P2不可能的值为()。
  第58题    2017年上半年  
   22%
已知栈S初始为空,用I表示入栈、O表示出栈,若入栈序列为a1a2a3a4a5,..
   知识点讲解    
   · 队列    · 编码    · 编码方案    · 霍夫曼编码
 
       队列
        1)队列的定义及基本运算
        队列是一种先进先出(FIFO)的线性表,它只允许在表的一端插入元素,而在表的另一端删除元素。在队列中,允许插入元素的一端称为队尾(Rear),允许删除元素的一端称为队头(Front)。
        对队列进行的基本操作如下。
        (1)置队空InitQueue(Q):创建一个空的队列Q。
        (2)判队空Empty(Q):判断队列是否为空。
        (3)入队EnQueue(Q,x):将元素x加入到队列Q的队尾,并更新队尾指针。
        (4)出队DeQueue(Q):将队头元素从队列Q中删除,并更新队头指针。
        (5)读队头元素Frontque(Q):返回队头元素的值,但并不更新队头指针。
        2)队列的存储结构
        (1)顺序存储。队列的顺序存储结构是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在队列的两端进行,因此设置队头指针和队尾指针,分别指示当前的队首元素和队尾元素。
        在顺序队列中,为了降低运算的复杂度,元素入队时只需修改队尾指针,元素出队时只需修改队头指针。由于顺序队列的存储空间是提前设定的,所以队尾指针会有一个上限值,当队尾指针达到其上限时,就不能只通过修改队尾指针来实现新元素的入队操作了。此时,可通过整除取余运算将顺序队列假想成一个环状结构,称之为循环队列。在队列空和队列满的情况下,循环队列的队头、队尾指针指向的位置是相同的。为了区别队空和队满的情况,可采用两种处理方式:其一是设置一个标志位,以区别头、尾指针的值相同时队列是空还是满;其二是牺牲一个元素空间,约定以"队列的尾指针所指位置的下一个位置是头指针时"表示队列满,头、尾指针的值相同时表示队列空。
        (2)链式存储。用链表表示的队列简称为链队列。为了便于操作,给链队列添加一个头节点,并令头指针指向头节点。队列为空的判定条件是:头指针和尾指针的值相同,且均指向头节点。
        3)队列的应用
        队列结构常用于处理需要排队的场合,如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。
 
       编码
               编码过程
               在给定了软件设计规格说明书后,下一步的工作就是编写代码。一般来说,编码工作可以分为四个步骤:
               (1)确定源程序的标准格式,制订编程规范。
               (2)准备编程环境,包括软硬件平台的选择,包括操作系统、编程语言、集成开发环境等。
               (3)编写代码。
               (4)进行代码审查,以提高编码质量。为提高审查的效率,在代码审查前需要准备一份检查清单,并设定此次审查须找到的bug数量。在审查时,要检查软件规格说明书与编码内容是否一致;代码对硬件和操作系统资源的访问是否正确;中断控制模块是否正确等。
               编码准则
               在嵌入式系统中,由于资源有限,且实时性和可靠性要求较高,因此,在开发嵌入式软件时,要注意对执行时间、存储空间和开发/维护时间这三种资源的使用进行优化。也就是说,代码的执行速度要越快越好,系统占用的存储空间要越小越好,软件开发和维护的时间要越少越好。
               具体来说,在编写代码时,需要做到以下几点:
               .保持函数短小精悍。一个函数应该只实现一个功能,如果函数的代码过于复杂,将多个功能混杂在一起,就很难具备可靠性和可维护性。另外,要限制函数的长度,一般来说,一个函数的长度最好不要超过100行。
               .封装代码。将数据以及对其进行操作的代码封装在一个实体中,其他代码不能直接访问这些数据。例如,全局变量必须在使用该变量的函数或模块内定义。对代码进行封装的结果就是消除了代码之间的依赖性,提高了对象的内聚性,使封装后的代码对其他行为的依赖性较小。
               .消除冗余代码。例如,将一个变量赋给它自己,初始化或设置一个变量后却从不使用它,等等。研究表明,即使是无害的冗余也往往和程序的缺陷高度关联。
               .减少实时代码。实时代码不但容易出错、编写成本较高,而且调试成本可能更高。如果可能,最好将对执行时间要求严格的代码转移到一个单独的任务或者程序段中。
               .编写优雅流畅的代码。
               .遵守代码编写标准并借助检查工具。用自动检验工具寻找缺陷比人工调试便宜,而且能捕捉到通过传统测试检查不到的各种问题。
               编码技术
                      编程规范
                      在嵌入式软件开发过程中,遵守编程规范,养成良好的编程习惯,这是非常重要的,将直接影响到所编写代码的质量。
                      编程规范主要涉及的三方面内容:
                      .命名规则。从编译器的角度,一个合法的变量名由字母、数字和下画线三种字符组成,且第一个字符必须为字母或下画线。但是从程序员的角度,一个好的名字不仅要合法,还要载有足够的信息,做到“见名知意”,并且在语意清晰、不含歧义的前提下,尽可能地简短。
                      .编码格式。在程序布局时,要使用缩进规则,例如变量的定义和可执行语句要缩进一级,当函数的参数过长时,也要缩进。另外,括弧的使用要整齐配对,要善于使用空格和空行来美化代码。例如,在二元运算符与其运算对象之间,要留有空格;在变量定义和代码之间要留有空行;在不同功能的代码段之间也要用空行隔开。
                      .注释的书写。注释的典型内容包括:函数的功能描述;设计过程中的决策,如数据结构和算法的选择;错误的处理方式;复杂代码的设计思想等。在书写注释时要注意,注释的内容应该与相应的代码保持一致,同时要避免不必要的注释,过犹不及。
                      性能优化
                      由于嵌入式系统对实时性的要求较高,因此一般要求对代码的性能进行优化,使代码的执行速度越快越好。以算术运算为例,在编写代码时,需要仔细地选择和使用算术运算符。一般来说,整数的算术运算最快,其次是带有硬件支持的浮点运算,而用软件来实现的浮点运算是非常慢的。因此,在编码时要遵守以下准则:
                      .尽量使用整数(char、short、int和long)的加法和减法。
                      .如果没有硬件支持,尽量避免使用乘法。
                      .尽量避免使用除法。
                      .如果没有硬件支持,尽量避免使用浮点数。
                      下图是一个例子,其中两段代码的功能完全一样,都是对一个结构体数组的各个元素进行初始化,但采用两种不同的方法来实现。下图(a)采用数组下标的方法,在定位第i个数组元素时,需要将i乘以结构体元素的大小,再加上数组的起始地址。下图(b)采用的是指针访问的方法,先把指针fp初始化为数组的起始地址,然后每访问完一个数组元素,就把fp加1,指向下一个元素。在一个奔腾4的PC上,将这两段代码分别重复10 700次,右边这段代码需要1ms,而左边这段代码需要2.13ms。
                      
                      算术运算性能优化的例子
 
       编码方案
        DOI的编码方案(即美国标准ANSI/NISO Z39.84-2000)规定,一个DOI由两部分组成:前缀和后缀,中间用“/”分割。前缀与后缀的字符长度没有任何限制,因此理论上DOI编码体系的容量是无限的。
 
       霍夫曼编码
        霍夫曼(Huffman)编码的基本原理是根据信源的频率进行编码。出现频率大的符号用较少的位数表示,出现频率小的符号用较多位数表示。这种方法的压缩率取决于符号的分布频率,分布越集中,压缩效果越好。
        霍夫曼编码的算法步骤如下。
        ①初始化。将信号源的符号按照出现概率递减的顺序排列。
        ②计算。将两个最小出现概率进行合并相加,将得到的结果作为新符号的出现概率。
        ③重复步骤①和②直到概率相加的结果等于1。
        ④分配码字。对所有出现的符号进行分配码字,概率大的符号用编码0表示,概率小的符号用编码1表示(当然也可以相反)。
        ⑤记录编码。记录概率为1处到当前信号源符号之间的0、1序列,从而得到每个符号的编码。
        霍夫曼编码的特点如下。
        ①霍夫曼编码属于异字头码,保证了码的唯一可译性。
        ②编码长度是可变的,因此译码时间较长,使得霍夫曼编码的压缩与还原相当费时。
        ③由于编码长度不统一,硬件实现起来有难度。
        ④对不同信号源的编码效率不同,当信号源的符号概率为2的负幂次方时,达到100%的编码效率;若信号源符号的概率相等,则编码效率最低。
        ⑤由于0与1的指定是任意的,故由上述过程编出的最佳码不是唯一的,但其平均码长是一样的,故不影响编码效率与数据压缩性能。
   题号导航      2012年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第64题    在手机中做本题