考研数据结构复试题

作者: 是归人不是过客 | 来源:发表于2020-07-03 16:39 被阅读0次

1、数组和链表的区别

从逻辑结构来看：

a) 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。

b) 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素

从内存存储来看：

a) (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小

b) 链表从堆中分配空间, 自由度大但是申请管理比较麻烦

从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反，如果需要经常插入和删除元素就需要用链表数据结构了。

从访问方式类看，数组在内存中是连续的存储，因此可以利用下标索引进行访问；链表是链式存储结构，在访问元素时候只能够通过线性方式由前到后顺序的访问，所以访问效率比数组要低。

2.排序算法有哪些？

插入排序：直接插入排序、折半排插入序、希尔排序

交换排序：冒泡排序、快速排序

选择排序：简单选择排序、堆排序

归并排序

基数排序

A）事件复杂度

时间复杂度来说：

(1)平方阶(O(n2))排序　　各类简单排序:直接插入、直接选择和冒泡排序； (2)线性对数阶(O(nlog2n))排序　　快速排序、堆排序和归并排序； (3)O(n1+§))排序,§是介于0和1之间的常数。

希尔排序 (4)线性阶(O(n))排序　　基数排序，此外还有桶、箱排序。

稳定性：

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

对比.png

2、邻接矩阵和邻接表

邻接矩阵表示法：在一个一维数组中存储所有的点，在一个二维数组中存储顶点之间的边的权值

邻接表表示法：图中顶点用一个一维数组存储，图中每个顶点vi的所有邻接点构成单链表

对比

1）在邻接矩阵表示中，无向图的邻接矩阵是对称的。矩阵中第 i 行或第 i 列有效元素个数之和就是顶点的度。

在有向图中第 i 行有效元素个数之和是顶点的出度，第 i 列有效元素个数之和是顶点的入度。

2）在邻接表的表示中，无向图的同一条边在邻接表中存储的两次。如果想要知道顶点的度，只需要求出所对应链表的结点个数即可。

有向图中每条边在邻接表中只出现一次，求顶点的出度只需要遍历所对应链表即可。求入度则需要遍历其他顶点的链表。

3）邻接矩阵与邻接表优缺点：

邻接矩阵的优点是可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边。而其缺点是如果顶点之间的边比较少，会比较浪费空间。因为是一个 n∗n 的矩阵。

而邻接表的优点是节省空间，只存储实际存在的边。其缺点是关注顶点的度时，就可能需要遍历一个链表。

data1.png

3、 简述快速排序过程

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

4、解决哈希冲突的方法

1）线性探测法

2）平方探测法

3）伪随机序列法

4）拉链法

5、KMP算法

在一个字符串中查找是否包含目标的匹配字符串。其主要思想是每趟比较过程让子串先后滑动一个合适的位置。当发生不匹配的情况时，不是右移一位，而是移动（当前匹配的长度– 当前匹配子串的部分匹配值）位。

6、介绍一下各种树：
a)二叉树：左右子树的度都不超过二
b)二叉排序树：在二叉树的基础上，左子树均小于根，根均小于右子树
c)满二叉树：深度为k且包含（2的k次幂）-1个结点的二叉树。
d)满二叉树：深度为k，有n个结点的二叉树，其中每个结点都与深度为k的满二叉树中编号从1到n的结点一一对应。
e)线索二叉树：设置两个标识来标记左右指针指的是左右孩子还是前驱后继节点
LTag 0：指向左孩子 1：指向前驱
RTag 0：指向右孩子 2：指向后继
f)平衡二叉树：左右子树的高度差的绝对值小于等于1（即：平衡因子只能得-1、0、1）
g)哈夫曼树：又称为最优树，是一类带权路径长度最短的树。权值大小排序。
补充：
二叉树的存储：顺序存储结构（满二叉树、完全二叉树）
链式存储结构（一般二叉树）
7、树的存储：
双亲表示法
孩子表示法
孩子兄弟表示法
8、树的遍历
先序中序后序三种。递归实现。