2023-2024-1 20231323《计算机基础与程序设计》第七周学习总结

作业信息

教材学习内容总结

1.数组是一种线性数据结构，它以连续的内存块来存储元素。每个元素都可以通过其索引来访问。由于数组的大小在创建时就已经确定，因此不能很好地扩展或收缩。链表则不需要连续的内存块，每个节点可以存储数据以及指向下一个节点的指针。所以链表可以动态地扩展或收缩，但访问特定位置的元素可能需要遍历整个链表。
2.顾名思义，无序列表的各项目通常没有特定的顺序，而有序列表的各项目则按照某种顺序排列。
3.栈是一种后进先出（LIFO）的数据结构，也就是最后添加到栈中的元素会先被删除。添加和删除操作都发生在同一点，称为栈顶。而队列是一种先进先出（FIFO）的数据结构，即最先添加到队列中的元素会最先被删除。队列中元素的添加和删除发生在不同的位置，分别称为队尾和队头。栈常用于实现深度优先搜索（DFS）、括号匹配、函数调用堆栈等；而队列常用于实现广度优先搜索（BFS）、CPU任务调度、缓冲处理等。
4.（1）一个二叉树是一个树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉检索树（也叫二叉排序树或二叉查找树）是一种特殊的二叉树，其中每个节点的值大于其左子树中的所有节点的值，且小于其右子树中的所有节点的值。
（2）二叉树被广泛用于各种算法和数据结构中，如表达式树、决策树、堆等。它们可以表示复杂的结构，并可用于执行各种计算任务。二叉检索树：二叉检索树主要用于高效地查找、插入和删除数据。在二叉检索树中，查找一个元素的时间复杂度为O(log n)，其中n是树中元素的数量。
5.树：树是一种层次结构，它有一个根节点，其他节点都是根节点的子孙节点。树中的每个节点最多有两个子节点，通常称为左子节点和右子节点。树表示一种“层次”关系。树中不存在环，它有一个明确的层次结构，从根节点开始，逐层向下。常见的树操作包括遍历（前序、中序、后序）、查找节点、插入节点、删除节点等。
图：图是由一组顶点（节点）和一组边构成的，边将某些顶点连接在一起。图可以用来描述网络、社交关系、交通路线等各种复杂的关系。图表示一种“网络”关系。
图可以是无向的或有向的。在无向图中，边没有方向；在有向图中，边有方向，表示从一个节点到另一个节点的关系。常见的图操作包括遍历（深度优先搜索、广度优先搜索）、查找最短路径、查找子图、添加边、删除边等。
6.子程序是一个或一组程序代码块，可以被主程序多次调用执行。它可以是自定义的函数或子例程，具有独立的名称和参数列表。子程序通常用于封装一些常用的功能或算法，以提高代码的可重用性和可维护性。
参数是指在调用子程序时传递给子程序的输入值。参数分为形参（形式参数）和实参（实际参数）两种。形参是在子程序定义时声明的变量，用于接收传递给子程序的输入值。实参是在主程序调用子程序时传递给子程序的实际值。
7.值传递（值参）：在值传递中，函数接收的是实际参数的拷贝，也就是说，函数对参数的任何修改都仅限于函数内部，不会影响到实际参数。
引用传递（引用参数）：在引用传递中，函数接收的是实际参数的地址或引用，也就是说，函数内部对参数的任何修改都会直接影响到实际参数。

教材学习中的问题和解决过程

• 问题1：不了解图的深度遍历与广度遍历
  解决方案：查找资料，询问gpt
  深度优先遍历（DFS）是从某个顶点出发，访问此顶点，然后从该顶点的第一个未被访问的邻接点出发，访问与该邻接点相邻的所有未被访问的顶点，直到所有的顶点都被访问到。
  广度优先遍历（BFS）是按照广度方向搜索，从某个顶点出发，访问该顶点，然后访问与该顶点相邻的所有未被访问过的顶点，然后再从这些邻接点中找出未被访问过的邻接点，依次类推，直到所有的顶点都被访问到。

• 问题2：不理解树的前序、中序与后序遍历
  解决方案：查找资料，询问gpt
  前序遍历：（1）访问根节点。（2）前序遍历左子树。（3）前序遍历右子树。
  中序遍历：（1）中序遍历左子树。（2）访问根节点。（3）中序遍历右子树。
  后序遍历：（1）后序遍历左子树。（2）后序遍历右子树。（3）访问根节点。

基于AI的学习

上周考试错题总结

1.An array is a named homogeneous collection of items in which individual items are accessed by an index.
正确答案： 正确

• 数组的命名更多是基于它的顺序排列，而非特定名称。

2.The general case of a recursive solution determines when the recursion stops.
正确答案： 错误

• 如果递归解决方案没有基本情况或基于其他条件终止，那么这句话可能是错误的。

3.An algorithm is a calculation that determines how long it will take to solve a problem.
正确答案： 错误

• 算法不仅是关于计算的，更是关于问题解决的方法和步骤的。

4.During top-down design, a concrete step is one that needs to be expanded further.
正确答案： 错误

• 在自上而下的设计过程中，需要进一步详细说明的具体步骤。

学习进度条

• 计划学习时间:25小时

• 实际学习时间:10小时