升研教育考研频道为23考研、24考研的同学们整理了“计算机考研备考资料：数据结构（查找表）”的相关信息，希望对正在备考的你有所帮助。考研复习效率不高怎么办？自己备考抓不住重点？想报考985/211等热门院校，但是没把握？升研教育推出考研集训营，全日制封闭式面授，10余年授课经验的老师，浓厚的学习氛围助你冲击目标、一战上研！

计算机考研专业课一般涉及到四个科目：数据结构、计算机组成原理、操作系统、计算机网络 ，知识点繁多，复习起来也并不失分容易，为了帮助大家复习，本篇为大家整理了一些数据结构中的知识点，供大家参考。

查找表

1、查找表及有关概念：是一种以集合为逻辑结构，以查找为核心的运算，同时包括其它运算的数据结构。

查找表可分为静态查找表(不插入和删除)和动态查找表(进行插入和删除)

关键字：用来标识数据元素的数据项称为关键字，简称键。该数据项的值称为键值。

查找：根据给定的某个值K，在查找表中寻找一个其键值等于K的数据元素。若找到一个这样的数据元素，则称查找成功，否则称查找不成功。

2、顺序表上的查找：以顺序表作为查找表的存储结构。顺序查找算法如下

顺序查找算法的平均查找长度为：ASL=(n+1)/2(SS等概率)

3、有序表上的查找:以顺序表作为查找表的存储结构，且按关键字有序(升序)。

4、索引顺序表上的查找：索引顺序表是按索引存储方式构造的一种存储结构。

一个索引顺序表由两部分组成：一个顺序表和一个索引表。

索引顺序表的特点：

①顺序表中的数据元素“按块有序”;

②索引表反映了这些“块”的有关特性。

在索引顺序表上的查找分两个阶段：

①确定待查元素所在的块;

②在块内查找待查的元素。

所以称为分块查找。分块查找的平均查找长度为: ASL=(n/s+s)/2+1 ;当s (块内元素的个数)取n的平方根时，ASL 最小。

5、二叉排序树或者二叉查找树：一棵二叉排序树或者是一棵空树，或者是一棵同时满足下列条件的二叉树

①若它的左子树不空，则左子树上所有结点的键值均小于它的根结点的键值;

②若它的右子树不空，则右子树上所有结点的键值均大于它的根结点的键值;

③它的左、右子树也分别为一棵二叉排序树。

二叉排序树的性质：中根遍历一棵二叉排序树所得的结点访问序列是键值的递增序列。

在二叉排序树上进行查找，若查找成功，则是从根结点出发走了一条从根结点到待查结点的路径;若查找不成功，则是从根结点出发走了一条从根结点到某个叶子的路径。

在随机情况下，含有n个结点的二叉排序树的平均查找长度为: 1+4log₂n

6、平衡二叉排序树：(简称AVL树)或者是一棵空树，或者是任一结点的左子树与右子树的高度至多差1的二叉排序树。对于二叉排序树上的任何结点，其平衡因子定义为该结点左子树的高度减去该结点右子树的高度。

7、散列表(哈希表):“散列”既是一种存储方式，又是一种查找方法。这种查找方法称为散列查找。

按散列存储方式构造的存储结构称为散列表。散列函数是一种将键值映射为散列表中的存储位置的函数。由散列函数决定的数据元素在列表中的存储位置称为散列地址。散列的基本思想是通过由散列函数决定的键值与散列地址之间的对应关系来实现存储组织和查找运算。

设有散列函数H和键值k_i、k_j，若k_i≠k_j，且H(k_i)=H(k_j)，则称k_i、k_j是(相对于H的)同义词。对应的两元素X_i和X_j要存入同一个散列表，这种情况称为冲突。

散列函数的构造方法：①数字分析法、②除余法、③平方取中法、④基数转换法、⑤随机数法

开散列表的组织方法：设选定的散列函数为H, H的值域为0~n-1。设置一个“地址向量”pointer HP[n], 其中的每个指针HP[i]指向一个单链表，该单链表用于存储所有散列地址为i的数据元素，即所有散列地址为i的同义词。每一个这样的单链表称为一个同义词子表。由地址向量以及向量中每个指针所指向的同义词子表构成的存储结构称为开散列表。

闭散列表：是一个一维数组，将所有的数据元素存入闭散列表的不同存储结点中。解决冲突的方法是在需要时为每个键值K生成一-个散列地址序列d₀、d₁、d₂、 .. d_i、.. d_m-1。其中d₀=H(K)是K的散列地址，所有d_i (0<i<m)是后继散列地址。当插入键值为K的元素X时，若d₀=H(K)上的结点已被别的数据元素占用，则按上述地址序列依次探测，将找到的第一个空闲位置d,作为X的存储位置。构造后继散列地址序列的方法也就是处理冲突的方法。有以下几种常用方法:

①线性探测法：后继散列地址序列为d+1, d+2, ...， m-1,0,1, ...,d-1

堆积：非同义词之间对同一个散列地址的争夺现象成为堆积。以下两种方法可以减少堆积。

②二次探测法：后继散列地址序列为(d₀+1²)%m， (d₀-1²)%m， (d₀+2²)%m， (d₀-2²)%m， ...

③多重散列法：设立多个散列函数H。

④公共溢出区法：此时，散列表由基本表和溢出表两个表组成。插入首先在基本表上进行，若发生冲突, 则将同，义词存入溢出表。

散列表的装填因子: a =表中填入的数据元素数/表的容量。

例如:设散列表的容量为14，散列函数是H(key)=key % 11，表中已存储有4个结点如下:

        0     1        2      3       4      5        6      7       8       9      10    11    12    13

用线性探测法处理冲突，则关键字为48的结点的地址是    8    

用二次探测法处理冲突，则关键字为48的结点的地址是    3