跳转到内容
NJUPTFreeExams

数据结构 23-24-1 考试复习及回忆

非算法题

  • 第1章，掌握数据概念，数据元素的概念，数据项的概念 【考试的第一道填空题：[ ]是组成数据的、有一定意义的基本单位】

  • 第1章，掌握时间复杂度的计算方法，仅考虑最高次幂 【选择题 (x3+3n2+nlog⁡2n+7n+9)/n(x^3+3n^2+n\log_2{n}+7n+9)/n，问近似时间复杂度】

  • 第4章，基础题1，掌握二维矩阵行优先或列优先存储的地址计算方法，P49 【考试的一道选择题，给了两个计算机中的地址，以及对应的数据下标，请问是行优先或列优先存储？】

  • 第5章，扩展题3，掌握方法: 已知二叉树的先序遍历和中序遍历序列或已知二叉树的后序遍历和中序遍历序列，可以唯一确定一棵二叉树 【考试的第一道大题，给了先序遍历、中序遍历和后序遍历，每个各自挖几个空，第一问填空，然后构造树，有点难度！】

    • 后序遍历中最后一个字母为根结点，中序遍历中根位置的左部分为左子树，右部分为右子树。
    • 前序遍历的第一个为根。中序遍历中，根位置的左边结点都为左子树，右边结点为右子树。
    • 先序和中序、中序和后序可以直接得出二叉树结构。先序和后序无法得出二叉树结构，但可以判断祖先。

  • 第5章，P85，一棵线索二叉树中含有的线索数比分支数多2个。

    • 总分支数（指的是度数）=总结点数-1。因为 二叉树中除了根结点以外，每个结点都有唯一的一个分支指向它。
    • 这一点的推导思路详见 链接：无论是什么样的二叉链表，空线索数由度为1和度为0的结点所提供，其中一个度为1的结点提供1个空线索数，一个度为0的结点提供2个空线索数，即总的空线索数为2∗n0+n12*n_0+n_1，又因为n0=n2+1n_0=n_2+1，所以2∗n0+n1=n0+n1+n2+1=n+12*n_0+n_1=n_0+n_1+n_2+1=n+1。结合上一点可以推出线索数=分支数+2
    • 补充：对任何一个二叉树，若齐叶子结点数为n0n_0，度为2的结点数为n2n_2，则n0=n2+1n_0=n_2+1。

  • 第5章，掌握高度为 h的完全二叉树的叶子结点最多和最少各是多少

    • 最多有 2h−12^h-1个结点，最少有 2h−12^{h-1}个结点

  • 第5章，扩展题6，8，哈夫曼树和哈夫曼编码的作业题必须掌握 【一道大题：1.高度为5的哈夫曼树最少表示几个数据？ 2.已经有1和01来表示数据了，这颗哈夫曼树的高度为5，最多还能表示几个数据。3.常规题目：给定一组权重和字母，让构造哈夫曼树。】

  • 第5章，要掌握树或森林转换为二叉树,反过来，二叉树转换为树或森林,P87，图5.18, 图5.19

  • 第6章，掌握对半搜索的定理 6.1和定理 6.2，掌握利用二叉判定树计算查找成功的平均比较次数，扩展题5，P114 建议参考：链接 【选择题：13个结点的搜索树，平均搜索成功的次数】

    • 定理 6.1：对半搜索算法在成功搜索的情况下，关键字值之间的比较次数不超过⌊log2n⌋+1⌊log_2 n⌋+1。对于不成功的搜索，算法需要做⌊log2n⌋+1⌊log_2 n⌋+1或⌊log2n⌋⌊log_2 n⌋次比较。【考试考了一道填空题。另一道是选择题:如果一棵树结点有15个，搜索了4次就判定失败（成功？），那么这个可能是[]树】
    • 定理 6.2：对半搜索算法在成功搜索的情况下的时间复杂度为O(log2n)O(log_2 n)

  • 第7章，扩展题7，掌握构造二叉平衡树的过程

    • 这个视频讲的好 链接

  • 第8章，扩展题 1、2，能采用线性探查法、二次探查法计算得到散列表

    • 线性探测法：h(key),h(key)+1, h(key)+2

  • 第9章，无向图和有向图中顶点的度与边数的关系。

    • 有向图
      1. 所有顶点的度数之和 等于 边数的二倍。
      2. 所有顶点的入度之和 等于 出度之和。
      3. n个顶点的有向完全图有n*（n-1）条边。
      4. n个顶点的强连通图至少有n条边。
    • 无向图
      1. 所有顶点的度数之和 等于 边数的二倍。
      2. n个顶点的无向完全图有 n（n-1）/2 条边。
      3. n个顶点的连通图至少有 n-1 条边。

  • 第9章，对于同一张图，掌握同时用邻接矩阵和邻接表两种存储结构表示，并能正确计算其存储空间。【给了一个稠密图，说指针大小4字节，权重2字节，点需要4字节，问用邻接矩阵和邻接表哪个需要的空间更多】

  • 第9章，扩展题 18、19，能写出构造步骤和过程

  • 第9章，图的深度优先遍历方法，采用邻接表或邻接矩阵表示图时的 DFS 算法的时间复杂度 链接 【填空题：邻接表表示图时的 DFS 算法的时间复杂度[ ]】

  • 第10童，简单选择、直接插入、冒泡排序和快速排序的方法要掌握，要能写出每趟排序结果 【考试考了四种算法的第一次排序后结果】

  • 第10章，掌握根据排序结果判断排序算法种类的方法，三种简单排序、快排和堆排序 【给定一个第一次排序后结果，问是哪一种排序(快速排序)】

  • 第10章，掌握三种简单排序算法的排序趟数 【考的是简单选择、直接插入、[ ]需要n-1次】

  • 第10章，掌握两路合并排序，两路合并排序算法中两个相邻有序序列合并为一个大的有序序列的算法实现。 【选择题：两个数列按顺序合并，最少需要比较[]次】

算法题

  • 第3章，循环队列的插入、删除操作，能写出程序代码，P34. 【考试考的很简单】
  • 第5章，扩展题14，二叉树遍历算法，P80，程序5.7，设计算法并写出程序代码 【考试最后一题程序设计题，考了怎么统计一棵树的叶子结点个数，实验二的内容】
  • 第9章，图的邻接表存储结构程序9.11 的深度优先遍历 DFS 和DFSGraph 算法，P163 【考试考了时间复杂度，没考大题】

@Dilettante258