软考软件设计师专题讲义九：数据结构相关算法

　　u 散列表的查找

　　散列表又称杂凑表，是一种非常实用的查找技术。它的原理是在结点的存储位置和它的关键码间建立一个确定的关系，从而让查找码直接利用这个关系确定结点的位置。其技术的关键在于解决两个问题。

　　I. 找一个好的散列函数

　　II. 设计有效解决冲突的方法

　　常见的散列函数有：

　　I. 质数除取余法

　　II. 基数转换法

　　III. 平方取中法

　　IV. 折叠法

　　V. 移位法

　　常见的解决冲突的方法有：

　　I. 线性探查法

　　II. 双散列函数法

　　III. 拉链法

　　假设HASH表的地址集为0-n-1，冲突是指由关键字得到的HASH地址的位置上已经存在记录，则处理冲突就是为该关键字的记录找到另一个空的HASH地址用于存放。

　　处理冲突的方法：

　　开放地址法(线性探查法)：二次地址=(一次地址+增量序列) MOD 散列表长度M

　　再HASH法(双散列函数法)：使用不同的散列函数计算，互相作为补偿;

　　二次地址=RH(key) R和H都是散列函数

　　拉链法(链地址法)：设立一个指针数组，初始状态是空指针，HASH地址为i的记录都插入到指针数组中第i项所指向的链表中，保持关键字有序。

　　建立一个公共的溢出区：将所有冲突的关键字和记录都添入到溢出区。

　　HASH查找分析： HASH的查找长度与查找表的长度无关，只与装添因子有关

　　装添因子=表中添入的记录数/HASH的长度

　　4. 重点、难点解析

　　数据结构的相关知识点在软考中是经常出现的，无论是上午的客观题，还是下午的程序填空，都会涉及，而且考试的题型除了一般的概念和常识以外，还涉及各种算法，出题十分灵活。因此对这部分的复习一定要非常重视。这里我们总结了数据结构部分的一些比较重要的要点。

　　n 链式存储结构

　　不管是线性表、栈，还是队列，都会使用链式存储结构。对于链式存储结构的操作与顺序存储结构不一样，因此我们需要熟悉它们的相关算法。如：

　　u 对于链式存储的线性表，它的插入、删除和查找算法。

　　u 对于链接存储栈，它的进栈、出栈算法

　　u 对于链接存储队列，它的进队、出队算法

　　另外，对于栈和队列的一些实际应用的算法也需要关心，特别在下午的程序填空的考试中，经常会碰到类似的算法。

　　关于图的概念和相关算法很多，这对高程软考来说，也是一个重点。

　　除了我们前面罗列的一些关于的图的基本概念以外，首先我们必须对图的几种存储结构要十分的清楚，因为这实际上是研究图的相关问题和算法的基础。包括：

　　u 邻接矩阵

　　u 邻接表

　　u 十字链表

　　u 邻接多重表

　　对于图的两种遍历算法(深度优先和广度优先)实际可以参考树的有关遍历算法，这样理解起来相对简单。

　　而对于图的有关算法，如求最小代价生成树、求最短路径、拓扑排序和求关键路径等，这是数据结构中的难点。不过一般来说，软考中很难直接考到。因此，大家在复习的时候主要抓住涉及算法的相关概念、算法的基本原理以及算法的复杂度这几个方面。当然，有时间最好参看一下相关资料，对它的具体实现仔细看看，这对理解其算法的核心思想当然会事半功倍。

　　　　　　　计算机软考软件设计师练习试题及答案解析汇总