首页 > 知识点讲解
       数据结构基础
知识路径: > 计算机系统基础知识 > 软件基础知识 > 
被考次数:17次     被考频率:高频率     总体答错率:44%     知识难度系数:     
考试要求:熟悉      相关知识点:30个      
               数据结构
               根据数据元素之间关系的不同特性,通常有下列4类基本的逻辑结构,即集合结构、线性结构、树形结构、图形结构。
               1)线性结构
               线性表是最常用且最简单的一种数据结构。线性表中除第一个元素外,每个元素均只有一个直接前驱;除最后一个元素外,每个元素都只有一个直接后继。
               栈是限定仅在表尾进行插入或删除操作的线性表,是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。
               队列是一种先进先出(FIFO)的线性表,它只允许在表的一端进行插入,而在另一端删除元素。
               2)树
               树是nn≥0)个互不相交的有限集,当n=0时称为空树。在一棵非空树中,有且仅有一个节点称为根节点;当n>1时,其余的节点可分为若干个不相交的集合,其中每一个集合本身又是一棵树,这些集合称为根节点的子树。
               3)图
               图是由两个集合VE组成的二元组,记为G=(V, E),其中V是顶点的非空有限集合,E是图中边的有限集合。
               查找
               1)顺序查找
               顺序查找又称线性查找,顺序查找的过程是从线性表的一端开始,依次逐个与表中元素的关键字值进行比较,如果找到其关键字与给定值相等的元素,则查找成功;若表中所有元素的关键字与给定值比较都不成功,则查找失败。
               2)折半查找
               折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较,若两者相等,则查找成功;若给定值小于该元素的关键字,那么选取中间位置元素关键字值小的那部分元素作为新的查找范围,然后继续进行折半查找;如果给定值大于该元素的关键字,那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围,然后继续进行折半查找,直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
               3)分块查找
               在分块查找过程中,首先将表分成若干块,每一块中关键字不一定有序,但块之间是有序的。此外,还建立了一个索引表,索引表按关键字有序。分块查找过程需分两步进行:先确定待查记录所在的块;然后在块中顺序查找。
               4)哈希表及其查找
               根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。
               排序
               1)简单排序
               简单排序包括直接插入排序、冒泡排序、简单选择排序等。
               2)希尔排序
               希尔排序的基本思想是:先将整个待排记录序列分割成若干序列,然后分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。
               3)快速排序
               快速排序是对冒泡排序的一种改进。先通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后分别对这两部分记录继续进行排序,以达到整个序列有序。
               4)堆排序
               堆排序的基本思想(小根堆)是:对一组待排序记录的关键字,首先把它们按堆的定义排成一个堆序列,从而输出堆顶的最小关键字;然后将剩余的关键字再调整成新堆,便得到次小的关键字,如此反复进行,直到全部关键字排成有序序列。
               5)归并排序
               归并排序是不断将多个小而有序的序列合成一个大而有序的序列的过程。
               6)基数排序
               基数排序的思想是按组成关键字的各个数位的值进行排序,它是分配排序的一种。
 
 相关知识点:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。


工作时间:9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2023 All Rights Reserved 软考在线版权所有