文章

7

粉丝

7

获赞

13

访问

35736

头像
计算机考研复试笔记——数据结构篇
数据结构
发布于2021年4月8日 23:22
阅读数 7062

1. 数据结构是研究计算机的操作对象的逻辑结构和物理结构以及在结构上定义的操作,逻辑结构包括线性结构和非线性结构,物理结构包括顺序结构、链式结构、索引结构和散列结构。

2. 时间复杂度:时间复杂度是指执行算法所需的计算工作量,所以将算法中基本操作的运行次数作为时间复杂度的度量,比如循环的层数和递归的深度等。

3. 算法:算法是对特定问题求解步骤的一种描述,是一系列输入转换为输出的计算步骤。算法的五个特性:输入、输出、有穷性、确定性、可行性。

4. 循环和递归:递归代码简单清晰,便于检查正确性,但递归有时可能会出现堆栈溢出的现象,执行效率较低;循环执行效率高,但不一定能解决所有问题,有时候可以用递归解决的问题不一定能用循环解决。

5. 贪心算法、动态规划以及分治法:贪心算法是自顶向下的算法,但它不从整体角度考虑而是考虑局部最优解,因此贪心算法得到的结果不一定是全局最优的;动态规划是自底向上的算法,将一个大问题分解成有重复的小问题,并把一些问题的解记录下来,这样可以减少重复计算,在求解子问题的过程中不断保留最优解,丢弃其他局部解,最后得到答案;分治法也是将一个大问题分解成若干个小问题,不过这些小问题和大问题有相同的结构,通过递归解决小问题,再合并结果成为大问题的解。

6. 在链表中设置头结点:作用是为了链表操作时,可以对空表、非空表以及对首元素结点进行统一处理。

7. 数组和链表的区别:数组的长度是固定的,不能适应数据动态增减的情况,即数组的大小一旦定义就不能改变。链表的长度是可以任意变化的,可以适应数据动态增减的情况,且可以方便插入删除数据。数组在内存中是连续存储的,因此可以利用下标索引进行访问,链表是链式存储结构,只能通过线性方式进行访问。

8. 静态链表:用数组来代替指针,来表述单链表,数组元素包含两个数据域,第一个数据域存放数据,第二个数据域存放后继元素在数组中的下标。

9. 循环链表的优点:从任一结点出发都可访问到表中的所有结点。

10. 栈和队列:栈和队列都是受限制的线性表,其中栈是只有一端可以插入和删除,可以进行插入和删除的一端称为栈顶,另一端称为栈底;队列是可以一端进行插入,另一端进行删除。

11. 共享栈:利用栈底位置的相对不变性,可以让两个顺序栈共享一个一维数组空间,将两个栈的栈底分别设置在共享栈的两端,两个栈顶向共享空间的中间延伸,这样能够更有效的利用存储空间,两个栈的空间相互调节,只有在整个数组空间被占满后才会发生上溢。

12. 队列的假溢出现象:假溢出是指队列在一端进行插入操作,队尾的值就会增加,在另一端删除,当队尾的值位于最大的时候,就会说明队列已满,但实际在队列的另一端还是有存储空间的,这就是队列的假溢出现象。

13. 循环队列中为什么要空一个位置:为了区分队空和队慢的状态,队空是首尾指针指向同一个位置,队满是尾指针的下一个位置是首指针。

14. 队列在计算机系统中的应用:第一是用于缓冲区,缓冲区是用来解决外部设备与CPU之间速度不匹配的问题,缓冲区主要用队列实现;第二是在CPU进行进程调度时,当某个进程处于就绪态时,就把该进程挂载到进程队列中,等待CPU的调用。

15. 什么是二叉树:二叉树是树的一种,和树一样只有一个根结点,其中每个结点的子节点个数不超过2。

16. 先序序列和中序序列确定一棵二叉树:在先序遍历中,第一个结点一定是二叉树的根结点,而在中序遍历中,根结点将中序序列分割成两个子序列,其中前一个子序列是根结点的左子树的中序序列,后一个子序列是根结点的右子树的中序序列。根据这两个子序列,在先序序列中找到对应的左子序列和右子序列。在先序遍历中,左子序列的第一个结点是左子树的根结点,右子序列的第一个结点是右子树的根结点。如此递归地进行下去,便能唯一的确定这棵二叉树。

