清华大学-912-2019-真题版.pdfVIP

各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 清华大学 912 考研真题 回忆版 数据结构(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.相对于一般的锦标赛树，败者树有什么优势？为什么？ 获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 7.红黑树对AVL树所不具有的优势？为什么？ 8.KMP算法对蛮力算法的优势，在什么条件足够明显？为什么？ 算法题(7+3+4=14) 第K大节点 struct BinNode{ int size; // 当前节点和孩⼦总数 BinNode *lchild,*rchild; }; BinNode *rank(BinNode* t,int k){ //有效代码⾏数不超过 12 ⾏ 微 // 求出后序遍历的第k大的结点 信 //不可直接模拟后续遍历，性能不能满足，会直接判0分 公 // 时间复杂度和空间复杂度不超过O(depth(x))(x为第k大的节点) } 众 号 1.实现 ，填写代码已完成上述功能 （不超过12行） 2.原理 计 ，解释说明代码思想 200字，可附一图 3.证明时间、空间复杂度