免费智能真题库 > 历年试卷 > 程序员 > 2016年下半年 程序员 上午试卷 综合知识
  第41题      
  知识点:   哈希表   排序算法   内存   日志文件   搜索引擎   索引
  关键词:   内存   搜索引擎        章/节:   常用算法       

 
索引会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的10个查询串,且要求使用的内存不能超过1GB。以下各方法中,可行且效率最高的方法是(41)。
 
 
  A.  将一千万个查询串存入数组并进行快速排序,再统计其中每个查询串重复的次数
 
  B.  将一千万个查询串存入数组并进行堆排序,再统计其中每个查询串重复的次数
 
  C.  利用哈希表保存所有的查询串并记下每个查询串的重复次数,再利用小根堆选出重复次数最多的10个查询串
 
  D.  利用哈希表保存所有的查询串并记下每个查询串的重复次数,再利用大根堆选出重复次数最多的10个查询串
 
 
 

 
  第41题    2013年上半年  
   44%
在一棵非空的二叉排序树中,关键字最大的结点的(41)。
  第42题    2012年下半年  
   42%
若采用链地址法对关键字序列(74, 10, 23, 6, 45, 38, 18)构造哈希表(或散列表),设散列函数为H(Key)=Key%7 (%表示整除取余运算..
  第42题    2012年上半年  
   46%
以下关于顺序查找和二分查找的叙述中,正确的是(42)。
 
  第35题    2017年上半年  
   54%
采用()算法对序列{18,12,10,11,23,2,7}进行一趟递增排序后,其元素的排列变为{12,10,11,18,2,7,23}。
  第42题    2016年上半年  
   39%
对n个记录进行非递减排序,在第一趟排序之后,一定能把关键码序列中的最大或最小元素放在其最终排序位置上的排序算法是(42)。<..
  第38题    2011年上半年  
   36%
设递增序列A为a1,a2,…,an,递增序列B为b1,b2…,b
   知识点讲解    
   · 哈希表    · 排序算法    · 内存    · 日志文件    · 搜索引擎    · 索引
 
       哈希表
        1)哈希表的定义
        根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。当选择了某个散列函数后,不同的关键字可能与同一个散列地址相对应,这种现象称为冲突。
        对于哈希表,主要考虑两个问题:一是如何构造哈希函数,二是如何解决冲突。
        2)哈希函数的构造方法
        常用的哈希函数的构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。
        3)处理冲突的方法
        解决冲突就是为出现冲突的关键字找到另一个"空"的哈希地址。常见的冲突处理方法有:开放地址法、链地址法、再哈希法等。
 
       排序算法
               简单排序
               简单排序包括直接插入排序、冒泡排序、简单选择排序等方法。
               1)直接插入排序
               直接插入排序的基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。
               2)冒泡排序
               首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序(即 r[1].key>r[2].key),则交换两个记录,接着比较第二个记录和第三个记录的关键字。依次类推,直至第n-1个记录和第n个记录的关键字进行过比较为止。这个过程称为第一趟冒泡排序,使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序,对前n-1个记录进行同样的操作,结果是使关键字次大的记录被安置到第n-1个记录的位置上。当进行完第n-1趟冒泡排序时,所有记录都已有序排列。
               3)简单选择排序
               简单选择排序的基本思想是:在进行每趟排序时,从无序的记录中选择出关键字最小(或最大)的记录,将其插入到有序序列(初始时为空)的尾部。
               希尔排序
               希尔排序又称"缩小增量排序",是对直接插入排序方法的改进。希尔排序的基本思想是:先将整个待排记录序列分割成若干序列,然后分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。
               快速排序
               快速排序是对冒泡排序的一种改进。先通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后分别对这两部分记录继续进行排序,使得整个序列有序。
               堆排序
               1)堆的概念
               对于n个元素的关键字序列{k1,k2,…,kn},当且仅当所有关键字都满足下列关系时称其为堆:
               
               从序列元素间的关系来看,堆是一棵完全二叉树的层次序列。显然,堆顶元素为序列中n个元素的最小值(或最大值)。若堆顶为最小元素,则称为小根堆;若堆顶为最大元素,则称为大根堆。
               2)堆排序的基本思想(小根堆)
               对一组待排序记录的关键字,首先把它们按堆的定义排成一个堆序列,从而输出堆顶的最小关键字,然后将剩余的关键字再调整成新堆,便得到次小的关键字,如此反复进行,直到全部关键字排成有序序列。
               归并排序
               归并排序是不断将多个小而有序的序列合成一个大而有序的序列的过程。其中最常用的归并排序是二路归并排序,它是将整个序列中的元素进行分组,相邻的两个元素为一组,然后分别为每个小组进行排序,随后将两个相邻的小组合成一个组,继续进行组内排序;直到所有元素被合并成一个组内,并使组内元素有序,此时排序结束。
               基数排序
               基数排序的思想是按组成关键字的各个数位的值进行排序,它是分配排序的一种。基数排序把一个关键字Ki看成一个d元组,即
               
               其中称为最高有效位,@称为最低有效位。基数排序可以从最高有效位开始,也可以从最低有效位开始。
               基数排序的基本思想是:设立r个队列(r为基数),队列的编号为0, 1, 2, …,r-1。首先按最低有效位的值,把n个关键字分配到这r个队列中;然后从小到大将各队列中的关键字再依次收集起来;接着再按次低有效位的值把刚收集起来的关键字再分配到r个队列中。重复上述收集过程,直至最高位有效。这样得到了一个从小到大有序的关键字序列。
 
       内存
        除了CPU,内存也是影响系统性能的最常见的瓶颈之一。看系统内存是否够用的一个重要参考就是分页文件的数目,分页文件是硬盘上的真实文件,当操作系统缺少物理内存时,它就会把内存中的数据挪到分页文件中去,如果单位时间内此类文件使用频繁(每秒个数大于5),那就应该考虑增加内存。具体考察内存的性能的参数包括内存利用率、物理内存和虚拟内存的大小。
 
       日志文件
        事务日志是针对数据库改变所做的记录,它可以记录针对数据库的任何操作,并将记录结果保存在独立的文件中,这种文件就称为日志文件。对于任何一个事务,事务日志都有非常全面的记录,根据这些记录可以将数据文件恢复成事务前的状态。从事务动作开始,事务日志就处于记录状态,事务执行过程中对数据库的任何操作都记录在内,直到用户提交或回滚后才结束记录。
        日志文件是用来记录对数据库每一次更新活动的文件,在动态备份方式中,必须建立日志文件,后援副本和日志文件综合起来才能有效地恢复数据库;在静态备份方式中,也可以建立日志文件,当数据库毁坏后可重新装入后援副本把数据库恢复到备份结束时刻的正确状态,然后利用日志文件,把已完成的事务进行重做处理,对故障发生时尚未完成的事务进行撤销处理。这样不必重新运行那些已完成的事务程序就可把数据库恢复到故障前某一时刻的正确状态。
        例如,在热备份期间的某时刻t1,系统把数据A=100备份到了磁带上,而在时刻t2,某一事务对A进行了修改使A=200。备份结束,后备副本上的A已是过时的数据了。为此,必须把备份期间各事务对数据库的修改活动登记下来,建立日志文件。这样,后备副本加上日志文件就能把数据库恢复到某一时刻的正确状态。
        事务在运行过程中,系统把事务开始、事务结束(包括COMMIT和ROLLBACK),以及对数据库的插入、删除、修改等每一个操作作为一个登记记录存放到日志文件中。每个记录包括的主要内容有:执行操作的事务标识、操作类型、更新前数据的旧值(对插入操作而言此项为空值)、更新后的新值(对删除操作而言此项为空值)。登记的次序严格按并行事务操作执行的时间次序,同时遵循“先写日志文件”的规则。写一个修改到数据库中和写一个表示这个修改的日志记录到日志文件中是两个不同的操作,有可能在这两个操作之间发生故障,即这两个写操作只完成了一个,如果先写了数据库修改,而在日志记录中没有登记这个修改,则以后就无法恢复这个修改了。因此,为了安全,应该先写日志文件,即首先把修改记录写到日志文件上,然后再写数据库的修改。这就是“先写日志文件”的原则。
 
       搜索引擎
        Internet是一个庞大的信息海洋,要想从中找出自己所需的信息并不是一件容易的事,应运而生的搜索引擎可帮了我们的大忙。
        搜索引擎是指为用户提供信息检索服务的程序,通过服务器上特定的程序把Internet上的所有信息分析、整理并归类,以帮助用户在Internet中搜索所需要的信息。当用户通过搜索引擎查找信息时,搜索引擎就会对用户的需求产生响应,并根据查找的关键字检索数据库,最后将与搜索标准匹配的站点列表返回给用户。用户可以从列表中选择需要的网站,单击链接即可进入相应的页面。搜索引擎也是一类网站,它们一般都具备分类主题查询和关键字查询两种功能:
        .按内容分类逐级检索
        分类检索是从搜索首页按照树型的主题分类逐层单击来查找所需信息的方法。
        .使用关键字检索
        关键字检索就是由用户指定一些词语(这些词语称为关键字),搜索引擎自动搜索和这些词语相关的网站,并按照匹配的程度由高到低排列输出给用户。使用关键字检索的核心是如何选择合适的关键字,不同的搜索引擎提供的查询方法并不完全相同。
        对于经常上网查阅资料的用户来说,记住一些好的搜索网站是很重要的,在这里给大家介绍几个常用的搜索网站。
        .http://www.google.com/ google搜索引擎
        .http://dir.sohu.com/搜狐分类搜索引擎
        .http://cn.yahoo.com/中文雅虎
        .http://search.sina.com.cn/新浪搜索
        .http://search.163.com/网易搜索引擎
        .http://www.baidu.com/百度搜索
 
       索引
        在数据库系统中,索引是一种可选结构,其目的是提高数据访问速度。利用索引可提高用户访问数据的速度,或直接从索引中独立检索数据。如果对索引的配置和使用进行了优化,那么索引能大大降低数据文件的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操作并加快访问速度,从而大大提高系统性能。
   题号导航      2016年下半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第41题    在手机中做本题