首页 考试吧论坛 Exam8视线 考试商城 网络课程 模拟考试 考友录 实用文档 求职招聘 论文下载
2011中考 | 2011高考 | 2012考研 | 考研培训 | 在职研 | 自学考试 | 成人高考 | 法律硕士 | MBA考试
MPA考试 | 中科院
四六级 | 职称英语 | 商务英语 | 公共英语 | 托福 | 雅思 | 专四专八 | 口译笔译 | 博思 | GRE GMAT
新概念英语 | 成人英语三级 | 申硕英语 | 攻硕英语 | 职称日语 | 日语学习 | 法语 | 德语 | 韩语
计算机等级考试 | 软件水平考试 | 职称计算机 | 微软认证 | 思科认证 | Oracle认证 | Linux认证
华为认证 | Java认证
公务员 | 报关员 | 银行从业资格 | 证券从业资格 | 期货从业资格 | 司法考试 | 法律顾问 | 导游资格
报检员 | 教师资格 | 社会工作者 | 外销员 | 国际商务师 | 跟单员 | 单证员 | 物流师 | 价格鉴证师
人力资源 | 管理咨询师考试 | 秘书资格 | 心理咨询师考试 | 出版专业资格 | 广告师职业水平
驾驶员 | 网络编辑
卫生资格 | 执业医师 | 执业药师 | 执业护士
会计从业资格考试会计证) | 经济师 | 会计职称 | 注册会计师 | 审计师 | 注册税务师
注册资产评估师 | 高级会计师 | ACCA | 统计师 | 精算师 | 理财规划师 | 国际内审师
一级建造师 | 二级建造师 | 造价工程师 | 造价员 | 咨询工程师 | 监理工程师 | 安全工程师
质量工程师 | 物业管理师 | 招标师 | 结构工程师 | 建筑师 | 房地产估价师 | 土地估价师 | 岩土师
设备监理师 | 房地产经纪人 | 投资项目管理师 | 土地登记代理人 | 环境影响评价师 | 环保工程师
城市规划师 | 公路监理师 | 公路造价师 | 安全评价师 | 电气工程师 | 注册测绘师 | 注册计量师
缤纷校园 | 实用文档 | 英语学习 | 作文大全 | 求职招聘 | 论文下载 | 访谈 | 游戏

2011计算机等考二级公共基础知识讲义:第1章(7)

来源:考试吧Exam8.com) 2011-2-14 11:42:17 考试吧:中国教育培训第一门户 模拟考场
考试吧编辑整理“2011计算机等考二级公共基础知识辅导讲义”,供大家复习使用。

  点击进入:2011计算机等考二级公共基础知识讲义汇总>>

  1.7 查找技术

  查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素。

  查找结果:(查找成功:找到;查找不成功:没找到。)

  平均查找长度:查找过程中关键字和给定值比较的平均次数。

  1、顺序查找

  基本思想:从表中的第一个元素开始,将给定的值与表中逐个元素的关键字进行比较,直到两者相符,查到所要找的元素为止。否则就是表中没有要找的元素,查找不成功。

  在平均情况下,利用顺序查找法在线性表中查找一个元素,大约要与线性表中一半的元素进行比较,最坏情况下需要比较n次。

  顺序查找一个具有n个元素的线性表,其平均复杂度为O(n)。

  下列两种情况下只能采用顺序查找:

  1)如果线性表是无序表(即表中的元素是无序的),则不管是顺序存储结构还是链式存储结构,都只能用顺序查找。

  2)即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。

  2、二分法查找

  思想:先确定待查找记录所在的范围,然后逐步缩小范围,直到找到或确认找不到该记录为止。

  前提:必须在具有顺序存储结构的有序表中进行。

  查找过程:

  1)若中间项(中间项mid=(n-1)/2,mid的值四舍五入取整)的值等于x,则说明已查到;

  2)若x小于中间项的值,则在线性表的前半部分查找;

  3)若x大于中间项的值,则在线性表的后半部分查找。

  特点:比顺序查找方法效率高。最坏的情况下,需要比较log2n次。

  二分法查找只适用于顺序存储的线性表,且表中元素必须按关键字有序(升序)排列[注释1] 。对于无序线性表和线性表的链式存储结构只能用顺序查找。在长度为n的有序线性表中进行二分法查找,其时间复杂度为O(log2n)。(注释1:允许相邻元素值相等。)

  1.8 排序技术

  排序是指将一个无序序列整理成按值非递减顺序排列的有序序列,即是将无序的记录序列调整为有序记录序列的一种操作。

  1、交换类排序法(方法:冒泡排序,快速排序)。

  2、插入类排序法(方法:简单插入排序,希尔排序)。

  3、选择类排序法(方法:简单选择排序,堆排序)。

  总结:各种排序法比较

2011计算机等考二级公共基础知识讲义:第1章(7) 

  本章应考点拨:本章内容在笔试中会出现5-6个题目,是公共基础知识部分出题量比较多的一章,所占分值也比较大,约10分。

  相关推荐:

  2011计算机等考二级公共基础知识要点汇总

  2010年9月计算机等级考试成绩查询时间汇总

  2011年上半年计算机等级考试报名时间汇总

文章搜索
版权声明:如果计算机等级考试网所转载内容不慎侵犯了您的权益,请与我们联系800@exam8.com,我们将会及时处理。如转载本计算机等级考试网内容,请注明出处。