17. 树的存储结构:双亲表示法:采用一组连续的空间来存储每个结点,同时在每个结点中增设一个伪指针,指示其双亲结点在数组中的位置,使得每个结点能很快得到其双亲结点,但求结点的孩子需要遍历整个结构;孩子表示法:将每个结点的孩子结点都用单链表链接起来形成一个线性结构,这种存储方式寻找子女的操作非常直接,而寻找双亲的操作非常复杂;孩子兄弟表示法:这种就是最普遍的二叉树存结构,双亲直接指向其孩子结点,最大的优点是可以方便查找结点的孩子,但缺点是寻找其双亲比较麻烦,可以为每个结点增设一个指向父节点的空间。

18. 线索二叉树:线索二叉树就是将二叉链表中的空指针改为前驱或者后继的线索,可以加快查找前驱和后继的速度。

19. 什么是二叉排序树:二叉排序树是递归定义的二叉树,左子树的值小于根结点的值,右子树的值大于根结点的值,同时左子树和右子树都满足二叉排序树的定义。

20. 哈夫曼树:哈夫曼树是带权路径长度最小的二叉树,可以用于最小冗余编码,实现信息高效传输。

21. 满二叉树和完全二叉树:满二叉树是叶子一个也不少的树,而完全二叉树最底层允许在右边缺少连续若干个结点,满二叉树是完全二叉树的一个特例。

22. 平衡二叉树:平衡二叉树是在二叉排序树的基础上做的改进,是左子树和右子树高度之差不超过1。

23. 树转换为二叉树:树中所有相邻兄弟结点之间加一条连线,对树中的每个结点,只保留它与第一个孩子结点之间的连线,删去它与其他孩子结点之间的连线;然后转动整棵树,使之层次分明。

24. 图和树的区别:图和树都是数据的非线性表示,其中树是只有一个根结点,可以有多个子节点,查询任意子节点时都必须从根结点出发;图则没有固定的一个根结点,任意两个结点间都可能相连。

25. 邻接矩阵:邻接矩阵是指用二维数组来存储图中的边的信息,比较适合稠密图;

26. 邻接链表:邻接链表是对图中的顶点建立了一个单链表,单链表中的每个结点都有一个边表,用来存放与这个点有连接的顶点,比较适合稀疏图。如果是有向图的话,边表中存放的是出度的顶点。

27. 逆邻接链表:和邻接链表的区别在于有向图的话边表中存放的是入度的顶点。

28. 邻接多重表:邻接多重表和邻接链表的区别在于无向图,无向图中每个边在邻接表都用两个边表结点表示,而在邻接多重表中只用一个结点,这样对边的操作就比较方便。

29. 十字链表:十字链表适用于有向图,可以很方便的寻找一个顶点的入度和出度信息。

30. 图的遍历:从连通图的某一顶点出发,沿着一些边,访问图中所有的顶点,并且每个顶点只访问一次。

31. 最短路径:在带权有向图中由源点到终点的多条路径中,找到的一条权值之和最小的路径。

32. 最小生成树的概念:最小生成树是图的一个极大连通子图,包含图中n个结点和n-1条边,并且n-1条边的权值之和最小。

33. B树和B+树:B树又称多路平衡查找树,一棵m阶的B树要么是空树,要么每个结点最多只有m条边,最多只有m-1个关键字。B+树是为了满足数据库的查询需求而出现的一种B树的变种,一棵m阶B+树每个结点最多有m棵子树并且结点子树的个数与结点关键字的个数相同。

34. 哈希表:哈希表又称为散列表,是根据关键字的值直接进行访问的数据结构,即它通过把关键字的值映射到表中的一个位置以加快查找速度,其中映射函数被称为散列函数,存放记录的表称为散列表。

35. 什么是哈希冲突,如何解决:哈希冲突是出现在哈希表中的现象,是由于不同的数据映射到同一个位置而引起的冲突,可以使用线性探测法、平方探测法或者链地址法解决。

36. 衡量排序算法好坏的标准:时间效率、空间效率和稳定性。



登录后发布评论

暂无评论,来抢沙发