[生活]数据结构笔试面试总结

《[生活]数据结构笔试面试总结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、线性表：线性表的定义和抽象数据类型：线性表可以是有序、无序表；抽象类型包括数据和操作两个部分，数据部分可以用顺序，链接，散列，索引任何一种方法存储到计算机中；线性表的顺序存储结构和链接存储结构(单链表，双向链表，带表头的附加结点的线性链表，循环链表)；操作：初始化单链表，删除单链衣中的所有结点，使Z成为一个空表，得到单链表的长度，检查单链表是否为空，得到单链表多种第及个结点中的元素，遍历一个单链表，从单链表中查找出等于给定值的笫一个元素，更新单链表中等于给定值的笫一个元素，向单链表中按照给定条件插入一个元索，从单链表屮删除符合给定条件的第一个元索，对单链表进

2、行数据排序.二、稀疏矩阵、集合、广义表稀疏矩阵：非零元索的个数远远小于零元索个数，对于每个非零元索的表示是通过三元组(主序：行号，辅序：列号，元素值)，采用顺序或链式方式存储。广义表：线性表的推广，表或表中表。采用动态链接结构。递归的数据结构。三、栈和队列栈：只允许在表的一端进行插入和删除运算，对栈进行运算的成为栈顶，另一端为栈底。向栈插入元素叫进栈，删除元素叫岀栈。栈是先进后岀。栈顶指针为-1表示栈为空，进栈，栈顶指针+1,III栈，栈顶指针-1•递归数据结构。队列：在一端进行插入，在另一端进行删除，插入的一端叫做队尾(rear),进行删除的—端叫做队首(fr

3、ont),先进先出。四、树非线性数据结构。结点的度和树的度；分支结点和叶子结点；孩子结点和双亲结点；结点的层数和树的深度;有序树和无序树；森林；树的性质；二义树：度为2的有序树。存储结构：顺序存储，数组；链接存储结构：指针；二叉树的遍历：前序遍历：DLR中序遍历：LDR后序遍历:LRD树的遍历：先根遍历，后根遍历，按层遍历五:图顶点的度依附于顶点的边的数目记为td(v)；顶点的出度od(v)；顶点的入度id(v):td(v)=od(v)+id(v)；性质：1n个顶点的无向图最多有n(n-1)/2条边；2n个顶点的冇向图最多冇n(n-1)条边；六：查找：查找：1、

4、顺序查找2、二分查找3、分块杳找4、数表的动态查找(二义排序树查找、平衡二义树AVL树、B树、B+树)5、哈希查找查找冇静态查找和动态查找两种，静态查找只在数据结构里查找是否存在某个记录而不改变数据结构。实现静态查找的数据结构称为静态查找表；动态查找要在查找过程屮插入数据结构中不存在的记录，或者从数据结构中删除已存在的记录。实现动态查找的数据结构称为动态査找表。衡量查找算法的标准是平均查找长度，它是指在查找过程中进行的关键码比较次数的平均值。实现动态查找的数据结构称为动态查找表。静态杳找表的查找方法主要有顺序查找、折半查找和索引杳找等。顺序查找不要求查找表中的记

5、录有序，效率不是很高，适合于记录不是很多的情况。折半查找耍求查找表中的记录冇序，查找效率很高，适合于记录比较多的悄况。索引查找要求查找表分段冇序，适合于记录非常多的情况。动态查找表主要介绍了二叉排序树。二叉排序树是一棵二叉树，其左了树结点关键码的值小于根结点关键码的值，右了树结点关键码的值人于根结点关键码的值。二叉排序树上的操作主要冇查找、插入和删除等操作。在哈希表中查找记录不需婆进行关键码的比较，而是通过哈希函数确定记录的存放位置。哈希函数的构造方法很多，主要有直接定址法、除留余数法、数字分析法和平方取中法等。由于同义词会产牛哈希冲突，解决哈希冲突的方法主要有

6、开放地址法和链表法等，其屮开放地址法主要有线性探测法和二次探测法等。查找乂称检索，是在程序设计中対数据结构中的记录进行处理时经常采用的一种操作。同排序一样，查找是对关键码进行处理，关键码分为主关键码和次关键码，以主关键码进行的杏找是最经常、也是最主要的杳找。1.顺序杏找法即从第一个元素顺序到最后一个元素依次为待查的值进行比较，如果相等，查找成功，否则继续比较，直到所有元素都比较过了，如果还没有匹配的值，查找失败。查找适用于数据量少、不要求已经排序的数据，它的时间复杂度为0(N)；2.二分查找乂称折半查找，适用于数据量大、己经排序的数据，它的时I'可复杂度为0(L

7、og2(N))o二分查找的基本思想是(设R[low..high]是当前的查找区间):(1)首先确定该区间的中点位置:mid=(low+high)/2(2)然后将待查的K值与R[mid],key比较：若相等,则查找成功并返回此位置,否则须确定新的查找区间，继续二分查找，具体方法如下：①若R[mid]・key>K,贝9由表的有序性可知R[mid..nJ.keys均大于K,因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[l..mid-1]中，故新的杳找区间是左子表R[l..mid-1]o②类似地，若R[mid].key

8、id的右子表R[mid+