algorithms/fds/mistakes

[giscus[bot]]

algorithms/fds/mistakes

NoughtQ的笔记本

https://note.noughtq.top/algorithms/fds/mistakes

[John15380]

Chap 3 Q1 我认为是因为可以另外加一个count纪录循环队列中的元素个数，这样rear和front只要留一个即可
Chap 9 Q4 选C 感觉o1对图相关的题目也不一定能正确解答[ac01]

[NoughtQ]

• 对于 Chap 3 Q1，我现在想通了，但我觉得可能甚至都不需要这个count吧，反正最坏情况下在循环队列遍历一遍总能找到要插入的位置或者要删除的节点吧

• 对于 Chap 9 Q4，我问了deepseek（比ChatGPT靠谱点吧，免费版的越来越zz了），它的回答也是C，我想是想通了，但是不知道怎么说好，画画图应该就能判断了吧(x)

我有点好奇的是，话说怎么现在在看FDS的笔记？

[John15380]

确实
我这学期上的是别的学院的数据结构[ac06]
deepseek感觉确实顶hhh

[p3rm1t]

Chap4 Q4，可以通过Firstchild-Nextsibling把树转化为二叉树，而二叉树是可以用一维数组表示的，把空节点空出
我的理解是这样！

[NoughtQ]

问题是这道题没有讲清楚到底是几叉树，这样的话每个子树可以有任意多个孩子，所以我还是不太理解😵‍💫

[kenqia]

其实我感觉可以通过“约定”来用数组唯一表示一颗树，比如已知该树度为m，然后我们依旧用层序遍历数列表示这个树，但是我们会为每一层中缺少的节点添加一个标记。这样放到数组里面第一层一定是1个格子，第二层m个，第三个m^2个格子占据，其中标记格子就代表不存在节点，这样可以唯一表示。

[NoughtQ]

但约束是我们自己设的，题目没设，所以我还是认为题目出的不合理（不想管这道题了）

[p3rm1t]

不管几叉树都可以呀，用Firstchild-Nextsibling转化的时候不是都可以转成二叉树嘛

[NoughtQ]

哦哦，有道理啊（好久没碰算法，大脑退化了（悲）），稍后我会补充的，感谢分享🙏

[kenqia]

Chap 3Q1，应该是说只需要一个尾巴指针指向最后一个节点，而这个节点指向dummy节点，就可以完全利用这个尾巴指针常数时间enqueue（插入，尾巴跟上）和dequeue（把dummy前的节点移除）。

Chap 9 Q4：题目主要指的是在每个递归结束前（也就是大括号前面的那一条语句）打印出数值，就像是后序遍历一样，所以是倒着的

[NoughtQ]

C3Q1：你这里的尾巴指针是指 rear poniter吗？我想题目的意思是每个节点都有一个 rear pointer，指向后一个节点，所以我感觉我们的理解有些偏差...

C9Q4：这道题我已经想通了，忘记更新了doge