免费智能真题库 > 历年试卷 > 程序员 > 2009年上半年 程序员 下午试卷 案例
  第6题      
  知识点：   Java   编码   存储结构   模板   数组   索引

 
【说明】
java.util包中提供了HashMap模板类，该模板类可以表示多个“键-值”对的集合， 其中“键”的作用与普通数组中的索引相当，而“值”用作待存储和检索的数据。HashMap 实现了 Map接口。在Map接口中定义了put和get方法，put方法表示Map对象中加入一个“键-值”对，get方在则通过“键”来获取其对应的“值”。
下面的Java代码中使用了HashMap模板类，将编号为1001、1002、1003的员工信息插入到HashMap对象中，然后输入一个指定的员工编号，通过员工编号来获取员工的 基本信息。员工编号为整型编码，而员工的基本信息定义为类employee。
HashMap对象与员工对象之间的关系及存储结构如下图所示。
 
问题：6.1  

 
 
 

   知识点讲解    
   · Java    · 编码    · 存储结构    · 模板    · 数组    · 索引
 
       Java
        Java语言起源于Oak语言，Oak语言被设计成能运行在设备的嵌入式芯片上。
        Java编译成伪代码，这需要一个虚拟机来对其进行解释，Java的虚拟机在几乎每一种平台上都可以运行。这实质上使得开发是与机器独立无关的，并且提供了通用的可移植性。
        Java把类的概念和接口的概念区分开来，并试图通过只允许接口的多继承来克服多继承的危险。
        Java的异常处理机制与C++的try/throw/catch相类似，但更加严密。在Java中，通过声明轻型线程来处理并发性，这些线程通过副作用和同步协议进行通信。
        Java Beans是组件，即类及其所需资源的集合，它们主要被设计用来提供定制的GUI小配件。
        Java中关于面向对象概念的术语有对象、类、方法、实例变量、消息、子类和继承。
 
       编码
               编码过程
               在给定了软件设计规格说明书后，下一步的工作就是编写代码。一般来说，编码工作可以分为四个步骤：
               （1）确定源程序的标准格式，制订编程规范。
               （2）准备编程环境，包括软硬件平台的选择，包括操作系统、编程语言、集成开发环境等。
               （3）编写代码。
               （4）进行代码审查，以提高编码质量。为提高审查的效率，在代码审查前需要准备一份检查清单，并设定此次审查须找到的bug数量。在审查时，要检查软件规格说明书与编码内容是否一致；代码对硬件和操作系统资源的访问是否正确；中断控制模块是否正确等。
               编码准则
               在嵌入式系统中，由于资源有限，且实时性和可靠性要求较高，因此，在开发嵌入式软件时，要注意对执行时间、存储空间和开发／维护时间这三种资源的使用进行优化。也就是说，代码的执行速度要越快越好，系统占用的存储空间要越小越好，软件开发和维护的时间要越少越好。
               具体来说，在编写代码时，需要做到以下几点：
               .保持函数短小精悍。一个函数应该只实现一个功能，如果函数的代码过于复杂，将多个功能混杂在一起，就很难具备可靠性和可维护性。另外，要限制函数的长度，一般来说，一个函数的长度最好不要超过100行。
               .封装代码。将数据以及对其进行操作的代码封装在一个实体中，其他代码不能直接访问这些数据。例如，全局变量必须在使用该变量的函数或模块内定义。对代码进行封装的结果就是消除了代码之间的依赖性，提高了对象的内聚性，使封装后的代码对其他行为的依赖性较小。
               .消除冗余代码。例如，将一个变量赋给它自己，初始化或设置一个变量后却从不使用它，等等。研究表明，即使是无害的冗余也往往和程序的缺陷高度关联。
               .减少实时代码。实时代码不但容易出错、编写成本较高，而且调试成本可能更高。如果可能，最好将对执行时间要求严格的代码转移到一个单独的任务或者程序段中。
               .编写优雅流畅的代码。
               .遵守代码编写标准并借助检查工具。用自动检验工具寻找缺陷比人工调试便宜，而且能捕捉到通过传统测试检查不到的各种问题。
               编码技术
                      编程规范
                      在嵌入式软件开发过程中，遵守编程规范，养成良好的编程习惯，这是非常重要的，将直接影响到所编写代码的质量。
                      编程规范主要涉及的三方面内容：
                      .命名规则。从编译器的角度，一个合法的变量名由字母、数字和下画线三种字符组成，且第一个字符必须为字母或下画线。但是从程序员的角度，一个好的名字不仅要合法，还要载有足够的信息，做到“见名知意”，并且在语意清晰、不含歧义的前提下，尽可能地简短。
                      .编码格式。在程序布局时，要使用缩进规则，例如变量的定义和可执行语句要缩进一级，当函数的参数过长时，也要缩进。另外，括弧的使用要整齐配对，要善于使用空格和空行来美化代码。例如，在二元运算符与其运算对象之间，要留有空格；在变量定义和代码之间要留有空行；在不同功能的代码段之间也要用空行隔开。
                      .注释的书写。注释的典型内容包括：函数的功能描述；设计过程中的决策，如数据结构和算法的选择；错误的处理方式；复杂代码的设计思想等。在书写注释时要注意，注释的内容应该与相应的代码保持一致，同时要避免不必要的注释，过犹不及。
                      性能优化
                      由于嵌入式系统对实时性的要求较高，因此一般要求对代码的性能进行优化，使代码的执行速度越快越好。以算术运算为例，在编写代码时，需要仔细地选择和使用算术运算符。一般来说，整数的算术运算最快，其次是带有硬件支持的浮点运算，而用软件来实现的浮点运算是非常慢的。因此，在编码时要遵守以下准则：
                      .尽量使用整数（char、short、int和long）的加法和减法。
                      .如果没有硬件支持，尽量避免使用乘法。
                      .尽量避免使用除法。
                      .如果没有硬件支持，尽量避免使用浮点数。
                      下图是一个例子，其中两段代码的功能完全一样，都是对一个结构体数组的各个元素进行初始化，但采用两种不同的方法来实现。下图（a）采用数组下标的方法，在定位第i个数组元素时，需要将i乘以结构体元素的大小，再加上数组的起始地址。下图（b）采用的是指针访问的方法，先把指针fp初始化为数组的起始地址，然后每访问完一个数组元素，就把fp加1，指向下一个元素。在一个奔腾4的PC上，将这两段代码分别重复10 700次，右边这段代码需要1ms，而左边这段代码需要2.13ms。
                      
                      算术运算性能优化的例子
 
       存储结构
               邻接矩阵表示法
               对于具有n个顶点的图G(V,E)来说，其邻接矩阵是一个n阶方阵，且满足
               
               由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有向图的邻接矩阵就不一定对称了。借助邻接矩阵易判定任意两个顶点之间是否有边（或弧）相连，并且容易求得各个顶点的度。
               网（赋权图）的邻接矩阵可定义为
               
               邻接链表表示法
               邻接链表指的是为图的每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的边（对于有向图是以vi为尾的弧）。邻接链表中的节点有表节点和表头节点两种类型。
               邻接矩阵和邻接链表表示法对有向图和无向图都适用。
 
       模板
        模板是Word 2003中采用dot为扩展名的特殊文档，它由多个特定的样式组合而成，能为用户提供一种预先设置好的最终文档外观框架，也允许用户加入自己的信息。新建一个文档时，用户可以选择系统提供的模板建立文档。用户也可以自建一个新的模板。
        当用户自己创建好一个文档后，若要保存为模板，只要在“另存为”对话框中选择保存类型为“文档模板（*.dot）”就可以了。使用模板的方法在如何创建一个空白文档时已经介绍，这里不再赘述。
 
       数组
               数组的定义及基本运算
               一维数组是长度固定的线性表，数组中的每个数据元素类型相同。n维数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
               设有n维数组A［b1，b2，…，bn］，其每一维的下界都为1，bi是第i维的上界。从数据结构的逻辑关系角度来看，A中的每个元素A［j1，j2，…，jn］（1≤ji≤bi）都被n个关系所约束。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言，这n个关系仍是线性的。
               以下面的二维数组A［m］［n］为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。
               
               可将A看作一个行向量形式的线性表：
               Am*n=［［a11a12…a1n］［a21a22…a2n］…［am1am2…amn］］
               也可将A看作列向量形式的线性表：
               Am*n=［［a11a21…am1］［a12a22…am2］…［a1na2n…amn］］
               数组结构的特点如下：
               （1）数据元素数目固定。一旦定义了一个数组结构，就不再有元素的增减变化。
               （2）数据元素具有相同的类型。
               （3）数据元素的下标关系具有上下界的约束且下标有序。
               在数组中通常做下面两种操作：
               （1）取值操作。给定一组下标，读其对应的数据元素。
               （2）赋值操作。给定一组下标，存储或修改与其相对应的数据元素。
               几乎所有的程序设计语言都提供了数组类型。实际上，在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是，不能对数组进行整体的运算，只能对单个数组元素进行运算。
               数组的顺序存储
               由于数组一般不作插入和删除运算，也就是说，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
               对于数组，一旦确定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置，也就是说，在数据的顺序存储结构中，数据元素的位置是其下标的线性函数。
               二维数组的存储结构可分为以行为主序（按行存储）和以列为主序（按列存储）两种方法，如下图所示。
               
               二维数组的两种存储方式
               设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为：
               Loc（aij）=Loc（a11）+（（i-1）×n+（j-1））×L
               同理，以列为主序优先存储的地址计算公式为：
               Loc（aij）=Loc（a11）+（（j-l）×m+（i-1））×L
 
       索引
        在数据库系统中，索引是一种可选结构，其目的是提高数据访问速度。利用索引可提高用户访问数据的速度，或直接从索引中独立检索数据。如果对索引的配置和使用进行了优化，那么索引能大大降低数据文件的I/O操作并提高系统性能。
        但是在为一个表创建索引之后，Oracle将自动维护这个索引。当用户在表中插入、更新或删除记录时，系统将自动更新与该表相关的索引。一个表可以有任意数量的索引，但一个表的索引越多，用户在该表中插入、更新或删除记录时所造成的系统开销也越大。其原因是无论何时更新表，系统都必须更新与之相关的索引。
        索引是建立在表的一个或多个字段之上的。索引的作用大小取决于该字段或字段集的选择性。所谓选择性，是指索引能降低数据集中的程度。如果表中与某个索引相关的字段值各不相同，那么该索引就有很好的选择性。一个选择性很差的索引的例子，是基于字段值仅为true/false的字段创建的索引，因为表中很多记录该字段的字段值都相同。一个索引可能只能帮助管理员降低检索的记录数，而不能惟一地确定一条记录。例如：如果为一个表的LastName字段创建了一个索引，现在用户需要搜索John Smith，那么这个索引将返回LastName字段值为Smith的所有记录，因而用户还不得不在返回的记录中搜索含John的记录。索引的选择性越好，就越有助于降低返回记录的数量，从而提高数据访问速度。下面介绍有效创建和使用索引的技巧和方法。
        . 索引和降低系统处理的数据量。
        索引的主要作用之一就是降低系统处理的数据量。对CPU使用和等待完成I/O操作的时间上，I/O操作引起的系统开销都是非常昂贵的。降低I/O操作可提高系统性能和处理能力。如果不使用索引，那么为了找到特定的数据，系统将不得不扫描表中的所有数据。
        例如如下查询语句：
        
        如果不使用索引，系统必须扫描整个emp表并检查表中每条记录的employee_id字段的值。如果emp表很大，那么这个操作可能意味着数量巨大的I/O读写和很长的处理时间。
        如果为emp表的employee_id字段创建了索引，那么系统将遍历该索引并找到用户所查询记录的ID。找到记录ID之后，只需一条额外的I/O操作就能检索到用户所需的数据。
        用于说明这个问题的最好例子，是只需查找一条记录的情况。在表的每条记录中，类似employee_id这样的字段的值可能在整个表中都是惟一的。这意味着查询结果值返回一条记录，这种查询的效率是非常高的。
        在某些情况下，索引必须返回大量数据。如下面的例子：
        
        这个查询语句很可能返回大量数据，因为索引操作返回了大量记录的ID，并且系统必须独立访问这些记录的ID，所以这种情况下，不使用索引可能比使用索引的效率更高，直接进行表扫描可能效率更高。不同情况下，采用哪种查寻方法更好，很大程度上取决于表的数据量和组织形式。
        对于不同的数据，在某些情况下位图索引可能非常有用，而在另外一些情况下，使用位图索引可能没有任何好处。
        . 索引和更新。
        如果对表创建了索引，那么更新、插入和删除表中的记录都将导致额外的系统开销。在系统提交这些操作之前，系统将会更新所有与该表相关的索引。这可能需要花费很长时间，并额外增加一定的系统开销。
        . 在字段选择性很低的情况下适用索引。
        在某些情况下，表中的某些字段的选择性可能很低。开发人员没必要为所有表创建索引，实事上，在某些情况下索引引起的问题比解决的问题更多。在很多情况下，需要反复试验，才能确定一个索引是否有助于提高系统性能。
        但是，位图索引能在字段选择性不高的情况下工作得很好。一个位图索引可以和其他位图索引联合使用，以降低系统检索的数据集。对于某些值为true/false、yes/no或其他小范围数据的字段，建立位图索引是非常合适的。请记住：位图索引所占用的空间，是随着与该索引相关的字段的不同值的数量的增加而增加的。
        如果决定创建一个索引，那么确定为哪些字段创建索引是非常重要的。对于不同的表，可能会选择一个或多个字段创建索引。可使用如下方法来确定在哪些字段上创建索引：
        ①选择那些最常出现在where子句中的字段。经常被访问的字段最可能受益于索引。
        ②经常用于连接表的字段是创建索引的必然候选字段。
        ③必须注意索引导致的查询语句性能的提高与更新数据时性能的降低之间的平衡。
        ④经常被修改的字段不适合创建索引，其原因是，更新索引将增加系统开销。
        在某些情况下，使用复合索引的效率可能比使用简单索引的效率更高。下面的一些例子说明了应当在何种情况下使用复合索引。
        ①某两个字段单独来看都不具有惟一性，但结合在一起却有惟一性，那么这种情况下，复合索引将工作得很好。例如：A字段和B字段都几乎没有惟一性值，但绝大多数情况下，字段A和B的某个特定组合却具有惟一性特点。那么在检索数据时，可在where子句重视and操作符来将这两个字段连接在一起。
        ②如果select语句中的所有值都位于复合索引中，那么Oracle将不会检索表，而直接从索引中返回数据。
        ③如果多个查询语句的where子句中作为查询条件的字段都不相同，但返回的记录相同，那么应当考虑利用这些字段创建一个复合索引。
        在创建索引之后，开发人员应当定期利用SQL TRACE工具或EXPLAIN PLAN来察看用户查询是否充分利用了索引。很有必要花费一定精力来试验使用索引和未使用索引在效率上的差别，以判断索引所耗费资源是否物有所值。
        应该删除那些不经常使用的索引。可使用alter index monitoring usage语句来跟踪索引的使用情况。还可以从系统表all_indexes、user_indexes和dba_indexes中查询用户访问索引的频率。
        如果为一个不适合创建索引的字段或表创建了索引，那么这可能会导致系统能力的下降。而如果创建的索引合理，那么这将降低系统的I/O操作并加快访问速度，从而大大提高系统性能。
   题号导航      2009年上半年 程序员 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第6题    在手机中做本题