数据结构(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.相对于一般的锦标赛树,败者树有什么优势?为什么?