数据结构(70)
判断题 (12*2=24)
(1)nlogloglogn = Ο(⌊logn⌋!)
(2)交换哈夫曼树的不同深度的节点，编码长度必然改变
(3) 伸展树若不具备局部性，平摊复杂度就无法达到 O(logn) 或
对于不符合局部性原理的访问，splay 的分摊复杂度不是 O(logn)
(4)即使不使⽤改进的 next[]，kmp 依然可以达到线性的时间复杂度
(5)对于二叉树，通过先序遍历和后序遍历不能确定其层次遍历
(6) 拥有 2019 个节点的真二叉树的种数比 2018 个所能够成的合法序列要
少
(7)对于叶节点数量为 2018 的⼆叉树，对其进行层次遍历时辅助队列大小
最多不超过 2018
(8)插⼊排序每次插⼊数据，即使不增加循环节，也不⾄减少
(9)交换两个逆序对，必然会减少总逆序对数
(10)如果基数排序底层采⽤不稳定的算法，那么得到的结果可能是不正确
的
(11)函数的调⽤栈中如果有相同的函数，则他们必然紧邻
(12)如果插⼊的关键码独⽴均匀分布，堆的插⼊操作平均 O(1)
简答题(8*4=32)
1.逆波兰表达式为什么相比普通表达式计算效率更高，既然转换为逆波
兰式已经消耗掉了一次相当于普通计算的时间，那这样的转换价值何在？
2.用 DFS 搜索图，何时标前向边，何时标后向边
3.相对于选择排序，插入排序有哪些优点？2 条
4.Dijstra 在处理稠密图时为何使用多叉堆替换常规的完全二叉堆，多叉堆
的分叉数又如何确定？
5.相比于开放散列，封闭散列有什么优点？2 条
6.相对于一般的锦标赛树，败者树有什么优势？为什么？
资源评论
wangkan0202
- 粉丝: 0
- 资源: 6
